LucioDemeioDipartimentodiScienzeMatematiche CorsodiAnalisiNumerica

Corso di Laurea in Ingegneria Informatica

Corso di Analisi Numerica

8 - METODI ITERATIVI PER I SISTEMI LINEARI

Lucio Demeio

Dipartimento di Scienze Matematiche

1

Norme e distanze

2

Autovalori ed autovettori

3

Matrici convergenti

4

Metodi iterativi

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

||αx|| = |α| ||x|| ;

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

||αx|| = |α| ||x|| ;

||x + y|| ≤ ||x|| + ||y|| ;

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

||αx|| = |α| ||x|| ;

||x + y|| ≤ ||x|| + ||y|| ;

Considereremo due norme notevoli in R

:

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

||αx|| = |α| ||x|| ;

||x + y|| ≤ ||x|| + ||y|| ;

Considereremo due norme notevoli in R

:

La norma l

(o norma euclidea): se x = (x

, x

, ..., x

)

||x||

= pP

x

;

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

||αx|| = |α| ||x|| ;

||x + y|| ≤ ||x|| + ||y|| ;

Considereremo due norme notevoli in R

:

La norma l

(o norma euclidea): se x = (x

, x

, ..., x

)

||x||

= pP

x

;

La norma l

(norma infinito): ||x||

= max

|x

|

Norme

Una norma in R

`e una funzione ||.|| : R

→ R tale che

||x|| ≥ 0 ∀ x ∈ R

;

||x|| = 0 ⇐⇒ x = 0 ;

||αx|| = |α| ||x|| ;

||x + y|| ≤ ||x|| + ||y|| ;

Considereremo due norme notevoli in R

:

La norma l

(o norma euclidea): se x = (x

, x

, ..., x

)

||x||

= pP

x

;

La norma l

(norma infinito): ||x||

= max

|x

|

La norma l

rappresenta la (ben nota) distanza euclidea dall’origine. In R

,

il luogo dei punti (vettori) per i quali ||x||

≤ R `e un cerchio di raggio R,

mentre il luogo dei punti per i quali ||x||

≤ R `e un quadrato di lato R.

Esempio con le norme

Sia x = (−1, −2, 0) . Allora: ||x||

= √

5 e ||x||

= 2.

Esempio con le norme

Sia x = (−1, −2, 0) . Allora: ||x||

= √

5 e ||x||

= 2.

Verifiche

E facile verificare che le norme ` l

ed l

soddisfano le propriet` a elencate all’inizio. Per esempio,

||x + y||

= max

|x

+ y

| ≤ max

(|x

| + |y

|)

≤ max

|x

| + max

|y

| = ||x||

+ ||y||

||x + y||

= X

i=1,n

(x

+ y

)

= X

i=1,n

(x

+ y

+ 2 x

y

)

≤ ||x||

+ ||y||

+ 2 ||x||

||y||

e quindi ||x + y||

≤ ||x||

+ ||y||

Nel penultimo passaggio `e stata applicata la disuguaglianza di

Cauchy-Schwarz: x

y ≤ ||x|| ||y|| .

Distanza

Dati due vettori x , y ∈ R

, si definisce distanza tra x e y la norma del vettore differenza,

d(x, y) = ||x − y||

Ovviamente, ogni norma porta con s´e una distanza.

Distanza

Dati due vettori x , y ∈ R

, si definisce distanza tra x e y la norma del vettore differenza,

d(x, y) = ||x − y||

Ovviamente, ogni norma porta con s´e una distanza.

Limiti e convergenza

Si dice che una successione di vettori {x

}

∈ R

converge ad un

vettore x ∈ R

rispetto ad una data norma ||.|| se, per ogni ε > 0,

esiste un intero N (ε) tale che ||x

− x|| < ε per ogni k ≥ N(ε) .

Distanza

Dati due vettori x , y ∈ R

, si definisce distanza tra x e y la norma del vettore differenza,

d(x, y) = ||x − y||

Ovviamente, ogni norma porta con s´e una distanza.

Limiti e convergenza

Si dice che una successione di vettori {x

}

∈ R

converge ad un vettore x ∈ R

rispetto ad una data norma ||.|| se, per ogni ε > 0, esiste un intero N (ε) tale che ||x

− x|| < ε per ogni k ≥ N(ε) .

Theorem

La successione {x

} ∈ R

converge ad x ∈ R

rispetto alla norma

l

se e solo se lim

x

= x

per ogni i = 1, 2, .., n.

Dimostrazione

Supponiamo che {x

} → x rispetto a ||.||

. Allora, dato ε > 0, esiste N (ε) t.c., per ogni k ≥ N(ε) , ||x

− x||

= max

|x

− x

| < ε . Questo implica che |x

− x

| < ε per ogni i = 1, 2, ..., n, e quindi la tesi.

Viceversa, sia lim

x

= x

per ogni i = 1, 2, .., n Allora, dato ε > 0, esistono N

(ε) t.c. |x

− x

| < ε per k > N

(ε). Sia

N (ε) = max

N

(ε). Se k > N (ε) allora

max

|x

− x

| = ||x

− x||

< ε, che implica la convergenza della

successione {x

} ad x.

Dimostrazione

Supponiamo che {x

} → x rispetto a ||.||

. Allora, dato ε > 0, esiste N (ε) t.c., per ogni k ≥ N(ε) , ||x

− x||

= max

|x

− x

| < ε . Questo implica che |x

− x

| < ε per ogni i = 1, 2, ..., n, e quindi la tesi.

