Metodi iterativi per la soluzione di sistemi lineari

Metodi iterativi per la soluzione di sistemi lineari

Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica

Metodi iterativi e diretti

Problema.

Supponiamo che siano A ∈ Cn×n(matrice non singolare), b ∈ Cn(vettore colonna). Bisogna risolvere il problemaAx = bavente sol. unica x∗. Si pu`o utilizzare lafattorizzazione LU con pivoting, il cui costo computazionale `e in generale diO(n3_{/3)operazioni moltiplicative, che}

diventa proibitivo se n `e particolarmente elevato.

In tal senso, sia A una matrice invertibile. AlloraPA = LU dove P `e una matrice di permutazione,

L `e una matrice triangolare inferiore a diagonale unitaria (lii = 1, ∀i ),

U una matrice triangolare superiore.

Se Ax = b, determinata PA = LU, per risolvere Ax = b da

Ax = b ⇔ PAx = Pb ⇔ LUx = Pb

Metodi iterativi e diretti

L’idea dei

metodi iterativi

`

e quello di ottenere una

successione di vettori x

(k)

→ x

∗

cosicch`

e per ¯

k  n sia

x

(¯k)

≈ x

∗

_.

In generale, la soluzione non `

e ottenuta esattamente come nei

metodi diretti in un numero finito di operazioni (in aritmetica

esatta), ma quale limite, accontentandosi di poche iterazioni

ognuna dal costo quadratico (tipicamente quello di un

prodotto matrice-vettore).

Il costo totale sar`

a

O(¯

k · n

2

)

da paragonarsi con

O(n

3

/3)

Metodi iterativi stazionari

Supponiamo che la matrice non singolare A ∈ C

n×n

sia tale che

A = M − N, con M non singolare.

Allora, visto che M ´

e invertibile,

Ax = b

⇔ Mx − Nx = b ⇔ Mx = Nx + b ⇔ x =

M

−1

Nx + M

−1

b

e quindi abbiamo x = φ(x ) ove

φ(x ) = M

−1

Nx + M

−1

b

.

Viene quindi naturale utilizzare la succ. del metodo di punto fisso

x

(k+1)

= φ(x

(k)

) = M

−1

Nx

(k)

+ M

−1

b.

Esempio A, E, F

Definizione

Sia A = M − N, con M non singolare. Un metodo iterativo le cui

iterazioni sono

x

(k+1)

= φ(x

(k)

) = M

−1

Nx

(k)

+ M

−1

b.

si dice

iterativo stazionario

.

La matrice P = M

−1

N si dice di

matrice iterazione

.

Nota.

Esempio A, E, F

Risulta utile anche scrivere la matrice A come A = D − E − F dove

D `

e una matrice diagonale,

Esempio A, E, F

Esempio

>> A =[1 2 3 4 ; 5 6 7 2 ; 8 9 1 2 ; 3 4 5 1 ] A = 1 2 3 4 5 6 7 2 8 9 1 2 3 4 5 1 >> E=−(t r i l( A )−d i a g(d i a g( A ) ) ) E = 0 0 0 0 −5 0 0 0 −8 −9 0 0 −3 −4 −5 0 >> F=−(t r i u( A )−d i a g(d i a g( A ) ) ) F = 0 −2 −3 −4 0 0 −7 −2 0 0 0 −2 0 0 0 0 >> D=d i a g(d i a g( A ) ) D = 1 0 0 0 0 6 0 0 0 0 1 0 0 0 0 1

Metodo di Jacobi

Definizione (Metodo di Jacobi, 1846)

Sia A = D − E − F ∈ Cn×n dove

D `e una matrice diagonale, non singolare

E `e triangolare inferiore con elementi diagonali nulli, F `e triangolare superiore con elementi diagonali nulli. Fissato x(0)_{∈ C}n_{, ilmetodo di Jacobi´e tale che}

x(k+1)= φ(x(k)) = M−1Nx + M−1b

dove

M = D, N = E + F .

Si vede che la matrice di iterazione P = M−1N `e in questo caso

Metodo di Jacobi

Nota.

Se D `e non singolare il metodo di Jacobi

x(k+1)= φ(x(k)) = D−1(E + F )x(k)+ D−1b pu`o essere descritto comemetodo delle sostituzioni simultanee

x_i(k+1)= (bi− i −1 X j =1 aijx (k) j − n X j =i +1 aijx (k) j )/aii, i = 1, . . . , n. (1) Nota.

Metodo di Jacobi

Vediamo perch`e questa derivazione. Da Ax = b, con A ∈ Cn×n abbiamo X j <i ai ,jxj+ ai ,ixi+ X j >i ai ,jxj= X j ai ,jxj= bi, i = 1, . . . , n

e quindi evidenziando xi, supposto ai ,i 6= 0 deduciamo xi= 1 ai ,i bi− X j <i ai ,jxj+ X j >i ai ,jxj !! , i = 1, . . . , n

Quindi note delle approssimazioni della soluzione x(k)_{= {x}(k)

j } per j = 1, . . . , n `e naturale introdurre il metodo iterativo

