Metodo Newton Tangenti e ordine di convergenza

[cestra1]

Salve ragazzi ecco il mio problema.

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

Punto1.
Dimostrare che il metodo di Newton o delle Tangenti converge linearmente alla radice 0 per la funzione $f(x)=x^3-x$
Innanzi tutto posso scomporre la funzione in $x(x^2-1)$ e di conseguenza ho 3 radici reali $x0=1 x1=-1 x2=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 $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 [tex]lim_{k \to \infty}\left(\frac{|e_k_+_1|}{|e_k|}\right) = \frac{|2x_k^2|}{|3x_k^2-1|}[/tex] (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 [tex]-\sqrt{\frac{1}{3}}, +\sqrt{\frac{1}{3}}[/tex] (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 [tex]e_i[/tex] l'errore commesso al passo [tex]i[/tex], diciamo che un metodo ha ordine di convergenza [tex]p[/tex] se [tex]p[/tex] è il più grande reale [tex]k \; t.c. \;lim_{i\rightarrow\infty}\dfrac{|e_{i+1}|}{|e_i|^p} = c < \infty[/tex]

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

Per la dimostrazione, basta sviluppare con Taylor [tex]f(\overline{x})[/tex] in [tex]x_n[/tex], ovvero:
[tex]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.[/tex]
Da cui deriva che
[tex]\dfrac{e_{n+1}}{e_n^2} = \dfrac{1}{2}\dfrac{f''(\xi)}{f'(x_n)}[/tex].
Adesso possiamo calcolare il limite, e avendo supposto la convergenza del metodo e sapendo che [tex]\xi\in I(\overline{x}, x_n)[/tex](un intorno della radice)
[tex]lim_{n\rightarrow\infty}\dfrac{e_{n+1}}{e_n^2} = \dfrac{1}{2}\dfrac{f''(\overline{x})}{f'(\overline{x})}[/tex], che è ben definito in quanto per ipotesi [tex]f\in \mathcal{C}^2[/tex]
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...