Viceversa, sia lim

x

= x

per ogni i = 1, 2, .., n Allora, dato ε > 0, esistono N

(ε) t.c. |x

− x

| < ε per k > N

(ε). Sia

N (ε) = max

N

(ε). Se k > N (ε) allora

max

|x

− x

| = ||x

− x||

< ε, che implica la convergenza della successione {x

} ad x.

Norme equivalenti (senza dimostrazione)

Tutte le norme in R

sono equivalenti rispetto alle propriet` a di

convergenza: se una successione {x

} → x rispetto a ||.|| , allora converge rispetto a qualunque altra norma ||.||

. Per le norme viste qui, vale la relazione ||.||

≤ ||.||

≤ √

n ||.||

.

Convergenza: esempio Sia

{x

} =

 1, 2 + 1

k , 3

k

, e

sin k



Abbiamo

k→∞

lim 2 + 1 k = 2

k→∞

lim 3 k

= 0

k→∞

lim e

sin k = 0

e quindi {x

} → (1, 2, 0, 0)

.

Norme delle matrici

Sia M

lo spazio vettoriale delle matrici reali n × n . Una norma su M

`e una funzione ||.|| : M

→ R tale che

||A|| ≥ 0 ∀ A ∈ M

;

Norme delle matrici

Sia M

lo spazio vettoriale delle matrici reali n × n . Una norma su M

`e una funzione ||.|| : M

→ R tale che

||A|| ≥ 0 ∀ A ∈ M

;

||A|| = 0 ⇐⇒ A = 0 ;

Norme delle matrici

Sia M

lo spazio vettoriale delle matrici reali n × n . Una norma su M

`e una funzione ||.|| : M

→ R tale che

||A|| ≥ 0 ∀ A ∈ M

;

||A|| = 0 ⇐⇒ A = 0 ;

||αA|| = |α| ||A|| ;

Norme delle matrici

Sia M

lo spazio vettoriale delle matrici reali n × n . Una norma su M

`e una funzione ||.|| : M

→ R tale che

||A|| ≥ 0 ∀ A ∈ M

;

||A|| = 0 ⇐⇒ A = 0 ;

||αA|| = |α| ||A|| ;

||A + B|| ≤ ||A|| + ||B|| ;

Norme delle matrici

Sia M

lo spazio vettoriale delle matrici reali n × n . Una norma su M

`e una funzione ||.|| : M

→ R tale che

||A|| ≥ 0 ∀ A ∈ M

;

||A|| = 0 ⇐⇒ A = 0 ;

||αA|| = |α| ||A|| ;

||A + B|| ≤ ||A|| + ||B|| ;

||A B|| ≤ ||A|| ||B|| ;

Norme delle matrici

Sia M

lo spazio vettoriale delle matrici reali n × n . Una norma su M

`e una funzione ||.|| : M

→ R tale che

||A|| ≥ 0 ∀ A ∈ M

;

||A|| = 0 ⇐⇒ A = 0 ;

||αA|| = |α| ||A|| ;

||A + B|| ≤ ||A|| + ||B|| ;

||A B|| ≤ ||A|| ||B|| ;

Distanza

Si definisce distanza tra due matrici A e B la norma della differenza A − B :

d(A, B) = ||A − B||

Norme delle matrici (teorema)

Se ||.|| `e una norma sui vettori in R

, allora

||A|| = max

||Ax|| = max

||Az||

||z||

`e una norma su M

, che viene detta norma naturale o indotta. Da qui

in poi, salvo eccezioni, useremo sempre questa norma matriciale. L’ultima

uguaglianza segue dal fatto che, se z ha norma non nulla, allora z /||z|| ha

norma unitaria.

Norme delle matrici (teorema)

Se ||.|| `e una norma sui vettori in R

, allora

||A|| = max

||Ax|| = max

||Az||

||z||

`e una norma su M

, che viene detta norma naturale o indotta. Da qui in poi, salvo eccezioni, useremo sempre questa norma matriciale. L’ultima uguaglianza segue dal fatto che, se z ha norma non nulla, allora z /||z|| ha norma unitaria.

Corollario

Dal teorema precedente, segue che, per ogni z 6= 0 , per ogni A ∈ M

e per ogni norma naturale su M

abbiamo che

||Az|| ≤ ||A|| ||z||.

Norme delle matrici

Le norme naturali che considereremo sono quelle indotte dalle norme gi`a viste per i vettori:

||A||

= max

||Ax||

||A||

= max

||Ax||

,

dette rispettivamente norma l

e norma l

.

Norme delle matrici

Le norme naturali che considereremo sono quelle indotte dalle norme gi`a viste per i vettori:

||A||

= max

||Ax||

||A||

= max

||Ax||

, dette rispettivamente norma l

e norma l

.

Theorem (Norma infinito)

Sia A = {a

} una matrice n × n . Si ha allora

||A||

= max

X

j=1

|a

|

Dimostrazione

Dimostriamo che valgono contemporaneamente le due disuguaglianze

||A||

≤ max

n

X

j=1

|a

| e ||A||

≥ max

n

X

j=1

|a

|

Per la prima disuguaglianza, se x `e un vettore con ||x||

= 1, allora

||A x||

= max

|(A x)

| = max

n

X

j=1

a

x

≤ max

X

j=1

|a

| |x

| ≤ max

X

j=1

|a

|

da cui segue la prima disuguaglianza.

Per la seconda disuguaglianza, consideriamo dapprima le somme P