x_i(k+1)= 1 ai ,i bi− X j <i ai ,jx_j(k)+ X j >i ai ,jx_j(k) !! , i = 1, . . . , n,

Metodo di Jacobi

Esempio Applicando x_i(k+1)= 1 ai ,i  bi−   X j <i ai ,jx (k) j + X j >i ai ,jx (k) j     , i = 1, . . . , n

al per risolvere problemi Ax = b con A ∈ C3×3_{, otteniamo:} 1 x₁(k+1)= _a1 1,1(b1− a1,2x (k) 2 − a1,3x (k) 3 ); 2 x₂(k+1)= _a1 2,2(b2− a2,1x (k) 1 − a2,3x (k) 3 ); 3 x₃(k+1)= _a1 3,3(b3− a3,1x (k) 1 − a3,2x (k) 2 ). Nota.

Jacobi consider´o un problema Ax = b inserito in Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientium (1809), dove

Metodo di Gauss-Seidel

Definizione (Metodo di Gauss-Seidel, 1823-1874)

Sia A = D − E − F ∈ Cn×n dove

D `e una matrice diagonale, non singolare

E `e triangolare inferiore con elementi diagonali nulli, F `e triangolare superiore con elementi diagonali nulli. Sia fissato x(0)_{∈ C}n_{. Ilmetodo di Gauss-Seidelgenera {x}(k)_}

k con

x(k+1)= φ(x(k)) = M−1Nx(k)+ M−1b

dove

M = D − E , N = F .

Si vede che la matrice di iterazione P = M−1N `e in questo caso

Metodo di Gauss-Seidel

Nota.

Se D `e non singolare il metodo di Gauss-Seidel

x(k+1)= φ(x(k)) = (D − E )−1Fx(k)+ (D − E )−1b pu`o essere descritto comemetodo delle sostituzioni successive

x_i(k+1)= bi− i −1 X j =1 aijx (k+1) j − n X j =i +1 aijx (k) j ! /aii, i = 1, . . . , n. (3) Nota.

Metodo di Gauss-Seidel

