Integrazione sui criteri di arresto e sul metodo

di accelerazione di Aitken
Alessandra Sestini
7 novembre 2019

Supposto che xk → x∗ , un criterio spesso usato come criterio di arresto è

il cosiddetto criterio dell’incremento,

|xk+1 − xk | ≤ tolx , (1)

dove tolx > 0 è una tolleranza assegnata che mira a controllare l’errore
assoluto. A questo riguardo, tenendo presente che noi vorremmo fermarci in
effetti quando |xk+1 − x∗ | ≤ tolx, è interessante il seguente risultato,
Teorema 1. Se la successione {xk }∞ ∗
k=0 converge superlinearmente a x , allora

|xk+1 − xk |
lim = 1.
k→+∞ |xk − x∗ |

Dimostrazione : Infatti, tenendo presente che xk+1 − xk = ek+1 − ek , ha che

|ek | − |ek+1 | |xk+1 − xk | |ek+1 | + |ek |
≤ ∗
≤ . (2)
|ek | |xk − x | |ek |
Passando al limite, per il teorema dei carabinieri, si ottiene la tesi.
Se quindi la convergenza è superlineare, non appena vale (1) possiamo confi-
dare che sia anche |ek | ≤ tolx e quindi, a maggior ragione, confidare che sia
|ek+1 | ≤ tolx (si noti che ek+1 è quanto ci interessa, visto che forniamo in usci-
ta xk+1 naturalmente). In effetti, se per es. la convergenza della successione
è quadratica e la costante asintotica non è troppo diversa da 1, se risulta
|xk+1 − xk | ≈ tolx avremo che |ek | ≈ tolx e quindi |ek+1 | ≈ tolx2 . Quindi
se siamo interessati a garantire che |ek+1 | ≈ T OL e la successione converge

1
 √
quadraticamente, possiamo pensare di provare a prendere tolx = T OL. Nel
caso in cui la convergenza della successione a x∗ sia solo lineare con costante
asintotica 0 < c < 1, dalla (2), possiamo solo concludere che

|ek | − |ek+1 | |xk+1 − xk | |ek+1 | + |ek |

1−c≈ ≤ ∗
≤ ≈ 1 + c.
|ek | |xk − x | |ek |
Questo ci permette solo di concludere che per k grande risulta,
1
|ek | = |xk − x∗ | ≤ |xk+1 − xk | .
1−c
Se quindi vale la (1), possiamo solo dire che
c
|ek+1 | ≤ tolx .
1−c
1−c
Per garantire quindi che |ek+1 | ≤ T OL, dovremmo scegliere tolx = c
T OL.
In generale però c non si conosce.... Se però risulta che
ek+1
lim =C, con 0 < |C| < 1 (3)
k→+∞ ek

(si noti che quindi c = |C|), allora, osservando nuovamente che |xk+1 − xk | =
|ek+1 − ek | , ne consegue che

|xk+1 − xk | |ek+1 /ek − 1| |C − 1|

lim = lim = = |C| = c .
k→+∞ |xk − xk−1 | k→+∞ |1 − ek−1 /ek | |1 − 1/C|

Si osservi che se C > 0 la (3) implica che gli errori avranno lo stesso segno
da un certo k in poi; se invece C < 0 avranno segno alterno. Per esempio
l’ipotesi in (3) vale per il metodo di Newton quando la successione da esso
generata converge ad uno zero multiplo. In questi casi si può pensare di
approssimare c come segue
|xk+1 − xk |
c ≈ ck = .
|xk − xk−1 |
Naturalmente se si usa questa approssimazione, viene data in entrata T OL
e all’iterazione k–esima controllato se risulta
1 − ck
|xk+1 − xk | ≤ T OL ,
ck

2
(si osservi che, per evitare complicazioni in particolare alle prime iterazioni, si
può pensare di introdurre una correzione di sicurezza andando a sostituire il
rapporto (1 − ck )/ck con 1 se ck non è minore di 1). Concludiamo osservando
che spesso il criterio di arresto in (1) viene sostituito con il cosiddetto criterio
misto, definito come segue

|xk+1 − xk |
≤ 1, (4)
tolx + tolr|xk+1 |

dove tolx e tolr vengono rispettivamente dette tolleranza assoluta e relativa.

Si osservi che, se |xk+1 | >> tolx/tolr, si ha che (4) sostanzialmente equivale
a chiedere
|xk+1 − xk |
≤ tolr ,
|xk+1 |
ossia si cerca di controllare l’errore relativo. Quando invece |xk+1 | <<
tolx/tolr, esso sostanzialmente equivale a chiedere (1).

