Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 323: Numerical Analysis and Computing
MIDTERM #2
Instructions: This is an open notes exam, i.e., you are allowed to consult any textbook, your class notes, homeworks, or any of the handouts from us. You are not permitted to use laptop computers, cell phones, tablets, or any other hand-held electronic devices.
1. [28% = 4 questions × 7% each] MULTIPLE CHOICE SECTION. Circle or underline the correct answer (or answers). No justification is required for your answer(s).
(a) In practice, Secant’s method is preferred over Newton’s method because:
i. It is always guaranteed to converge, while Newton’s method is not.
ii. It is computationally cheaper than Newton’s method.
iii. It does not require computing the derivative.
(b) In practice, the order of convergence of Newton’s method is:
i. always 2, if f does not have a multiple root.
ii. somewhere between 1 and 2, if f does not have a multiple root, because it is not always guaranteed to converge and so is used in combination with bisection search.
iii. 1 if the unknown function f has a multiple root and its explicit formula is known.
(c) Which of the following are valid reasons for using piecewise polynomial interpolation, as opposed to using a single polynomial?
i. In the monomial basis, piecewise polynomials are cheaper to compute than high-degree polynomials.
ii. Piecewise polynomials can be extended to include more data points, while it is impossible to update a single polynomial interpolant incrementally to include additional points.
iii. High-degree polynomials can suffer from global changes when a single data point is perturbed, while piecewise polynomials only change locally.
(d) An iterative method for solving f(x) = 0 has an error that satisfies the inequality |ek+1| < C|ek| 1.6 . Which of the following are true?
i. Convergence is guaranteed if C < 1.
ii. Convergence is guaranteed if we start our iteration close enough to the solution.
iii. The correct significant digits are expected to double after each iteration.
2. [24% = 3 questions × 6% each] SHORT ANSWER SECTION. Answer each of the following questions in no more than 2-3 sentences.
(a) Even if the cost of solving a linear system was cheap, what would be a good reason to still not use Vandermonde interpolation?
(b) Describe two benefits of using Chebyshev points for polynomial interpolation.
(c) Write the iterative formula of Newton’s method for solving the non-linear equation 3x = sin(2x) + 1.
3. [14%] Use Lagrange interpolation to find a cubic polynomial in the monomial basis that interpolates the following four data points:
(−4, −3), (−2, 1), (0, 2), (1, 1)
Reminder: Lagrange polynomials are given by the formula:
li(x) = Q j6=i (x − xj ) Q j6=i (xi − xj )
4. [14%] Find a cubic polynomial s(x) in the monomial basis, defined over [0, 1], that satisfies:
s(0) = 1
s(0) = −1
s(1) = 2
s (1) = −3
5. [20%] Consider a piecewise quadratic polynomial function s(x) that interpolates the n data points (x1, y1), . . . ,(xn, yn). In each subinterval Ik = [xk, xk+1], we define s(x) as a quadratic polynomial sk(x) = a (k) 2 x 2 + a (k) 1 x + a (k) 0 , such that:
• For k = 1, 2, . . . , n − 2, sk(x) should interpolate points (xk, yk), (xk+1, yk+1) and (xk+2, yk+2),
• sn−1(x) should interpolate (xn−2, yn−2), (xn−1, yn−1) and (xn, yn).
Derive a bound for the interpolation error |f(x) − s(x)|. You may assume that the length hk = |xk+1 − xk| of each subinterval is constant and equal to h.
Note: You may find the following theorem useful. Theorem 1. Let
• x0 < x1 < . . . < xn−1 < xn
• yn = f(xn), k = 0, 1, . . . , n, where f is a function which is n-times differentiable with continuous derivatives
• Pn(x) is a polynomial that interpolates (x0, y0),(x1, y1). . . ,(xn, yn)
then for any x ∈ (x0, xn), there exists a θ = θ(x) ∈ (x0, xn) such that
f(x) − Pn(x) = f (n+1)(θ) (n + 1)! (x − x0)(x − x1). . .(x − xn)