File: Root-Finding-Algorithms-using-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 (187 lines) | stat: -rw-r--r-- 8,805 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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
<!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: Root Finding Algorithms using Derivatives</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Root Finding Algorithms using Derivatives">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Root Finding Algorithms using 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="One-dimensional-Root_002dFinding.html#One-dimensional-Root_002dFinding" rel="up" title="One dimensional Root-Finding">
<link href="Root-Finding-Examples.html#Root-Finding-Examples" rel="next" title="Root Finding Examples">
<link href="Root-Bracketing-Algorithms.html#Root-Bracketing-Algorithms" rel="previous" title="Root Bracketing Algorithms">
<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="Root-Finding-Algorithms-using-Derivatives"></a>
<div class="header">
<p>
Next: <a href="Root-Finding-Examples.html#Root-Finding-Examples" accesskey="n" rel="next">Root Finding Examples</a>, Previous: <a href="Root-Bracketing-Algorithms.html#Root-Bracketing-Algorithms" accesskey="p" rel="previous">Root Bracketing Algorithms</a>, Up: <a href="One-dimensional-Root_002dFinding.html#One-dimensional-Root_002dFinding" accesskey="u" rel="up">One dimensional Root-Finding</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Root-Finding-Algorithms-using-Derivatives-1"></a>
<h3 class="section">34.9 Root Finding Algorithms using Derivatives</h3>

<p>The root polishing algorithms described in this section require an
initial guess for the location of the root.  There is no absolute
guarantee of convergence&mdash;the function must be suitable for this
technique and the initial guess must be sufficiently close to the root
for it to work.  When these conditions are satisfied then convergence is
quadratic.
</p>
<p>These algorithms make use of both the function and its derivative. 
</p>
<dl>
<dt><a name="index-gsl_005froot_005ffdfsolver_005fnewton"></a>Derivative Solver: <strong>gsl_root_fdfsolver_newton</strong></dt>
<dd><a name="index-Newton_0027s-method-for-finding-roots"></a>
<a name="index-root-finding_002c-Newton_0027s-method"></a>

<p>Newton&rsquo;s Method is the standard root-polishing algorithm.  The algorithm
begins with an initial guess for the location of the root.  On each
iteration, a line tangent to the function <em>f</em> is drawn at that
position.  The point where this line crosses the <em>x</em>-axis becomes
the new guess.  The iteration is defined by the following sequence,
</p>
<div class="example">
<pre class="example">x_{i+1} = x_i - f(x_i)/f'(x_i)
</pre></div>

<p>Newton&rsquo;s method converges quadratically for single roots, and linearly
for multiple roots.
</p>

</dd></dl>


<dl>
<dt><a name="index-gsl_005froot_005ffdfsolver_005fsecant"></a>Derivative Solver: <strong>gsl_root_fdfsolver_secant</strong></dt>
<dd><a name="index-secant-method-for-finding-roots"></a>
<a name="index-root-finding_002c-secant-method"></a>

<p>The <em>secant method</em> is a simplified version of Newton&rsquo;s method which does
not require the computation of the derivative on every step.
</p>
<p>On its first iteration the algorithm begins with Newton&rsquo;s method, using
the derivative to compute a first step,
</p>
<div class="example">
<pre class="example">x_1 = x_0 - f(x_0)/f'(x_0)
</pre></div>

<p>Subsequent iterations avoid the evaluation of the derivative by
replacing it with a numerical estimate, the slope of the line through
the previous two points,
</p>
<div class="example">
<pre class="example">x_{i+1} = x_i f(x_i) / f'_{est} where
 f'_{est} = (f(x_i) - f(x_{i-1})/(x_i - x_{i-1})
</pre></div>

<p>When the derivative does not change significantly in the vicinity of the
root the secant method gives a useful saving.  Asymptotically the secant
method is faster than Newton&rsquo;s method whenever the cost of evaluating
the derivative is more than 0.44 times the cost of evaluating the
function itself.  As with all methods of computing a numerical
derivative the estimate can suffer from cancellation errors if the
separation of the points becomes too small.
</p>
<p>On single roots, the method has a convergence of order <em>(1 + \sqrt
5)/2</em> (approximately <em>1.62</em>).  It converges linearly for multiple
roots.  
</p>
</dd></dl>


<dl>
<dt><a name="index-gsl_005froot_005ffdfsolver_005fsteffenson"></a>Derivative Solver: <strong>gsl_root_fdfsolver_steffenson</strong></dt>
<dd><a name="index-Steffenson_0027s-method-for-finding-roots"></a>
<a name="index-root-finding_002c-Steffenson_0027s-method"></a>

<p>The <em>Steffenson Method</em><a name="DOCF14" href="#FOOT14"><sup>14</sup></a> provides the fastest
convergence of all the routines.  It combines the basic Newton
algorithm with an Aitken &ldquo;delta-squared&rdquo; acceleration.  If the
Newton iterates are <em>x_i</em> then the acceleration procedure
generates a new sequence <em>R_i</em>,
</p>
<div class="example">
<pre class="example">R_i = x_i - (x_{i+1} - x_i)^2 / (x_{i+2} - 2 x_{i+1} + x_{i})
</pre></div>

<p>which converges faster than the original sequence under reasonable
conditions.  The new sequence requires three terms before it can produce
its first value so the method returns accelerated values on the second
and subsequent iterations.  On the first iteration it returns the
ordinary Newton estimate.  The Newton iterate is also returned if the
denominator of the acceleration term ever becomes zero.
</p>
<p>As with all acceleration procedures this method can become unstable if
the function is not well-behaved. 
</p></dd></dl>

<div class="footnote">
<hr>
<h4 class="footnotes-heading">Footnotes</h4>

<h3><a name="FOOT14" href="#DOCF14">(14)</a></h3>
<p>J.F. Steffensen (1873&ndash;1961). The
spelling used in the name of the function is slightly incorrect, but
has been preserved to avoid incompatibility.</p>
</div>
<hr>
<div class="header">
<p>
Next: <a href="Root-Finding-Examples.html#Root-Finding-Examples" accesskey="n" rel="next">Root Finding Examples</a>, Previous: <a href="Root-Bracketing-Algorithms.html#Root-Bracketing-Algorithms" accesskey="p" rel="previous">Root Bracketing Algorithms</a>, Up: <a href="One-dimensional-Root_002dFinding.html#One-dimensional-Root_002dFinding" accesskey="u" rel="up">One dimensional Root-Finding</a> &nbsp; [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>