Il metodo iterativo del punto unito

Il metodo iterativo del punto unito, detto anche metodo del punto fisso, è un metodo numerico che permette di trovare una soluzione approssimata di un'equazione attraverso una successione di valori calcolati iterativamente. Il metodo consiste nel trasformare un'equazione della forma \[ f(x)=0 \] in un'equazione equivalente \[ x=g(x) \] e cercare un numero \(\alpha\) che soddisfi la condizione \[ g(\alpha)=\alpha \]

Il numero \(\alpha\) è detto punto unito o punto fisso della funzione \(g(x)\), perché la funzione lo trasforma in sé stesso.

Se le due equazioni sono equivalenti nell'intervallo considerato, il punto unito è anche una radice dell'equazione originale.

Il vantaggio del metodo è che permette di cercare una radice senza risolvere direttamente l'equazione, utilizzando soltanto valutazioni successive della funzione \(g(x)\).

Nota. Due equazioni equivalenti hanno le stesse soluzioni. Quindi, se un numero è un punto unito della funzione \( g(x) \), è anche una radice dell'equazione originale \( f(x)=0 \). In sostanza, il metodo del punto unito non cambia il problema matematico da risolvere, ma soltanto il modo in cui cerco le soluzioni.

Come funziona il metodo

Considero un'equazione

\[ f(x)=0 \]

La trasformo nella forma equivalente

\[ x=g(x) \]

Scelgo un valore iniziale \(x_0\), che rappresenta una prima approssimazione della radice.

Sostituisco questo valore nella funzione \(g(x)\) e ottengo una nuova approssimazione:

\[ x_1=g(x_0) \]

Ripeto il procedimento utilizzando il valore appena calcolato:

\[ x_2=g(x_1) \]

Continuando, ottengo una successione di numeri:

\[ x_0,\quad x_1,\quad x_2,\quad \ldots,\quad x_n,\quad \ldots \]

La formula iterativa del metodo è quindi

\[ x_{n+1}=g(x_n) \]

Ogni termine della successione viene calcolato applicando la funzione \(g\) al termine precedente.

Se la successione converge a un valore \(\alpha\) e la funzione \(g\) è continua in tale punto, allora

\[ \lim_{n\to\infty}x_n=\alpha \]

Usando il limite nella formula iterativa, ottengo

\[ \alpha=g(\alpha) \]

Pertanto, \( \alpha \) è contemporaneamente un punto unito della funzione iterativa \(g(x)\), una radice dell'equazione originale \(f(x)=0\).

\[ g(\alpha)=\alpha\iff f(\alpha)=0 \]

La distinzione è soltanto nel ruolo che lo stesso numero assume nei due contesti.

Interpretazione geometrica

Il metodo del punto unito può essere rappresentato graficamente considerando le due funzioni

\[ y=x \] \[ y=g(x) \]

La prima è la bisettrice del primo e terzo quadrante, mentre la seconda è la funzione ottenuta dalla trasformazione dell'equazione originale.

I punti di intersezione dei due grafici soddisfano contemporaneamente le condizioni

\[ y=x \qquad y=g(x) \]

e quindi

\[ x=g(x) \]

Le loro ascisse sono pertanto i punti uniti della funzione.

Per rappresentare graficamente le iterazioni, parto dal valore iniziale \(x_0\) sull'asse delle ascisse e procedo nel seguente modo:

• Traccio una retta verticale da \( x_0 \) fino a incontrare il grafico di \(y=g(x)\) nel punto \( P_0 \).
  
• Dal punto di intersezione \( P_0 \) traccio una retta orizzontale fino alla bisettrice \(y=x\) ossia il punto \( Q_0 \).
  
• Il punto raggiunto sulla bisettrice \( Q_0 \) ha ascissa \(x_1=g(x_0)\).
  
• Ripeto il procedimento partendo dalla nuova ascissa \(x_1\). Trovo il punto \( P_1 \), poi il punto \( Q_1 \) e via dicendo.
  

In questo modo costruisco una spezzata formata da segmenti verticali e orizzontali.

Se il metodo converge, la spezzata si avvicina progressivamente al punto di intersezione \( S \) tra le due curve, ossia alla soluzione dell'equazione iniziale.

La successione può avvicinarsi alla soluzione in modo monotòno, ossia sempre dalla stessa parte, oppure oscillando attorno al punto unito.

Un esempio pratico

Voglio trovare una soluzione approssimata dell'equazione

\[ x^2+x-6=0 \]

In questo caso potrei risolvere direttamente l'equazione di secondo grado, ma utilizzo il metodo iterativo per comprenderne il funzionamento.

