Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Questions (Forward difference operator, Backward difference operator and Shifting operator)

Questions Example: Given that y₅=4, y₆=3, y₇=4, y₈=10, y₉=24, find the value of ∆⁴y₅: (i) By using the difference table and (ii) Without using the difference table. Solution: (i) Forward difference table. From the difference table ∆⁴y₅=0. Ans. (ii) We have ∆⁴y₅= (E-1)⁴y₅ [∵ ∆=E-1]                               = (E⁴-4E³+6E²-4E+1)y₅                               = E⁴y₅-4E³y₅+6E²y₅-4Ey₅+1y₅                               = y₉ -4y₈+6y₇-4y₆+y₅ [Eⁿyₓ=yₓ₊ₙ]                               = 24-4×10+6×4-4×3+4                               = 24-40-24-12+4 =0Ans. Example: Given x:  1     2     3...
Post a Comment
Read more

Different operators

 Different operators We will study the following operators: 1) The Shifting Operator (E): Ef(x) = f(x+h) i.e Ey₀= y₁ E²f(x) = f(x+2h) i.e E²y₀ = y₂ Eⁿf(x) = f(x+nh) i.e Eⁿy₀ = yₙ Here n takes integral or fractional, positive or negative values. For example: E⁻¹f(x) = f(x-h) i.e E⁻¹ y₂ = y₁ E¹/²f(x) = f[x+(1/2)h] i.e E¹/² y₁ = y₃ₗ₂ Properties of Operator E 1) Operator E is distributive. 2) Operator E is commutative with respect to constant. 3) Operator E obeys laws of indices. 2) Forward difference operator (∆): If x₀, x₁,x₂,......., xₙ are equally spaced with interval of differencing h and if y = f(x), then  ∆f(x) = f(x+h) - f(x) i.e ∆yᵢ = yᵢ₊₁ - yᵢ for i = 0,1,2,3,..... n-1, The symbol ∆ is called forward difference operator and  ∆yᵢ is called first forward difference. Similarly, the second forward differences are ∆²yᵢ =∆yᵢ₊₁ - ∆yᵢ For example: ∆²y₀ =∆y₁ - ∆y₀ = (y₂ - y₁)-(y₁-y₀)                           ...
Post a Comment
Read more

Relation between the operators.

 Relation between the operators: We can express each of Δ,∇,𝛿,μ and D in terms of E.  1) Δ = E - 1 Proof: By definition of  Δ  Δf(x) = f(x+h) - f(x)           =Ef(x) - f(x)         [∵Ef(x) = f(x+h)] Hence Δ = E -1 2) ∇ = 1 - E⁻¹ Proof: By definition of ∇ ∇f(x) = f(x) - f(x-h)          = f(x) - E⁻¹f(x)   [∵E⁻¹f(x) = f(x-h)] => ∇f(x) =  (1 - E⁻¹)f(x) => ∇ = 1 - E⁻¹ 3) 𝛿 =E ¹/² - E⁻ ¹/² Proof: By definition of 𝛿 𝛿f(x) = f[x+(h/2)] - f[x-(h/2)]           = E ¹/²f(x) -  E⁻ ¹/²f(x) Hence  𝛿 =E ¹/² - E⁻ ¹/² 4) 𝝁 = 1/2 (E ¹/² + E⁻ ¹/²) Proof: By definition of  𝝁     𝝁f(x) = (1/2){f[x+(h/2)] + f[x-(h/2)]}              = (1/2){E ¹/²f(x) +  E⁻ ¹/²f(x)}              =(1/2){E ¹/² + E⁻ ¹/²}f(x) Hence        𝝁 = 1/2 (E ¹/² +...
Post a Comment
Read more