Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three ways
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.
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 nobody placed would be a picture no essay asked for and no claim was ever checked against.
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 nobody placed would be a picture no essay asked for and no claim was ever checked against.
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 nobody placed would be a picture no essay asked for and no claim was ever checked against.
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 nobody placed would be a picture no essay asked for and no claim was ever checked against.
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 nobody placed would be a picture no essay asked for and no claim was ever checked against.
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 checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks 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.
45 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.
every route satisfies the constraints at ε = 1 — checked 2 times
‖λ‖ is one constant times δ/ε² across three ε and four strains
a constraint family the row orders are measured on
a coupling the dial draws
a distance between the two constraints the sweep measures
a family of third constraint this measures
a family the scale sweep is drawn for
a family the sweep is drawn for
a finite double, since an infinity is not a rational
a fit conditioning the sweep is drawn at
a fit whose difficulty lies in its constraint is solved to the rounding level
a method this file implements
a nearly repeated constraint costs the null-space route digits
a number of constraints the contrast can be drawn at
a problem with more data than unknowns
a problem with more data than unknowns and fewer constraints
a reading of the constrained problem this generator draws
a row order this file implements
an alignment this figure draws
and completely different conditioning once the constraint is eliminated
and costs the saddle-point route far more
and nearly all of what the other loses is the forming rather than the solving
and one whose difficulty lies outside it is not
and the normal equations have no digits at the far end
every route returns something measurable
every route satisfies the constraints at ε = 10⁻¹⁰
every route satisfies the constraints at ε = 10⁻¹²
every route satisfies the constraints at ε = 10⁻⁴
every route satisfies the constraints at ε = 10⁻⁶
every route satisfies the constraints at ε = 10⁻⁸
Householder QR reaches the rounding level
LU is for square matrices
matmul shapes agree
the error falls as the square of the weight
the null-space error does not follow the strain
the optimality conditions have a solution
the optimality conditions of the data have a solution
the route that never forms a cross-product keeps the digits the other loses
the two problems have the same κ(A) at 1000
the two problems have the same κ(A) at 10¹²
the two problems have the same κ(A) at 10⁶
the two problems have the same κ(A) at 10⁹
while the problem left after the constraint is far better conditioned than the fit
with the null-space route losing κ(B) times the rounding rather than its square
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 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 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.
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.
Least squares, and the road not to takeA multiplier is a force
A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.
Least squares, and the road not to takeFeasible and wrong
A third constraint that nearly repeats the first takes the best route's answer from 2.96·10⁻¹⁵ to 1.16·10⁻⁴, and the other two routes to no correct digit at all. Every one of those answers satisfies every constraint to 10⁻¹⁵. The quantity a caller checks after a constrained solve is the one quantity here that says nothing.
Least squares, and the road not to takeThe condition number that does not know
Two constrained fits with the same size, the same number of constraints and the same κ(A) to twelve figures. One returns 4.7·10⁻¹⁶ and the other 3.0·10⁻⁴. What separates them is the conditioning of A restricted to the constraint's null space — 1.00 against 10¹² — which every solver computes on the way and none reports.
Randomised, and the guarantee that changes kindThe 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.
Least squares, and the road not to takeThe reference was a method
The optimality conditions of a constrained fit contain AᵀA, so solving them is the road that squares the problem wearing a block structure. At κ(A) = 10¹¹ the route that never forms a cross-product returns 1.89·10⁻⁹ and the route that does returns 4.64·10⁻⁴ — and forming AᵀA and then solving it in exact rationals returns 3.45·10⁻⁴, so nearly all of the loss happens before any elimination begins.
Least squares, and the road not to takeThe scale that only moved a pivot
Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.
Least squares, and the road not to takeThe switch is read before the solve
Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.