Appunti di calcolo numerico

I

pT 1

-

p

· =

la matrice di permutazione P è una matrice ortogonale

Metodo di eliminazione di Gauss con scambio di righe e perni massimo (x)

la fattorizzazione di una matrice A nel prodotto LR è possibile solo se tutti i perni a ,

kk

k=1, …, n-1, sono diversi da zero. Il metodo di eliminazione di Gauss con scambio di righe e

perno massimo è detto metodo di Gauss con pivoting e permette di ottenere sempre la

fattorizzazione LR se la matrice A è non singolare e, soprattutto, come visto nell'esempio,

permette di ottenere una soluzione numericamente più accurata

esempio ha

sia si

applichiamo il metodo di Gauss con scambio di righe e perno massimo

primo K

passo 1

=

,

il candidato pivot è l'elemento a =1=0. Ricerchiamo invece, l'elemento di modulo

11

massimo tra tutti gli elementi della prima colonna. Abbiamo che

allora il perno è l'elemento a . Moltiplichiamo quindi la matrice A ed il vettore b per

31

una matrice elementare di permutazione P (così facendo scambiamo la prima con la

1

terza riga della matrice A e del termine noto b) la

costruisce

si

matzice

* come

,

B secondo K 2

passo =

,

il candidato pivot è l'elemento a =3/4=0. Ricerchiamo l'elemento di modulo massimo

22

tra gli elementi della seconda colonna di A a partire dall'elemento della seconda riga in

giù. Abbiamo che

* *

*

B

terto ultime K 3

passo

e =

, s

a B3= ? ma la

pivet

candidato 10 a =

: , s

* -

-

applicando ora il metodo di sostituzione all'indietro per risolvere il sistema Rx=y si ottiene il

T

vettore soluzione x=(1, 1, 1, 1)

anche per il metodo di Gauss con scambio di righe e perno massimo si può scrivere un risultato

di fattorizzazione tra due matrici L e R

sia A una matrice n x n non singolare, Allora esiste una matrice di permutazione P, n x n per

cui

dove L è matrice triangolare inferiore con elementi sulla diagonale tutti uguali a 1 ed R matrice

triangolare inferiore superiore con elementi sulla diagonale tutti diversi da zero

pseudo-codifica per Matlab

la scrittura del metodo di Gauss con pivoting è analoga a quella del metodo di Gauss con

l'aggiunta del calcolo del pivot ad ogni passo k (ricerca del massimo in modulo di un array di

n-k+1 elementi a per i=k, …, n) e dello scambio delle righe p e k dell'array contenente A e di

(k)

ik (k)

quello contenente il vettore dei termini noti b dove p è la componente relativa all'elemento di

modulo massimo al passo k. Questo scambio avviene soltanto se p è diversa da k

e la risoluzione di Rx=y si scrive

Analisi dell'errore per il metodo di Gauss

studiamo l'errore che si commette quando si risolve un sistema lineare Ax=b mediante il metodo

di eliminazione di Gauss quando gli elementi dei dati A e b del sistema lineare sono numeri

finiti e le operazioni del metodo sono eseguite con l'aritmetica dei numeri finiti.

Si utilizza la tecnica dell'analisi dell'errore all'indietro di Wilkinston.

L'analisi dell'errore all'indietro valuta se la fattorizzazione calcolata di una matrice A è la

fattorizzazione esatta di una matrice perturbata A+E e fornisce una stima della perturbazione E.

Chiamiamo L' e R' i fattori L ed R calcolati facendo uso dell'aritmetica dei numeri finiti.

/

esemipe ⑧

consideriamo il problema di fattorizzare la matrice A

supponendo di risolvere il problema con un calcolatore che usa la base 10 e 3 cifre decimali per

rappresentare la mantissa,

abbiamo che L' e R' con il metodo di Gauss sono:

mentre con il metodo di Gauss con pivoting sono:

nel primo caso si osserva che L'R', fattorizzazione calcolata di A, è la fattorizzazione

esatta di A+E; com *

nel secondo caso si ha che L'R', fattorizzazione calcolata di PA è la

coll

fattorizzazione esatta di PA+E com ⑤

allora notiamo che, nel primo caso, la fattorizzazione L'R' risulta la fattorizzazione

esatta di una matrice molto perturbata rispetto ad A, mentre nell secondo caso L'R' è la

fattorizzazione di una matrice poco perturbata rispetto a PA quindi stabile

numericamente

si ricorda che un numero reale x viene approssimato dal numero di macchina x' con

con eps precisione di macchina

l'analisi dell'errore all'indietro cerca una matrice E tale che L'R' (fattorizzazione calcolata di A o

di PA) sia la fattorizzazione esatta di A+E o di PA+E, cioè

si scrive dove δL e δR hanno struttura come L e R rispettivamente e

e

hanno elementi di grandezza O(eps) (grandezza come la precisione di macchina).

Si ha che

dunque E

