Equazioni non lineari

BISEZIONE

•

TH. Per una funzione f(x) continua in un intervallo [a,b] tale che f(a)f(b)<0 esiste almeno un

punto x appartenente ad [a,b] tale che f(x)=0. In particolare la funzione ha un’unico zero se

monotona e un numero dispari altrimenti.

Il metodo si basa su questa proprietà e produce a ogni iterazione intervalli sempre più piccoli

contenenti la soluzione cercata. Richiede in input gli estremi dell’intervallo [a,b] in cui la funzione

deve assumere valori discordi, dopodiché ottiene la prima soluzione approssimata xm come punto

medio dell’intervallo e valuta la funzione nel punto. Se f(xm)=0 allora xm è la soluzione cercata,

altrimenti:

- se f(a) f(xm)<0 la radice è nell’intervallo [a,xm) assegna b=xm

- se f(xm) f(b)<0 la radice è nell’intervallo (xm,b] assegna a=xm

e procede con la seconda iterazione con il nuovo intervallo.

Bisection.m

La condizione f(xm)=0 può non essere mai verificata esattamente, perciò come criterio d’arresto si

utilizza un residuo e il metodo si arresta quando questo scende sotto ad una tolleranza prefissata.

Come residuo si può utilizzare l’ampiezza dell’ultimo intervallo ottenuto, o come in questo caso il

modulo di f(xm).

E’ un metodo molto robusto che, sotto l’unica ipotesi fatta e per funzioni monotone, converge

sempre all’unico zero. Lo svantaggio è che converge lentamente ed è condizionato dalla

conoscenza dell’intervallo iniziale contenente lo zero; inoltre nel caso di intervalli contenenti un

numero dispari di zeri il metodo si arresta al primo zero e non riesce ad individuare gli altri. 3 di 26

REGULA FALSI

•

Come il metodo di bisezione richiede in input gli estremi dell’intervallo [a,b] contenente lo zero

cercato, ma determina la prima soluzione approssimata come intersezione con l’asse x della retta

passante per i punti [a,f(a)] e [b,f(b)] di eq: In questo modo si

ottiene

un’approssimazione

della soluzione

migliore rispetto al

metodo di bisezione

successivamente valuta la funzione nel punto e, come per il metodo di bisezione, se f(x)=0 allora x

è la soluzione cercata, altrimenti:

- se f(a) f(x)<0 la radice è nell’intervallo [a,x) assegna b=x

- se f(x) f(b)<0 la radice è nell’intervallo (x,b] assegna a=x

e si prosegue iterando il procedimento nel nuovo intervallo.

Il metodo si arresta quando il modulo di f(x) è minore della tolleranza.

Robusto e con ordine di convergenza lineare. 4 di 26

RegulaFalsi.m

SECANTI

•

Simile al metodo Regula Falsi e procede allo stesso modo, con la differenza che utilizza a ogni

iterazione sempre gli ultimi 2 punti trovati in successione. Il metodo risulta quindi più veloce con

velocità di convergenza superlineare, tuttavia è meno stabile e potrebbe non convergere in quanto

non si ha la certezza di avere a ogni iterazione la soluzione cercata all’interno dell’intervallo [xi,

xi-1].

Secant.m

Anche in questo caso il metodo si arresta quando il modulo di f(x) è minore della tolleranza. 5 di 26

NEWTON

•

Come Regula Falsi e Secanti anche il metodo di Newton trova la soluzione a ogni iterazione

approssimando la funzione in input con una retta di eq:

Se il modulo di f(x) è minore della tolleranza il metodo si arresta, altrimenti procede con una nuova

iterazione ponendo x=x0.

Newton.m

Diversamente dai metodi precedenti non richiede un intervallo, ma solo un punto x0 che

rappresenta una stima iniziale della soluzione; inoltre richiede, oltre alla funzione, anche la

conoscenza della sua derivata, che vengono valutate a ogni iterazione. Un’altra limitazione è

legata al fatto che utilizzando la derivata della funzione, quando questa assume valore prossimi

allo zero (in particolare per radici in prossimità di punti di massimo/minimo) il metodo non

converge.

Tuttavia è un metodo molto utilizzato in quanto sotto opportune ipotesi risulta sempre convergente

e con velocità di convergenza quadratica. Inoltre se vale: 6 di 26

TH Convergenza globale

allora il metodo di Newton converge per ogni x0 appartenente [a,b].

• Criteri d’arresto

L’errore rispetto la soluzione esatta è impossibile da valutare essendo questa non nota a priori.

Una possibile scelta del residuo da utilizzare è la variazione (assoluta o relativa) delle ultime due

soluzioni approssimate ottenute, ma per utilizzare un residuo più affidabile e per poter confrontare i

metodi si è scelto di utilizzare il modulo di f(x) con x soluzione approssimata ottenuta dal metodo e

tolleranza sul residuo pari a 10^-6.

Come ulteriore criterio tutti i metodi si arrestano anche quando viene raggiunto il numero massimo

di iterazioni fissato pari a 100.

RISOLUZIONE

Eseguendo lo script matlab main_zeri.m è possibile scegliere tramite menu la funzione da

analizzare. In output il programma mostra un grafico della funzione con tutti gli zeri visibili e un

subplot con un grafico per ogni zero con le soluzioni approssimate ottenute dai vari metodi. Infine

viene mostrata per ogni zero una tabella contenete la soluzione ottenuta, il numero di iterazioni e

residuo, relativi con ogni metodo utilizzato.

Per poter confrontare i metodi, salvo casi paricolari, è stato scelto lo stesso intervallo iniziale per

