Homework 4 Solution

Description

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 = ¹₂ 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 ⁼ ₂ ^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

x_n+1 = ₂ cos x_n; a₁ = 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

2. Now we only need to show that sequence x_n 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.

2. 1. 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) = ¹₂ 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

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 jf⁰(x)j C, for any x in [a; b]. Then

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

2. Using any x₀ in [a; b], the scheme x_n+1 = f(x_n) converges to x at least linearly.

4. Consider solving f(x) = x³ + 6x² 8 = 0

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

2. Consider the xed point iteration de ned by

i. Function g₁(x) = x³ + 6x² + x 8

r

8

ii. Function g2(x) =

x + 6

r

• x³

iii. Function g3(x) =

6

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

3. Try each scheme with several random initial x₀ in Matlab. What do you see?

3. 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

1. Prove this iteration converges at least quadratically.

2. What will the iteration converge to? Explain.

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

4. 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 x₀ = 0:5; x₁ = 2.

Newton’s Method with initial guess x₀ = 0:5.

For each, compute until you reach absolute error less than 10 ¹⁴.

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

1. 2. How many steps did each method take to reach the required accuracy?

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

1. 4. (Challenge) Prove the rate of convergence for scheme de ned by g₁(x) and g₂(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.

7. 1. Write a step by step instruction.

7. 2. Give three distinct examples that works ne.

7. 3. Give three distinct examples that will fail.

2