QR decomposition - Wikipedia

Abstraction: Matrix factorization into orthogonal and upper-triangular factors

Key points:

• QR decomposition factors a matrix A = QR where Q is orthogonal (or unitary) and R is upper triangular; unique when A is invertible and diagonal of R is required positive.
• Three main algorithms: Gram–Schmidt (simple but numerically unstable), Householder reflections (more stable, less parallelizable), Givens rotations (sparse, parallelizable).
• Used to solve the linear least-squares problem: for overdetermined Ax ≈ b, solution is x = R⁻¹Q^T b via back-substitution.
• Column-pivoted QR (with permutation P: AP = QR) reveals numerical rank at lower cost than SVD; diagonal of R in decreasing order.
• Householder QR: O(2n²(m − n/3)) flops for m×n matrix; numerically satisfies ‖QR − A‖ ≈ machine precision.
• First n columns of Q form an orthonormal basis for the column space of A.

Connections: Qr Decomposition · Gram Schmidt Process · Least Squares · Eigenvalue Algorithms

Source: http://en.wikipedia.org/wiki/QR_decomposition