#![allow(clippy::cast_precision_loss)]
#[must_use]
pub fn richardson2<const N: usize>(
x1: &[f64; N],
t1: f64,
x2: &[f64; N],
t2: f64,
alpha: f64,
) -> [f64; N] {
let (u1, u2) = (libm::pow(t1, alpha), libm::pow(t2, alpha));
let inv = 1.0 / (u2 - u1);
core::array::from_fn(|i| (u2 * x1[i] - u1 * x2[i]) * inv)
}
#[must_use]
pub fn richardson_extrapolate<const N: usize, const M: usize>(
nodes: &[f64; M],
values: &[[f64; N]; M],
alpha: f64,
) -> ([f64; N], f64) {
let u: [f64; M] = core::array::from_fn(|i| libm::pow(nodes[i], alpha));
let mut prev = [[0.0; N]; M]; let mut row = [[0.0; N]; M];
let mut err = 0.0;
for i in 0..M {
row = [[0.0; N]; M];
row[0] = values[i];
for c in 1..=i {
let denom = u[i - c] / u[i] - 1.0;
for k in 0..N {
row[c][k] = row[c - 1][k] + (row[c - 1][k] - prev[c - 1][k]) / denom;
}
}
if i >= 1 {
err = libm::sqrt(
(0..N)
.map(|k| {
let d = row[i][k] - row[i - 1][k];
d * d
})
.sum(),
);
}
prev = row;
}
(row[M - 1], err)
}
#[cfg(test)]
mod tests {
#![allow(clippy::cast_precision_loss)]
use super::*;
#[test]
fn the_reported_error_is_the_gap_between_the_last_two_orders() {
let f = |h: f64| 5.0 + 3.0 * h + 7.0 * h * h;
let nodes = [4.0, 2.0, 1.0];
let values: [[f64; 1]; 3] = core::array::from_fn(|i| [f(nodes[i])]);
let (value, err) = richardson_extrapolate::<1, 3>(&nodes, &values, 1.0);
assert!((value[0] - 5.0).abs() < 1e-12, "T₂,₂ = {}", value[0]);
assert!((err - 14.0).abs() < 1e-12, "err = {err}");
}
#[test]
fn accelerates_a_one_over_k_sequence() {
let x_star = 5.0;
let seq = |k: f64| [x_star + 3.0 / k - 2.0 / (k * k) + 0.5 / (k * k * k)];
let nodes = [10.0, 20.0, 40.0];
let values = [seq(10.0), seq(20.0), seq(40.0)];
let (ext, err) = richardson_extrapolate(&nodes, &values, -1.0);
let raw_err = (values[2][0] - x_star).abs(); let ext_err = (ext[0] - x_star).abs();
println!(
"1/k accel: raw(k=40) err {raw_err:.3e}, Richardson err {ext_err:.3e}, gauge {err:.3e}"
);
assert!(
ext_err < raw_err / 100.0,
"extrapolation did not accelerate: {ext_err:.3e} vs {raw_err:.3e}"
);
}
#[test]
fn debiases_ridge_regression() {
let (s, beta) = (4.0_f64, 2.0_f64); let ridge = |lam: f64| [s * beta / (s + lam)];
let lam = 0.1;
let deb = richardson2(&ridge(lam), lam, &ridge(2.0 * lam), 2.0 * lam, 1.0);
let ridge_bias = (ridge(lam)[0] - beta).abs();
let deb_bias = (deb[0] - beta).abs();
println!("ridge debias: ridge(λ) bias {ridge_bias:.3e}, debiased bias {deb_bias:.3e}");
assert!(
deb_bias < ridge_bias / 20.0,
"debiasing failed: {deb_bias:.3e} vs {ridge_bias:.3e}"
);
let deb_half = richardson2(&ridge(lam / 2.0), lam / 2.0, &ridge(lam), lam, 1.0);
let ratio = deb_bias / (deb_half[0] - beta).abs();
assert!(ratio > 3.0, "debiased bias is not O(λ²) (ratio {ratio:.2})");
}
#[test]
fn two_point_matches_the_tableau() {
let x1 = [1.25, -0.5];
let x2 = [1.10, -0.2];
let (t1, t2, a) = (0.2, 0.4, 1.0);
let closed = richardson2(&x1, t1, &x2, t2, a);
let (tab, _) = richardson_extrapolate(&[t1, t2], &[x1, x2], a);
for i in 0..2 {
assert!(
(closed[i] - tab[i]).abs() < 1e-14,
"axis {i}: {} vs {}",
closed[i],
tab[i]
);
}
}
}