Convergenza del metodo di Jacobi e Gauss-Seidel per matrici tridiagonali.

Metodi iterativi per la soluzione di sistemi lineari ¹

A. Sommariva

²

Keywords: Metodi iterativi stazionari. Metodo di Jacobi. Gauss-Seidel. SOR. Metodi di Richardson. Legame tra metodi di Richardson stazionari e metodi iterativi

stazionari. Norme di matrici e loro proprieta’. Teorema di convergenza di un metodo iterativo stazionario, caso generale (con dimostrazione). Velocit`a di convergenza.

Convergenza del metodo di Jacobi e Gauss-Seidel per matrici tridiagonali.

Convergenza del metodo di Jacobi e Gauss-Seidel per matrici a predominanza diagonale. Teorema di Kahan (condizione convergenza SOR). Convergenza dei metodi SOR per matrici simmetriche. Test dello step. (e sua breve analisi). Test del residuo (e sua breve analisi). Metodi del gradiente. Metodo del gradiente classico.

Stima dell’errore del gradiente classico. Metodo del gradiente coniugato. Spazi di Krylov e gradiente coniugato. Stima dell’errore del gradiente coniugato.

Revisione: 11 maggio 2021

1. Metodi iterativi e diretti

Supponiamo che siano A ∈ C

^n×n

(matrice non singolare), b ∈ C

ⁿ

(vettore colon- na). Bisogna risolvere il problema Ax = b avente sol. unica x

^∗

.

Si pu`o utilizzare la fattorizzazione LU con pivoting, il cui costo computaziona- le `e in generale di O(n

³

/3) operazioni moltiplicative, che diventa proibitivo se n `e particolarmente elevato.

In tal senso, sia A una matrice invertibile. Allora P A = LU dove

• P `e una matrice di permutazione,

• L `e una matrice triangolare inferiore a diagonale unitaria (l

_ii

= 1, ∀i),

• U una matrice triangolare superiore.

Se Ax = b, determinata P A = LU , per risolvere Ax = b da Ax = b ⇔ P Ax = P b ⇔ LU x = P b

si risolve prima Ly = P b e detta y

^∗

la soluzione, si determina x

^∗

tale che U x

^∗

= y

^∗

.

• 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, acconten- tandosi di poche iterazioni ognuna dal costo quadratico (tipicamente quello di un prodotto matrice-vettore).

Il costo totale sar`a O(¯ k · n

²

) da paragonarsi con O(n

³

/3) della eliminazione gaussiana con pivoting.

2. 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 ⇔ M x − N x = b ⇔ M x = N x + b ⇔ x = M

⁻¹

N x + M

⁻¹

b e quindi abbiamo x = φ(x) ove φ(x) = M

⁻¹

N x + M

⁻¹

b.

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

^(k+1)

= φ(x

^(k)

) = M

⁻¹

N x

^(k)

+ M

⁻¹

b.

La matrice P = M

⁻¹

N si dice di iterazione e non dipende, come pure b dall’indice di iterazione k. Per questo motivo tali metodi si chiamano iterativi stazionari.

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

x

^(k+1)

= φ(x

^(k)

) = M

⁻¹

N x

^(k)

+ M

⁻¹

b.

si dice iterativo stazionario.

La matrice P = M

⁻¹

N si dice di matrice iterazione.

Nota. Si osservi che la matrice di iterazione M

⁻¹

N come pure M

⁻¹

b non dipen- dono dall’indice di iterazione k.

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

• D `e una matrice diagonale,

• E `e triangolare inferiore con elementi diagonali nulli,

• F `e triangolare superiore con elementi diagonali nulli.

• E’ immediato osservato che tale scrittura esiste ed `e unica.

• Tramite questo splitting di matrici descriveremo i metodi iterativi stazionari pi`u

noti e sar`a particolarmente semplice la loro implementazione su computer.

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=-(tril(A)-diag(diag(A))) E =

0 0 0 0

-5 0 0 0

-8 -9 0 0

-3 -4 -5 0

>> F=-(triu(A)-diag(diag(A))) F =

0 -2 -3 -4

0 0 -7 -2

0 0 0 -2

0 0 0 0

>> D=diag(diag(A)) D =

1 0 0 0

0 6 0 0

0 0 1 0

0 0 0 1

>>% A=diag(diag(A))-E-F.

2.1. Metodo di Jacobi

Definizione 2.2 (Metodo di Jacobi, 1846). 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.

Fissato x

⁽⁰⁾

∈ C

ⁿ

, il metodo di Jacobi ´e tale che

x

^(k+1)

= φ(x

^(k)

) = M

⁻¹

N x + M

⁻¹

b dove

M = D, N = E + F.

Si vede che la matrice di iterazione P = M

⁻¹

N `e in questo caso

P = M

⁻¹

N = D

⁻¹

(E + F ) = D

⁻¹

(D − D + E + F ) = I − D

⁻¹

A.

Nota. Se D `e non singolare il metodo di Jacobi

x

^(k+1)

= φ(x

^(k)

) = D

⁻¹

(E + F )x

^(k)

+ D

⁻¹

b pu`o essere descritto come metodo delle sostituzioni simultanee

x

^(k+1)_i

