Calcolo numerico/Radici di equazioni non lineari

Problema da risolvere

Data una funzione $f\colon [a,b]\to \mathbb {R}$, si cerca $\alpha$ tale che $f(\alpha )=0$. Si utilizzano metodi iterativi, cioè si cercano $x_{k}$ tali che

$\lim _{k\to \infty }x_{k}=\alpha$

La convergenza del metodo non dipende solo dal metodo usato, ma anche dalla scelta del vettore d'innesco: infatti se il vettore d'innesco appartiene a un determinato intorno della radice, il metodo converge, altrimenti questa condizione non è verificata.

I metodi usati possono avere una convergenza lineare, del tipo $E_{k}\leq c*E_{k-1}$ in cui sono necessarie varie iterazioni prima che l'ordine di grandezza dell'errore diminuisca. Altrimenti può verificarsi una convergenza superlineare: consideriamo un esempio di convergenza quadratica, in cui a un certo passo $E_{k}=10^{-2}$, al successivo $E_{k+1}=10^{-4}$ e al successivo $E_{k+2}=10^{-8}$, cioè l'errore crolla velocemente.

Ordine di convergenza

Definizione

Consideriamo una successione $x_{k}\to \alpha$, con $x_{k}\neq \alpha \forall k$. Diciamo che la successione ha ordine di convergenza $P$ se esiste un $P\geq 1$ tale che

$\lim _{k\to \infty }{\frac {|x_{k+1}-\alpha |}{(|x_{k}-\alpha |)^{P}}}=\gamma$

dove $0<\gamma <1$ se $P=1$, mentre $\gamma >1$ se $P>1$. $\gamma$ si dice fattore di convergenza.

1. Se $P=1$ e $\gamma <1$ abbiamo una convergenza lineare;
2. se $P=1$ e $\gamma =1$ abbiamo una convergenza sublineare;
3. se $P>1$ e $\gamma >0$ abbiamo una convergenza superlineare.

In ogni caso, esiste una costante $c>0$ tale che

$|x_{k+1}-\alpha |\leq c|x_{k}-\alpha |^{P}$

Per $k$ abbastanza grande, cioè, in termini dell'errore assoluto:

$E_{k+1}\leq cE_{k}^{P}$

e in termini di errore relativo:

$E_{r,k+1}={\frac {|x_{k+1}-\alpha |}{\alpha }}\leq c{\frac {|x_{k}-\alpha |^{P}}{\alpha }}$

$\leq c|\alpha ^{P-1}|({\frac {|x_{k}-\alpha |}{\alpha }})^{P}\leq c\alpha ^{P-1}E_{r,k}^{P}$

Se $P=1$, più è piccola la costante $\gamma$ più il metodo converge rapidamente.

Supponiamo di avere $P=2$. Allora se $E_{k}=10^{-2}$, al passo successivo si ha $E_{k+1}=(10^{-2})^{2}=10^{-4}$, e $E_{k+2}=(10^{-4})^{2}=10^{-8}$. Se invece $P=1$, $E_{k+1}=c*10^{-2}$, dove $0<c<1$ e ci vogliono più iterazioni prima che cambi l'ordine dell'errore.

Esempi sui tipi di convergenza

Esempio 4.1 (convergenza lineare)

Consideriamo la successione

$x_{k+1}=\cos x_{k}$

con $P=1$. Allora $\gamma =\sin \alpha$.

Esempio 4.2 (convergenza sublineare)

In questo tipo di convergenza la velocità di convergenza diminuisce quando ci si avvicina ad $\alpha$. Consideriamo la successione:

$x_{k+1}=\sin x_{k}$

$\gamma =1$

Esempio 4.3 (convergenza superlineare)

Consideriamo la successione:

$5x_{k}^{3}+x_{k}^{4},\,P=3,\,x\in (0,1/3)$

allora

$\gamma =\lim _{k\to \infty }{\frac {|x_{k+1}-\alpha |}{|x_{k}-\alpha |^{P}}}=$

$\gamma =\lim _{k\to \infty }{\frac {|5x_{k}^{3}+x_{k}^{4}-\alpha |}{|x_{k}-\alpha |^{3}}}=$

$\gamma =5$