University of Toronto Scarborough
Department of Computer and Mathematical Sciences
April/May Examinations 2020
CSC D37H3 S
This is a take-home exam. Print off, complete, and submit no later
than the originally scheduled finish time for the exam, following the
instructions given on the final exam page of the course website.
Aids allowed: Open-book. All aids are allowed.
Make sure that your examination booklet has 20 pages (including this one). Write your answers
in the spaces provided. You will be rewarded for concise, well-thought-out answers, rather than long
rambling ones. Please write legibly.
This exam was designed so that you have plenty of time to write it. Take a few minutes to read each
question before you begin, and then start with the question you are most comfortable with.
Name:
(Circle your family name.)
Student #: UTORid:
YOU MUST SIGN THE FOLLOWING:
I declare that this exam was written by the person whose name and student # appear above.
Signature:
Your grade
1. / 10 6. / 5
2. / 15 7. / 10
3. / 5 8. / 10
4. / 10 9. / 15
5. / 10 10. / 10
Total / 100
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 2 of 20
Question 1
[10 marks]
Consider the over-determined linear system:
Ax = b, A ∈ Rm×n, b ∈ Rm, x ∈ Rn,m > n.
In lecture we proved that the best least-squares solution x∗ which minimizes ‖Ax− b‖2 satisfies the normal
equations ATAx = AT b. Alternatively, we could proceed to find x∗ as follows: Let
S(x) = ‖Ax− b‖22
be a function of the n variables x1, x2, . . . , xn. A well-known result in calculus states that a necessary
condition for S to have a minimum at x∗ is that x∗ satisfies the system of equations
∂S
∂xi
= 0, i = 1, 2, . . . , n.
Show that this system is exactly the normal equations.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 3 of 20
Question 2
[15 marks]
Consider the over-determined linear system Ax = b where
A =
2 21 1
2 2
, b =
36
9
.
a. Compute the QR-factorization of A using Householder reflections. Show all intermediate calcula-
tions. For example, the first reflection is given by
Q1 = I − 2vv
T
vT v
, v = a1 − ‖a1‖2e1,
where a1 is the first column of A. Verify that Q = QT1QT2 is orthogonal.
[Continue your answer on the next page . . . ]
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 4 of 20
[. . . continue your answer to (a) here.]
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 5 of 20
b. Use the QR-factorization computed in (a) to solve the least squares problem minx ‖Ax− b‖2.
Hint: This problem is rank-deficient—there are infinitely many solutions. For full marks, you must
compute the minimum-norm solution.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 6 of 20
Question 3
[5 marks]
Consider the over-determined linear system:
Ax = b, A ∈ Rm×n, b ∈ Rm, x ∈ Rn,m > n.
In general there is no exact solution to this system and the best we can do to solve the problem is minimize
the norm of the residual Ax − b. In certain cases, though, there is an exact solution and the norm of the
residual is zero. State the conditions required for this to happen and give an example.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 7 of 20
Question 4
[10 marks]
Show that in solving the least-squares problem for Ax = b, we can replace the normal equations by CAx =
Cb, where C ∈ Rn×m is any matrix row-equivalent to AT . (Two matrices G and H are row-equivalent if
there is a nonsingular matrix F for which G = FH .)
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 8 of 20
Question 5
[10 marks]
Recall the full-Newton algorithm for solving the nonlinear system F (x) = 0;F, x ∈ Rn:
Generate an initial approximation xˆ0.
for k = 0, 1, . . . until convergence
compute −F (xˆk)
compute ∂F (xˆk)∂x
solve ∂F (xˆk)∂x ∆k = −F (xˆk)
update xˆk+1 = xˆk + ∆k
end for
a. This algorithm is computationally expensive. Give a detailed analysis of the cost using standard big-oh
notation. You may use results from CSCC37; e.g., the cost (measuring flops) of the LU-factorization
of an n× n matrix is (1/3)n3 +O(n2).
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 9 of 20
b. We briefly discussed in lecture the “quasi-Newton algorithm” for solving nonlinear systems. Modify
the algorithm above to take advantage of the optimizations we discussed. You do not need to im-
plement the modifications . . . pseudo-code will suffice. Be careful to discuss both flop optimizations
and convergence issues (“X-test” and “F-test” tolerance, maximum number of iterations, condition of
Jacobian, how long to hold Jacobian fixed, etc.).
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 10 of 20
Question 6
[5 marks]
Recall the Newton polynomial for the simple interpolation problem p(xi) = yi, i = 0, 1, . . . , n:
p(x) = a0 + a1(x− x0) + a2(x− x0)(x− x1) + · · ·+ an(x− x0)(x− x1) · · · (x− xn−1)
To compute the coefficients ai we could set up the interpolation conditions in matrix-vector form resulting
in a lower triangular system which can be solved by forward elimination (no factorization is required).
However, we also showed that the Newton coefficients are divided differences (this required a theorem), and
in practice they are computed as such.
For n = 2, write out and solve the lower triangular system for Newton coefficients a0, a1, and a2, and show
that these coefficients are indeed the 0-th, 1-st,and 2-nd divided difference, respectively, as per the recursive
definition of divided differences given in lecture.
Hint: It is trivial to show a0 and a1 are the 0-th and 1-st divided difference, respectively. It is tricky to show
that a2, when computed during forward elimination on the above system, is the 2-nd divided difference.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 11 of 20
Question 7
[10 marks]
Using any technique you wish, find p ∈ P5 that satisfies
p(x) = cos(x) and p′(x) = cos′(x)
at x = 0, pi/4, pi/2 (radians). Derive a tight upper bound for ‖p(x)− cos(x)‖∞ on [0, pi/2].
Hint: It would be wise to choose the technique requiring the least amount of computation. Also, coefficients
may not be integral. Simplify only where possible.
[Continue your answer on the next page . . . ]
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 12 of 20
[. . . continue your answer to #7 here.]
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 13 of 20
Question 8
[10 marks]
Consider the definite integral I(f) =
∫ 2
0 f(x) dx.
a. Construct the interpolatory quadrature rule for this integral based on nodes 0, 1, 2. You must do this
without first computing the interpolating polynomial.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 14 of 20
b. What is the precision of the quadrature rule derived in (a)? Justify your answer.
c. If possible, use the quadrature rule derived in (a) to compute the exact value of
∫ 2
0 (2x
3 + 4x2) dx. If
this is not possible, explain why not.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 15 of 20
Question 9
[15 marks]
For any continuous function f on [a, b], we proved that an interpolatory quadrature rule converges to the
true value of the integral I(f) =
∫ b
a f(x) dx as the number of nodes increases to infinity:
Theorem: Let f ∈ C[a, b], and
Qn(f) =
n∑
i=0
A
(n)
i f(x
(n)
i ).
If ∃ a constant k ∈ R such that
n∑
i=0
|A(n)i | ≤ k ∀n
then limn→∞Qn(f) = I(f).
Review the delta-epsilon proof given in lecture. Recall we used Weierstrass’ Theorem in this proof.
a. At first glance this result seems to contradict our illustration of the Runge phenomenon, where we
showed that the accuracy of a polynomial interpolant can decrease dramatically as the number of
interpolation points increases.
Give an intuitive explanation, aided with a picture, arguing why this result does not contradict the
Runge phenomenon.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 16 of 20
b. A condition of the theorem is that ∃k ∈ R such that ∑ni=0 |A(n)i | ≤ k ∀n. This is sometimes true,
but not always, for an interpolatory quadrature rule.
When can we expect this condition to be true?
Hint: The precision of any useful rule must be m ≥ 0, implying Qn(1) = I(1) = (b− a).
c. The theorem can be proven in the other direction:
If limn→∞Qn(f) = I(f), then ∃ a constant k ∈ R such that
n∑
i=0
|A(n)i | ≤ k ∀n
In other words, the theorem is actually ”if and only if”. Prove the theorem in the other direction.
Hint: This is a difficult question. For part marks, at least cite some relevant references.
[Continue your answer on the next page . . . ]
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 17 of 20
[. . . continue your answer to (c) here.]
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 18 of 20
Question 10
[10 marks]
Consider the Trapezoidal Rule
yk+1 = yk +
hk
2
[f(tk, yk) + f(tk+1, yk+1)] , k = 0, 1, 2, . . . (1)
for integrating the general Initial Value Problem y′(t) = f(t, y(t)), y(t0) = y0.
a. Show how (1) is derived by combining two appropriate Taylor expansions. What is the truncation
error (local error) in (1)?
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 19 of 20
b. When (1) is applied to the model problem y′(t) = λy(t) it simplifies. Write out the simplified form.
c. Derive the growth factor (amplification factor) for the simplified form.
CONTINUED . . .
CSC D37H3 S FINAL EXAMINATION, WINTER 2020 Page 20 of 20
d. Using the growth factor for the simplified form derived in (c), define and sketch the region of absolute
stability for (1). Show all of your work.
e. Is (1) A-stable? Is it L-stable? Justify your answer.
END OF EXAM