= (b

i

−

i−1

X a

ij

x

^(k)_j

−

n

X a

ij

x

^(k)_j

)/a

ii

, i = 1, . . . , n. (1)

Nota. Si osservi che se D `e non singolare, ovviamente a

i,i

6= 0 per ogni indice i e quindi la successione `e ben definita.

Vediamo perch`e questa derivazione. Da Ax = b, con A ∈ C

^n×n

abbiamo X

j<i

a

i,j

x

j

+ a

i,i

x

i

+ X

j>i

a

i,j

x

j

= X

j

a

i,j

x

j

= b

i

, i = 1, . . . , n

e quindi evidenziando x

i

, supposto a

i,i

6= 0 deduciamo

x

i

= 1 a

i,i



b

i

−



 X

j<i

a

i,j

x

j

+ X

j>i

a

i,j

x

j







 , 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

^(k+1)_i

= 1 a

i,i



b

_i

−



 X

j<i

a

_i,j

x

^(k)_j

+ X

j>i

a

_i,j

x

^(k)_j







 , i = 1, . . . , n,

che si vede facilmente essere il metodo di Jacobi.

Esempio. Applicando

x

^(k+1)_i

= 1 a

i,i



b

i

−



 X

j<i

a

i,j

x

^(k)_j

+ X

j>i

a

i,j

x

^(k)_j







 , i = 1, . . . , n

al per risolvere problemi Ax = b con A ∈ C

^3×3

, otteniamo:

1. x

^(k+1)₁

=

_a¹

1,1

(b

1

− a

1,2

x

^(k)₂

− a

1,3

x

^(k)₃

);

2. x

^(k+1)₂

=

_a¹

2,2

(b

2

− a

2,1

x

^(k)₁

− a

2,3

x

^(k)₃

);

3. x

^(k+1)₃

=

_a¹

3,3

(b

3

− a

3,1

x

^(k)₁

− a

3,2

x

^(k)₂

).

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

A =





27 6 0

6 15 1

0 1 54



 , b =



 88 70 107



 .

2.2. Metodo di Gauss-Seidel

Definizione 2.3 (Metodo di Gauss-Seidel, 1823-1874). 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

⁽⁰⁾

∈ C

ⁿ

. Il metodo di Gauss-Seidel genera {x

^(k)

}

k

con x

^(k+1)

= φ(x

^(k)

) = M

⁻¹

N x

^(k)

+ M

⁻¹

b dove

M = D − E, N = F.

Si vede che la matrice di iterazione P = M

⁻¹

N `e in questo caso

P = M

⁻¹

N = (D − E)

⁻¹

F. (2)

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

x

^(k+1)

= φ(x

^(k)

) = (D − E)

⁻¹

F x

^(k)

+ (D − E)

⁻¹

b pu`o essere descritto come metodo delle sostituzioni successive

x

^(k+1)_i

=



b

i

−

i−1

X

j=1

a

ij

x

^(k+1)_j

−

n

X

j=i+1

a

ij

x

^(k)_j



 /a

ii

, i = 1, . . . , n. (3)

Nota. Si osservi che se D `e non singolare, ovviamente a

i,i

6= 0 per ogni indice i e quindi la successione `e ben definita.

Vediamo perch`e questa derivazione. Da Ax = b, con A ∈ C

^n×n

abbiamo X

j<i

a

_i,j

x

_j

+ a

_i,i

x

_i

+ X

j>i

a

_i,j

x

_j

= X

j

a

_i,j

x

_j

= b

_i

, i = 1, . . . , n

e quindi evidenziando x

i

, supposto a

i,i

6= 0 deduciamo

x

i

= 1 a

i,i



b

i

−



 X

j<i

a

i,j

x

j

+ X

j>i

a

i,j

x

j







 , i = 1, . . . , n

Quindi note delle approssimazioni della soluzione x

^(k)

= {x

^(k)_j

} per j > i, e gi`a calcolate x

^(k+1)

= {x

^(k+1)_j

} per j < i `e naturale introdurre il metodo iterativo

x

^(k+1)_i

= 1 a

i,i



b

i

−



 X

j<i

a

i,j

x

^(k+1)_j

+ X

j>i

a

i,j

x

^(k)_j







 , i = 1, . . . , n.

Esempio. Applicando

x

^(k+1)_i

= 1 a

i,i



b

i

−



 X

j<i

a

i,j

x

^(k+1)_j

+ X

j>i

a

i,j

x

^(k)_j







 , i = 1, . . . , n

al caso di A ∈ C

^3×3

, otteniamo:

1. x

^(k+1)₁

=

_a¹

1,1

(b

1

− a

1,2

x

^(k)₂

− a

1,3

x

^(k)₃

);

2. x

^(k+1)₂

=

_a¹

2,2

(b

2

− a

2,1

x

^(k+1)₁

− a

2,3

x

^(k)₃

);

3. x

^(k+1)₃

=

_a¹

3,3

(b

₃

− a

3,1

x

^(k+1)₁

− a

3,2

x

^(k+1)₂

);

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):

One could do this even half asleep or one could think of other things during the computations.

2.3. SOR

