Method of normal equation

The method of normal equation consists in solving

$$(A^{T}A)x=A^{T}b$$

The solution is:

$$x=(A^{T}A{)}^{-1}{A}^{T}b$$

The matrix $A^{T}A$ is SPD. So the system can be solved using Cholesky.

This method is best for very tall skinny $A$.

One of the main drawbacks is that the condition number grows very quickly! Indeed we can prove that

$$\kappa (A^{T}A)=\Vert A^{T}A{\Vert }_2\Vert (A^{T}A{)}^{-1}{\Vert }_2=\kappa (A{)}^2$$

So the condition number grows much faster than $\kappa (A)$.

This method requires $A^{T}A$ to be non-singular. This is equivalent to saying that $A$ should be full column rank.

The computational cost is $O(m{n}^2)$.

Least-squares problems, Symmetric Positive Definite Matrices, Cholesky factorization, Conditioning of a linear system, Stability of the Cholesky factorization