## 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?