CALCOLO NUMERICO
Francesca Mazzia
Dipartimento Interuniversitario di Matematica Universit`a di Bari
Metodi numerici per zeri di funzioni
1
Metodo delle successive bisezioni
Se f (x) ∈ C([a, b]) ed f (a) f (b) < 0, per il teorema di Bolzano, esiste almeno uno zero reale α contenuto nell’intervallo [a, b].
Supponiamo che α sia l’unico zero contenuto nell’intervallo [a, b]. Posto a0 = a, b0 = b, risulta f (a0) f (b0) < 0; si considera come prima stima di α il punto medio dell’interval- lo, ovvero
c0 = a0 + b0 2 .
Si calcola poi il valore che la funzione assume in tale punto:
se f (c0) = 0 abbiamo trovato la soluzione, se f (c0) 6= 0:
f (a0) f (c0) < 0 =⇒ lo zero cade in [a0, c0[ e si definisce come nuovo intervallo [a1, b1] = [a0, c0].
f (c0) f (b0) < 0 =⇒ lo zero cade in [c0, b0[ e si considera come nuovo intervallo [a1, b1] = [c0, b0].
2
A questo punto si analizza nuovamente il comportamento della funzione nel punto me- dio
c1 = a1 + b1 2
assunto come nuova approssimazione dello zero, ed il processo si ripete.
La procedura definita dal metodo delle bi- sezioni determina una sequenza di intervalli ciascuno dei quali `e contenuto nel precedente [an, bn] ⊆ [an−1, bn−1] ⊆ . . . ⊆ [a1, b1] ⊆ [a0, b0];
il generico intervallo ha ampiezza pari alla met`a di quella dell’intervallo precedentemen- te determinato e contiene lo zero α di f (x).
Generalizzando, la procedura costruisce la suc- cessione dei punti medi
cn = an−1 + bn−1
2 n ≥ 1
e se f (cn) 6= 0, definisce i nuovi intervalli nel modo seguente
[an, bn] =
( [cn, bn−1] se f (cn) f (bn−1) < 0 [an−1, cn] se f (an−1) f (cn) < 0.
3
Convergenza del metodo
Il metodo delle bisezioni fornisce sempre uno zero α di f in [a, b], quindi risulta essere sem- pre convergente. Per questo viene detto glo- balmente convergente.
Definiamo
|en| = |cn − α|
allora
|en| ≤ b − a 2n+1 quindi
nlim→∞cn = α
e l’errore viene dimezzato ad ogni iterata.
In particolare applicando il metodo al calcolo degli zeri di una data funzione, si pu`o osser- vare che ad ogni iterata si guadagna una cifra binaria e quindi dopo 3.3 iterate circa si gua- dagner`a una cifra decimale esatta, essendo 3.3 ' log2 10.
4
Criteri di arresto e stime dell’errore
Pur essendo comunque convergente `e neces- sario definire dei criteri di arresto che inter- rompano il succedersi delle iterazioni nel mo- mento in cui `e stata raggiunta una stima buo- na dello zero. Cio`e quando l’ errore relativo scende al di sotto di una certa tolleranza ε:
Ev =
cn − α α
< ε.
Possiamo considerare la successione degli estre- mi dell’intervallo definiti ad ogni passo e im- porre che l’ampiezza di quest’ultimo sia suf- ficientemente piccola:
bn − an = b − a
2n < ε.
sicuramente verificata se n > log2
b − a ε
.
Essa garantisce che α sia approssimata da cn con un errore assoluto minore in modulo di ε.
5
Nell’ipotesi che c = 0 non appartenga ad [a, b]
un altro criterio di arresto potrebbe essere bn − an
min(|an|, |bn|) < ε
il quale garantisce che la soluzione α sia ap- prossimata da cn con un errore relativo mino- re in modulo di ε. Un altro possibile criterio di terminazione `e
|f (cn)| < ε.
La costante ε non deve essere scelta troppo piccola perch`e a causa degli errori di arroton- damento l’ultima condizione di arresto po- trebbe non essere mai soddisfatta. Ad esem- pio pu`o accadere che al passo n-esimo an e bn siano cos`ı vicini da far risultare
cn+1 = an = bn mentre
f (cn+1) = ε2 > ε ε2 > 0.
Ne segue che
cn+1 = cn+2 = cn+3 = · · · e quindi
f (cn+2) = f (cn+3) = ε2
ed il processo non avr`a mai termine. Per prevenire questa possibilit`a si pu`o controllare ad ogni passo che
cn 6= an e cn 6= bn;
E quindi importante specificare anche un nu-` mero massimo di iterate per il procedimento iterativo.
6
Vantaggi e svantaggi
Il metodo delle bisezioni ha bisogno per po- ter essere implementato di due punti in cui la funzione assume segno opposto, che de- finiscano l’intervallo iniziale. Una volta lo- calizzato tale intervallo di osservazione, non importa quanto sia ampio, le iterazioni pro- cedono fino a convergere allo zero α della funzione. La convergenza globale `e sicura- mente uno dei vantaggi forniti dal metodo.
Tuttavia esso non pu`o essere sempre appli- cato come accade ad esempio per il calcolo di zeri di funzioni positive come f (x) = x2 che non verificano le ipotesi su cui si fonda.
A volte invece, pur verificandole, la funzione studiata presenta pi`u zeri all’interno dell’in- tervallo iniziale. In tale situazione per cia- scuno zero `e necessario individuare un inter- vallo diverso, talvolta di non facile localizza- zione perch`e di ampiezza piuttosto piccola.
Per risolvere questo problema intervengono i metodi cosiddetti ”localmente convergen- ti” che per poter essere implementati hanno per`o bisogno di una stima iniziale prossima allo zero.
7
Il polinomio di TAYLOR
Sia f (x) una funzione data e assumiamo che sia derivabile in un intervallo [a, b] con n + 1 derivate continue, n ≥ 0. Allora, dati x e x0 ∈ [a, b],
f (x) = pn(x) + Rn+1(x)
pn(x) =
f (x0) + (x − x0)
1! f0(x0) + · · · + (x − x0)n
n! f(n)(x0)
Rn+1(x) = 1 n!
Z x
x0(x − t)nf(n+1)(t)dt = (x − x0)n+1
(n + 1)! f(n+1)(ξ) ξ compreso fra x0 e x.
8
Metodi iterativi
Un metodo iterativo genera, a partire da un punto iniziale x0, una successione di punti xn definita da
xn+1 = φ(xn)
la funzione φ `e detta funzione iteratrice ed `e continua.
Se questo procedimento converge verso un punto α allora deve essere α = φ(α). Infatti:
α = lim
n→∞xn+1 = lim
n→∞φ(xn) e per la continuit`a della funzione φ:
α = lim
n→∞φ(xn) = φ( lim
n→∞xn) = φ(α).
Se siamo interessati a cercare uno zero α del- la equazione f (x) = 0, nella costruzione della funzione iteratrice φ(x) dobbiamo fare in mo- do che α = φ(α), in tal caso α `e detto punto fisso di φ.
I procedimenti iterativi hanno una interessan- te interpretazione grafica.
9
-2 -1 0 1 2 3 4 5
-2 -1 0 1 2 3 4 5
o oo
oo oo
oo oooo o
x0 x1 x2
y=x
xn+1 = φ(xn) ≡ (2xn + 5)1/3
Si disegna in un piano cartesiano la bisettri- ce del primo e terzo quadrante e la curva y = φ(x). Partendo dal punto iniziale x0 sul- l’asse orizzontale, si traccia la verticale fino ad incontrare la curva. Da questo punto si
traccia la parallela all’asse x fino ad incon- trare la bisettrice. L’ascissa del punto di in- tersezione `e il nuovo punto x1. Ripetendo la costruzione si ottengono gli altri punti.
Se l’equazione da risolvere `e non lineare, allo- ra i procedimenti iterativi possono diventare indispensabili, sia perch´e i metodi diretti pos- sono essere costosi, sia perch´e, molto spes- so, i metodi diretti non esistono. Il seguente teorema descrive una condizione sulla funzio- ne iteratrice φ che garantisce la convergenza locale della successione.
Per poter usare questo teorema `e necessaria una conoscenza approssimata sulla localizza- zione dello zero.
10
Teorema di contrazione o del punto fisso.
Sia xn+1 = φ(xn) un procedimento iterativo tale che α = φ(α) e con φ(x) derivabile e con derivata prima continua in un intorno I0 di α.
Se |φ0(α)| < λ < 1, partendo da un opportuno intorno di α, il procedimento converge ad α.
Dim. Per la continuit`a di φ0(x) in I0, esiste un altro intorno dello zero, contenuto in I0, che indicheremo con I, in cui |φ0(x)| < λ < 1.
Supponendo che x0 ∈ I, si ha
|x1 − α| = |φ(x0) − φ(α)| = |φ0(ξ)||x0 − α|
con ξ ∈ I. Essendo |φ0(x)| < λ < 1, si ha che x1 ∈ I.
Allo stesso modo si dimostra che tutti i suc- cessivi punti sono in I. Inoltre si ha
|xn − α| = |φ(xn−1) − φ(α)| < λ|xn−1 − α|
< . . . < λn|x0 − α|
e quindi
nlim→∞|xn+1 − α| = limn→∞λn|x0 − α| = 0 e il metodo converge.
11
Calcoliamo la radice positiva di f (x) ≡ x3 − 2x − 5.
Poich`e f (1.5) < 0, ed f (2.5) > 0, la radi- ce deve trovarsi nell’intervallo (1.5, 2.5). La funzione iteratrice pi`u immediata
φ(x) = 0.5 ∗ (x3 − 5),
che definisce il procedimento iterativo:
xn+1 = 0.5 ∗ (x3n − 5),
nell’intervallo (1.5, 2.5) `e sempre |φ0(x)| > 1 e quindi non `e soddisfatta l’ipotesi del teore- ma precedente. La funzione iteratrice φ(x) = (2xn + 5)1/3, che definisce il procedimento iterativo:
xn+1 = (2xn + 5)1/3,
invece soddisfa l’ipotesi del teorema essen- do, nell’intervallo considerato, 1/6 < φ0(x) <
0.15. Il procedimento `e quindi convergente.
12
Dopo aver trovato uno o pi`u procedimenti iterativi convergenti, `e necessario ancora di- stinguere tra questi in base ad altri criteri. Il principale di tali criteri `e la rapidit`a con cui la successione delle iterate converge. E possi-` bile definire un opportuno parametro che ef- fettua questa distinzione. Questo parametro
`e l’ ordine di convergenza.
en = xn − α errore al passo n-simo
Sia x0, x1, . . . , la successione ottenuta me- diante il metodo iterativo xn = φ(xn−1). Es- sa converge con ordine p ≥ 1 se esiste c > 0 tale che definitivamente
|en+1| ≤ c|en|p.
Nel caso p = 1 la convergenza si dice lineare;
in tal caso c deve essere strettamente minore di 1.
Se p = 2 la convergenza si dice quadratica.
13
Se la funzione φ `e sufficientemente regolare in un intorno del punto fisso α, l’ordine di convergenza p `e legato al valore delle derivate successive della φ.
Teorema. Sia φ(x) derivabile p volte in un intorno di α con derivata p-esima continua.
Allora la successione generata da φ ha ordine di convergenza p se e solo se risulta
φ0(α) = φ00(α) = . . . = φ(p−1)(α) = 0, e φ(p)(α) 6= 0.
Dimostrazione. `E sufficiente considerare lo sviluppo della serie di Taylor di φ in un intorno del punto fisso α, arrestato all’ordine p:
φ(x) = φ(α) + φ0(α)(x − α) + . . . + φ(p−1)(α)
(p − 1)! (x − α)p−1 + φ(p)(ξ)
p! (x − α)p
con ξ un opportuno punto tra x ed α. Si ha che en+1 = xn+1 − α = φ(xn) − φ(α) =
φ(p)(ξ)
p! (xn − α)p, da cui la tesi.
14
Come conseguenza osserviamo che se φ0(α) 6=
0, la convergenza del metodo `e lineare, men- tre se φ0(α) = 0, la convergenza `e almeno quadratica o superlineare. Un esempio clas- sico di un metodo di ordine p = 2 `e il metodo di Newton (o Newton-Rhapson).
Il Metodo di Newton
Supponiamo che la funzione f (x) abbia deri- vata non nulla; la funzione iteratrice φ(x) = x − f (x)/f0(x) definisce il procedimento ite- rativo
xn+1 = xn − f (xn) f0(xn)
detto metodo di Newton. Negli zeri di f (x) in cui f0(x) ´e diversa da zero, la derivata pri- ma di φ(x) si annulla. Infatti,
φ0(x) = 1 − (f0(x)2 − f (x)f00(x))/f0(x)2 e nel punto α, in cui f (α) = 0, si ha φ0(α) = 0.
Ci`o significa che in un opportuno intorno del- lo zero la convergenza del metodo `e superli- neare. Il metodo di Newton, quando la fun- zione f (x) ha derivata prima non nulla e de- rivata seconda continua in un intorno dello zero, ha ordine 2. Infatti si ha
xn+1 − α = φ(xn) − φ(α) =
= φ0(α)(xn − α) + 1
2φ00(ξn)(xn − α)2,
15
con ξn un opportuno punto tra lo zero ed xn, da cui, essendo φ0(α) = 0, si ha:
|en+1| = 1
2|φ00(ξn)||en|2. Se si pone
c = (1/2) maxξ |φ00(ξ)| ≡ (1/2) maxξ |f00(ξ)/f0(ξ)|, si ottiene che p = 2.
Il metodo di Newton ha una interessante in- terpretazione geometrica. Sia y = f (x) la curva definita dalla funzione di cui si vuol trovare uno zero. Gli zeri sono le intersezio- ni della curva con l’asse x. Sia x0 il punto iniziale, a cui corrisponde sulla curva il pun- to (x0, f (x0)). La retta tangente alla curva passante per tale punto ha equazione:
y = f (x0) + f0(x0)(x − x0).
Essa interseca l’asse x nel punto x1 dato da:
x1 = x0 − f (x0) f0(x0)
che `e proprio il primo punto ottenuto dal me- todo di Newton. Per questo motivo il meto- do di Newton `e anche chiamato metodo delle tangenti.
-20 0 20 40 60 80 100 120
1.5 2 2.5 3 3.5 4 4.5 5
o
o o
o o
o o oo ooooooo
x0 x1
x2
Metodo di Newton
Criteri di stop
xn+1 − α = φ(xn) − φ(α) = φ0(ξ)(xn − α), con ξ un punto compreso fra xn e α, si ha:
xn+1 − xn = (φ0(ξ) − 1)(xn − α), da cui si ha:
α − xn α
=
xn+1 − xn α(φ0(ξ) − 1)
=
1
α(φ0(ξ) − 1)
|xn+1 − xn| '
1
(φ0(ξ) − 1)
xn+1 − xn min(|xn|, |xn+1|)
.
Nell’ottenere l’ultima espressione si `e tenuto conto che quando il procedimento converge, i punti xn sono molto vicini allo zero.
Se si conosce una maggiorazione K < 1 del modulo di φ0(x) in un intorno di α, cio`e se esiste r > 0 tale che
∀x ∈]α − r, α + r[ : |φ0(x)| ≤ K < 1
16
allora `e possibile arrestare la procedura quan- do
1 (1 − K)
xn+1 − xn min(|xn|, |xn+1|)
< .
Uno studio a priori di φ0(x) in un intorno di α non `e sempre possibile, o comunque pu`o risultare complesso. Si utilizza in tali casi la condizione pi`u semplice:
xn+1 − xn min(|xn|, |xn+1|)
< .
Essa non rappresenta bene l’errore relativo quando φ0(x) `e vicino ad uno nell’intorno del- lo zero. Per i metodi superlineari (come il metodo di Newton) va invece molto bene.
Un altro criterio `e quello di arrestare il pro- cedimento quando:
|f (xn)| < .
Essendo f (xn) = f0(ξ)(xn−α), con ξ ∈ (α, xn), si ha:
α − xn α
=
f (xn) αf0(ξ)
da cui si deduce che il test `e valido se |αf0(ξ)| non `e troppo grande o troppo piccolo.
Metodi quasi-Newtoniani
Uno dei problemi del metodo di Newton `e che richiede il calcolo della derivata prima di f a ogni iterazione. Questo pu`o essere un problema quando
• La derivata pu`o essere costosa.
• La funzione f pu`o essere data con una formula complessa, e quindi `e difficile da calcolare.
• La funzione f si conosce solo come risu- latao di un lungo calcolo numerica e una formula per la derivata non `e disponibile.
Un modo per risolvere questo problema `e considerare il seguente procedimento itera- tivo
xn+1 = xn − f (xn) gn
17
con gn una approssimazione di f0(xn). Questi metodi vengono chiamati quasi-newtoniani.
Un esempio `e il metodo delle secanti, in cui la derivata `e approssimata dal rapporto in- crementale
gn = f (xn) − f (xn−1) xn − xn−1
un’altro esempio `e dato dal metodo della di- rezione costante in cui gn `e costante e il procedimento itarativo diventa:
xn+1 = xn − f (xn)
g = φ(xn) Se calcoliamo φ0(x) = 1−f0(xn)
g vediamo che il procedimento iterativo ´e convergente se
|φ0(α)| = |1 − f0(α)g | < 1 e il metodo converge linearmente.
Il metodo delle secanti
xn+1 = xn − xn − xn−1
f (xn) − f (xn−1)f (xn)
≡ f (xn)xn−1 − f (xn−1)xn f (xn) − f (xn−1) .
Questo procedimento iterativo non rientra nella classe dei procedimenti xn+1 = φ(xn), ma il nuovo punto dipende da due punti pre- cedenti, cio`e:
xn+1 = φ(xn−1, xn).
e necessita, per poter partire, di due punti iniziali.
L’interpretazione geometrica del metodo del- le secanti `e semplice. Il nuovo punto `e l’a- scissa del punto di intersezione con l’asse x della retta secante passante per i punti
(xn−1, f (xn−1)) e (xn, f (xn)).
18
Il metodo delle secanti `e superlineare nel ca- so in cui la funzione f abbia derivata seconda continua nell’intorno dello zero.
Si pu`o dimostrare che in questo caso l’ordi- ne `e p = 1.618. E un po’ meno veloce del` metodo di Newton ma ha il vantaggio che ad ogni passo calcola solo f (xn).
La stessa idea pu`o essere usata per ottene- re un procedimento iterativo ad un punto.
Basta tenere fisso uno dei due punti, per esempio x0. Si ottiene quindi:
xn+1 = xn − xn − x0
f (xn) − f (x0)f (xn).
Questo metodo, detto regula falsi `e lineare e quindi meno veloce del metodo delle secanti.
Errore, accuratezza e numero di condizione Quando cerchiamo di valutare la funzione f nel punto x il valore non sar`a esatto, ma otteniamo un valore perturbato
f (x) = f (x) + e(x)˜
L’errore e(x) pu`o essere generato da diverse fonti. Pu`o derivare dagli errori di arrotonda- mento, o dall’approssimazione fatta per va- lutare la funzione, per esempio se la fun- zione `e definita da un integrale che viene approssimato numericamente.
Dato α uno zero di f e supponiamo di cono- scere un limite superiore sull’errore |e(x)| < , se x1 `e un punto con f (x1) > allora
f (x˜ 1) = f (x1) + e(x1) ≥ f (x1) − ≥ 0
e quindi ˜f (x1) ha lo stesso segno di f (x1).
Lo stesso accade se f (x1) < −. Quindi se
|f (x)| > il segno di f (x) ci da informazioni sulla localizzazione dello zero.
19
Sia [a, b] il pi`u grande intervallo contenente α per cui
x ∈ [a, b] implica |f (x)| ≤
Se siamo fuori da questo intervallo il valore di ˜f (x) da informazioni sullo zero di f . Nel- l’intervallo il valore di ˜f (x) non ci da infor- mazioni, neanche sul segno della funzione.
L’intervallo [a, b] si chiama intervallo di in- certezza dello zero. Gli algoritmi che calco- lano una approssimazione dello zero all’inter- no di questo intervallo di incertezza si dicono stabili.
La grandezza dell’intervallo di incertezza va- ria da problema a problema. Se l’intervallo `e piccolo il problema si dice ben condizionato, quindi un algoritmo stabile risolver`a un pro- blema ben condizionato accuratamente. Se l’intervallo `e grande il problema si dice mal condizionato.
20
Per quantificare il grado di malcondiziona- mento calcoliamo il numero di condizione nel caso in cui f0(α) 6= 0.
f (x) ≈ f (α) + f0(α)(x − α) = f0(α)(x − α) segue che |f (x)| . quando |f0(α)(x−α)| . , quindi
|x − α| .
|f0(α)| cio`e
[a, b] ≈ [α −
|f0(α)|, α +
|f0(α)|].
quindi
1
|f0(α)|
`e il numero di condizione del problema.
21
Soluzione di sistemi non lineari
Siano f1, f2, . . . , fn, n funzioni scalari defi- nite nei punti x ∈ Rn e f (x) il vettore di Rn avente come componenti le fi(x):
f (x) =
f1(x) f2(x) ...
fn(x)
.
La f `e una funzione definita su Rn (o un suo sottoinsieme) a valori in Rn. Risolvere il sistema
f1(x) = 0 f2(x) = 0 ...
fn(x) = 0
equivale a cercare il vettore x ∈ Rn tale che f (x) = 0.
Esempio f (x) ≡ Ax − b con fi(x) ≡
n X j=1
aijxj − bi.
22
I procedimenti iterativi per sistemi sono for- malmente simili a quelli per equazioni scalari.
Essi sono del tipo
xk+1 = φ(xk)
con x0 scelto opportunamente. La funzione φ `e definita in Rn ed ha valori in Rn.
Se φ `e definita in un sottoinsieme D ⊂ Rn allora `e importante che φ(D) ⊆ D. Infatti, se xk ∈ D e φ(xk) 6∈ D allora φ(xk+1) non
`e pi`u definita ed il procedimento iterativo si arresta.
Supponiamo che la funzione φ sia almeno continua, in tal caso se la successione xk, per k = 0, 1, . . ., converge ad x, allora x `e un punto fisso della funzione iteratrice, cio`e x soddisfa l’equazione
x = φ(x).
23
Nella discussione sulla convergenza il ruolo che nel caso scalare aveva la derivata pri- ma della funzione iteratrice viene qui assunto dalla matrice Jacobiana:
φ0(x) ≡ J(x, φ) =
∂φ1
∂x1
∂φ1
∂x2 . . . ∂φ∂x1
n
... ... . . . ...
∂φn
∂x1
∂φn
∂x2 . . . ∂φ∂xn
n
.
si ha:
xk+1 − x = φ(xk) − φ(x),
e se φ0 `e continua in un intorno di x, allora kxk+1 − xk ≤ kφ0(ξ)kkxk − xk
con ξ `e un punto del segmento di estremi xk ed x.
Se I `e un intorno di x in cui
kφ0(x)k ≤ m < 1 , allora scegliendo x0 ∈ I il procedimento ite- rativo converge. Infatti si ha:
kxk+1 − xk ≤ mkxk − xk ≤ . . . ≤ mk+1kx0 − xk e quindi
lim
k→∞xk = x.
24
Il metodo di Newton `e definito da xk+1 = xk − J(xk, f )−1f (xk).
in cui φ(x) = x−J−1(x, f )f . Essendo φ0(x) = 0. Il metodo di Newton converge quando l’approssimazione iniziale della soluzione `e ab- bastanza buona.
Anche in questo caso il metodo ha ordine di convergenza due se J (x, f ) `e non singolare.
Dal punto di vista operativo conviene scrivere il metodo nella forma
J (xk, f )yk = −f (xk) xk+1 = xk + yk .
In questo modo si vede subito che ad ogni passo si deve risolvere un sistema lineare in cui la matrice dei coefficienti `e J (xk, f ) ed il vettore incognito `e yk.
25
Esempio Risolviamo il seguente sistema non lineare
( 2x1 − cos(x2) = 0 2x2 + sin(x1) = 0
con il metodo di Newton. La matrice Jaco- biana `e
J (x) = 2 sin(x2) cos(x1) 2
!
.
Considerato come vettore di partenza x0 = (0, 0)T e come condizione di uscita = 10−5, si ha la seguente successione di vettori:
x1 x2
0.0000000e + 00 0.0000000e + 00 5.0000000e − 01 −2.5000000e − 01 4.8646351e − 01 −2.3377308e − 01 4.8640516e − 01 −2.3372550e − 01 4.8640515e − 01 −2.3372550e − 01
La scelta del punto iniziale `e fondamentale per la buona riuscita del metodo. Se sce- gliamo x0 = (10, −10)T, la convergenza `e raggiunta dopo un numero superiore di passi.
26
x1 x2
1.0000000e + 01 −1.0000000e + 01
−1.8601703e + 00 −4.7037551e + 00
−2.5467277e + 00 3.8125600e − 01 2.6618546e − 01 1.4450598e + 00 1.0267753e + 00 −4.9842802e − 01 4.8929212e − 01 −2.8872174e − 01 4.8709056e − 01 −2.3402897e − 01 4.8640517e − 01 −2.3372556e − 01 4.8640515e − 01 −2.3372550e − 01 Quando la dimensione del sistema `e elevata, la soluzione del sistema lineare `e la fase pi`u costosa del metodo.
Per questo motivo, nei casi in cui la matri- ce Jacobiana `e lentamente variabile, si pre- ferisce usare la stessa matrice per un certo numero di passi (Metodo di Newton modi- ficato). In tal caso se si risolve il sistema lineare con la fattorizzazione LU, si pu`o usa- re la stessa fattorizzazione nei passi in cui la matrice J `e mantenuta costante.
Esempio Nell’esempio precedente modifican- do lo Jacobiano ogni 3 passi si ottiene:
x1 x2
−1.0000000e + 01 1.0000000e + 01
−1.8601703e + 00 −4.7037551e + 00 ∗
−1.4598251e + 00 6.4717047e − 01 2.4519162e − 01 1.2122400e + 00
9.6283807e − 01 −4.6946223e − 01 ∗ 2.5824358e − 01 −6.8647654e − 02 6.0527804e − 01 −2.9601886e − 01 4.8702539e − 01 −2.3587320e − 01 ∗ 4.8646237e − 01 −2.3376811e − 01 4.8640612e − 01 −2.3372766e − 01 4.8640515e − 01 −2.3372550e − 01 ∗
La convergenza `e ottenuta dopo 10 passi. Il numero di fattorizzazioni dello Jacobiano `e per`o ridotto a 4.
Esempio Usando il metodo di Newton cer- chiamo le soluzioni del sistema
( x1 + x2 = 3 x1x2 = 2 . La matrice Jacobiana `e:
J (x) = 1 1 x2 x1
!
e la sua inversa `e:
J−1 = 1 x1 − x2
x1 −1
−x2 1
!
. Quindi:
x(k+1)1 = x(k)1 − x(k)1 2 − 3x(k)1 + 2 x(k)1 − x(k)2
,
x(k+1)2 = x(k)2 − x(k)2 2 − 3x(k)2 + 2 x(k)2 − x(k)1
.
Il metodo converge sempre ad una delle due soluzioni (1, 2) e (2, 1), coppia di radici del polinomio p(x) = x2−3x+2. Infatti la somma delle radici di un polinomio di secondo grado
`e uguale al coefficiente del termine lineare cambiato di segno mentre il prodotto delle radici `e dato dal termine noto.
27