j=1

|a

| e sia p l’intero per cui questa somma assume il massimo, cio`e

n

X

j=1

|a

| = max

X

j=1

|a

|.

Sia x il vettore di componenti x

= 1 se a

≥ 0 e x

= −1 se a

< 0.

Ovviamente `e ||x||

= 1, ed inoltre a

x

= |a

| per ogni j = 1, 2, ..., n.

Pertanto

||A x||

= max

|(A x)

| = max

˛

˛

˛

˛

˛

n

X

j=1

a

x

˛

˛

˛

˛

˛

≥

˛

˛

˛

˛

˛

n

X

j=1

a

x

˛

˛

˛

˛

˛

=

˛

˛

˛

˛

˛

n

X

j=1

|a

|

˛

˛

˛

˛

˛

= max

X

j=1

|a

|

da cui segue la seconda disuguaglianza.

Esempio

A =













4 −1 4 −3 −1

−1 3 −2 3 −3

3 −3 3 0 2

−2 2 −2 3 1

3 −3 −2 −4 2













X

j=1,n

|a

| = 13 X

j=1,n

|a

| = 12

X

j=1,n

|a

| = 11 X

j=1,n

|a

| = 10

X

j=1,n

|a

| = 14

quindi ||A||

= 14.

Esercizio 7.1.2

||x||

= P

|x

| .

Esercizio 7.1.2

||x||

= P

|x

| .

(a) Verifica delle propriet` a:

Esercizio 7.1.2

||x||

= P

|x

| . (a) Verifica delle propriet` a:

||x||

≥ 0 perch`e somma di numeri non negativi;

Esercizio 7.1.2

||x||

= P

|x

| . (a) Verifica delle propriet` a:

||x||

≥ 0 perch`e somma di numeri non negativi;

x = 0 ⇒ ||x||

= 0 perch`e x

= 0 ∀i , e ||x||

= 0 ⇒ x = 0 , perch`e se x

6= 0 per qualche i allora P

i=1

|x

| > 0 ;

Esercizio 7.1.2

||x||

= P

|x

| . (a) Verifica delle propriet` a:

||x||

≥ 0 perch`e somma di numeri non negativi;

x = 0 ⇒ ||x||

= 0 perch`e x

= 0 ∀i , e ||x||

= 0 ⇒ x = 0 , perch`e se x

6= 0 per qualche i allora P

i=1

|x

| > 0 ;

||α x||

= P

i=1

|α x

| = |α| ||x||

;

Esercizio 7.1.2

||x||

= P

|x

| . (a) Verifica delle propriet` a:

||x||

≥ 0 perch`e somma di numeri non negativi;

x = 0 ⇒ ||x||

= 0 perch`e x

= 0 ∀i , e ||x||

= 0 ⇒ x = 0 , perch`e se x

6= 0 per qualche i allora P

i=1

|x

| > 0 ;

||α x||

= P

i=1

|α x

| = |α| ||x||

;

||x + y||

= P

i=1

|x

+ y

| ≤ P

i=1

(|x

| + |y

|) = ||x||

+ ||y||

.

Esercizio 7.1.2

||x||

= P

|x

| . (a) Verifica delle propriet` a:

||x||

≥ 0 perch`e somma di numeri non negativi;

x = 0 ⇒ ||x||

= 0 perch`e x

= 0 ∀i , e ||x||

= 0 ⇒ x = 0 , perch`e se x

6= 0 per qualche i allora P

i=1

|x

| > 0 ;

||α x||

= P

i=1

|α x

| = |α| ||x||

;

||x + y||

= P

i=1

|x

+ y

| ≤ P

i=1

(|x

| + |y

|) = ||x||

+ ||y||

. (c) Relazione con la norma l

:

||x||

=

n

X

i=1

|x

|

!

=

n

X

i=1

|x

|

+ X

i6=j

|x

| |x

| ≥

n

X

i=1

|x

|

= ||x||

Esercizio 7.1.7

||A||

= max

|a

| .

A =

 1 2 1 1

 B =

 1 1 1 1



AB =

 3 3 2 2



Quindi

||A||

= 2 ||B||

= 1 ||A B||

= 3

in contraddizione con la propriet` a ||A B|| ≤ ||A|| ||B|| .

Autovalori ed autovettori

Autovalori ed autovettori

Data una matrice quadrata A di dimensione n, un vettore non nullo x ∈ R

si dice autovettore di A se esiste un numero λ, reale o complesso, tale che

A x = λx

ed in tal caso λ si chiama autovalore di A e l’equazione scritta sopra equazione agli autovalori. Tale equazione pu` o anche essere scritta come

(A − λ I) x = 0

e quindi gli autovettori sono le soluzioni non nulle di tale sistema.

Siccome si tratta di un sistema omogeneo, esso ammette soluzioni non nulle se e solo se la matrice A − λ I `e singolare, ovvero ha

determinante nullo.

Autovalori ed autovettori

Data una matrice quadrata A di dimensione n, un vettore non nullo x ∈ R

si dice autovettore di A se esiste un numero λ, reale o complesso, tale che

A x = λx

ed in tal caso λ si chiama autovalore di A e l’equazione scritta sopra equazione agli autovalori. Tale equazione pu` o anche essere scritta come

(A − λ I) x = 0

e quindi gli autovettori sono le soluzioni non nulle di tale sistema.

Siccome si tratta di un sistema omogeneo, esso ammette soluzioni non nulle se e solo se la matrice A − λ I `e singolare, ovvero ha

