Ricerca di zeri
DEI - Univ. Padova (Italia)
Equazioni non lineari
• Il problema è ricavare le radici (gli zeri) di una funzione f(x), cioè i valori z:
f(z)=0
quando non si possa ottenere la soluzione in forma chiusa (una formula)
DEI - Univ. Padova (Italia)
Separazione delle radici
Per semplificare il problema e renderlo trattabile, bisogna individuare un intervallo I=[a,b] contenente un solo zero:
Separazione delle radici
DEI - Univ. Padova (Italia)
Metodi iterativi
• Un metodo iterativo fornisce una successione di approssimazioni alla soluzione {xn}:
• Avendo già a disposizione k approssimazioni, un metodo iterativo fornisce la n-esima:
zxnn=
∞→lim
),,,( 21 knnnnn xxxGx −−−= K
DEI - Univ. Padova (Italia)
Velocità di convergenza
• Data una successione di approssimazioni {xn} convergente a z, si definisce l’errore di troncamento al passo n-esimo:
• La successione ha ordine di convergenza p e fattore di convergenza C se:
il valore di p dà una indicazione della velocità con cui la soluzione viene raggiunta
nn xze −=
Ce
ep
n
n
n=+
∞→
1lim
DEI - Univ. Padova (Italia)
Efficienza computazionale
• Se p=1 la convergenza è lineare• Se p=2 la convergenza è quadratica
per grandi n le cifre raddoppiano ad ogni iterazione
• E se un metodo fa molte più operazioni a parità di p?
L’efficienza computazionale guarda il numero r di valutazioni della funzione f(x) e delle sue derivate
rpE /1=
DEI - Univ. Padova (Italia)
Teorema di Bolzano
• Sia• f(a)<0<f(b)• f è almeno C0
RR →⊂],[: bafEsiste z in (a,b): f(z)=0
Dimostrazione 1:per assurdo
Dimostrazione 2:per bisezione
DEI - Univ. Padova (Italia)
Dimostrazione: metodo di bisezione
• Il metodo di bisezione ci fornisce metodo per costruire una successione convergente a z:
Nnbax
bbaa
nnn ,,1
211
00
K=+
=
==
−−
• Se f(xn)=0 allora z=xn, altrimenti:
⎩⎨⎧
<⋅=<⋅=
−−
−−
0)()(],[],[0)()(],[],[
11
11
nnnnnn
nnnnnn
xfbfbxbaxfafxaba
DEI - Univ. Padova (Italia)
Dimostrazione: metodo di bisezione
• {an} è monotona non-decrescente • {bn} è monotona non-crescente
•
•
nnnnnncba
∞→∞→∞→== limlimlim
)()(lim0)(lim)(
)(lim)(lim)(
cfafafcf
bfafcf
nnnn
nnnn
=≤≤=
==
∞→∞→
∞→∞→
DEI - Univ. Padova (Italia)
Metodo di bisezione:esempio
I1
I2
I3
I4
f(x)=(x-1)2-x-2
DEI - Univ. Padova (Italia)
Metodo di bisezione:esempio
iterazioni
cn
iterazioni
f(cn)
Valore vero dello zero
DEI - Univ. Padova (Italia)
Metodo di bisezione: convergenza
• Al passo k dell’algoritmo
kkkkk
kkabababxze
222/)(
2002211 −
==−
=−
≤−= −−−− L
02
limlim 00 =−
≤∞←∞→ kkkk
abe
• E dunque la stima dell’errore dopo k passi è
DEI - Univ. Padova (Italia)
Metodo di bisezione: convergenza
Per k grande si ottiene che:
1−−≅ kkk xxe
21
11 ≅+
k
k
e
e
E dunque si ha:
Da cui l’ordine di convergenza è p=1
DEI - Univ. Padova (Italia)
Metodo di bisezione: Criterio di arresto
• Non possiamo eseguire il procedimento per infinite iterazioni
• Quando fermarsi?
ε≤−=
− −−k
kk abab22
0011
ε22 log)(log −−≥ abk
DEI - Univ. Padova (Italia)
Metodo di bisezione: Matlab
function z=Bisezione(f,a,b,tol,display);
an=a;bn=b;cn=(bn+an)/2;
while((bn-an)>tol)
cn=(bn+an)/2;
f1=feval(inline(f),an);f2=feval(inline(f),cn);f3=feval(inline(f),bn);if(f1*f2<0)
bn=cn;else
an=cn;end;
end;z=cn;
Condizione di convergenza
Aggiornamento del punto medio(bisezione)
Calcolo della funzione fnei nuovi punti an,bn,cn
DEI - Univ. Padova (Italia)
Punti fissi
• Ho una funzione non-lineare f(x) di cui voglio trovare una radice z t.c. f(z)=0
• Posso trovare una funzione ausiliara:
h(x)=x-φ(x)
con gli stessi zeri di f(x)
)(0)( xxxf ϕ=⇔=
DEI - Univ. Padova (Italia)
• Data una contrazione:
• Allora esiste uno ed un solo punto fisso z
Teorema delle contrazioni (Banach-Cacioppoli)
IxqxqRIII
∈∀≤∈∃⊂→
)(')1,0(:
ϕϕ
)(
lim
1−
∞→
=
=
nn
nn
xx
zx
ϕ
DEI - Univ. Padova (Italia)
Metodo del punto fisso: convergenza
• L’ordine di convergenza della successione costruita col teorema di Banach dipende dalla funzione φ() nell’intorno del punto fisso z
• Se f(z) è derivabile almeno p-volte in z, e:
allora l’ordine di convergenza è p
0)(1,,10)(
)(
)(
)(
=
−==
=
zpkz
zz
p
k
ϕ
ϕ
ϕ
K
DEI - Univ. Padova (Italia)
Metodo del punto fisso: criterio di arresto
• Se il metodo converge e φ è una contrazione:
111111
1
)()( −−−−−−
−
−+−≤−+−≤−+−≤−
−≤−
nnnnnnnnnn
nnn
xxxzqxxxzxxxzxz
xxqxz
ϕϕ
La successione converge con ordine di convergenza q
Disuguaglianza triangolare
DEI - Univ. Padova (Italia)
Metodo del punto fisso: criterio di arresto
• Se il metodo converge e φ è una contrazione:
01
1
1
1
xxq
qxz
xxq
qxz
n
n
nnn
−−
≤−
−−
≤− −
Stima dell’errore al passo n-esimo
Stima iniziale dell’errore dopo n passi
DEI - Univ. Padova (Italia)
Metodo del punto fisso : esempio
f(x)=(x-1)2-x-2
Proviamo a scegliereφ(x)=(x-1)2-2
con x in I=[0,4]
x0=2x1=φ(x0)=-1x2=φ(x1)=2x3=-1x4=2
DEI - Univ. Padova (Italia)
Metodo del punto fisso : esempio
Bisogna verificare che φ(x) sia una
contrazione in I!!!
DEI - Univ. Padova (Italia)
Metodo del punto fisso: esempio
Proviamo a scegliereφ(x)=(x+2)1/2+1con x in I=[0,4]
φ’(x)<1/2x in I=[0,4]
x0=2.0000x1=φ(x0)=3.0000x2=φ(x1)=3.2361x3=3.2882x4=3.2996x5=3.3021x6=3.3026x7=3.3026
DEI - Univ. Padova (Italia)
Metodo del punto fisso: Matlab
function z=PuntoFisso(f,a,b,tol,display);
j=1;cn=(a+b)/2;z(j)=cn;fz(j)=feval(inline(f),cn);
cold=cn+1;while(abs(cold-cn)>tol)
cold=cn;cn=feval(inline(f),cn); j=j+1;z(j)=cn;
end;
Condizione di convergenza
Inizializzazione
Iterazione di punto fisso