Esercizio - Newton su una radice tripla e metodo modificato

Teoria: Metodo di Newton, metodo delle secanti e ordine di convergenzaOrdine di convergenza p: |e_{k+1}| ≈ C|e_k|^p (p = 1 lineare, p = 2 quadratica: le cifre corrette raddoppiano a ogni passo). Newton x_{k+1} = x_k − f(x_k)/f'(x_k): zero della tangente, ordine 2 per radici semplici con e_{k+1} ≈ f''(α)/(2f'(α)) e_k²; per radici di molteplicità m è solo lineare con tasso (m−1)/m (si recupera con x − m f/f'). Secanti: sostituisce f' con un rapporto incrementale, ordine (1+√5)/2 ≈ 1,618, una sola valutazione di f per passo. Newton richiede un x_0 abbastanza vicino: può ciclare o divergere.Metodo di Newton, metodo delle secanti e ordine di convergenza → (radici multiple).

Testo

Si consideri $f(x) = (x-2)^3(x+1)$.

• (a) Determinare le radici e le loro molteplicità. Calcolare $f'$.
• (b) Eseguire tre passi del metodo di Newton da $x_0 = 3$ e calcolare il rapporto $e_k/e_{k-1}$. Cosa ci si aspetta dalla teoria?
• (c) Eseguire tre passi del metodo modificato $x_{k+1} = x_k - m\,\frac{f(x_k)}{f'(x_k)}$ con la molteplicità $m$ corretta.
• (d) Domanda teorica: se la molteplicità non fosse nota, come si può stimarla dai rapporti $e_k/e_{k-1}$ di Newton?

Soluzione

(a) Radici

$f$ ha la radice $x=2$ con molteplicità $m=3$ e la radice $x=-1$ semplice. Derivata (regola del prodotto): $$f'(x) = 3(x-2)^2(x+1) + (x-2)^3 = (x-2)^2\bigl[3(x+1) + (x-2)\bigr] = (x-2)^2(4x+1).$$ Si vede che $f'(2) = 0$: Newton non soddisfa le ipotesi del teorema di convergenza quadratica.

(b) Newton da $x_0 = 3$

$f(3) = 1\cdot 4 = 4$, $f'(3) = 1\cdot 13 = 13$, quindi $x_1 = 3 - \frac4{13} = 2{,}69231$. $f(2{,}69231) = (0{,}69231)^3\cdot 3{,}69231 = 0{,}33181\cdot 3{,}69231 = 1{,}2252$; $f'(2{,}69231) = (0{,}69231)^2(4\cdot 2{,}69231 + 1) = 0{,}47929\cdot 11{,}76923 = 5{,}6410$; $x_2 = 2{,}69231 - \frac{1{,}2252}{5{,}6410} = 2{,}69231 - 0{,}21720 = 2{,}47511$.

Teoria: per una radice di molteplicità $m$ Newton converge linearmente con tasso $\frac{m-1}{m} = \frac23 = 0{,}667$. I rapporti $0{,}692,\ 0{,}686,\ 0{,}681,\dots$ si avvicinano a $0{,}6667$ (da otto iterazioni, $0{,}6691$). Convergenza lentissima: dopo $8$ passi l'errore è ancora $4{,}4\cdot 10^{-2}$.

(c) Metodo modificato con $m=3$

• $x_1 = 3 - 3\cdot\frac{4}{13} = 3 - 0{,}92308 = 2{,}07692$; $e_1 = 7{,}69\cdot 10^{-2}$.
• $x_2 = 2{,}00063573$; $e_2 = 6{,}36\cdot 10^{-4}$.
• $x_3 = 2{,}000000045$; $e_3 = 4{,}5\cdot 10^{-8}$.

Il rapporto $e_k/e_{k-1}^2$ vale $0{,}107$ e $0{,}111$: convergenza di nuovo quadratica. In $3$ passi l'errore scende a $4{,}5\cdot10^{-8}$, mentre Newton standard dopo $8$ passi è ancora a $4{,}4\cdot10^{-2}$.

(Per il calcolo di $x_2$: $f(2{,}07692) = (0{,}07692)^3\cdot 3{,}07692 = 4{,}552\cdot 10^{-4}\cdot 3{,}07692 = 1{,}4006\cdot 10^{-3}$; $f'(2{,}07692) = (0{,}07692)^2(4\cdot 2{,}07692 + 1) = 5{,}917\cdot 10^{-3}\cdot 9{,}30769 = 5{,}5075\cdot 10^{-2}$; $x_2 = 2{,}07692 - 3\cdot\frac{1{,}4006\cdot 10^{-3}}{5{,}5075\cdot 10^{-2}} = 2{,}07692 - 0{,}07629 = 2{,}00063$.)

(d) Stima della molteplicità

Se Newton converge linearmente con tasso $\rho = \frac{m-1}{m}$, allora $m = \frac1{1-\rho}$. Osservando $\rho \approx \frac{|x_{k+1}-x_k|}{|x_k - x_{k-1}|}$ (si usano gli incrementi perché $\alpha$ non è noto) si ha $m \approx \frac1{1-\rho}$: con $\rho \approx 0{,}67$ si ottiene $m \approx 3$. La stima si arrotonda all'intero più vicino e poi si usa il metodo modificato (o si applica Newton a $\frac{f}{f'}$, che ha la radice semplice).

Risultati. $m = \mathbf{3}$; Newton: tasso $\to \mathbf{2/3}$; modificato: $x_3 = \mathbf{2{,}000000045}$ (errore $4{,}5\cdot10^{-8}$).

Errori tipici

• Applicare Newton a una radice multipla aspettandosi la quadratica: ci si accorge dal rapporto $e_k/e_{k-1}$ costante e diverso da $0$.
• Usare $m$ sbagliato nel metodo modificato: con $m$ troppo grande ($m=4$) l'iterazione supera la radice e oscilla.