Vediamo perch`e questa derivazione. Da Ax = b, con A ∈ Cn×n abbiamo X j <i ai ,jxj+ ai ,ixi+ X j >i ai ,jxj= X j ai ,jxj= bi, i = 1, . . . , n

e quindi evidenziando xi, supposto ai ,i 6= 0 deduciamo xi= 1 ai ,i bi− X j <i ai ,jxj+ X j >i ai ,jxj !! , i = 1, . . . , n

Quindi note delle approssimazioni della soluzione x(k)= {x_j(k)} per j > i , e gi`a calcolate x(k+1)_{= {x}(k+1)

Metodo di Gauss-Seidel

Nota.

Secondo Forsythe:

The Gauss-Seidel method was not known to Gauss and not recommended by Seidel.

Secondo Gauss, in una lettera a Gerling (26 dicembre 1823):

SOR

Definizione (Successive over relaxation, (SOR), 1884-1950

(Frankel-Young))

Sia A = D − E − F ∈ C

n×n

dove

D `

e una matrice diagonale, non singolare

E `

e triangolare inferiore con elementi diagonali nulli,

F `

e triangolare superiore con elementi diagonali nulli.

Sia fissato x

(0)

_{∈ C}

n

_{e ω ∈ C\0. Il}

_{metodo SOR}

_{genera {x}

(k)

_}

SOR

Nota. ((cf.[1, p.555]))

SOR deriva dallo descrivere esplicitamente una iter. di Gauss-Seidel

z_i(k+1)= 1 aii " bi− i −1 X j =1 aijxj(k+1)− n X j =i +1 aijxj(k) #

e sostituirla, per ω ∈ C, con la combinazione

SOR

Per convincersi dell’equivalenza tra formulazione matriciale ed equazione per equazione, osserviamo che

x_i(k+1)= ω aii " bi− i −1 X j =1 aijx_j(k+1)− n X j =i +1 aijx_j(k) # + (1 − ω)x_i(k) diventa x(k+1)= ωD−1[b + Ex(k+1)+ Fx(k)] + (1 − ω)x(k) e dopo noiosi calcoli in cui si evidenziano x(k)e x(k+1)

D ω(I − ωD −1 E )x(k+1)=D ω  ωD−1F + (1 − ω)x(k)+ b da cui, dovendo essere Mx(k+1)_{= Nx}(k)_{+ b,}

M = D ω − E , N = F + 1 − ω ω D =  1 ω− 1  D + F . Nota.

SOR

Nota.

Notiamo che le iterazioni di SOR verificano l’uguaglianza x(k+1)= M−1Nxk+ M−1b con M =D ω − E , N =  1 ω− 1  D + F ed `e M − N = D ω − E  − 1 ω− 1  D + F  = −E + D − F = A. Quindi effettivamente A = M − N. Nota.

I metodi SOR hanno reso possibile la soluzione di alcuni sistemi lineari con oltre 20000 incognite gi`a nel 1960 e perfino di ordine 100000 nel 1965.

I metodi di Richardson stazionari

Definizione (Residuo)

Sia A una matrice quadrata in Cn×n, b ∈ Cn, x ∈ Cn. La quantit`a

r = b − Ax (4)

`e nota comeresiduo(relativamente ad A e b).

Definizione (Metodo di Richardson stazionario, 1910)

Fissato α, un metodo diRichardson stazionario, conmatrice di precondizionamentoP, verifica

P(x(k+1)− x(k)) = αr(k). (5)

dove il residuo alla k-sima iterazione `e

I metodi di Richardson non stazionari

Definizione (Metodo di Richardson non stazionario)

Fissati α

k

dipendenti dalla iterazione k, un metodo di

Richardson

non stazionario

, con

matrice di precondizionamento

P, verifica

P(x

(k+1)

− x

(k)

) = α

k

r

(k)

.

(7)

Nota.

Si osservi che se αk= α per ogni k, allora il metodo di Richardson non stazionario diventa stazionario.

Tipicamente la matrice P viene scelta cosicch`e il la soluzione di P(x(k+1)− x(k)

I metodi di Richardson

I metodi di Jacobi e di Gauss-Seidel, SOR, sono metodi di

Richardson stazionari.

Proposizione.

I metodi del tipo Mx

(k+1)

= Nx

(k)

+ b, con M invertibile e

A = M − N sono di Richardson stazionari con P = M, α = 1.

Dimostrazione.

Sia, come da ipotesi,

Mx

(k+1)

= Nx

(k)

+ b,

(8)

Essendo r

(k)

= b − Ax

(k)

,

I metodi di Richardson

Nota.

Per l’asserto precedente, poich`e i metodi di Jacobi e di Gauss-Seidel, SOR, verificano

M(x(k+1)− x(k)

) = r(k) (10)

necessariamente sono metodi di Richardson stazionari, con α = 1 e matrice di precondizionamento P = M.

I metodi di tipo Richardson x(k+1)_{− x}(k)_{= α(b − Ax}(k)_{) sono spesso} usati cercando di selezionare i parametri α cos`ı da rendere pi`u veloce la convergenza del metodo. Nel caso A = AT, tale parametro ottimale `e

α = 2/(λmin+ λmax).

Norma di matrici

Definizione (Raggio spettrale)

Siano λ1, . . . , λngli autovalori di A ∈ Cn×n. Si definisceraggio spettraledi A

ρ(A) := max i (|λi|)

Definizione (Norma naturale)

Sia k · k : Cn_{→ R}

+ una norma vettoriale. Si definiscenorma naturale(o indotta) di

una matrice A ∈ Cn×n_{la quantit`a}

kAk := sup x ∈Cn_{,x 6=0}

kAxk kxk .

Nota.

Se k · k ´e una norma indotta, si vede facilmente che per A ∈ Cn×n_{si ha}

kAxk ≤ kAkkxk, per ogni x ∈ Cn_;

Norma di matrici

Esempio ([4], p. 24)

Sia x un arbitrario elemento di C

n

, A ∈ C

n×n

.

Norma vettoriale

Norma naturale

kxk

1

:=

P

n_k=1

|x

k

|

kAk

1

= max

j

P

n i =1

|a

i ,j

|

kxk

2

:=

P

n_k=1

|x

k

|

2

1/2

kAk

2

= ρ

1/2

(A

H

A)

kxk

∞

:= max

k

|x

k

|

kAk

∞

= max

i

P

n_{j =1}

|a

i ,j

|

Nota.

Nella norma matriciale 1, di ogni colonna si fanno i moduli di ogni componente e li si somma. Quindi si considera il massimo dei valori ottenuti, al variare della riga.

Norma di matrici

Norma di matrici

Si dimostra che (cf. [4, p.28])

Teorema

Per ogni norma naturale k · k e ogni matrice quadrata A si ha ρ(A) ≤ kAk. Inoltre per ogni matrice A di ordine n e per ogni  > 0 esiste una norma naturale k · k tale che

ρ(A) ≤ kAk ≤ ρ(A) + .

e inoltre, anche per mezzo del teorema precedente e l’equivalenza delle norme, (cf. [4, p.29], [3, p.232])

Teorema (Hensel 1926, Oldenburger 1940, Householder 1958)

Fissata una norma qualsiasi naturale k · k, A ∈ Cn×n _{i seguenti asserti sono} equivalenti

