Question 1. [8 marks]
Circle either “True” or “False” for each of the below statements.
1. False
2. False
3. True
4. True
5. False
6. True
7. False
8. True
We need a well-conditioned algorithm in order to obtain an accurate result.
The truncation error is larger if we use a floating-point system with a smaller precision.
In the floating-point system F(β = 2,p = 23,L = −100,U = 100), the underflow level is less than the machine precision.
Floating-point multiplication is commutative.
If an n×n matrix A is invertible, then it can be written as a product A = LU
where L is lower-triangular and U is upper-triangular.
The number of solutions to the system Ax = b where A is n×n can be
determined without knowing the right-hand side vector b.
A 2 × 2 matrix A is ill-conditioned if its determinant is small.
The conditioning of a system Ax = b where A is an m × n matrix with m > n is worse when the angle between b and span(A) is large.
Midterm Test — Solutions Winter 2020
Page 1 of 6
Midterm Test — Solutions Winter 2020
Question 2. [5 marks]
Answer the following questions with at most 1-2 sentences.
Part (a) [2 marks]
Recall that a problem is well-posed if a solution exists, the solution is unique, and the solution depends continuously on the problem data. Why is the continuity condition necessary for a numerical problem that we wish to solve using a computer?
Solution: Continuity condition is necessary because the problem is usually represented using floating- point numbers, so the problem representation will not be exact. Only if the problem is continuous will our computed solution be close to the exact solution.
Grading: One point for mentioning floating-point numbers. One point for detailed explanation about continuity.
Part (b) [2 marks]
Is it possible for floating-point division to overflow? Justify your answer.
Solution: Yes, by dividing a number with an exponent close to U by a number with an exponent close to L (or just something negative).
Grading: One point for ”yes”. One point for justification or example.
Part (c) [1 mark]
Show that the pseudo-inverse of an invertible n × n matrix A is A−1.
Solution: A+ = A−1 because
A+ = (AT A)−1AT
A+A = (ATA)−1ATA = I
Grading: No part marks except for very minor typos.
Page 2 of 6
Midterm Test — Solutions Winter 2020
Question 3. [5 marks]
Consider the floating-point system F (β = 5, p = 3, L = −5, U = 5), where chopping is used for rounding.
Part (a) [1 mark]
What is the representation of the decimal number 12.6 in this system? (What are the values of the mantissa
and exponent?)
Solution: The values of the mantissa is 2.23 and the exponent is 1.
5 52
Grading: Half point if only exponent the is wrong. Otherwise no part marks.
Part (b) [1 mark]
Perform floating-point addition on these two floating-point values: 4.31 × 53 and 2.44 × 52, where the
mantissa here contains digits in base β = 5. Solution:
04.31 ×53 +00.244 ×53 =10.104 ×53 =1.01 ×54
Grading: Part mark for minor typos only.
Part (c) [2 marks]
Show that the relative error in the above computation is below εmach. Show all your work.
Solution and Grading:
• one point for computing εmach = β1−3 = 0.04
• one point for computing the relative error 1.01−1.0104 = −0.00396 1.0104
12.6=2·5+2·50 +3·5−1 = (2 + 21 + 3 1 ) × 51
Page 3 of 6
Midterm Test — Solutions Winter 2020
Question 4. [4 marks]
Perform one step of Gauss Elimination with pivoting on the matrix A′′ to elimiate below the third
diagonal. The first two steps of Gauss Elimination has already been done for you.
Write down the permutation matrix P3, the elementary matrix M3, and the new value A′′′ = M3P3A′′.
12 5 07
02 0 13 A′′=0 0 3 0 1 0 0 −4 1 2
00213 Solution: First, apply the permutation matrix to swap rows 3 and 4.
10000 12 5 07
01000 02 0 13 P3=0 0 0 1 0P3A′′=0 0 −4 1 2
00100 00 3 01
00001 00213 Now the matrix M3 is below, and when applied the new matrix becomes:
10000 12507
01000 02013 M3=0 0 1 0 0A′′′=0 0 −4 1 2
4 0 0 3 1 0 0 0 0 0.75 2.5
0 0 1 0 1 0 0 0 1.5 5 2
Grading:
• one point for P3 (no part marks?)
• one point for M3 (half point for getting the sign right) • two points for A(′′′)
Page 4 of 6
Solution:
Grading: Half point per entry.
1 2 1 A=2 5 1
113
1 0 0 L=2 1 0
1 −1 1
Midterm Test — Solutions Winter 2020
Question 5. [6 marks] Part (a) [3 marks]
Given an n × n non-singular matrix A and a second matrix B, describe an efficient algorithm to compute A−1B.
• First, compute the LU factorization of P A = LU
• Then, for each column bk of B, compute xk = A−1bk using forward and backward substitution • The solution matrix hs the columns xk from the previous step
Grading:
• one point: Computes the LU factorization only once,
• one point: Specifies use of forward/backward substitution
• one point: Separating the columns of B, and treating them as problems Ax = b
Part (b) [3 marks]
Perform Cholesky Factorization on this matrix.
Page 5 of 6
Midterm Test — Solutions Winter 2020
Question 6. [4 marks]
Consider the function f(x) = ||Ax||2, where x is a n × 1 vector, A is an n × n invertible matrix, and f(x) is a real number representing the 2-norm of the vector Ax. We’ll omit the subscript in || · ||2 to keep the notation clean, but all norms in this question are 2-norms.
In this question, we will show that the condition number of f is cond(A), so that the relative error f (x+∆x)−f (x) ||∆x||
f(x) is bounded above by cond(A) ||x|| .
To that end, let y = Ax so that f(x) = ||y||. Suppose that there is a perturbation ∆x in x. Let
∆y = A(x + ∆x) − Ax Part (a) [1 mark]
Show that ||∆y|| ≤ ||A||||∆x||, justifying your steps.
Solution: First, ∆y = A(x + ∆x) − Ax = A∆x
So, using the matrix norm property that ||A∆x|| ≤ ||A||||∆x||, we have ||∆y|| = ||A∆x|| ≤ ||A||||∆x||
Part (b) [1 mark]
Show that ||x|| ≤ ||A−1||||y||, justifying your steps.
Solution: Since y = Ax and A is invertible, we can write x = A−1y. Using the matrix norm property that ||A−1y|| ≤ ||A−1||||y||, we have ||x|| = ||A−1y|| ≤ ||A−1||||y||
Part (c) [2 marks]
||∆y|| ||∆x|| f (x+∆x)−f (x) ||∆x||
Show that ||y|| ≤ cond(A) ||x|| , so that f(x) ≤ cond(A) ||x|| . Solution:
Since ||∆y|| ≤ ||A||||∆x|| and ||x|| ≤ ||A−1||||y||, we have that ||∆y|| ≤ ||A||||∆x||
||A−1||||y|| ||x||
||∆y|| ≤ ||A||||A−1||||∆x||
||y|| ||x|| ||∆y|| ≤ cond(A)||∆x||
||y|| ||x||
Page 6 of 6
End of Solutions