Metodi Numerici (A.A. 2007-2008)
Prof. F. Pitolli
Appunti delle lezioni su: metodo di Newton in IRn;
equazioni non lineari, metodo di bisezione e metodo di Newton in IR
Equazioni non lineari
Numerosi problemi applicativi vengono modellizzati da un’equazione non lineare del tipo
f (x) = 0
Lesoluzioniξ dell’equazione, cio`e quei valori tali chef (ξ) = 0, vengono chiamatiradici dell’equazione non lineare ozeri della funzione f.
Ci limiteremo al caso di radici reali.
1
Separazione delle radici
Prima di utilizzare un metodo numerico bisogna sapere:
• quante sono le radici (reali);
• dove si trovano approssimativamente;
• se ci sono delle simmetrie.
Per rispondere a queste domande si pu`o ricorrere alla tabu- lazione o al grafico della funzione f.
Separazione delle radici: esempio 1
Equazioni polinomiali: p4(x) = x4+ 2x3+ 7x2− 11 = 0
−10 −5 0 5 10
−2000 0 2000 4000 6000 8000 10000 12000 14000
x p4(x)
−2 −1.5 −1 −0.5 0 0.5 1 1.5 2
−20
−10 0 10 20 30 40 50
x p4(x)
ξ1• •ξ2
>> x=linspace(-10,10); >> x=linspace(-2,2);
>> f=x.^4+2*x.^3+7*x.^2-11; >> f=x.^4+2*x.^3+7*x.^2-11;
>> plot(x,f,x,zeros(1,length(x))) >> plot(x,f,x,zeros(1,length(x)))
Delle 4 radici di p4(x) due sono reali, ξ1 ∈ [−1.5, −1] e ξ2 ∈ [0.75, 1.25], mentre due sono complesse coniugate.
Separazione delle radici: esempio 2
Equazione trascendente: f (x) = cos x cosh x− 1 = 0 La funzione f (x) `e simmetrica rispetto all’origine ⇒ se ξ
`e radice lo `e anche −ξ ⇒ x > 0 (ξ = 0 `e radice banale)
0 0.5 1 1.5 2 2.5 3
−7000
−6000
−5000
−4000
−3000
−2000
−1000 0 1000
π π π π π π
f(x)=cosh(x)*cos(x)−1
0 0.5 1 1.5 2 2.5 3
−1000 0 1000 2000 3000 4000 5000 6000 7000
π π π π x π π
g(x)=cosh(x)
h(x)=1/cos(x)
>> x=linspace(0,3*pi); >> x=linspace(0,3*pi);
>> f=cosh(x).*cos(x)-1; >> g=cosh(x);
>> plot(x,f,x,zeros(1,length(x))) >> h=1./cos(x);
>> plot(x,g,’r’,x,h,’b’,x,zeros(1,length(x)),’k’)
4
Separazione delle radici: esempio 2
Equazione trascendente: f (x) = cos x cosh x− 1 = 0
0 0.5 1 1.5 2 2.5 3
−100
−80
−60
−40
−20 0 20 40 60 80 100
π π π π x π π
g(x)=cosh(x)
h(x)=1/cos(x)
0 0.5 1 1.5 2 2.5 3
−100
−80
−60
−40
−20 0 20 40 60 80 100
π π π π x π π
g(x)=cosh(x)
h(x)=1/cos(x)
>> axis([0 3*pi -100 100]) >> x=linspace(0,3*pi,300);
>> g=cosh(x);
>> h=1./cos(x);
>> plot(x,g,’r’,x,h,’b’,x,zeros(1,length(x)),’k’)
>> axis([0 3 -100 100])
5
Separazione delle radici: esempio 2
Ci sonoinfinite radici, che corrispondono alle intersezioni delle due curve h e g:
f (x) = 0 ⇔ h(x) = g(x)
Separazione delle radici: in ciascun intervallo
2k−12π2,2k +12π2, k = 1, 2, 3, ...
ci sono due radici. Per k → ∞ le due radici si avvicinano ai due estremi dell’intervallo.
Nota. In genere, nelle applicazioni interessa approssimare la radice pi`u piccola.
6
Metodo di bisezione (o metodo dicotomico)
Il metodo di bisezione`e un metodo molto semplice: una volta individuato un intervallo di separazione in cui si trova una sola radice, permette di costruire una successione {xk} di approssimazioni di ξ.
Ipotesi di applicabilit`a :
• `e stato separato un intervallo I = [a, b] in cui c’`e un’unica radice ξ;
• la funzione f `e continua in I: f ∈ C0[a, b];
• f (a)f (b) < 0.
x
•ξ
a b
f(x)
7
Metodo di bisezione: algoritmo
Si genera una successione di approssimazioni {xk} con xk ∈ [ak−1, bk−1] e
ξ ∈ [ak−1, bk−1].
•ξ
a0 b1=b0
f(x)
x x1•
a2=a1
•x2
b2 x3•
Algoritmo:
a0= a, b0= b per k = 1, 2, 3, ...
per xk = ak−1+b2 k−1 (punto medio di [ak−1, bk−1]) per se f (xk) = 0, allora stop
per se f (ak−1)f (xk) < 0, allora [ak, bk] = [ak−1, xk] per se f (xk)f (bk−1) < 0, allora [ak, bk] = [xk, bk−1]
8
Convergenza del metodo di bisezione
Errore di troncamento: ek = ξ− xk Convergenza: lim
k→∞xk = ξ ⇔ lim
k→∞|ek| = 0 Per il metodo di bisezione si ha
q • • • •
q ak−1 xk ξ bk−1
|ek| < bk−1− ak−1
2 =bk−2− ak−2
22 =· · · = b− a 2k
⇒ lim
k→∞|ek| < lim
k→∞
b− a 2k = 0
9
Ordine di convergenza
Sia {xk} una successione di approssimazioni conver- gente a ξ. La successione ha ordine di convergenza p e fattore di convergenza C, se esistono due reali p ≥ 1 e C > 0 tali che
klim→∞
|ek+1|
|ek|p =C
Nota. La convergenza si dice lineare se p = 1, Nota. quadratica se p = 2.
Metodo di bisezione: ordine di convergenza
Per k→ ∞ si ha |e|ek+1|
k|1 12.
⇒ Ordine di convergenza: 1 (lineare)
⇒ Fattore di convergenza: 12
La convergenza `e lenta, in quanto ad ogni passo l’errore viene dimezzato, cio`e ad ogni passo si guadagna una cifra binaria
⇒ poich´e 2−4 < 10−1 < 2−3, per guadagnare una
⇒ cifra decimale servono 3-4 iterazioni.
Metodo di bisezione: criteri di arresto
Nella pratica, a causa degli errori di arrotondamento e degli errori di troncamento non si verifica mai che f (xk) = 0. Quando si arrestano le iterazioni?
Criteri di arresto a posteriori
⎧⎪
⎪⎨
⎪⎪
⎩
|ek| |xk− xk−1| < ε
|f(xk)| < ε
Criterio di arresto a priori: La stima a priori del numero di iterazioni K necessario per ottenere un errore minore di ε `e
|ek| < b− a
2k < ε ⇒ K > log(b− a) − log(ε) log 2
12
Criteri di arresto: esempi
|ek| |xk− xk−1| < oppure |f(xk)| <
ξ•
a b
f(x)
x xk
•ξ
a
f(x)
x b
• xk
f (xk)`e ”grande” anche se xk `e ”vicino” a ξ
f (xk) `e ”piccolo” anche se xk `e ”lontano” da ξ
13
Esercizio
La crescita di una popolazione pu`o essere modellata, su un periodo di tempo piccolo, assumendo che la popolazione abbia un tasso di crescita proporzionale al numero di individui presenti in ciascun istante. SeN (t)indica il numero di individui al tempoteλ`e il fattore di crescita della popolazione, alloraN (t)soddisfa l’equazione differenziale
dN (t)
dt = λN (t).
La soluzione di questa equazione `e N (t) = N0eλt, dove N0 indica la popolazione iniziale.
Questo modello `e valido solo quando la popolazione `e isolata e non c’`e immigrazione dall’esterno. Se si suppone che ci sia una immigrazione a un tasso costante ν, il modello differenziale diventa
dN (t)
dt = λN (t) + ν
la cui soluzione `eN (t) = N0eλt+νλ(eλt− 1).
Supponendo che la popolazione iniziale sia di un milione di individui, che la comunit`a cresca di 435·000 immigrati il primo anno e che 1·564·000 individui siano presenti alla fine del primo anno, determinare il tasso di crescitaλdella popolazione.
14
Soluzione
Si tratta di risolvere nell’incognita λl’equazione non lineare N|t=1 anno = N0eλ+νλ(eλ− 1),
doveN|t=1 anno = 1·564·000,N0= 1·000·000,ν = 435·000.
q ⇒ f (λ) = eλ+0.435λ (eλ− 1) − 1.564 = 0 Separazione grafica
>> x=linspace(0,1);
>> f=exp(x)+0.435./x.*(exp(x)-1)-1.564;
Warning: Divide by zero.
(Type "warning off MATLAB:divideByZero"
to suppress this warning.)
>> plot(x,f,x,zeros(1,length(x)))
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
−0.5 0 0.5 1 1.5 2
λ f(λ)
.ξ
Intervallo di separazione: I = [a, b] = [0.05, 0.15]
qquad⇒f (a) =−0.0667, f(b) = 0.0672⇒f (a)f (b) < 0
15
Iterazioni
k ak−1 bk−1 xk |xk− xk−1| |f(xk)|
1 0.05000000000000 0.15000000000000 0.10000000000000 10.00000000000000 10.00000000000000 2 0.10000000000000 0.15000000000000 0.12500000000000 0.02500000000000 0.03250506973938 3 0.10000000000000 0.12500000000000 0.11250000000000 0.01250000000000 0.01548498364220 4 0.10000000000000 0.11250000000000 0.10625000000000 0.00625000000000 0.00704990930651 5 0.10000000000000 0.10625000000000 0.10312500000000 0.00312500000000 0.00285098217571 6 0.10000000000000 0.10312500000000 0.10156250000000 0.00156250000000 0.00075615469668 7 0.10000000000000 0.10156250000000 0.10078125000000 0.00078125000000 0.00029010206821 8 0.10078125000000 0.10156250000000 0.10117187500000 0.00039062500000 0.00023292996053 9 0.10078125000000 0.10117187500000 0.10097656250000 0.00019531250000 0.00002861013771 10 0.10097656250000 0.10117187500000 0.10107421875000 0.00009765625000 0.00010215388987 11 0.10097656250000 0.10107421875000 0.10102539062500 0.00004882812500 0.00003677037077
16
Metodo delle bisezioni: script MATLAB
format long;
f = inline(’exp(x)+0.435/x*(exp(x)-1)-1.564’,’x’) a = 0.05; b = 0.15; xn = (a+b)/2;
iter = 0; err1 = 10; err2 = 10;
for i= 1:30
if ( f(a)*f(xn) < 0 ) b = xn;
elseif ( f(xn)*f(b) < 0 ) a = xn;
end xv = xn;
xn = (a+b)/2;
iter = iter+1;
err1 = abs(xn-xv);
err2 = abs(f(xn));
[iter a b xn err1 err2]
end
17
Metodi di linearizzazione
Si approssima la funzione f (x) in un intorno I di ξ con la sua tangente o con la sua secante, calcolate tramite un opportuno sviluppo in serie di Taylor.
• Metodo di Newton-Raphson o
• metodo delle tangenti
• Metodo delle secanti
Metodo di Newton-Raphson
Approssimazione iniziale: x0 Prima iterazione: t0 `e la retta tangente a f (x) nel punto (x0, f (x0)):
t0→ y = f (x0) + f (x0)(x− x0) Nuova approssimazione x1:
intersezione tra t0 e y = 0. x
•ξ
a b
f(x)
x0 t0 (x0,f(x
0)).
x1
f (x0) + f (x0)(x1− x0) = 0 → x1= x0− f (x0) f (x0)
Metodo di Newton-Raphson
Nuova approssimazione: x1 Seconda iterazione: t1 `e la retta tangente a f (x) nel punto (x1, f (x1)):
t1 →y = f (x1) + f (x1)(x− x1) Nuova approssimazione x2:
intersezione tra t1 e y = 0. x
ξ•
a b
f(x)
x0 t0 (x0,f(x0)).
x1 t1
.
(x1,f(x 1))
x2
f (x1) + f (x1)(x2− x1) = 0 → x2 = x1− f (x1) f (x1)
20
Metodo di Newton-Raphson: algoritmo
Ad ogni iterazione k = 1, 2, . . . la nuova approssimazione xk `e data dall’intersezione tra la retta tk−1, tangente a f (x) nel punto (xk−1, f (xk−1)), e y = 0.
tk−1→y=f (xk−1)+f (xk−1)(x-xk−1) x
ξ•
a b
f(x)
xk−1 tk−1 (xk−1,f(xk−1)).
xk tk
.
(xk,f(xk))
xk+1
f (xk−1) + f (xk↓−1)(xk− xk−1) = 0 Algoritmo:
⎧⎪
⎪⎪
⎨
⎪⎪
⎪⎩
x0 dato
xk = xk−1− f (xk−1)
f (xk−1), k = 1, 2, . . .
21
Metodo di Newton-Raphson: convergenza
⎧⎪
⎪⎪
⎨
⎪⎪
⎪⎩
x0 dato
xk = xk−1− f (xk−1)
f (xk−1), k = 1, 2, . . . Ipotesi di applicabilit`a :
• `e stato separato un intervallo I = [a, b] in cui
• c’`e un’unica radice ξ;
• f, f , f sono continue in I: f ∈ C2[a, b];
• f (x) = 0 per x ∈ [a, b].
⇒ esiste un intorno J ⊆ I di ξ tale che, se x0 ∈ J, la successione delle approssimazioni{xk} converge a ξ. • [ • J • ]
•
a ξ x0 b
22
Metodo di Newton-Raphson: ordine di convergenza Ordine di convergenza: lim
k→∞
|ek+1|
|ek|p =C ek+1=ξ− xk+1 =
⎛
⎝ξ− f (ξ) f (ξ)
⎞
⎠−
⎛
⎝xk− f (xk) f (xk)
⎞
⎠=
= (ξ− xk)−
⎛
⎝f (ξ)
f (ξ)− f (xk) f (xk)
⎞
⎠
Sviluppo in serie di Taylor:
f (xk) = f (ξ) + f (ξ) (x k −ξ)
−ek
+12f (ξ)(xk−ξ)2+ ...
f (xk) f (ξ)
|ek+1|
ek−f (ξ)− f(ξ) + f (ξ)ek− 12f (ξ)e2k f (ξ)
=
12f (ξ)e2k f (ξ)
klim→∞
|ek+1|
|ek|2 =1 2
f (ξ) f (ξ)
⇒ p ≥ 2 se f (x) ∈ C3[a, b] la conver- genza `e almeno quadratica
23
Efficienza computazionale
Per valutare l’efficienza di un metodo iterativo bisogna tener conto sia dell’ordine di convergenza che del costo computazionale, cio`e della quantit`a di calcoli richiesta ad ogni passo.
Efficienza computazionale: E = p1/r p: ordine di convergenza del metodo
r: numero di valutazioni funzionali (calcolo di funzioni o derivate) richieste ad ogni passo
Metodo di bisezione: E = 1 Metodo di Newton: E = 21/2
24
Metodo di Newton-Raphson: esempio
Approssimare la radice ξ = 0 dell’equazione f (x) = 4x3− 5x = 0
con il metodo di Newton-Raphson scegliendo come ap- prossimazione iniziale una volta x0 = 0.5 e una volta x0 = 0.4.
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5
−2
−1.5
−1
−0.5 0 0.5 1 1.5 2
f(x) ξ.
x t0
a b
qqqqqqq x2k = 0.5
−0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5
−2
−1.5
−1
−0.5 0 0.5 1 1.5 2
f(x) ξ.
x t0
t1
a b
qqqqqqq x2k+1 =−0.5
25
Estremo di Fourier
Nel caso particolare in cui f (x) ha concavit`a fissa in un intervallo I si pu`o garantire la convergenza anche senza procedere a una separazione preliminare della radice.
Estremo di Fourier:
Data una funzione f continua e convessa in I = [a, b] con f (a)f (b) < 0, si dice estremo di Fourier di I l’estremo verso cui f rivolge la convessit`a .
Se esiste f , allora l’estremo di Fourier `e a o b a seconda che f (a)f (a) > 0 oppure f (b)f (b) > 0.
Estremo di Fourier: esempi
f(x)
a x b
Estremo di Fourier
f (x)<0 per x∈ [a, b]
f (a)f (a) > 0
f (b)f (b) < 0
⇒ a `e estremo di Fourier
f(x)
a x b
Estremo di Fourier
f (x)>0 per x∈ [a, b]
f (a)f (a) < 0 f (b)f (b) > 0
⇒ b`e estremo di Fourier
Metodo di Newton-Raphson: convergenza
Ipotesi di applicabilit`a :
•f (a)f (b) < 0
•f, f , f sono continue in I: f ∈ C2[a, b];
•f (x) = 0 per x∈ [a, b];
•f (x) = 0 per x∈ [a, b]e x0 `e l’estremo di Fourier di [a, b].
⇒ 1)esiste un’unica radice ξ∈ [a, b]; 2)la successione delle approssimazioni
xk= xk−1− f (xk−1) f (xk−1)
k = 1, 2, ...
`
e monotona e converge a ξ;
3)se f ∈ C3[a, b], la convergenza `e quadratica.
28
Esercizio 1
Separare la radice dell’equazione non lineare f (λ) = eλ+0.435λ (eλ− 1) − 1.564 = 0 λ> 0 e approssimarla con il metodo di Newton.
Script MATLAB
format long;
f = inline(’exp(x)+0.435/x*(exp(x)-1)-1.564’,’x’)
df = inline(’exp(x)+0.435/x*exp(x)-0.435/x^2*(exp(x)-1)’,’x’) a = 0.05; b = 0.15; xn = b;
iter = 0; err1 = 10; err2 = 10;
for i= 1:30 xv = xn;
xn = xv-f(xv)/df(xv);
iter = iter+1;
err1 = abs(xn-xv);
err2 = abs(f(xn));
[iter xn err1 err2]
end
29
Metodi di linearizzione
Metodo di Newton-Raphson (o delle tangenti)
x
ξ•
a b
f(x)
xk−1 tk−1 (xk−1,f(xk−1)).
xk tk
.
(xk,f(xk))
xk+1
Ad ogni iterazione k = 1, 2, . . . la nuova approssimazione xk `e data dall’intersezione tra la retta tk−1, tangente a f (x) nel punto (xk−1, f (xk−1)), ey = 0.
Algoritmo:⎧
⎨
⎩
x0 dato
xk= xk−1−f (xk−1)
f (xk−1), k = 1, 2, . . .
Metodo delle secanti con estremi variabili
x
ξ•
a b
f(x)
xk−1 sk−1
(xk−1,f(xk−1))
.
xk
(xk,f(xk)) xk−2 (xk−2,f(xk−2. ))
.
sk xk+1
Ad ogniiterazionek = 2, 3, . . .lanuova ap- prossimazione xk `e data dall’intersezione tra la retta sk−1, secante f (x) nei punti (xk−2, f (xk−2))e(xk−1, f (xk−1)), ey = 0.
Algoritmo:⎧
⎨
⎩
x0, x1 dati
xk= xk−1− f(xk−1) xk−1− xk−2
f (xk−1)− f(xk−2), k = 2, ...
30
Metodo delle secanti
⎧⎪
⎨
⎪⎩
x0, x1 dati
xk= xk−1− f(xk−1) xk−1− xk−2
f (xk−1)− f(xk−2), k = 2, ...
Vantaggi:
• si pu`o usare quando non si conosce la derivata di f (x) o quando f (x) `e nota per punti
• ad ogni passo richiede una sola valutazione funzionale
Svantaggi:
• servono due approssimazioni iniziali x0 e x1
• la scelta di x0 e x1 deve essere ”accurata”
31
Convergenza del metodo delle secanti
Se • `e stato separato un intervallo I = [a, b]simmetrico intorno alla radice ξ,
• f, f , f sono continue in I: f ∈ C2[a, b],
• f (x) = 0 per x ∈ [a, b],
⇒ esiste un intornoJ ⊆ I diξ tale che, se x0, x1∈ J, la successione delle approssimazioni{xk} converge a ξ con convergenza superlineare, cio`e 2 > p > 1.
Se f (x) = 0 in I, l’ordine di convergenza `e p = 1+
√5
2 ⇒ E = p 1.62
32
Esercizio
Data l’equazione non lineare f (x) = x3+1
3− cos x = 0: 1) individuare quante sono le radici e separarle,
2) fornire una stima a priori del numero di iterazioni nec- essarie per approssimare la radice minore ξ con un errore inferiore a = 10−6 tramite il metodo di bisezioni;
3) quante iterazioni sono necessarie per approssimare con la stessa tolleranza la radice ξ tramite il metodo di New- ton e il metodo delle secanti?
33
Traccia della soluzione
1) Tracciando qualitativamente i grafici delle funzioni y = g(x) = x3+1
3 y = h(x) = cos x, si isola lo zero unico nell’intervallo [0, 1].
Con Matlab si possono tracciare i grafici di f (x), g(x), h(x). La radice ξ `e l’intersezione tra il grafico di f (x) e l’asse delle x (e coincide, ovviamente, con l’intersezione tra i grafici di g(x) e h(x)).
2) Nell’intervallo [0, 1] sono verificate le ipotesi di appli- cabilit`a del metodo di bisezioni.
Quindi il numero di iterazioni K per cui |eK| ≤ si ricava dalla relazione
|eK| = |ξ − xK| ≤ b− a 2K ≤
⇒ K > log(b− a) − log
log 2 .
In questo caso a = 0, b = 1, = 10−6 ⇒K > 20.
3)Nel caso dei metodi di Newton e delle secanti si possono verificare le ipotesi di applicabilit`a nell’intervallo [0, 1]
sia analiticamente che per via grafica; l’estremo b = 1 `e l’estremo di Fourier dell’intervallo.
Il numero di iterazioni si pu`o calcolare eseguendo le iterate con un programma Matlab.
36
k xk(bisez.) |xk− xk−1| xk (Newton) |xk− xk−1| xk (secanti) |xk− xk−1|
1 0.500000000 1. 0., 1.
2 0.750000000 0.25e+0 0.793560583 0.21e+0 0.456715571 0.54e+0 3 0.625000000 0.12e+0 0.742925006 0.51e-1 0.658587384 0.20e+0 4 0.687500000 0.62e-1 0.739971453 0.29e-2 0.775393863 0.12e+0 5 0.718750000 0.31e-1 0.739961685 0.98e-5 0.736625691 0.39e-1 6 0.734375000 0.16e-1 0.739961685 0.11e-9 0.739832822 0.32e-2
7 0.742187500 0.78e-2 0.739962167 0.13e-3
8 0.738281250 0.39e-2 0.739961685 0.48e-6
9 0.740234375 0.19e-2 10 0.739257812 0.97e-3 11 0.739746097 0.49e-3 12 0.739990234 0.24e-3 13 0.739868164 0.12e-3 14 0.739929199 0.61e-4 15 0.739959717 0.30e-4 16 0.739974976 0.15e-4 17 0.739967346 0.76e-5 18 0.739963531 0.38e-5 19 0.739961624 0.19e-5 20 0.739962578 0.95e-6 Tempo di calcolo
Bisezione: 4.87secondi,Newton: 8.47secondi,Secanti: 4.46secondi 37
Metodo di Newton per sistemi
Sistema non lineare: F (X) = 0 X = [x1, x2, . . . , xn]T
Il metodo di Newton per la soluzione di sistemi non lineari si basa sulla linearizzazione della F (X) = [f1(X), . . . , fn(X)]T
Se le funzioni fi(X) hanno derivate parziali limitate, allora si pu`o sviluppare in serie di Taylor la funzione vettoriale F (X) scegliendo come punto iniziale X(k)
F (X) = F (X(k)) + JF(X(k)) (X− X(k)) + ...
dove [JF(X)]ij = ∂fi
∂xj `e lo jacobianodella F (X)
⇒ F (X(k+1))≈ F (X(k)) + JF(X(k)) (X(k+1)− X(k)) = 0
⇒
⎧⎨
⎩
X(0) dato
X(k+1)= X(k)−JF(X(k))−1F (X(k)) k≥ 0
38
Convergenza del metodo di Newton
Il metodo di Newton `e un metodo iterativo la cui fun- zione di iterazione `e Φ(X) = X − [JF(X)]−1F (X)
Teorema. Sia X una soluzione del sistema non lineare F (X) = 0
con F ∈ C2(I) (I ∈ IRn intorno di X).
Sia det JF(X) = 0 per X ∈ I.
⇒ i) ∃ A ⊆ I tale che, ∀ X(0) ∈ A, la successione {X(k+1)} = {Φ(X(k))} converge a X;
ii) la convergenza `e quadratica: lim
k→∞
||E(k+1)||
||E(k)||2 > 0.
39
Osservazioni sul metodo di Newton per sistemi
• Laconvergenzadel metodo `e legata all’accuratezzadell’approssi- mazione iniziale.
• Ad ogni passo bisogna verificare che det JF(X(k)) = 0. Nella pra- tica, si pu`o avere instabilit`a numerica se det JF(X(k))`e ”piccolo”
→ conviene utilizzare una precisione elevata.
• Poich´e il costo computazionale del calcolo di det JF(X(k)) pu`o essereelevato, si preferisce risolvere ad ogni passo il sistema lineare
JF(X(k))Y =−F (X(k)) ⇒ X(k+1)= X(k)+ Y
• Criterio di arresto: il procedimento iterativo viene arrestato quando ||X(k+1)− X(k)|| ≤ .
• A volte si preferisce ricalcolare JF(X(k)) non ad ogni iterazione ma dopo 3-4 iterazioni (metodi di tipo quasi-Newton).
40
Metodo di Newton per sistemi: n = 2
Per n = 2si ha:
f (X) = f (x, y) = 0 g(X) = g(x, y) = 0
Formula di Taylor di punto iniziale X(k)= [xk, yk]T:
⇓
f (X) = f (X(k)) + fx(X(k))(x− xk) + fy(X(k))(y− yk) + R1= 0 g(X) = g(X(k)) + gx(X(k))(x− xk) + gy(X(k))(y− yk) + R2= 0 dove R1 = R1(X, X(k)), R2= R2(X, X(k)) rappresentano il resto.
La soluzione approssimata del sistema non lineare `e la soluzione del sistema lineare che si ottiene trascurando il resto nello sviluppo precedente.
fx(X(k))(xk+1− xk) + fy(X(k))(yk+1− yk) =−f(X(k)) gx(X(k))(xk+1− xk) + gy(X(k))(yk+1− yk) =−g(X(k))
41
Metodo di Newton per sistemi: n = 2
⎧⎪
⎨
⎪⎩
fx(X(k))(xk+1− xk) + fy(X(k))(yk+1− yk) =−f(X(k))
gx(X(k))(xk+1− xk) + gy(X(k))(yk+1− yk) =−g(X(k))
⇓
JF(k)(X(k+1)− X(k)) =−F (X(k))
dove JF(k):= JF(X(k)) =
fx(X(k)) fy(X(k)) gx(X(k)) gy(X(k))
Ilsistema lineare ammette soluzione se
|JF(k)| = det JF(k) = 0 La soluzione `e
⎧⎪
⎪⎪
⎪⎪
⎪⎪
⎨
⎪⎪
⎪⎪
⎪⎪
⎪⎩
xk+1= xk− 1
|JF(k)|
f (Xk) gy(X(k))− g(X(k)) fy(X(k))
yk+1= yk− 1
|JF(k)|
g(Xk) fx(X(k))− f(X(k)) gx(X(k))
Esempio
Il problema di due specie che competono per la stessa quan- tit`a di cibo pu`o essere descritto dal sistema di equazioni differenziali
⎧⎨
⎩
x (t) = x(t)[2− 0.0002 y(t) − 0.0001 x(t)]
y (t) = y(t)[4− 0.0003 y(t) − 0.0004 x(t)]
dove x(t) e y(t) rappresentano le popolazioni delle due specie al tempo t.
Trovare i valori di equilibrio delle due specie.
Soluzione
Si devono trovare i valori di x(t) e y(t) che risolvono si- multaneamente le equazioni
⎧⎨
⎩
x (t) = 0 y (t) = 0 ⇒
⎧⎨
⎩
x = x[2− 0.0002 y − 0.0001 x] = 0 y = y[4− 0.0003 y − 0.0004 x] = 0 Si tratta quindi di risolvere il sistema non lineare
⎧⎨
⎩
f (x, y) = 2 x− 0.0002 x y − 0.0001 x2= 0 g(x, y) = 4 y− 0.0003 y2− 0.0004 x y = 0
Nota: le soluzioni x = y = 0, x = 0 e y = 13·333, x = 20·000 e y = 0 sono soluzioni banali (una o tutte e due le specie si sono estinte)
44
Esercizio
Dato il sistema non lineare
⎧⎨
⎩
f (x, y) = 2 x− 0.0002 x y − 0.0001 x2 = 0 g(x, y) = 4 y− 0.0003 y2− 0.0004 x y = 0 i) separare le radici;
ii) trovare, per ciascuna delle radici,una trasformazione adatta ad approssimarla con il metodo delle approssimazioni successive;
iii) utilizzare il metodo di Newton per approssimare la radice in D = [3000, 6000]× [6000, 9000].
45
Traccia della soluzione
i) Dalle due equazioni si pu`o ricavare y come funzione lineare di x:
⎧⎪
⎪⎨
⎪⎪
⎩
y = 104− 0.5 x y = 4
3(104− x) .
Le due rette si intersecano solo quando
⎧⎨
⎩
x = 4000 y = 8000
⇒ X = [4000, 8000] `e l’unica soluzione non banale del sitema dato.
46
ii) Il sistema non lineare di partenza pu`o essere riscritto in modo equivalente come
⎧⎪
⎪⎨
⎪⎪
⎩
y = 104− 0.5 x = ψ(x, y) x = 104−3
4y = ϕ(x, y) Si verificare facilmente che per il dominio D = [2000, 9000] × [3000, 9000], si ha Φ(D) ⊆ D (Suggerimento: ϕ e ψ sono funzioni monotone decrescenti).
⎧⎨
⎩
ϕx(x, y) =−0.5 ϕy(x, y) = 0 ψx(x, y) = 0 ψy(x, y) =−0.75
⇒ M =
⎡
⎣ 0.5 0 0 0.75
⎤
⎦ ⇒ ||M|| < 1
⇒ La trasformazione Φ = [ϕ, ψ]T `e una contrazione
47
Verificare che le trasformazioni
⎧⎪
⎪⎪
⎪⎪
⎨
⎪⎪
⎪⎪
⎪⎩
x = 10−4x y− 0.5 · 10−4x2= ϕ(x, y) y = 3
410−4− 10−4x y = ψ(x, y)
e
⎧⎪
⎪⎪
⎪⎪
⎪⎨
⎪⎪
⎪⎪
⎪⎪
⎩
x = 2· 104x− 2 x y = ϕ(x, y)
y =
4
3104y−4
3x y = ψ(x, y)
non soddisfano la condizione suffieciente per essere una contrazione.
Suggerimento: calcolare ϕx, ψx, ϕy e ψy in X.
48
iii) Le funzioni f, g ∈ C2(D).
⎧⎨
⎩
fx= 2− 2 · 10−4y− 2 · 10−4x fy =−2 · 10−4x gy= 4− 6 · 10−4y− 4 · 10−4x gx=−4 · 10−4y Utilizzando come approssimazione iniziale il punto medio del dominio D, dopo 30 iterazioni si ottiene
x30= 3999.998 y30= 8000.001
||E(30)||∞ = 0.43· 10−2
Cosa succede utilizzando il metodo dell’iterazione continua?
49
Riferimenti bibliografici
L. Gori, Calcolo Numerico: Cap. 3, §§ 3.1, 3.2, 3.3, 3.4 (escluso metodo di falsa posizione), 3.6 (escluso metodo delle secanti con estremo fisso), 3.9, 3.10
F. Pitolli, Problemi ai limti per equazioni differenziali ordinarie: §4
L. Gori, M.L. Lo Cascio, Esercizi di Calcolo Numerico: Es. 1.1, 1.4, 1.5, 1.8, 1.9, 1.10, 1.13, 1.14, 1.21, 1.27, 1.28, 1.29, 1.30, 7.12, 7.14, 7.29, 7.40
