Assignment 2

Math 213_ Assignment 2_ Spring 2019 Due date: Friday, April 5 2019
1. Bisection. Write a script that uses the bisection method to solve a scalar nonlinear
equation f(x) = 0.
• Test your method by solving x3 = sin(x) in the interval 0.5 ≤ x ≤ 2 to a tolerance of
10-6.
• Plot (on a semilog graph) the error as a function of iteration number. Comment.
2. Newton's Method. Write Matlab code that implements Newton's method to find the
root of the equation x3 -2x - 5 = 0 in the interval 2 ≤ x ≤ 3 to an accuracy of 10-6.
• Print each iterate and its corresponding function value. (use format long)
• Use the function values at the last three iterates to compute the observed
convergence rate.
3. Cubic Root by Newton’s Method: Write a MATLAB script for computing the cube root of
a number, x = 3√a, with only basic arithmetic operations using Newton’s method, by
finding a root of the function f (x) = x3 − a. Run your program for a = 0, 2, 10. For each of
these cases, start with an initial guess reasonably close to the solution. As a stopping
criterion, require the function value whose root you are searching to be smaller than
10−8. Print out the values of xk and f (xk ) in each iteration. Comment on the convergence
rates and explain how they match your expectations.
4. Secant method.
a) Solve the univariate equation x3 - 2x - 5 = 0 in the interval 2 ≤ x ≤ 3 to an accuracy
of 10-6 using the secant method.
b) Compare your solution with the one produced by the built-in fzero() function.
c) Show the sequence of iterates produced and the corresponding function values.
Do you observe slower convergence than with Newton's method of problem 2
above?
d) What is the theoretical rate of convergence of the secant method? Check if your
results converge at this rate.
5. Compare All methods: For x > 0 consider the equation

x +ln x = 0.
a) Show analytically that there is exactly one root, 0 < x∗ <∞.
b) Plot a graph of the function on the interval [0.1,1].
c) As you can see from the graph, the root is between 0.5 and 0.6. Write MATLAB
routines for finding the root, using the following:
i. The bisection method, with the initial interval [0.5, 0.6]. Explain why this choice
of the initial interval is valid.
ii. A linearly convergent fixed point iteration, with x0 = 0.5. Show that the
conditions of the Fixed Point Theorem (for the function g you have selected)
are satisfied.
iii. Newton’s method, with x0 = 0.5.
iv. The secant method, with x0 = 0.5 and x1 = 0.6.
For each of the methods:
• Use |xk −xk−1| < 10−10 as a stopping criterion.
• Print out the iterates and show the progress in the number of correct decimal
digits throughout the iteration.
• Explain the convergence behavior and how it matches theoretical expectations.
Written:
Problem 1: The reciprocal of a positive number function
Assume 𝑎 > 0. We seek an approximation to 𝑟 = 1/𝑎, where r is the unique positive root
of 𝑓(𝑥) = 𝑎 – 1/𝑥.
1. Show that Newton’s iterations satisfy the following identity:

𝑟𝑛+1 = r𝑛 (2 − a𝑟𝑛 ) ∀ 𝑛 > 0
Choosing restrictively the initial condition 𝑟0 ∈ (0, 2/𝑎) leads to an iterative sequence
{𝑟𝑛 } where:
𝑟𝑛 + 1 > 0, whenever 𝑟𝑛 ∈ (0, 2/𝑎)
In such case, for all 𝑛 > 1, prove that:
(𝑟 −𝑟)2
2. 𝑟𝑛+1 − 𝑟 = − 𝑛 𝑟
3. The generated sequence is an increasing sequence
4. The sequence {𝑟𝑛 } converges to the root of f, i.e. lim 𝑟𝑛 = 𝑟
𝑛→∞
5. Convergence of the sequence is quadratic.
Problem 2:
The iteration formula 𝑥𝑛+1 = 𝑥𝑛 − (𝑐𝑜𝑠𝑥𝑛 )(𝑠𝑖𝑛𝑥𝑛 ) + 𝑅𝑐𝑜𝑠 2 𝑥𝑛 ,where R is a positive constant,
was obtained by applying Newton’s method to some function f(x). What is f(x)? What can this
formula be used for?
Problem 3:
Each of the following functions has p3 R as a zero for any positive real number R. Determine the
formulas for Newton’s method for each and any necessary restrictions on the choice for x0.
1. a(x) = x3 − R
2. b(x) = 1/x3 − 1/R
3. c(x) = x2 − R/x
4. d(x) = x − R/x2
5. e(x) = 1 − R/x3
6. f(x) = 1/x − x2/R
7. g(x) = 1/x2 − x/R
8. h(x) = 1 − x3/R
Problem 4:
Consider Steffensen’s method”

𝑓 (𝑥𝑘 )
𝑥𝑘+1 = 𝑥𝑘 −
𝑔(𝑥𝑘 )
k = 0, 1, . . . ,
where
𝑓 (𝑥 + 𝑓 (𝑥)) − 𝑓 (𝑥)
𝑔(𝑥) =
𝑓 (𝑥)
(a) Show that in general the method converges quadratically to a root of f (x).
Problem 5:
Let 𝑝(𝑥) = 𝑐2 𝑥 2 + 𝑐1 𝑥 + 𝑐0 be a quadratic polynomial with one of its roots r located in an

interval (a, b), with |𝑝′(𝑥)| ≥ 𝑑 > 0 ∀ 𝑥 ∈ (𝑎, 𝑏). Using Newton’s method with 𝑟 0 sufficiently
close to r:
|𝑐 |
a- Show that if 𝑟𝑛 ∈ (𝑎, 𝑏) then |𝑟𝑛+1 − 𝑟| ≤ 𝐶| 𝑟𝑛 − 𝑟|2 , where = 𝑑2 .
b- Let 𝑒𝑛 = 𝐶|𝑟 − 𝑟𝑛 |. Show that if 𝑟𝑛 ∈ (𝑎, 𝑏) then 𝑒𝑛+1 ≤ 𝑒𝑛2 . Give also the condition
on |𝑟 0 − 𝑟| that makes 𝑒0 < 1, and therefore 𝑒𝑛 < 1 for all n.
1
c- Assume |𝑟𝑛 − 𝑟| = 2𝐶 . Show that 𝑒𝑛 < (𝑒0 )2𝑛 , then estimate the smallest value 𝑛𝑝 of
𝑛, so that:
|𝑟 𝑛𝑝 − 𝑟|
≤ 2−𝑝
|𝑟0 − 𝑟|

Assignment 2

Uploaded by

Copyright:

Available Formats

Assignment 2

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Assignment 2

Uploaded by

Copyright:

Available Formats

Math 213_ Assignment 2_ Spring 2019 Due date: Friday, April 5 2019

5. Compare All methods: For x > 0 consider the equation

Problem 1: The reciprocal of a positive number function

1. Show that Newton’s iterations satisfy the following identity:

Consider Steffensen’s method”

Let 𝑝(𝑥) = 𝑐2 𝑥 2 + 𝑐1 𝑥 + 𝑐0 be a quadratic polynomial with one of its roots r located in an

You might also like