xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

计算题代写-CS 510

时间：2021-03-04

CS 510 - Problem Set 2 - Non-linear Equations

Prof. Gunawardena

Due Date, Sunday March 07, 2021

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

https://www.cs.rutgers.edu/academic-integrity/introduction

sign your name:

PRINT your name:

NetID:

Official Use Only

Grade:

Grader:

i

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)

iv

学霸联盟

Prof. Gunawardena

Due Date, Sunday March 07, 2021

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

https://www.cs.rutgers.edu/academic-integrity/introduction

sign your name:

PRINT your name:

NetID:

Official Use Only

Grade:

Grader:

i

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)

iv

学霸联盟