Esercizio - Punto fisso per x = e^(-x), teorema delle contrazioni e stima a priori

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

L'equazione $x = e^{-x}$ ha un'unica soluzione reale $\alpha \approx 0{,}567$ (il grafico di $y = e^{-x}$ è decrescente e quello di $y = x$ è crescente). Si usa $g(x) = e^{-x}$ e $x_0 = 0{,}5$.

• (a) Verificare le ipotesi del teorema delle contrazioni su $I = [0{,}4,\ 0{,}7]$ e dare la costante $L$.
• (b) Calcolare a mano $x_1, \dots, x_6$ e gli errori rispetto a $\alpha = 0{,}5671433$. Osservare il rapporto $e_k/e_{k-1}$.
• (c) Stimare con la stima a priori quante iterazioni bastano per un errore $\le 10^{-4}$ e confrontare con il numero reale.
• (d) Domanda teorica: la riscrittura $x = -\ln x$ dello stesso problema converge?

Soluzione

(a) Ipotesi del teorema

• $g$ manda $I$ in sé. $g$ è decrescente, quindi $g(I) = [g(0{,}7),\, g(0{,}4)] = [e^{-0{,}7},\, e^{-0{,}4}] = [0{,}4966,\ 0{,}6703]$, che è contenuto in $[0{,}4,\ 0{,}7]$ ✓.
• Contrazione. $g'(x) = -e^{-x}$, quindi $|g'(x)| = e^{-x}$ è decrescente e il massimo su $I$ si ha in $x = 0{,}4$: $L = e^{-0{,}4} = \mathbf{0{,}6703} < 1$ ✓.

Quindi esiste un unico punto fisso $\alpha\in I$ e l'iterazione converge da ogni $x_0 \in I$.

(b) Iterazioni

$x_{k+1} = e^{-x_k}$, con $e_k = x_k - \alpha$:

(Ad esempio $x_1 = e^{-0{,}5} = 0{,}606531$, $x_2 = e^{-0{,}606531} = 0{,}545239$.) Il rapporto tende a $g'(\alpha) = -e^{-\alpha} = -\alpha = -0{,}5671$ (perché $e^{-\alpha} = \alpha$): convergenza lineare con tasso $0{,}567$, errori di segno alterno.

(c) Stima a priori

$x_1 - x_0 = 0{,}606531 - 0{,}5 = 0{,}106531$. La stima è $$|x_k - \alpha| \le \frac{L^k}{1-L}|x_1 - x_0| = \frac{0{,}6703^k}{0{,}3297}\cdot 0{,}106531 = 0{,}3231\cdot 0{,}6703^k.$$ Per essere $\le 10^{-4}$: $0{,}6703^k \le 3{,}095\cdot 10^{-4}$, cioè $k \ge \dfrac{\ln(3{,}095\cdot 10^{-4})}{\ln 0{,}6703} = \dfrac{-8{,}081}{-0{,}4000} = 20{,}2$, quindi $\mathbf{k = 21}$. In realtà l'errore effettivo vale $7{,}6\cdot 10^{-5} \le 10^{-4}$ già a $k = 12$ (tabella delle iterazioni: $x_{12} = 0{,}567067$): la stima a priori è prudente perché usa $L = 0{,}67$ (il massimo su tutto $I$) invece del tasso vero $|g'(\alpha)| = 0{,}567$ e perché è un maggiorante.

(d) La riscrittura $x = -\ln x$

Da $x = e^{-x}$ si ricava $x = -\ln x$ (cioè $g_2(x) = -\ln x$, definita per $x>0$). Qui $g_2'(x) = -\frac1x$, e $|g_2'(\alpha)| = \frac{1}{0{,}5671} = 1{,}763 > 1$: il punto fisso è repulsivo, l'iterazione si allontana. Da $x_0 = 0{,}5$ si ottiene $0{,}6931,\ 0{,}3665,\ 1{,}0037,\ -0{,}0037$: al passo successivo $\ln(-0{,}0037)$ non è definito. Le due iterazioni sono l'una l'inversa dell'altra: dove $g$ contrae, $g^{-1}$ espande.

Risultati. $L = \mathbf{0{,}6703}$; $x_6 = \mathbf{0{,}564863}$ ($e_6 = -2{,}3\cdot 10^{-3}$); stima a priori: $\mathbf{21}$ iterazioni, ne bastano $12$; la riscrittura $-\ln x$ diverge.

Errori tipici

• Prendere $L = |g'(\alpha)|$ nella stima a priori: la stima richiede il massimo di $|g'|$ su un intervallo che $g$ manda in sé.
• Scegliere un intervallo non invariante: ad esempio $[0{,}5,\,0{,}6]$ non va, perché $g(0{,}5) = 0{,}6065 > 0{,}6$.