1 Metodo di accelerazione di Aitken

Si tratta di una tecnica da combinare con un metodo di iterazione funzionale
a convergenza lineare in modo da costruire un nuovo metodo a convergenza
quadratica. Supponiamo che ϕ sia la funzione di iterazione di base (che
supponiamo essere una contrazione in un intorno di x∗ ) che, ponendo xk+1 =
ϕ(xk ), a partire da un certo x0 definisce la successione {xk } convergente ad
un punto fisso x∗ della ϕ, con
xk+1 − x∗
lim =C
k→+∞ xk − x∗

dove 0 < |C| < 1. Dato che per k grande risulta

xk+1 − x∗ xk − x∗
≈ ,
xk − x∗ xk−1 − x∗
da questa uguaglianza approssimata si può ricavare una nuova approssima-
zione di x∗ , essendo
xk−1 xk+1 − x2k
x∗ ≈ ,
xk+1 − 2xk + xk−1

3
(naturalmente purché il denominatore sia diverso da zero). Da questa idea,
possiamo ricavare un metodo nuovo per costruire una nuova successione{zk }
a partire da un punto di innesco z0 ponendo
zk ϕ (ϕ(zk )) − ϕ(zk )2
zk+1 = , (5)
ϕ (ϕ(zk )) − 2ϕ(zk ) + zk
al solito, supposto che il denominatore non sia nullo. Osserviamo che, posto
(
zϕ(ϕ(z))−ϕ(z)2
ϕ(ϕ(z))−2ϕ(z)+z
se z 6= x∗
Φ(z) := (6)
x∗ se z = x∗

Φ è ben definita in un intorno di x∗ . Infatti, essendo ϕ una contrazione,

esiste un intorno di x∗ in cui x∗ è il suo unico punto fisso; ciò implica che,
se z 6= x∗ è in tale intorno, risulta ϕ(z) 6= z e ancora nell’intorno. Quindi
|ϕ(ϕ(z)) − ϕ(z)| < |ϕ(z) − z| che implica che il denominatore non può essere
nullo. Si osservi inoltre che in tale intorno l’unico punto fisso della Φ è x∗ .
Infatti se ne esistesse un altro, ẑ 6= x∗ sarebbe
ẑ[ϕ (ϕ(ẑ)) − 2ϕ(ẑ) + ẑ] = ẑϕ (ϕ(ẑ)) − ϕ(ẑ)2
e quindi (ϕ(ẑ) − ẑ)2 = 0 e questo è assurdo per le ipotesi sulla ϕ. Supposta
ϕ di classe C 1 in un intorno di x∗ (con in particolare |ϕ0 (x∗ )| < 1 essendo
una contrazione), possiamo verificare che Φ(z) è continua in x∗ , utilizzando
il teorema dell’Hopital,
ϕ0 (ϕ(z))ϕ0 (z)z + ϕ(ϕ(z)) − 2ϕ(z)ϕ0 (z)
lim∗ Φ(z) = lim∗
z→x z→x ϕ0 (ϕ(z))ϕ0 (z) − 2ϕ0 (z) + 1
e quindi
x∗ (ϕ0 (x∗ ) − 1)2
lim∗ Φ(z) = = x∗ .
z→x (ϕ0 (x∗ ) − 1)2
Quindi, se converge {zk } converge a x∗ . A questo riguardo e a riguardo della
velocità di convergenza della successione, può essere dimostrato il seguen-
te risultato, che è basato sul Lemma 1 riportato in appendice insieme alla
dimostrazione del teorema stesso (parte facoltativa),
Teorema 2. Se x∗ ∈ (a , b) è punto fisso di ϕ con ϕ ∈ C 2 [a , b] e tale
che 0 < |ϕ0 (x∗ )| < 1. Allora esiste un intorno I di x∗ tale che ∀z0 ∈ I
la successione {zk } definita mediante l’iterazione in (5) converge (almeno)
quadraticamente a x∗ .

4
 Si noti che, anche tenendo conto che il costo di un’iterazione di Aitken è
pari al doppio di quello di due iterazioni del metodo di base, il procedimento
risulta vantaggioso. Se infatti {xk } è la successione generata dal metodo
di base con ordine p = 1, detta c1 la corrispondente costante asintotica
(0 < c1 < 1), si ha che
|xk+2 − x∗ | ≈ c1 |xk+1 − x∗ | ≈ c21 |xk − x∗ |
mentre, in generale la successione di Aitken avrà ordine di convergenza 2 e
quindi sarà
|zk+1 − x∗ | ≈ c2 |zk − x∗ |2 ,
che implica che la convergenza sarà più rapida.
Osserviamo infine che, considerando la dimostrazione riportata in appendice,
dalle ipotesi del Teorema 2 si potrebbe rimuovere la richiesta ϕ0 (x∗ ) 6= 0 che
in effetti non è usata. Tuttavia in questo caso non sarebbe vantaggioso
utilizzare l’accelerazione di Aitken. Infatti, sebbene si possa dimostrare che
se il metodo di base ha ordine p > 1 il corrispondente metodo di Aitken
ha in generale ordine 2p − 1, non si avrebbe vantaggio. Se infatti {xk } è
la successione generata dal metodo di base con ordine p > 1, detta c1 la
corrispondente costante asintotica, si ha che
2
|xk+2 − x∗ | ≈ c1 |xk+1 − x∗ |p ≈ cp+1 ∗ p
1 |xk − x |

mentre
|zk+1 − x∗ | ≈ c2 |zk − x∗ |2p−1 ,
dove però p2 > 2p − 1.

2 Appendice
Lemma 1. Sia Φ la funzione di iterazione associata al metodo di Aitken
definita in (6), dove ϕ è una contrazione di classe C 2 in un intorno del suo
punto fisso x∗ . Allora
ϕ0 (x∗ )ϕ00 (x∗ )
lim q(η) = ,
η→0 2(ϕ0 (x∗ ) − 1)
dove la funzione q è definita come segue,
Φ(x∗ + η) − x∗
q(η) := . (7)
η2

5
Dimostrazione : Osserviamo che si può scrivere
ϕ(x∗ + η) = x∗ + θη + ση 2
con θ := ϕ0 (x∗ ) e σ = σ(η) := 12 ϕ00 (ξ1 ), con ξ1 compreso fra x∗ e x∗ + η.
Analogamente, posto
δ = δ(η) := θ + ση ,
essendo ϕ(x∗ + η) = x∗ + δη, si ha anche che
ϕ(ϕ(x∗ + η)) = x∗ + θδη + τ δ 2 η 2 ,
dove τ = τ (η) := 21 ϕ00 (ξ2 ) e ξ2 è compreso fra x∗ e x∗ + δη. Si ha quindi che
(x∗ + η)(x∗ + θδη + τ δ 2 η 2 ) − (x∗ + δη)2
Φ(x∗ + η) = .
(x∗ + θδη + τ δ 2 η 2 ) − 2(x∗ + δη) + (x∗ + η)
Riorganizzando meglio questa espressione si ottiene che
η 2 (θδ + τ δ 2 η − δ 2 )
Φ(x∗ + η) = x∗ + .
η(1 − 2δ + θδ + τ δ 2 η)
Sostituendo a δ la sua espressione in η si ottiene infine che
θ(τ θ − σ) + O(η)
Φ(x∗ + η) = x∗ + η 2 ,
(1 − θ)2 + O(η)
e quindi, tenendo conto che sia τ che σ tendono a ϕ00 (x∗ )/2 quando η tende
a zero, che
ϕ0 (x∗ )ϕ00 (x∗ )
lim q(η) = .
η→0 2(ϕ0 (x∗ ) − 1)

Dimostrazione del Teorema 2

Dimostrazione : poniamo ηk := zk − x∗ e, tenendo presente il lemma sopra,
facciamo vedere che ηk → 0 e che limk→+∞ ηk+1 /ηk2 è limitato. Osserviamo
che per definizione risulta ηk+1 = Φ(x∗ + ηk ) − x∗ e quindi, dalla definizione
della funzione q data in (7), risulta ηk+1 = q(ηk )ηk2 . Sia M una maggiora-
zione di |q| in un intorno dello zero (che grazie al lemma sappiamo esistere)
e supponiamo che γ := M |η0 | < 1. Allora, essendo |η1 | = q(η0 )η02 , risulta
|η1 | < γ|η0 |, e, in generale, si ha che |ηk+1 | < γ|ηk |, il che assicura la conver-
genza a zero della successione {ηk }. Essendo poi ηk+1 /ηk2 = q(ηk ), il limite
limk→0 ηk+1 /ηk2 risulta finito.

6
Riferimenti bibliografici
[1] Slides della prof. Papini per il corso di AN1, A.A. 2017-2018.

[2] R. Bevilacqua, D. Bini, M. Capovani, O. Menchi, Analisi Numerica.

Metodi Numerici, Zanichelli, Bologna 1992.