Metodi diretti

(1)

METODI NUMERICI (A.A. 2007-2008)

Prof. F.Pitolli

Appunti delle lezioni sui sistemi lineari:

metodi diretti; condizionamento

Metodi diretti

per la soluzione di sistemi lineari

Metodi diretti

Sono basati sulla trasformazione del sistema di partenza in uno equivalente che abbia una struttura particolarmente semplice per cui ` e facile calcolarne la soluzione.

La soluzione numerica viene calcolata in un numero ﬁnito di passi e, se non vi fossero errori di arrotondamento nei dati o durante i calcoli, la soluzione numerica sarebbe esatta.

Data l’occupazione di memoria (RAM) richiesta nei pas- saggi dell’algoritmo, vengono utilizzati quando la matrice dei coeﬃcienti ha dimensione non ”troppo” elevata .

1

Costo computazionale di un algoritmo

Prima di implementare un algoritmo bisogna stimare il suocosto com- putazionale, cio`e il numero di operazioni pesanti (moltiplicazioni o divisioni) necessarie per calcolare numericamente la soluzione.

Costo computazionale:

Cc≈ numero di moltiplicazioni o divisioni

Metodo di Cramer

Dall’Algebrasappiamo che la soluzioneesatta di un sistema lineare si pu`o ottenere con ilmetodo di Cramer.

Se A `e regolare, X = A⁻¹B =⇒ xi= Di

detA, i = 1, 2, ..., n, dove Di `e il determinante della matrice ottenuta da A sostituendo alla colonna i-esima il vettore B.

Costo computazionale del metodo di Cramer

x_i= D_i

detA i = 1, 2, ..., n

• n + 1 determinanti ( D

_i

, i = 1, . . . , n e det A )

• n! ↓ prodotti per ciascun determinante

• n − 1 ↓ moltiplicazioni per ciascun prodotto

+ n divisioni (trascurabili) Costo computazionale:

C

c

= (n + 1)n!(n − 1) + n (n + 1)n!(n − 1)

n = 15→ Cc 3 · 10¹⁴moltiplicazioni→ 3 giorni n = 20→ Cc 3 · 10²¹moltiplicazioni→ 3 · 10⁵ anni

⎫⎬

⎭Inutilizzabile!!

(supponendo 10⁻⁹secondi per operazione)

(2)

Metodo di eliminazione di Gauss

Ilmetodo di eliminazione di Gausstrasforma, inn−1passi, il sistema lineare

AX = B X, B ∈ IRⁿ A ∈ IR^n×n

con matrice dei coeﬃcientiA ”piena”, nel sistema equivalente U X =B X,B ∈ IR ⁿ U ∈ IR^n×n

con matrice dei coeﬃcientiU triangolare superiore.

Il metodo utilizza le seguenti operazioni ”lecite”:

•scambio di 2 equazioni

•somma su un’equazione di un’altra moltiplicata per una costante Costo computazionale: Ccn³

3 = O(n³)

4

Soluzione di sistemi triangolari

Sistemi triangolari superiori

⎧⎪

⎪⎪

n

⇓

UX = B →

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

x

n

= b

n

u

nn

x

_k

=

⎛

⎜⎝

b

_k

−

ⁿ

i=k+1

u

_ki

x

_i

⎞

⎟⎠

1 u

_kk

, k = n − 1, n − 2, ..., 2, 1

(Algoritmo di sostituzione all’indietro)

5

Sistemi triangolari inferiori

⎧⎪

⎪⎪

⎪⎨

⎪⎪

⎩

l

11

x

1

= b

1

· · · · · · · · · · · · ·

l

_k1

x

1

+ l

_k2

x

2

+ · · · + l

_kk

x

_k

= b

_k

· · · · · · · · · · · · ·

l

_n

⇓

LX = B →

⎧⎪

⎪⎪

⎪⎨

⎪⎪

⎩

x

1

= b

1

l

11

x

_k

=

⎛

⎝

b

_k

−

^k−1

i=1

l

_ki

x

_i

⎞

⎠

1 l

_kk

k = 1, 2, . . . , n

(Algoritmo di sostituzione in avanti)

Costo computazionale dell’algoritmo di sostituzione

Ad ogni passo ci sono

• n − k moltiplicazioni

• 1 divisione

C

c

=

ⁿ

k=1

(n − k + 1) = n

²

2 + n

2 n

²

2 = O(n

²

)

Nota: Se le matrici U e L sono regolari, sicuramente u

_kk

e l

_kk

sono = 0 .

(3)

Fattorizzazione LU

Ilmetodo di eliminazione di Gauss pu`o essere interpretato come la fattorizzazionedella matrice di partenzaAnel prodotto di due matrici triangolari.

