Calcolo numerico/Bisezione corde secanti Newton

Data una funzione $f\colon [a,b]\to \mathbb {R}$, trovare $\alpha$ tale che $f(\alpha )=0$.

Metodo di bisezione

Teorema 4.1 (teorema degli zeri per funzioni continue)

Data una funzione $f\colon [a,b]\to \mathbb {R}$ con $f\in C^{0}(a,b)$ se $f(a)*f(b)<0$, allora esiste $\alpha \in (a,b)$ tale che $f(\alpha )=0$.

Definizione

Diciamo che $a,b$ costituiscono una bracket, cioè un intervallo contenente la radice, se $f(a)*f(b)<0$.

Idea del metodo di bisezione: abbiamo una bracket di partenza $(a,b)$, tale che $f(a)*f(b)<0$, e cerco una bracket più piccola, e così via.

I passi del metodo sono i seguenti: calcolo $c=(a+b)/2$ punto medio di $(a,b)$ (sul calcolatore per questioni di stabilità il punto medio si calcola come $c=a+(b-a)/2)$). Trovato $c$, si possono verificare tre casi:

1. se $f(a)*f(c)<0$ allora la nuova bracket è l'intervallo $(a,c)$;
2. se invece $f(c)*f(b)<0$, allora la bracket è $(b,c)$;
3. nel caso $f(c)=0$, $c$ è la radice cercata.

A partire da una bracket $T_{0}$, genero una sottosuccessione di intervalli $I_{k}$ di estremi $(a_{k},b_{k})$ con $k\geq 0$ con la proprietà che $I_{k}\subset I_{k-1}$, e tali che per ogni $f(a_{k})*f(b_{k})<0$. Viene contemporaneamente generata una successione di valori $C_{k}$ punti medi degli intervallini $I_{k}$, che converge alla radice.

A ogni iterazione, la distanza tra il punto medio $C_{k}$ e $\alpha$ è minore di metà dell'ampiezza della bracket. Sia $L_{0}=|b-a|$ l'ampiezza della bracket iniziale. Allora

$L_{k}=d(a_{k},b_{k})={\frac {L_{0}}{2^{k}}}.$

Di conseguenza possiamo affermare

$|C_{k}-\alpha |\leq 1/2L_{k}={\frac {L_{0}}{2^{k+1}}}$

Per ottenere un'approssimazione sufficientemente buona della radice si richiede che ${\frac {L_{0}}{2^{k+1}}}\leq \varepsilon$.

In termini di iterazioni segue che:

$2^{k+1}\geq {\frac {L_{0}}{\varepsilon }}\,\longrightarrow \,{\bar {k}}\geq \log _{2}({\frac {L_{0}}{\varepsilon }})-1$

dove ${\bar {k}}$ è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di $\varepsilon$. Il numero di iterazioni richieste dal metodo dipende solo dall'ampiezza della bracket iniziale.

La convergenza del metodo di bisezione è lenta, "lineare", e il metodo converge sempre. Questo metodo viene usato in mancanza di informazioni preliminari su dove si trova la radice, però non è applicabile a sistemi di equazioni non lineari. Per guadagnare una cifra decimale occorrono $3.3=\log _{2}10$ iterazioni.

Struttura generale degli altri metodi

Consideriamo la funzione $f$ e lo sviluppo di Taylor centrato in $\alpha$.

$f(x)=f(\alpha )+(x-\alpha )*f'(\xi ),\,\xi \in (\alpha ,x)$

che si riscrive come:

$0=f(\alpha )=f(x)-(\alpha -x)*f'(\xi )$

Definiamo il metodo iterativo nel seguente modo: assegnato $x_{0}$, per ogni $k\geq 0$ determiniamo la nuova iterata $x_{k+1}$ risolvendo l'equazione $\circ$:

$\,f(x_{k})+(x_{k+1}-x_{k})*m_{k}=0$

dove $m_{k}$ è un'opportuna approssimazione di $f'(x_{k})$.

Trovare la soluzione di $\circ$ equivale a trovare l'intersezione tra l'asse $x$ e la retta $y=m_{k}*(x-x_{k})+f(x_{k})$.

Esplicitando $x_{k+1}$, la relazione $\circ$ diventa

