- Show that
|x =||1||cos x||(1)|
has a solution in [0; 0:5].
Hint: use the Brouwer’s xed point theorem to show that y = 12 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
xn+1 = 2 cos(xn)
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
xn+1 = 2 cos xn; a1 = 0:5 for n = 1; 2; 3; : : :
(a) Show that if the sequence xn converges, the limit x = lim xn will be the solution of (1).
- Now we only need to show that sequence xn 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) = 12 cos x is a contraction with C = 1=2. ii. De ne a series yn = xn+1 xn. Use i to show that
|jy1j||for any positive integer n 2:|
|iii. Show that n=1||jy1j is convergent. Then by the comparison test n=1 jynj is convergent.|
|iv. Use iii to show that||yn is convergent.|
|v. The conclusion in iv implies that||lim (an||1) is convergent. Therefore lim an is convergent.|
- (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 jf0(x)j C, for any x in [a; b]. Then
- f(x) has exactly one xed point x in [a; b]
- Using any x0in [a; b], the scheme xn+1 = f(xn) converges to x at least linearly.
- Consider solving f(x) = x3+ 6x2 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 g1(x) = x3+ 6x2+ x 8
- Function g2(x) =
x + 6
iii. Function g3(x) =
For each scheme, show that if it converges, it will converge to the zero of f.
- Try each scheme with several random initial x0in 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 xn =||1||xn||1 +||c||for constant c > 0.|
- 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 x4 + 2x2 x 3 = 0 using the following methods.|
|A xed point iteration for g1||(x) = (3 + x 2x2)1=4 with initial guess x0||= 0:5.|
|A xed point iteration for g2||3x4 + 2x2 + 3|
|(x) =||with a initial guess x0||= 0:5.|
|4x3 + 4x 1|
The Secant Method with initial guesses x0 = 0:5; x1 = 2.
Newton’s Method with initial guess x0 = 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 g1(x) and g2(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.