RISOLUZIONE NUMERICA DI SISTEMI NON LINEARI
Esempio:
si vuole risolvere numericamente ( x 1 2 − x 2 2 = 1
x 1 2 + x 2 2 − 2x 1 = 3. (1) Definisco:
f 1 (x 1 , x 2 ) = x 1 2 − x 2 2 − 1
f 2 (x 1 , x 2 ) = x 1 2 + x 2 2 − 2x 1 − 3 e F(x) =
f 1 (x 1 , x 2 ) f 2 (x 1 , x 2 )
Risolvere (1) vuol dire trovare α =
α 1 α 2
tale che F(α) = 0.
-2 0 2 x1 -3
-2 -1 0 1 2 3
x2
Pi` u in generale, per risolvere il sistema
f 1 (x 1 , x 2 , . . . , x n ) = 0 f 2 (x 1 , x 2 , . . . , x n ) = 0 .. .
f n (x 1 , x 2 , . . . , x n ) = 0
si definiscono x = [x 1 , x 2 , . . . , x n ] T e la funzione vettoriale
F : R n → R n : F(x) =
f 1 (x) = f 1 (x 1 , x 2 , . . . , x n ) f 2 (x) = f 2 (x 1 , x 2 , . . . , x n ) .. .
f n (x) = f n (x 1 , x 2 , . . . , x n )
Si cerca α = [α 1 , α 2 , . . . , α n ] T ∈ R n : tale che F(α) = 0.
METODO DI NEWTON PER SISTEMI
Ricordo che Newton per equazioni scalari ` e:
x (0) dato
x (k+1) = x (k) − f (x (k) )
f 0 (x (k) ) , k = 0, 1, ....
Per lavorare con funzioni vettoriali F(x) devo sostituire: f
0(x
(k)) con la matrice Jacobiana di F valutata in x
(k)J F (x (k) ) =
∂f
1∂x
1(x (k) ) ∂x ∂f
12
(x (k) ) ... ∂x ∂f
1n
(x (k) )
∂f
2∂x
1(x (k) ) ∂x ∂f
22
(x (k) ) ... ∂x ∂f
2n
(x (k) ) . . . . . . . . . . . .
∂f
n∂x
1(x (k) ) ∂x ∂f
n2
(x (k) ) ... ∂x ∂f
nn
(x (k) )
e reinterpretare la divisione 1/f
0(x
(k)) come calcolo della matrice inversa
J
F−1(x
(k)).
Allora il metodo di Newton per equazioni scalari
x (0) dato
x (k+1) = x (k) − f (x (k) )
f 0 (x (k) ) , k ≥ 0 diventa, per equazioni vettoriali:
( x (0) dato
x (k+1) = x (k) − J F −1 (x (k) )F(x (k) ) k ≥ 0 (2) Il problema cruciale ` e: come calcolare il vettore
z = x
(k+1)− x
(k)= −J
F−1(x
(k))F(x
(k))
Come calcolare z = −J F −1 (x (k) )F(x (k) )
Ad ogni iterazione k:
- valuto J F (x (k) ) e la memorizzo in una matrice A - valuto −F(x (k) ) e lo memorizzo in un vettore b - calcolo z = A\b
Attenzione: Il comando \ non calcola in maniera esplicita A −1 , ma calcola z risolvendo il sistema lineare Az = b
Se A ` e non singolare Az = b ⇔ z = A −1 b
Partendo dalla function newton.m scrivere NEWTON per SISTEMI newtonsys.m
Input: f, Jf, x0, tol, kmax k=0, err=tol+1
mentre k < kmax e err> tol valuto b = −F(x (k) ) valuto A = J F (x (k) ) risolvo Az = b
aggiorno la soluzione x (k+1) = x (k) + z calcolo l’errore err=kx (k+1) − x (k) k = kzk aggiorno k: k=k+1
aggiorno x
Output: zero, f(zero), n iterazioni, [err].
ESERCIZIO
(essisnl)
Calcolare numericamente le 4 radici del sistema non lineare
x 2 − y 2 = 1
x 2 + y 2 − 2x = 3 ⇔
x 1 2 − x 2 2 = 1
x 1 2 + x 2 2 − 2x 1 = 3 (3) con il metodo di Newton. Rappresentare graficamente su un solo grafico le storie di convergenza (ovvero gli errori kx k+1 − x k k al variare di k = 0, ..., k max ) e commentare i risultati ottenuti.
Scegliere questi tre dati inziali x0=[1;1], x0=[2;-1], x0=[-2;-2].
Svolgimento
1. Rappresentazione grafica per la localizzazione delle radici
2. Risoluzione numerica
1. Rappresentazione grafica per la localizzazione delle radici
x = [x 1 , x 2 ] t , f 1 (x) = x 1 2 − x 2 2 − 1, f 2 (x) = x 1 2 + x 2 2 − 2x 1 − 3.
Per localizzare le radici del sistema: disegno le superfici z = f 1 (x) e z = f 2 (x) e le contour f 1 (x) = 0 e f 2 (x) = 0.
f1 = @ ( x1 , x2 ) x1 .^2 - x2 .^2 -1;
f2 = @ ( x1 , x2 ) x1 . ^ 2 + x2 .^2 -2* x1 -3;
[ x1 , x2 ]= m e s h g r i d ( - 3 : . 1 : 3 ) ; z _ f 1 = f1 ( x1 , x2 );
z _ f 2 = f2 ( x1 , x2 );
f i g u r e ( 1 ) ; clf
m e s h c ( x1 , x2 , z _ f 1 ); t i t l e ( ’ z = f1 ( x_1 , x_2 ) ’) x l a b e l (’ x_1 ’ ); y l a b e l ( ’ x_2 ’)
h o l d on
c o n t o u r ( x1 , x2 , z1 ,[0 0] , ’ g ’, ’ l i n e w i d t h ’ ,2);
Disegnare f 2 su una seconda figura e le due contour (in z = 0) su
una terza figura.
-2 0 2 x1 -3
-2 -1 0 1 2 3
x2
f e Jf devono essere function handle che dipendono dal vettore x.
Prima per disegnare le superifici ho utilizzato gli array x1 e x2.
Ora per risolvere il sistema, x(1) e x(2) sono le componenti di un unico array x.
f ` e un function handle vettore colonna di 2 componenti f = @ ( x )[ f1 ( x (1) , x ( 2 ) ) ; % <−− f_1(x_1,x_2)
f2 ( x (1) , x ( 2 ) ) ] % <−− f_2(x_1,x_2) Jf ` e un function handle matrice 2 × 2
Jf = @ ( x ) [ 2 * x (1) , -2* x ( 2 ) ; % df_1/dx_1 , df_1/dx_2
2* x (1) -2 , 2* x ( 2 ) ] % df_2/dx_1 , df_2/dx_2
Definire gli altri input per newtonsys.m e chiamare newtonsys.m
Storie di convergenza.
Con i comandi
p l o t ( Err1 , ’ r ’); h o l d on
p l o t ( Err2 , ’ b ’); p l o t ( Err3 ,’ k ’)
l e g e n d (’ x0 =[1;1] , a l p h a = ( 2 , 1 . 7 3 ) ’ , ...
’ x0 =[2; -1] , a l p h a =(2 , -1.73) ’ , ...
’ x0 =[ -2; -2] , a l p h a =( -1 ,0) ’ ) si ottengono le seguenti storie di convergenza:
0 5 10 15 20 25 30
0 0.5 1 1.5 2 2.5
x0=[1;1], alpha=(2,1.73) x0=[2;−1], alpha=(2,−1.73) x0=[−2;−2], alpha=(−1,0)
La rappresentazione non ` e buona.
Comando semilogy
Sostituendo il comando plot con semilogy s e m i l o g y ( Err1 ,’ r ’ ); h o l d on
s e m i l o g y ( Err2 ,’ b ’ ); s e m i l o g y ( Err3 , ’ k ’) l e g e n d (’ x0 =[1;1] , a l p h a = ( 2 , 1 . 7 3 ) ’ , ...
’ x0 =[2; -1] , a l p h a =(2 , -1.73) ’, ...
’ x0 =[ -2; -2] , a l p h a =( -1 ,0) ’)
si ottengono le seguenti storie di convergenza:
0 5 10 15 20 25 30
10−10 10−8 10−6 10−4 10−2 100 102
x0=[1;1], alpha=(2,1.73) x0=[2;−1], alpha=(2,−1.73)
x0=[−2;−2], alpha=(−1,0)