Definizione 2.4 (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

⁽⁰⁾

∈ C

ⁿ

e ω ∈ C\0. Il metodo SOR genera {x

^(k)

}

k

con x

^(k+1)

= φ(x

^(k)

) = M

⁻¹

N x

^(k)

+ M

⁻¹

b dove

M = D

ω − E, N =  1 ω − 1

 D + F

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

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

z

^(k+1)_i

= 1 a

_ii



b

i

−

i−1

X

j=1

a

ij

x

^(k+1)_j

−

n

X

j=i+1

a

ij

x

^(k)_j





e sostituirla, per ω ∈ C, con la combinazione

x

^(k+1)_i

= ωz

_i^(k+1)

+ (1 − ω)x

^(k)_i

. cio`e

x

^(k+1)_i

= ω a

ii



b

i

−

i−1

X

j=1

a

ij

x

^(k+1)_j

−

n

X

j=i+1

a

ij

x

^(k)_j



 + (1 − ω)x

^(k)_i

.

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

x^(k+1)_i = ω aii



b_i−

i−1

X

j=1

aijx^(k+1)_j −

n

X

j=i+1

aijx^(k)_j



 + (1 − ω)x

(k) i

diventa

x^(k+1)= ωD⁻¹[b + Ex^(k+1)+ F x^(k)] + (1 − ω)x^(k) e dopo noiosi calcoli in cui si evidenziano x^(k)e x^(k+1)

D

ω(I − ωD⁻¹E)x^(k+1)=D

ω ωD⁻¹F + (1 − ω)
x^(k)+ b da cui, dovendo essere M x^(k+1)= N x^(k)+ b,

M =D

ω − E, N = F +1 − ω ω D = 1

ω− 1

 D + F.

Nota. Gauss-Seidel `e SOR in cui si `e scelto ω = 1.

Nota. Notiamo che le iterazioni di SOR verificano l’uguaglianza x

^(k+1)

= M

⁻¹

N x

^k

+ M

⁻¹

b

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.

• Il loro utilizzo `e stato costante fino al 1980, quando metodi pi`u potenti sono stati

introdotti per i problemi pi`u comuni della modellistica matematica.

3. I metodi di Richardson stazionari

Definizione 3.1 (Residuo). Sia A una matrice quadrata in C

^n×n

, b ∈ C

ⁿ

, x ∈ C

ⁿ

. La quantit`a

r = b − Ax (4)

`e nota come residuo (relativamente ad A e b).

Definizione 3.2 (Metodo di Richardson stazionario, 1910). Fissato α, un metodo di Richardson stazionario, con matrice di precondizionamento P , verifica

P (x

^(k+1)

− x

^(k)

) = αr

^(k)

. (5)

dove il residuo alla k-sima iterazione `e

r

^(k)

= b − Ax

^(k)

. (6)

Definizione 3.3 (Metodo di Richardson non stazionario). Fissati α

k

dipendenti dal- la iterazione k, un metodo di Richardson non stazionario, con matrice di precondi- zionamento 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 stazio- nario diventa stazionario.

• Tipicamente la matrice P viene scelta cosicch`e il la soluzione di P (x

^(k+1)

− x

^(k)

) = α

k

r

^(k)

non sia computazionalmente costosa. Ad esempio, P diagonale o triangolare.

I metodi di Jacobi e di Gauss-Seidel, SOR, sono metodi di Richardson stazionari.

Proposizione 3.4. I metodi del tipo M x

^(k+1)

= N x

^(k)

+ b, con M invertibile e A = M − N sono di Richardson stazionari con P = M , α = 1.

Sia, come da ipotesi,

M x

^(k+1)

= N x

^(k)

+ b, (8)

Essendo r

^(k)

= b − Ax

^(k)

,

M (x

^(k+1)

− x

^(k)

) = N x

^(k)

+ b − M x

^(k)

= b − Ax

^(k)

= r

^(k)

. (9)

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 = A

^T

, tale parametro ottimale `e α = 2/(λ

_min

+ λ

_max

).

• Per quanto riguarda i metodi di Richardson precondizionati e non stazionari, un classico esempio `e il metodo del gradiente classico che vedremo in seguito.

4. Norma di matrici

Definizione 4.1 (Raggio spettrale). Siano λ

₁

, . . . , λ

_n

gli autovalori di A ∈ C

^n×n

. Si definisce raggio spettrale di A

ρ(A) := max

i

(|λ

i

|)

Definizione 4.2 (Norma naturale). Sia k · k : C

ⁿ

→ R

+

una norma vettoriale. Si definisce norma naturale (o indotta) di una matrice A ∈ C

^n×n

la quantit`a

kAk := sup

x∈Cⁿ,x6=0

kAxk kxk .

Nota.

• Se k · k ´e una norma indotta, si vede facilmente che per A ∈ C

^n×n

si ha kAxk ≤ kAkkxk, per ogni x ∈ C

ⁿ

;

• La definizione di norma indotta coincide con quella di norma di un operatore lineare e continuo in spazi normati.

Esempio. [[4], p. 24]

Sia x un arbitrario elemento di C

ⁿ

, A ∈ C

^n×n

.

Norma vettoriale Norma naturale kxk

₁

:= P

n

k=1

|x

_k

| kAk

₁

= max

_j

P

n i=1

|a

_i,j

| kxk

2

:= P

n

k=1

|x

k

|

²

^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.

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

Per quanto riguarda un esempio chiarificatore in Matlab/Octave

>> A=[1 5; 7 13]

A =

1 5

7 13

>>norm(A,1) ans =

18

>>norm(A,inf) ans =

20

>>norm(A,2) ans =

15.5563

>>eig(A*A’) ans =

2 242

>>sqrt(242) ans =

15.5563

>> raggio_spettrale_A=max(abs(eig(A))) raggio_spettrale_A =

15.4261

>>

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

Teorema 4.3. 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 4.4 (Hensel 1926, Oldenburger 1940, Householder 1958). Fissata una nor- ma qualsiasi naturale k · k, A ∈ C

^n×n

i seguenti asserti sono equivalenti

1. A

^m

→ 0 (ovvero kA

^m

k

_∗

→ 0 per una certa norma naturale k · k

_∗

);

2. kA

^m

k → 0;

3. ρ(A) < 1.

Si noti che nel teorema precedente non si richiede che kAk < 1.

4.1. Sul raggio spettrale Nota.

• Siano {λ

k

}

k=1,...,n

autovalori di A ∈ C

^n×n

. Il raggio 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.

• Osserviamo che dagli esempi il raggio spettrale di una matrice A non coincide in generale con la norma 1, 2, ∞, ma che a volte ρ(A) = kAk

2

come nel caso di una matrice diagonale A (essendo gli autovalori di una matrice diagonale, proprio i suoi elementi diagonali).

5. Convergenza dei metodi iterativi stazionari

Definizione 5.1 (Matrice diagonalizzabile). Una matrice A ∈ C

^n×n

`e diagonalizza- bile se e solo C

ⁿ

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

⁻¹

DS.

Definizione 5.2 (Metodo consistente). Sia A una matrice non singolare e Ax

^∗

= b.

Il metodo stazionario

x

^(k+1)

= P x

^(k)

+ c

si dice consistente relativamente al problema Ax = b se e solo se x

^∗

= P x

^∗

+ c.

Lemma 5.3. Sia x

^(k+1)

= P x

^(k)

+ c un metodo iterativo stazionario. Supponiamo sia consistente, relativamente al problema Ax = b, cio`e

Ax

^∗

= b implica x

^∗

= P x

^∗

+ c.

Allora, posto e

^(k)

= x

^(k)

− x

^∗

si ha che e

^(m)

= P

^m

e

⁽⁰⁾

.

Basta osservare che

e

^(m)

:= x

^(m)

− x

^∗

= (P x

^(m−1)

+ c) − (P x

^∗

+ c) = P (x

^(m−1)

− x

^∗

) = P e

^(m−1)

e quindi reiterando il ragionamento

e

^(m)

= P e

^(m−1)

= P (P e

^(m−2)

) = P

²

e

^(m−2)

= . . . = P

^m

e

⁽⁰⁾

.

Introduciamo il teorema di convergenza nel caso generale, basato sul teorema di Hensel.

Teorema 5.4. Un metodo iterativo stazionario consistente x

^(k+1)

= P x

^(k)

+ c, ove P ∈ C

^n×n

, converge per ogni vettore iniziale x

0

∈ C

ⁿ

se e solo se ρ(P ) < 1.

Nota.

• Si noti che il teorema riguarda la convergenza per ogni vettore iniziale x

₀

ed `e quindi di convergenza globale.

• Non si richiede che la matrice P sia diagonalizzabile.

⇐ 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)

