Salta al contenuto
Note per Studenti Esercizio - Criteri di arresto, incremento contro errore e residuo di (x-1)3

Esercizio - Criteri di arresto, incremento contro errore e residuo di (x-1)^3

In questa pagina 3

Teoria: 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 →; condizionamento delle radici in Condizionamento di un problema e stabilità di un algoritmoL'errore finale ha tre origini (dati, troncamento, arrotondamento). Un problema è ben posto se la soluzione esiste, è unica e dipende con continuità dai dati; il numero di condizionamento K = |x f'(x)/f(x)| misura di quanto un errore relativo sui dati si amplifica nel risultato (si perdono circa log10 K cifre). La stabilità riguarda invece l'algoritmo: un algoritmo instabile amplifica gli errori anche su un problema ben condizionato (ricorrenza I_n = 1 − n I_{n−1}); un problema mal condizionato non si salva con nessun algoritmo. Uno schema numerico converge se è consistente e stabile (derivata numerica: troncamento contro arrotondamento).Condizionamento di un problema e stabilità di un algoritmo →.

Testo

Si considera l'iterazione xk+1=g(xk)x_{k+1} = g(x_k) con g(x)=0,9 x+0,1g(x) = 0{,}9\,x + 0{,}1 da x0=2x_0 = 2, il cui punto fisso è α=1\alpha = 1.

  • (a) Trovare LL, scrivere l'errore ek=xk−αe_k = x_k - \alpha in forma chiusa e calcolare x1,…,x5x_1, \dots, x_5.
  • (b) Calcolare il rapporto tra errore e incremento ∣xk−xk−1∣|x_k - x_{k-1}| e confrontarlo con L1−L\frac{L}{1-L}.
  • (c) Si ferma l'iterazione quando ∣xk−xk−1∣≤10−3|x_k - x_{k-1}| \le 10^{-3}. A quale kk ci si ferma e quanto vale l'errore vero? Come si deve scegliere la soglia sull'incremento per garantire un errore ≤10−3\le 10^{-3}?
  • (d) Domanda teorica: la funzione f(x)=(x−1)3f(x) = (x-1)^3 ha lo zero α=1\alpha = 1. Se si usa come criterio ∣f(xk)∣≤10−6|f(x_k)| \le 10^{-6}, quale errore si può avere? Perché?

Soluzione

(a) Errore in forma chiusa

g′(x)=0,9g'(x) = 0{,}9 costante, quindi L=0,9L = \mathbf{0{,}9} (qui il tasso è esattamente 0,90{,}9 ovunque). Poiché α=g(α)\alpha = g(\alpha), ek+1=xk+1−α=g(xk)−g(α)=0,9 (xk−α)=0,9 ek⟹ek=0,9ke0=0,9k.e_{k+1} = x_{k+1} - \alpha = g(x_k) - g(\alpha) = 0{,}9\,(x_k - \alpha) = 0{,}9\,e_k \quad\Longrightarrow\quad e_k = 0{,}9^k e_0 = 0{,}9^k. Iterazioni: x1=0,9⋅2+0,1=1,9x_1 = 0{,}9\cdot 2 + 0{,}1 = 1{,}9; x2=0,9⋅1,9+0,1=1,81x_2 = 0{,}9\cdot 1{,}9 + 0{,}1 = 1{,}81; x3=1,729x_3 = 1{,}729; x4=1,6561x_4 = 1{,}6561; x5=1,59049x_5 = 1{,}59049. Gli errori sono 0,9, 0,81, 0,729, 0,6561, 0,590490{,}9,\ 0{,}81,\ 0{,}729,\ 0{,}6561,\ 0{,}59049: lenti, perché LL è vicino a 11.

(b) Errore contro incremento

L'incremento è ∣xk−xk−1∣=∣ek−ek−1∣=∣0,9k−0,9k−1∣=0,1⋅0,9k−1|x_k - x_{k-1}| = |e_k - e_{k-1}| = |0{,}9^k - 0{,}9^{k-1}| = 0{,}1\cdot 0{,}9^{k-1}. Quindi ∣ek∣∣xk−xk−1∣=0,9k0,1⋅0,9k−1=0,90,1=9=L1−L.\frac{|e_k|}{|x_k - x_{k-1}|} = \frac{0{,}9^k}{0{,}1\cdot 0{,}9^{k-1}} = \frac{0{,}9}{0{,}1} = 9 = \frac{L}{1-L}. Tabella per k=1,…,5k=1,\dots,5: incrementi 0,1, 0,09, 0,081, 0,0729, 0,065610{,}1,\ 0{,}09,\ 0{,}081,\ 0{,}0729,\ 0{,}06561; errori 0,9, 0,81, 0,729, 0,6561, 0,590490{,}9,\ 0{,}81,\ 0{,}729,\ 0{,}6561,\ 0{,}59049; rapporto sempre 99. In questo caso la stima a posteriori ∣xk−α∣≤L1−L∣xk−xk−1∣|x_k - \alpha| \le \frac{L}{1-L}|x_k - x_{k-1}| è un'uguaglianza.

