Appunti di calcolo numerico

X- XT X--

e =

. ...,

, ,

sia A una matrice simmetrica di elementi reali, di ordine n con autovalori λ , j=1, …, n; si

j

nominano gli autovalori in modo che sia

Allora per ogni vettore x di elementi reali e non tutti nulli, vale

=

dimostrazione

I QDQ

A =

poiché A è simmetrica, esiste una matrice ortogonale Q tale che

dove Λ è la matrice diagonale avente sugli elementi diagonali gli autovalori di A e Q è la matrice

che ha per colonne gli autovettori di A.

#

- *

Posto y=Q x, si ha y y=x QQ y=x x e

* . . .

L'altra maggiorazione λ x x≤x Ax si prova in

I ↑

n

- - -æ

modo analogo

se una matrice A è simmetrica e ammette autovalori positivi allora è definita positiva

questo

A e def

mostrato A

Siccome A def

X Xi

prime n simm sim

=

pos >0

: o : =n

con pos

. . .

.

dimontzazi

a c

denotiamo con λ , λ , …, λ gli autovalori della matrice A, con λ ≥ λ ≥ … ≥ λ ; per il risultato

1 2 n 1 2 n

sulle matrici simmetriche appena dimostrato si ottiene perché 8

-

e dunque x Ax>0 per ogni x non nullo

#

- >

-

in modo analogo si dimostra che,

se una matrice A è simmetrica e ammette autovalori negativi allora è definita negativa

per una matrice simmetrica A di elementi reali, il rapporto A

Aut

è detto quoziente di Rayleigh

il quoziente di Rayleigh ha senso solo per le matrici simmetriche

⑱ Ast=

As simmetrice