= P x

^(k)

+ c,

• x

^∗

= P x

^∗

+ c,

per un lemma precedente e

^(k)

= P

^k

e

⁽⁰⁾

e quindi essendo k · k una norma naturale ke

^(k)

k = kP

^k

e

⁽⁰⁾

k ≤ kP

^k

kke

⁽⁰⁾

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 x

^(k)

→ x

^∗

.

Dimostrazione. ⇒ Supponiamo che la successione x

^(k+1)

= P x

^(k)

+ c converga a x

^∗

per qualsiasi x

⁽⁰⁾

∈ C

ⁿ

ma che sia ρ(P ) ≥ 1. Sia λmax∈ C il massimo autova- lore in modulo di P e scegliamo x

⁽⁰⁾

tale che e

⁽⁰⁾

= x

⁽⁰⁾

− x

^∗

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

• P e

⁽⁰⁾

= λmaxe

⁽⁰⁾

,

• e

^(k)

= P

^k

e

⁽⁰⁾

,

abbiamo che

e

^(k)

= P

^k

e

⁽⁰⁾

= P

^k−1

(P e

⁽⁰⁾

) = P

^k−1

(λmaxe

⁽⁰⁾

)

= λmaxP

^k−1

e

⁽⁰⁾

= . . . = λ

^k

maxe

⁽⁰⁾

da cui, qualsiasi sia la norma naturale k · k, per ogni k = 1, 2, . . . si ha ke

^(k)

k = |λ

^k

max|

C

ke

⁽⁰⁾

k ≥ ke

⁽⁰⁾

k

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

^(k)

< e

⁽⁰⁾

).

Nota.

• Nella prima parte della dimostrazione, in cui abbiamo supposto ρ(P ) < 1, ab- biamo utilizzato che x

^∗

= P x

^∗

+ 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 x

0

= ˜ x, la successione e’ tale che x

k

