NAME (PRINT): STUDENT #:
Lasf/Surname First /Given Name SIGNATURE:
UNIVERSITY OF TORONTO MISSISSAUGA APRIL 2018 FINAL EXAMINATION CSC338H5S
Numerical Methods
Anthony Banner
Duration – 2 hours
Aids: 1 page(s) of double-sided Letter (8-1/2 x 11) sheet with no more than 12,000 characters
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 al! electronic devices with storage, including but not limited to: ceil phones, SMART devices, tablets, laptops, calculators, and MP3 players. Please turn off ail devices, seal them in the bag provided, and place the bag under your desk for the duration of the examination. You wifi 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-wrife it.
Write your answers on the examination sheet En the spaces provided. You may use the backs of pages if necessary. Concise, weli-written answers will receive more points than long, rambling ones.
I don’t know policy: If you do not know the answer to a question (or part), and you write “I don’t know”, you will receive 20% of the marks of that question (or part). If you just leave a qyestion blank with no such statement, you get 0 marks for that question.
For marking purposes only
Question Value Score 1 16
2 20 3 17 4 12 5 15 6 12 7 16
Total: 108
Name:StudentNo.:CSG338H5Spage3of17
1. (16 points total) True or False.
For each of tlie following statements, state whether it is true or false, without giving a expla- nation (2 points each):
(a) A Householder matrbi: can be inverted without incurring any numerical error.
(b) QR factorization decomposes a matrix into an. orthogonal matrbc and a positive-definite matrix.
(c) Newton’s method for solving equations converges quadratically at simple roots.
(d) If g{x*} ^ a;*, then fixed-point iteration converges at x* if \g (x*}\ < 1.
(e) TIie norm of a matrix is the maximum amount by which it streches a. vector.
(f) Cholesky factorization of an n x n matrbc performs n3/3 floating point multiplications.
(g) The expression (a; + I}2 -• {x -~ l)'i can be accurately evaluated near x ^= 0.
(h) Multiplication by an orthogonal matrbc can change the length of a vector.
continued on page 4
Name:StudentNo,:CSC338H5Spage4of17
2. (20 points total) Systems of Linear Equations.
Suppose A, B and (7 are uon-singular n x n matrices, and x is an n-vector. How would you efficiently evaluate the following expression without computing any matrix inverses:
(3I+(A-l)2)(4C'-5-l)a;
continued on page 5
Name: Student No.: CSG338H5S page 5 of 17
3. (17 points total) Householder Transformations.
(a) (5 points total) Suppose you are using Householder transformations to compute the QR factorization of the following mafcrbc:
2-37
10 4 -242
A
3 1 "9
L (1 point) How many Houseliolder transformations are required?
ii. (2 points) Specify the first Householder transformation, (z.e., Give the vector v for the transformation.)
iii. (1 point) What does the first column of A become as a result of applying tlie first Householder transformation?
iv. (1 point) What does the first column of A then become as a result of applying the second Hous&holder transformation?
continued on page 6
Name:StudentNo.:CSG338H5Spage6of17
(b) (5 points) Describe a fast method for computing the product Ha, where H is a House- holder transformation and a is a column vector. Justify your answer.
(c) (5 points) If a is n-dimensional, how many floating-point multiplications does your metiiod in part (b) perform? Justify yarn' answer.
(d) (2 points) How many floating-point multiplications are required to compute the product HB, where H is a Householder transformation a,nd B is a n x m matrbc. Justify your answer.
continued on page 7
Name:StudentNo.:CSG338H5Spage7of17
4. (12 points total) Fixed-Poiut Iteration.
For each function, g, below, verify that it has a fixed point at x =^ 2, and determine whether fixed-point iteration converges or diverges there. If it converges, determine whether conver- gence is linear or quadratic, and if ifc is linear, determine the convergence constant, 0. Justify your answers. (4 points each)
(a) ff0£)-(a;24-2)/3 (b) g[x} ^ V3a; - 2
(c) g{x} = 4a; — a;2 — 2
continued on page 8
Name:StudentNo.:CSC338H5Spage9of17
5. (15 points total) Newton's Method.
For each of the functions, ^, below, verify that it has a root at x == 1, and determine the multiplicity of the root. What is the (absolute) condition number of the root-fmding problem at x == I? Suppose we use Newton's method to find the root. Write down the Newton step for updating tlie iterate Xk) and determine whether convergence at a; = 1 is quadrafcic or linear. If it is linear, determine the convergence constant, C. Justify your answers. (5 points each)
(a) f{x}==x2m3x+2
(b) f{x)=:xs-^+Sx~-4: (c) f{x) - x3 - 4a;2 + 5a; ~ 2
continued on page 10
Name: Student No.: GSG338H5SpageIIof17
6. (12 points total) Elementaiy Elimination Matrices. Consider the following matrices:
Ml=
/10000^ f1000c^ fI0000^ 21000 D100c 01000
9 0 1 0 0 MZ D4 1 0 c Ms 0 0 1 0 0 30010 D201c 00310
<7 0 0 0 1^ <0 7 0 0 1/ ^0 0 2 0 1)
f 1 0 0 0 0 ^ { 2 7 6 4 9 ^ 01000 43862 Mi 00100 A 12121 00010 97368
<00051/ <35647/
Write down the value of each of tlie matrix formulas below\ Also write down fche number of floating-point multiplications required to compute this value efficiently. You do not need to justify your answers.
(a) (4 points) M$A
(b) (2 points) M-^M^MsM^
(c) (2 points) Mf1 (d) (2 points) My~1
(e) (2 points) M^M^
continued on page 12
Name:StudentNo.:CSC338H5Spage13of17
7. (16 points total) Optimization.
Consider the function f{x,y) = 3a;2 + 3y2 -~ 2a;y — Gx — 14y + 3.
(a) (2 points) What is the gradient of this function?
(b) (3 points) What is the critical point for this function? (There is only one.)
(c) (2 points) What is the Hessiau matrix of fcliis function?
continued on page 14
Name:StudentNo.:CSG338H5Spage14of17
(d) (5 points) Characterize the critical point as a maximum, minimum or saddle point. Justify your answer.
continued on page 15
Name:StudentNo.:GSC338H5Spage15of17
(e) (2 points) Write down the statement for updating the iterate (rcfc, y^} if we use Newton's method to find the critical point.
(f) (2 points) How would you efficiently execute the update staAement without computing any matrbc inverses?
continued on page 16