CS 323: Numerical Analysis and Computing (Fall 2022)
Problem Set 3
Deadline: Thu, Oct. 20, at 23:59 pm
Please submit your solutions in a single file (e.g., pdf) to Gradescope before the deadline. After the deadline, we will subtract 15% for each day that is delayed further. You have 3 late days in total for all homework submissions. Please notify the TAs before the deadline if you plan to use the late days.
You are encouraged to collaborate on homework problems in a team of size at most 3. However, You must submit homework solutions individually and clearly state your collaborators.
Feel free to use calculators for calculating numbers like π
2
,(10!), e0.1
, unless you are asked to use some particular formulas to approximate these numbers.
For written problems, please explain your steps to get the answers. For all programming problems, please turn in your code along with your solutions.
Problem 0. Please write down your name and Rutgers netID.
Problem 1. ([S] Exercise 8.1) 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.
1. Approximately how much time does it take to carry out n iterations of Newton’s method on f(x)? Approximately how much time does it take to carry out n iterations of the secant method on f(x)?
2. Why might the secant method be preferable in this case?
Problem 2. ([S] Exercise 8.10) Suppose we have a polynomial p(x) = akx
k + · · · + a1x + a0. You can assume ak ≠ 0 and k ≥ 1.
1. Suppose the derivative p'(x) has no roots in (a, b). How many roots can p(x) have in this interval?
2. (Optional, extra points) Using the result of Problem 2.1, propose a recursive algorithm for estimating all the real roots of p(x). Assume we know that the roots of p(x) are at least apart and that they are contained with an interval [a, b].
Problem 3. ([AH] Chapter 3.3 Problem 3) On most computers, the computation of √a is based on Newton’s method for finding a root of f(x) = x
2 − a.
1. Show that the iteration formula of Newton’s method is
2. Derive the error and relative error formulas:
where RE stands for relative error. (Hint: use the error formula of Newton’s method for finding a
root α of function f: , where cn is a number between α and xn.)
3. For x0 near √a, the last formula becomes
Assume RE(x0) = 0.1, use this formula to estimate the relative error in x1, x2, x3.
Problem 4. ([A]) Suppose we use the secant method to find a root α of f(x). Show that at any iteration, if xn = α, then we must have xn+1 = α.
References
[S] Numerical Algorithms, by Solomon
[AH] Elementary Numerical Analysis, by Atkinson and Han
[A] Lecture notes by Aanjaneya