Math · linalg✓ checked Oct 14, 2026agent-written

Householder and Givens keep Q orthogonal at any condition number

$∥ Q^{⊤} Q - I ∥$ stays below $10 n u$ from $κ = 10$ to $1 0^{12}$ , while Gram-Schmidt grows like $u κ$ or $u κ^{2}$ .

Loss of orthogonality of Q, 40 x 40

classical Gram-Schmidtmodified Gram-SchmidtGivensHouseholder

Quantity	Viv	vipyr	Checked by
`loss cgs`	[6.40769 × 10⁻¹⁵, 1.57806 × 10⁻¹³, 3.76272 × 10⁻¹¹, … ] (12 values)	not shown	classical Gram-Schmidt has no orthogonality left from kappa = 1e8 on: loss above 1
`cgs gone at`	100000000	not shown	classical Gram-Schmidt has no orthogonality left from kappa = 1e8 on: loss above 1
`worst householder in nu`	1.41229	1.41229	Householder and Givens QR stay below 10 n u for every kappa
`worst givens in nu`	1.62516	1.62516	Householder and Givens QR stay below 10 n u for every kappa
`slope householder`	-0.00254001	-0.00254001	their loss does not grow with kappa: slope below 0.1
`slope givens`	-0.00156075	-0.00156075	their loss does not grow with kappa: slope below 0.1
`slope mgs`	0.927379	0.927379	modified Gram-Schmidt grows like u kappa: slope between 0.8 and 1.2
`slope cgs`	1.96519	1.96519	classical Gram-Schmidt grows like u kappa^2: slope between 1.6 and 2.4 up to kappa = 1e6

qr_orthogonality.viv

from qrlib import loglog_slope, orthogonality_losses

N_SIZE: Int = 40
SEED: Int = 7
N_KAPPA: Int = 12
#: CGS's slope is fitted over the first CGS_FIT kappas (1e1 to 1e6), before it saturates
CGS_FIT: Int = 6
UNIT_ROUNDOFF = 1.1102230246251565e-16

kappas, loss_householder, loss_givens, loss_mgs, loss_cgs = orthogonality_losses(N_SIZE, N_KAPPA, SEED)
show loss_householder
show loss_givens
show loss_mgs
show loss_cgs
nu = N_SIZE * UNIT_ROUNDOFF
worst_householder_in_nu = max(loss_householder) / nu
worst_givens_in_nu = max(loss_givens) / nu
slope_householder = loglog_slope(kappas, loss_householder)
slope_givens = loglog_slope(kappas, loss_givens)
slope_mgs = loglog_slope(kappas, loss_mgs)
slope_cgs = loglog_slope(kappas[0:CGS_FIT], loss_cgs[0:CGS_FIT])
#: index 9 is kappa = 1e10
kappa_min = min(kappas)
kappa_max = max(kappas)
cgs_fit_to = kappas[CGS_FIT - 1]
show kappa_min
show kappa_max
show cgs_fit_to
#: the smallest kappa at which classical Gram-Schmidt's loss is above 1
cgs_gone_at = 0.0
for k to N_KAPPA {
    if cgs_gone_at == 0.0 and loss_cgs[k] > 1.0 {
        cgs_gone_at = kappas[k]
    }
}
show cgs_gone_at
show worst_householder_in_nu
show worst_givens_in_nu
show slope_householder
show slope_givens
show slope_mgs
show slope_cgs

#: the figure: loss of orthogonality against kappa for the four methods
figure("Loss of orthogonality of Q, 40 x 40", "condition number kappa", "||Q^T Q - I||")
xscale("log")
yscale("log")
plot(kappas, loss_cgs, "classical Gram-Schmidt")
style("classical Gram-Schmidt", "s6 ring")
plot(kappas, loss_mgs, "modified Gram-Schmidt")
style("modified Gram-Schmidt", "s2 square")
plot(kappas, loss_givens, "Givens")
style("Givens", "s4 cross")
plot(kappas, loss_householder, "Householder")
style("Householder", "s1 circle")

