Esercizio - Newton per x = cos x, confronto con il punto fisso e costante asintotica

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 →; l'iterazione $x_{k+1} = \cos x_k$ è nella nota Metodo di bisezione e iterazioni di punto fissoBisezione: se f è continua e f(a)f(b) < 0 si dimezza l'intervallo tenendo la metà con il cambio di segno; dopo n passi |c_n − α| ≤ (b−a)/2^(n+1), cioè un bit di precisione per iterazione (convergenza lineare, sempre garantita). Punto fisso x = g(x): se g manda [a,b] in sé con |g'| ≤ L < 1 (contrazione) il punto fisso è unico, l'iterazione x_{k+1} = g(x_k) converge da ogni x_0 e |x_k − α| ≤ L^k/(1−L)·|x_1−x_0|; l'errore si moltiplica per circa g'(α) a ogni passo. Una stessa equazione ha molte riscritture x = g(x), alcune convergenti e altre no.Metodo di bisezione e iterazioni di punto fisso →.

Testo

Si cerca la soluzione di $\cos x = x$ ($\alpha = 0{,}7390851332$), cioè lo zero di $f(x) = x - \cos x$.

• (a) Scrivere l'iterazione di Newton e verificarne le ipotesi.
• (b) Eseguire a mano tre passi da $x_0 = 1$, riportando $f(x_k)$, $f'(x_k)$ ed errore.
• (c) Calcolare la costante asintotica prevista dalla teoria e confrontarla con $e_k/e_{k-1}^2$.
• (d) Confrontare il numero di iterazioni con la sola iterazione di punto fisso $x_{k+1} = \cos x_k$ (che richiede $34$ passi per $10^{-6}$).

Soluzione

(a) Iterazione

$f'(x) = 1 + \sin x$, che per $x\in[0,1]$ è tra $1$ e $1{,}84$, quindi non si annulla. La radice è semplice ($f'(\alpha) = 1 + \sin\alpha = 1{,}6736 \ne 0$) e $f$ è $C^2$: vale il teorema di convergenza locale quadratica. $$x_{k+1} = x_k - \frac{x_k - \cos x_k}{1 + \sin x_k}.$$

(b) Tre passi da $x_0 = 1$

Passaggi: $x_1 = 1 - \frac{0{,}459698}{1{,}841471} = 1 - 0{,}249636 = 0{,}750364$; $x_2 = 0{,}7503639 - \frac{0{,}01892}{1{,}68190} = 0{,}7503639 - 0{,}011251 = 0{,}7391129$; $x_3 = 0{,}7391129 - \frac{4{,}646\cdot 10^{-5}}{1{,}67363} = 0{,}7391129 - 2{,}776\cdot 10^{-5} = 0{,}7390851$. Le cifre corrette sono $0$, $1$, $4$, $9$: dopo il primo passo raddoppiano.

(c) Costante asintotica

$f'' = \cos x$. La teoria dà $$C = \frac{f''(\alpha)}{2f'(\alpha)} = \frac{\cos\alpha}{2(1 + \sin\alpha)} = \frac{0{,}739085}{2\cdot 1{,}673612} = \mathbf{0{,}2208}.$$ Dalla tabella: $\frac{e_2}{e_1^2} = \frac{2{,}776\cdot 10^{-5}}{(1{,}128\cdot 10^{-2})^2} = 0{,}218$ e $\frac{e_3}{e_2^2} = \frac{1{,}70\cdot 10^{-10}}{(2{,}776\cdot 10^{-5})^2} = 0{,}2208$ ✓ (e $0{,}166$ al primo passo, ancora lontano dalla zona asintotica).

(d) Confronto

Il punto fisso $g = \cos$ ha $|g'(\alpha)| = \sin\alpha = 0{,}6736$: convergenza lineare, una cifra decimale ogni $5{,}8$ passi circa, $34$ iterazioni per $10^{-6}$. Newton è il punto fisso con $g_N(x) = x - \frac{x - \cos x}{1 + \sin x}$ per cui $g_N'(\alpha) = 0$: con $3$ passi si ha già $e_3 \approx 1{,}7\cdot 10^{-10}$. Ogni passo di Newton costa una valutazione di $\cos$, una di $\sin$ e una divisione, ma $3$ passi $\ll$ $34$.

Risultati. $x_1 = \mathbf{0{,}750364}$, $x_2 = \mathbf{0{,}739113}$, $x_3 = \mathbf{0{,}7390851}$; $C = \mathbf{0{,}2208}$; $3$ passi contro $34$.

Errori tipici

• Scambiare la costante di Newton con $|g'(\alpha)|$ del punto fisso $\cos$: per Newton $g'(\alpha) = 0$ e la costante è $\frac{f''}{2f'}$.
• Confrontare gli errori con il valore di $f$: $f(x_k) \approx f'(\alpha)\,e_k$, non coincidono (fattore $1{,}67$).