Francesca Mazzia
Dipartimento Interuniversitario di Matematica Universit` a di Bari
3. Algoritmi per la soluzione di sistemi lineari.
1
Sistemi triangolari inferiori
Sia L triangolare inferiore. La matrice ` e non singolare se gli elementi principali l i,i 6= 0, per i = 1, · · · , n.
Il sistema Lx = b pu` o scriversi:
l 1,1 x 1 = b 1
l 2,1 x 1 + l 2,2 x 2 = b 2 l 3,1 x 1 + l 3,2 x 2 + l 3,3 x 3 = b 3 . . .
. . .
l n,1 x 1 + l n,2 x 2 − . . . + l n,n x n = b n da cui si ottiene:
x 1 = b 1
l 1,1 , x 2 = b 2 − l 2,1 x 1 l 2,2
x 3 = b 3 − l 3,1 x 1 − l 3,2 x 2
l
in generale
x i =
b i −
i −1 X j=1
l i,j x j
l i,i i = 1, 2, . . . , n
Essendo l i,i 6= 0 queste formule determinano in modo univoco x i .
La procedura descritta si chiama algoritmo di sostituzione in avanti, in Matlab ` e descritta dal seguente algoritmo:
function b = soll(L,b) n = length(b);
b(1) = b(1)/L(1,1);
for i=2:n
b(i) = (b(i) - L(i,1:i-1)*b(1:i-1))/L(i,i);
end
3
L’istruzione matlab L(i,1:i-1)*b(1:i-1) ese- gue il prodotto riga per colonne fra il vettore L(i,1:i-1) e il vettore b(1:i-1).
L(i,1:i-1) elementi
( L(i,1), L(i,2), · · ·, L(i,i-1)) b(1:i-1) elementi
( b(1), b(2), · · ·, b(i-1)) Costo computazionale:
moltiplicazioni :
L(i,1:i-1)*b(1:i-1)
richiede i-1 moltiplicazioni
viene eseguita per i=2,n sommando
n X
2
(i − 1) =
n −1 X
1
i = n(n − 1)
2
Sistemi triangolari superiori
u 1,1 x 1 + u 1,2 x 2 + . . . + u 1,n x n = b 1 u 2,2 x 2 + . . . + u 2,n x n = b 2
. . . . . .
u n,n x n = b n
La matrice ` e non singolare se u i,i 6= 0.
La soluzione di questo sistema ` e:
x n = b n
u n,n , x n −1 = b n −1 − u n −1,n x n u n −1,n−1
x n −2 = b n −2 − u n −2,n−1 x n −1 − u n −2,n x n u n −2,n−2
5
In generale:
x i = 1 u i,i
b i −
n X j=i+1
u i,j x j
i = n, n −1, . . . , 1
La procedura descritta si chiama algoritmo di sostituzione all’indietro, in Matlab ` e descritta dal seguente algoritmo:
function b = solu(U,b) n = length(b);
b(n) = b(n)/U(n,n);
for i=n-1:-1:1
b(i) = (b(i) - U(i,i+1:n)*b(i+1:n))/U(i,i);
end
Matrici di permutazione
P r,s matrici di permutazione elementari si ot- tengono dalla matrice I di dimensione n × n scambiando la r.ma riga con la s.ma.
r s
P r,s =
1 0
0 . . . . . . . 1
0 0 . . . 0 1
0 1 0
... . . . ...
0 1 0
1 0 . . . 0 0
1 . . . . . . 0
0 1
r
s
P r,s A scambia le righe r ed s AP r,s scambia le colonne r ed s
7
Propriet` a delle matrici di permutazione Siano P, P 1 , P 2 matrici di permutazione n × n e A una matrice n × n allora:
1. PA ` e come A con le righe permutate.
AP ` e come A con le colonne permutate
2. P −1 = P T
3. det(P ) = ±1
4. P 1 P 2 ` e un matrice di permutazione.
Algoritmo di eliminazione di Gauss per risol- vere Ax = b:
1. Fattorizzare A in A = P LU con P = matrice di permutazione
L = matrice triangolare inferiore con ele- menti diagonali uguali a 1
U = matrice triangolare superiore non singolare
2. Risolvere P z = b, permutando le righe di b: z = LU x = P −1 b
3. risolvereLy = P −1 b,y = U x con l’algorit- mo di sostituzione in avanti
4. risolvere U x = L −1 (P −1 b) con l’algoritmo
di sostituzione all’indietro : x = U −1 (L −1 (P −1 b))
9
La sottomatrice principale di A di ordine j ` e A(1 : j, 1 : j).
Teorema. Le seguenti definizioni sono equi- valenti:
1. Esiste un’unica matrice triangolare L con elementi principali uguali ad 1 a un’u- nica matrice trangolare superiore U non singolare tale che A = LU .
2. Tutte le sottomatrici principali di A sono
non singolari
Dimostrazione: (1) implica (2) Partizioniamo le matrici A, L e U
A = LU ≡ A 1,1 A 1,2
A 2,1 A 2,2
!
= L 1,1 0 L 2,1 L 2,2
! U 1,1 U 1,2 0 U 2,2
!
= L 1,1 U 1,1 L 1,1 U 1,2
L 2,1 U 1,1 L 2,1 U 1,2 + L 2,2 U 2,2
!
A 1,1 sottomatrice principale di dimensione j.
det(A 1,1 ) = det(L 1,1 U 1,1 ) = det(L 1,1 )det(U 1,1 ) = 1 · Q j k=1 (u k,k ) 6= 0
proviamo che (2) implica (1) per induzione su n.
Per matrice di ordine 1 ` e vero: a = 1 · a.
11
Supponiamo sia vero per n − 1 e dimostria- molo per n.
Sia ˜ A di ordine n, allora dobbiamo mostrare che esistono e sono unici :
L e U triangolari di ordine n − 1,
s e t due vettori di lunghezza n −1 e η scalare tali che:
A = ˜ A b c T δ
!
= L 0
s T 1
! U t 0 η
!
= LU Lt
s T U s T t + η
!
Per induzione esistono L e U tali che A = LU .
Siano t = L −1 b, s T = c T U −1 e η = δ − s T t,
essi sono unici. Gli elementi diagonali di U
sono diversi da zero per induzione e η 6= 0
Algoritmo di eliminazione di Gauss Consideriamo il sistema lineare:
a 1,1 x 1 + a 1,2 x 2 + a 1,3 x 3 + a 1,4 x 4 = b 1 a 2,1 x 1 + a 2,2 x 2 + a 2,3 x 3 + a 2,4 x 4 = b 2 a 3,1 x 1 + a 3,2 x 2 + a 3,3 x 3 + a 3,4 x 4 = b 2 a 4,1 x 1 + a 4,2 x 2 + a 4,3 x 3 + a 4,4 x 4 = b 2
Poniamo m i,1 = a i,1 /a 1,1 , i = 2, 3, 4
e sottraiamo m i,1 moltiplicato per la prima equazione dalla equazione iesima.
a 1,1 x 1 + a 1,2 x 2 + a 1,3 x 3 + a 1,4 x 4 = b 1 a (1) 2,2 x 2 + a (1) 2,3 x 3 + a (1) 2,4 x 4 = b (1) 2 a (1) 3,2 x 2 + a (1) 3,3 x 3 + a (1) 3,4 x 4 = b (1) 3 a (1) 4,2 x 2 + a (1) 4,3 x 3 + a (1) 4,4 x 4 = b (1) 4
con
a (1) i,j = a i,j − m i,1 a 1,j , b (1) i = b i − m i,1 b 1
12
La variabile x 1 ` e stata eliminata dalle ultime tre equazioni.
Poniamo m i,2 = a (1) i,2 /a (1) 2,2 , i = 3, 4 e sot- traiamo m i,2 moltiplicato per la seconda equa- zione dalla equazione iesima.
a 1,1 x 1 + a 1,2 x 2 + a 1,3 x 3 + a 1,4 x 4 = b 1 a (1) 2,2 x 2 + a (1) 2,3 x 3 + a (1) 2,4 x 4 = b (1) 2
a (2) 3,3 x 3 + a (2) 3,4 x 4 = b (2) 3 a (2) 4,3 x 3 + a (2) 4,4 x 4 = b (2) 4 con
a (2) i,j = a (1) i,j −m i,2 a (1) 2,j , b (2) i = b (1) i −m i,2 b (1) 2
La variabile x 2 ` e stata eliminata dalle ultime
due equazioni.
Infine poniamo m i,3 = a (2) i,3 /a (2) 3,3 , i = 4 e sottraiamo m i,3 moltiplicato per la terza equazione dalla equazione iesima.
La variabile x 3 viene eliminata dall’ ultima equazione.
Otteniamo il sistema triangolare superiore:
a 1,1 x 1 + a 1,2 x 2 + a 1,3 x 3 + a 1,4 x 4 = b 1 a (1) 2,2 x 2 + a (1) 2,3 x 3 + a (1) 2,4 x 4 = b (1) 2
a (2) 3,3 x 3 + a (2) 3,4 x 4 = b (2) 3 a (3) 4,4 x 4 = b (3) 4 con
a (3) i,j = a (2) i,j −m i,3 a (2) 3,j , b (2) i = b (3) i −m i,2 b (3) 2
Questo algoritmo pu` o essere esteso ad un sistema di qualsiasi ordine.
14
Sia A 1 = A e
M 1 =
1 0 0 0
−m 2,1 1 0 0
−m 3,1 0 1 0
−m 4,1 0 0 1
allora
A 2 = M 1 A 1 =
=
1 0 0 0
−m 2,1 1 0 0
−m 3,1 0 1 0
−m 4,1 0 0 1
a 1,1 a 1,2 a 1,3 a 1,4 a 2,1 a 2,2 a 2,3 a 2,4 a 3,1 a 3,2 a 3,3 a 3,4 a 4,1 a 4,2 a 4,3 a 4,4
=
=
a 1,1 a 1,2 a 1,3 a 1,4 0 a (1) 2,2 a (1) 2,3 a (1) 2,4 0 a (1) 3,2 a (1) 3,3 a (1) 3,4 0 a (1) 4,2 a (1) 4,3 a (1) 4,4
M 2 =
1 0 0 0
0 1 0 0
0 −m 3,2 1 0 0 −m 4,2 0 1
A 3 = M 2 A 2 =
=
1 0 0 0
0 1 0 0
0 −m 3,2 1 0 0 −m 4,2 0 1
a 1,1 a 1,2 a 1,3 a 1,4 0 a (1) 2,2 a (1) 2,3 a (1) 2,4 0 a (1) 3,2 a (1) 3,3 a (1) 3,4 0 a (1) 4,2 a (1) 4,3 a (1) 4,4
=
=
a 1,1 a 1,2 a 1,3 a 1,4 0 a (1) 2,2 a (1) 2,3 a (1) 2,4 0 0 a (2) 3,3 a (2) 3,4 0 0 a (2) 4,3 a (2) 4,4
Infine
M 3 =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 −m 4,3 1
U = M 3 A 3 =
=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 −m 4,3 1
a 1,1 a 1,2 a 1,3 a 1,4 0 a (1) 2,2 a (1) 2,3 a (1) 2,4 0 0 a (2) 3,3 a (2) 3,4 0 0 a (2) 4,3 a (2) 4,4
=
a 1,1 a 1,2 a 1,3 a 1,4 0 a (1) 2,2 a (1) 2,3 a (1) 2,4 0 0 a (2) 3,3 a (2) 3,4 0 0 0 a (3) 4,4
U = M 3 M 2 M 1 A triangolare superiore.
Poniamo
L = M 1 −1 M 2 −1 M 3 −1 allora
A = LU
Possiamo scrivere la matrice
M 1 = I −m 1 e T 1 con m 1 = (0, m 2,1 , m 3,1 , m 4,1 ) T Si dimostra che
M 1 −1 = I + m 1 e T 1
infatti, essendo (e T 1 m 1 ) = 0
M 1 −1 M 1 = (I + m 1 e T 1 )(I − m 1 e T 1 ) =
= I + m 1 e T 1 − m 1 e T 1 + m 1 (e T 1 m 1 )e T 1 = I.
17
M 2 = I − m 2 e T 2 con m 2 = (0, 0, m 3,2 , m 4,2 ) T e M 2 −1 = I + m 2 e T 2
M 3 = I − m 3 e T 3 con m 3 = (0, 0, 0, m 4,3 ) T M 3 −1 = I + m 3 e T 3
Inoltre, essendo e T i m j = 0, i < j,
L = (I + m 1 e T 1 )(I + m 2 e T 2 )(I + m 3 e T 3 ) =
= I + m 1 e T 1 + m 2 e T 2 + m 3 e T 3 quindi
L =
1 0 0 0
m 2,1 1 0 0
m 3,1 m 3,2 1 0
m m m 1
Problemi dell’algoritmo di fattorizzazione LU senza permutazioni:
Non pu` o essere eseguita su matrici come:
P =
0 1 0 0 0 1 1 0 0
A =
1 2 5
−1 −2 −7
1 1 3
18
Presenta problemi di instabilit` a numerica:
( 10 −17 x 1 + x 2 = 1 x 1 + x 2 = 2
Il problema ` e ben posto, ed ha come solu- zione esatta x ' (1, 1) T . Applicando il me- todo di Gauss ed operando in virgola mobile in base 2 in doppia precisione, si ottengono i fattori L ed U seguenti:
L = 1 0
10 17 1
!
, U = 10 −17 1
0 −10 17
!
il prodotto LU non ` e A bens` ı la matrice se- guente
A = ˜ 10 −17 1
1 0
!
confrontando A con A si vede che l’ ele- ˜
mento a 22 di A ` e stato cambiato, pertan-
to la soluzione numerica che ` e ˜ x = (0, 1) T ` e
Teorema. Se A ` e non singolare, allora esisto- no due matrici di permutazione P 1 e P 2 , una matrice triangolare inferiore L con elementi diagonali uguali a uno e una matrice triango- lare superiore U tali che P 1 AP 2 = LU . Solo una fra P 1 e P 2 ` e necessaria.
P 1 A scambia le righe di A, AP 2 scambia le colonne,
P 1 AP 2 scambia righe e colonne di A.
20
Dimostrazione per induzione.
Per matrici di ordine 1 basta scegliere:
P 1 = P 2 = L = 1 e U = A.
Supponiamo sia vero per matrici di ordine n − 1 e sia A di ordine n.
Essendo A non singolare, allora ha sicura- mente un elemento diverso da zero.
Scegliamo P 1 0 e P 2 0 matrici di permutazione in modo da rendere l’elemento in posizione (1,1) di P 1 0 AP 2 0 diverso da zero.
Scriviamo la fattorizzazione e risolviamo per le componenti incognite.
P 0 AP 0 = a 1,1 A 1,2 !
1 0 L 2,1 I
! u 1,1 U 1,2 0 A ˜ 2,2
!
a 1,1 A 1,2 A 2,1 A 2,2
!
= u 1,1 U 1,2
L 2,1 u 1,1 L 2,1 U 1,2 + ˜ A 2,2
!
A 2,2 e ˜ A 2,2 di ordine n −1, L 2,1 e U 1,2 ∈ IR n −1 Risolvendo per le componenti di questa fat- torizzazione a blocchi otteniamo:
u 1,1 = a 1,1 6= 0 U 1,2 = A 1,2
L 2,1 = A 2,1 /a 1,1
A ˜ 2,2 = A 2,2 − L 2,1 U 1,2
det(P 1 0 AP 2 0 ) = ±det(A) 6= 0 det(P 1 0 AP 2 0 ) = 1 · u 1,1 det( ˜ A 2,2 )
22
det( ˜ A 2,2 ) 6= 0
quindi per induzione esistono due matrici di permutazione ˜ P 1 e ˜ P 2 tali che ˜ P 1 A ˜ 2,2 P ˜ 2 = ˜ L ˜ U . Sostituendo si ha:
P 1 0 AP 2 0 = 1 0 L 2,1 I
! u 1,1 U 1,2 0 P ˜ 1 T L ˜ ˜ U ˜ P 2 T
!
= 1 0
L 2,1 I
! 1 0 0 P ˜ 1 T L ˜
! u 1,1 U 1,2 0 U ˜ ˜ P 2 T
!
= 1 0
L 2,1 P ˜ 1 T L ˜
! u 1,1 U 1,2 0 U ˜
! 1 0 0 P ˜ 2 T
!
= 1 0
0 P ˜ 1 T
! 1 0 P ˜ 1 L 2,1 L ˜
! u 1,1 U 1,2 0 U ˜
! 1 0 0 P ˜ 2 T
!
quindi
P 1 AP 2 = 1 0 0 P ˜ 1
!
P 1 0 AP 2 0 1 0 0 P ˜ 2
!
= 1 0 ! u 1,1 U 1,2 !
Possiamo scegliere P 2 0 = I e P 1 0 in modo tale che a 1,1 sia il pi` u garnde elemento in valo- re assoluto nella colonna, il che implica che L 2,1 = A 2,1 /a 1,1 ha elementi limitati da 1 in valore assoluto. In generale al passo i dell’e- liminazione di Gauss, ordiniamo le righe da i a n in modo da portare l’elemento pi` u gran- de in valore assoluto in posizione i, i. Questa tecnica si chiama eliminazione di Gauss con Pivot Parziale.
Possiamo scegliere P 2 0 e P 1 0 in modo tale che a 1,1 sia il pi` u garnde elemento in valore asso- luto di tutta la matrice. In generale al pas- so i dell’eliminazione di Gauss, ordiniamo le righe e le colonne da i a n in modo da por- tare l’elemento pi` u grande in valore assoluto in posizione i, i. Questa tecnica si chiama eliminazione di Gauss con Pivot Totale.
23
L’algoritmo di eliminazione di Gauss con pi- vot parziale.
Se eseguiamo le permutazioni partendo dalla matrice A calcoliamo:
M 3 P 3 M 2 P 2 M 1 P 1 A = U
Per ricavarci la matrice P e la matrice L tali che P A = LU poniamo
M ˜ 2 = P 3 M 2 P 2 T = P 3 (I −m 2 e T 2 )P 3 T = I −P 3 m 2 e T 2 M ˜ 1 = P 3 P 2 M 2 P 2 T P 3 T = P 3 P 2 (I − m 1 e T 1 )P 2 T P 3 T
= I − P 3 P 2 m 1 e T 1 e
P = P 3 P 2 P 1 quindi
L = ˜ M 1 −1 M ˜ 2 −1 M 3 −1
cioe’ gli elementi dei vettori m che costitui-
function [L,U] = gauss(A) [n,m] = size(A);
for k=1:n −1
if abs(A(k,k)) <= realmin
error(’ Un elemento pivotale e” piccolo’) else
L(k+1:n,k)= A(k+1:n,k)/A(k,k);
end
A(k+1:n,k+1:n)=A(k+1:n,k+1:n) − ....
L(k+1:n,k) ∗A(k,k+1:n);
end
U = triu(A);
end
La funzione Matlab che esegue la fattorizza- zione LU con pivot ` e lu. Essa pu` o essere richiamata con l’istruzione:
[L,U,P]=lu(A)
25
Supponiamo che det(A) = 0 e U abbia l’ulti- mo elemento diagonale nullo.
Quindi l’ultima riga di U ` e un vettore nullo che si ottiene moltiplicando l’ultima riga di L −1 per le righe di A, cio` e:
l n,1 a T 1 + . . . + l n,n −1 a T n −1 + l n,n a T n = 0
con l n,i non tutti nulli e ci` o implica la lineare dipendenza delle righe di A.
L’annullarsi del determinante di una matri- ce quadrata ` e condizione necessaria e suffi- ciente affinch` e i vettori riga siano linearmente dipendenti.
Lo stesso discorso pu` o farsi con i vettori co-
Numero di operazioni
1) Calcolo dei coefficienti m i,j . Questi sono n − 1 per la prima colonna, n − 2 per la seconda, fino ad 1 per la penultima. In totale abbiamo:
n −1 X k=1
(n − k) = n(n − 1) 2
divisioni.
2) Calcolo degli a (k) i,j . Questi sono (n −1) 2 al primo passo (k = 2), (n − 2) 2 al secondo passo fino ad 1 all’ultimo passo (k = n − 1). In totale il numero degli a (k) i,j calcolati sono:
n −1 X k=1
(n − k) 2 = n(n − 1)(2n − 1)
6 ∼ n 3
3 .
Riassumendo:
moltiplicazioni e divisioni: ∼ n 3 /3 sottrazioni:
∼ n 3 /3.
27
Sia Ax = b e (A + δA)ˆ x = b + δb, ˆ x = x + δx Studiamo il comportamento di δx in funzione della perturbazione sui dati di input.
(A + δA)(x + δx) − Ax = b + δb − b δAx + Aδx + δAδx = δb
δx = A −1 ( −δAˆ x + δb) Passando alle norme
kδxk = kA −1 k(kδAkkˆ x k + kδbk) Dividendo per kˆ x k
kδxk
kˆ x k ≤ kA −1 kkAk kδAk
kAk + kδbk kAkkˆ x k
!
kAkkA −1 k `
La maggiorazione dipende da δx, ed ` e diffi- cile da interpretare. Possiamo derivare una maggiorazione teorica che non dipende da δx utilizzando il seguente lemma:
Lemma. Sia k·k una norma matriciale. Allora kBk < 1 implica che I − B ` e invertibile e
k(I − B) −1 k ≤ 1/(1 − kBk).
Dimostrazione. Sia λ autovalore di B con x autovettore, allora (I − B) ha l’autovalore 1 − λ con x autovettore:
(I − B)x = x − Bx = x − λx = (1 − λ)x
quindi (I − B) ` e non singolare, infatti gli au- tovalori sono tutti diversi da zero e quindi il determinante ` e diverso da zero, essendo uguale al prodotto degli autovalori.
I = (I −B)(I −B) −1 = (I −B) −1 −B(I −B) −1 I + B(I − B) −1 = (I − B) −1
k(I − B) −1 k ≤ kIk + kBkk(I − B) −1 k
k(I − B) −1 k − kBkk(I − B) −1 k ≤ 1
k(I − B) −1 k ≤ 1/(1 − kBk)
Troviamo una maggiorazione relativa per kδxk δAx + (A + δA)δx = δb
(A + δA)δx = δb − δAx
(I + A −1 δA)δx = A −1 (δb − δAx)
Se kA −1 kkδAk < 1 possiamo applicare il lem- ma e
δx = (I + A −1 δA) −1 A −1 (δb − δAx) passando alle norme
kδxk ≤ k(I+A −1 δA) −1 kkA −1 k(kδbk+kδAkkxk) kδxk ≤ kA −1 k
1 − kA −1 kkδAk kAk kδbk
kAk + kδAkkxk kAk
!
kδxk
kxk ≤ kA −1 kkA||
1 − kA −1 kkδAk
kδbk
kAkkxk + kδAk kAk
!
kbk = kAxk ≤ kAkkxk kδxk
kxk ≤ kA −1 kkAk 1 − kA −1 kkδAk
kδbk
kbk + kδAk kAk
!
Residuo : r = Aˆ x − b r = 0 se ˆ x = x
Aδx = Aˆ x − Ax = Aˆ x − b δx = A −1 r
kδxk ≤ kA −1 kkrk
30
Sistema lineare Ax=b : A =
"
1 1
0.99 1
#
, b =
"
2 1.99
#
soluzione x = [1, 1] T . La matrice inversa di A ` e
A −1 = 1 0.01
"
1 −1
−0.99 1
#
κ ∞ (A) = 400. Perturbiamo A sommando ad essa la seguente matrice
δA = 0.002
"
1 1
−1 −1
#
.
Essendo kA −1 k ∞ = 200 e kδAk ∞ = 0.004 si ha kA −1 k ∞ kδAk ∞ = 0.8, quindi il sistema perturbato
(A + δA)ˆ x = b
ha matrice dei coefficienti non singolare. La soluzione del sistema perturbato ` e
ˆ x = [0.2016..., 1.794...] T , per cui
kδxk ∞ / kxk ∞ = 0.3992.... La maggiorazione
kδxk kxk ≤ 4.
Ci sono sistemi che non sono mal condizio- nati ma per i quali il numero di condizione della matrice ` e grande. Esempio:
A =
u 0
0 1/u
.
con u sufficientemente piccolo, ha numero di condizione κ 1 (A) = (1/u) 2 . Se si moltiplica la seconda equazione per u 2 , cio` e se si scala la matrice, risulta
A 0 =
u 0
0 u
che ha numero di condizione pari ad 1.
Il condizionamento di una matrice pu` o essere modificato dallo scaling.
Si va alla ricerca di due matrici diagonali D 1 e D 2 in modo da minimizzare κ(D 1 AD 2 ).
32
Matrice di Hilbert
La matrice di Hilbert rappresenta un classico esempio di matrice mal condizionata reale, nel senso che ha origine da modelli reali.
Gli elementi della matrice di Hilbert sono dati dalla espressione seguente:
a (n) ij = 1
i + j − 1 , i, j = 1, ..., n
La tabella riporta i valori del numero di con- dizione di A, in norma 2 e in norma ∞, per diversi valori di n.
n κ 2 (A (n) ) κ ∞ (A (n) )
2 1.505 27
3 5.241 10 2 7.480 10 2
4 1.551 10 4 2.837 10 4
5 4.766 10 5 9.436 10 5
6 1.495 10 7 2.907 10 7
7 4.754 10 8 9.852 10 8
8 1.526 10 10 3.387 10 10
9 4.932 10 11 1.099 10 12
5 4.766 10 5 9.436 10 5
6 1.495 10 7 2.907 10 7
7 4.754 10 8 9.852 10 8
8 1.526 10 10 3.387 10 10
9 4.932 10 11 1.099 10 12
7 4.754 10 8 9.852 10 8
8 1.526 10 10 3.387 10 10
9 4.932 10 11 1.099 10 12
9 4.932 10 11 1.099 10 12
Si consideri la matrice A e il vettore b definiti da:
A =
"
1.2969 0.8648 0.2161 0.1441
#
, b =
"
0.8642 0.1440
#
. La soluzione esatta del sistema Ax = b ` e x = [2, −2] T .
Sia ˆ x = [0.9911, −0.4870] T , e sia r = Aˆ x − b, quindi r = [ −10 −8 , 10 −8 ] T .
Questo valore di r fa intendere che ˆ x ` e una buona approssimazione della soluzione esatta anche se in realt` a non lo ` e.
La matrice inversa di A ` e data da A −1 = −10 −8
"
0.8648 −0.1441
−1.2969 0.2161
#
per cui κ ∞ (A) = 3 10 8 , quindi A ` e mal con- dizionata.
34
Il residuo non ` e una buona indicazione di pre- cisione della soluzione di un sistema quando la matrice ` e mal condizionata. Infatti, vale la disuguaglianza
kδxk
kxk ≤ κ(A) krk kbk che si ottiene da
kδxk ≤ kA −1 kkrk
dividendo per kxk e sfruttando la disugua-
glianza kbk ≤ kAk · kxk.
Matrici diagonali dominanti
Sia A una matrice di ordine n diagonale do- minante per colonne. Allora i fattori di A ottenuti con il metodo di Gauss coincidono con quelli che si ottengono con il metodo di Gauss con pivot parziale.
Esempio: matrice diagonale dominante per righe
A =
3 1 1 4 8 2 2 2 5
I fattori di A ottenuti con il metodo di Gauss sono:
L =
1
4 3 1
2 3
1 5 1
, U =
3 1 1
20 3
2 21 3
5
, mentre i fattori ottenuti con il metodo di Gauss con pivot parziale sono:
L =
1
3 4 1
1 2
2 5 1
, U =
4 8 2
−5 − 2 3
21 5
.
36
Nel primo caso L non ` e diagonale predomi- nante, nel secondo caso ` e U a non essere diagonale predominante. Utilizzando il me- todo di Gauss con pivot totale si ottengono i seguenti fattori:
L =
1
1 8 1
1 4
1 6 1
, U =
8 2 4
9 2 1
7 3
.
In questo caso i fattori sono entrambi diago-
nali predominanti.
Errore nel metodo di Gauss
La propagazione pi` u o meno rapida degli er- rori di arrotondamento caratterizza la stabi- lit` a di un algoritmo. Per studiare la stabilit` a si utilizza generalmente l’analisi all’indietro (backward).
L’idea alla base di questa analisi consiste nel considerare la soluzione calcolata in aritmeti- ca floating point come la soluzione esatta di un problema perturbato e misurare la quan- tit` a di questa perturbazione. In questo caso si cerca di trovare la matrice δA tale che:
P (A + δA) = LU
ove L ed U sono le matrici calcolate effet- tivamente e P ` e la matrice di permutazione dovuta al pivoting. La norma di δA misurer` a la stabilit` a dell’algoritmo.
37
Il risultato finale stabilisce che:
kδAk ∞ ≤ 3g n kAk ∞ n(n − 1)
2 u (1)
u: l’unit` a di arrotondamento (precisione di macchina),
g n =
max i,j,k |a (k) i,j | max i.j |a i,j |
Questo termine, detto fattore di crescita, sti-
ma la crescita degli elementi delle successi-
ve matrici A (k) al crescere di k e caratteriz-
za la stabilit` a della fattorizzazione. Nei casi
peggiori questo termine pu` o crescere espo-
nenzialmente con n. Si considerano stabili
le fattorizzazioni in cui g n cresce al massi-
mo come n α , con α ≥ 0. Si pu` o dimostrare
che sono stabili le fattorizzazioni di matrici
a diagonale dominante e la fattorizzazione di
Naturalmente, nel caso in cui stiamo risol- vendo un sistema lineare, bisogna considerare anche gli errori che si commettono nella riso- luzione dei sistemi triangolari. Anche in que- sto caso le soluzioni ottenute al calcolatore possono essere considerate come le soluzioni esatte dei sistemi perturbati:
(L + δL)y = b (U + δU )x = y
Si pu` o dimostrare che, supponendo di usare il pivoting, si ha:
kδLk ∞ ≤ n(n + 1)
2 u
kδUk ∞ ≤ n(n + 1)
2 g n kAk ∞ u
La soluzione di un sistema lineare, tenendo conto degli errori dovuti all’uso dell’aritmeti- ca floating point e a possibili errori nel ter- mine noto, pu` o essere considerata come la soluzione esatta di un problema perturbato del tipo:
(A + E)(x + δx) = b + δb
in cui x + δx ` e la soluzione fornita dal calcola- tore ed x ` e la soluzione esatta che si sarebbe ottenuta in assenza di errori. Dovendo essere (A + E) = (L + δL)(U + δU ) + δA
si ha, trascurando il termine contenente δLδU ,
kEk ≤ kδAk + kL|kkδUk + kδLkkUk, e
kδxk
kxk ≤ k(A)
1 − kA −1 kkEk
kδbk
kbk + kEk kAk
!
.
Matrici simmetriche definite positive Si incontrano nelle applicazioni.
Sono le pi` u semplici da trattare.
La loro fattorizzazione non richiede il proce- dimento di pivoting:
si pu` o dimostrare che a (k) k,k > 0 .
Sia D la matrice diagonale formata dagli ele- menti pivotali, cio` e dagli elementi sulla dia- gonale principale della matrice U , si ha:
A = LU = LDD −1 U = LD ˆ U
U = D ˆ −1 U ` e una matrice triangolare supe- riore con elementi diagonali uguali ad 1.
39
Poich` e A ` e simmetrica si ha:
A T = ˆ U T DL T = A = LD ˆ U ,
con ˆ U T triangolare inferiore e L T triangolare superiore.
L’uguaglianza ` e verificata se ˆ U T = L quindi A = LDL T .
Poich` e abbiamo detto che gli elementi sulla diagonale di D sono positivi, si pu` o definire la matrice D 1/2 , con elementi le radici quadrate degli elementi di D. Si ha:
A = LD 1/2 D 1/2 L T . Ponendo S = LD 1/2 si ha:
A = SS T .
Questa fattorizzazione ` e detta fattorizzazione di Cholesky.
E pi` ` u semplice della fattorizzazione LU per-
ch` e ha come incognite solo gli elementi della
La fattorizzazione si pu` o ottenere diretta- mente uguagliando gli elementi di A e quelli di SS T .
Consideriamo la prima riga di A e la prima riga di SS T
a 1,1 = s 2 1,1
a 1,j = s 1,1 s j,1 per j = 2, . . . , n.
ed ` e quindi possibile ricavare:
s 1,1 = a 1/2 1,1
s j,1 = a 1,j /s 1,1 per j = 2, . . . , n.
In generale si avr` a:
a i,i = P i k=1 s 2 i,k per i = 1, . . . , n a i,j = P i k=1 s i,k s j,k per i = 1, . . . , n
j = i + 1, . . . , n.
Data la simmetria di A ` e sufficiente conside-
rare solo la parte triangolare superiore. Dalle
due precedenti relazioni si ricava:
s i,i = a i,i − P i k=1 −1 s 2 i,k 1/2 per i = 1, . . . , n
s j,i = a i,j − P i k=1 −1 s i,k s j,k /s i,i per
( i = 1, . . . , n
j = i + 1, . . . , n .
Le istruzioni Matlab per eseguire la fattoriz- zazione di Cholesky sono le seguenti:
for i=1:n
s(i,i) = a(i,i);
for k=1:i–1
s(i,i)=s(i,i) – s(i,k)^2;
end
s(i,i)=s(i,i)^(.5);
for j = i+1:n s(j,i)=a(i,j);
for k=1:i–1
s(j,i) = s(j,i) – s(i,k)*s(j,k);
end
s(j,i)=s(j,i)/s(i,i);
end
end
La funzione Matlab che calcola la fattorizza- zione di Cholesky di una matrice ` e chol. Se A ` e definita positiva allora dopo l’istruzione
R = chol(A);
la variabile R ` e la matrice triangolare supe-
riore della fattorizzazione di Cholesky.
Metodo dei minimi quadrati
Matrice A rettangolare con numero di righe maggiore del numero di colonne.
Sistemi sovradeterminati.
Sia A formata da una sola colonna a 1 ∈ IR m . Il sistema diventa:
a 1 x = b
con x scalare e b ∈ IR m .
la soluzione esiste se i vettori b ed a 1 sono
proporzionali, cio` e se hanno la stessa dire-
zione; la costante di proporzionalit` a x ` e la
soluzione.
E possibile trovare una soluzione approssima- ` ta del problema?
Geometricamente il problema si presenta nel seguente modo: dati un vettore b ed un altro vettore a 1 con direzione diverse, trovare un vettore proporzionale ad a 1 che approssimi meglio b .
- -
