Exercise sheet 3 – NLAA– Numerical Linear Algebra with Applications
Instructions: Please hand in solutions to Q1, and Q2 by Friday 1pm week 11 (March 29). You should also upload to Canvas by the same deadline a single zip file containing the files nsd.m, eigspower.m. Please name your files as suggested in the question.
Plagiarism check: Your handwritten and electronic submissions should be your own work and should not be identical or similar to other submissions. A check for plagiarism will be performed on all submissions.
1. Let A ∈ Rn×n be a non-symmetric positive definite matrix. Let F(x) = 1∥b − Ax∥2. 2
(a) Show that F has a unique global minimizer x∗ which is the solution of a linear system which you should specify.
(b) Consider the iteration xk+1 = xk +αkdk for approximating x∗. Find the value of αk which achieves the greatest reduction in F(xk+1) in the direction dk = rk. Write down the pseudo-code for the resulting iterative method.
(c) Implement in Matlab the algorithm from (b) using x0 = 0. You should write a function file nsd.m which takes as input a matrix A, a vector b and returns an approximation xk to x = A−1b such that
∥b − Axk∥2 ≤ 10−6∥b∥2.
2. Let A ∈ Cn×n be a diagonalisable matrix whose eigenvalues have algebraic multiplicity equal to one.
Let {λ1, v1} denote its dominant eigenpair and assume (v1)1 ̸= 0.
(a) Define A1 := A and consider the Gauss matrix L1 := L1(v1). Show that the first column of L−1 is
a dominant eigenvector of A1. Write down the columns of A1L−1. Deduce that 1
−1 λ1 r A1L1 = q B
[20]
for a matrix B, row vector r and column vector q which you should specify in terms of certain sub-blocks of A.
(b) Using part (a) show that
−1 λ1 r L1A1L1 = 0 A2
for a matrix A2 which you should specify. Hence, show that λ1(A2) = λ2(A1).
(c) Find the expression for the eigenvector v2 corresponding to λ2(A1) in terms of r, λ1(A), λ2(A) and
the dominant eigenvector for A2.
(d) Part (b) indicates that the power method can be employed on A1, then A2 to find λ1(A) and λ2(A), respectively. This suggests an iterative procedure, where the power method is applied to a set of matrices {Ak}1≤k≤n−1 of size n − k + 1 to compute the eigenvalues of A. Write a Matlab function eigspower.m that would compute sequentially the eigenvalues of A in decreasing order of magnitude. Your input should be a matrix A and your output should be a column vector D containing the eigenvalues of A. The power method employed should use a tolerance of 10−12, kmax = 1, 000 and a starting vector v = 1 + i1. Your function file should
• employ the expression for A2 derived in part (b) (i.e., it should avoid generating L1 and forming the product L1A1L−1 explicitly).
1
• check at every step that (v1)1 ̸= 0 and display an error message if it does, while still returning
the partially computed vector D. [Type help error to see how to handle error messages in Matlab.]
1
[30]