= ˜ x e pure ˜ x → x

^∗

ovvero ˜ x = x

^∗

.

• Si osservi che nel precedente teorema, se P ∈ R

^n×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 arbitrariamente il vettore iniziale in C

ⁿ

, mentre non basta se possiamo scegliere il vettore solo in R

ⁿ

.

5.1. Velocit`a di convergenza

Proposito. 5.1. L’analisi che faremo in questa sezione non `e rigorosamente matema- tica. 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)

= P x

^(k)

+ c.

Supporremo tale metodo consistente e quindi se Ax

^∗

= b allora x

^∗

= P x

^∗

+ c.

Inoltre indicheremo con e

^(k)

l’errore

e

^(k)

= x

^(k)

− x

^∗

.

• Da un lemma precedente

e

^(m)

= P

^m

e

⁽⁰⁾

. (12)

• Si dimostra che se A ∈ C

^n×n

e k · k `e una norma naturale allora lim

m

kA

^m

k

^m1

= ρ(A)

Quindi per m sufficientemente grande si ha kP

^m

k

^1/m

≈ ρ(P ) ovvero kP

^m

k ≈ ρ

^m

(P ).

Sotto queste ipotesi, per m sufficientemente grande, da

• e

^(m)

= P

^m

e

⁽⁰⁾

,

• kP

^m

k ≈ ρ

^m

(P ), abbiamo

ke

^(m)

k = kP

^m

e

⁽⁰⁾

k ≤ kP

^m

kke

⁽⁰⁾

k ≈ ρ

^m

(P )ke

⁽⁰⁾

k (13) e quindi

ke

^(m)

k/ke

⁽⁰⁾

k / ρ

^m

(P ). (14)

Per cui se

• ρ

^m∗

(P ) = , ovvero m

^∗

=

log (ρ(P ))^log()

,

• m = dm

^∗

e,

• ρ(P ) < 1, necessariamente

ke

^(m)

k/ke

⁽⁰⁾

k / ρ

^m

(P ) ≤ ρ

^m∗

(P ) = .

Quindi per avere una riduzione dell’errore ke

⁽⁰⁾

k di un fattore , servono asintoti- camente (circa) al pi´u m iterazioni.

Se

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

`e la cosidetta velocit`a di convergenza asintotica del metodo iterativo stazionario rela- tivo 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.

Si desidera quindi cercare metodi con ρ(P ) pi`u piccolo possibile cio`e R(P ) il pi`u

grande possibile.

Definizione 5.5 (Matrice tridiagonale). Una matrice A si dice tridiagonale se A

i,j

= 0 qualora |i − j| > 1.

Esempio:













1 2 0 0 0

1 5 7 0 0

0 2 0 9 0

0 0 4 4 2

0 0 0 5 3













5.2. Alcuni teoremi di convergenza

Teorema 5.6. 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. Questo significa vuol dire che asintoticamente sono necessarie met`a ite- razioni del metodo di Gauss-Seidel per ottenere la stessa precisione del metodo di Jacobi.

Definizione 5.7 (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,j6=i

|a

i,j

|

e per almeno un indice s si abbia

|a

s,s

| >

n

X

j=1,j6=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 diagonale per righe, ove ¯ z = a − ib qualora z = a + ib.

Definizione 5.8 (Matrice a predom. diagonale in senso stretto). Se

|a

s,s

| >

n

X

j=1,j6=s

|a

s,j

|, s = 1, . . . , n

allora la matrice A ∈ C

^n×n

si dice a predominanza diagonale (per righe) in senso

stretto.

• La matrice A `e a predominanza diagonale (per colonne) in senso stretto se A

^H

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





`e a predominanza diagonale per righe (non stretta).

Teorema 5.9. 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

⁽⁰⁾

iniziale.

Teorema 5.10. Sia A `e a predominanza diagonale per righe in senso stretto. Allora il metodo di Gauss-Seidel converge, qualsiasi sia il punto x

⁽⁰⁾

iniziale.

• Tali teoremi valgono anche se A `e a predominanza diagonale per colonne in senso stretto.

• Si basano sul teorema di convergenza dei metodi iterativi stazionari.

Definizione 5.11 (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 5.12 (Matrice definita positiva). Una matrice hermitiana A ∈ C

^n×n

`e definita positiva se ha tutti gli autovalori positivi.

Equivalentemente una matrice hermitiana A `e definita positiva se x

^H

Ax > 0, per ogni x ∈ C

ⁿ

6= 0.

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 autova- lori positivi.

>> A=[4 -1 0; -1 4 -1; 0 -1 4];

>>eig(A) % AUTOVALORI DI A.

ans = 2.5858 4.0000 5.4142

>>

Teorema 5.13 (Kahan, 1958). Sia A ∈ C

^n×n

una matrice quadrata. Condizione ne- cessaria 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 5.14 (Ostrowski (1954)-Reich(1949)). Sia A ∈ C

^n×n

• simmetrica e definita positiva,

• ω ∈ (0, 2).

Allora il metodo SOR converge.

Per una dimostrazione si veda [3, p. 263].

6. Test di arresto

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

^∗

e supponia- mo di risolverlo numericamente con un metodo iterativo stazionario del tipo

x

^(k+1)

= P x

^(k)

+ c, che sia consistente cio`e

