Overview
QR decomposition is useful for least-squares problems, eigenvalue methods, and numerically stable linear algebra workflows.
CoreSource checked
QR Decomposition
Factors a matrix into an orthogonal matrix and an upper triangular matrix.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Intermediate
- Family
- Matrix Decomposition
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
orthogonal basisupper triangular matrixleast squaresmatrix factorization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^3)
Average
O(n^3)
Worst
O(n^3)
Space
O(n^2)
When to Use
- Use when solving equations needs orthogonal basis.
- Use when the input matches the assumptions behind matrix Decomposition.
When Not to Use
- Avoid when the problem is ill-conditioned and no scaling or stability checks are available.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Factors a matrix into an orthogonal matrix and an upper triangular matrix
- Uses orthogonal basis and upper triangular matrix to guide the work.
- Produces approximate numeric result.
Use Cases
- Solving equations
- Approximating integrals
- Working with matrices and differential equations
Inputs
- Numeric function, matrix, or sampled data
- Initial estimate or discretization
- Tolerance
Outputs
- Approximate numeric result
- Error estimate or residual
Key Formulas (1)
QR factorization
A = Q R
A = Q RDecomposes a matrix into an orthogonal matrix and an upper triangular matrix.
Pseudocode
- 1.Prepare the inputs and state needed for QR Decomposition.
- 2.Apply the orthogonal basis step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return approximate numeric result.
Canonical Example
- Input
- QR Decomposition input with a small representative case
- Output
- Approximate numeric result
- Explanation
- QR Decomposition applies orthogonal basis to produce approximate numeric result.
Implementation Notes
- Check convergence with residuals or estimated error, not iteration count alone.
- Keep the orthogonal basis step separate enough to test independently.
Common Pitfalls
- Ignoring conditioning and residuals can produce plausible-looking but wrong numeric answers.
- Forgetting to check edge cases can make QR Decomposition look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow the numeric approximation improving against the target function, matrix, or state.
Step 1 of 4: Prepare the inputs and state needed for QR Decomposition.
numerical-methods-mechanismNotes
QR decomposition is commonly preferred over normal equations for numerically safer least-squares solving.
Sources (1)
What each reference supports for this entry.
Matrix Computations
BookReference text for numerical linear algebra, matrix factorizations, SVD, and eigenvalue methods.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageOften paired withEigenvalue Decomposition
QR iteration is a classic path to eigenvalue computation.
Alternative toLU Decomposition
QR decomposition is often preferred for least-squares and numerical stability.
Related Algorithms
Tags
Numerical MethodsLinear AlgebraDecompositionMatrix Factorization