Description
Question 1 10 marks
Consider the following matrices and vector:
A =
1 2 −4
2 4 1
−2 −1 3
B =
2 0 −4
2 −4 1
2 10 3
C =
2 0
50 1
R =
2
−3
1
(a) Compute the decomposition P A = LU (by hand!). Show the intermediary steps like we did
in lecture 5/6.
(b) Use the decomposition you found at (a) to solve Ax = R (by hand!).
(c) Use Gaussian elimination to solve Bx = R (by hand!). Show intermediary steps like we did
in lecture 5.
(d) Compute the condition number of C (use Python/SciPy). If we solve Cx = Q, where Q is a
2-vector of which we know the entries up to 5 digits of precision, then how accurately can we
compute x?
Question 2 10 marks
The banded, upper triangular matrix A ∈ R
n×n can be written as
A =
a1 b1 c1
a2 b2 c2
a3 b3 c3
.
.
.
.
.
.
.
.
.
an−2 bn−2 cn−2
an−1 bn−1
an
(1)
where
~a = (a1, a2, . . . , an−2, an−1, an) ∈ R
n
,
~b = (b1, b2, . . . , bn−2, bn−1) ∈ R
n−1
,
~c = (c1, c2, . . . , cn−2) ∈ R
n−2
.
The entries of ~a,
~b, and ~c are all assumed to be nonzero.
(a) Write a pseudocode for computing the matrix-vector product of A with a vector x. That is,
given vectors ~a,
~b, and ~c that define A as in definition (1), and given a vector x ∈ R
n, your
algorithm should compute the matrix-vector product ~y = A~x.
Your pseudocode should have the following form:
Input: vector ~x∈ R
n and vectors ~a ∈ R
n,
~b ∈ R
n−1 and ~c ∈ R
n−2
.
.
.
.
Insert pseudocode here
.
.
.
Output: vector ~y ∈ R
n such that ~y = A~x
(b) Analyse the complexity of the algorithm from part (a). That is, determine how many flops
are required to compute the product ~y = A~x with your algorithm. In terms of “Big-Oh”
notation, what is the asymptotic behaviour of your algorithm as n increases?
(c) Implement your pseudo-code in as a function called tridag matvec.py. Also, write a script
called compare.py to generate a tridiagonal test matrix and a test vector for a n = 10k
, k =
2, . . . , 7, compute the product and measure the time your code takes to complete. Produce a
plot of the time taken versus n on a logarithmic scale, along with your prediction.
(d) Repeat the test, but now using the built-in matrix-vector product (scipy.dot/scipy.matmul)
and the matrix A defined as an n × n matrix with mostly zeros. Plot the time taken in the
same plot as for (c). Which algorithm is faster? Is the difference as great as you expected?