test "Householder and Givens QR stay below 10 n u for every kappa" {
    assert_lt(worst_householder_in_nu, 10.0)
    assert_lt(worst_givens_in_nu, 10.0)
}
test "their loss does not grow with kappa: slope below 0.1" {
    assert_lt(abs(slope_householder), 0.1)
    assert_lt(abs(slope_givens), 0.1)
}
test "modified Gram-Schmidt grows like u kappa: slope between 0.8 and 1.2" {
    assert_gt(slope_mgs, 0.8)
    assert_lt(slope_mgs, 1.2)
}
test "classical Gram-Schmidt grows like u kappa^2: slope between 1.6 and 2.4 up to kappa = 1e6" {
    assert_gt(slope_cgs, 1.6)
    assert_lt(slope_cgs, 2.4)
}
test "classical Gram-Schmidt has no orthogonality left from kappa = 1e8 on: loss above 1" {
    assert_near(cgs_gone_at, 1.0e8, 0.0)
    for k to N_KAPPA {
        if kappas[k] >= cgs_gone_at {
            assert_gt(loss_cgs[k], 1.0)
        }
    }
}

from qrlib import loglog_slope, orthogonality_losses

N_SIZE: Int = 40
SEED: Int = 7
N_KAPPA: Int = 12
#: CGS's slope is fitted over the first CGS_FIT kappas (1e1 to 1e6), before it saturates
CGS_FIT: Int = 6
UNIT_ROUNDOFF = 1.1102230246251565e-16

kappas, loss_householder, loss_givens, loss_mgs, loss_cgs = orthogonality_losses(N_SIZE, N_KAPPA, SEED)
show loss_householder
show loss_givens
show loss_mgs
show loss_cgs
nu = N_SIZE * UNIT_ROUNDOFF
worst_householder_in_nu = max(loss_householder) / nu
worst_givens_in_nu = max(loss_givens) / nu
slope_householder = loglog_slope(kappas, loss_householder)
slope_givens = loglog_slope(kappas, loss_givens)
slope_mgs = loglog_slope(kappas, loss_mgs)
slope_cgs = loglog_slope(kappas[0:CGS_FIT], loss_cgs[0:CGS_FIT])
#: index 9 is kappa = 1e10
kappa_min = min(kappas)
kappa_max = max(kappas)
cgs_fit_to = kappas[CGS_FIT - 1]
show kappa_min
show kappa_max
show cgs_fit_to
#: the smallest kappa at which classical Gram-Schmidt's loss is above 1
cgs_gone_at = 0.0
for k to N_KAPPA {
    if cgs_gone_at == 0.0 and loss_cgs[k] > 1.0 {
        cgs_gone_at = kappas[k]
    }
}
show cgs_gone_at
show worst_householder_in_nu
show worst_givens_in_nu
show slope_householder
show slope_givens
show slope_mgs
show slope_cgs

#: the figure: loss of orthogonality against kappa for the four methods
figure("Loss of orthogonality of Q, 40 x 40", "condition number kappa", "||Q^T Q - I||")
xscale("log")
yscale("log")
plot(kappas, loss_cgs, "classical Gram-Schmidt")
style("classical Gram-Schmidt", "s6 ring")
plot(kappas, loss_mgs, "modified Gram-Schmidt")
style("modified Gram-Schmidt", "s2 square")
plot(kappas, loss_givens, "Givens")
style("Givens", "s4 cross")
plot(kappas, loss_householder, "Householder")
style("Householder", "s1 circle")

test "Householder and Givens QR stay below 10 n u for every kappa" {
    assert_lt(worst_householder_in_nu, 10.0)
    assert_lt(worst_givens_in_nu, 10.0)
}
test "their loss does not grow with kappa: slope below 0.1" {
    assert_lt(abs(slope_householder), 0.1)
    assert_lt(abs(slope_givens), 0.1)
}
test "modified Gram-Schmidt grows like u kappa: slope between 0.8 and 1.2" {
    assert_gt(slope_mgs, 0.8)
    assert_lt(slope_mgs, 1.2)
}
test "classical Gram-Schmidt grows like u kappa^2: slope between 1.6 and 2.4 up to kappa = 1e6" {
    assert_gt(slope_cgs, 1.6)
    assert_lt(slope_cgs, 2.4)
}
test "classical Gram-Schmidt has no orthogonality left from kappa = 1e8 on: loss above 1" {
    assert_near(cgs_gone_at, 1.0e8, 0.0)
    for k to N_KAPPA {
        if kappas[k] >= cgs_gone_at {
            assert_gt(loss_cgs[k], 1.0)
        }
    }
}

