Numerical Analysis

Math 370  MWF 2:30-3:25
Spring 1997  127 Fowler

(02.12.97) \underline{Accelerating Convergence and Termination Criteria} In the previous class we proved that Bisection is a linearly convergent method and Newton-Raphson is a quadratically convergent method. I also told you that False Position has an order of convergence of 1.442. Actually, that is the best case scenario for a slightly modified version of False Position. In most cases False Position is also a linearly convergent method like Bisection. It is still true that Secant Method is order 1/2 + \sqrt{5}/2 ≈ 1.618, though. Understanding and writing up the proofs of these facts may be interesting term projects that people should consider.

Because Quadratic Convergence is such a desired quantity, all sorts of people have tried to take linearly convergent methods and think of a way to make them faster. One such technique is called Aitken’s Δ^{2} Method also known as “Aitken acceleration.”

Aitken’s Δ^{2} Method Define a new sequence q_{n} in terms of p_{n} such that q_{n} converges faster than p_{n}. This new sequence is defined as

q_{n} = \frac{(p_{n+1} − p_{n})^{2}}{p_{n+2} − 2p_{n+1} + p_{n}} = \frac{(Δp_{n})^{2}}{Δ^{2}p_{n}}

Let’s see where this idea comes from:

But does it work? \underline{Example} Consider the sequences p_{n} = cos(1/n). REVIEW First, compute the rate of convergence of the method (i.e. “big oh” notation) as n goes to ∞.

Secondly, compute the order of convergence of p_{n}

Use Aitken’s Method to compute the first few terms of the sequence q_{n} from the sequence p_{n}. (You should try and use your calculator to program this in, or possibly even think of writing a short program in TruBasic to help you, you might also try looking at page 79 of the textbook!) Iterate

Linear Convergence Aitken’s acceleration

n  p_{n} =  q_{n} =

Steffensen’s Method Applying Aitken’s acceleration to Picard Iteration gives us a new algorithm called Steffensen’s Method. This is online as ALG26.TRU.

\underline{Example} Compare solving x^{3} −x−1 = 0 using Bisection, Picard Iteration, Newton’s and Steffensen’s. (Is anything missing from the statement of this problem?)

Do you think Steffensen’s is a useful method?

Termination Criteria for root finding methods In the TruBasic programs that I have made available for you we have been using the termination criteria that |p_{n} − p_{n−1}| < TOLERANCE to terminate our solution algorithms. Let’s think more about what this means.

What is the largest value TOLERANCE can be for your final iterate to be accurate to k decimal places, using absolute error as your termination criterion?

On the graph below, shade the region that the final iterate (p_{n}, f(p_{n}) could possibly fall in, known as the “convergence band”, if one uses the absolute eror as the termination criterion.

What would the graph look like if the termination criterion was |f(p_{n})| < TOLERANCE? Sketch it below...

Sketch the “convergence band” for the termination criterion |p_{n} −p_{n−1}| < δ AND |f(p_{n})| < ϵ Sketch the “convergence band” for the termination criterion |p_{n} − p_{n−1}| < δ OR |f(p_{n})| < ϵ Which of these termination criterion is “the best”? Is there one of these that would “work” for all functions? Can you think of another termination criterion we haven’t considered yet?

NOTE: Wed & Fri Classes Will Be Held In Fowler 127