determinante nullo.

Gli autovettori sono quei vettori che vengono moltiplicati per uno

scalare sotto l’azione della matrice, cio`e conservano la direzione.

Questa condizione fornisce gli autovalori:

|A − λ I| =        

a

− λ a

... a

a

a

− λ ... a

... ... ... ...

a

a

... a

− λ        

≡ p

(λ) = 0

che `e un’equazione polinomiale di grado n in λ, detta equazione

caratteristica. Per il teorema fondamentale dell’algebra, p

(λ)

possiede n radici, reali o complesse, ciascuna contata con la propria

molteplicit` a. Se la matrice `e reale, allora, se z `e una radice, lo `e pure

z

. Ricordiamo anche che, se x `e un autovettore, anche α x lo `e, per

qualunque α (reale o complesso), cio`e gli autovettori sono determinati

a meno di una costante arbitraria.

Questa condizione fornisce gli autovalori:

|A − λ I| =        

a

− λ a

... a

a

a

− λ ... a

... ... ... ...

a

a

... a

− λ        

≡ p

(λ) = 0

che `e un’equazione polinomiale di grado n in λ, detta equazione caratteristica. Per il teorema fondamentale dell’algebra, p

(λ) possiede n radici, reali o complesse, ciascuna contata con la propria molteplicit` a. Se la matrice `e reale, allora, se z `e una radice, lo `e pure z

. Ricordiamo anche che, se x `e un autovettore, anche α x lo `e, per qualunque α (reale o complesso), cio`e gli autovettori sono determinati a meno di una costante arbitraria.

Esempi

Mathematica file Iterativi1.nb

Raggio spettrale

Sia A una matrice n × n e siano λ

, i = 1, 2, ..., n gli autovalori. Il massimo, in valore assoluto, degli autovalori `e detto raggio spettrale:

ρ(A) = max

|λ

| Ad esempio, se

A =





1 −2 0

1 1 0

0 0 4



 abbiamo

λ

= 1 + i √

2, λ

= 1 − i √

2, λ

= 4 con |λ

| = √

3, |λ

| = √

3, |λ

| = 4 e quindi ρ(A) = 4.

Theorem (Raggio spettrale) Sia A una matrice n × n . Allora

||A||

= [ρ( ˜ AA)]

ρ(A) ≤ ||A|| per ogni norma naturale ||.|| .

Theorem (Raggio spettrale) Sia A una matrice n × n . Allora

||A||

= [ρ( ˜ AA)]

ρ(A) ≤ ||A|| per ogni norma naturale ||.|| .

Dimostrazione

Dimostriamo solo la seconda parte. Se x `e un autovettore appartenente all’ autovalore λ, con ||x|| = 1 , abbiamo

||A x|| = ||λ x|| = |λ| ||x|| = |λ|.

Ma ||A x|| ≤ ||A|| e quindi

ρ(A) = max |λ| ≤ ||A||

Se A `e simmetrica, allora ||A||

= ρ(A).

Re (λ) Im (λ)

O ρ (A)

Matrici convergenti

In molte applicazioni, `e importante studiare le potenze delle matrici, ed in particolare cosa succede delle potenze successive quando l’esponente va all’infinito, cio`e lim

A

. Si d´ a allora la seguente definizione: una matrice si dice che `e convergente se

k→∞

lim (A

)

= 0 ∀ 1 ≤ i, j ≤ n

Matrici convergenti

In molte applicazioni, `e importante studiare le potenze delle matrici, ed in particolare cosa succede delle potenze successive quando l’esponente va all’infinito, cio`e lim

A

. Si d´ a allora la seguente definizione: una matrice si dice che `e convergente se

k→∞

lim (A

)

= 0 ∀ 1 ≤ i, j ≤ n

Theorem (Matrici convergenti)

Le seguenti affermazioni sono equivalenti:

A ` e una matrice convergente;

Matrici convergenti

In molte applicazioni, `e importante studiare le potenze delle matrici, ed in particolare cosa succede delle potenze successive quando l’esponente va all’infinito, cio`e lim

A

. Si d´ a allora la seguente definizione: una matrice si dice che `e convergente se

k→∞

lim (A

)

= 0 ∀ 1 ≤ i, j ≤ n

Theorem (Matrici convergenti)

Le seguenti affermazioni sono equivalenti:

A ` e una matrice convergente;

esiste una norma naturale t.c. lim

||A

|| = 0 ;

Matrici convergenti

In molte applicazioni, `e importante studiare le potenze delle matrici, ed in particolare cosa succede delle potenze successive quando l’esponente va all’infinito, cio`e lim

A

. Si d´ a allora la seguente definizione: una matrice si dice che `e convergente se

k→∞

lim (A

)

= 0 ∀ 1 ≤ i, j ≤ n

Theorem (Matrici convergenti)

Le seguenti affermazioni sono equivalenti:

A ` e una matrice convergente;

esiste una norma naturale t.c. lim

||A

|| = 0 ;

lim

||A

|| = 0 per tutte le norme naturali;

Matrici convergenti

In molte applicazioni, `e importante studiare le potenze delle matrici, ed in particolare cosa succede delle potenze successive quando l’esponente va all’infinito, cio`e lim

A

. Si d´ a allora la seguente definizione: una matrice si dice che `e convergente se

k→∞

lim (A

)

= 0 ∀ 1 ≤ i, j ≤ n

Theorem (Matrici convergenti)

Le seguenti affermazioni sono equivalenti:

