APRIL 2019
Final Exam
CSC 338H5S
Last Name: Student #:
First Name: Signature:
UNIVERSITY OF TORONTO MISSISSAUGA APRIL 2019 FINAL EXAMINATION CSC338H5S
NUMERICAL METHODS
Lisa Zhang
Duration – 2 hours
Aids: double-sided aid sheet, non-programmable calculator
The University of Toronto Mississauga and you, as a student, share a commitment to academic integrity. You are reminded that you may be charged with an academic offence for possessing any unauthorized aids during the writing of an exam. Clear, sealable, plastic bags have been provided for all electronic devices with storage, including but not limited to: cell phones, smart devices, tablets, laptops, calculators, and MP3 players. Please turn off all devices, seal them in the bag provided, and place the bag under your desk for the duration of the examination. You will not be able to touch the bag or its contents until the exam is over.
If, during an exam, any of these items are found on your person or in the area of your desk other than in the clear, sealable, plastic bag, you may be charged with an academic offence. A typical penalty for an academic offence may cause you to fail the course.
Please note, once this exam has begun, you CANNOT re-write it.
You must earn 40% or above on the exam to pass the course; else, your final course mark will be set no higher than
47%.
This final examination consists of 8 questions on 16 pages (including this page). When you receive the signal to start, please make sure that your copy of the examination is complete.
If you need more space for one of your solutions, use the last pages of the exam and indicate clearly the part of your work that should be marked.
Good Luck!
Marking Guide
#1: /10 #2: /16 #3: /8 #4: /12 #5: /14 #6: /15 #7: /12 #8: /13
TOTAL: /100
Page 1 of 16
cont’d. . .
CSC 338H5S Final Exam APRIL 2019 Question 1. [10 marks]
Circle either “True” or “False” for each of the below statements.
1. True
2. True
3. True
4. True
5. True
6. True
7. True
8. True
9. True
10. True
False False False
False
False
False
False False False
False
You can improve the conditioning of a problem by choosing a better algo- rithm to solve it.
If we use Newton’s method to find the minimum of the function f (x) = x2 + 3x − 4, the method will converge in exactly one iteration.
If a matrix has a very small determinant, then it has a very high condition number.
1 0 0
√
The matrix 0 2 √2 is orthogonal.
0−1 3 22
The secant method for root-finding typically converges faster than Newton’s method.
Given a system of linear equations, a small residual and a small condition number guarantees an accurate solution.
The series 10−2, 10−4, 10−6, 10−8, … converges quadratically. A linear least squares problem always has a solution.
For an invertible, square matrix A, we have A−1 = A+.
Householder Transformation is preferred because it is more numerically sta-
ble than Gauss Elimination.
31
Page 2 of 16 cont’d. . .
APRIL 2019 Final Exam CSC 338H5S
Question 2. [16 marks]
Part (a) [2 marks]
What is the (relative) condition number of the problem of evaluating the function f (x) = x2 + 1 at x = 1?
Part (b) [2 marks]
What is the (relative) condition number of the problem of solving for the vector x that satisfies Ax = b,
30 0
whereA= 0 −0.1 andb= 0 ? UsetheL1 norm(the1-norm).
Part (c) [2 marks]
What is the condition number of the problem of finding the root of f(x) = x3 − 1?
Part (d) [2 marks]
Consider the problems of minimizing f1(x) = (x − 3)8 and minimizing f2(x) = (x − 2)12. Which of the two
minimization problems has worse conditioning? Briefly (with no more than 10 words) explain why.
Page 3 of 16 cont’d. . .
CSC 338H5S Final Exam APRIL 2019 Part (e) [2 marks]
Write down the permutation matrix that would reverse the rows of a 4 × 4 matrix.
Part (f) [2 marks]
Write down a 4 × 4 elementary elimination matrix that would perform the operation R4 → R2 + R4 and
leave the other rows unchanged.
Part (g) [4 marks]
What is the normal equation for the least squares problem Ax ≈ b, where A = 1 0, and b = 1?
Perform all the computations to set up the normal equation, but do not solve it.
Page 4 of 16 cont’d. . .
0 1 1 1 1 0
101
APRIL 2019 Final Exam Question 3. [8 marks]
Consider the following Python code, where A is an n × n matrix, and v is a vector of size n. import numpy as np
A_inv = np.linalg.inv(A)
A_inv_sq = np.matmul(A_inv, A_inv)
b = np.matmul(A_inv_sq, v)
Part (a) [2 marks]
Write a mathematical expression relating b to A and v.
b=
CSC 338H5S
Part (b) [6 marks]
Describe an algorithm to compute b without inverting any matrices. You do not have to write Python
code. Instead, explain step by step what operations to perform.
Page 5 of 16 cont’d. . .
CSC 338H5S Final Exam APRIL 2019
Question 4. [12 marks] Part (a) [6 marks]
Consider the floating-point system F (β = 10, p = 4, L = −10, U = 10). Suppose we wish to compute the average of three numbers x, y, and z. Consider two algorithms:
# Algorithm 1:
avg = (x + y + z) / 3
# Algorithm 2:
avg = x/3 + y/3 + z/3
Which algorithm is preferable? Circle your choice above.
Provide example values for x, y and z, and show that your chosen algorithm provides the correct answer, whereas the other algorithm provides an incorrect answer or no answer at all.
Page 6 of 16 cont’d. . .
APRIL 2019 Final Exam CSC 338H5S Part (b) [6 marks]
Consider the normalized floating-point system F(β = 2,p = 6,L = −100,U = 100), where chopping is used for rounding. We wish to perform the computation below using the floating-point system.
f(n) = (2n −10)−((2n −5)−5)
Find one positive integer n such that f(n) evaluates to a nonzero floating-point value. Show the compu-
tation and the results of 2n −10 and (2n −5)−5.
Page 7 of 16 cont’d. . .
CSC 338H5S Final Exam APRIL 2019 Question 5. [14 marks]
Suppose you are using Householder transformations to compute the QR factorization of the following matrix:
Part (a)
[2 marks]
2 3 1
2 5 1 A=2 3 9
2 5 5 311
How many Householder transformations are required?
Part (b) [4 marks]
Specify the first Householder transformation by finding the vector v describing the transformation.
Page 8 of 16 cont’d. . .
APRIL 2019 Final Exam CSC 338H5S Part (c) [6 marks]
Apply the first Householder transformation from Part (b) to the matrix A. Draw a box around your final result.
Part (d) [2 marks]
What does the first column of A become as a result of applying the second Householder transformation?
(Do not compute the second Householder transformation for the entire matrix.)
Page 9 of 16 cont’d. . .
CSC 338H5S Final Exam APRIL 2019
Question 6. [15 marks]
Consider the function f(x) = x2 sin(x). We wish to find a root of f(x).
Part (a) [3 marks]
Notice that f(0.1) = 0.0009983 and f(−0.2) = −0.007947, so we can apply the bisection method beginnig with the interval [−0.2, 0.1]. If we wish to find an estimate of the true root x∗ accurate within 10−6 (i.e. |xest − x∗| ≤ 10−6), what is the minimum number of bisection method steps required?
Part (b) [2 marks]
Write out the Newton’s Method iterant for f(x).
xk+1 =
Part (c) [2 marks]
Compute x1 using Newton’s Method assuming x0 = 0.1, accurate to at least 4 significant digits. x1 =
Part (d) [2 marks]
Based on the above result, do you think that the secant method will converge if we set x0 = 0.1 and
x1 = 0.11? Provide a brief explanation, but do not perform any computations.
Page 10 of 16 cont’d. . .
APRIL 2019 Final Exam CSC 338H5S Part (e) [6 marks]
Consider using fixed-point iteration on g(x) = x2 sin(x) + x to find a root of f(x) = x2 sin(x). Will the iteration converge? If so, what is the convergence rate? Show your work.
Page 11 of 16 cont’d. . .
CSC 338H5S Final Exam APRIL 2019 Question 7. [12 marks]
Considerthefunctionf(x)=(x−2)2(1+sin(x)). Itisunimodalontheinterval[−2,0].
Perform two iterations of Golden Section search, beginning with a = −2 and b = 0. Recall that τ = 0.618.
Part (a) [6 marks]
Perform the first iteration of Golden Section search, beginning with a = −2 and b = 0.
a = −2 f(a) = 1.451
b=0 f(b) = 4
x1 =
f(x1) =
x2 =
f(x2) =
The minimum is not in the interval:
Reduced interval to search:
Page 12 of 16
cont’d. . .
APRIL 2019 Final Exam Part (b) [6 marks]
Perform the second iteration of Golden Section search.
a= f(a) = b= f(b) =
x1 =
f(x1) =
x2 =
f(x2) =
CSC 338H5S
The minimum is not in the interval:
Reduced interval to search:
Page 13 of 16
cont’d. . .
CSC 338H5S Final Exam
APRIL 2019
Question 8. [13 marks]
Consider the function f (x1 , x2 ) = x21 + 2×2 − x1 x2 − 3×1 − 9×2 + 3
Part (a) [2 marks]
Compute the gradient of the function.
Part (b) [2 marks]
What is the critical point of this function? You do not need to show your work.
x1 = x2 = Part (c) [2 marks]
Compute the Hessian of the function at the critical point.
Part (d) [5 marks]
Is the Hessian you found in part (c) positive definite, negative definite, or indefinite? Justify your answer
by attempting to perform Cholesky factorization on the matrix. Show your work.
Part (e) [2 marks]
Characterize the critical point as a maximum, minimum or saddle point. Justify your answer.
Page 14 of 16 cont’d. . .
APRIL 2019 Final Exam CSC 338H5S
[Use the space below for rough work. This page will not be marked, unless you clearly indicate the part of your work that you want us to mark.]
Page 15 of 16 cont’d. . .
CSC 338H5S Final Exam APRIL 2019
[Use the space below for rough work. This page will not be marked, unless you clearly indicate the part of your work that you want us to mark.]
Page 16 of 16 End of Examination