# QR decomposition

## 1 QR Decomposition

Orthogonal matrix^{} triangularization (QR decomposition^{}) reduces a real $m\times n$ matrix $A$ with $m\ge n$ and full rank to a much simpler form. It guarantees numerical stability by minimizing errors caused by machine roundoffs. A suitably chosen orthogonal matrix $Q$ will triangularize the given matrix:

$$A=Q\left[\begin{array}{c}\hfill R\hfill \\ \hfill 0\hfill \end{array}\right]$$ |

with the $n\times n$ right triangular matrix $R$. One only has then to solve the triangular system $Rx=Pb$, where $P$ consists of the first $n$ rows of $Q$.

The least squares problem $Ax\approx b$ is easy to solve with $A=QR$ and $Q$ an orthogonal matrix (here and henceforth $R$ is the entire $m\times n$ augmented matrix from above). The solution

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

becomes

$$x={({R}^{T}{Q}^{T}QR)}^{-1}{R}^{T}{Q}^{T}b={({R}^{T}R)}^{-1}{R}^{T}{Q}^{T}b={R}^{-1}{Q}^{T}b$$ |

This is a matrix-vector multiplication ${Q}^{T}b$, followed by the solution of the triangular system $Rx={Q}^{T}b$ by back-substitution. The QR factorization saves us the formation of ${A}^{T}A$ and the solution of the normal equations^{}.

Many different methods exist for the QR decomposition, e.g. the Householder transformation, the Givens rotation, or the Gram-Schmidt decomposition.

## References

- 1 The Data Analysis Briefbook. http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html

Title | QR decomposition |

Canonical name | QRDecomposition |

Date of creation | 2013-03-22 12:06:04 |

Last modified on | 2013-03-22 12:06:04 |

Owner | akrowne (2) |

Last modified by | akrowne (2) |

Numerical id | 8 |

Author | akrowne (2) |

Entry type | Definition |

Classification | msc 65F25 |

Classification | msc 15A23 |

Synonym | QR factorization |

Synonym | QR-decomposition |

Synonym | QR-factorization |

Related topic | LUDecomposition |

Related topic | GramSchmidtOrthogonalization |