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
Le soluzioni ξ dell’equazione, cio`e quei valori tali che f (ξ) = 0, vengono chiamati radici dell’equazione non lineare o zeri della funzione f.
Ci limiteremo al caso di radici reali.
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 ξ ∈ [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’)
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])
Separazione delle radici: esempio 2
Ci sono infinite radici, che corrispondono alle intersezioni delle due curve h e g:
f (x) = 0 ⇔ h(x) = g(x)
Separazione delle radici: in ciascun intervallo
h2k − 12 π2, 2k + 12 π2i , 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.
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)
Metodo di bisezione: algoritmo
Si genera una successione di approssimazioni {xk} con xk ∈ [ak−1, bk−1] e
ξ ∈ [ak−1, bk−1].
• ξ
a0 b
1=b
0
f(x)
x x1
•
a2=a
1
•
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]
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
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
k→∞lim
|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 |ek+1|
|ek|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
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 ξ
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. Se N (t) indica il numero di individui al tempo t e λ `e il fattore di crescita della popolazione, allora N (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 `e N (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.
Soluzione
Si tratta di risolvere nell’incognita λ l’equazione non lineare N |t=1 anno = N0eλ + λν(eλ − 1),
dove N |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
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
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
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(x
0)) .
x1
t1
.
(x1,f(x
1))
x2
f (x1) + f′(x1)(x2 − x1) = 0 → x2 = x1 − f (x1) f′(x1)
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(x
k−1)) .
xk
tk
.
(xk,f(x
k))
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, . . .
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) 6= 0 per x ∈ [a, b].
⇒ esiste un intorno J ⊆ I di ξ tale che, se x0 ∈ J, la successione delle approssimazioni {xk} converge a ξ. • [| • {zJ • }]
•
a ξ x0 b
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′(ξ) (xk − ξ)
| {z }
−ek
+12f′′(ξ)(xk − ξ)2 + ...
f′(xk) ≃ f′(ξ)
|ek+1| ≃
ek − f (ξ) − f(ξ) + f′(ξ)ek − 12f′′(ξ)e2k f′(ξ)
=
1
2f′′(ξ)e2k f′(ξ)
k→∞lim
|ek+1|
|e |2 = 1 2
f′′(ξ) f′(ξ)
⇒ p ≥ 2 se f (x) ∈ C3[a, b] la conver-
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
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
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) 6= 0 per x ∈ [a, b];
• f′′(x) 6= 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.
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
Metodi di linearizzione
Metodo di Newton-Raphson (o delle tangenti)
x
ξ•
a b
f(x)
xk−1
tk−1
(xk−1,f(x
k−1)) .
xk
tk
.
(xk,f(x
k))
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)), e y = 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(x
k−1))
.
xk
(xk,f(x
k)) xk−2
(x .
k−2,f(x
k−2))
.
sk
xk+1
Ad ogni iterazione k = 2, 3, . . . la nuova 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)), e y = 0.
Algoritmo:
x0, x1 dati
xk = xk−1 − f(xk−1) xk−1 − xk−2
f (xk−1) − f(xk−2), k = 2, ...
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”
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) 6= 0 per x ∈ [a, b],
⇒ esiste un intorno J ⊆ 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) 6= 0 in I, l’ordine di convergenza `e p = 1+
√5
2 ⇒ E = p ≃ 1.62
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 ξe 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 ξe tramite il metodo di New- ton e il metodo delle secanti?
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 `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.
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.87 secondi, Newton: ≃ 8.47 secondi, Secanti: ≃ 4.46 secondi
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 jacobiano della 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) − hJF(X(k))i−1 F (X(k)) k ≥ 0
Convergenza del metodo di Newton
Il metodo di Newton `e un metodo iterativo la cui fun- zione di iterazione `e Φ(X) = X − [JF(X)]−1 F (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) 6= 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.
Osservazioni sul metodo di Newton per sistemi
• La convergenza del metodo `e legata all’accuratezza dell’approssi- mazione iniziale.
• Ad ogni passo bisogna verificare che det JF(X(k)) 6= 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 essere elevato, 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).
Metodo di Newton per sistemi: n = 2
Per n = 2 si 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))
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))
#
Il sistema lineare ammette soluzione se
|JF(k)| = det JF(k) 6= 0 La soluzione `e
xk+1 = xk − 1
|JF(k)|
hf (Xk) gy(X(k)) − g(X(k)) fy(X(k)) i
yk+1 = yk − 1
|JF(k)|
h g(Xk) fx(X(k)) − f(X(k)) gx(X(k)) i
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)
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].
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.
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
4 y = ϕ(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
Verificare che le trasformazioni
x = 10−4 x y − 0.5 · 10−4 x2 = ϕ(x, y) y = 3
410−4 − 10−4 x y = ψ(x, y)
e
x = q2 · 104 x − 2 x y = ϕ(x, y)
y =
vu ut4
3104 y − 4
3 x y = ψ(x, y)
non soddisfano la condizione suffieciente per essere una contrazione.
Suggerimento: calcolare ϕx, ψx, ϕy e ψy in X.
iii) Le funzioni f, g ∈ C2(D).
fx = 2 − 2 · 10−4 y − 2 · 10−4 x fy = −2 · 10−4 x gy = 4 − 6 · 10−4 y − 4 · 10−4 x gx = −4 · 10−4 y
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?
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