Teorema. Se la matrice A ∈ IR^n×n ha determinanti principali di testa tali che

detA_k = 0, k = 1, 2, · · · , n, allora

A = LU

dove L ∈ IR^n×n `e una matrice triangolare inferiore con ele- menti diagonali pari a 1 eU ∈ IR^n×n`e unamatrice triangolare superiore.

8

Struttura delle matrici L e U

A = LU =

⎡

⎢⎢

⎣

1 0 0 0 · · · 0

m21 1 0 0 · · · 0 m31 m32 1 0 · · · 0 ... ... ... ... ... ...

m_n1 m_n2 m_n3 · · · 1

⎤

⎥⎥

⎦

⎡

⎢⎢

⎢⎣

a⁽¹⁾₁₁ a⁽¹⁾₁₂ a⁽¹⁾₁₃ · · · a⁽¹⁾_1n 0 a⁽²⁾₂₂ a⁽²⁾₂₃ · · · a⁽²⁾_2n ... 0 a⁽³⁾₃₃ ... a⁽³⁾_3n ... ... ... ... ...

0 0 0 ... a⁽ⁿ⁾nn

⎤

⎥⎥

⎥⎦

Nota 1: Se A non soddisfa le ipotesi detA_k = 0, ma è comunque regolare, tramite scambi di righepuò essere riportata ad una matrice che soddisfa le ipotesi e che quindi può essere fattorizzata.

Nota 2: il costo computazionaledella fattorizzazione `e lo stesso di quello dell’eliminazione di Gauss Cc n³

3 = O(n³).

9

Applicazioni della fattorizzazione

Soluzione di un sistema lineare

Consideriamo ilsistema lineareAX = B e supponiamo che la matrice dei coeﬃcienti A possa essere fattorizzata.

AX = B ^A=LU→ LU X = B⇒

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

LY = B sistema triang. inf.

(algoritmo di sost. in avanti) U X = Y sistema triang. sup.

(algoritmo di sost. all’indietro)

Una voltafattorizzataA, la soluzione del sistema si ottiene risolvendo i due sistemi trangolari con costo computazionale ≈ 2n²

2 = O(n²) .

Soluzione di pi`u sistemi lineari

Se dobbiamo risolvere pi`u sistemi lineari

AXi= Bi i = 1, 2, . . . , r

aventi la stessa matrice A e diversi termini noti, si fattorizza una volta per tutte la matrice A = LU e si risolvono, per ogni vettoreBi, i due sistemi triangolari

⎧⎪

⎨

⎪⎩

LY_i= B_i i = 1, 2, . . . , r U Xi= Yi

per la soluzione dei quali il costo computazionale `e ”solo”n².

(4)

Calcolo del determinante di A

detA = det(L U) = detL detU =

⎛

⎝ⁿ k=1

l_kk

⎞

⎠

⎛

⎝ⁿ k=1

u_kk

⎞

⎠= a⁽¹⁾₁₁a⁽²⁾₂₂ · · · a⁽ⁿ⁾nn

↓

Teorema di Binet = 1

