Module solve 

Root finding, polynomial roots and minimization.

The numerical substrate every intersection, projection and extrema algorithm in the kernel sits on. Nothing here is geometric. It is kept separate so those algorithms are about geometry rather than about convergence.

What to reach for

• A root inside a known bracket: brent. Guaranteed to converge, and nearly as fast as Newton in practice.
• A root with a known derivative and a good starting point: newton, which falls back to bisection whenever a step would leave the bracket. Unsafeguarded Newton diverges on the configurations that matter: a tangential intersection is exactly where the derivative vanishes.
• Roots of a polynomial: roots. Closed form up to the cubic, the quadratic written to avoid the cancellation the schoolbook formula suffers. Above that, or with no allocation, real_roots: each root bracketed between its derivative’s roots.
• A system of equations: newton_system. Surface projection is two equations in two unknowns. Intersection marching is much the same.
• A minimum without derivatives: minimize.

Structs

Criteria

Stopping criteria for an iterative solver.

Solution

A solver result: the estimate, the residual there, and how it finished.

SystemSolution

The outcome of solving a system of equations.

Enums

Convergence

How a solver finished.

Functions

brent

Find a root of f in [a, b] by Brent’s method.

cubic_roots

Real roots of a x^3 + b x^2 + c x + d.

linear_fixed

A x = b for an N × N system, by LU with partial pivoting: the step newton_system_fixed solves. None at a zero pivot.

minimize

Minimize a scalar function on [a, b] without derivatives.

newton

Find a root of f near start, using its derivative, safeguarded by a bracket.

newton_system

Solve f(x) = 0 for a vector x, by damped Newton.

newton_system_2

A two-unknown newton_system, allocation-free.

newton_system_fixed

A fixed-size newton_system for N unknowns, allocation-free.

newton_system_fixed_lazy

newton_system_fixed with the residual and the Jacobian measured apart, the Jacobian only where a step is taken.

quadratic_roots

Real roots of a x^2 + b x + c.

real_roots

The real roots of a polynomial, in increasing order, written to the front of out; returns how many there are.

roots

The real roots of a polynomial, in increasing order.