File: Algorithms-without-Derivatives.html

package info (click to toggle)
gsl-ref-html 2.3-1
  • links: PTS
  • area: non-free
  • in suites: bullseye, buster, sid
  • size: 6,876 kB
  • ctags: 4,574
  • sloc: makefile: 35
file content (168 lines) | stat: -rw-r--r-- 8,455 bytes parent folder | download
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
<!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, 2014, 2015, 2016 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 the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".

(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library &ndash; Reference Manual: Algorithms without Derivatives</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Algorithms without Derivatives">
<meta name="keywords" content="GNU Scientific Library &ndash; 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> &nbsp; [<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">36.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
</p>
<div class="example">
<pre class="example">x -&gt; x - J^{-1} f(x)
</pre></div>

<p>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,
</p>
<div class="example">
<pre class="example">J_{ij} = (f_i(x + \delta_j) - f_i(x)) /  \delta_j
</pre></div>

<p>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&rsquo;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,
</p>
<div class="example">
<pre class="example">J^{-1} \to J^{-1} - (J^{-1} df - dx) dx^T J^{-1} / dx^T J^{-1} df
</pre></div>

<p>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> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>