x

^∗

= P x

^∗

+ c.

Desideriamo introdurre un test di arresto che interrompa le iterazioni, qualora una certa quantit`a relativa al sistema lineare Ax = b e alle iterazioni eseguite, sia al di sotto di una tolleranza  > 0 fissata dall’utente.

6.1. Test di arresto: criterio dello step

Proposizione 6.1 (Stima a posteriori). Sia Ax = b con A non singolare e x

^(k+1)

= P x

^(k)

+ c un metodo iterativo stazionario consistente, con kP k < 1, ove k · k ´e una norma naturale. Allora

ke

^(k)

k := kx

^∗

− x

^(k)

k ≤ 1

1 − kP k · kx

^(k+1)

− x

^(k)

k.

Posto ∆

^(k)

:= x

^(k+1)

− x

^(k)

e e

^(k)

= x

^∗

− x

^(k)

, essendo e

^(k)

= P e

^(k−1)

abbiamo

ke

^(k)

k = kx

^∗

− x

^(k)

k = k(x

^∗

− x

^(k+1)

) + (x

^(k+1)

− x

^(k)

)k

= ke

^(k+1)

+ ∆

^(k)

k = kP e

^(k)

+ ∆

^(k)

k≤ kP k · ke

^(k)

k + k∆

^(k)

k da cui

(1 − kP k)ke

^(k)

k ≤ k∆

^(k)

k ⇔ ke

^(k)

k := kx

^∗

− x

^(k)

k ≤ kx

^(k+1)

− x

^(k)

k

1 − kP k .

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

kx

^∗

− x

^(k)

k ≤ tol.

Definizione 6.2 (Criterio dello step). Il criterio dello step, consiste nell’interrompe- re 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)_{1−kP k}^−x(k)k

, se kP k  1 allora il criterio dello step, se verificato, implica che la soluzione `e probabilmente approssimata a meno della tolleranza prefissata.

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

2

. Teorema 6.3. Sia Ax

^∗

= b con A non singolare e x

^(k+1)

= P x

^(k)

+ c un metodo iterativo stazionario

• consistente,

• convergente,

• con P simmetrica.

Allora

ke

^(k)

k

2

:= kx

^∗

− x

^(k)

k

2

≤ kx

^(k+1)

− x

^(k)

k

₂

1 − ρ(P ) .

Nota. Osserviamo che da ρ(P ) ≤ kP k, qualsiasi sia la norma k · k e ke

^(k)

k := kx

^∗

− x

^(k)

k ≤ kx

^(k+1)

− x

^(k)

k

1 − kP k non consegue direttamente per k · k = k · k

2

ke

^(k)

k

2

:= kx

^∗

− x

^(k)

k

2

≤ kx

^(k+1)

− x

^(k)

k

₂

1 − ρ(P ) in quanto per ogni norma k · k

1

1 − ρ(P ) ≤ 1

1 − kP k .

Per´o, nel caso in cui P sia simmetrica, allora ρ(P ) = kP k

2

.

Lemma 6.4 (Facoltativo). Se P `e simmetrica, allora esistono

• una matrice ortogonale U , cio`e tale che U

^T

= U

⁻¹

,

• una matrice diagonale a coefficienti reali Λ

per cui P = U ΛU

^T

ed essendo P e Λ simili, le matrici P e Λ hanno gli stessi autovalori {λ

k

}

k

.

Dal lemma, se P `e simmetrica, essendo kP k

2

:= pρ(P P

^T

), U

^T

U = I

kP k

₂

= q

ρ(P P

^T

) = q

ρ(U ΛU

^T

(U ΛU

^T

)

^T

) = q

ρ(U ΛU

^T

U ΛU

^T

) = q

ρ(U Λ

²

U (15)

^T

) Essendo U Λ

²

U

^T

simile a Λ

²

, U Λ

²

U

^T

e Λ

²

hanno gli stessi autovalori uguali a {λ

²_k

}

k

e di conseguenza lo stesso raggio spettrale, da cui ρ(U Λ

²

U

^T

) = ρ(Λ

²

).

Da ρ(U Λ

²

U

^T

) = ρ(Λ

²

) ricaviamo

kP k

2

= p

ρ(Λ

²

) = q max

k

|λ

²_k

| = q max

k

|λ

k

|

²

= q (max

k

|λ

k

|)

²

= max

k

|λ

k

| = ρ(P ). (16) Se il metodo stazionario x

^(k+1)

= P x

^(k)

+ c `e convergente, per il teorema di convergenza kP k

2

= ρ(P ) < 1 e per la precedente proposizione

ke

^(k)

k

2

:= kx

^∗

− x

^(k)

k

2

≤ kx

^(k+1)

− x

^(k)

k

2

1 − kP k

₂

= kx

^(k+1)

− x

^(k)

k

2

1 − ρ(P ) .

Il teorema afferma che se la matrice di iterazione P, di un metodo consistente e convergente, `e simmetrica, il criterio dello step `e affidabile se ρ(P ) < 1 `e piccolo.

6.2. Test di arresto: criterio del residuo

Definizione 6.5 (Criterio del residuo). Il criterio del residuo, consiste nell’interrom- pere il metodo iterativo che genera la successione {x

^(k)

} alla k-sima iterazione qua- lora

kr

^(k)

k ≤ tol dove

• tol `e una tolleranza fissata dall’utente,