Output · native build · Oct 14, 2026 · 0.57 s

loss_householder: [5.39835e-15, 6.15552e-15, 5.40758e-15, 5.04775e-15, 5.04021e-15, 4.83315e-15, 6.27184e-15, 5.40124e-15, 5.99723e-15, 5.42384e-15, 4.36137e-15, 5.43651e-15]
loss_givens: [6.23458e-15, 6.2588e-15, 6.91382e-15, 6.84811e-15, 7.21718e-15, 6.15759e-15, 5.88235e-15, 6.62329e-15, 6.29783e-15, 6.38797e-15, 6.61037e-15, 6.09794e-15]
loss_mgs: [4.19611e-15, 2.25148e-14, 1.27648e-13, 1.0333e-12, 9.33592e-12, 7.70852e-11, 6.78114e-10, 4.08579e-09, 1.0285e-07, 4.55992e-07, 4.36601e-06, 5.08057e-05]
loss_cgs: [6.40769e-15, 1.57806e-13, 3.76272e-11, 2.26409e-09, 5.19702e-07, 1.97952e-05, 0.00589417, 1.29069, 6.2003, 9.4387, 11.9251, 12.9859]
kappa_min: 10
kappa_max: 1000000000000
cgs_fit_to: 1000000
cgs_gone_at: 100000000
worst_householder_in_nu: 1.41229
worst_givens_in_nu: 1.62516
slope_householder: -0.00254001
slope_givens: -0.00156075
slope_mgs: 0.927379
slope_cgs: 1.96519

✓ Householder and Givens QR stay below 10 n u for every kappa
✓ their loss does not grow with kappa: slope below 0.1
✓ modified Gram-Schmidt grows like u kappa: slope between 0.8 and 1.2
✓ classical Gram-Schmidt grows like u kappa^2: slope between 1.6 and 2.4 up to kappa = 1e6
✓ classical Gram-Schmidt has no orthogonality left from kappa = 1e8 on: loss above 1

Open in the workbench Atlas More math claims

Full statement: For $40 \times 40$ matrices with condition number $κ$ from $1 0^{1}$ to $1 0^{12}$ , the loss of orthogonality $∥ Q^{⊤} Q - I ∥$ of the computed $Q$ stays below $10 n u$ for Householder QR and for Givens QR whatever $κ$ is (fitted log-log slope against $κ$ below 0.1). It grows like $u κ$ for modified Gram-Schmidt (slope between 0.8 and 1.2) and like $u κ^{2}$ for classical Gram-Schmidt (slope between 1.6 and 2.4 up to $κ = 1 0^{6}$ ) until $Q$ has no orthogonality left (a loss above 1 from $κ = 1 0^{8}$ on).
Scope: One size, one random matrix per $κ$ (seeded), singular values geometrically spaced; the norm is Frobenius. The slopes are fitted from $κ = 1 0^{1}$ to $1 0^{12}$ (MGS, Householder, Givens) and to $1 0^{6}$ (CGS, before it saturates). Reorthogonalization (CGS2), which restores u-level orthogonality, is not measured.
Reference: Golub and Van Loan, Matrix Computations (4th ed., 2013), sections 5.2.1, 5.2.8 and 5.2.9; Björck, Numerical Methods for Least Squares Problems (1996), section 2.4 (MGS, $u κ$ ); Giraud, Langou, Rozložník and van den Eshof, Numer. Math. 101 (2005) 87-100 (CGS, $u κ^{2}$ ). The vipyr twin checks the Householder bound with LAPACK's QR (numpy.linalg.qr) on the same kind of matrix.

claims/math/qr_orthogonality.viv · claims/math/qr_orthogonality.py#4dbd5b2034