(R ( SR)

54)(R S

s

+

=

= + .

+ +

-

grandezza degli elementi delle tre matrici che compongono E:

gli elementi di δL δR hanno grandezza come la precisione di macchina al quadrato, ovvero

⑧ 8

O(eps )

2

la grandezza degli elementi di L δR dipende dalla grandezza degli elementi di L in quanto

⑳ ⑳

quelli di δR sono O(eps) elementi di grandezza della precisione

di macchina, infatti molto piccoli

*

condizione

min

I stabilità

di

1 ~ (L

sugli elementi di waswa

·

la grandezza degli elementi di δL R dipende dalla grandezza degli elementi di R in quanto

⑧ .

8

quelli di δL sono O(eps) (n)

Gli elementi di R (R=A ) sono:

⑳

S E

(n)

ais la las /

i .

i

wis J

1

per

ais m-e per e

M

=

= = i

mm 5 = i

i e

=

; .,

,

...., .

. ...,

⑧

(n) i -sel(min i

peri=2

=0 =e 1 2 1

j m

per =

mi I

=

mi =B ...,

....,

... ...,

1)

1) (n

(n

(m) - - Ian

lan1+Immu h

clawn"I+la

cul/

lann I

an

ann-Mmm-1

amm :

= n

- -1

e quindi si ha 1)

(n

applicando lo stesso procedimento agli elementi di A otteniamo

-

1)

(n - 1)

(n

questa relazione vale per ogni elemento a della matrice A e dunque anche per l'elemento

ij -

il cui valore è massimo in modulo; possiamo scrivere (3)

Applicando lo stesso procedimento per gli elementi di A , A , …, A e A con la

(2)

(n 3)

2) (m -

-

condizione di stabilità verificata, possiamo scrivere per gli elementi di R la seguente

relazione (j=1, …, n; i=1, …, n) B

(n)

vale per ogni elemento a per i=1, …, n e j=1, …, n, e dunque vale anche per l'elemento di

ij

modulo massimo, cioè

gli elementi di R sono maggiorati da un fattore ρ che può essere grande fino a 2 per il

1

n -

massimo degli elementi di A

si ha allora che L'R' fattorizzazione calcolata di A (in cui vale la cond. di stabilità) o di PA, è la

fattorizzazione esatta di A+E o di PA+E con dove 22-1

f

/ il

se ρ è molto grande (prossimo o uguale a 2 ), allora la

1

n -

fattorizzazione L'R' calcolata di A o di Pa è la fattorizzazione

"esatta" di A+E o di PA+E con E grande, cioè è molto

11 Ila

diversa dalla fattorizzazione (esatta di A o di PA) LR -

i

quando si applica il metodo di eliminazione di Gauss con scambio di righe e perno massimo per

*

la risoluzione di un sistema lineare in n equazioni e n incognite

tenendo conto dell'analisi dell'errore all'indietro per i sistemi lineari triangolari e per la

fattorizzazione LR, si ha che la soluzione calcolata x' è soluzione esatta di un sistema lineare

perturbato dove 1

confzn -

X il

il metodo di eliminazione di Gauss con scambio di righe e

perno massimo è tra i metodi più efficienti per realizzare la

fattorizzazione LR di una matrice non singolare di ordine n,

e quindi per la risoluzione di un sistema lineare Ax=b I

i CAPITOLO 11

FATTORIZZAZIONE DI MATRICI

PARTICOLARI NEL PRODOTTO DI DUE

MATRICI TRIANGOLARI

matrice densa se ha pochi elementi pari a 0

matrice sparsa se ha molti elementi pari a 0

si considera il metodo di Gauss per la risoluzione

Risoluzione di sistemi tridiagonali di sistemi algebrici lineari tridiagonali

partendo da una matrice tridiagonale colonna

delle

indice dix

↑ colonne

indice

X &

"

altre -

am ar dove .

*

aik a ic

. si raggruppano i numeri ≠0 in a si perdono

informazioni sulle colonne, infatti si aggiunge

- una colonna ia: indice della colonna di x

3) +x(ia(iis) i

in(i

y(i) a)i

y(i) 2

+ 1 1

aijxs

y mej

con = =

=

y ·

+

= ...., .

.

,

,

, T

si considera il sistema di n equazioni algebriche lineari nelle n incognite x=(x , …, x )

1 n

(1) ⑧

dove la matrice dei coefficienti A ha una forma tridiagonale ovvero è data da

termini

dei

il vettore noti

e

sepradiagonale sottodiagonale

diagonale principale :

:

supponiamo che per gli elementi della matrice A valgano le seguenti ipotesi di diagonale

dominanza

per colonne: per righe:

per risolvere il sistema lineare applichiamo il metodo di eliminazione di Gauss (che consiste in

un procedimento di sostituzione in avanti e successivamente di sostituzione all'indietro)

Supposto b ≠0, si esplicita l'incognita x dalla prima equazione e la si sostituisce nella seconda

1 1 1

equazione,

definiti p e y , la seconda equazione si riscrive

I 2 2

supposto p ≠0, si esplicita l'incognita x

2 2

e la si sostituisce nella terza equazione

definiti p e y , la terza equazione si riscrive

3 3

3 procedendo con le sostituzioni in avanti, dopo aver sostituito il valore esplicitato di x nella

n-2

1

M - (n-1)-esima equazione, quest'ultima si scrive

supposto p ≠0, esplicitando x dalla (n-1)-esima equazione si ha

n-1 n-1

e sostituendo nella n-esima equazione si ottiene

⑰

dunque, dopo il procedimento di sostituzione in avanti, il sistema si è riscritto come un sistema

lineare bidiagonale superiore yide

dave pibe e

se p ≠0, dall'ultima equazione is determina x

n n

M successivamente si effettua la sostituzione all'indietro 1)

/ queste formule mostrano che è possibile determinare la

soluzione del sistema tridiagonale se ogni p ≠0, i=1, …, n

i "

M

E

si dimostra che se valgono le condizioni di diagonale dominanza per colonne allora vale che

ogni p , i=1, …, n, è non nullo

i

dimostrazione esistel

(an mon