Expand description
Multi dimensional Root-Finding
This chapter describes functions for multidimensional root-finding (solving nonlinear systems with
n equations in n unknowns). The library provides low level components for a variety of iterative
solvers and convergence tests. These can be combined by the user to achieve the desired solution,
with full access to the intermediate steps of the iteration. Each class of methods uses the same
framework, so that you can switch between solvers at runtime without needing to recompile your
program. Each instance of a solver keeps track of its own state, allowing the solvers to be used
in multi-threaded programs. The solvers are based on the original Fortran library MINPACK.
The header file gsl_multiroots.h contains prototypes for the multidimensional root finding functions
and related declarations.
Overview
The problem of multidimensional root finding requires the simultaneous solution of n equations, f_i, in n variables, x_i,
f_i (x_1, \dots, x_n) = 0 \qquad\hbox{for}~i = 1 \dots n.In general there are no bracketing methods available for n dimensional systems, and no way of knowing whether any solutions exist. All algorithms proceed from an initial guess using a variant of the Newton iteration,
x \to x' = x - J^{-1} f(x)where x, f are vector quantities and J is the Jacobian matrix J_{ij} = \partial f_i / \partial x_j. Additional strategies can be used to enlarge the region of convergence. These include requiring a decrease in the norm |f| on each step proposed by Newton’s method, or taking steepest-descent steps in the direction of the negative gradient of |f|.
Several root-finding algorithms are available within a single framework. The user provides a high-level driver for the algorithms, and the library provides the individual functions necessary for each of the steps. There are three main phases of the iteration. The steps are,
- initialize solver state,
s, for algorithmT - update
susing the iterationT - test
sfor convergence, and repeat iteration if necessary
The evaluation of the Jacobian matrix can be problematic, either because programming the derivatives is intractable or because computation of the n^2 terms of the matrix becomes too expensive. For these reasons the algorithms provided by the library are divided into two classes according to whether the derivatives are available or not.
The state for solvers with an analytic Jacobian matrix is held in a gsl_multiroot_fdfsolver struct.
The updating procedure requires both the function and its derivatives to be supplied by the user.
The state for solvers which do not use an analytic Jacobian matrix is held in a
gsl_multiroot_fsolver struct. The updating procedure uses only function evaluations (not derivatives).
The algorithms estimate the matrix J or J^{-1} by approximate methods.
!
Structs
This is a workspace for multidimensional root-finding without derivatives.
The multiroot algorithms described in this section do not require any derivative information to be supplied by the user. Any derivatives needed are approximated by finite differences. Note that if the finite-differencing step size chosen by these routines is inappropriate, an explicit user-supplied numerical derivative can always be used with derivative-based algorithms.