Se durante la fattorizzazione sono stati fatti s scambi di righe, allora

detA = (−1)^sa⁽¹⁾₁₁a⁽²⁾₂₂ · · · a⁽ⁿ⁾nn

12

Calcolo dell’inversa di A

La matrice inversa A⁻¹ di una matrice regolare A `e la matrice tale che

A A⁻¹= I I : matrice identit`a

I :=

⎡

⎢⎢

⎢⎣

1 0 · · · 0 0 1 · · · 0

· · · · 0 0 · · · 1

⎤

⎥⎥

⎥⎦= [E1E2 · · · En] E_i= [0, 0, · · · , 1

i

, 0, · · · , 0]^T

↓

Vettori dellabase canonica

A A⁻¹= I ⇒ A X_i= E_i i = 1, 2, · · · , n ⇒ A⁻¹= [X1 X2· · · Xn] Una volta nota la fattorizzazione di A, basta risolvere glin sistemi

L Yi= E_i, U Xi= Y_i, i = 1, · · · , n

Costo computazionale: Cc n³

3 + n · n²=4 3n³

13

Calcolo del rango di A

•Se l’algoritmo di eliminazione applicato alla matrice quadrata A ∈ IR^n×n termina regolarmente dopo n − 1 passi ⇒ la matriceA ha rango massimo pari a n (matrice regolare).

•Se l’algoritmo di eliminazione applicato alla matrice quadrata A ∈ IR^n×n non pu`o proseguire dopo q passi perch´e a^(k)_rk = 0, r = k, . . . , n ⇒ la matrice A ha rango pari a q ≤ n (matrice singolare).

•L’algoritmo di eliminazione applicato alla matrice rettangolare A ∈ IR^m×n termina necessariamente dopo q ≤ m passi ⇒ la matrice A ha rango pari a q.

Nota: le operazioni ”lecite” conservano il rango.

Matrici tridiagonali

Nel caso in cui la matrice dei coefficienti Aètridiagonale la fattoriz- zazione LU è molto semplice in quanto le matrici L e U hanno una struttura semplice.

A =

⎡

⎢⎢

⎣

d1 s1 0 · · · 0 a2 d2 s2 · · · 0

· · · ... ... . . . · · · 0 0 · · · dn−1 sn−1

0 0 · · · an dn

⎤

⎥⎥

⎦

=

⎡

⎢⎢

⎣

1 0 0 · · · 0 α2 1 0 · · · 0 0 α3 1 · · · 0 ... ... ... ... ...

0 0 · · · αn 1

⎤

⎥⎥

⎦

⎡

⎢⎢

⎣

u1 v1 0 · · · 0 0 u2 v2 · · · 0 ... ... ... . . . ...

0 0 · · · u_n−1 v_n−1 0 0 · · · 0 un

⎤

⎥⎥

⎦

= LU

(5)

Algoritmo di Thomas

⎧⎪

⎪⎪

⎪⎨

⎪⎪

⎩

u1 = d1

vi= si i = 1, 2, . . . , n − 1 α_i= a_i/u_i−1 i = 2, 3, . . . , n u_i= d_i− α_iv_i−1 i = 2, 3, . . . , n Costo computazionale: Cc=2n − 2

Soluzione del sistema lineareAX = B

y1= b1 y_i= b_i− α_iy_i−1 i = 2, 3, . . . , n xn= yn/un x_i= (y_i− vix_i+1)/u_i i = n − 1, . . . , 1 Costo computazionale: Cc=3n − 2

16

Condizionamento di un sistema lineare

Ilcondizionamento del problema della soluzione di un sistema lineare

`

e indipendente dal metodo numerico scelto per risolverlo.

Il condizionamento ”misura” quanto una perturbazione sui dati di input (matrice dei coeﬃcienti e termine noto) inﬂuenzi i risultati (la soluzione).