1 Am→ 0 (ovvero kAm_k

∗→ 0 per una certa norma naturale k · k∗); 2 kAm_{k → 0;}

3 ρ(A) < 1.

Sul raggio spettrale

Nota.

Siano {λk}k=1,...,nautovalori di A ∈ Cn×n. Ilraggio spettrale ρ(A) = max

k (|λk|)

non `e una norma. Infatti la matrice 

0 1 0 0



ha raggio spettrale nullo, ma non `e la matrice nulla.

Convergenza dei metodi iterativi stazionari

Definizione (Matrice diagonalizzabile)

Una matrice A ∈ C

n×n

`

e

diagonalizzabile

se e solo C

n

possiede una

base composta di autovettori

di A.

Equivalentemente A ∈ C

n×n

`

e diagonalizzabile se e solo se `

e

simile

ad una matrice diagonale D

, cio`

e esiste S tale che

A = S

−1

DS.

Definizione (Metodo consistente)

Sia A una matrice non singolare e Ax

∗

= b. Il metodo stazionario

x

(k+1)

= Px

(k)

+ c

Convergenza dei metodi iterativi stazionari

Lemma

Sia

x

(k+1)

= Px

(k)

+ c

un metodo iterativo stazionario.

Supponiamo sia consistente, relativamente al problema Ax = b,

cio`

e

Ax

∗

= b implica x

∗

= Px

∗

+ c.

Allora, posto e

(k)

_{= x}

(k)

_{− x}

∗

_{si ha che}

_e

(m)

_{= P}

m

_e

(0)

_.

Dimostrazione.

Basta osservare che

e(m) := x(m)− x∗= (Px(m−1)+ c) − (Px∗+ c) = P(x(m−1)− x∗) = Pe(m−1) e quindi reiterando il ragionamento

Convergenza dei metodi iterativi stazionari

Introduciamo il teorema di convergenza nel caso generale, basato

sul teorema di Hensel.

Teorema

Un metodo iterativo stazionario consistente x

(k+1)

= Px

(k)

+ c,

ove P ∈

C

n×n

, converge per ogni vettore iniziale x

0

∈

C

n

se e solo

se ρ(P) < 1.

Nota.

Si noti che il teorema riguarda la convergenzaper ogni vettore iniziale x0ed `e quindi di convergenza globale.

Convergenza dei metodi iterativi stazionari.

Dimostrazione.

⇐ Sia e

(k)

_{= x}

(k)

_{− x}

∗

_{. Come stabilito dal Teorema che lega}

norme a raggi spettrali, se ρ(P) < 1 e k · k `

e una norma naturale

allora kP

m

_{k → 0 per m → ∞.}

Da

x

(k+1)

= Px

(k)

+ c,

x

∗

= Px

∗

+ c,

per un lemma precedente

e

(k)

= P

k

e

(0)

e quindi essendo k · k una

norma naturale

ke

(k)

k = kP

k

e

(0)

k ≤ kP

k

kke

(0)

k.

(11)

Essendo ρ(P) < 1, abbiamo che kP

k

k → 0 da cui per (11) `

e

ke

(k+1)

_{k → 0 e quindi per le propriet`}

_{a delle norme e}

(k)

_{→ 0 cio`}

_e

Convergenza dei metodi iterativi stazionari.

Dimostrazione.

⇒ Supponiamo che la successione x(k+1)

= Px(k)+ c converga a x∗per qualsiasi x(0)

∈ Cn _{ma che sia ρ(P) ≥ 1. Sia λ}

max∈ Cil massimo autovalore in modulo di P e scegliamo x(0) tale che e(0)= x(0)− x∗

sia autovettore di P relativamente all’autovalore λmax. Essendo

Pe(0)= λmaxe(0), e(k)= Pke(0), abbiamo che e(k) = Pke(0)= Pk−1(Pe(0)) = Pk−1(λmaxe(0)) = λmaxPk−1e(0)= . . . =λkmaxe (0)

da cui, qualsiasi sia la norma naturale k · k, per ogni k = 1, 2, . . . si ha ke(k)_{k = |λ}k

max|Cke

(0)_{k ≥ ke}(0)_k

il che comporta che la successione non `e convergente (altrimenti per qualche k

Convergenza dei metodi iterativi stazionari .

Nota.

Nella prima parte della dimostrazione, in cui abbiamo supposto ρ(P) < 1, abbiamo utilizzato che x∗= Px∗+ c. A priori ci sarebbero problemi se ci fosse un certo ˜x tale che ˜x = P ˜x + c, in quanto si proverebbe similmente che per qualsiasi scelta iniziale si converge pure a ˜x . In realt´a, ci´o non ´e possibile. Posto x0= ˜x , la successione e’ tale che xk= ˜x e pure ˜x → x∗ ovvero ˜x = x∗.

Si osservi che nel precedente teorema, se P ∈ Rn×n_{allora a priori} potrebbe essere

λmax∈C\R,

e pure il suo autovettore potrebbe avere componenti complesse ma non reali.

Di conseguenza la dimostrazione vale se possiamo scegliere

Velocit`