• r

^(k)

= b − Ax

^(k)

.

Definizione 6.6 (Criterio del residuo relativo). Si supponga di dover risolvere il si- stema lineare Ax = b, con A invertibile e b 6= 0. Il criterio del residuo relativo, consiste nell’interrompere il metodo iterativo che genera la successione {x

^(k)

} alla k-sima iterazione qualora

kr

^(k)

k

kbk ≤ tol

Teorema 6.7. 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)−x

∗k

kx^∗k

per κ(A)  1.

• Nella dimostrazione che segue non si richiede che il metodo sia iterativo stazio- nario.

Se b = Ax

^∗

allora, essendo A invertibile

e

^(k)

= x

^∗

− x

^(k)

= A

⁻¹

A(x

^∗

− x

^(k)

) = A

⁻¹

(b − Ax

^(k)

) = A

⁻¹

r

^(k)

e quindi, essendo k · k una norma naturale

ke

^(k)

k = kA

⁻¹

r

^(k)

k ≤ kA

⁻¹

kkr

^(k)

k.

Inoltre, poich`e b = Ax

^∗

abbiamo kbk = kAx

^∗

k ≤ kAkkx

^∗

k e quindi 1

kx

^∗

k ≤ kAk kbk .

Di conseguenza, posto κ(A) = kAkkA

⁻¹

k, se x

^∗

6= 0 ricaviamo ke

^(k)

k

kx

^∗

k ≤ kAk

kbk · kA

⁻¹

kkr

^(k)

k = κ(A) kr

^(k)

k kbk .

7. 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

ⁿ

in quanto

grad(φ(x)) = Ax − b = 0 ⇔ Ax = b.

Quindi invece di calcolare la soluzione del sistema lineare, intendiamo calcolare il minimo del funzionale φ.

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)

),

e che il punto x

^∗

, in cui si ha il minimo di φ, venga calcolato rapidamente.

Definizione 7.1 (Metodo del gradiente classico, Cauchy 1847). Il metodo del gradien- te classico `e un metodo di discesa

x

^(k+1)

= x

^(k)

+ α

k

p

^(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) =

¹₂

x

^T

Ax − b

^T

x, x ∈ R

ⁿ

si mostra che tale scelta coincide con lo scegliere

p

^(k)

= r

^(k)

, α

_k

= kr

^(k)

k

²₂

(r

^(k)

)

^T

Ar

^(k)

. (17)

Nota. Con qualche facile conto si vede che `e un metodo di Richardson non stazio- nario con P = I e parametro α

k

, visto che x

^(k+1)

− x

^(k)

= α

_k

r

^(k)

.

7.1. Il metodo del gradiente: propriet`a Teorema 7.2. Se

• A `e simmetrica e definita positiva,

• kxk

A

= √ x

^T

Ax,

• e

^(k)

= x

^∗

− x

^(k)

, con x

^(k)

iterazione del gradiente classico,

• κ

2

(A) = kA

⁻¹

k

2

kAk

2

, allora

ke

^(k)

k

A

≤  κ

2

(A) − 1 κ

₂

(A) + 1



^k

ke

⁽⁰⁾

k

A

.

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

κ

₂

(A) := kAk

₂

kA

⁻¹

k

2

= max

_i

|λ

i

|

min

j

|λ

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

⁻⁶

, si ha in particolare

• k(10) = 69,

• k(1000) = 6908,

• k(100000) = 690776.

7.2. Il metodo del gradiente coniugato.

Definizione 7.3 (Gradiente coniugato, Hestenes-Stiefel, 1952). Il metodo del gradien- te coniugato `e un metodo di discesa

x

^(k+1)

= x

^(k)

+ α

k

p

^(k)

con

• α

k

=

