Esercizio - Tre riscritture di x^2 - 5x + 4 = 0 e punti fissi attrattivi

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^2 - 5x + 4 = 0$ ha le radici $\alpha_1 = 1$ e $\alpha_2 = 4$. Si considerano le tre riscritture $x = g(x)$: $$g_1(x) = \frac{x^2 + 4}{5}, \qquad g_2(x) = 5 - \frac4x, \qquad g_3(x) = \sqrt{5x - 4}.$$

• (a) Verificare che ciascuna ha per punti fissi le radici dell'equazione.
• (b) Calcolare $g'(\alpha_1)$ e $g'(\alpha_2)$ per ciascuna e dire a quale radice (se una) l'iterazione converge localmente.
• (c) Eseguire cinque iterazioni di $g_1$ da $x_0 = 0$ e di $g_2$ da $x_0 = 2$, e verificare il rapporto tra gli errori.
• (d) Domanda teorica: cosa succede a $g_1$ partendo da $x_0 = 3{,}9$ (vicino a $4$) e da $x_0 = 4{,}1$?

Soluzione

(a) Punti fissi

• $x = \frac{x^2+4}{5} \iff 5x = x^2 + 4 \iff x^2 - 5x + 4 = 0$ ✓.
• $x = 5 - \frac4x \iff x^2 = 5x - 4 \iff x^2 - 5x + 4 = 0$ ✓ (per $x \ne 0$).
• $x = \sqrt{5x - 4} \iff x^2 = 5x - 4$ con $x \ge 0$ ✓ (per $x \ge \frac45$).

(b) Derivate nei punti fissi

Convergenza locale se $|g'(\alpha)| < 1$:

• $g_1$ converge a $\alpha_1 = 1$ (tasso $0{,}4$), non a $4$ ($1{,}6>1$, repulsivo).
• $g_2$ converge a $\alpha_2 = 4$ (tasso $0{,}25$), non a $1$ ($4>1$).
• $g_3$ converge a $\alpha_2 = 4$ (tasso $0{,}625$), non a $1$ ($2{,}5>1$).

La stessa equazione fornisce tre metodi diversi, ciascuno capace di "trovare" una sola delle due radici.

(c) Iterazioni

$g_1$ da $x_0 = 0$ (errore $e_k = x_k - 1$):

(Ad esempio $x_1 = \frac{0 + 4}{5} = 0{,}8$, $x_2 = \frac{0{,}64 + 4}{5} = 0{,}928$.) Il rapporto tende a $g_1'(1) = 0{,}4$.

$g_2$ da $x_0 = 2$ (errore $e_k = x_k - 4$):

($x_1 = 5 - \frac42 = 3$, $x_2 = 5 - \frac43 = 3{,}6667$.) Il rapporto tende a $g_2'(4) = 0{,}25$: più veloce, guadagna circa $0{,}6$ cifre decimali per iterazione.

(d) Vicino alla radice repulsiva

Con $g_1$ da $x_0 = 3{,}9$: $3{,}9,\ 3{,}842,\ 3{,}752,\ 3{,}616,\ 3{,}415,\ 3{,}132,\ 2{,}762,\ 2{,}326,\dots$ si allontana da $4$ e scende verso $1$ (dove $g_1'(1) = 0{,}4 < 1$ lo cattura). Da $x_0 = 4{,}1$: $4{,}162,\ 4{,}264,\ 4{,}437,\ 4{,}738,\dots$ cresce senza limite (diverge). Il valore $4$ è un punto fisso "instabile": solo partendo esattamente da $4$ si resta lì. Una zona di convergenza garantita dal teorema delle contrazioni è $[0,2]$: $g_1$ è crescente, $g_1(0) = 0{,}8$ e $g_1(2) = 1{,}6$, quindi $g_1([0,2]) = [0{,}8,\,1{,}6] \subset [0,2]$, e $|g_1'| = \frac{2x}{5} \le 0{,}8 = L < 1$ su $[0,2]$. Un metodo più veloce (con $g'(\alpha) = 0$) è quello di Newton (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 →).

Risultati. $g_1 \to \mathbf{1}$ (tasso $0{,}4$); $g_2 \to \mathbf{4}$ (tasso $0{,}25$); $g_3 \to \mathbf{4}$ (tasso $0{,}625$).

Errori tipici

• Dire che una riscrittura "converge" senza specificare a quale punto fisso: l'esito dipende da $g'$ nel punto fisso.
• Dimenticare di controllare il dominio di $g$ ($g_2$ in $x = 0$, $g_3$ per $x < \frac45$).