Calcolo numerico/Radici di equazioni non lineari

Problema da risolvere

Data una funzione $f:[a,b]\to ℝ$, si cerca $\alpha$ tale che $f(\alpha )=0$. Si utilizzano metodi iterativi, cioè si cercano $x_k$ tali che

$\underset{k\to \mathrm{\infty }}{lim}{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\le c\ast 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

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 |\le c|x_k-\alpha {|}^P$

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

$E_{k+1}\le c{E}_k^P$

e in termini di errore relativo:

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

$\le c|{\alpha }^{P-1}|(\frac{|x_k-\alpha |}{\alpha }{)}^P\le 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\ast 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 =\underset{k\to \mathrm{\infty }}{lim}\frac{|x_{k+1}-\alpha |}{|x_k-\alpha {|}^P}=$

$\gamma =\underset{k\to \mathrm{\infty }}{lim}\frac{|5x_k^3+x_k^4-\alpha |}{|x_k-\alpha {|}^3}=$

$\gamma =5$