A ` e una matrice convergente;

esiste una norma naturale t.c. lim

||A

|| = 0 ; lim

||A

|| = 0 per tutte le norme naturali;

ρ(A) < 1;

Matrici convergenti

In molte applicazioni, `e importante studiare le potenze delle matrici, ed in particolare cosa succede delle potenze successive quando l’esponente va all’infinito, cio`e lim

A

. Si d´ a allora la seguente definizione: una matrice si dice che `e convergente se

k→∞

lim (A

)

= 0 ∀ 1 ≤ i, j ≤ n

Theorem (Matrici convergenti)

Le seguenti affermazioni sono equivalenti:

A ` e una matrice convergente;

esiste una norma naturale t.c. lim

||A

|| = 0 ; lim

||A

|| = 0 per tutte le norme naturali;

ρ(A) < 1;

lim

A

x = 0 per ogni x.

Matrici convergenti Ad esempio, la matrice



2

0

16



`e convergente (provare!!).

Metodi classici

Metodi classici

I metodi iterativi per la soluzione dei sistemi lineari vengono

usati in alternativa ai metodi diretti (eliminazione Gaussiana)

quando il numero di equazioni/incognite `e elevato e la matrice

dei coefficienti `e sparsa. In tal caso, i metodi iterativi sono pi` u

veloci e richiedono meno memorizzazione dei metodi diretti.

Metodi classici

I metodi iterativi per la soluzione dei sistemi lineari vengono usati in alternativa ai metodi diretti (eliminazione Gaussiana) quando il numero di equazioni/incognite `e elevato e la matrice dei coefficienti `e sparsa. In tal caso, i metodi iterativi sono pi` u veloci e richiedono meno memorizzazione dei metodi diretti.

Un metodo iterativo per risolvere un sistema lineare A x = b

parte, in generale, da una stima iniziale x

e costruisce una

successione di vettori {x

} che converge alla soluzione.

Metodi classici

I metodi iterativi per la soluzione dei sistemi lineari vengono usati in alternativa ai metodi diretti (eliminazione Gaussiana) quando il numero di equazioni/incognite `e elevato e la matrice dei coefficienti `e sparsa. In tal caso, i metodi iterativi sono pi` u veloci e richiedono meno memorizzazione dei metodi diretti.

Un metodo iterativo per risolvere un sistema lineare A x = b parte, in generale, da una stima iniziale x

e costruisce una successione di vettori {x

} che converge alla soluzione.

Vedremo tre metodi classici: quello di Jacobi, quello di

Gauss-Seidel e quello di Gauss-Seidel con rilassamento.

Il metodo di Jacobi

Consideriamo il sistema A x = b e scriviamo esplicitamente le equazioni:

a

x

+ a

x

+ ... + a

x

= b

a

x

+ a

x

+ ... + a

x

= b

...

a

x

+ a

x

+ ... + a

x

= b

Risolviamo ora la i− esima equazione per l’incognita diagonale x

,

sotto l’ipotesi che a

6= 0 per ogni i = 1, 2, ..., n:

Il metodo di Jacobi

x

= [b

− (a

x

+ ... + a

x

)] /a

x

= [b

− (a

x

+ ... + a

x

)] /a

...

x

= [b

− (a

x

+ a

x

+ ...)] /a

ovvero

x

= 0

@b

− X

j6=1

a

x

1 A /a

x

= 0

@b

− X

j6=2

a

x

1 A /a

...

x

= 0

@b

− X

j6=n

a

x

1

A /a

Il metodo di Jacobi

Supponiamo ora di aver ottenuto il vettore {x

} della k− esima iterazione. L’iterazione successiva viene allora data da

x

=



b

− X

j6=1

a

x



 /a

x

=



b

− X

j6=2

a

x



 /a

...

x

=



b

− X

j6=n

a

x



 /a

L’ipotesi a

6= 0 per ogni i `e una condizione necessaria (ma non

sufficiente !!) per la convergenza del metodo.

Il metodo di Jacobi - Esempio

7 x

+ 3 x

+ x

= 18 2 x

− 9 x

+ 4 x

= 12 x

− 4 x

+ 12 x

= 6

Risolvendo per le ingognite diagonali otteniamo lo schema iterativo:

x

= (18 − 3 x

− x

)/7

x

= (2 x

+ 4 x

− 12)/9

x

= (6 − x

+ 4 x

)/12

Mathematica file Jacobi.nb

Il metodo di Gauss-Seidel

Riprendiamo lo schema iterativo di Jacobi:

x

= 0

@b

− X

j6=1

a

x

1 A /a

x

= 0

@b

− X

j6=2

a

x

1 A /a

...

x

= 0

@b

− X

j6=n

a

x

1 A /a

E chiaro che, una volta determinato ` x

dalla prima equazione, possiamo

utilizzare il nuovo valore nelle equazioni successive, al posto di x

. Lo

stesso dicasi per x

nelle equazioni dalla terza in poi, e cos`ı via per le

altre incognite.

Il metodo di Gauss-Seidel

Lo schema iterativo che si ottiene in tal guisa `e detto metodo di Gauss-Seidel:

x

=



b

− X

j6=1

a

x



 /a

x

=



b

− a

x

− X

j≥3

a

x



 /a

x

=



b

− a

x

− a

x

− X

j≥4

a

x



 /a

...

x

=



b

− X

j<n

a

x



 /a

ovvero

x

=



b

−

i−1

X

j=1

a

x

−

n

X

j=i+1

a

x



 /a

Versioni matriciali: Jacobi

Il metodo di Jacobi `e equivalente a scrivere la matrice dei coefficienti, A, come somma della sua parte diagonale e di quella non diagonale, A = D + R, dove

