Bisezione corde secanti Newton

Data una funzione , trovare tale che .

Metodo di bisezione

Teorema 4.1

Data una funzione con se , allora esiste tale che .

 


Definizione 4.2

Diciamo che costituiscono una bracket, cioè un intervallo contenente la radice, se .

 



Idea del metodo di bisezione: ho una bracket di partenza , tale che , e cerco una bracket più piccola, e così via.


I passi del metodo sono i seguenti: calcolo punto medio di (sul calcolatore per questioni di stabilità il punto medio si calcola come ). Trovato , si possono verificare tre casi:

  1. se allora la nuova bracket è l'intervallo .
  2. Se invece , allora la bracket è .
  3. Nel caso , è la radice cercata.


A partire da una bracket , genero una sottosuccessione di intervalli di estremi con con la proprietà che , e tali che per ogni k, . Viene contemporaneamente generata una successione di valori punti medi degli intervallini , che converge alla radice.


Ad ogni iterazione, la distanza tra il punto medio e è minore di metà dell'ampiezza della bracket. Sia l'ampiezza della bracket iniziale. Allora

Di conseguenza possiamo affermare
Per ottenere un'approssimazione sufficientemente buona della radice si richiede che .


In termini di iterazioni segue che:

dove è il numero di iterazioni necessarie per ottenere un'approssimazione della radice a meno di . 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 iterazioni.

Struttura generale degli altri metodi

Considero la funzione e lo sviluppo di Taylor centrato in .

che si riscrive come:
Definisco il metodo iterativo nel seguente modo: assegnato , per ogni determino la nuova iterata risolvendo l'equazione :
dove è un'opportuna approssimazione di .


Trovare la soluzione di equivale a trovare l'intersezione tra l'asse x e la retta .


Esplicitando , la relazione diventa

A seconda dell'approssimazione di e quindi della scelta di si ottengono i metodi delle corde, secanti e di Newton.

Metodo delle corde

Scelta del coefficiente
Per ogni , scelgo il coefficiente ponendo

quindi la relazione diventa:

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 , quindi la convergenza è lineare.
Interpretazione gemetrica
Supponiamo di avere una funzione su un intervallo , considero un punto , considero la retta per con coefficiente angolare definito come sopra.

L'iterata è l'intersezione di questa retta con l'asse delle ascisse. Considero poi la retta per parallela a quelle disegnate sopra, e l'intersezione con l'asse x è l'iterata .


Si considerano quindi rette tra loro parallele e ognuna passante per il punto .

Metodo delle secanti

Scelta del coefficiente
Per ogni , fisso il coefficiente ponendo

quindi la relazione diventa:

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 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é .

In particolare vale il seguente teorema:

Teorema 4.2

Se è in un opportuno intorno della radice, se cioè se è una radice semplice, e se , allora il metodo delle secanti converge con ordine , cioè con una convergenza superlineare.

 
Interpretazione geometrica
A differenza del grafico precedente qui le rette non sono parallele. Dopo aver tracciato la retta per e , l'iterata successiva è l'intersezione di questa retta con l'asse x.

Metodo di Newton

Scelta del coefficiente
Si richiede che sia di classe in un opportuno intorno della radice, che , e per ogni , fissiamo il coefficiente . Allora

Caratteristiche
Il costo computazionale viene aumentato in modo considerevole perché viene richiesta anche la valutazione della funzione e della sua derivata prima in .
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 , e si considera la sua intersezione con l'asse x che è l'iterata successiva.
 PrecedenteSuccessivo