Numerical Analysis

Math 370 Fall 1998  MWF 11:30am - 12:25pm
\begin{matrix}c \\ ◯ \end{matrix}1998 Ron Buckmire  Fowler 127

Class 15: Wednesday October 07

SUMMARY Generalizing Root-Finding Algorithms: Fixed Point Iteration READING Burden & Faires, 54–63

Fixed Point

A function g(x) is said to have a fixed point p if g(p) = p. In other words, if the value you put into the function is exactly the same value that you get out.

Solving the equation g(x) = f(x) − x = 0 is identical to finding the fixed point of f(x) AND the zero of g(x). So, we are dealing with another possible method for finding the root of a one-variable equation.

Fixed Point Iteration The iteration process is p_{n} = g(p_{n−1}) for n = 1, 2, 3, . . .. This process is also called picard or functional iteration or sometimes repeated substitution. \underline{Example} Consider the function g(x) = log(x + 4) on [1,2]. Each one of you should pick a starting value, (i.e. p_{0} = 1) and then actually execute a number of Picard iterations. Record your results below:

p_{n} g(p_{n})

Do you think your sequence is converging? How many fixed points does g(x) = log(x + 4) have? What’s the value of its fixed point(s) to 4 decimal places?

Uniqueness: The Fixed Point Theorem

If g is continuous on [a,b] and g(x) ∈ [a, b] for all x ∈ [a, b] then g has a fixed point in [a,b]. In addition, if 0 < |g′(x)| < 1 for all x ∈ [a, b] then g has a unique fixed point in [a,b]

Using the above theorem what can we say about our example function?

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]

Using the above theorem what can we say about our example iteration process?

GroupWork Take a look at the following examples of possible functions to do fixed-point interation on and in groups of two or three graphically indicate what happens. Try the initial guesses like p_{0} = 0 and p_{0} = 1.

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}

1. Let us try to use Picard Iteration to approximate \sqrt[5]{7}, assuming p_{0} = 1

2. What function f(x) would we have to use to find a zero for in order to compute 7^{1/5}?

3. 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 possible g(x) functions which have the fixed point 7^{1/5}

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

5. Try running q:\calculus\370\ALG22.TRU on your choices and see if this confirms your choice of function above...