D =









a

0 0 ... 0 0 a

0 ... 0 0 0 ... ... 0 0 0 0 ... a







 R =









0 a

a

... a

a

0 a

... a

... ... ... ... ...

a

a

a

... 0









Versioni matriciali: Jacobi

Il metodo di Jacobi `e equivalente a scrivere la matrice dei coefficienti, A, come somma della sua parte diagonale e di quella non diagonale, A = D + R, dove

D =









a

0 0 ... 0 0 a

0 ... 0 0 0 ... ... 0 0 0 0 ... a







 R =









0 a

a

... a

a

0 a

... a

... ... ... ... ...

a

a

a

... 0









Il sistema A x = b si pu` o scrivere allora: (D + R) x = b, ovvero D x = b − R x . Quindi x = D

(b − R x) e l’algoritmo iterativo di Jacobi si pu` o scrivere come

x

= D

(b − R x

) = T x

+ c.

dove T ≡ −D

R e c = D

b .

Versioni matriciali: Gauss-Seidel

Per il metodo di Gauss-Seidel scriviamo ancora A = D + R, ma poniamo inoltre R = −L − U , dove

L = −













0 0 0 ... 0

a

0 0 ... 0 a

a

0 ... 0 ... ... ... ... ...

a

a

a

... 0













U = −













0 a

a

... a

0 0 a

... a

... ... ... ... ...

0 0 0 ... a

0 0 0 ... 0













Il sistema A x = b si pu` o scrivere allora: (D − L − U) x = b , ovvero (D − L) x = U x + b . Quindi x = (D − L)

(U x + b) e l’algoritmo iterativo di Gauss-Seidel si pu` o scrivere come

x

= (D − L)

(U x

+ b) = T x

+ c.

dove T ≡ (D − L)

U e c = (D − L)

b .

Il sistema A x = b si pu` o scrivere allora: (D − L − U) x = b , ovvero (D − L) x = U x + b . Quindi x = (D − L)

(U x + b) e l’algoritmo iterativo di Gauss-Seidel si pu` o scrivere come

x

= (D − L)

(U x

+ b) = T x

+ c.

dove T ≡ (D − L)

U e c = (D − L)

b .

Forme matriciali

Le forme matriciali per il metodo di Jacobi e di Gauss-Seidel

torneranno utili per l’analisi di convergenza dei metodi.

Convergenza dei metodi iterativi

Abbiamo visto che i metodi di Jacobi e di Gauss-Seidel in forma

matriciale si scrivono x

= T x

+ c, dove T ≡ −D

R per

Jacobi e T ≡ (D − L)

U per Gauss-Seidel. Il teorema principale

sulla convergenza dice che

Convergenza dei metodi iterativi

Abbiamo visto che i metodi di Jacobi e di Gauss-Seidel in forma matriciale si scrivono x

= T x

+ c, dove T ≡ −D

R per Jacobi e T ≡ (D − L)

U per Gauss-Seidel. Il teorema principale sulla convergenza dice che

Theorem

Per ogni vettore x

∈ R

, la successione {x

} definita da x

= T x

+ c,

converge all’unica soluzione del problema x = T x + c se e solo se

ρ(T) < 1.

Convergenza dei metodi iterativi

Abbiamo visto che i metodi di Jacobi e di Gauss-Seidel in forma matriciale si scrivono x

= T x

+ c, dove T ≡ −D

R per Jacobi e T ≡ (D − L)

U per Gauss-Seidel. Il teorema principale sulla convergenza dice che

Theorem

Per ogni vettore x

∈ R

, la successione {x

} definita da x

= T x

+ c,

converge all’unica soluzione del problema x = T x + c se e solo se ρ(T) < 1.

Per la dimostrazione del teorema, abbiamo bisogno di un lemma

preparatorio.

Lemma

Sia T una matrice n × n e sia ρ(T) il suo raggio spettrale. Se ρ(T) < 1 allora la matrice I − T ` e invertibile e

(I − T)

= I + T + T

+ ... =

∞

X

n=0

T

Lemma

Sia T una matrice n × n e sia ρ(T) il suo raggio spettrale. Se ρ(T) < 1 allora la matrice I − T ` e invertibile e

(I − T)

= I + T + T

+ ... =

∞

X

n=0

T

Dimostrazione

Cominciamo con l’osservare che, se T x = λ x (cio`e se λ `e un autovalore di T) allora 1 − λ `e un autovalore dt I − T , infatti (I − T) x = (1 − λ) x . Ma, per ipotesi, ρ(T) < 1 e quindi |λ| < 1 per ogni autovalore. Di conseguenza, la matrice I − T non ha autovalori nulli ed `e invertibile. Sia ora

S

= I + T + T

+ ... + T

= P

n=0

T

. Allora

(I − T) S

= (I + T + T

+ ... + T

) − (T + T

+ ... + T

) = I − T

.

Ora, dall’ipotesi ρ(T) < 1 segue che T `e convergente, e quindi

m→∞

lim (I − T) S

= lim

m→∞

(I − T

) = I da cui (I − T)

= lim

m→∞

S

=

∞

X

n=0

T

