CSC338 Midterm Solutions Notes
• Some of the grading was done on paper, and others were done on Markus
• The annotations on Markus supersedes the paper grading (we went back to try to give more part marks)
Question 1
1. False: We need a stable algorithm. The conditioning is a property of the problem, not the algorithm
2. False: The truncation error is the error due to truncating finite series, or taking a fininte series of steps in an infinite process. The truncation error is unchanged if you change a different floating-point system. The rounding
error is increased.
3. True: The under flow level βL is much smaller than the machine precision β1−p or 1β1−p.
4. True: If x and y are floating-point numbers, then x ∗ y and y ∗ x are the same.
5. False: There was a counter example in homework 3 (or 4).
6. True: We have one solution if A is invertible, and infinite solutions otherwise.
0.00001 1
7. False: The matrix A = 1 0.00001
2
is well conditioned but has a small determinant. 8. True: This is from lecture 6, page 4 in the notes.
Question 2
Part (a): 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.
Part (b): Yes, by dividing a number with an exponent close to U by a number with an exponent close to L (or just something negative).
Part (c):
Question 3
A+ = (AT A)−1AT
= A−1(AT )−1AT = A−1
Part (a): The values of the mantissa is 2.23 and the exponent is 1.
12.6=2·5+2·50 +3·5−1 = (2 + 2 1 + 3 1 ) × 51
Some people thought that 1.26 was already in base β = 5. You can tell this is incorrect for two reasons: (1) the question statement tells us that the number 12.6 is indecimal, and (2) we can’t have a digit 6 in base β = 5.
Part (b):
5 52
1
04.31 ×53 +00.244 ×53 =10.104 ×53 =1.01 ×54
Some people included digits outside the base β = 5 digits {0, 1, 2, 3, 4}, or forgot to carry. Some people forgot to align the mantissas of the two inputs based on the difference in the exponents.
Part (c):
We have εmach = β1−3 = 0.04, and the relative error 1.01−1.0104 = −0.00396.
1.0104
Question 4
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 003
4
0 0 1 2
0 0A′′′=0 0 −4 1 2
1 0 0 1
0 0 0 0.75 2.5 0 0 0 1.5 5
Question 5
Part (a)
• 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 has the columns xk from the previous step
Part (b) See lecture 5 notes.
Question 6
1 0 0 L=2 1 0
1 −1 1
The math in this question is identical to those in lecture 4, page Part (a): First, ∆y = A(x + ∆x) − Ax = A∆x
2
So, using the matrix norm property that ||A∆x|| ≤ ||A||||∆x||, we have ||∆y|| = ||A∆x|| ≤ ||A||||∆x||
Part (b): 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): 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||
3