Numerical Linear Algebra
where the algebra stops being the arithmetic
Generator

weighting-limit

One function in the lse library, called 11 times across 3 essays. Below: what it draws at its defaults, what it draws at every value an essay asks for, the 11 claims it put to the test while drawing them, and where it stands against the rule this site is named for.

At its defaults it draws minimise ‖ax − b‖ subject to bx = d, solved as a weighted least-squares problem, three ways. Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 14.3. Householder QR has no such ceiling and is at 4.8·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 4.9·10¹⁰.

weighting-limit is one function in lib/figures/lse.js — a constraint as a weight — the limit, the ceiling that belongs to the solver, and the order of the rows. Everything below came out of it during this build, at arguments taken from the essays rather than invented for this page. A figure here is the figure a reader meets in an essay, and if the generator changes, this page changes with it.

At its defaults

Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 14.3. Householder QR has no such ceiling and is at 4.8·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 4.9·10¹⁰.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 14.3. Householder QR has no such ceiling and is at 4.8·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 4.9·10¹⁰.

cons: 2

The arguments are the ones A constraint is a weight at infinity passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 14.3. Householder QR has no such ceiling and is at 4.8·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 4.9·10¹⁰.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 14.3. Householder QR has no such ceiling and is at 4.8·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 4.9·10¹⁰.

cons: 1

The arguments are the ones A constraint is a weight at infinity passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 35.3. Householder QR has no such ceiling and is at 1.35·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 0.74.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴1.4·10⁻¹⁵normal equations35Gram–Schmidt0.741/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 35.3. Householder QR has no such ceiling and is at 1.35·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 0.74.

rows: 20

The arguments are the ones A constraint is a weight at infinity passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 2.62. Householder QR has no such ceiling and is at 6.55·10⁻¹⁶ at the same weight. Classical Gram–Schmidt is worse than either, at 1.24·10¹¹.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴6.6·10⁻¹⁶normal equations2.6Gram–Schmidt1.2·10¹¹1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 2.62. Householder QR has no such ceiling and is at 6.55·10⁻¹⁶ at the same weight. Classical Gram–Schmidt is worse than either, at 1.24·10¹¹.

cons: 3

The arguments are the ones A constraint is a weight at infinity passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 1.45. Householder QR has no such ceiling and is at 3.29·10⁻¹⁶ at the same weight. Classical Gram–Schmidt is worse than either, at 5.09·10¹¹.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴3.3·10⁻¹⁶normal equations1.4Gram–Schmidt5.1·10¹¹1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 1.45. Householder QR has no such ceiling and is at 3.29·10⁻¹⁶ at the same weight. Classical Gram–Schmidt is worse than either, at 5.09·10¹¹.

cons: 4

The arguments are the ones A constraint is a weight at infinity passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 0.575. Householder QR has no such ceiling and is at 6.04·10⁻¹⁶ at the same weight. Classical Gram–Schmidt is worse than either, at 2.69·10¹¹.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴6·10⁻¹⁶normal equations0.57Gram–Schmidt2.7·10¹¹1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

Stack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 0.575. Householder QR has no such ceiling and is at 6.04·10⁻¹⁶ at the same weight. Classical Gram–Schmidt is worse than either, at 2.69·10¹¹.

What it checked while drawing

Every figure above asserted its own claims on the way to being drawn, and a claim that failed would have failed the build rather than drawn a wrong picture. Those assertions used to leave no trace at all: a passing one returned true and the only evidence the figure had checked anything was that nothing crashed. The list below is what they actually said, collected by running this generator with an observer installed — not a description of what it is believed to check.

11 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.

a finite double, since an infinity is not a rational

a method this file implements

a problem with more data than unknowns

a problem with more data than unknowns and fewer constraints

a row order this file implements

and the normal equations have no digits at the far end

Householder QR reaches the rounding level

LU is for square matrices

matmul shapes agree

the error falls as the square of the weight

the optimality conditions have a solution

Against the rule

It draws a decomposition and prints its residual. It calls weightingSweep, and every figure above carries the badge — which residualcheck verifies by looking for it in the emitted SVG rather than by finding the call that builds one. A badge that is constructed and then left out of the body is the failure that check exists for.

Across the library: the rule bites on 165 of 306 generators — 150 print a residual and 15 are exempt with a published reason; 141 factorise nothing. Read from lib/residual-rule.js, which is the same body the gate enforces from, and the gate's last check fails the build if this page and it disagree about any generator.

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

Least squares, and the road not to take

A constraint is a weight at infinity

Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.

 The matrix a constraint makes

A preconditioner that need not know the constraint

Keep the constraint block exactly and replace the objective block by anything positive definite on the null space. The preconditioned matrix then has 2m eigenvalues at exactly one, and its remaining n − m are the generalised eigenvalues of a pencil in which the constraint does not appear. Sweep its condition number over six decades and they do not move in six digits.

 Randomised, and the guarantee that changes kind

The half of a problem a sketch may touch

A sketch guarantees that a norm is preserved to within a factor. An equality constraint is a statement that a quantity is zero, and no multiplicative guarantee says anything about zero. Sketch a constrained problem written as a weighted one and the constraint is not destroyed — it is demoted, from a violation of 1/τ² to one of ε/τ, exactly half the exponent.

The whole library · All essays · What must fail