omnibias.core.verified.rootfind

0.5.0rc1Release candidatePython >=3.10Apache-2.0

Coefficient recurrences, activation contracts, jet algebra, and verified arithmetic shared by the numerical backends.

import omnibias.core.verified.rootfind

Module contract & mathematical conventions

Verified scalar root isolation -- the rigorous rate/eigenvalue selector.

A self-similar blow-up *rate* is an eigenvalue fixed by a scalar *connection condition* g(c) = 0 (residual minimisation alone leaves it degenerate -- see the certified-evidence research log). This module pins such a c *rigorously*:

certified_sign_change proves a root exists in [a, b] via the intermediate value theorem with certified endpoint signs.
interval_newton proves a root **exists and is unique** in an interval by the interval-Newton test N(X) \subseteq \mathrm{int}(X) and returns a tight enclosure of it.

Both consume callables returning Interval enclosures of g (and, for Newton, g'), so they compose directly with the verified jet / sigma tower.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

CONSTANT

GFn

omnibias.core.verified.rootfind.GFnSource ↗

GFn = Callable[[Interval], Interval]

This exported constant is defined by the expression above. Its exact value and annotation come from the pinned source; use it with the module contract.

Read the implementation

GFn = Callable[[Interval], Interval]

CLASS

NewtonResult

omnibias.core.verified.rootfind.NewtonResultSource ↗

class NewtonResult(TypedDict)

The module contract describes the context for this operation. Its signature, explicit validation, return expressions, and implementation are recorded below.

Fields & methods

statusfield

status: str

Declared str field on NewtonResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

enclosurefield

enclosure: tuple[float, float]

Declared tuple[float, float] field on NewtonResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

widthfield

width: float

Declared float field on NewtonResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

iterationsfield

iterations: int

Declared int field on NewtonResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

uniquefield

unique: bool

Declared bool field on NewtonResult. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

Read the implementation

class NewtonResult(TypedDict):
    status: str
    enclosure: tuple[float, float]
    width: float
    iterations: int
    unique: bool

FUNCTION

bisection_bracket

omnibias.core.verified.bisection_bracketSource ↗

bisection_bracket(g: GFn, a: float, b: float, *, iters: int=60) -> tuple[float, float]

Shrink a certified sign-change bracket by interval-safe bisection.

Parameters

Name	Type & default	Contract
`g`positional-or-keyword	`GFn`Required	See the operation contract and implementation below.
`a`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`b`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`iters`keyword-only	`int`Default: 60	See the operation contract and implementation below.

Returnstuple[float, float]

Explicit validation & failure cases

When not certified_sign_change(g, a, b), raises ValueError('no certified sign change on the initial bracket').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · bisection then newton

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_bisection_then_newton() -> None:
    def g(x: Interval) -> Interval:
        return x.pow_int(3) - Interval.point(2.0) * x - Interval.point(5.0)

    def gp(x: Interval) -> Interval:
        return Interval.point(3.0) * x.pow_int(2) - Interval.point(2.0)

    br = bisection_bracket(g, 2.0, 3.0, iters=20)
    res = interval_newton(g, gp, br)
    assert res["status"] == "unique_root"
    lo, hi = res["enclosure"]
    # Wallis' root of x^3 - 2x - 5 ~ 2.0945514815423265
    assert lo <= 2.0945514815423265 <= hi

python -m pytest "packages/omnibias-core/tests/verified/test_numerics.py::test_bisection_then_newton" -q

Read the implementation

def bisection_bracket(
    g: GFn, a: float, b: float, *, iters: int = 60
) -> tuple[float, float]:
    """Shrink a certified sign-change bracket by interval-safe bisection."""
    if not certified_sign_change(g, a, b):
        raise ValueError("no certified sign change on the initial bracket")
    ga = g(Interval.point(a))
    a_pos = ga.lo > 0.0
    lo, hi = a, b
    for _ in range(iters):
        mid = 0.5 * (lo + hi)
        gm = g(Interval.point(mid))
        if gm.contains_zero():
            break  # cannot certify the sign of g(mid); stop refining.
        mid_pos = gm.lo > 0.0
        if mid_pos == a_pos:
            lo = mid
        else:
            hi = mid
    return (lo, hi)

Other public import paths

omnibias.core.verified.bisection_bracket
omnibias.core.verified.rootfind.bisection_bracket

FUNCTION

certified_sign_change

omnibias.core.verified.certified_sign_changeSource ↗

certified_sign_change(g: GFn, a: float, b: float) -> bool

True iff g provably changes sign across [a, b] (so a root exists).

Parameters

Name	Type & default	Contract
`g`positional-or-keyword	`GFn`Required	See the operation contract and implementation below.
`a`positional-or-keyword	`float`Required	See the operation contract and implementation below.
`b`positional-or-keyword	`float`Required	See the operation contract and implementation below.

Returnsbool

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · certified sign change

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certified_sign_change() -> None:
    g = lambda x: x.pow_int(2) - Interval.point(2.0)  # noqa: E731
    assert certified_sign_change(g, 1.0, 2.0) is True
    assert certified_sign_change(g, 1.5, 1.6) is False  # both negative

python -m pytest packages/omnibias-core/tests/verified/test_numerics.py -k test_certified_sign_change -q

Read the implementation

def certified_sign_change(g: GFn, a: float, b: float) -> bool:
    """True iff ``g`` provably changes sign across ``[a, b]`` (so a root exists)."""
    ga = g(Interval.point(a))
    gb = g(Interval.point(b))
    a_neg = ga.hi < 0.0
    a_pos = ga.lo > 0.0
    b_neg = gb.hi < 0.0
    b_pos = gb.lo > 0.0
    return (a_neg and b_pos) or (a_pos and b_neg)

Other public import paths

omnibias.core.verified.certified_sign_change
omnibias.core.verified.rootfind.certified_sign_change

FUNCTION

interval_newton

omnibias.core.verified.interval_newtonSource ↗

interval_newton(g: GFn, gprime: GFn, bracket: tuple[float, float], *, max_iter: int=100, tol: float=1e-14) -> NewtonResult

Isolate a unique root of g in bracket via the interval-Newton test.

Parameters

Name	Type & default	Contract
`g`positional-or-keyword	`GFn`Required	See the operation contract and implementation below.
`gprime`positional-or-keyword	`GFn`Required	See the operation contract and implementation below.
`bracket`positional-or-keyword	`tuple[float, float]`Required	See the operation contract and implementation below.
`max_iter`keyword-only	`int`Default: 100	See the operation contract and implementation below.
`tol`keyword-only	`float`Default: 1e-14	See the operation contract and implementation below.

ReturnsNewtonResult

Executed regression · run model requires actual when verify

Full file, imports & fixtures ↗

def test_run_model_requires_actual_when_verify() -> None:
    with pytest.raises(ValueError, match="actual_fn"):
        run_model_line_search(_QUARTIC_DERIVS, config=JetLineSearchConfig(order=4))

python -m pytest "packages/omnibias-core/tests/test_line_search.py::test_run_model_requires_actual_when_verify" -q

Regression example · interval newton isolates sqrt2

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_interval_newton_isolates_sqrt2() -> None:
    g = lambda x: x.pow_int(2) - Interval.point(2.0)  # noqa: E731
    gp = lambda x: Interval.point(2.0) * x  # noqa: E731
    res = interval_newton(g, gp, (1.0, 2.0))
    assert res["status"] == "unique_root"
    assert res["unique"] is True
    lo, hi = res["enclosure"]
    assert lo <= math.sqrt(2.0) <= hi
    assert res["width"] < 1e-12

python -m pytest packages/omnibias-core/tests/verified/test_numerics.py -k test_interval_newton_isolates_sqrt2 -q

Read the implementation

def interval_newton(
    g: GFn,
    gprime: GFn,
    bracket: tuple[float, float],
    *,
    max_iter: int = 100,
    tol: float = 1e-14,
) -> NewtonResult:
    """Isolate a unique root of ``g`` in ``bracket`` via the interval-Newton test."""
    x = Interval(bracket[0], bracket[1])
    unique = False
    iterations = 0
    status = "max_iter"
    while iterations < max_iter:
        iterations += 1
        m = Interval.point(x.mid)
        gm = g(m)
        gp = gprime(x)
        if gp.contains_zero():
            # Derivative enclosure straddles zero: cannot apply the test here.
            status = "derivative_contains_zero" if not unique else "unique_root"
            break
        n_op = m - gm * gp.reciprocal()
        # Uniqueness test: N(X) strictly inside X.
        if x.lo < n_op.lo and n_op.hi < x.hi:
            unique = True
        try:
            x_new = n_op.intersect(x)
        except ValueError:
            status = "no_root"
            x = n_op
            break
        x = x_new
        if x.width <= tol:
            status = "unique_root" if unique else "converged_not_certified"
            break
    return {
        "status": status,
        "enclosure": (x.lo, x.hi),
        "width": x.width,
        "iterations": iterations,
        "unique": unique,
    }

Other public import paths

omnibias.core.verified.interval_newton
omnibias.core.verified.rootfind.interval_newton

← Package overview Runnable learning examples →

omnibias.core.verified.rootfind

GFn​

NewtonResult​

Fields & methods

bisection_bracket​

Parameters

certified_sign_change​

Parameters

interval_newton​

Parameters

GFn

NewtonResult

bisection_bracket

certified_sign_change

interval_newton