Esercizio - Bisezione per e^x = 3x, numero di iterazioni e intervalli con segni uguali

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

Testo

Si consideri l'equazione $e^x = 3x$, cioè $f(x) = e^x - 3x = 0$.

• (a) Verificare che $[0,1]$ soddisfa le ipotesi della bisezione e che anche $[1,2]$ le soddisfa. Perché $[0,2]$ non va bene, pur contenendo due radici?
• (b) Eseguire a mano sei iterazioni sull'intervallo $[0,1]$ (da $n=0$ a $n=5$), dando $c_n$, $f(c_n)$ e il nuovo intervallo.
• (c) Dare il maggiorante dell'errore di $c_5$ e il numero minimo di iterazioni per ottenere $|c_n - \alpha| \le 10^{-5}$.
• (d) Domanda teorica: la sequenza degli errori effettivi $|c_n - \alpha|$ è monotona? Cosa si può dire di sicuro?

Soluzione

(a) Ipotesi

$f$ è continua (somma di funzioni continue). Valori: $f(0) = 1 - 0 = 1 > 0$, $f(1) = e - 3 = -0{,}2817 < 0$, $f(2) = e^2 - 6 = 1{,}3891 > 0$.

• Su $[0,1]$: $f(0)f(1) < 0$ ✓, c'è una radice (è $\alpha_1 = 0{,}61906$).
• Su $[1,2]$: $f(1)f(2) < 0$ ✓, c'è un'altra radice ($\alpha_2 = 1{,}51213$).
• Su $[0,2]$: $f(0)f(2) = 1{,}39 > 0$. Il prodotto è positivo perché le due radici fanno cambiare segno a $f$ due volte: il segno agli estremi è lo stesso e la condizione non si può verificare. La bisezione richiede un cambio di segno (numero dispari di radici); con due radici si deve prima separarle guardando i segni in un punto intermedio ($x=1$).

(b) Sei iterazioni su $[0,1]$

Si usa $f(0) > 0$: se $f(c_n) > 0$ la radice è a destra ($a_{n+1} = c_n$), se $f(c_n) < 0$ è a sinistra ($b_{n+1} = c_n$).

Dopo $n = 5$ si può prendere $c_5 = 0{,}609375$, oppure $c_6 = 0{,}6171875$.

(c) Errore e numero di iterazioni

• Maggiorante: $|c_5 - \alpha_1| \le \frac{b-a}{2^{6}} = \frac{1}{64} = 0{,}0156$. Errore effettivo: $|0{,}609375 - 0{,}619061| = 0{,}0097$ ✓ (inferiore al maggiorante).
• Per $10^{-5}$: $\frac{1}{2^{n+1}} \le 10^{-5} \iff n + 1 \ge \log_2 10^5 = 16{,}61 \iff n \ge 15{,}61$, quindi $n_{\min} = \mathbf{16}$ (cioè si arriva fino a $c_{16}$).

(d) Monotonia

L'errore effettivo non è monotono: gli errori sono $0{,}1191,\ 0{,}1309,\ 0{,}0059,\ 0{,}0566,\ 0{,}0253,\ 0{,}0097,\ 0{,}0019,\ 0{,}0020$ (cresce da $n=0$ a $n=1$, da $n=2$ a $n=3$, da $n=6$ a $n=7$). Quello che si può garantire è il maggiorante $\frac{b-a}{2^{n+1}}$, che dimezza ad ogni passo, e la lunghezza dell'intervallo $[a_n,b_n]$.

Risultati. Radici $\alpha_1 = \mathbf{0{,}61906}$ in $[0,1]$ e $\alpha_2 = \mathbf{1{,}51213}$ in $[1,2]$; $c_5 = \mathbf{0{,}609375}$ con errore $\le \mathbf{0{,}0156}$; servono $\mathbf{16}$ iterazioni per $10^{-5}$.

Errori tipici

• Applicare la bisezione a $[0,2]$: stesso segno agli estremi, quindi il test non si può fare (e il metodo potrebbe non vedere nessuna delle due radici).
• Contare le iterazioni con $2^n$ invece di $2^{n+1}$.
• Fermarsi quando $|f(c_n)|$ è piccolo senza guardare la pendenza di $f$ vicino alla radice.