Per prima cosa trasformo l'equazione:

\[ x^2+x=6 \] \[ x(x+1)=6 \]

Dividendo per \(x+1\), ottengo

\[ x=\frac{6}{x+1} \]

Questa trasformazione è equivalente all'equazione originale, perché \(x=-1\) non è una sua soluzione.

La funzione da utilizzare è quindi

\[ g(x)=\frac{6}{x+1} \]

e la formula iterativa diventa

\[ x_{n+1}=\frac{6}{x_n+1} \]

Scelgo come valore iniziale

\[ x_0=1 \]

Calcolo la prima approssimazione:

\[ x_1=\frac{6}{1+1}=3 \]

Utilizzo il risultato per calcolare la seconda:

\[ x_2=\frac{6}{3+1}=1.5 \]

Continuo nello stesso modo:

\[ x_3=\frac{6}{1.5+1}=2.4 \] \[ x_4=\frac{6}{2.4+1}\approx1.764706 \] \[ x_5=\frac{6}{1.764706+1}\approx2.170213 \]

Ripetendo le iterazioni ottengo i seguenti valori:

Iterazione	Approssimazione
\(x_0\)	1
\(x_1\)	3
\(x_2\)	1.5
\(x_3\)	2.4
\(x_4\)	1.764706
\(x_5\)	2.170213
\(x_6\)	1.892562
\(x_7\)	2.074286
\(x_8\)	1.951667

Osservo che i valori oscillano sopra e sotto il numero 2, avvicinandosi progressivamente a esso.

Proseguendo il calcolo, la successione converge a

\[ \alpha=2 \]

Verifico il risultato sostituendolo \( x= \alpha = 2 \) nell'equazione originale:

\[ x^2+x-6=0 \]

\[ 2^2+2-6=0 \]

\[ 4+2-6=0 \]

\[ 0=0 \]

La soluzione trovata è corretta.

Nota. Va sottolineato che l'equazione originale \( x^2+x-6=0 \) possiede anche la radice \(x=-3\), ma questa particolare iterazione, partendo da \(x_0=1\), converge alla radice positiva. Quindi, il metodo trova una radice dell'equazione a seconda del punto iniziale che scelgo ma non garantisce che sia l'unica.

Dal punto di vista geometrico si può vedere meglio come l'algoritmo converge passo dopo passo verso la soluzione.

La scelta della funzione iterativa

Un aspetto importante del metodo è che la stessa equazione può essere trasformata in modi differenti, ottenendo funzioni iterative con comportamenti diversi.

Esempio

Considero l'equazione

\[ x^2-5=0 \]

che ha come radici

\[ x=\pm\sqrt5 \]

Per cercare la radice positiva, posso trasformarla nella forma

\[ x=\frac5x \]

La formula iterativa diventa

\[ x_{n+1}=\frac5{x_n} \]

Scelgo \(x_0=2\) e calcolo:

\[ x_1=\frac52=2.5 \]

\[ x_2=\frac5{2.5}=2 \]

\[ x_3=\frac52=2.5 \]

La successione continua ad alternare i valori 2 e 2.5, senza convergere. Quindi, non la posso usare nel metodo del punto fisso.

Iterazione	Approssimazione
\(x_0\)	2
\(x_1\)	2.5
\(x_2\)	2
\(x_3\)	2.5
\(x_4\)	2

A questo punto, provo a trasformare la stessa equazione in un altro modo.

Riparto dall'equazione equivalente

\[ x=\frac5x \]

Aggiungo \(x\) a entrambi i membri:

\[ x+x=x+\frac5x \]

Ottengo

\[ 2x=x+\frac5x \]

Divido entrambi i membri per 2 e ottengo un'altra equazione equivalente:

\[ x=\frac12\left(x+\frac5x\right) \]

Ora la nuova funzione iterativa è

\[ g(x)=\frac12\left(x+\frac5x\right) \]

Quindi, la formula di ricorrenza diventa

\[ x_{n+1}=\frac12\left(x_n+\frac5{x_n}\right) \]

La nuova equazione è equivalente in tutto e per tutto a quella originale per \(x\ne0\), ma utilizza una funzione iterativa diversa.

Questa trasformazione è però preferibile perché riduce l'errore nelle vicinanze della radice positiva.

Infatti, se ora calcolo le nuove approssimazioni partendo nuovamente da \(x_0=2\), ottengo una successione convergente di valori:

Iterazione	Approssimazione
\(x_0\)	2
\(x_1\)	2.25
\(x_2\)	2.236111111
\(x_3\)	2.236067978
\(x_4\)	2.236067977

