Appunti di Calcolo numerico

B

termini noti

allora, la regola di Cramer, per il calcolo della soluzione di un sistema di n equazionni lineari

in n incognite, calcola n+1 determinanti di matrici di ordine n

- i

il calcolo della soluzione x attraverso il prodotto A^-1b con A^-1 ottenuto dalla formula

- (2) oppure attraverso la regola di Cramer non è efficiente, in quanto sono necessarie molte

operazioni per calcolare il determinante.

-

L I

si vuole studiare il numero di operazioni necessarie per calcolare il determinante di una matrice

quadrata di ordine n. dz 3

=

·

(Il calcolo del determinante di una matrice 2 x 2 richiede il calcolo di 3 operazioni aritmetiche).

Indicando con d il numero di operazioni necessarie per il calcolo del determinante di una

n

matrice di ordine n, si ha d =3.

2 il calcolo del determinante di una matrice A

di ordine n con la regola di Laplace richiede

Vale la moltiplicazione di ciascuno degli n

cou elementi della prima riga di A per il

determinante delle sottomatrici di ordine

n-1 e la somma degli n numeri risultanti

poiché , allora per n che tende all'infinito si ha

D

=

dunque, per valori grandi di n possiamo scrivere

Soluzione con calcolo della matrice inversa: matrice 2 x 2, matrice diagonale e

matrice ortogonale

analizziamo 3 casi particolari in cui è efficiente calcolare il sistema mediante il prodotto tra la

matrice inversa e il temirne noto

aiananda

a

i)

