La matrice M è chiamata
la matrice di iterazione; per ogni M c’è un unico spezzamento M = N – P con N triangolare inferiore e P triangolare
strettamente superiore (cioè con zeri sulla diagonale).
Il problema di
punto fisso viene quindi affrontato con l'iterazione
b(k+1)= M b(k) +
a
(6)
o, più precisamente, con
l'iterazione equivalente
N b(k+1)= P b(k) + e
(
cioè
b(k+1)=
N-1P b(k) + N-1P
e
(6’’)
a partire da un vettore
iniziale b(0) assegnato. Affinché questo approccio sia
vantaggioso occorre che il sistema lineare
N y = P b(k) + e
(dove il termine di destra è un
vettore noto e y è un vettore incognito) sia risolvibile per y in maniera
rapida, cioè con un tempo di calcolo trascurabile rispetto a quello richiesto
per la risoluzione del problema originale Mb = e . Per questo si cerca
di ridursi al caso in cui l’operatore invertibile N sia espresso da una matrice
triangolare (inferiore o superiore), perché in questo caso la soluzione avviene
per sostituzioni successive di ogni equazione del sistema lineare nella
precedente. Qui abbiamo scelto N triangolare inferiore.
Ricordiamo che
il raggio spettrale di un operatore T su Cn è definito come :
ρ(T) = limsupk
→ ∞ ||Tk||1/k
E’ ovvio che ρ(T)
≤ ||T||, perché ||UV|| ≤ ||U|| ||V|| per ogni coppia di
operatori lineari su CN.
Ora proveremo che, se la
matrice M ha raggio spettrale minore di 1, allora l'errore tende a zero
qualunque sia il vettore iniziale b(0), ma può accadere che l'errore
tenda a zero senza che la matrice abbia raggio spettrale minore di 1. Ciò
accade quando Mk tende ad una matrice il cui nucleo includa e(0)
(come si vede dalla identità (6’’’) più sotto). D’altra parte, se l'errore
tende a zero per ogni vettore iniziale b(0), allora M deve avere
raggio spettrale minore di 1.
Ecco la
dimostrazione: definendo l’errore alla k-sima iterazione (k>0) come
e(k) = b(k) – b
sottraendo (5) da (6’’) si
ottiene per gli errori la relazione di ricorrenza
e(k+1) = M e(k)
=M2 e(k-1) =... = Mk+1 e(0)
(6’’’)