University of Alberta
Computing Science Department
CMPUT 340 - Winter 2021
Sample Final
Introduction to Numerical Methods (CMPUT 340)
1. (Heath 2018) Consider the nonlinear equation
f(x) = x2 − 2 = 0
a) With x0 = 1 as a starting point, what is the value of x1 if you use Newton’s method for solving
this problem?
b) With x0 = 1 and x1 = 2 as a starting points, what is the value of x2 if you use the secant method
for solving this problem?
2. (Heath 2018) Write out Newton’s iteration for solving each of the following nonlinear equations:
a) x3 − 2x− 5 = 0
b) e−x = x
c) x sin(x) = 1
3. (Heath 2018) On a computer with no functional unit for floating-point division, one might instead
use multiplication by the reciprocal of the divisor. Apply Newton’s method to produce an iterative
scheme for approximating the reciprocal of a number y > 0. Considering the intended application,
your formula should contain no divisions.
4. Consider a function f : Rn → R given by
f(x) =
1
2
xTAx− xT b+ c ,
where x and b are vectors, A is a matrix, and c is a constant. Explain in English why Newton’s method
is able to find the minimum of the equation above in a single step for any starting point x0.
5. Prove that any local minimum of a convex function f on a convex set S ⊆ Rn is a global minimum of
f on S.
6. Consider a procedure for finding the minimum of the function depicted in the image below in the
interval [a, b]. We will assume that the function is convex in the interval.
1
a) Given that f(x1) > f(x2), what is the smallest interval involving values a, x1, x2, b that will
contain the minimum of the function?
b) The bisection algorithm reduces the interval [a, b] using the procedure described in (a) to reduce
the bracket containing the minimum of the function. The algorithm’s efficiency clearly depends
on the choice of x1 and x2. Describe a method for choosing x1 and x2 and explain how this is
more efficient than using arbitrary values of x1 and x2.
7. (Heath 2018) Given the three data points (−1, 1), (0, 0), (1, 1), determine the interpolating degree two:
a) Using the monomial basis
b) Using the Lagrange basis
c) Using the Newton basis
Can you see that all three approaches give the same polynomial?
8. (Heath 2018) Express the following polynomial in the correct form for evaluation by Horner’s method
(the nested form we studied in class)
p(t) = 5t3 − 3t2 + 7t− 2
Why is the nested form more efficient than the exponential form written above?
9. Using the composite midpoint quadrature rule, compute the approximate value for the integral
∫ 1
0
x3dx,
using a mesh size (subinterval length) of h = 1 and also using h = 0.5. Compare the results.
10. Using the computational graph below compute the partial derivatives of the following function with
respect to x0, x1, w0, w1, b: g(w0, w1, b, x0, x1) = 11+exp(−(w0·x0+w1·x1+b)) .
x0
w0
x1
w1
b
∗
∗ + + ∗ − 1 exp +1 1/x g
2
−1
−3
−2
−3
−2
6 4 1 −1 0.367 1.367 0.731
2




































































学霸联盟