1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with no
Invariant Sections and no cover texts. A copy of the license is
included in the section entitled "GNU Free Documentation License". -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Algorithms without Derivatives</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Algorithms without Derivatives">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Algorithms without Derivatives">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Multidimensional-Root_002dFinding.html#Multidimensional-Root_002dFinding" rel="up" title="Multidimensional Root-Finding">
<link href="Example-programs-for-Multidimensional-Root-finding.html#Example-programs-for-Multidimensional-Root-finding" rel="next" title="Example programs for Multidimensional Root finding">
<link href="Algorithms-using-Derivatives.html#Algorithms-using-Derivatives" rel="previous" title="Algorithms using Derivatives">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Algorithms-without-Derivatives"></a>
<div class="header">
<p>
Next: <a href="Example-programs-for-Multidimensional-Root-finding.html#Example-programs-for-Multidimensional-Root-finding" accesskey="n" rel="next">Example programs for Multidimensional Root finding</a>, Previous: <a href="Algorithms-using-Derivatives.html#Algorithms-using-Derivatives" accesskey="p" rel="previous">Algorithms using Derivatives</a>, Up: <a href="Multidimensional-Root_002dFinding.html#Multidimensional-Root_002dFinding" accesskey="u" rel="up">Multidimensional Root-Finding</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Algorithms-without-Derivatives-1"></a>
<h3 class="section">35.7 Algorithms without Derivatives</h3>
<p>The 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
the algorithms described in the previous section.
</p>
<dl>
<dt><a name="index-gsl_005fmultiroot_005ffsolver_005fhybrids"></a>Solver: <strong>gsl_multiroot_fsolver_hybrids</strong></dt>
<dd><a name="index-HYBRIDS-algorithm_002c-scaled-without-derivatives"></a>
<p>This is a version of the Hybrid algorithm which replaces calls to the
Jacobian function by its finite difference approximation. The finite
difference approximation is computed using <code>gsl_multiroots_fdjac</code>
with a relative step size of <code>GSL_SQRT_DBL_EPSILON</code>. Note that
this step size will not be suitable for all problems.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fmultiroot_005ffsolver_005fhybrid"></a>Solver: <strong>gsl_multiroot_fsolver_hybrid</strong></dt>
<dd><a name="index-HYBRID-algorithm_002c-unscaled-without-derivatives"></a>
<p>This is a finite difference version of the Hybrid algorithm without
internal scaling.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fmultiroot_005ffsolver_005fdnewton"></a>Solver: <strong>gsl_multiroot_fsolver_dnewton</strong></dt>
<dd>
<a name="index-Discrete-Newton-algorithm-for-multidimensional-roots"></a>
<a name="index-Newton-algorithm_002c-discrete"></a>
<p>The <em>discrete Newton algorithm</em> is the simplest method of solving a
multidimensional system. It uses the Newton iteration
where the Jacobian matrix <em>J</em> is approximated by taking finite
differences of the function <var>f</var>. The approximation scheme used by
this implementation is,
where <em>\delta_j</em> is a step of size <em>\sqrt\epsilon |x_j|</em> with
<em>\epsilon</em> being the machine precision
(<em>\epsilon \approx 2.22 \times 10^-16</em>).
The order of convergence of Newton’s algorithm is quadratic, but the
finite differences require <em>n^2</em> function evaluations on each
iteration. The algorithm may become unstable if the finite differences
are not a good approximation to the true derivatives.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005fmultiroot_005ffsolver_005fbroyden"></a>Solver: <strong>gsl_multiroot_fsolver_broyden</strong></dt>
<dd><a name="index-Broyden-algorithm-for-multidimensional-roots"></a>
<a name="index-multidimensional-root-finding_002c-Broyden-algorithm"></a>
<p>The <em>Broyden algorithm</em> is a version of the discrete Newton
algorithm which attempts to avoids the expensive update of the Jacobian
matrix on each iteration. The changes to the Jacobian are also
approximated, using a rank-1 update,
where the vectors <em>dx</em> and <em>df</em> are the changes in <em>x</em>
and <em>f</em>. On the first iteration the inverse Jacobian is estimated
using finite differences, as in the discrete Newton algorithm.
</p>
<p>This approximation gives a fast update but is unreliable if the changes
are not small, and the estimate of the inverse Jacobian becomes worse as
time passes. The algorithm has a tendency to become unstable unless it
starts close to the root. The Jacobian is refreshed if this instability
is detected (consult the source for details).
</p>
<p>This algorithm is included only for demonstration purposes, and is not
recommended for serious use.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Example-programs-for-Multidimensional-Root-finding.html#Example-programs-for-Multidimensional-Root-finding" accesskey="n" rel="next">Example programs for Multidimensional Root finding</a>, Previous: <a href="Algorithms-using-Derivatives.html#Algorithms-using-Derivatives" accesskey="p" rel="previous">Algorithms using Derivatives</a>, Up: <a href="Multidimensional-Root_002dFinding.html#Multidimensional-Root_002dFinding" accesskey="u" rel="up">Multidimensional Root-Finding</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