Un sistema lineare si dice ben condizionato se a piccole variazioni sui dati corrispondono piccole variazioni sui risultati.

Viceversa, se a piccolevariazioni sui dati corrispondono grandi variazioni sui risultati, si dice che il sistema `emal condizionato.

Quando si approssima la soluzione di un sistema linearemal condizio- nato bisogna ridurre il pi`u possibile gli errori di arrotondamento.

17

Errore sul termine noto

Supponiamo che il termine noto B sia aﬀetto da un errore δB. A X = B^δB→A(X +δX) = B +δB

Per sottrazione si ricava

AδX=δB → δX= A⁻¹δB

Per ”misurare” la perturbazioneδX indotta suX si ricorre alla norma.

||δX||=||A⁻¹δB|| ≤ ||A⁻¹|| ·||δB||

||B||=||AX|| ≤ ||A|| ·||X||

Dividendo termine a termine si trova una maggiorazione per l’errore relativo ||δX||/||X||.

||δX||

||X|| ≤ ||A|| · ||A ⁻¹||||δB||

||B|| = K(A)||δB||

||B||

Numero di condizionamento

K(A):=||A|| · ||A⁻¹||: numero di condizionamento della matrice A

||δX||

||X|| ≤K(A)||δB||

||B||

Rappresenta ilcoeﬃciente di ampliﬁ- cazione dell’errore relativo sui dati

Si pu`o dimostrare che 1≤K(A)≤ +∞

Condizionamentoottimo Condizionamentopeggiore (matrici ortogonali) (matrici singolari)

Esempi di matrici malcondizionate: matrici di Hilbert

H =

⎛

⎜⎜

⎜⎝

1 1/2 1/3 · · · 1/n

1/2 1/3 1/4 · · · 1/(n + 1) 1/3 1/4 1/5 · · · 1/(n + 2)

· · · · · · · · · · · · · · · 1/n 1/(n + 1) 1/(n + 2) · · · 1/(2n − 1)

⎞

⎟⎟

⎟⎠

(6)

Errore sulla matrice dei coeﬃcienti

Se anche la matriceA `e aﬀetta da un errore δA si ha

||δX||

||X|| ≤ K(A) 1− K(A)||δA||

||A||

||δB||

||B|| +||δA||

||A||

↓

Coeﬃciente di ampliﬁcazione Condizionamento in norma 2

SeA`e (simmetrica)deﬁnita positivasi ha K2(A) = ||A||2||A⁻¹||2=λmax

λ_min

Infatti||A||2=

ρ(A^TA) =

ρ(A²) = ρ(A) = λmax

||A⁻¹||2= ρ(A⁻¹) = max_i 1 λi

= 1

λmin

20

Esempio

Una persona compie una passaggiata casuale, facendo un passo a sini- stra o a destra a caso lungo una retta. Quando raggiunge un estremo, si ferma. Se x_k, k = 0, 1, . . . , N, rappresenta la probabilit`a di raggiun- gere l’estremo sinistro partendo dalla posizionek conx0= 1 ex_N = 0, si ottiene il sistema lineare

⎧⎪

⎨

⎪⎩

2x1 − x2 = 1

−x_i−1 + 2x_i − x_i+1 = 0 i = 2, . . . , N − 1

− x_N−1 + 2x_N = 0

Utilizzare il metodo di Thomas per approssimare la soluzione del sistema lineare con N = 100, 1000, 10000.

Riferimenti bibliograﬁci

L. Gori, Calcolo Numerico: §§4.1, 4.2, 4.3, 4.8, 4.10 (solo enunciati dei teoremi), 4.12

L. Gori, M.L. Lo Cascio, Esercizi di Calcolo Numerico: 2.1, 2.2, 2.3, 2.4, 7.27 (solo domanda 2; si suggerisce di utilizzare l’algoritmo di Thomas per risolvere il sistema lineare AX = B con B = (1, 1, 1, 1)^T), 7.52

21