pub fn forward_error_bound(
a: &CsrMatrix<f64>,
r: &[Interval],
solve_transpose: &mut dyn FnMut(&mut [f64]),
opts: &ForwardErrorOptions,
) -> Result<ForwardErrorBound, VerifyError>Expand description
Algorithm E: from r ∋ A x − b (from residual or
residual_of_dd) and a transposed solve (c ← ≈ A⁻ᵀ c, f64),
proves that A is nonsingular and bounds x − A⁻¹b (Theorem E of
Chapter 11.10): if the result is certified, then for the b whose
residual r encloses — precisely, for every x and b with A x − b ∈ r componentwise — ‖x − A⁻¹b‖∞ ≤ norm_inf and |x_p − (A⁻¹b)_p| ≤ componentwise[p], for the stored f64 values of A.
The bound is a theorem whatever solve_transpose returns: a wrong
solve can only prevent the certificate or loosen the bound. It is called
at most n times (at most 2n with
ForwardErrorOptions::refine_rows; fewer when it stops early), each
time on a vector of length n.
use xingo_extprec::verify::{
ForwardErrorOptions, forward_error_bound, residual,
};
use xingo_sparse::CsrMatrix;
// [[2, 1], [1, 3]] x = (1, 1): x* = (2/5, 1/5), not representable.
let a = CsrMatrix::from_raw_parts(2, vec![0, 2, 4], vec![0, 1, 0, 1],
vec![2.0, 1.0, 1.0, 3.0]).unwrap();
let (b, x) = ([1.0, 1.0], [0.4, 0.2]);
// Aᵀ = A: the transposed solve is the exact inverse, rounded.
let mut solve_t = |c: &mut [f64]| {
let (p, q) = (c[0], c[1]);
c[0] = (3.0 * p - q) / 5.0;
c[1] = (2.0 * q - p) / 5.0;
};
let r = residual(&a, &x, &b).unwrap();
let e = forward_error_bound(&a, &r, &mut solve_t, &ForwardErrorOptions::default())
.unwrap();
assert!(e.is_certified() && e.contraction < 1e-15);
// |0.4 − 2/5| and |0.2 − 1/5| are below 2⁻⁵⁴ and 2⁻⁵⁵.
assert!(e.norm_inf < 1e-16 && e.componentwise[1] < 1e-16);§Errors
VerifyError::Dimension if a is not square or r does not have
one entry per row.
§Panics
If a violates the invariants of its type.