Esercizio - Reciproco con Newton senza divisioni e intervallo di convergenza

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 →.

Testo

Un microcontrollore non ha l'istruzione di divisione. Per calcolare $\frac1a$ ($a>0$) si applica il metodo di Newton all'equazione $f(x) = \frac1x - a = 0$.

• (a) Ricavare l'iterazione e verificare che usa solo prodotti e differenze.
• (b) Dimostrare che $e_{k+1} = -a\,e_k^2$ (con $e_k = x_k - \frac1a$) e dedurne la condizione di convergenza sul dato iniziale.
• (c) Per $a = 3$ e $x_0 = 0{,}3$ calcolare $x_1, x_2, x_3$ e gli errori.
• (d) Per $a = 7$ confrontare $x_0 = 0{,}1$ con $x_0 = 0{,}3$.

Soluzione

(a) Iterazione

$f(x) = \frac1x - a$, $f'(x) = -\frac1{x^2}$. Allora $$x_{k+1} = x_k - \frac{\frac1{x_k} - a}{-\frac{1}{x_k^2}} = x_k + x_k^2\left(\frac1{x_k} - a\right) = x_k + x_k - a x_k^2 = x_k\,(2 - a\,x_k).$$ Due prodotti e una differenza, nessuna divisione.

(b) Errore e condizione di convergenza

Si pone $r = \frac1a$ (la radice) e $x_k = r + e_k$. Allora $$x_{k+1} - r = x_k(2 - ax_k) - r.$$ Con $a x_k = 1 + a e_k$ (perché $a r = 1$): $2 - ax_k = 1 - ae_k$ e $$x_{k+1} = (r + e_k)(1 - ae_k) = r - a r e_k + e_k - a e_k^2 = r - e_k + e_k - ae_k^2 = r - ae_k^2,$$ dove si è usato $ar = 1$. Quindi $$e_{k+1} = -a\,e_k^2.$$ Convergenza quadratica con costante $a$ (coincide con $\frac{f''(r)}{2f'(r)} = \frac{2/r^3}{2\cdot(-1/r^2)} = -\frac1r = -a$ ✓). Condizione: $|e_{k+1}| < |e_k| \iff a|e_k| < 1 \iff |e_0| < \frac1a$. Inoltre $e_{k+1} \le 0$ sempre, quindi dopo il primo passo $x_k \le r$. Se $0 < x_0 < \frac2a$ allora $e_0 \in\,]-\frac1a, \frac1a[$ e l'iterazione converge. Se $x_0 > \frac2a$ ($e_0 > \frac1a$) l'errore cresce in modulo e $x_1 = x_0(2 - ax_0) < 0$: diverge a $-\infty$.

(c) $a = 3$, $x_0 = 0{,}3$

Radice $r = 0{,}33333\ldots$; $x_0 = 0{,}3 \in\,]0, \frac23[$ ✓.

• $x_1 = 0{,}3\,(2 - 0{,}9) = 0{,}3\cdot 1{,}1 = 0{,}33$; $e_1 = -3{,}33\cdot 10^{-3}$.
• $x_2 = 0{,}33\,(2 - 0{,}99) = 0{,}33\cdot 1{,}01 = 0{,}3333$; $e_2 = -3{,}33\cdot 10^{-5}$.
• $x_3 = 0{,}3333\,(2 - 0{,}9999) = 0{,}3333\cdot 1{,}0001 = 0{,}33333333$; $e_3 = -3{,}33\cdot 10^{-9}$.

Controllo: $e_1 = -3\,e_0^2 = -3\cdot (3{,}33\cdot 10^{-2})^2 = -3{,}33\cdot 10^{-3}$ ✓; $e_2 = -3\,e_1^2 = -3{,}33\cdot 10^{-5}$ ✓. Le cifre corrette sono $2$, $4$, $8$: raddoppiano.

(d) $a = 7$

$r = 0{,}142857\ldots$ e $\frac2a = 0{,}2857$.

• $x_0 = 0{,}1 \in\,]0,\,0{,}2857[$: $x_1 = 0{,}1\,(2 - 0{,}7) = 0{,}13$; $x_2 = 0{,}13\,(2 - 0{,}91) = 0{,}1417$; $x_3 = 0{,}1417\,(2 - 0{,}9919) = 0{,}14284777$; errori $-1{,}29\cdot 10^{-2},\ -1{,}16\cdot 10^{-3},\ -9{,}4\cdot 10^{-6}$; rapporto $e_{k+1}/e_k^2 = -7$ ✓.
• $x_0 = 0{,}3 > \frac27 = 0{,}2857$: $x_1 = 0{,}3\,(2 - 2{,}1) = -0{,}03$, $x_2 = -0{,}0663$, $x_3 = -0{,}1634$, $x_4 = -0{,}5136$, $x_5 = -2{,}873$: diverge.

Risultati. $x_{k+1} = x_k(2 - ax_k)$; $e_{k+1} = -ae_k^2$; converge per $0<x_0<\frac2a$; $\frac13 \approx \mathbf{0{,}33333333}$ in tre passi.

Errori tipici

• Pensare che serva $x_0$ "vicino" in senso generico: qui l'intervallo di convergenza è esplicito, $]0,\frac2a[$, e basta un'approssimazione grossolana (ad esempio una tabella o una potenza di $2$).
• Dimenticare il segno: $e_{k+1} = -ae_k^2 \le 0$, quindi dopo il primo passo si resta sempre sotto la radice.