## Description

- Show that

x = | 1 | cos x | (1) |

2 | |||

has a solution in [0; 0:5].

Hint: use the Brouwer’s xed point theorem to show that y = ^{1}_{2} cos x has a xed point in [0; 0:5].

- This problem is a writing project from Calculus II. The goal is to show that the iteration

1

^{x}n+1 ^{=} _{2} ^{cos(x}n^{)}

^{ }

will converge to the real solution thus can be used as a numerical algorithm to solve (1). This problem also captures the idea of the proof of the Brouwer’s xed point theorem in general.

Construct the following sequence

1

x_{n+1} = _{2} cos x_{n}; a_{1} = 0:5 for n = 1; 2; 3; : : :

(a) Show that if the sequence x_{n} converges, the limit x = lim x_{n} will be the solution of (1).

n!1

- Now we only need to show that sequence x
_{n}Below are the step by step instructions. Warp them up and write a complete proof. Make you proof precise and good looking with all necessary details included.

- A function f(x) is called a CONTRACTION if there is a positive constant C < 1 such that

jf(a) f(b)j Cja bj for any a; b in R:

Use the Mean Value Theorem to show that f(x) = ^{1}_{2} cos x is a contraction with C = 1=2. ii. De ne a series y_{n} = x_{n+1} x_{n}. Use i to show that

jy_{n}j |
1 | n | 1 | ||||||||||||||||||||

jy_{1}j |
for any positive integer n 2: | ||||||||||||||||||||||

2 | |||||||||||||||||||||||

1 | 1 | n | 1 | 1 | |||||||||||||||||||

X | X | ||||||||||||||||||||||

iii. Show that _{n=1} |
jy_{1}j is convergent. Then by the comparison test _{n=1} jy_{n}j is convergent. |
||||||||||||||||||||||

2 | |||||||||||||||||||||||

1 | |||||||||||||||||||||||

X | |||||||||||||||||||||||

iv. Use iii to show that | y_{n} is convergent. |
||||||||||||||||||||||

n=1 | |||||||||||||||||||||||

v. The conclusion in iv implies that | lim (a_{n} |
1) is convergent. Therefore lim a_{n} is convergent. |
|||||||||||||||||||||

n!1 | n!1 |

- (Challenge) Based on problem 2 prove the following variation of the xed point theorem.

Fixed theorem: let f(x) : [a; b] ! [a; b]. Suppose there is a constant C < 1 such that jf^{0}(x)j C, for any x in [a; b]. Then

1

- f(x) has exactly one xed point x in [a; b]

- Using any x
_{0}in [a; b], the scheme x_{n+1}= f(x_{n}) converges to x at least linearly.

- Consider solving f(x) = x
^{3}+ 6x^{2}8 = 0

- Use the Intermediate Value Theorem to show f has a root on [1; 2].

- Consider the xed point iteration de ned by

- Function g
_{1}(x) = x^{3}+ 6x^{2}+ x 8

r

8

- Function g2(x) =

x + 6

r

- x
^{3}

iii. Function g3(x) =

6

For each scheme, show that if it converges, it will converge to the zero of f.

- Try each scheme with several random initial x
_{0}in Matlab. What do you see?

- Use the theorem in problem 3 to explain what you saw in (c).

5. Fixed point iteration: Consider the iteration x_{n} = |
1 | x_{n} |
1 ^{+} |
c | for constant c > 0. |

2 | ^{x}n 1 |

- Prove this iteration converges at least quadratically.

- What will the iteration converge to? Explain.

- Verify your results of parts (a) and (b) in Matlab.

- Relate this iteration to Newton’s Method.

6. Find a solution p to x^{4} + 2x^{2} x 3 = 0 using the following methods. |
||||

A xed point iteration for g_{1} |
(x) = (3 + x 2x^{2})^{1=4} with initial guess x_{0} |
= 0:5. | ||

A xed point iteration for g_{2} |
3x^{4} + 2x^{2} + 3 |
|||

(x) = | with a initial guess x_{0} |
= 0:5. | ||

4x^{3} + 4x 1 |

The Secant Method with initial guesses x_{0} = 0:5; x_{1} = 2.

Newton’s Method with initial guess x_{0} = 0:5.

For each, compute until you reach absolute error less than 10 ^{14}.

- For each method, print the approximation, absolute error, and computed rate of convergence. Use a table format and label the columns.

- How many steps did each method take to reach the required accuracy?

- For each method, how does the convergence rate compare to the number of correct digits gained at each step?

- (Challenge) Prove the rate of convergence for scheme de ned by g
_{1}(x) and g_{2}(x). Use it to support your computed rate of convergence.

- Read the rst two part of the article at
__http://en.wikipedia.org/wiki/Fixed_point_(mathematics)__(everything up to but not including Applications). Wrap up the idea of using xed point theorem to solve equations.

- Write a step by step instruction.

- Give three distinct examples that works ne.

- Give three distinct examples that will fail.

2