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.
Comments
Post a Comment