(c) Soglia sull'incremento

  • Incremento ≤10−3\le 10^{-3}: 0,1⋅0,9k−1≤10−3  ⟺  0,9k−1≤0,01  ⟺  k−1≥ln⁡0,01ln⁡0,9=43,70{,}1\cdot 0{,}9^{k-1} \le 10^{-3} \iff 0{,}9^{k-1} \le 0{,}01 \iff k - 1 \ge \frac{\ln 0{,}01}{\ln 0{,}9} = 43{,}7, quindi k=45k = \mathbf{45}. L'incremento vale 9,7⋅10−49{,}7\cdot 10^{-4}, ma l'errore vero è 0,945=8,7⋅10−30{,}9^{45} = \mathbf{8{,}7\cdot 10^{-3}}: quasi 99 volte la tolleranza. L'iterazione si ferma troppo presto.
  • Per garantire ∣xk−α∣≤10−3|x_k - \alpha| \le 10^{-3} occorre L1−L∣xk−xk−1∣≤10−3\frac{L}{1-L}|x_k - x_{k-1}| \le 10^{-3}, cioè incremento ≤1−LL10−3=1,11⋅10−4\le \frac{1-L}{L}10^{-3} = 1{,}11\cdot 10^{-4}: la prima volta che succede è a k=66k = 66 (incremento 0,1⋅0,965=1,06⋅10−40{,}1\cdot 0{,}9^{65} = 1{,}06\cdot 10^{-4}, mentre a k=65k=65 era 1,18⋅10−41{,}18\cdot 10^{-4}), con errore vero 0,966=9,55⋅10−4≤10−30{,}9^{66} = 9{,}55\cdot 10^{-4} \le 10^{-3} ✓. Qui la stima a posteriori è un'uguaglianza, quindi l'errore è esattamente 99 volte l'incremento.

(d) Il residuo

Per f(x)=(x−1)3f(x) = (x-1)^3: ∣f(xk)∣≤10−6|f(x_k)| \le 10^{-6} equivale a ∣xk−1∣≤(10−6)1/3=10−2|x_k - 1| \le (10^{-6})^{1/3} = \mathbf{10^{-2}}. Quindi con residuo 10−610^{-6} l'errore può essere 10−210^{-2} (esempio: x=1,01x = 1{,}01 ha f=10−6f = 10^{-6}). In generale vale ∣xk−α∣≈∣f(xk)∣∣f′(α)∣|x_k - \alpha| \approx \frac{|f(x_k)|}{|f'(\alpha)|} se f′(α)≠0f'(\alpha) \ne 0; qui f′(1)=0f'(1) = 0 (radice tripla), e il problema è molto mal condizionato: l'errore è la radice cubica del residuo. Anche con residuo 10−910^{-9} l'errore resta 10−310^{-3}.

Risultati. L=0,9L = \mathbf{0{,}9}, ek=0,9ke_k = 0{,}9^k; rapporto errore/incremento 9\mathbf{9}; con soglia 10−310^{-3} sull'incremento si ferma a k=45k=45 con errore 8,7⋅10−3\mathbf{8{,}7\cdot 10^{-3}}; la soglia corretta è 1,1⋅10−41{,}1\cdot 10^{-4} (k=66k=66).

Errori tipici

  • Pensare che "incremento piccolo" significhi "errore piccolo": serve il fattore L1−L\frac{L}{1-L} (qui 99; vale 9999 se L=0,99L=0{,}99).
  • Pensare che "residuo piccolo" significhi "errore piccolo": dipende da f′(α)f'(\alpha).

Versione ripasso

(a) g=0,9x+0,1g=0{,}9x+0{,}1, α=1\alpha=1, L=0,9L=0{,}9; ek+1=0,9eke_{k+1}=0{,}9e_k, ek=0,9ke_k=0{,}9^k (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 →). x1,…,x5=1,9, 1,81, 1,729, 1,6561, 1,59049x_1,\dots,x_5=1{,}9,\ 1{,}81,\ 1{,}729,\ 1{,}6561,\ 1{,}59049.

(b) Incremento 0,1⋅0,9k−10{,}1\cdot0{,}9^{k-1}; ∣ek∣∣xk−xk−1∣=0,90,1=9=L1−L\frac{|e_k|}{|x_k-x_{k-1}|}=\frac{0{,}9}{0{,}1}=9=\frac L{1-L} (qui uguaglianza della stima a posteriori).

(c)

  • Soglia 10−310^{-3} sull'incremento: 0,9k−1≤0,010{,}9^{k-1}\le0{,}01, k−1≥43,7k-1\ge43{,}7, k=45k=45, incremento 9,7⋅10−49{,}7\cdot10^{-4}, errore vero 0,945=8,7⋅10−30{,}9^{45}=8{,}7\cdot10^{-3} (circa 99 volte la tolleranza).
  • Garanzia: incremento ≤1−LL10−3=1,1⋅10−4\le\frac{1-L}L10^{-3}=1{,}1\cdot10^{-4}, k=66k=66, errore 0,966=9,55⋅10−4≤10−30{,}9^{66}=9{,}55\cdot10^{-4}\le10^{-3}.

(d) f=(x−1)3f=(x-1)^3: ∣f∣≤10−6⇔∣x−1∣≤10−2|f|\le10^{-6}\Leftrightarrow|x-1|\le10^{-2} (es. x=1,01x=1{,}01). In generale errore ≈∣f∣∣f′(α)∣\approx\frac{|f|}{|f'(\alpha)|}; qui f′(1)=0f'(1)=0 (radice tripla), errore =∣f∣3=\sqrt[3]{|f|}; con residuo 10−910^{-9} errore 10−310^{-3}.

Errori tipici: incremento piccolo ≠\ne errore piccolo (fattore L1−L\frac L{1-L}, 9999 se L=0,99L=0{,}99); residuo piccolo ≠\ne errore piccolo (dipende da f′(α)f'(\alpha)).

Teoria collegata