Risoluzione di equazioni non lineari con metodi numerici

Risoluzione di equazioni non lineari con metodi numerici

L'obiettivo di questa lezione è imparare strumenti che ci permettano di calcolare con metodi numerici le soluzioni di un'equazione non lineare di tipo $f(x)=0$.

Supponiamo esista $\alpha \in ℝ$ tale che $f(\alpha )=0$. Vogliamo costruire una successione $x_k$, con $k\in \mathbb{N}$, tale che

$\underset{k\to \mathrm{\infty }}{\lim }{x}_k=\alpha$

Il numero $\alpha$ è detto radice (della funzione $f$).

Convergenza

Se la successione definita dal metodo numerico converge, possiamo allora chiederci quanto converga velocemente. A questo scopo si definisce l'ordine di convergenza di una successione:

Definizione (Ordine di convergenza). Una successione $x_k$ converge ad $\alpha$ con ordine $p\ge 1$ se

$|x_{k+1}-\alpha |\le C|x_k-\alpha {|}^p,\mathrm{\forall }k>0,$

$p$ è l'ordine di convergenza del metodo numerico che ha generato la successione $x_k$. Se $p=1$, il metodo converge linearmente e la costante $C$ è detta fattore di convergenza.

La quantità

$e_{k+1}\equiv |x_{k+1}-\alpha |$

costituisce l'errore commesso al passo $k$. In generale, con un metodo numerico, non vorremo fare infinite iterazioni e cercheremo solo un'approssimazione $\overline{\alpha }$ del valore $\alpha$. In particolare, potremo definire una tolleranza $ϵ$ tale che se $|x_k-\alpha |\le ϵ$ allora $\overline{\alpha }=x_k$.

Esempio

Supponiamo che la successione $x_k$ converga ad $\alpha$ con ordine 2, dove la costante $C=1$, e supponiamo che l'errore iniziale $e_0=|x_0-\alpha |=0.1$. Consideriamo un tolleranza $ϵ=10^{-10}$, allora il metodo numerico convergerà al più in quattro iterazioni, ovvero $\overline{\alpha }=x_4$, infatti:

$e_0=|x_0-\alpha |\le 10^{-1}$

$e_1=|x_1-\alpha |\le 10^{-2}$

$e_2=|x_2-\alpha |\le 10^{-4}$

$e_3=|x_3-\alpha |\le 10^{-8}$

$e_4=|x_4-\alpha |\le 10^{-16}$