Extra task – NLAA– Numerical Linear Algebra with Applications
Instructions: Please upload to Canvas by the end of the Friday lecture in week 8 (March 8) a single file corresponding to part (b) of the task below. Please name your file as suggested in the question.
Plagiarism check: Your 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.
Let A ∈ Rn×m have full rank and let b ∈ Rn. Consider the least squares problem: find the minimiser x∗ ∈ Rm of the functional F : Rm → [0,∞) given by
F(x) := ∥b − Ax∥2.
(a) Modify the algorithm for the LU-factorization with partial pivoting so that it constructs the
factorization
PA = LU, (1)
where P is a permutation matrix, U ∈ Rm×m is upper triangular and L ∈ Rn×m is unit lower triangular (i.e., for 1 ≤ i ≤ n, Lij = 0 if j > i and Lii = 1). Write a function file luppgen.m with A as input, while your output should be the factors LE,UE in the economy (thin) version of (1) and a permutation vector corresponding to P.
(b) Using the factorisation from part (a), derive the LU factorisation method for the least squares problem. Write a function file lslusolve.m to implement this method. Your input should be A,b, while your output should be the solution vector x∗. Your file should contain luppgen.m as a subfunction.
Note: You should submit the matlab file for this task only if you are registered on the LM version of this course (module code 27689), i.e., if you are a Year 4 or MSc student, or you registered specifically on the LM version as an exchange or Erasmus student.