Salta al contenuto
Note per Studenti Esercizio - Secanti contro Newton per la radice di 2 e un ciclo di Newton

Esercizio - Secanti contro Newton per la radice di 2 e un ciclo di Newton

In questa pagina 3

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

  • (a) Applicare il metodo delle secanti a f(x)=x2−2f(x) = x^2 - 2 con x0=1x_0 = 1, x1=2x_1 = 2 e calcolare x2,…,x5x_2, \dots, x_5 con i relativi errori rispetto a 2=1,41421356237\sqrt2 = 1{,}41421356237.
  • (b) Verificare che ek+1ekek−1\frac{e_{k+1}}{e_ke_{k-1}} tende alla costante prevista dalla teoria e stimare l'ordine.
  • (c) Confrontare il costo con Newton (x0=2x_0 = 2) per ottenere un errore sotto 10−910^{-9}, contando le valutazioni di ff e di f′f'.
  • (d) Domanda teorica: mostrare che Newton applicato a f(x)=x3−2x+2f(x) = x^3 - 2x + 2 con x0=0x_0 = 0 cicla, e dire come procedere per trovare la radice reale.

Soluzione

(a) Secanti

La formula è xk+1=xk−f(xk)xk−xk−1f(xk)−f(xk−1)x_{k+1} = x_k - f(x_k)\dfrac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}, con f(1)=−1f(1) = -1 e f(2)=2f(2) = 2.

  • x2=2−2⋅2−12−(−1)=2−23=1,33333x_2 = 2 - 2\cdot\dfrac{2-1}{2-(-1)} = 2 - \dfrac23 = 1{,}33333; f(x2)=1,77778−2=−0,22222f(x_2) = 1{,}77778 - 2 = -0{,}22222.
  • x3=1,33333−(−0,22222)⋅1,33333−2−0,22222−2=1,33333+0,22222⋅−0,66667−2,22222=1,33333+0,22222⋅0,3=1,4x_3 = 1{,}33333 - (-0{,}22222)\cdot\dfrac{1{,}33333 - 2}{-0{,}22222 - 2} = 1{,}33333 + 0{,}22222\cdot\dfrac{-0{,}66667}{-2{,}22222} = 1{,}33333 + 0{,}22222\cdot 0{,}3 = 1{,}4; f(x3)=−0,04f(x_3) = -0{,}04.
  • Da qui conviene la forma semplificata, valida per x2−2x^2 - 2: xk+1=xkxk−1+2xk+xk−1x_{k+1} = \dfrac{x_kx_{k-1} + 2}{x_k + x_{k-1}}. Con x3=1,4x_3 = 1{,}4 e x2=43x_2 = \frac43: x4=1,4⋅1,33333+21,4+1,33333=3,866672,73333=1,414634x_4 = \dfrac{1{,}4\cdot 1{,}33333 + 2}{1{,}4 + 1{,}33333} = \dfrac{3{,}86667}{2{,}73333} = 1{,}414634.
  • x5=1,414634⋅1,4+21,414634+1,4=3,9804882,814634=1,414211x_5 = \dfrac{1{,}414634\cdot 1{,}4 + 2}{1{,}414634 + 1{,}4} = \dfrac{3{,}980488}{2{,}814634} = 1{,}414211.

(La formula semplificata segue da xk−(xk2−2)(xk−xk−1)xk2−xk−12=xk−xk2−2xk+xk−1=xkxk−1+2xk+xk−1x_k - \frac{(x_k^2-2)(x_k - x_{k-1})}{x_k^2 - x_{k-1}^2} = x_k - \frac{x_k^2 - 2}{x_k + x_{k-1}} = \frac{x_kx_{k-1} + 2}{x_k + x_{k-1}}; controllo: x2=2⋅1+23=43x_2 = \frac{2\cdot1+2}{3} = \frac43 ✓.)

kk xkx_k eke_k
22 1,3333331{,}333333 −8,09⋅10−2-8{,}09\cdot 10^{-2}
33 1,4000001{,}400000 −1,42⋅10−2-1{,}42\cdot 10^{-2}
44 1,4146341{,}414634 +4,21⋅10−4+4{,}21\cdot 10^{-4}
55 1,4142111{,}414211 −2,12⋅10−6-2{,}12\cdot 10^{-6}
66 1,41421356211{,}4142135621 −3,16⋅10−10-3{,}16\cdot 10^{-10}

(b) Costante e ordine