_(p^(r_(k)^(k)₎⁾_T^T_Ap^r(k)_(k)

,

• p

⁽⁰⁾

= r

⁽⁰⁾

,

• p

^(k)

= r

^(k)

+ β

k

p

^(k−1)

, k = 1, 2, . . .

• β

k

=

_(r(k−1)^(r(k))₎^T_T^r_r^(k)_(k−1)

=

^kr(k)k22

kr^(k−1)k²₂

.

Con questa scelta si prova che p

^(k)

e p

^(k−1)

sono A-coniugati.

(p

^(k)

)

^T

Ap

^(k−1)

= 0.

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] The anecdote told at the recent conference . . . by Emer. Prof. M. Stein, the post-doc who programmed the algorithm for M. Hestenes the first time, is that Stiefel was visiting UCLA at the occasion of a conference in 1951.

Hestenes then a faculty member at UCLA, offered to demonstrate this effective new method to Stiefel, in the evening after dinner. Steifel was impressed by the algorithm.

After seeing the deck of cards he discovered that this was the same method as the one he had developed independently in Zurich. Stiefel also had an assistant, by the name of Hochstrasser, who programmed the method.

Il metodo del gradiente coniugato ha molte propriet`a particolari. Ne citiamo alcune.

Teorema 7.4. Se A `e una matrice simmetrica e definita positiva di ordine n, allo- ra 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

• in generale i calcoli non sono compiuti in aritmetica esatta,

• in molti casi della modellistica matematica n risulta essere molto alto.

Definizione 7.5 (Spazio di Krylov). Lo spazio

K

k

= span(r

⁽⁰⁾

, Ar

⁽⁰⁾

, . . . , A

^k−1

r

⁽⁰⁾

) per k ≥ 1 si dice spazio di Krylov.

Osserviamo che per quanto concerne il gradiente coniugato x

^(k+1)

= x

^(k)

+ α

_k

p

^(k)

, p

^(k)

= r

^(k)

+ β

_k

p

^(k−1)

con p

⁽⁰⁾

= r

⁽⁰⁾

, denotato x

⁽⁰⁾

+ K

_k

= {x ∈ R

ⁿ

: x = x

⁽⁰⁾

+ t, t ∈ K

_k

},

• x

⁽⁰⁾

∈ x

⁽⁰⁾

+ K

0

, supposto K

0

= ∅;

• x

⁽¹⁾

= x

⁽⁰⁾

+ α

0

p

⁽⁰⁾

= x

⁽⁰⁾

+ α

0

r

⁽⁰⁾

∈ x

⁽⁰⁾

+ K

1

;

• r

⁽¹⁾

= b − Ax

⁽¹⁾

= b − Ax

⁽⁰⁾

− α

0

Ar

⁽⁰⁾

= r

⁽⁰⁾

− α

0

Ar

⁽⁰⁾

∈ K

2

;

• x

⁽²⁾

= x

⁽¹⁾

+ α

₁

p

⁽¹⁾

= x

⁽¹⁾

+ α

₁

(r

⁽¹⁾

+ β

₁

p

⁽⁰⁾

) = x

⁽¹⁾

+ α

₁

(r

⁽¹⁾

+ β

₁

r

⁽⁰⁾

) ∈ x

⁽⁰⁾

+ K

₂

;

• x

^(k)

∈ x

⁽⁰⁾

+ K

_k

(con ragionamenti analoghi).

Teorema 7.6 ([7, p.12]). Sia

K

k

= span(r

⁽⁰⁾

, Ar

⁽⁰⁾

, . . . , A

^k−1

r

⁽⁰⁾

)

per k ≥ 1. Allora la k-sima iterata dal metodo del gradiente coniugato, minimizza il

funzionale φ nell’insieme x

⁽⁰⁾

+ K

k

.

• Si osservi che essendo la k-sima iterazione del gradiente classico pure in x

⁽⁰⁾

+ K

k

, il gradiente classico in generale non minimizza il funzionale φ in x

⁽⁰⁾

+ K

k

.

• Se K

_n

ha dimensione n, visto che conseguentemente K

n

= R

ⁿ

, si ha che x

^∗

∈ R

ⁿ

, soluzione di Ax

^∗

= b, appartiene a x

⁽⁰⁾

+ K

_n

= R

ⁿ

ed `e l’unico minimo del funzionale dell’energia, come pure l’iterazione x

⁽ⁿ⁾

del gradiente coniugato.

Quindi x

⁽ⁿ⁾

= x

^∗

.

• Si dimostra che se K

n

ha dimensione minore di n allora il gradiente coniugato ha raggiunto la soluzione in meno di n iterazioni.

Teorema 7.7. Se

• A `e simmetrica e definita positiva,

• kxk

A

= √ x

^T

Ax,

• e

^(k)

= x

^∗

− x

^(k)

, con x

^(k)

iterazione del gradiente coniugato allora (cf. [6, p.530])

ke

^(k)

k

A

≤ 2

p κ

2

(A) − 1 pκ

2

(A) + 1

!

^k

ke

⁽⁰⁾

k

A

.

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

κ

₂

(A) := kAk

₂

kA

⁻¹

k

2

= max

_i

|λ

_i

|

min

j

|λ

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.

mentre per il gradiente classico era ke

^(k)

k

A

≤ 

_κ

2(A)−1 κ₂(A)+1



^k

ke

⁽⁰⁾

k

A

ove per µ

g

(x) =

x−1

x+1

, avevamo µ

g

(10) ≈ 0.8182, µ

g

(1000) ≈ 0.9980, µ

g

(100000) ≈ 0.99998.

Affinch´e 2

 √

κ₂(A)−1

√

κ₂(A)+1



^k

< , serve k(κ

2

(A)) = dlog(/2)/ log(µ

cg

(κ

2

(A)))e.

Per  = 10

⁻⁶

, 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 clas- sico

• k(10) = 69,

• k(1000) = 6908,

• k(100000) = 690776.

[1] K. Atkinson, Introduction to Numerical Analysis, Wiley, 1989.

[2] K. Atkinson e W. Han, Theoretical Numerical Analysis, Springer, 2001.

[3] D. Bini, M. Capovani e O. Menchi, Metodi numerici per l’algebra lineare, Zanichelli, 1988.

[4] V. Comincioli, Analisi Numerica, metodi modelli applicazioni, Mc Graw-Hill, 1990.

[5] S.D. Conte e C. de Boor, Elementary Numerical Analysis, 3rd Edition, Mc Graw- Hill, 1980.

[6] G.H. Golub, C.F. Van Loan Matrix Computations, third edition, The John Hopkins University Press, 1996.

[7] C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995.