Numerical Analysis

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

(02.14.97) \underline{Termination Criteria} Warm-Up Let’s review how we use Aitken’s Acceleration and Steffensen’s Agorithm. The idea of Aitken’s Acceleration is to generate a sequence {q_{n}} from a given sequence {p_{n}} by using this formula:

\underline{Example}

Given the sequence p_{n} = \frac{1}{2n + 1} write down the first 5 terms of the sequence p_{n} and then compute the first 2 terms of q_{n} using Aitken’s Acceleration

Steffensen’s Method is just using a slightly modified Aitken’s Acceleration on the sequence generated through Picard Iteration (a.k.a fixed point iteration): p_{n} = g(p_{n−1}). \underline{Example} Consider the iterative relation p_{n} = cos(p_{n−1}). What equation does the limit of this iterative relation solve?

What method does this iterative relation represent?

Will this method converge using this iteration? How will it do so? Predict!

Let’s use Steffensen’s Method to generate the first couple terms of a sequence...

Look at Theorem 2.14 on page 81 of the textbook. Sometime, Steffensen can be quadratic!

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