a di convergenza

Proposito.

L’analisi che faremo in questa sezione non `

e rigorosamente

matematica. Ci`

o nonostante permette di capire il legame tra il

raggio spettrale della matrice di iterazione P e la riduzione

dell’errore.

Supponiamo di voler approssimare x

∗

tale che Ax

∗

= b con il

metodo stazionario

x

(k+1)

= Px

(k)

+ c.

Supporremo tale metodo consistente e quindi se Ax

∗

= b allora

x

∗

= Px

∗

+ c

.

Inoltre indicheremo con e

(k)

l’errore

Velocit`

a di convergenza

Da un lemma precedente

e

(m)

=

P

m

e

(0)

.

(12)

Si dimostra che se A ∈ C

n×n

_{e k · k `}

_{e una norma naturale}

allora

lim

m

kA

m

_k

1

m

= ρ(A)

Quindi per m sufficientemente grande si ha kP

m

k

1/m

_{≈ ρ(P)}

Velocit`

a di convergenza

Sotto queste ipotesi, per m sufficientemente grande, da e(m)= Pme(0), kPm_{k ≈ ρ}m_(P), abbiamo ke(m)_{k = kP}m e(0)k ≤ kPm_kke(0)_{k ≈ ρ}m (P)ke(0)k (13) e quindi ke(m)k/ke(0)k / ρm(P). (14) Per cui se

ρm∗(P) = , ovverom∗=_{log (ρ(P))}log() ,

m = dm∗e, ρ(P) < 1, necessariamente ke(m)_k/ke(0) k / ρm (P) ≤ ρm∗(P) = .

Velocit`

a di convergenza

Se

R(P) = − log(ρ(P))

`

e la cosidetta

velocit`

a di convergenza asintotica

del metodo

iterativo stazionario relativo a P abbiamo

m =



log 

log (ρ(P))



=

 − log()

R(P)



.

Se ρ(P) < 1 `

a particolarmente piccolo allora log(ρ(P))  0 e

quindi R(P) = − log(ρ(P))  0 per cui asintoticamente il numero

di iterazioni m per abbattere l’errore di un fattore  sar`

a

particolarmente basso e quindi il metodo

veloce

.

Alcuni teoremi di convergenza

Definizione (Matrice tridiagonale)

Una matrice A si dice

tridiagonale

se A

i ,j

= 0 qualora |i − j | > 1.

Alcuni teoremi di convergenza

Teorema

Per matrici

tridiagonali

A = (a

i ,j

) ∈ C

n×n

con

componenti

diagonali non nulle

,

i metodi di Jacobi e Gauss-Seidel

sono

o entrambi convergenti

o entrambi divergenti.

La velocit`

a di convergenza del metodo di Gauss-Seidel `

e il

doppio

di quello del metodo di Jacobi.

Nota.

Alcune definizioni

Definizione (Matrice a predominanza diagonale)

La matrice A ∈ C

n×n

`

e a

predominanza diagonale

(per righe) se

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

|a

i ,i

| ≥

n

X

j =1,j 6=i

|a

i ,j

|

e per almeno un indice s si abbia

|a

_s,s

| >

n

X

j =1,j 6=s

|a

_s,j

|.

La matrice A = (a

i ,j

) ∈ C

n×n

`

e a predominanza diagonale per

colonne se la matrice hermitiana A

H

= (¯

a

i ,j

) a predominanza

Alcune definizioni

Definizione (Matrice a predom. diagonale in senso stretto)

Se |as,s| > n X j =1,j 6=s |as,j|, s = 1, . . . , n

allora la matrice A ∈ Cn×nsi dice apredominanza diagonale (per righe) in senso stretto.

La matrice A `e apredominanza diagonale (per colonne) in senso strettose AH a predominanza diagonale per righe in senso stretto. Si noti che per il primo teorema di Gerschgorin, ogni matrice a predominanza diagonale in senso stretto ´e non singolare. Ad esempio la matrice A =   4 −4 0 −1 4 −1 0 −4 4  

Teoremi di convergenza

Teorema

Sia A una matrice quadrata a

predominanza diagonale per righe in

senso stretto

. Allora il metodo di

Jacobi converge

alla soluzione di

Ax = b, qualsiasi sia il punto x

(0)

iniziale.

Teorema

Sia A `

e a

predominanza diagonale per righe in senso stretto

. Allora

il metodo di

Gauss-Seidel converge

, qualsiasi sia il punto x

(0)

iniziale.

