Calcolo numerico/Bisezione corde secanti Newton

Data una funzione $f:[a,b]\to ℝ$, trovare $\alpha$ tale che $f(\alpha )=0$.

Metodo di bisezione

Teorema 4.1 (teorema degli zeri per funzioni continue)

Data una funzione $f:[a,b]\to ℝ$ con $f\in C^0(a,b)$ se $f(a)\ast f(b)<0$, allora esiste $\alpha \in (a,b)$ tale che $f(\alpha )=0$.

Idea del metodo di bisezione: abbiamo una bracket di partenza $(a,b)$, tale che $f(a)\ast 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)\ast f(c)<0$ allora la nuova bracket è l'intervallo $(a,c)$;
2. se invece $f(c)\ast 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\ge 0$ con la proprietà che $I_k\subset I_{k-1}$, e tali che per ogni $f(a_k)\ast 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 |\le 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}}\le \epsilon$.

In termini di iterazioni segue che:

$2^{k+1}\ge \frac{L_0}{\epsilon }⟶\overline{k}\ge {\log }_2(\frac{L_0}{\epsilon })-1$

dove $\overline{k}$ è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di $\epsilon$. 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 )\ast f^{\prime }(\xi ),\xi \in (\alpha ,x)$

che si riscrive come:

$0=f(\alpha )=f(x)-(\alpha -x)\ast f^{\prime }(\xi )$

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

$f(x_k)+(x_{k+1}-x_k)\ast m_k=0$

dove $m_k$ è un'opportuna approssimazione di $f^{\prime }(x_k)$.

Trovare la soluzione di $\circ$ equivale a trovare l'intersezione tra l'asse $x$ e la retta $y=m_k\ast (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),k\ge 0$

A seconda dell'approssimazione di $f^{\prime }(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\ge 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)}\ast f(x_k),k\ge 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\ge 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})}\ast f(x_k),\mathrm{\forall }k\ge 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^{\prime }(\alpha )\ne 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^{\prime }(\alpha )\ne 0$, e per ogni $k$, fissiamo il coefficiente $m_k=f^{\prime }(x_k)$. Allora

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)},k\ge 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.