[Intermediate] · Worked answers to note 11. Measured, not estimated, Python 3.14, August 2026.
Part A — Error and conditioning
1. The U-curve
Measured, , :
| error | error | |||
|---|---|---|---|---|
| 4.29e-02 | 2.97e-09 ← minimum | |||
| 4.21e-05 | 5.85e-08 | |||
| 4.21e-07 | 7.34e-04 | |||
| 4.18e-08 | 5.40e-01 |
The two arms:
Left (large ): truncation error, for a forward difference — the error falls linearly, exactly one decade per decade, which you can see in the table.
Right (small ): round-off error, . and agree to more and more digits, so subtracting them cancels the leading digits and you divide the surviving noise by a tiny , amplifying it.
The minimum is predictable without measuring anything. Total error is minimised at — and the measured minimum is at .
The best achievable accuracy is about , not . You lose half your digits, unavoidably, for this method. That single fact is why central differences (, optimum at ), complex-step differentiation and automatic differentiation exist.
2. Break the quadratic formula
. True small root .
naive : -7.45058059692382812500e-09 ← ~25% wrong
stable: -1.00000000000000002092e-08 ← correct to ~16 digits
The mechanism is catastrophic cancellation. and agree to about 16 significant digits. Subtracting them annihilates every meaningful digit and leaves only representation noise — which is then divided by 2 and reported confidently.
The stable form multiplies numerator and denominator by the conjugate, turning the subtraction into an addition of two same-signed quantities. No cancellation.
The general rule: never subtract two nearly-equal floating-point numbers if algebra can avoid it. The two expressions are identical over the reals and completely different over floats.
3. Hilbert conditioning
Measured, solving where the true is all ones:
| max error | correct digits | |
|---|---|---|
| 5 | 6.17e-13 | ~12 |
| 8 | 1.37e-07 | ~7 |
| 10 | 7.18e-04 | ~3 |
| 12 | 5.95e-03 | ~2 |
Doubles carry ~16 digits. At you have two.
The rule of thumb: you lose about digits. The Hilbert matrix’s condition number grows roughly exponentially — at , at , at , where it exhausts double precision entirely.
Nothing was wrong with the algorithm. Gaussian elimination with pivoting is backward-stable; it returns the exact solution to a slightly perturbed problem. The problem itself amplifies perturbations — that’s what ill-conditioning means, and no algorithm can fix it. Contrast with exercise 7, where the algorithm is at fault.
Always compute before trusting a linear solve.
4. Non-associative addition
Summing copies of 0.1 (exact answer ):
- Left to right — worst. The accumulator grows large while each addend stays small, so each addition rounds away a bit of the small value
- Ascending order — better, for the same reason in reverse: add small things together first, while the accumulator is comparably sized
- Kahan summation — best, essentially exact. It keeps a running compensation term capturing what each addition rounded off, and adds it back
Floating-point addition is commutative but not associative. in general — which means summing an array is order-dependent, and therefore that parallel reductions give different answers than serial ones, and different answers run to run if the reduction order varies. That’s a real reproducibility problem in ML training and in GPU reductions.
Part B — Solving things
5. Race the root-finders
Root of near 2.0946, to from :
| method | iterations | order |
|---|---|---|
| Bisection | ~40 | linear — one bit per step |
| Secant | ~7 | superlinear, |
| Newton | ~5 | quadratic |
You can read the order off your own error sequence. For Newton, the number of correct digits roughly doubles each iteration: 1 → 2 → 5 → 10 → 12. That doubling is quadratic convergence, and seeing it in your own output is the exercise.
Bisection needs 40 steps because it gains exactly digits per step — but it is guaranteed to converge given a sign change, which the other two are not.
6. Break Newton
(a) Flat derivative: with throws the iterate an enormous distance. It may diverge or land in a different basin entirely.
(b) Cycles: from gives forever. Newton has no notion of progress and will not notice.
(c) Multiple roots: on , convergence drops from quadratic to linear — error halves per step instead of squaring. Because vanishes at the root too, the correction is systematically half of what’s needed. (The fix is the modified Newton for known multiplicity .)
The unifying point: Newton is fast and unsafe. Production root-finders (Brent’s method) hybridise — take the fast step when it stays in the bracket, fall back to bisection when it doesn’t. Guaranteed convergence with fast convergence in the common case → note 03.
7. Pivot, or don’t
, . True answer , . — this system is perfectly well-conditioned.
Without pivoting, the multiplier is . Eliminating gives , and in floating point both sides round to , so — fine. Then back-substitution: . Wrong, and badly.
Partial pivoting swaps the rows first so the multiplier is rather than , and everything is exact.
Contrast this with exercise 3, and the contrast is the lesson. There, the problem was ill-conditioned and no algorithm could help. Here the problem is fine and the algorithm was unstable. Distinguishing those two is the core diagnostic skill of the whole domain — one is answered by more precision or a reformulation, the other by a better algorithm.
Part C — Approximation and integration
8. Runge’s phenomenon
Equally-spaced interpolation of : max error is moderate at , worse at , far worse at — with wild oscillation near while the middle fits well.
At Chebyshev nodes (clustered toward the endpoints) the error falls with , converging nicely.
More data made the approximation worse. That’s the result worth internalising, and it’s genuinely counter-intuitive.
Why: the interpolation error carries a factor , which for equally-spaced nodes grows enormously near the interval ends. Chebyshev nodes are exactly the placement that minimises that product’s maximum.
The practical consequence: never fit a high-degree polynomial through equally-spaced data. Use low-degree piecewise fits (splines) or Chebyshev nodes. This is also why high-degree polynomial regression on evenly-sampled data behaves badly at the edges → note 06.
9. Convergence study
. Halving , the ratio of successive errors:
- Trapezoid → ≈ 4. Error , so halving divides error by
- Simpson → ≈ 16. Error , so
This is the most valuable habit in the domain, and it’s a self-test that needs no reference answer. If the theory says and your ratios are 2, your implementation is first-order — you have a bug. If they’re erratic, you’ve hit round-off (the is too small) or your function isn’t smooth enough for the assumed order.
A method whose observed order doesn’t match its claimed order is broken, and this check finds it in five lines.
10. Defeat a quadrature rule
on : the integral converges (to 2) but the integrand is unbounded at 0. Fixed-step rules evaluate at or near and get a huge or infinite value; convergence collapses because the error bounds assume bounded derivatives. Fix: substitution to remove the singularity, or a rule that avoids the endpoint (Gauss–Legendre), or adaptive refinement.
: ~16 oscillations on . Any step that doesn’t resolve them samples essentially arbitrary points, and the estimate is nonsense until is small enough — then it converges normally. Fix: resolve the frequency, or use a method designed for oscillatory integrands (Filon, Levin).
Both failures share a cause: the error bounds assume smoothness the integrand doesn’t have. Reading the assumptions is the skill.
Part D — Dynamics and optimisation
11. Stiffness
Explicit RK4 on is stable only for — roughly . Above that it doesn’t lose accuracy gracefully, it explodes, error growing without bound.
An implicit/BDF solver takes steps sized by the accuracy you asked for, not by stability, and typically needs orders of magnitude fewer.
Stiffness is when stability, not accuracy, dictates the step size. It arises when the system has widely separated timescales — here a fast decay of rate 1000 alongside slow dynamics. The fast mode is uninteresting (it dies immediately) but it governs the step size for any explicit method.
Recognising it matters practically: chemical kinetics, circuits, control systems and stiff PDE discretisations all show it, and “my ODE solver is mysteriously slow” is almost always this → note 08.
12. Conditioning and optimisers
Rosenbrock from :
- Gradient descent: thousands of iterations, or fails to converge in a reasonable budget
- BFGS: roughly 20–40
The explanation is conditioning, not quality. Rosenbrock’s valley is extremely elongated — the Hessian’s condition number is large, so the steepest-descent direction points nearly across the valley rather than along it. Gradient descent zig-zags, taking tiny useful steps.
BFGS builds an approximation to the inverse Hessian, which rescales the space so the valley looks round. In the rescaled coordinates, steepest descent is a good direction.
This is the same from exercise 3, in a different costume, and it’s why preconditioning matters, why input normalisation helps neural network training, and why Adam’s per-parameter scaling works → note 10 · AI & ML.
Related
Source: [reference] — measured August 2026.
Software engineering
Infrastructure & security
Computer science
Hardware & engineering