Enum newton_rootfinder::solver::UpdateQuasiNewtonMethod

pub enum UpdateQuasiNewtonMethod {
    BroydenFirstMethod,
    BroydenSecondMethod,
    GreenstadtFirstMethod,
    GreenstadtSecondMethod,
}

This quasi-Newton methods either work on the jacobian or its inverse

Stationary Newton [1967]

A quasi Newton Method requiring the evaluation of the jacobian only at the first iteration step.

The jacobian of the first iteration is used for all the updates

The convergence rate is locally linear and controlled by the first error :

|| x_{n+1} - x_sol || < || x_{n} - x_sol ||*|| x_{0} - x_sol ||

General form of others Quasi-Newton method considered

The general formula taken from [1997] is:

H_{i+1} = H_{i} - (H_{i}*y_{i}-s_{i})c_{i}^{T}/(c_{i}^{T}*y_{i}),

With, for the iteration i:

• H_{i} = J_{i}^{-1}, the inverse of the approximated jacobian
• s_{i} = x_{i+1} - x_{i}, the vector of the iterative update
• y_{i} = F_{x_{i+1}} - F_{x_{i}}, the vector of the residual update
• c_{i}, a vector that is chosen differently according to the method.

This method can also be applied, instead on the inverse of the jacobian, with the jacobian itself. Householder’s formula (also known as Sherman-Morrison’s formula) yields:

J_{i+1} = J_{i} - (J_{i}*s_{i}-y_{i})*c_{i}^{T}*J_{i}/(c_{i}^{T}*J_{i}*s_{i})

Broyden methods

Two methods have been published by Broyden,

• The first method, knowned as “Broyden Good Method”
• The second method, knowned as “Broyden Bad Method”

For the different methods, c_{i} is taken as such:

• First method: c_{i} = H_{i}^{T} * s_{i}
• Second method: c_{i} = y_{i}

The update formulas are the following:

Method	c_{i} value	Jacobian update	Inverse jacobian update
First	H_{i}^{T} * s_{i}	J_{i+1} = J_{i} - (J_{i}*s_{i}-y_{i})*s_{i}^{T}/(s_{i}^{T}*s_{i})	H_{i+1} = H_{i} - (H_{i}*y_{i}-s_{i})s_{i}^{T}*H_{i}/(s_{i}^{T}*H_{i}*y_{i})
Second	y_{i}	J_{i+1} = J_{i} - (J_{i}*s_{i}-y_{i})*y_{i}^{T}*J_{i}/(y_{i}^{T}*J_{i}*s_{i})	H_{i+1} = H_{i} - (H_{i}*y_{i}-s_{i})y_{i}^{T}/(y_{i}^{T}*y_{i})

Reference

Dennis, Jr., J. E. (1967)

A Stationary Newton Method for Nonlinear Functional Equations

SIAM Journal on Numerical Analysis, 4(2), p 222–232.

doi:10.1137/0704021

Spedicato, E. ; Huang, Z. (1996)

Numerical experience with Newton-like methods for nonlinear algebraic systems,

Computing, p 68-89.

doi:10.1007/BF02684472

Variants

BroydenFirstMethod

BroydenSecondMethod

GreenstadtFirstMethod

GreenstadtSecondMethod

Trait Implementations

impl Clone for UpdateQuasiNewtonMethod

fn clone(&self) -> UpdateQuasiNewtonMethod

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for UpdateQuasiNewtonMethod

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for UpdateQuasiNewtonMethod

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq<UpdateQuasiNewtonMethod> for UpdateQuasiNewtonMethod

fn eq(&self, other: &UpdateQuasiNewtonMethod) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl Copy for UpdateQuasiNewtonMethod

impl StructuralPartialEq for UpdateQuasiNewtonMethod