Tali teoremi valgono anche se A `

e a predominanza diagonale

per colonne in senso stretto.

Alcune definizioni

Definizione (Matrice hermitiana)

La matrice A ∈ C

n×n

`

e

hermitiana

se A = A

H

.

Una matrice A ∈ R

n×n

`

e

simmetrica

se A = A

T

Definizione (Matrice definita positiva)

Una matrice hermitiana A ∈ C

n×n

_`

_e

_{definita positiva}

_{se ha tutti gli}

autovalori positivi.

Alcune definizioni

Esempio

Ad esempio la matrice

A =





4

−1

0

−1

4

−1

0

−1

4





`

e simmetrica e definita positiva. Per convincersene basta vedere

che ha tutti gli autovalori positivi.

Alcuni teoremi di convergenza

Teorema (Kahan, 1958)

Sia A ∈ C

n×n

una matrice quadrata. Condizione necessaria affinch`

e

il metodo SOR converga globalmente alla soluzione di Ax = b `

e

che sia |1 − ω| < 1. Se ω ∈ R in particolare `e che sia ω ∈ (0, 2).

Teorema (Ostrowski (1954)-Reich(1949))

Sia A ∈ C

n×n

simmetrica e definita positiva,

ω ∈ (0, 2).

Allora il metodo SOR converge.

Test di arresto

Problema. (Test di arresto)

Consideriamo il sistema lineare Ax = b avente un’unica soluzione

x

∗

e supponiamo di risolverlo numericamente con un metodo

iterativo stazionario del tipo

x

(k+1)

= Px

(k)

+ c,

che sia consistente cio`

e

x

∗

= Px

∗

+ c.

Test di arresto: criterio dello step

Proposizione. (Stima a posteriori)

Sia Ax = b con A non singolare e x(k+1)_{= Px}(k)_{+ c un metodo iterativo}

Test di arresto: criterio dello step

Fissata dall’utente una tolleranza tol, si desidera interrompere il

processo iterativo quando

kx

∗

− x

(k)

k ≤ tol.

Definizione (Criterio dello step)

Il

criterio dello step

, consiste nell’interrompere il metodo iterativo

che genera la successione {x

(k)

} alla k-sima iterazione qualora

kx

(k+1)

− x

(k)

k ≤ tol

(dove tol `

e una tolleranza fissata dall’utente).

Quindi, da ke(k)_{k := kx}∗

− x(k)_{k ≤} kx(k+1)−x(k)k

Test di arresto: criterio dello step

Analizziamo il caso particolare in cui P sia simmetrica e la norma

sia k · k

2

.

Teorema

Test di arresto: criterio dello step

Nota.

Osserviamo che da ρ(P) ≤ kPk, qualsiasi sia la norma k · k e ke(k)k := kx∗− x(k)k ≤kx

(k+1)_{− x}(k)_k 1 − kPk non consegue direttamente per k · k = k · k2

ke(k)k2:= kx∗− x(k)k2≤

kx(k+1)_{− x}(k)_k 2 1 − ρ(P) in quanto per ogni norma k · k

1 1 − ρ(P)≤

Test di arresto: criterio dello step

Lemma (Facoltativo)

SeP `e simmetrica, allora esistono

una matrice ortogonale U, cio`e tale che UT= U−1, una matrice diagonale a coefficienti reali Λ

per cuiP = UΛUTed essendo P e Λ simili, le matrici P e Λ hanno gli stessi autovalori {λk}k.

Dimostrazione. (Facoltativo)

Dal lemma, se P `e simmetrica, essendokPk₂:= q ρ(PPT_),UT_{U = I} kPk2 = q ρ(PPT) = q ρ(UΛUT(UΛUT)T) = q ρ(UΛUTUΛUT) = q ρ(UΛ2UT) (15)

Essendo UΛ2_UT_{simile a Λ}2_{, UΛ}2_UT_{e Λ}2_{hanno gli stessi autovalori uguali a {λ}2

k}ke di conseguenza lo stesso

raggio spettrale, da cuiρ(UΛ2UT) = ρ(Λ2). Da ρ(UΛ2UT) = ρ(Λ2) ricaviamo kPk₂ = q ρ(Λ2_{) =}r_max k |λ2 k| = r max k |λ_k|2₌r_(max k |λ_k|)2_{= max} k |λ_k| =ρ(P). (16)

Se il metodo stazionario x(k+1)_{= Px}(k)_{+ c `e convergente, per il teorema di convergenza kPk}

2= ρ(P) < 1 e

per la precedente proposizione

ke(k)k₂:= kx∗− x(k)k₂≤kx (k+1)_{− x}(k)_k 2 1 − kPk2 =kx (k+1)_{− x}(k)_k 2 1 − ρ(P) . 4

Test di arresto: criterio del residuo

Definizione (Criterio del residuo)

