3
<title>Algorithms using Derivatives - GNU Scientific Library -- Reference Manual</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="GNU Scientific Library -- Reference Manual">
6
<meta name="generator" content="makeinfo 4.8">
7
<link title="Top" rel="start" href="index.html#Top">
8
<link rel="up" href="Multidimensional-Root_002dFinding.html#Multidimensional-Root_002dFinding" title="Multidimensional Root-Finding">
9
<link rel="prev" href="Search-Stopping-Parameters-for-the-multidimensional-solver.html#Search-Stopping-Parameters-for-the-multidimensional-solver" title="Search Stopping Parameters for the multidimensional solver">
10
<link rel="next" href="Algorithms-without-Derivatives.html#Algorithms-without-Derivatives" title="Algorithms without Derivatives">
11
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
13
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 The GSL Team.
15
Permission is granted to copy, distribute and/or modify this document
16
under the terms of the GNU Free Documentation License, Version 1.2 or
17
any later version published by the Free Software Foundation; with the
18
Invariant Sections being ``GNU General Public License'' and ``Free Software
19
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
20
and with the Back-Cover Text being (a) (see below). A copy of the
21
license is included in the section entitled ``GNU Free Documentation
24
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
25
GNU Manual, like GNU software.''-->
26
<meta http-equiv="Content-Style-Type" content="text/css">
27
<style type="text/css"><!--
28
pre.display { font-family:inherit }
29
pre.format { font-family:inherit }
30
pre.smalldisplay { font-family:inherit; font-size:smaller }
31
pre.smallformat { font-family:inherit; font-size:smaller }
32
pre.smallexample { font-size:smaller }
33
pre.smalllisp { font-size:smaller }
34
span.sc { font-variant:small-caps }
35
span.roman { font-family:serif; font-weight:normal; }
36
span.sansserif { font-family:sans-serif; font-weight:normal; }
42
<a name="Algorithms-using-Derivatives"></a>
43
Next: <a rel="next" accesskey="n" href="Algorithms-without-Derivatives.html#Algorithms-without-Derivatives">Algorithms without Derivatives</a>,
44
Previous: <a rel="previous" accesskey="p" href="Search-Stopping-Parameters-for-the-multidimensional-solver.html#Search-Stopping-Parameters-for-the-multidimensional-solver">Search Stopping Parameters for the multidimensional solver</a>,
45
Up: <a rel="up" accesskey="u" href="Multidimensional-Root_002dFinding.html#Multidimensional-Root_002dFinding">Multidimensional Root-Finding</a>
49
<h3 class="section">34.6 Algorithms using Derivatives</h3>
51
<p>The root finding algorithms described in this section make use of both
52
the function and its derivative. They require an initial guess for the
53
location of the root, but there is no absolute guarantee of
54
convergence—the function must be suitable for this technique and the
55
initial guess must be sufficiently close to the root for it to work.
56
When the conditions are satisfied then convergence is quadratic.
58
<!-- ============================================================ -->
59
<p><a name="index-HYBRID-algorithms-for-nonlinear-systems-2196"></a>
62
— Derivative Solver: <b>gsl_multiroot_fdfsolver_hybridsj</b><var><a name="index-gsl_005fmultiroot_005ffdfsolver_005fhybridsj-2197"></a></var><br>
63
<blockquote><p><a name="index-HYBRIDSJ-algorithm-2198"></a><a name="index-MINPACK_002c-minimization-algorithms-2199"></a>This is a modified version of Powell's Hybrid method as implemented in
64
the <span class="sc">hybrj</span> algorithm in <span class="sc">minpack</span>. Minpack was written by Jorge
65
J. Moré, Burton S. Garbow and Kenneth E. Hillstrom. The Hybrid
66
algorithm retains the fast convergence of Newton's method but will also
67
reduce the residual when Newton's method is unreliable.
69
<p>The algorithm uses a generalized trust region to keep each step under
70
control. In order to be accepted a proposed new position x' must
71
satisfy the condition |D (x' - x)| < \delta, where D is a
72
diagonal scaling matrix and \delta is the size of the trust
73
region. The components of D are computed internally, using the
74
column norms of the Jacobian to estimate the sensitivity of the residual
75
to each component of x. This improves the behavior of the
76
algorithm for badly scaled functions.
78
<p>On each iteration the algorithm first determines the standard Newton
79
step by solving the system J dx = - f. If this step falls inside
80
the trust region it is used as a trial step in the next stage. If not,
81
the algorithm uses the linear combination of the Newton and gradient
82
directions which is predicted to minimize the norm of the function while
83
staying inside the trust region,
84
This combination of Newton and gradient directions is referred to as a
85
<dfn>dogleg step</dfn>.
87
<p>The proposed step is now tested by evaluating the function at the
88
resulting point, x'. If the step reduces the norm of the function
89
sufficiently then it is accepted and size of the trust region is
90
increased. If the proposed step fails to improve the solution then the
91
size of the trust region is decreased and another trial step is
94
<p>The speed of the algorithm is increased by computing the changes to the
95
Jacobian approximately, using a rank-1 update. If two successive
96
attempts fail to reduce the residual then the full Jacobian is
97
recomputed. The algorithm also monitors the progress of the solution
98
and returns an error if several steps fail to make any improvement,
101
<dt><code>GSL_ENOPROG</code><dd>the iteration is not making any progress, preventing the algorithm from
104
<br><dt><code>GSL_ENOPROGJ</code><dd>re-evaluations of the Jacobian indicate that the iteration is not
105
making any progress, preventing the algorithm from continuing.
111
— Derivative Solver: <b>gsl_multiroot_fdfsolver_hybridj</b><var><a name="index-gsl_005fmultiroot_005ffdfsolver_005fhybridj-2200"></a></var><br>
112
<blockquote><p><a name="index-HYBRIDJ-algorithm-2201"></a>This algorithm is an unscaled version of <code>hybridsj</code>. The steps are
113
controlled by a spherical trust region |x' - x| < \delta, instead
114
of a generalized region. This can be useful if the generalized region
115
estimated by <code>hybridsj</code> is inappropriate.
116
</p></blockquote></div>
119
— Derivative Solver: <b>gsl_multiroot_fdfsolver_newton</b><var><a name="index-gsl_005fmultiroot_005ffdfsolver_005fnewton-2202"></a></var><br>
120
<blockquote><p><a name="index-Newton_0027s-method-for-systems-of-nonlinear-equations-2203"></a>
121
Newton's Method is the standard root-polishing algorithm. The algorithm
122
begins with an initial guess for the location of the solution. On each
123
iteration a linear approximation to the function F is used to
124
estimate the step which will zero all the components of the residual.
125
The iteration is defined by the following sequence,
126
where the Jacobian matrix J is computed from the derivative
127
functions provided by <var>f</var>. The step dx is obtained by solving
129
using LU decomposition.
130
</p></blockquote></div>
132
<!-- ============================================================ -->
134
— Derivative Solver: <b>gsl_multiroot_fdfsolver_gnewton</b><var><a name="index-gsl_005fmultiroot_005ffdfsolver_005fgnewton-2204"></a></var><br>
135
<blockquote><p><a name="index-Modified-Newton_0027s-method-for-nonlinear-systems-2205"></a><a name="index-Newton-algorithm_002c-globally-convergent-2206"></a>This is a modified version of Newton's method which attempts to improve
136
global convergence by requiring every step to reduce the Euclidean norm
137
of the residual, |f(x)|. If the Newton step leads to an increase
138
in the norm then a reduced step of relative size,
139
is proposed, with r being the ratio of norms
140
|f(x')|^2/|f(x)|^2. This procedure is repeated until a suitable step
142
</p></blockquote></div>
144
<!-- ============================================================ -->
added
removed
Algorithms-using-Derivatives.html