Ora, dall’ipotesi ρ(T) < 1 segue che T `e convergente, e quindi

m→∞

lim (I − T) S

= lim

m→∞

(I − T

) = I da cui (I − T)

= lim

m→∞

S

=

∞

X

n=0

T

Dimostrazione del teorema

Dimostriamo prima che se ρ(T) < 1 la successione converge. Consideriamo la successione

x

= T x

+ c

= T (T x

+ c) + c

= T

x

+ (T + I) c ...

= T

x

+ (T

+ T

+ ... + I) c

Riassumendo,

x

= T

x

+ (T

+ T

+ ... + I) c Ma ρ(T) < 1, quindi T `e convergente e quindi

k→∞

lim T

x

= 0

e quindi, per il lemma precedente,

k→∞

lim x

=

∞

X

n=0

T

!

c = (I − T)

c

La successione {x

} converge pertanto al vettore x = (I − T)

c, ed

abbiamo x = T x + c.

Supponiamo ora che la successione {x

} converga alla soluzione (unica) di x = T x + c e dimostriamo che deve essere ρ(T) < 1.

Dimostreremo in realt` a l’affermazione equivalente che T `e

convergente. Sia allora z ∈ R

arbitrario e sia x la soluzione (unica) di x = T x + c. Poniamo x

= x − z e costruiamo la successione x

= T x

+ c; per ipotesi, {x

} converge ad x e

x − x

= (T x + c) − (T x

+ c) = T (x − x

)

= T

(x − x

) = ... = T

(x − x

) = T

z E pertanto

k→∞

lim T

z = lim

k→∞

(x − x

) = 0

che, per l’arbitrariet` a di z, implica la convergenza di T.

Alcuni fatti importanti

Elenchiamo di seguito alcuni teoremi sulla convergenza dei metodi

iterativi senza dimostrarli; comunque essi seguono dai teoremi visti in

precedenza.

Alcuni fatti importanti

Elenchiamo di seguito alcuni teoremi sulla convergenza dei metodi iterativi senza dimostrarli; comunque essi seguono dai teoremi visti in precedenza.

Sia ||T|| < 1 in qualunque norma naturale e sia c ∈ R

un vettore dato. Allora la successione {x

} data da

x

= T x

+ c converge, per ogni x

∈ R

ad un vettore

x ∈ R

e valgono le seguenti limitazioni sull’errore:

Alcuni fatti importanti

Elenchiamo di seguito alcuni teoremi sulla convergenza dei metodi iterativi senza dimostrarli; comunque essi seguono dai teoremi visti in precedenza.

Sia ||T|| < 1 in qualunque norma naturale e sia c ∈ R

un vettore dato. Allora la successione {x

} data da

x

= T x

+ c converge, per ogni x

∈ R

ad un vettore x ∈ R

e valgono le seguenti limitazioni sull’errore:

1

||x − x

|| ≤ ||T||

||x

− x|| ;

2

||x − x

|| ≤

||x

− x

|| ;

Alcuni fatti importanti

Elenchiamo di seguito alcuni teoremi sulla convergenza dei metodi iterativi senza dimostrarli; comunque essi seguono dai teoremi visti in precedenza.

Sia ||T|| < 1 in qualunque norma naturale e sia c ∈ R

un vettore dato. Allora la successione {x

} data da

x

= T x

+ c converge, per ogni x

∈ R

ad un vettore x ∈ R

e valgono le seguenti limitazioni sull’errore:

1

||x − x

|| ≤ ||T||

||x

− x|| ;

2

||x − x

|| ≤

||x

− x

|| ;

Se A `e a dominanza diagonale stretta, allora i metodi di Jacobi e

di Gauss-Seidel convergono per qualunque scelta della stima

iniziale x

;

Alcuni fatti importanti

Elenchiamo di seguito alcuni teoremi sulla convergenza dei metodi iterativi senza dimostrarli; comunque essi seguono dai teoremi visti in precedenza.

Sia ||T|| < 1 in qualunque norma naturale e sia c ∈ R

un vettore dato. Allora la successione {x

} data da

x

= T x

+ c converge, per ogni x

∈ R

ad un vettore x ∈ R

e valgono le seguenti limitazioni sull’errore:

1

||x − x

|| ≤ ||T||

||x

− x|| ;

2

||x − x

|| ≤

||x

− x

|| ;

Se A `e a dominanza diagonale stretta, allora i metodi di Jacobi e di Gauss-Seidel convergono per qualunque scelta della stima iniziale x

;

il raggio spettrale d` a una misura della rapidit` a della convergenza

del metodo iterativo, ||x

− x|| ≈ ρ(T)

||x

− x|| .

Alcuni fatti importanti: teorema di Stein-Rosenberg

Indichiamo con T

e T

le matrici T rispettivamente del metodo di Jacobi e di Gauss-Seidel e sia A la matrice dei coefficienti del sistema.

Allora, se a

> 0 per ogni i e a

≤ 0 per ogni i 6= j , una e solo una

delle seguenti affermazioni `e vera:

Alcuni fatti importanti: teorema di Stein-Rosenberg

Indichiamo con T

e T

le matrici T rispettivamente del metodo di Jacobi e di Gauss-Seidel e sia A la matrice dei coefficienti del sistema.

Allora, se a

> 0 per ogni i e a

≤ 0 per ogni i 6= j , una e solo una delle seguenti affermazioni `e vera:

0 ≤ ρ(T

) < ρ(T

) < 1;

Alcuni fatti importanti: teorema di Stein-Rosenberg

Indichiamo con T

e T

le matrici T rispettivamente del metodo di Jacobi e di Gauss-Seidel e sia A la matrice dei coefficienti del sistema.

Allora, se a

> 0 per ogni i e a

≤ 0 per ogni i 6= j , una e solo una delle seguenti affermazioni `e vera:

