About
The QR decomposition allows us to decompose any type of matrix A into QR.
A=QR
where Q is orthogonal matrix, and R is upper trianguler matrix.
It is used for some applications, like solving linear equations, least squares eigenvalue calculation, and principal component analysis. But why is using QR good for solving linear equations?
Linear Equations
What we are going to solve is this equations.
Ax=b
You would find the solution using LU decomposition or Gaussian Elimination In linear algebra textbook or something. But pivot operations, which is unstable sometimes, and need additional computation, are needed for this solutions.
A=LU
QR decomposition for linear equations solution
Since Q is orthogonal matrix, the transportation matrix Q^T should be inverse matrix of Q. So, We would rewrite the equation as Rx=Q^Tb.
\begin{align}
A=QR\\
Rx=Q^Tb
\end{align}And since R is upper triangular matrix, we can use back substitution of an upper triangular matrix to get solution x. What this back-substitution is that It is a method of obtaining all solutions by substituting the obtained solution back from the end. It is efficient way because of its simplicity. It turns out that the pivot operation is not required.
And the advantage of using this solution is its numeric stability. Therefore Q is orthogonal matrix, applying it with a vector never changes its norm.
\|Q v\| = \|v\|
Back-substitution helps prevent the accumulation of numerical errors.
