Bisezione corde secanti Newton

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

 

Definizione 4.2

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

 

Idea del metodo di bisezione: ho una bracket di partenza $(a,b)$$(a,b)$, tale che $f(a)*f(b)<0$$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$$c=(a+b)/2$ punto medio di $(a,b)$$(a,b)$ (sul calcolatore per questioni di stabilità il punto medio si calcola come $c=a+(b-a)/2)$$c=a+(b-a)/2)$). Trovato $c$$c$, si possono verificare tre casi:

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

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

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

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

$$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}}}$$

$$|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$${\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$$

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

dove ${\bar {k}}$${\bar {k}}$ è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di $\varepsilon$$\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$$3.3=\log _{2}10$ iterazioni.

Struttura generale degli altri metodi

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

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

$$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 )$$

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

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

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

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

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

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

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

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

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

Metodo delle corde

Scelta del coefficiente

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

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

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

quindi la relazione $\circ$$\circ$ diventa:

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

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

Caratteristiche

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

Ordine di convergenza

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

Interpretazione gemetrica

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

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

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

Metodo delle secanti

Scelta del coefficiente

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

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

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

quindi la relazione $\circ$$\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$$

$$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é ad ogni passo si considerano informazioni ottenute nelle due iterate precedenti. Tranne nel primo passo, in cui $f$$f$ viene valutata nei due valori di innesco, ad 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$$P>1$.

In particolare vale il seguente teorema:

Teorema 4.2

Se $f$$f$ è $C^{2}$$C^2$ in un opportuno intorno della radice, se $f'(\alpha )\neq 0$$f'(\alpha )\neq 0$ cioè se $\alpha$$\alpha$ è una radice semplice, e se $x_{0},x_{1}\in U(\alpha )$$x_{0},x_{1}\in U(\alpha )$, allora il metodo delle secanti converge con ordine $P=(1+{\sqrt {5}})/2=1.6$$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}))$$(x_k,f(x_k))$ e $(x_{k-1},f(x_{k-1})$$(x_{k-1},f(x_{k-1})$, l'iterata successiva $x_{k+1}$$x_{k+1}$ è l'intersezione di questa retta con l'asse x.

Metodo di Newton

Scelta del coefficiente

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

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

$$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}$$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}))$$(x_{k},f(x_{k}))$, e si considera la sua intersezione con l'asse x che è l'iterata successiva.