Metodo Newton Tangenti e ordine di convergenza

[cestra]

Salve ragazzi ecco il mio problema.

Dimostrare che il metodo di Newton o delle Tangenti converge linearmente alla radice 0 per la funzione \( \displaystyle {f{{\left({x}\right)}}}={{x}}^{{3}}-{x} \). Con che ordine di conergenza convergerà alla radice \( \displaystyle {x}={1} \) e perchè?

Punto1.
Dimostrare che il metodo di Newton o delle Tangenti converge linearmente alla radice 0 per la funzione \( \displaystyle {f{{\left({x}\right)}}}={{x}}^{{3}}-{x} \)
Innanzi tutto posso scomporre la funzione in \( \displaystyle {x}{\left({{x}}^{{2}}-{1}\right)} \) e di conseguenza ho 3 radici reali \( \displaystyle {x}{0}={1}{x}{1}=-{1}{x}{2}={0} \). Siccome mi chiede di dimostrare la convergenza LINEARE sulla radice 0, io so che questo è impossibile visto che ha molteplicità 1 e quindi ha una convergenza quadratica e non lineare. Ma come lo posso dimostrare?

Punto2
Con che ordine di conergenza convergerà alla radice \( \displaystyle {x}={1} \) e perchè
Vorrei sapere come trovare questo maledetto p che mi indica l'ordine di convergenza per questa radice!! Suppongo che sia 2 visto che la radice 1 è una radice semplice. Ma come posso determinarlo?

Grazie a tutti

[gugo82]

[mod="Gugo82"]Sposto in Analisi Numerica e Ricerca Operativa.[/mod]

[valepu]

Salve,

Sto studiando calcolo numerico per un esame all'università e mi sono imbattuto esattamente nello stesso esercizio. spero non sia un problema se faccio il bump di questo messaggio (ho letto il regolamento prima di postare, e non ho trovato nulla a riguardo)

L'ordine di convergenza lo si studia facendo il limite del rapporto tra l'errore al passo k+1 e quello al passo k \( \displaystyle lim_{k \to \infty}\left(\frac{|e_k_+_1|}{|e_k|}\right) = \frac{|2x_k^2|}{|3x_k^2-1|} \) (ho tagliato un po' di passaggi, comunque questa è la soluzione finale). Alla fine il risultato è 2/3 (poichè Xk tende a 0), il che dimostrerebbe che il metodo di Newton converge linearmente per x=0 (p=1, c=2/3)

Il professore però ci ha mostrato un teorema secondo cui se una funzione è derivabile 2 volte in un intorno della radice cercata, e la derivata prima è diversa da 0 in questo intorno allora la funzione converge quadraticamente.

A me pare che in questo caso le ipotesi del teorema siano verificate, basta prendere un intervallo più piccolo di \( \displaystyle -\sqrt{\frac{1}{3}}, +\sqrt{\frac{1}{3}} \) (che sarebbero gli 0 della derivata prima)

a questo punto non so più che fare

[canemacchina]

Per la verità l'ordine di convergenza è definito così:
chiamando \( \displaystyle e_i \) l'errore commesso al passo \( \displaystyle i \) , diciamo che un metodo ha ordine di convergenza \( \displaystyle p \) se \( \displaystyle p \) è il più grande reale \( \displaystyle k \; t.c. \;lim_{i\rightarrow\infty}\dfrac{|e_{i+1}|}{|e_i|^p} = c < \infty \)

Certamente può essere che anche \( \displaystyle lim_{i\rightarrow\infty}\dfrac{|e_{i+1}|}{|e_i|^q} = c < \inft\; \) con \( \displaystyle q

Dire che \( \displaystyle lim_{i\rightarrow\infty}\dfrac{|e_{i+1}|}{|e_i|} = \dfrac{|2x_k^2|}{|3x_k^2-1|} \) quindi non implica necessariamente che l'ordine sia 1.
Piuttosto, per il metodo di Newton vale questo Teorema (indichiamo con \( \displaystyle \overline{x} \) la radice di \( \displaystyle f \) ):
Se \( \displaystyle f\in \mathcal{C}^2 \) e la successione \( \displaystyle x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)} \) converge a \( \displaystyle \overline{x} \) allora l'ordine di convergenza è 2.

Per la dimostrazione, basta sviluppare con Taylor \( \displaystyle f(\overline{x}) \) in \( \displaystyle x_n \) , ovvero:
\( \displaystyle f(\overline{x}) =\\
= f(x_n) + f'(x_n)(\overline{x} - x_n) + \dfrac{1}{2}f''(\xi)(\overline{x} - x_n)^2 =\\
= f'(x_n)\left(\dfrac{f(x_n)}{f'(x_n)} + \overline{x} - x_n\right) + \dfrac{1}{2}f''(\xi)(\overline{x} - x_n)^2 =\\
= f'(x_n)(\overline{x} - x_{n+1}) + \dfrac{1}{2}f''(\xi)(\overline{x} - x_n)^2 =\\
= f'(x_n)e_{n+1} + \dfrac{1}{2}f''(\xi)e_n^2=0. \)
Da cui deriva che
\( \displaystyle \dfrac{e_{n+1}}{e_n^2} = \dfrac{1}{2}\dfrac{f''(\xi)}{f'(x_n)} \) .
Adesso possiamo calcolare il limite, e avendo supposto la convergenza del metodo e sapendo che \( \displaystyle \xi\in I(\overline{x}, x_n) \) (un intorno della radice)
\( \displaystyle lim_{n\rightarrow\infty}\dfrac{e_{n+1}}{e_n^2} = \dfrac{1}{2}\dfrac{f''(\overline{x})}{f'(\overline{x})} \) , che è ben definito in quanto per ipotesi \( \displaystyle f\in \mathcal{C}^2 \)
Questo quindi dimostra la convergenza quadratica del metodo di Newton alle radici semplici.

A mio avviso questa dimostrazione risponde già alle due domande. Alla prima risponde "Errato, converge quadraticamente perché 0 è radice semplice", alla seconda risponde "converge quadraticamente perché 1 è radice semplice".

Rimarrebbe da dimostrare la convergenza di Newton alle due radici, ma questo è assicurato dal Teorema del punto fisso, e che in pratica ci assicura la convergenza locale del metodo di Newton.
Spero di aver capito bene le domande...