1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
;;; Copyright (c) 2026 Nicholas Vermeulen
;;; SPDX-License-Identifier: AGPL-3.0-or-later
;; interp.lisp — polynomial (Lagrange) and piecewise-linear interpolation with
;; error envelopes measured on a DECLARED verification grid. Pure Lisp, zero
;; interpreter changes.
;;
;; Nodes are `((x0 y0) (x1 y1) …)` in ascending x. `lagrange-eval` evaluates
;; the unique degree-(n-1) interpolant through the nodes; `plin-eval` evaluates
;; the piecewise-linear interpolant (end segments extended for x outside the
;; node range — documented, not hidden). `max-abs-residual` is the max
;; |f(x) − g(x)| over an explicit finite grid — an error bound ON THAT GRID.
;;
;; THE VERIFICATION BITE: with nodes at {-1, 0, 1} every Lagrange basis
;; denominator is ±1 or ±2, so evaluation at integer x is EXACT dyadic
;; arithmetic — "the interpolant through 3 samples of a quadratic reproduces
;; the quadratic" is checkable with exact `=` over a real coefficient×grid
;; product, not an epsilon. The same claim for piecewise-linear is FALSE and
;; is refused with the offending coefficients as witnesses.
;;
;; PORTABILITY: only + - * / (no libm). Division-only floats are IEEE-
;; correctly-rounded and therefore bit-stable across platforms (root.lisp
;; precedent), so the Runge residuals below may be printed raw.
;;
;; CLAIM DISCIPLINE — the caveat is the crack: an error bound here is a bound
;; on the DECLARED verification grid, NEVER a continuous supremum ("max error
;; on [-1,1]") and NEVER a convergence claim. The Runge demonstration is the
;; negative control that more degree does NOT mean less error.
;; ── Node helpers ──────────────────────────────────────────────────────────
;; ── Lagrange interpolation ────────────────────────────────────────────────
;; basis_i(x) = Π_{j≠i} (x − xj)/(xi − xj); L(x) = Σ yi·basis_i(x).
;; ── Piecewise-linear interpolation ────────────────────────────────────────
;; Segment [xi, xi+1] containing x (end segments extended beyond the range).
;; ── Residual on a declared grid ───────────────────────────────────────────
;; ── Exhaustive verification ───────────────────────────────────────────────
;; (1) Lagrange through samples of ax²+bx+c at nodes {-1,0,1} reproduces the
;; quadratic EXACTLY at every x in the verification grid {-2,…,2} — for every
;; coefficient triple in the domain. Exact `=`: basis denominators are ±1/±2,
;; so all arithmetic is dyadic. A real 3-D coefficient domain.
;; (2) The same claim for PIECEWISE-LINEAR is false whenever a ≠ 0 — refused
;; with the coefficients as witnesses (the a = 0 rows genuinely pass).
;; ── Runge demonstration (honest negative control) ─────────────────────────
;; f(x) = 1/(1+25x²) interpolated at 5 equispaced nodes on [-1,1]: the
;; degree-4 interpolant's residual at the declared midpoints is LARGE, and
;; piecewise-linear through the same nodes is far smaller — degree does not
;; buy accuracy. Division-only arithmetic; the residuals are printable floats.