Skip to main content

forward_error_bound

Function forward_error_bound 

Source
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.