La successione converge rapidamente al avalore seguente:

\[ \sqrt5\approx2.236067977 \]

Ho così trovato la soluzione approssimativa dell'equazione iniziale.

\[ x^2-5=0 \]

\[ ( \sqrt5 )^2 - 5 = 0 \]

\[ 5 - 5 = 0 \]

\[ 0 = 0 \]

In conclusione, la seconda forma equivalente converge alla soluzione mentre la prima è inutilizzabile.

Questo dimostra l'importanza della scelta della funzione iterativa.

Come fare a capire quale forma equivalente converge alla soluzione?

Per capirlo, senza dover svolgere le approssimazioni, posso applicare il teorema della convergenza alla forma equivalente e verificare se soddisfa tutte le condizioni.

Teorema di convergenza del metodo del punto unito

Il metodo iterativo non converge necessariamente per qualsiasi funzione \(g(x)\).

La convergenza dipende dalla funzione scelta, dal valore iniziale e dall'intervallo in cui viene applicato il procedimento.

Una condizione sufficiente di convergenza è fornita dal seguente teorema di convergenza. 

La prima condizione \( g([a,b])\subseteq[a,b] \) richiede che la funzione trasformi ogni punto dell'intervallo in un altro punto dello stesso intervallo.

La seconda condizione \( |g'(x)|\le m<1 \) richiede che il valore assoluto della derivata sia uniformemente minore di 1.

Perché la derivata è importante?

La derivata misura quanto varia la funzione al variare della variabile indipendente.

Se il valore assoluto della derivata è minore di 1, la funzione riduce le distanze tra i punti dell'intervallo.

In particolare, indicando con \(\alpha\) il punto unito, il teorema del valor medio permette di scrivere

\[ |x_{n+1}-\alpha| =|g(x_n)-g(\alpha)| \le m|x_n-\alpha| \]

Poiché \(m<1\), l'errore della nuova approssimazione è al massimo una frazione dell'errore precedente.

Ripetendo il ragionamento ottengo

\[ |x_n-\alpha|\le m^n|x_0-\alpha| \]

Il termine \(m^n\) tende a zero quando \(n\) tende all'infinito. Di conseguenza, anche l'errore tende a zero e la successione converge al punto unito.

Nota. Queste condizioni sono sufficienti, ma non necessarie: il metodo può convergere anche quando non è possibile applicare direttamente il teorema.

Esempio pratico

Voglio trovare la radice positiva dell'equazione

\[ x^2-5=0 \]

utilizzando il metodo iterativo del punto unito.

1] Prima trasformazione dell'equazione

Porto il termine noto al secondo membro:

\[ x^2=5 \]

Ottengo la forma equivalente nella forma \(x=g(x)\)

\[ x=\frac5x \]

La formula iterativa è quindi

\[ x_{n+1}=\frac5{x_n} \]

Verifico se soddisfa le condizioni di convergenza.

Calcolo la derivata:

\[ g'(x)=-\frac5{x^2} \]

Il valore assoluto è

\[ |g'(x)|=\frac5{x^2} \]

Nell'intervallo \([2,3]\), questa espressione assume il valore massimo in \(x=2\):

\[ |g'(2)|=\frac54=1.25 \]

Pertanto, non esiste una costante \(m<1\) tale che

\[ |g'(x)|\le m<1 \]

per ogni \(x\in[2,3]\).

Inoltre,

\[ g(2)=2.5,\qquad g(3)=\frac53 \]

Quindi

\[ g([2,3])=\left[\frac53,\frac52\right] \]

Questo intervallo non è contenuto in \([2,3]\), perché \(\frac53<2\).

Nessuna delle due condizioni del teorema è soddisfatta.

Il mancato rispetto delle condizioni non implica, in generale, che una successione debba divergere.

In questo caso, però, ho già verificato direttamente che la successione oscilla tra due valori senza convergere.

Nota. In effetti, scegliendo come valore iniziale \(x_0=2\) ottengo una successione che alterna continuamente gli stessi valori. \[ x_1=\frac52=2.5 \] \[ x_2=\frac5{2.5}=2 \] \[ x_3=\frac52=2.5 \]  Pertanto, il metodo non converge. La trasformazione è corretta, ma la funzione iterativa scelta non permette di avvicinarmi alla radice.

Devo quindi cercare un'altra trasformazione dell'equazione originale che permetta di ottenere una successione convergente.

2] Scelta di una nuova funzione iterativa

Nel paragrafo precedente ho già trovato un'altra forma equivalente

\[ x=\frac12\left(x+\frac5x\right) \]

La nuova funzione iterativa è

\[ g(x)=\frac12\left(x+\frac5x\right) \]

Adesso la formula di ricorrenza diventa

\[ x_{n+1}=\frac12\left(x_n+\frac5{x_n}\right) \]

Questa nuova equazione è del tutto equivalente a quella originale per \(x\ne0\), ma usa una funzione iterativa diversa.

A questo punto verifico se soddisfa le condizioni di convegenza.

Scelgo l'intervallo

\[ [a,b]=[2,3] \]

Devo verificare che

\[ g([2,3])\subseteq[2,3] \]

Calcolo la derivata della nuova funzione:

\[ g'(x)=\frac12\left(1-\frac5{x^2}\right) \]

La derivata si annulla quando

\[ 1-\frac5{x^2}=0 \]

da cui

\[ x^2=5 \]

Nell'intervallo considerato ottengo

\[ x=\sqrt5 \]

La funzione è decrescente tra 2 e \(\sqrt5\) e crescente tra \(\sqrt5\) e 3. Quindi il minimo si trova in \(x=\sqrt5\), mentre il massimo si trova in uno degli estremi.

Calcolo i valori:

\[ g(2)=\frac12\left(2+\frac52\right)=2.25 \] \[ g(\sqrt5)=\sqrt5\approx2.236068 \] \[ g(3)=\frac12\left(3+\frac53\right)=\frac73 \]

Pertanto,

\[ g([2,3])=\left[\sqrt5,\frac73\right] \]

Poiché

\[ \left[\sqrt5,\frac73\right]\subseteq[2,3] \]

Quindi, la prima condizione è soddisfatta.

Ora devo verificare se è soddisfatta anche la seconda condizione.

Devo verificare che esista una costante \(m<1\) tale che

\[ |g'(x)|\le m<1 \]

per ogni \(x\in[2,3]\).

La derivata è

\[ g'(x)=\frac12-\frac5{2x^2} \]

Calcolo la derivata seconda:

\[ g''(x)=\frac5{x^3} \]

Poiché \(g''(x)>0\) nell'intervallo \([2,3]\), la derivata prima è crescente.

Calcolo i valori agli estremi:

\[ g'(2)=\frac12-\frac58=-\frac18 \] \[ g'(3)=\frac12-\frac5{18}=\frac29 \]

Quindi, per ogni \(x\in[2,3]\),

\[ -\frac18\le g'(x)\le\frac29 \]

Il massimo valore assoluto della derivata è \(\frac29\) ed è minore di 1. Quindi, posso scegliere

\[ m=\frac29<1 \]

Pertanto, anche la seconda condizione è soddisfatta.

Il teorema mi garantisce che la successione converge all'unico punto unito dell'intervallo \([2,3]\), qualunque sia il valore iniziale scelto in tale intervallo.

A questo punto posso procedere con il calcolo delle approssimazioni. 

Scelgo nuovamente

\[ x_0=2 \]

Applico la nuova formula iterativa:

\[ x_{n+1}=\frac12\left(x_n+\frac5{x_n}\right) \]

Calcolo la prima approssimazione:

\[ x_1=\frac12\left(2+\frac52\right)=2.25 \]

La seconda:

\[ x_2=\frac12\left(2.25+\frac5{2.25}\right) \] \[ x_2\approx2.236111111 \]

Continuo nello stesso modo e ottengo:

Iterazione	Approssimazione
\(x_0\)	2
\(x_1\)	2.25
\(x_2\)	2.236111111
\(x_3\)	2.236067978
\(x_4\)	2.236067977

Osservo che la successione converge rapidamente al valore

\[ \alpha=\sqrt5\approx2.236067977 \]

Verifico il risultato \( x= \alpha \) nell'equazione originale:

\[ x^2 - 5 = 0 \]

\[ ( \sqrt5 )^2 - 5 = 0  \]

\[ 0 = 0 \]

Quindi \(\alpha = \sqrt5 \) è la radice positiva che stavo cercando.

Nota. Il teorema permette anche di stimare l'errore delle approssimazioni successive: \[ |x_n-\alpha|\le m^n|x_0-\alpha| \] Nel nostro esempio ho trovato \[ m=\frac29 \] Quindi \[ |x_n-\alpha|\le\left(\frac29\right)^n|2-\sqrt5| \] Dopo quattro iterazioni: \[ |x_4-\alpha|\le\left(\frac29\right)^4(\sqrt5-2) \] \[ |x_4-\alpha|\lesssim0.000574 \] Il teorema garantisce che l'errore dopo quattro iterazioni sia inferiore a circa \(0.000574\). L'errore effettivo è molto più piccolo.

In conclusione, l'esempio mostra perché la scelta della funzione iterativa è fondamentale nel metodo del punto unito.

Partendo dalla stessa equazione \(x^2-5=0\), ho ottenuto due trasformazioni equivalenti:

\[ x=\frac5x \] \[ x=\frac12\left(x+\frac5x\right) \]

La prima produce una successione che oscilla senza convergere, mentre la seconda converge rapidamente alla radice positiva.

Quindi, non basta quindi trasformare l'equazione nella forma \(x=g(x)\). Occorre scegliere una funzione iterativa che soddisfi, quando possibile, le condizioni del teorema di convergenza.

Quale criterio di arresto scegliere?

Nelle applicazioni numeriche non è possibile eseguire un numero infinito di iterazioni. Occorre quindi stabilire quando interrompere il procedimento.

Un criterio pratico consiste nello scegliere una tolleranza \(\varepsilon>0\) e confrontare due approssimazioni consecutive:

\[ |x_{n+1}-x_n|<\varepsilon \]

Quando questa condizione è soddisfatta, il procedimento viene arrestato.

Ad esempio, scegliendo \(\varepsilon=10^{-6}\), interrompo le iterazioni quando la differenza assoluta tra due approssimazioni consecutive diventa inferiore a un milionesimo.

Tuttavia, una differenza piccola tra due iterazioni non garantisce, da sola, che l'errore rispetto alla radice sia inferiore alla tolleranza scelta.

Se sono soddisfatte le condizioni del teorema di convergenza, posso utilizzare una stima più affidabile dell'errore:

\[ |x_n-\alpha|\le\frac{m}{1-m}|x_n-x_{n-1}| \]

dove \(\alpha\) è la radice cercata e \(m<1\) è la costante individuata nel teorema.

Questa disuguaglianza permette di stimare un limite superiore dell'errore senza conoscere il valore esatto della radice. Posso quindi arrestare il procedimento quando

\[ \frac{m}{1-m}|x_n-x_{n-1}|<\varepsilon \]

In questo caso ho la garanzia che

\[ |x_n-\alpha|<\varepsilon \]

ossia che la distanza tra l'approssimazione calcolata e la radice sia inferiore alla tolleranza prefissata.

Un altro controllo consiste nel calcolare il residuo dell'equazione originale:

\[ |f(x_n)| \]

Se il residuo è piccolo, significa che il valore \(x_n\) soddisfa approssimativamente l'equazione \(f(x)=0\). Tuttavia, un residuo piccolo non garantisce necessariamente che l'approssimazione sia vicina alla radice.

Ad esempio, considero l'equazione seguente \[ f(x)=x^2-5=0 \] Dopo due iterazioni del metodo del punto unito ho ottenuto \[ x_2\approx2.236111111 \] Calcolo il residuo sostituendo questo valore \( x=x_2 \) nell'equazione originale: \[ r = | x^2 - 5 | \] \[ r=|(2.236111111)^2-5| \] Ottengo: \[ r\approx0.0001929 \] Il residuo è vicino a zero. Questo significa che l'approssimazione soddisfa quasi esattamente l'equazione originale. Ovviamente il residuo non coincide necessariamente con l'errore sulla radice, che invece è \[ e_n=|x_n-\alpha| \] Dove \(\alpha \) è la radice esatta.

In conclusione, il confronto tra iterazioni consecutive è il criterio più semplice, mentre la stima dell'errore basata sul teorema di convergenza permette di arrestare il procedimento con una garanzia sulla precisione raggiunta. Il controllo del residuo costituisce un'ulteriore verifica del risultato.

Considerazioni finali

Il metodo iterativo del punto unito mi permette di cercare le radici di un'equazione costruendo una successione di approssimazioni successive.

La sua applicazione richiede tre operazioni fondamentali:

1. trasformare l'equazione nella forma \(x=g(x)\)
2. scegliere un valore iniziale
3. applicare ripetutamente la formula \(x_{n+1}=g(x_n)\).

La difficoltà principale non consiste nel calcolo delle iterazioni, ma nella scelta della funzione \(g(x)\).

Due trasformazioni della stessa equazione possono infatti produrre successioni con comportamenti molto diversi.

Per questo motivo, prima di applicare il metodo, è opportuno studiare la funzione iterativa e, quando possibile, verificare le condizioni che garantiscono la convergenza.

E così via.