$x_{k+1}=x_{k}-m_{k}^{-1}f(x_{k}),\quad k\geq 0$

A seconda dell'approssimazione di $f'(x_{k})$ e quindi della scelta di $m_{k}$ si ottengono i metodi delle corde, secanti e di Newton.

Metodo delle corde

Scelta del coefficiente

Per ogni $k\geq 0$, scegliamo il coefficiente $m_{k}=m$ ponendo

$m={\frac {f(b)-f(a)}{b-a}},$

quindi la relazione $\circ$ diventa:

$x_{k+1}=x_{k}-{\frac {b-a}{f(b)-f(a)}}*f(x_{k}),\quad k\geq 0$

Caratteristiche

A differenza del metodo di bisezione, qui a ogni iterata si usa il vettore ottenuto all'iterata precedente.

Ordine di convergenza

Questo metodo ha un ordine di convergenza di $P=1$, quindi la convergenza è lineare.

Interpretazione gemetrica

Supponiamo di avere una funzione su un intervallo $[a,b]$, consideriamo un punto $x_{0}\in ({\sqrt {\alpha }},b)$, consideriamo la retta per $(x_{0},f(x_{0}))$ con coefficiente angolare $m$ definito come sopra.

L'iterata $x_{1}$ è l'intersezione di questa retta con l'asse delle ascisse. Consideriamo poi la retta per $(x_{1},f(x_{1}))$ parallela a quelle disegnate sopra, e l'intersezione con l'asse $x$ è l'iterata $x_{2}$.

Si considerano quindi rette tra loro parallele e ognuna passante per il punto $(x_{k},f(x_{k}))$.

Metodo delle secanti

Scelta del coefficiente

Per ogni $k\geq 0$, fisso il coefficiente $m_{k}$ ponendo

$m_{k}={\frac {f(x_{k})-f(x_{k-1})}{x_{k}-x_{k-1}}}$

quindi la relazione $\circ$ diventa:

$x_{k+1}=x_{k}-{\frac {x_{k}-x_{k-1}}{f(x_{k})-f(x_{k-1})}}*f(x_{k}),\quad \forall k\geq 0$

Caratteristiche

Questo non è un metodo del punto fisso, perché a ogni passo si considerano informazioni ottenute nelle due iterate precedenti. Tranne nel primo passo, in cui $f$ viene valutata nei due valori di innesco, a ogni iterazione viene fatta una sola valutazione della funzione, e quindi, rispetto al metodo delle corde, il costo computazionale non aumenta di molto, aumenta solo nella prima iterazione.

Ordine di convergenza =

Questo metodo è superlineare, perché $P>1$.

In particolare vale il seguente teorema.

Teorema 4.2

Se $f$ è $C^{2}$ in un opportuno intorno della radice, se $f'(\alpha )\neq 0$ cioè se $\alpha$ è una radice semplice, e se $x_{0},x_{1}\in U(\alpha )$, allora il metodo delle secanti converge con ordine $P=(1+{\sqrt {5}})/2=1.6$, cioè con una convergenza superlineare.

Interpretazione geometrica

A differenza del grafico precedente qui le rette non sono parallele. Dopo aver tracciato la retta per $(x_{k},f(x_{k}))$ e $(x_{k-1},f(x_{k-1})$, l'iterata successiva $x_{k+1}$ è l'intersezione di questa retta con l'asse $x$.

Metodo di Newton

Scelta del coefficiente

Si richiede che $f$ sia di classe $C^{1}$ in un opportuno intorno della radice, che $f'(\alpha )\neq 0$, e per ogni $k$, fissiamo il coefficiente $m_{k}=f'(x_{k})$. Allora

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}},\quad k\geq 0$

Caratteristiche

Il costo computazionale viene aumentato in modo considerevole perché viene richiesta anche la valutazione della funzione e della sua derivata prima in $x_{k}$.

Ordine di convergenza

Sotto opportune ipotesi di regolarità, il metodo permette di avere ordine di convergenza 2.

Interpretazione geometrica

Graficamente viene considerata la retta tangente alla funzione nel punto $(x_{k},f(x_{k}))$, e si considera la sua intersezione con l'asse $x$ che è l'iterata successiva.