Numerical Linear Algebra Cookbook
Thomas Dickson
This crib sheet is based on material from Part 2 of LALFD.
Solving Least Squares:
Many applications lead to unsolvable linear equations $Ax=b$. The best solution to these equations is $\hat{x}$.
Least squares chooses $\hat{x}$ to minimise the error $\lvert \lvert b - A \hat{x} \rvert \rvert^2$
Minimising the error means that the derivatives are zero, this leads to the normal equations: $A^T A \hat{x} = A^T b$
There are four ways to calculate $\hat{x}$ as an approximate solution:
- The singular value decomposition of $A$ leads to its pseudo inverse $A^+$. Then $\hat{x}=A^+b$
- $A^TA\hat{x} = A^Tb$ can be solved directly when $A$ has independent columns.
- The Gram-Schmidt idea produces orthogonal columns in $Q$. Then $A=QR$.
- Minimise $\lvert \lvert b - A \hat{x} \rvert \rvert^2 + \delta^2 \lvert \lvert x \rvert \rvert^2$. The penalty alters the normal equations to $(A_TA + \delta^2 I)x_{\delta} = A^T b$.