pub enum UpdateQuasiNewtonMethod {
BroydenFirstMethod,
BroydenSecondMethod,
GreenstadtFirstMethod,
GreenstadtSecondMethod,
}
Expand description
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
sourceimpl Clone for UpdateQuasiNewtonMethod
impl Clone for UpdateQuasiNewtonMethod
sourcefn clone(&self) -> UpdateQuasiNewtonMethod
fn clone(&self) -> UpdateQuasiNewtonMethod
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresourceimpl Debug for UpdateQuasiNewtonMethod
impl Debug for UpdateQuasiNewtonMethod
sourceimpl Display for UpdateQuasiNewtonMethod
impl Display for UpdateQuasiNewtonMethod
sourceimpl PartialEq<UpdateQuasiNewtonMethod> for UpdateQuasiNewtonMethod
impl PartialEq<UpdateQuasiNewtonMethod> for UpdateQuasiNewtonMethod
sourcefn eq(&self, other: &UpdateQuasiNewtonMethod) -> bool
fn eq(&self, other: &UpdateQuasiNewtonMethod) -> bool
impl Copy for UpdateQuasiNewtonMethod
impl StructuralPartialEq for UpdateQuasiNewtonMethod
Auto Trait Implementations
impl RefUnwindSafe for UpdateQuasiNewtonMethod
impl Send for UpdateQuasiNewtonMethod
impl Sync for UpdateQuasiNewtonMethod
impl Unpin for UpdateQuasiNewtonMethod
impl UnwindSafe for UpdateQuasiNewtonMethod
Blanket Implementations
sourceimpl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
impl<SS, SP> SupersetOf<SS> for SPwhere
SS: SubsetOf<SP>,
impl<SS, SP> SupersetOf<SS> for SPwhere
SS: SubsetOf<SP>,
fn to_subset(&self) -> Option<SS>
fn to_subset(&self) -> Option<SS>
self
from the equivalent element of its
superset. Read morefn is_in_subset(&self) -> bool
fn is_in_subset(&self) -> bool
self
is actually part of its subset T
(and can be converted to it).fn to_subset_unchecked(&self) -> SS
fn to_subset_unchecked(&self) -> SS
self.to_subset
but without any property checks. Always succeeds.fn from_subset(element: &SS) -> SP
fn from_subset(element: &SS) -> SP
self
to the equivalent element of its superset.