parte A (A(A)

As=

d

A As+Aa ,

= An=-A=

Ac [A-AY

con autisimmetrice A

d .

IT As

ITAx As

IT (AstAal== =

= AT

I(A I(I

T Ax I(=

1 TA) (AE))

+ T(AE)

=x =

=

- 0

- =

-

=

Autovalori di matrici e radici di polinomi

dato un polinomio di cui vogliamo calcolare le radici, si definisce matrice compagna del

polinomio o matrice di Frobenius, una matrice compagna che abbia come polinomio

caratteristico il polinomio assegnato.

complesso

auche

si consideri il seguente polinomio monico di grado n

di coefficienti q , q , …, q reali

1 2 n-1

definiamo la matrice di Frobenius di ordine n

associata al polinomio Q (z) nel modo seguente

n lungs le rige

prine

calcolando det(F–λΙ) mediante Laplace, si ottiene: e

esempio le aizadici

z-6z

(z)

Q

dato

Sie Z 3

1 zz

z 2

1z-6

+ e

raue

= = =

=

> .

( S

I

F det

be (F-1I)

asociate calcolianc

matrice Frabenire

d

univiana = e

:

-2) 1

( (di) st

det( 111

&

det (6-1) -2) 6 det

(F-1I) det + 6

+

=

-> + -

= +

-

il polinomio (-1)PQb()

di

caratteristico Freincide

cioe can

,

Cerchi di Gerschgorin e localizzazione di autovalori

sia A una matrice n x n di elementi a reali o complessi e si definiscono i seguenti cerchi K nel

ij i

piano complesso, detti cerchi di Gerschgorin, di centro a e raggio r

ii i

dove

esempio autovalore a

I

I Lautaalari

- -

↑ lagine

frautiere

mille

-I cerchio

I -

3 he

siccome

-2 comprende

C 1 un o

N -

-

data -I

ov autovelare

S A singolare

willo

pre prä

un essere essere

· -

-

-

2 3

- singolare

incluse

I

3' ' * se l'origine

man e van

-

-

-

Teorem di Gerschgeziu

gli autovalori λ , λ , …, λ , di A appartengono tutti all'unione dei cerchi K , i=1, …, n

1 2 n i

corollario

se gli n cerchi di Gerschgorin K formano s unioni disgiunte, denotate M , M , …, M , allora

i 1 2 s

ciascuna di queste unioni conterrà tanti autovalori di A quanti sono i cerchi che la compongono

se la matrice A è a coefficienti reali e simmetrica, i suoi autovalori sono reali e i cerchi di

⑧ Gerschgorin si riducono ad intervalli dell'asse reale

dal teorema di Gerschgorin si nota che se una matrice è strettamente diagonale

⑧ dominante per righe, allora nessun cerchio di Gerschgorin include l'origine degli assi del

piano complesso. Quindi una matrice strettamente diagonale dominante per righe ha

tutti i suoi autovalori diversi da zero e dunque è non singolare.

se A è una matrice strettamente diagonale dominante per colonne allora la matrice A

⑧

lo è per righe e, poiché A e A hanno gli stessi autovalori, abbiamo ce A è non singolare

B)

( (B) autovalore

XA) di A

é

vou

+ + CAPITOLO 16 calcolo autadori

di

-

METODO DELLE POTENZE

E METODO QR ITERATIVO

Convergenza di successioni di vettori e matrici

si definisce la convergenza di una successione di vettori una successione di matrici sulla base della

definizione di convergenza di una successione numerica.

una successione di vettori {x }, k=0,1,…, di n componenti converge ad un vettore x* e si scrive

k

* =>

(

er=

se le successioni numeriche definite da ogni componente die vettori x della successione di vettori,

k

-

⑦ >

convergono alle rispettive componenti del vettore x*, cioè se

-

(k) #

dove con x si indica la i-esima componente di x e con x la i-esima componente di x*.

i k i

E ->

ed è equivalente a

e quindi, la convergenza di una successione di vettori si può equivalentemente definire nel modo seguente.

una successione di vettori {x } è convergente ad un vettore x* se e solo se per ogni norma di

k

* -

vettori vale

per una successione di vettori {x } si può definire una successione di Cauchy

k

una successione di vettori {x } si dice successione di Cauchy se per ogni numero positivo ε,

k

--

esiste un numero positivo k (che dipende da ε) tale che, per ogni norma di vettori vale

Ik=K(2)/Franue

<0

[Xr} vale

Cauchy IlXp-InIk

di Fr

accessione se

· ,

,

lo stesso vale per le successioni di vettori:

una successione di vettori è convergente se e solo se è una successione di Cauchy

una successione di matrici {A }, k=0,1,…, di n x n elementi converge ad una matrice A e si scrive

->

k

*

se le successioni numeriche definite da ogni elemento della matrice A della successione di matrici,

k

convergono ai rispettivi elementi della matrice A, cioè se

- (3)

(k)

dove con a si indica l'elemento di riga i e colonna j della matrice A e con a il corrispondente

-

ij k ij

elemento di A

->

la definizione (3) è equivalente a

e dunque, la convergenza di una successione di matrici si può equivalentemente definire nel modo seguente

una successione di matrici {A } è convergente ad una matrice A se e solo se per ogni norma di

=>

k

matrici vale

Metodo delle potenze per il calcolo dell'autovalore di modulo massimo

metodo delle potenze:

metodo iterativo per il calcolo dell'autovalore di modulo massimo di un matrice A di ordine n

sotto le ipotesi che la matrice abbia autovettori linearmente indipendenti (ovvero sia

diagonalizzabile) e che i suoi autovalori λ , λ , …, λ siano nominati in modo tale che

1 2 n

allora, a partire da un vettore arbitrario v di norma uguale ad 1, genera una successione di

0

-

vettori {v } convergente all'autovettore x associato all'autovalore λ e, una successione di scalari

k 1 1

>

- -

{β } convergente all'autovalore di modulo massimo λ .

k 1

11

dunque, assegnato v arbitrario, con v =1 (dove la norma è una qualsiasi norma di vettore), il

Il

0 0

*

metodo delle potenze calcola un vettore u come il prodotto

1

- Il

11

e definisce il vettore v di norma uguale a 1 ( v =1)

1 1

- -IIIl

il metodo poi, calcola il vettore u da u =Av e definisce il vettore v con v =1

2 2 1 2 2

-

in generale, alla k-esima iterazione si ha

Il

Il

e definisce il vettore v con v =1

k k

_

>

si dimostra che

dimostrazione = E

si prova che ·

infatti si ha

e allora da ratieve

cui

implica

essendo per ipotesi la matrice diagonalizzabile, gli autovettori x , x , …, x sono linearmente

1 2 n

- - -

indipendenti, ogni vettore si può scrivere come combinazione lineare di x , x , …, x . Anche il vettore

1 2 n

- -

u

v si scrive come combinazione lineare degli autovettori:

0

- si suppone α ≠0. La scelta arbitraria di v , in generale assicura

1 0

ì

che v abbia componente non nulla rispetto a x

0 1

- ->

dalla definizione di autovalore e autovettore possiamo scrivere 3 Ti

raiche 2

⑮ e

raccogliendo λ si ottiene

1 e

-so

D

allora abbiamo che, *

antetzt dutüku wo

+ 40

...

Er Illanetazzt Ente all

...

la velocità di convergenza della successione {v } è governata dal rapporto |λ |/|λ |, infatti è

k 2 1

quello che tende a zero meno rapidamente rispetto agli altri rapporti |λ |/|λ |

j 1

esempio *

· piübento

10-6 X2=

Xs 999999

preso = , * velace

(

10-6 pi

Xz

Xs ?

1

preso =

= ·

,

delle {}

successione all'autovalore modula

di massima

auvergenze & Tr

K -

- Illall

la A

relazione

considera Bx v

Ex

si - = k 1

- -

-

poiché la successione {v } converge all'autovettore x /(± x ), per la definizione di autovalore e

Il

Il

k 1 1

-

-

-

autovettore, si deve avere che la successione {β } converge all'autovettore λ associato

κ 1

all'autovettore x /(± x ) per k che tende a infinito,

Il

11

1 1

- _ ⑰

nel metodo delle potenze, dalla definizione di si ha

AEk- (7)

Mx=

vie

↑

1 =41|a

I

de

riparte

esplicitare -

Br 7

+

I 1 -

per x

=

, ,

Bk ?

la Izk-Il

Euclider ha definizione

-VI-kn-

applicando be verber

che di

ei Wr-

per

manue s e

e vanne

: ,

VI

Br =

· k

- e

=Ar ↑

dove z è un vettore qualsiasi non ortogonale ad x (x z≠0)

implica auche Br

A 1 1

= - - -

il valore β converge all'autovalore λ con la stessa velocit&agra