Ilcriterio del residuo, consiste nell’interrompere il metodo iterativo che genera la successione {x(k)} alla k-sima iterazione qualora

kr(k)k ≤ tol

dove

tol `e una tolleranza fissata dall’utente, r(k)= b − Ax(k).

Definizione (Criterio del residuo relativo)

Si supponga di dover risolvere il sistema lineare Ax = b, con A invertibile e b 6= 0. Ilcriterio del residuo relativo, consiste nell’interrompere il metodo iterativo che genera la successione {x(k)} alla k-sima iterazione qualora

kr(k)_k

Test di arresto: criterio del residuo

Teorema

Sia Ax

∗

= b con A non singolare, b 6= 0 e k · k una norma naturale.

Sia {x

(k)

} la successione generata da un metodo iterativo. Allora

kx

(k)

_{− x}

∗

_k

kx

∗

_k

=

ke

(k)

_k

kx

∗

_k

≤ κ(A)

kr

(k)

_k

kbk

.

dove κ(A) `

e il numero di condizionamento di A.

Nota.

Dal teorema si evince che il criterio del residuo relativo kr_kbk(k)k ≤ tol non offre indicazioni su kx(k)_kx−x∗_k∗k per κ(A)  1.

Test di arresto: criterio del residuo

Dimostrazione.

Se b = Ax∗allora, essendo A invertibile e(k)= x∗− x(k)

= A−1A(x∗− x(k)

) = A−1(b − Ax(k)) = A−1r(k) e quindi, essendo k · k una norma naturale

ke(k)_{k = kA}−1

r(k)k ≤ kA−1kkr(k)_k.

Inoltre, poich`e b = Ax∗abbiamo kbk = kAx∗k ≤ kAkkx∗_{k e quindi}

1 kx∗_k≤

kAk kbk.

I metodi di discesa

Sia

A una matrice simmetrica definita positiva

.

Si osserva che se x

∗

`

e l’unica soluzione di Ax = b allora `

e pure il

minimo del

funzionale dell’energia

φ(x ) =

1

2

x

T

_{Ax − b}

T

_{x , x ∈ R}

n

in quanto

I metodi di discesa

Un generico

metodo di discesa

consiste nel generare una

successione

x

(k+1)

= x

(k)

+ α

k

p

(k)

dove p

(k)

`

e una direzione fissata secondo qualche criterio.

Lo scopo ovviamente `

e che

φ(x

(k+1)

) < φ(x

(k)

),

I metodi di discesa

Definizione (Metodo del gradiente classico, Cauchy 1847)

Il metodo delgradiente classico`e un metodo di discesa

x(k+1)= x(k)+ αkp(k)

con αk e p(k)scelti cos`ı da ottenere la massima riduzione del funzionale dell’energia a partire dal punto x(k)_.

Differenziandoφ(x ) = 1 2x

T_{Ax − b}T

x , x ∈ Rn_{si mostra che tale scelta}

coincide con lo scegliere

p(k)= r(k), αk=

kr(k)_k2 2

(r(k)₎T_Ar(k). (17)

Nota.

Con qualche facile conto si vede che `e unmetodo di Richardson non stazionario

Il metodo del gradiente: propriet`

a

Teorema

Se

A `

e simmetrica e definita positiva,

kxk

_A

=

√

x

T

_{Ax ,}

e

(k)

= x

∗

− x

(k)

_{, con x}

(k)

_{iterazione del gradiente classico,}

Il metodo del gradiente: propriet`

a

Nota.

Questo risultato stabilisce che la convergenza del gradiente `e lenta qualora si abbiano alti numeri di condizionamento

κ2(A) := kAk2kA−1k2=

maxi|λi| minj|λj|

, {λi} = spettro(A). Postoµg(x ) =x −1_{x +1} abbiamo ad esempio

µg(10) ≈ 0.8182, µg(1000) ≈ 0.9980, µg(100000) ≈ 0.99998. Cos´ı affinch´eκ2(A)−1

κ2(A)+1

k

< , necessita k(κ2(A)) = dlog()/ log(µg(κ2(A)))e. Per  = 10−6, si ha in particolare

Il metodo del gradiente coniugato.

Definizione (Gradiente coniugato, Hestenes-Stiefel, 1952)

Il metodo del

gradiente coniugato

`

e un metodo di discesa

x

(k+1)

= x

(k)

+ α

k

p

(k)

con

α

k

=

(r (k)₎T_r(k) (p(k)₎T_Ap(k)

,

p

(0)

= r

(0)

,

p

(k)

= r

(k)

+ β

k

p

(k−1)

, k = 1, 2, . . .

β

k

=

(r (k)₎T_r(k) (r(k−1)₎T_r(k−1)

=

kr(k)_k2 2 kr(k−1)_k2 2

.

Il metodo del gradiente coniugato

Nota.

Hestenes was working at the I.N.A. at UCLA. In June and early July 1951, he derived the conjugate gradient algorithm.

When, in August, Stiefel arrived at I.N.A. from Switzerland for a congress, the librarian gave him the routine written by Hestenes. Shortly after, Stiefel came to Hestenes office and said about the paper ”this is my talk!”.

Indeed, Stiefel had invented the same algorithm from a different point of view. So they decided to write a joint paper from a different point of view.

Nota. (Saad, van der Vorst)

Il metodo del gradiente coniugato: propriet`