La teoria dà ek+1≈f′′(α)2f′(α)ekek−1e_{k+1} \approx \frac{f''(\alpha)}{2f'(\alpha)}e_ke_{k-1} con f′′2f′=22⋅22=0,35355\frac{f''}{2f'} = \frac{2}{2\cdot 2\sqrt2} = 0{,}35355. Rapporti calcolati (con i segni: e2<0e_2<0, e3<0e_3<0, e4>0e_4>0, e5<0e_5<0, e6<0e_6<0): e4e3e2=4,21⋅10−4(−1,42⋅10−2)(−8,09⋅10−2)=0,366\frac{e_4}{e_3e_2} = \frac{4{,}21\cdot 10^{-4}}{(-1{,}42\cdot 10^{-2})(-8{,}09\cdot 10^{-2})} = 0{,}366, e5e4e3=−2,124⋅10−6(4,206⋅10−4)(−1,42⋅10−2)=0,355\frac{e_5}{e_4e_3} = \frac{-2{,}124\cdot 10^{-6}}{(4{,}206\cdot 10^{-4})(-1{,}42\cdot 10^{-2})} = 0{,}355, e6e5e4=−3,16⋅10−10(−2,124⋅10−6)(4,206⋅10−4)=0,3535\frac{e_6}{e_5e_4} = \frac{-3{,}16\cdot 10^{-10}}{(-2{,}124\cdot 10^{-6})(4{,}206\cdot 10^{-4})} = 0{,}3535: tende a 0,35350{,}3535 ✓. Ordine stimato con ∣e4∣,∣e5∣,∣e6∣|e_4|,|e_5|,|e_6|: p≈ln⁡(∣e6∣/∣e5∣)ln⁡(∣e5∣/∣e4∣)=ln⁡(1,49⋅10−4)ln⁡(5,05⋅10−3)=−8,81−5,29=1,67p \approx \frac{\ln(|e_6|/|e_5|)}{\ln(|e_5|/|e_4|)} = \frac{\ln(1{,}49\cdot 10^{-4})}{\ln(5{,}05\cdot 10^{-3})} = \frac{-8{,}81}{-5{,}29} = 1{,}67, compatibile con 1,6181{,}618.

(c) Costo

  • Newton da x0=2x_0 = 2: x1=1,5x_1 = 1{,}5, x2=1,416667x_2 = 1{,}416667, x3=1,414215686x_3 = 1{,}414215686, x4=1,414213562375x_4 = 1{,}414213562375; errori 8,6⋅10−28{,}6\cdot10^{-2}, 2,5⋅10−32{,}5\cdot10^{-3}, 2,1⋅10−62{,}1\cdot10^{-6}, 1,6⋅10−121{,}6\cdot 10^{-12}. Sotto 10−910^{-9} dopo 44 passi: 44 valutazioni di ff e 44 di f′f', in totale 88.
  • Secanti: x6x_6 ha errore 3,16⋅10−10<10−93{,}16\cdot 10^{-10} < 10^{-9}. Le valutazioni di ff: f(x0),…,f(x5)f(x_0), \dots, f(x_5) per ottenere x6x_6: 66 in totale, nessuna di f′f'.

Per questa ff, f′(x)=2xf'(x) = 2x costa quanto ff: Newton 88 valutazioni, secanti 66. Se la derivata fosse molto più costosa (o non disponibile) il vantaggio sarebbe ancora maggiore.

(d) Un ciclo di Newton

Per f(x)=x3−2x+2f(x) = x^3 - 2x + 2, f′(x)=3x2−2f'(x) = 3x^2 - 2:

  • x0=0x_0 = 0: f(0)=2f(0) = 2, f′(0)=−2f'(0) = -2, x1=0−2−2=1x_1 = 0 - \frac{2}{-2} = 1.
  • x1=1x_1 = 1: f(1)=1f(1) = 1, f′(1)=1f'(1) = 1, x2=1−1=0x_2 = 1 - 1 = 0. Si ritorna a x0=0x_0 = 0: l'iterazione cicla 0→1→0→⋯0 \to 1 \to 0 \to \cdots e non converge. La radice reale è α=−1,76929\alpha = -1{,}76929 (le altre due sono complesse): la tangente in 00 e quella in 11 si "rimpallano" lontano dalla radice. Rimedio: separare la radice con la bisezione (f(−2)=−2<0f(-2) = -2 < 0, f(−1)=3>0f(-1) = 3 > 0) e usare Newton da un punto dentro [−2,−1][-2,-1]: da x0=−1,5x_0 = -1{,}5 si ottiene −1,84211, −1,77283, −1,769301, −1,7692924-1{,}84211,\ -1{,}77283,\ -1{,}769301,\ -1{,}7692924 (errori 2,7⋅10−1→7,3⋅10−2→3,5⋅10−3→8,9⋅10−6→6⋅10−112{,}7\cdot10^{-1}\to 7{,}3\cdot 10^{-2} \to 3{,}5\cdot 10^{-3}\to 8{,}9\cdot 10^{-6}\to 6\cdot 10^{-11}).

