$29
Homework 4 Solution
1. 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 = 12 cos x has a xed point in [0; 0:5].
2. This problem is a writing project from Calculus II. The goal is to show that the iteration
1
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
1
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).
n!1
(b) Now we only need to show that sequence xn converges. 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.
i. 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
jynj
1
n
1
jy1j
for any positive integer n 2:
2
1
1
n
1
1
X
X
iii. Show that n=1
jy1j is convergent. Then by the comparison test n=1 jynj is convergent.
2
1
X
iv. Use iii to show that
yn is convergent.
n=1
v. The conclusion in iv implies that
lim (an
1) is convergent. Therefore lim an is convergent.
n!1
n!1
3. (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
1
(a) f(x) has exactly one xed point x in [a; b]
(b) Using any x0 in [a; b], the scheme xn+1 = f(xn) converges to x at least linearly.
4. Consider solving f(x) = x3 + 6x2 8 = 0
(a) Use the Intermediate Value Theorem to show f has a root on [1; 2].
(b) Consider the xed point iteration de ned by
i. Function g1(x) = x3 + 6x2 + x 8
r
8
ii. Function g2(x) =
x + 6
r
• x3
iii. Function g3(x) =
6
For each scheme, show that if it converges, it will converge to the zero of f.
(c) Try each scheme with several random initial x0 in Matlab. What do you see?
(d) 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.
2
xn 1
(a) Prove this iteration converges at least quadratically.
(b) What will the iteration converge to? Explain.
(c) Verify your results of parts (a) and (b) in Matlab.
(d) 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.
(a) For each method, print the approximation, absolute error, and computed rate of convergence. Use a table format and label the columns.
(b) How many steps did each method take to reach the required accuracy?
(c) For each method, how does the convergence rate compare to the number of correct digits gained at each step?
(d) (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.
7. 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.
(a) Write a step by step instruction.
(b) Give three distinct examples that works ne.
(c) Give three distinct examples that will fail.
2
