QR Decomposition Simulator — Gram-Schmidt & Least Squares
Factor a 3x3 matrix A into an orthogonal Q and upper-triangular R using Modified Gram-Schmidt, then solve the least-squares system Rx=Qt b by back substitution.
Parameters
A[0][0] diagonal
—
A[1][1] diagonal
—
A[2][2] diagonal
—
b[0] right-hand side
—
Off-diagonal entries of A and other components of b are fixed (A[0][1]=1, A[0][2]=0, A[1][0]=1, A[1][2]=1, A[2][0]=0, A[2][1]=1, b[1]=2, b[2]=2). Defaults give x=(1,1,1), residual ~ 0, orthogonality error ~ 0.
Results
—
det(A) = signed |det(R)|
—
x_1 least-squares solution
—
Residual ||Ax-b||_2
—
Orthogonality error ||Qt Q-I||_F
Visualization of A, b, Q, R, x
Top: matrix A and vector b / Middle: Q (orthogonal columns q1 q2 q3) and R (upper triangular, blue=upper, gray=lower) / Bottom: solution vector x
Theory & Key Formulas
QR decomposition factors a matrix A whose columns are linearly independent into an orthogonal matrix Q and an upper-triangular matrix R. It is the standard tool for the least-squares problem ||Ax-b||_2.
The least-squares solution is obtained by back substitution on Rx = Qt b:
$$\min_x \|Ax - b\|_2^2 \iff R\,x = Q^{\top} b$$
When A is square and nonsingular, the residual is zero and the determinant satisfies |det(A)| = |det(R)| = product of r_{kk}.
What is the QR Decomposition Simulator?
🙋
Why are the letters Q and R used in "QR decomposition"? Do they mean anything specific?
🎓
Good question. Q stands for "orthogonal" (the convention comes through European notation), and R stands for "right triangular," that is, upper triangular. Householder and Gram-Schmidt independently introduced the names and they stuck. With the default values above (A diagonal = 1, 0, 1) you can see Q is orthogonal and R is upper triangular. The "Orthogonality error" card sits around 1e-15, which is essentially machine precision and is the numerical proof that Q is orthogonal.
🙋
The residual is also zero with the default values. So even though you call it "least squares," it gives the same answer as just solving the linear system?
🎓
Sharp observation. When A is square and nonsingular, the least-squares solution is the exact solution and the residual is zero. The real power of least squares shows up in overdetermined systems (more equations than unknowns) or when measurement noise makes an exact solution impossible. This tool uses 3x3 for visualization, but the same Rx=Qt b back-substitution applies to tall rectangular matrices. Try sliding A[1][1] away from 0 - det changes and so does x. That is the linear-system solution.
🙋
Then how does this differ from solving the normal equations At A x = At b? My textbook teaches that first.
🎓
Mathematically the same answer, but numerically very different. Forming At A squares the condition number to kappa(A)^2. If kappa(A) is 1e6, then kappa(At A) is 1e12 - you lose 12 of the 15 double-precision digits. Going through QR keeps the condition number at kappa(A) and you only lose about half. That is why modern libraries (NumPy lstsq, MATLAB backslash) use QR or SVD internally. Textbooks teach the normal equations first because the derivation is intuitive, but in implementation you should avoid them.
🙋
Why is "Modified" Gram-Schmidt used? What is wrong with the classical version?
🎓
Classical Gram-Schmidt (CGS) is numerically fragile. It subtracts all previous orthogonal components at once, so rounding errors accumulate and the resulting Q can lose orthogonality (||Qt Q - I|| around 1e-3). Modified Gram-Schmidt subtracts one basis at a time and reuses the updated vector, so the error stays around 1e-15. The "Orthogonality error" card in this tool quantifies exactly that difference. In production code people often use the even more robust Householder transformation, but MGS is the most natural for understanding the concept.
Frequently Asked Questions
Classical Gram-Schmidt (CGS) subtracts all previously computed orthogonal components from each column at once, while Modified Gram-Schmidt (MGS) subtracts them one basis vector at a time using updated intermediate vectors. They are mathematically equivalent but in finite precision arithmetic, CGS rapidly loses orthogonality whereas MGS keeps the error close to machine epsilon. In practice, MGS or the more robust Householder transformation is preferred.
The normal equations At A x = At b have a condition number of kappa(A)^2, which is numerically unstable. With A=QR, however, the residual norm satisfies ||Ax-b||^2 = ||Rx-Qt b||^2, so back-substitution on Rx=Qt b only carries condition number kappa(A) and is far more stable. As long as the columns of A are linearly independent, the solution is unique and the cost is comparable.
Householder transformations apply reflection matrices in sequence to triangularize A. They give even better orthogonality than MGS and tend to preserve sparse structure. The LAPACK routine geqrf is also Householder based. Gram-Schmidt, on the other hand, orthogonalizes one column at a time, which makes it convenient for streaming data or partial orthogonalization inside iterative solvers such as GMRES.
Yes, the QR algorithm is the standard method for eigenvalue computation. By factoring A_k = Q_k R_k and forming A_{k+1} = R_k Q_k repeatedly, A_k converges to an upper-triangular matrix whose diagonal entries are the eigenvalues. Combined with shift strategies (such as the Wilkinson shift), convergence becomes very fast and the QR algorithm sits at the core of nearly every eigenvalue solver, including LAPACK dgeev. This tool visualizes a single QR step.
Real-World Applications
Linear regression and statistical modeling: Polynomial fits, multiple regression, and machine-learning least-squares problems are all essentially least-squares solutions of Ax=b. R's lm function, Python's numpy.linalg.lstsq, and MATLAB's backslash operator perform QR (or SVD) internally. Parameter fitting in CAE workflows, least-squares fits of fluid drag coefficients, and many other engineering tasks rely on it directly.
Iterative solvers in finite element analysis: Krylov-subspace methods such as GMRES (Generalized Minimal Residual) build orthonormal bases by performing Modified Gram-Schmidt at every iteration. It sits at the heart of CFD and structural Krylov solvers; with long vectors, classical Gram-Schmidt diverges, so MGS (or DGKS reorthogonalization) is mandatory.
Eigenvalue computation and PCA: Principal component analysis and modal analysis rely on the QR algorithm as the standard eigenvalue extraction routine. Iterating the single QR step shown by this tool until the matrix becomes upper triangular yields the eigenvalues used in structural natural frequency analysis or feature extraction in machine learning.
Sensor fusion and Kalman filtering: Square-root Kalman filters update the Cholesky factor (or QR factor) of the covariance matrix directly to avoid numerical instability. GPS+IMU fusion, robotic control, and aerospace attitude estimation all rely on QR decomposition where real-time response and numerical stability must coexist.
Common Misconceptions and Pitfalls
The most common misconception is that QR decomposition only works for square matrices. In fact, it applies to any m x n matrix with m >= n and is the standard tool for solving overdetermined least-squares problems where the number of equations m is much larger than the number of unknowns n. This tool uses 3x3 for visualization, but the Modified Gram-Schmidt logic shown here extends directly to rectangular matrices simply by changing the loop bounds. In practice, very tall matrices (m=10000, n=10 for example) are common.
The next common pitfall is assuming that Q is orthogonal so Qt Q = I will hold exactly in numerical computation. In theory yes, but in finite precision arithmetic, error always sneaks in. The "Orthogonality error" card here shows around 1e-15 (machine epsilon for double precision) precisely because Modified Gram-Schmidt is so good. With Classical Gram-Schmidt on an ill-conditioned matrix, the same error can jump to 1e-3 or worse. The iron rule is: always verify orthogonality after computation.
Finally, note that this simulator works with a special matrix family where most entries are fixed. Only the three diagonal entries of A and the first component of b are sliders; the off-diagonal entries are fixed at values that yield well-conditioned problems. In real applications you may face matrices with condition number above 1e8, where even MGS sees increased orthogonality error. This tool is for conceptual understanding and well-conditioned cases; for highly ill-conditioned problems, prefer Householder transformations or singular value decomposition (SVD).