(â

A 5A

IAIF=

X 2 =

caron = se = a

, abil

(a

(i) amanFanaze

A

= (Ei)

= = =

= (ai 8

.

A diagonale A= =Aénonmingdabe

A canasto i

supponiamo -> =e .

,

-elemento diegence an

0

dax be

S i 1

per M

=

=peri=e ....,

Matlab

distbz =x in

...n

: :

S bi/di

X :

↳

danku= bu B

equivale A

E

a =

per la risoluziome di un sistema diagonale si effettuano n operazioni di divisione.

Si osserva che la matrice inversa della matrice diagonale A è ancora una matrice diagonale

(E)- (Bere I

- e

divisione

di

operazioni

n

·

la matrice A è ortogonale

- due vettori si dicono ortogonali quando il loro prodotto scalare è nullo

n vettori non nulli, q , q , …, q si dicono ortogonali a due a due se

1 2 n -

n vettori non nulli, q , q , …, q si dicono ortonormali a due a due se

1 2 n

n vettori ortogonali (o ortonormali) a due a due sono linearmente indipendenti

una matrice non singolare Q si dice ortogonale se

⑧ una matrice Q è ortogonale se e solo se ha le colonne ortonormali a due a due

· righe

di

mostrazione

- definita la matrice ortogonale Q per colonne, , la matrice trasposta di Q ha

espressione 1 q

I

a =

= =

=

S Siccome notonozel

.....

I= ortoverwali

an an

Q =

e re .....

> --

sia da risolvere il sistema lineare di n equaizoni in n incognite , Ax=b, con A matrice

ortogonale di ordine n At

A =

-

b

A Matlab

E moltiplicazion

in

-i

in

= eseguace

=> u somme

e

moltiplication

~ somme e

·

Metodo di sostituzione per sistemi lineari triangolari

Metodo di sosituzione in avanti b

Ax

sia da risolvere il sistema lineare in n equazioni lineari in n incognite =

con A matrice dei coefficienti triangolare inferiore

-

singolare

m-sA

to i= 1

ai

con n on

....,

utilizziamo il metodo di sostituzione in avanti

(bz-are)/azz

ban (bz-azx)/azz azxz)/ase

(b3 azx

- xz

xz

- = - = = -

- -

= -

ann-eXne)/aum

(br-ansXs-anzXz-antz-

Xn=

-> -

...

arrexiel/aii=(bi-zaists)/air

xi=(bi-ainxi-aizx

quind -

.... Easts

Matlab fine

Salle

in vale aimxn=

ainketaintzt ...

Metodo di sostituzione all'indietro

-

si considera un sistema lineare Ax=b con A triangolare superiore

*

A mingelare

i

aiiFo 1 non

con m

= =

, ....,

utilizziamo il metodo di sostituzione all'indietro

braun-1Xu=(bue-amenxn)/amen

Xn = (bi-naxyl/an

quindi xi=(biacitixite-anxitzt tainfallaci ise

- m

... ..

Matlab

in

a)

- per determinare la soluzione di un sistema normale con matrice dei coefficienti triangolare non

- singolare, occorre eseguire moltiplicazioni e divisioni

In

per valutare l'errore che si commette quando si risolve un problema con un metodo di calcolo

mediante calcolatore, si può adottare la tecnica dell'analisi dell'errore all'indietro

si vuole valutare se la soluzione calcolata è soluzione esatta di un problema di poco perturbato

--

dato il sistema triangolare Ax=b, la soluzione x' calcolata con il metodo di

--

sostituzione è soluzione esatta del sistema (A+ΔA)x=b dove la matrice ΔA è

triangolare come A e vale si nota che viene calcolata una soluzione

vicina alla soluzione esatta, e quindi si dice

I che il metodo è numericamente stabile

x è la soluzione esatta di Ax=b e x' (soluzione calcolata di Ax=b) è la soluzione esatta di

....

. . .

--

(A+ΔΑ)x=b.

Se ΔΑ è piccolo, ovvero la sua norma è piccola, possiamo vedere (A+ΔΑ)x=b come un problema

--

ottenuto perturbando di poco i dati del problema Ax=b. La matrice ΔA è la perturbazione del

dato A. --

Se il problema Ax=b è ben condizionato, allora ΔA piccolo implica che la perturbazione sui

risultati x-x' sia piccola, ovvero x' è una buona approssimazione di x.

- - - -

Analisi dell'errore del metodo di sostituzione per sistemi lineari triangolari

dove x è un numero reale e x' è

x

x il corrispondente numero di 2)

2 x x(1

= - = + .

macchina che approssima x 121-eps

per il teorema della precisione di macchina dove eps indica la precisione di macchina

-

analogamente, posto E = Inkseps

xx

y con

x

= - n

CAPITOLO 9

METODO DI ELIMINAZIONE DI GAUSS

E FATTORIZZAZIONE LR

per studiare sitemi lineari e matrici

Fattorizzazione LR di una matrice inverse senza passare dal determinante

si studia la possibilità di fattorizzare una matrice quadrata A di ordine n nel prodotto di

una matrice n x n triangolare inferiore L per una matrice n x n triangolare superiore R.

L'esistenza di una tale fattorizzazione renderebbe facile la determinazione della soluzione

del sistema normale non singolare di n equazioni in n incognite

infatti, se si potesse fattorizzare la matrice A nel prodotto LR, si otterrebbe È

un metodo per realizzare la fattorizzazione di una matrice quadrata A di ordine n nel prodotto di

due matrici triangolari L e R si basa sull'utilizzo delle matrici elementari di Gauss

questo metodo si chiama metodo di fattorizzzione LR o

metodo di eleminazione di Gausso metodo di Gauss

passi

1

· n -

si effettua una triangolarizzazione della matrice A: si calcolano sistemi lineari equivalenti in

cui le matrici dei coefficienti hanno via via sempre più colonne con elementi nulli sotto la

diagonale prinicpale

1 passo A2

si definisce la prima matrice elementare di Gauss che ha

/GA

Le =

ka nulli gli elementi della prima colonna dalla seconda alla n-esima riga

si

supponendo 0 col

ane -=== i

I

A= ?,

LA di elementi i I

e M

a = ..... "

!

elementi hamio

delle matrice d'ordine

gli sotto m-n espressione

2

a m

1

=

, , ....,

2 passo Al

LILzA

si definisce la seconda matrice elementare di Gauss che ha nulli gli elementi della

=

seconda colonna dalla terza alla n-esima riga oltre che gli elementi della prima colonna dalla seconda

alla n-esima riga.

a?

supponendo o coll

termini te

il le

tal rige-colonna

definiti predetto Le

che i-esime ziged

i

i sono per

wiz 3 m

= ....,

, A

la di

i colonne uguale

seconde sia

3 e

= m zero

a

. .,

.

, , .

Al= LA s

a

elementi

di i

I è

=1 m

,

, ....,

=L2A (2)

n dielementials i ....

1

=

, "

!

gli ordine

elementi a dalle sottomatzice

=3 di m-2

m

, .....

hanno espressione

pausi

2

n - Al

la la

ha

matzice

abbianco forma

led ultima

m-n-esimo passo la

definisce matrice elementare di

supponendo " diadine

. Fo si Gauss -1

a n

,

n con

mmm il prodotto riga-colonna tra la n-esima riga di e la n-1-esima colonna

Lu -r

e)

A(m

di fornisce il valore zero.

- A(n)

La-eAlm-e

Il prodotto fornisce una matrice triangolare superiore

fattorizzazione

la possibile

é se i perii to

com =

le Li I'm

l'

le

matzie L matrici

poiché L esistone

singolari inverse

vou -ne save

sono :

.....

me

, .... .

,

, A *

A

.. -1) LR

(2) (Lili

A (m inf

matzici t

dim

prodotto

=> con

= -s e

=

= ... .

1

- ⑲ triangolare inferiors

matrica

quindi

(n)

Le

LIL vale

= R A

pouendo e :

=

... s sono

termini a detti pivat

i permi

a

an o

....

,

la matrice A

fattorizzare

esempio m ↳

= , di

produtto LpeR

nel la

al del metado il pivat matzica farma

he

170

primo am

é

passo e

= s

A

forince

produtto LA

il .

!

metodo

al pivot

recondo il definiamo

dal Le

270

a e :

é

passo =

LA"fornisce Al

produtto

il 13

ass=-3 costrince

si

testo ultimo Fo

pivot

il

al e

passo e

e Al

ottiene cioè

vi ,

la L

'

matrice = : 1)

(2) (n

la fattorizzazione LR della matrice A è dunque possibile se i perni sono

-

Azz Ann-

arm .....

,

diversi da zero anto

!..... 1)

(n

se i perni sono diversi da zero ed A è non singolare allora

-

ama Amen-s

⑳ -

!.... (n)

viceversa, se i perni sono diversi da zero allora la matrice A è

ama aum

⑧ non singolare

dimostrazione

i perni sono gli elementi diagonali di R. Essendo R una matrice triangolare, il

a (n)

am ann

....

,

suo determinante è dato dal prodotto degli elementi diagonali. Analogamente, la matrice

triangoare L di elementi diagonali uguali a 1, ha determinante uguale a 1.