Accelerating convergence and Aitken's ∆² method.

 Accelerating convergence

A technique called Aitken's ∆² method is used to accelerate the convergence of a sequence that is linearly convergent, regardless of its origin of application.

Aitken's ∆² method:

Suppose {pₙ}ₙ᪲₌₀ is a linearly convergent sequence with limit p. To motivate the construction of a sequence  {p̂ₙ}ₙ᪲₌₀ that converges more rapidly to p than {pₙ}ₙ᪲₌₀. Let us first assume that 

(pₙ₊₁ - p)/(pₙ - p) ≈ (pₙ₊₂ - p)/(pₙ₊₁ - p)

=> (pₙ₊₁ - p)² ≈ (pₙ₊₂ - p)×(pₙ - p)

=> (pₙ₊₁)² -2pₙ₊₁p + p² ≈ pₙ₊₂pₙ -(pₙ+ pₙ₊₂)p+p²

=>  (pₙ₊₁)² -2pₙ₊₁p ≈ pₙ₊₂pₙ -(pₙ+ pₙ₊₂)p

=> (pₙ₊₂ + pₙ - 2pₙ₊₁)p ≈ pₙ₊₂pₙ - (pₙ₊₁)²

=> p ≈  [pₙ₊₂pₙ - (pₙ₊₁)²] /  (pₙ₊₂ + pₙ - 2pₙ₊₁)

Adding and subtracting the terms (pₙ)² and 2pₙ₊₁pₙ in the numerator and grouping terms appropriately gives

p ≈ [pₙ₊₂pₙ -2pₙ₊₁pₙ +(pₙ)² - (pₙ₊₁)² +2pₙ₊₁pₙ -(pₙ)² ] / (pₙ₊₂ + pₙ - 2pₙ₊₁)

=> p ≈ [(pₙ₊₂ -2pₙ₊₁+pₙ)pₙ - {(pₙ₊₁)² -2pₙ₊₁pₙ +(pₙ)² }] / (pₙ₊₂ + pₙ - 2pₙ₊₁)

=> p ≈ pₙ - {(pₙ₊₁ -pₙ)² / (pₙ₊₂ + pₙ - 2pₙ₊₁)}

Aitken's ∆² method is based on the assumption that the sequence {p̂ₙ}ₙ᪲₌₀  defined by

p̂ₙ ≈ pₙ - {(pₙ₊₁ -pₙ)² / (pₙ₊₂ + pₙ - 2pₙ₊₁)}

converges more rapidly to p than does the original sequence  {pₙ}ₙ᪲₌₀.

Question 1) The sequence pₙ = 1/n ,n≥1 converges to 0. Use Aitken's ∆² method to generate p̂ₙ until |p̂ₙ|≤ 5× 10⁻²?

Solution. pₙ = 1/n, n≥1

p₁ = 1

p₂ = 1/2 = 0.5

p₃ = 1/3 = 0.33

p₄ = 0.25

p₅ = 0.2

p₆ = 0.167

p₇ = 0.143

p₈ = 0.125

p₉ = 0.11

p̂₁ = p₁ - (p₂ - p₁)²/[p₃-2p₂+p₁ ]

= 1 - (0.5-1)²/[0.33-2(0.5)+1] = 1 - 0.25/[1.33 - 1] = 1 - 0.25/0.33 = 1- 0.76 = 0.24

p̂₂ = p₂ - (p₃-p₂)²/[p₄-2p₃+p₂]

= 0.5 - (0.33 - 0.5)²/ [0.25 - 2(0.33) + 0.5 ]= 0.5 - 0.0289/0.09 = 0.5 - 0.321 = 0.179.

p̂₃ = p₃ - (p₄-p₃)²/[p₅-2p₄+p₃]

= 0.33 - (0.25 - 0.33)²/[0.2 - 2(0.25)+0.33] = 0.33 - 0.0064/0.03 = 0.33 - 0.213 = 0.117

p̂₄ = p₄ - (p₅-p₄)²/[p₆-2p₅+p₄]

= 0.25 - (0.2-0.25)²/[0.167-2(0.2)+0.25] = 0.25 - 0.0025/[0.417-0.4] = 0.25 - 0.0025/0.017 = 0.25 - 0.1470 = 0.103

Similarly

p̂₅ = 0.079

p̂₆ = 0.071

p̂₇ = 0.035 Ans.