Risultati. Secanti: x5=1,414211x_5 = \mathbf{1{,}414211}, x6=1,41421356x_6 = \mathbf{1{,}41421356}, ordine ≈1,6\approx 1{,}6; 66 valutazioni contro 88; Newton da 00 per x3−2x+2x^3-2x+2: ciclo 0↔1\mathbf{0 \leftrightarrow 1}.

Errori tipici

  • Indicare per le secanti l'ordine 22 o dire che "converge come Newton": l'ordine è 1,6181{,}618, ma costa meno per passo.
  • Partire con x0x_0 e x1x_1 troppo vicini: il denominatore f(xk)−f(xk−1)f(x_k) - f(x_{k-1}) perde cifre (cancellazione) e il metodo si inceppa quando xk≈xk−1x_k \approx x_{k-1}.

Versione ripasso

(a) Per x2−2x^2-2 la secante diventa xk+1=xkxk−1+2xk+xk−1x_{k+1}=\frac{x_kx_{k-1}+2}{x_k+x_{k-1}} (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 →). Da x0=1x_0=1, x1=2x_1=2: x2=43x_2=\frac43, x3=1,4x_3=1{,}4, x4=1,4⋅1,33333+22,73333=1,414634x_4=\frac{1{,}4\cdot1{,}33333+2}{2{,}73333}=1{,}414634, x5=3,9804882,814634=1,414211x_5=\frac{3{,}980488}{2{,}814634}=1{,}414211, x6=1,4142135621x_6=1{,}4142135621; errori −8,1⋅10−2, −1,4⋅10−2, 4,2⋅10−4, −2,1⋅10−6, −3,2⋅10−10-8{,}1\cdot10^{-2},\ -1{,}4\cdot10^{-2},\ 4{,}2\cdot10^{-4},\ -2{,}1\cdot10^{-6},\ -3{,}2\cdot10^{-10}.

(b) ek+1ekek−1=0,366, 0,355, 0,3535→f′′2f′=122=0,3535\frac{e_{k+1}}{e_ke_{k-1}}=0{,}366,\ 0{,}355,\ 0{,}3535\to\frac{f''}{2f'}=\frac1{2\sqrt2}=0{,}3535; ordine stimato 1,67≈1,6181{,}67\approx1{,}618.

(c) Newton da 22: 1,5, 1,416667, 1,414215686, 1,4142135623751{,}5,\ 1{,}416667,\ 1{,}414215686,\ 1{,}414213562375, 44 passi, 88 valutazioni (ff e f′f'). Secanti: x6x_6 con 66 valutazioni di ff.

(d) x3−2x+2x^3-2x+2, x0=0x_0=0: x1=0−2−2=1x_1=0-\frac2{-2}=1, x2=1−11=0x_2=1-\frac11=0: ciclo 0↔10\leftrightarrow1; radice reale −1,76929-1{,}76929. Si separa con la bisezione (f(−2)=−2f(-2)=-2, f(−1)=3f(-1)=3) e da −1,5-1{,}5 Newton dà −1,84211, −1,77283, −1,769301, −1,7692924-1{,}84211,\ -1{,}77283,\ -1{,}769301,\ -1{,}7692924.

Passaggi. Forma semplificata: xk−(xk2−2)(xk−xk−1)xk2−xk−12=xk−xk2−2xk+xk−1=xkxk−1+2xk+xk−1x_k-\frac{(x_k^2-2)(x_k-x_{k-1})}{x_k^2-x_{k-1}^2}=x_k-\frac{x_k^2-2}{x_k+x_{k-1}}=\frac{x_kx_{k-1}+2}{x_k+x_{k-1}}; controllo x2=2⋅1+23=43x_2=\frac{2\cdot1+2}3=\frac43. Con f(x2)=−0,22222f(x_2)=-0{,}22222 e la formula generale x3=1,33333+0,22222⋅0,3=1,4x_3=1{,}33333+0{,}22222\cdot0{,}3=1{,}4. Costo: Newton 4 (f)+4 (f′)=84\,(f)+4\,(f')=8 valutazioni, secanti 66 (f(x0),…,f(x5)f(x_0),\dots,f(x_5)).

Errori tipici: ordine delle secanti 22 (è 1,6181{,}618); x0x_0 e x1x_1 troppo vicini (cancellazione nel denominatore).

Teoria collegata