Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 510- Non-linear Equations
Instructions
• Download the PDF, write the solution to each problem in a separate sheet
• Scan and upload to gradescope, one page at a time
your work may not be graded without you signing below
I certify that this paper represents my own work and I have read RU academic integrity policies
Problem 1 - Newton’s Method
Suppose it takes processor time t to evaluate f(x) or f ′(x) given x ∈ R. So, computing the pair
(f(x), f ′(x)) takes time 2t. For this problem, assume that individual arithmetic operations take
negligible amounts of processor time compared to t.
• Approximately how much time does it take to carry out k iterations of Newton’s method on
f(x)?
• Assuming quadratic convergence in Newton’s method, how many iterations are needed to
obtain an absolute error of less than 10−16 if the initial absolute error is |α− x0| = 0.9?
• Suppose α is a root of f(x) of multiplicity m. If we compute the root using Newton’s method,
Show that limn→inf n+1/n = (m− 1)/m, where n is the absolute error at xn
• Consider the following graphs where x∗ is the root. A well conditioned problem is a problem
such that moving δ away from graph changes the function f by a large amount. Identity the
well-conditioned and poorly conditioned problem in this case. Which of the methods (Newton
or Secant) would be preferrable in each case? Briefly justify your answer.
Problem 2 - Newton’s Method
The function f(x) = x/
√
1 + x2 has a unique root at x = 0.
1. Show that Newton method gives xk+1 = −xk3
2. Conclude that the method succeeds if and only if |x0| < 1.
3. Using MATLAB, produce graphs to show convergence/divergence of xk when x0 = 0.5 and
x0 = 1.5
ii
Problem 3 - Choosing a method
Provide an example of root-finding problems that satisfy the following criteria. Please justify your
example in each case.
• Can be solved by bisection but not by fixed point iteration
• can be solved using fixed point iteration, but not using Newton’s method
• f ∈ C1 and f ′ is inexpensive to evaluate
• f is Lipschitz with constant c satisfying 0 ≤ c ≤< 1
•
Problem 4 - roots of Polynomial
(A. Nguyen) Suppose that we have a polynomial f(x) = akx
k + ak−1xk−1 + .... + a1x + a0 and
assume that ak 6= 0 and k ≥ 1
• Suppose that the derivative of f ′(x) has no roots in (a, b). How many roots can f(x) have in
this interval? Justify your answer.
• Propose a recursive algorithm for estimating all of the real roots of f(x). Assume that we
know the roots of f(x) are at least δ apart and contained in a bounded interval [a, b].
Problem 5 - Division Algorithm
IEEE-754 hardware has implemented a fast convergence method known as Newton-Raphson division
method. We will discuss its components below.
1. If a ∈ R and a 6= 0, show how 1/a can be computed iteratively using Newton’s method. Write
your iterative formula in a way that requires at most two multiplications, one addition/sub-
traction and no divisions.
2. Show that rk+1 = r
2
k, where rk is the relative error in iterate xk. For what range of initial
iterates x0 will converge to 1/a?
3. Suppose that the algorithm is used to create a division capability for a binary computer which
has 53-bit mantissa and rounds. For a = (1.d1d2...d52)2 × 2e, the initial iterate is taken to
be x0 = 2
−(e+1) (and analoously for a < 0). Bound the initial relative error r0. How many
iterations are needed to guarantee full machine precision?
4. Show that, if |rk+1| ≤ Mr2k for all k, then |rk| ≤ (1/M)(Mr0)2k . Thus |rk| approaches 0, if
|r0| < 1/M
iii
5. Let xk be the estimate of 1/a during the k-th iteration of the Newton’s method. Define
k = axk − 1, show that k+1 = -2k
6. Approximately how many iterations of the Newton’s method are needed to compute 1/a within
d binary decimals? Write your answer in terms of e0 and d. You may assume that |0| < 1
7. What can you say about the convergence of this method regardless of the initial guess x0 of
1/a?
Problem 6 - Fixed Point Iteration
Suppose that we wish to compute
√
(a) where a is positive. Following are three fixed point equations
with solutions α =
√
(a), a > 0
• x = g1(x) = a+ x− x2
• x = g2(x) = 1 + x− x2/a
• x = g3(x) = x− (x2 − a)/2x
1. For what values of a, if any, will the corresponding fixed point iterations be locally convergent
to α? Explain
2. For what value of a, if any will the iterations in (i) be quadratically convergent?
3. Suppose a = 5. Show that xk+1 = g2(xk) will converge for arbitrary initial iterate x0 ∈ [2, 3].
How many iterations will guarantee absolute error < 0.01?
4. Compute
√
(5) to within absolute error 10−6 using one of the above functions gi(x)
Problem 7 - Convergence analysis
Suppose xk is converging to a root α of function f(x).
1. Assuming |xk+1 − α| ≤M |xk − α| , where M < 1, Show that
|xk+1 − α| ≤ (M/(1−M))|xk+1 − xk|
2. Suppose we wish to approximate α within an absolute error . Will it be safe to take as the
approximation of the first iterate |x1 − x0| < (Your answer may depend on M)