0 ≤ ρ(T

) < ρ(T

) < 1;

1 < ρ(T

) < ρ(T

);

Alcuni fatti importanti: teorema di Stein-Rosenberg

Indichiamo con T

e T

le matrici T rispettivamente del metodo di Jacobi e di Gauss-Seidel e sia A la matrice dei coefficienti del sistema.

Allora, se a

> 0 per ogni i e a

≤ 0 per ogni i 6= j , una e solo una delle seguenti affermazioni `e vera:

0 ≤ ρ(T

) < ρ(T

) < 1;

1 < ρ(T

) < ρ(T

);

ρ(T

) = ρ(T

) = 0

Alcuni fatti importanti: teorema di Stein-Rosenberg

Indichiamo con T

e T

le matrici T rispettivamente del metodo di Jacobi e di Gauss-Seidel e sia A la matrice dei coefficienti del sistema.

Allora, se a

> 0 per ogni i e a

≤ 0 per ogni i 6= j , una e solo una delle seguenti affermazioni `e vera:

0 ≤ ρ(T

) < ρ(T

) < 1;

1 < ρ(T

) < ρ(T

);

ρ(T

) = ρ(T

) = 0

ρ(T

) = ρ(T

) = 1.

Alcuni fatti importanti: teorema di Stein-Rosenberg

Indichiamo con T

e T

le matrici T rispettivamente del metodo di Jacobi e di Gauss-Seidel e sia A la matrice dei coefficienti del sistema.

Allora, se a

> 0 per ogni i e a

≤ 0 per ogni i 6= j , una e solo una delle seguenti affermazioni `e vera:

0 ≤ ρ(T

) < ρ(T

) < 1;

1 < ρ(T

) < ρ(T

);

ρ(T

) = ρ(T

) = 0 ρ(T

) = ρ(T

) = 1.

Vediamo che, sotto le ipotesi particolari enunciate nel teorema, quando uno dei due metodi converge allora convergono entrambi, Gauss-Seidel facendolo con maggior rapidit` a (vedi prima

affermazione) e che quando un metodo diverge allora divergono

entrambi (seconda affermazione).

Il Successive Over Relaxation Method, SOR

Dalle considerazioni precedenti, `e chiaro che un metodo iterativo converge tanto pi` u rapidamente quanto pi` u piccolo `e il raggio spettrale della matrice che lo caratterizza. ` E pertanto vantaggioso scegliere un metodo iterativo che abbia raggio spettrale il pi` u piccolo possibile. Questo sogno si pu` o realizzare con il metodo del sovrarilassamento (Successive Over

Relaxation Method, SOR).

Il Successive Over Relaxation Method, SOR

Dalle considerazioni precedenti, `e chiaro che un metodo iterativo converge tanto pi` u rapidamente quanto pi` u piccolo `e il raggio spettrale della matrice che lo caratterizza. ` E pertanto vantaggioso scegliere un metodo iterativo che abbia raggio spettrale il pi` u piccolo possibile. Questo sogno si pu` o realizzare con il metodo del sovrarilassamento (Successive Over

Relaxation Method, SOR).

Riprendiamo la formula iterativa esplicita (non matriciale) del metodo di Gauss-seidel e riportiamola subito sotto in forma matriciale:

x

=



b

−

i−1

X

j=1

a

x

−

n

X

j=i+1

a

x



 /a

x

= D

(b + L x

+ U x

)

con D , L ed U definite in precedenza.

Il Successive Over Relaxation Method, SOR

Il metodo SOR consiste in una variante del metodo di

Gauss-Seidel, in cui il valore x

viene ottenuto mediante una

media pesata tra il valore fornito dall’iterazione di Gauss-Seidel

(che riportiamo qui sotto per completezza) ed il valore x

dell’iterazione precedente:

Il Successive Over Relaxation Method, SOR

Il metodo SOR consiste in una variante del metodo di

Gauss-Seidel, in cui il valore x

viene ottenuto mediante una media pesata tra il valore fornito dall’iterazione di Gauss-Seidel (che riportiamo qui sotto per completezza) ed il valore x

dell’iterazione precedente:

x

= D

(b + L x

+ U x

)

x

= ω D

(b + L x

+ U x

) + (1 − ω)x

dove ω > 0 `e un parametro reale, per ora arbitario. Moltiplicando l’ultima equazione da sinistra per D,

D x

= ω (b + L x

+ U x

) + (1 − ω) D x

Riprendiamo:

D x

= ω (b + L x

+ U x

) + (1 − ω) D x

Riprendiamo:

D x

= ω (b + L x

+ U x

) + (1 − ω) D x

da cui

(D − ωL)x

= (ω U + (1 − ω) D) x

+ ω b x

= (D − ωL)

(ω U + (1 − ω) D) x

+ω (D − ωL)

b

Riprendiamo:

D x

= ω (b + L x

+ U x

) + (1 − ω) D x

da cui

(D − ωL)x

= (ω U + (1 − ω) D) x

+ ω b x

= (D − ωL)

(ω U + (1 − ω) D) x

+ω (D − ωL)

b

Lo schema iterativo SOR pu` o dunque essere scritto nella usuale forma matriciale x

= T x

+ c, dove

T = T

≡ (D − ωL)

(ω U + (1 − ω) D) e

c = c

≡ ω (D − ωL)

b