a

Il metodo del gradiente coniugato ha molte propriet`

a particolari.

Ne citiamo alcune.

Teorema

Se A `

e una matrice simmetrica e definita positiva di ordine n,

allora il metodo del gradiente coniugato `

e convergente e fornisce in

aritmetica esatta la soluzione del sistema Ax = b in al massimo n

iterazioni.

Questo teorema tradisce un po’ le attese, in quanto

Il metodo del gradiente coniugato: propriet`

a

Definizione (Spazio di Krylov)

Lo spazio

Kk= span(r(0), Ar(0), . . . , Ak−1r(0)) per k ≥ 1 si dicespazio di Krylov.

Osserviamo che per quanto concerne il gradiente coniugato x(k+1)= x(k)+ αkp(k), p(k)= r(k)+ βkp(k−1) con p(0)_{= r}(0)_{, denotato x}(0)_{+ K} k= {x ∈ Rn: x = x(0)+ t, t ∈ Kk}, x(0)∈ x(0) + K0, supposto K0= ∅; x(1)_{= x}(0)_{+ α} 0p(0)= x(0)+ α0r(0)∈ x(0)+ K1; r(1)= b − Ax(1)= b − Ax(0)− α0Ar(0)= r(0)− α0Ar(0)∈ K2; x(2)_{= x}(1)_{+ α} 1p(1)= x(1)+ α1(r(1)+ β1p(0)) = x(1)+ α1(r(1)+ β1r(0)) ∈ x(0)+ K2; x(k)∈ x(0)

Il metodo del gradiente coniugato: propriet`

a

Teorema ([7, p.12])

Sia

Kk = span(r(0), Ar(0), . . . , Ak−1r(0))

per k ≥ 1. Allora la k-sima iterata dal metodo del gradiente coniugato, minimizza il funzionale φ nell’insieme x(0)_{+ K}

k.

Si osservi che essendo la k-sima iterazione del gradiente classico pure in x(0)_{+ K}

k, ilgradiente classico in generale non minimizzail

funzionale φ in x(0)_{+ K} k.

SeKnha dimensione n, visto che conseguentemente Kn= Rn, si ha

che x∗ ∈ Rn_{, soluzione di Ax}∗_{= b, appartiene a x}(0)_{+ K}

n= Rn ed

`

e l’unico minimo del funzionale dell’energia, come pure l’iterazione x(n)del gradiente coniugato. Quindi x(n)= x∗.

Si dimostra che seKnha dimensione minore di n allora il gradiente

Il metodo del gradiente coniugato: propriet`

a

Teorema

Se

A `

e simmetrica e definita positiva,

kxk

_A

=

√

x

T

_{Ax ,}

e

(k)

= x

∗

− x

(k)

_{, con x}

(k)

_{iterazione del gradiente coniugato}

Il metodo del gradiente coniugato: propriet`

a

Nota.

Questo risultato stabilisce che la convergenza del gradiente coniugato `e lenta qualora si abbiano alti numeri di condizionamento

κ2(A) := kAk2kA −1 k2= maxi|λi| minj|λj| , {λi} = spettro(A). Posto µcg(x ) = √ x − 1 √ x + 1 abbiamo ad esempio µcg(10) ≈ 0.5195, µcg(1000) ≈ 0.9387, µcg(100000) ≈ 0.9937.

Il metodo del gradiente coniugato: propriet`

a

Affinch´e 2  √ κ2(A)−1 √ κ2(A)+1 k

< , serve k(κ2(A)) = dlog(/2)/ log(µcg(κ2(A)))e. Per  = 10−6, si ha in particolare nel caso del gradiente coniugato

k(10) = 23, k(1000) = 230, k(100000) = 2295,

da paragonarsi con simili risultati gi´a ottenuti da stime col metodo del gradiente classico

Bibliografia

K. Atkinson, Introduction to Numerical Analysis, Wiley, 1989. K. Atkinson e W. Han, Theoretical Numerical Analysis, Springer, 2001.

D. Bini, M. Capovani e O. Menchi, Metodi numerici per l’algebra lineare, Zanichelli, 1988. V. Comincioli, Analisi Numerica, metodi modelli applicazioni, Mc Graw-Hill, 1990. S.D. Conte e C. de Boor, Elementary Numerical Analysis, 3rd Edition, Mc Graw-Hill, 1980.