In the Python documentation for fsolve it says "Return the roots of the (non-linear) equations defined by func(x) = 0 given a starting estimate" f(x, *args). I wondered if anyone knew the mathematical mechanics behind what fsolve is actually doing? Thanks.
$\endgroup$ 23 Answers
$\begingroup$You can just check the source code.
fsolveis a wrapper around MINPACK's hybrd and hybrj algorithms.
Leading to minpack. Hybrd and hybrj are essentially the same, but hybrd uses forward differences to compute the jacobian whereas hybrj requires the user to provide the jacobian. They use Powell's method, with the modifications described in the previous link to minpack.
$\endgroup$ 1 $\begingroup$As the notes in the documentation say:
fsolve is a wrapper around MINPACK’s hybrd and hybrj algorithms.
Reading further to MINPACK's documentation
HYBRD is a modification of the Powell hybrid method. Two of its main characteristics involve the choice of the correction as a convex combination of the Newton and scaled gradient directions, and the updating of the Jacobian by the rank-1 method of Broy- den. The choice of the correction guarantees (under reasonable conditions) global convergence for starting points far from the solution and a fast rate of convergence. The Jacobian is approximated by forward differences at the starting point, but forward differences are not used again until the rank-1 method fails to produce satisfactory progress.
HYBRJ is a modification of the Powell hybrid method. Two of its main characteristics involve the choice of the correction as a convex combination of the Newton and scaled gradient directions, and the updating of the Jacobian by the rank-1 method of Broy- den. The choice of the correction guarantees (under reasonable conditions) global convergence for starting points far from the solution and a fast rate of convergence. The Jacobian is calcu- lated at the starting point, but it is not recalculated until the rank-1 method fails to produce satisfactory progress.
The citation even tells you where the original math is:
M. J. D. Powell, A Hybrid Method for Nonlinear Equations. Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, editor. Gordon and Breach, 1970.
I think the relevant wikipedia article is Powell's dog leg method. It's a version of gradient descent.
$\endgroup$ $\begingroup$The fsolve function returns the roots of a non linear equation defined by $f(x)=0$.
$\endgroup$
