Numerical Analysis

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

(02.07.97) \underline{Fixed Point Iteration (continued)} Analyzing Fixed Point Iteration Let us try and explain the behaviour of the examples from Wednesday by looking more closely at the functions we were using. First, recall the condition for Picard Iteration to work: Convergence Criteria for Picard Iteration The iteration process p_{n} = g(p_{n−1}) for n = 1, 2, 3, ⋯ will converge to a unique solution for any initial value p_{0} in [a,b] if g′ exists on (a,b) and 0 < |g′(x)| < 1 for all x ∈ [a, b]

The example functions were

\begin{matrix}g_{1}(x) = \frac{1}{2}x^{2} + \frac{1}{4} & g′_{1}(x) = \\ g_{2}(x) = 2e^{−1.5x} & g′_{2}(x) = \\ g_{3}(x) = cos^{2}(x) & g′_{3}(x) = \\ g_{4}(x) = sin(x + \frac{1}{4}) & g′_{4}(x) = \end{matrix}

Which of these functions converged using functional iteration?

Can you explain why? (Think about the behavior of the derivative on the interval of interest in each case)

Which of the iterations exhibit monotone convergence?

Which of the iterations exhibit oscillating convergence?

Consider these two other functions, g_{5}(x) = 2 ln(2x − 1) on [0,0.5] and g_{6}(x) = e^{−10x} on [1,3]

Will Picard Iteration converge or diverge for these examples? (prove your answer graphically on the next page)

Graphical Examples Look at these plots of g_{5}(x)2 ln(2x − 1) and g_{6}(x) = e^{−10x} and graphically indicate whether Picard iteration converges or diverges. In either case classify the convergence as either monotone or oscillating \underline{Example} page 54, #7 Let us try to use Picard Iteration to approximate \sqrt[5]{7}, assuming p_{0} = 1

What function would we have to use to find the zero of in order to compute 7^{1/5}?

What function would we have to use to do functional iteration on? [i.e. what is g(x)?] Is there only one such function? If you can, write down three.

How will you decide which function to do the functional iteration on? [i.e.which one will converge the fastest]

Try running ALG22.TRU on your choices and see if this confirms your choice of function above...

Rates of Convergence of Iterative Methods

If we have a sequence of approximations {p_{n}} which converges to p and there exist positive constants α and λ so that

lim_{n→∞} \frac{|p_{n+1} − p|}{|p_{n} − p|^{α}} = λ

then the sequence is said to converge to p with order α, with an asymptotic error constant λ. The method is said to be an “α order” method.

We have considered iterative methods in this class so far... Write them down below with their corresponding iterative step p_{n} = g(p_{n−1})

Let’s rank these in order of “order”.

How can we prove this order? Can we determine the order of these methods analytically? can we do it experimentally? How???

NOTE: Monday Classes Will Be Held In Fowler 201