QR Decomposition: Any matrix A can be factored as A = QR where Q is orthogonal and R is upper triangular
Orthogonal Matrix: Q^T Q = I (columns are orthonormal vectors)
Upper Triangular Matrix: All entries below diagonal are zero
- Start with linearly independent vectors {v₁, v₂, ..., vₙ}
- Initialize: u₁ = v₁, e₁ = u₁/||u₁||
- Iterate: For k = 2 to n, uₖ = vₖ - Σᵢ₌₁ᵏ⁻¹ projuᵢ(vₖ)
- Normalize: eₖ = uₖ/||uₖ||
• Vector projection: proju(v) = (u·v)/(u·u) × u
• Gram-Schmidt: uₖ = vₖ - Σᵢ₌₁ᵏ⁻¹ projuᵢ(vₖ)
• Normalization: eₖ = uₖ/||uₖ||
• Orthogonal matrix: Q^T Q = I
QR Decomposition: A = QR where Q has orthonormal columns and R is upper triangular
- Take columns of A as input vectors
- Apply Gram-Schmidt process
- Form Q from normalized vectors
- Compute R using inner products
v₁ = [3, 4], v₂ = [1, 0]
u₁ = v₁ = [3, 4]
||u₁|| = √(3² + 4²) = √25 = 5
e₁ = u₁/||u₁|| = [3/5, 4/5]
proju₁(v₂) = (u₁·v₂)/(u₁·u₁) × u₁
u₁·v₂ = 3×1 + 4×0 = 3
u₁·u₁ = 3² + 4² = 25
proju₁(v₂) = (3/25) × [3, 4] = [9/25, 12/25]
u₂ = v₂ - proju₁(v₂) = [1, 0] - [9/25, 12/25] = [16/25, -12/25]
||u₂|| = √((16/25)² + (-12/25)²) = √(256 + 144)/25 = √400/25 = 20/25 = 4/5
e₂ = u₂/||u₂|| = [16/25, -12/25] ÷ (4/5) = [4/5, -3/5]
Q = [e₁ e₂] =
R =
A = QR where Q has orthonormal columns and R is upper triangular
• Gram-Schmidt: Orthogonalize vectors systematically
• Normalization: Divide by norm to get unit vectors
• Projection: Remove components parallel to previous vectors
3x3 QR Decomposition: Extend Gram-Schmidt to higher dimensions
v₁ = [1, 1, 0], v₂ = [1, 0, 1], v₃ = [0, 1, 1]
u₁ = v₁ = [1, 1, 0]
||u₁|| = √(1² + 1² + 0²) = √2
e₁ = [1/√2, 1/√2, 0]
proju₁(v₂) = (u₁·v₂)/(u₁·u₁) × u₁ = (1×1 + 1×0 + 0×1)/(1² + 1² + 0²) × [1, 1, 0] = (1/2) × [1, 1, 0] = [1/2, 1/2, 0]
u₂ = v₂ - proju₁(v₂) = [1, 0, 1] - [1/2, 1/2, 0] = [1/2, -1/2, 1]
||u₂|| = √((1/2)² + (-1/2)² + 1²) = √(1/4 + 1/4 + 1) = √3/2
e₂ = [1/(√6), -1/(√6), 2/(√6)]
proju₁(v₃) = (u₁·v₃)/(u₁·u₁) × u₁ = (1×0 + 1×1 + 0×1)/2 × [1, 1, 0] = [1/2, 1/2, 0]
proju₂(v₃) = (u₂·v₃)/(u₂·u₂) × u₂ = (1/2×0 + (-1/2)×1 + 1×1)/3/2 × [1/2, -1/2, 1] = (1/2)/(3/2) × [1/2, -1/2, 1] = [1/6, -1/6, 1/3]
u₃ = v₃ - proju₁(v₃) - proju₂(v₃) = [0, 1, 1] - [1/2, 1/2, 0] - [1/6, -1/6, 1/3] = [-2/3, 2/3, 2/3]
Q has orthonormal columns, R is upper triangular
• Higher dimensions: Extend Gram-Schmidt iteratively
• Multiple projections: Subtract all previous projections
• Orthogonality check: Verify eᵢ·eⱼ = 0 for i ≠ j
Verification: Confirm QR decomposition by computing QR and comparing to A
Q =
QR =
=
QR = A, confirming our decomposition is correct
• Matrix multiplication: Row by column rule
• Verification: Essential to confirm correctness
• Arithmetic: Careful calculation of fractions
Orthogonal Matrix: Q is orthogonal if Q^T Q = I (identity matrix)
Q =
Q^T =
Q^T Q =
=
Q is indeed orthogonal since Q^T Q = I
• Transpose property: (Q^T)ᵢⱼ = Qⱼᵢ
• Orthogonality: Columns are orthonormal vectors
• Identity verification: Diagonal ones, off-diagonal zeros
QR Solution Method: Ax = b becomes QRx = b, then Rx = Q^T b
Q =
Ax = b → QRx = b → Rx = Q^T b
Q^T b =
From second equation: (4/5)x₂ = 2/5 → x₂ = 1/2
From first equation: 5x₁ + (3/5)(1/2) = 39/5 → 5x₁ + 3/10 = 39/5 → 5x₁ = 39/5 - 3/10 = 78/10 - 3/10 = 75/10 = 15/2 → x₁ = 3/2
x₁ = 3/2, x₂ = 1/2
• QR method: More stable than direct inversion
• Back substitution: Solve upper triangular systems efficiently
• Orthogonality advantage: Q^T = Q^(-1) simplifies computation