tutte le funcion e come guess iniziale x0 per Newton uno degli estremi dell’intervallo. 7 di 26

• f(x)a FUNZIONE 1

E’ una funzione molto regolare, ha un’unico zero, è continua e con derivate continue e tutti i

metodo possono essere applicati senza problemi e risultano convergenti entro la tolleranza e le

iterazioni massime fissate. E’ stato scelto l’intervallo [-1,2] in cui la funzione assume valori discordi,

più ampio del necessario per confrontare meglio la velocità di convergenza dei vari metodi. 8 di 26

Si può notare come Bisection sia il metodo più lento mentre Regula Falsi ottenendo una migliore

approssimazione richiede un numero minore di iterazione. In questo caso, essendo la funzione

convessa a ogni iterazione in Regula Falsi si mantiene il primo estremo dell’intervallo a=-1, mentre

Secanti utilizzando gli ultimi 2 punti trovati, in questa funzione, arriva prima a convergenza. Si può

apprezzare che pur non essendo garantita la convergenza con Secanti, per funzioni regolari

converge con velocità superlineare, mentre Newton ottiene la convergenza con il minimo di

iterazioni, come si poteva prevedere dalla velocità quadratica. 9 di 26

Si può verificare che per la funzione in esame il metodo di Newton converge per ogni x0

appartenente ad [a,b] per qualunque intervallo contenente la soluzione cercata, ovvero con a e b

tali che fa*fb<0 essendo soddisfatte le condizioni di convergenza globale. Infatti si ha infatti

derivata prima diversa da 0 e funzione convessa in tutto il dominio. Come dimostrazione si

riportano i risultati (in termini di soluzione residuo e iterazioni) al variare di x0 nell’intervallo

[-800,700] con passo 100, utilizzando la funcion matlab test_x0N.m

Si può notare che:

- x0 = 0 guess più vicino alla soluzione, converge con residuo e iterazioni minime.

- x0 -> b converge ma aumentano molto velocemente il numero di iterazioni richieste, questo

è dovuto al fatto che la derivata aumenta (in valore assoluto) molto

rapidamente e a ogni iterazione xi è poco distante da xi-1.

- x0 = 800 la derivata cresce al punto che non è più rappresentabile in numeri di macchina e si

verifica un underflow. 10 di 26

• f(x)b FUNZIONE 2

La funzione è continua, lineare a tratti e simmetrica rispetto x=2, presenta due radici simmetriche a

x=5/6 e x=19/6. Tutti i metodi risultano convergenti entro la tolleranza e le iterazioni massime

fissate. 11 di 26

Come si può notare dal grafico anche le soluzioni approssimate sono simmetriche. Il metodo di

Bisezione ha dimezzato l’intervallo iniziale 19 volte ottenendo la peggiore approssimazione,

mentre gli altri metodi sono del tutto identici. Questo dipende dal fatto che Regula Falsi, Secant e

Newton sono metodi che ad ogni iterazione calcolano la soluzione approssimata di f(x) come la

soluzione esatta di un’approssimazione lineare, ma essendo la funzione lineare nel tratto dato in

input in una sola iterazione convergono proprio alla soluzione esatta. Tuttavia, essendo le soluzioni

esatte x=5/6 e x=19/5 numeri illimitati periodici, non possono essere rappresentate in numeri di

macchina e in conseguenza si ha che il residuo non è zero, ma nell’ordine della precisione di

macchina per via dell’errore di arrotondamento. Il guess x0 per newton è stato scelto come punto

interno l’intervallo scelto per gli altri metodi perché in corrispondenza di quei punti è discontinua la

derivata prima. Escludendo questi punti si dimostra, sempre con la funcion matlab test_x0N.m, che

Newton converge per ogni scelta di x0, si riportano i risultati al variare di x0 nell’intervallo [0,4] con

passo 0.4+eps, dove si è usata la precisione di macchina per evitare i punti di discontinuità.

12 di 26

13 di 26

FUNZIONE 3

• f(x)c

A prima vista la funzione ha certamente due zeri a circa x=-5.5 x=3.5 per i quali si possono

applicare tutti i metodi visti senza problemi. Per quanto riguarda il tratto centrale potrebbe avere

nessuna radice o 2 radici (distinte o coincidenti). 14 di 26

Si può verificare, andando a plottare con passo 10^-4, che la funziona ha in totale 4 zeri distinti.

Utilizzando Newton per gli zeri in figura si ottiene subito la convergenza alle soluzioni cercate entro

la tolleranza e le iterazioni fissate: 15 di 26

Il metodo di Newton è quindi il migliore da utilizzare sicuramente per i due zeri centrali, in quanto

può essere praticamente difficile conoscere l’intervallo contenente la soluzione cercata; richiesto in

input da altri metodi. Inoltre, come si può vedere utilizzando la funcion test_x0N.m, converge molto

velocemente anche a tutte le altre soluzioni cercate:

Potrebbero però verificarsi dei risultati anomali per via della forte irregolarità della funzione e delle

sue derivate e non è possibile verificare la convergenza globale. Si hanno in totale 2 punti di

massimo e un punto di minimo, quest'ultimo in particolare vicino ai due zeri centrali, in cui la

derivata prima diventa uguale a zero. 16 di 26

Per poter utilizzare comunque tutti i metodi descritti è stata creata la funcion initial_guesses.m che

presi in input i vettori x e y=f(x) restituire il numero totale di zeri nell’intervallo e la matrice con gli

estremi dell’intervallo contenente ogni zero presi come due valori successivi di x in cui y assume

valore discorde:

Và specificato che la funcion può non trovare effettiv