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
|
<!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 – Reference Manual: Root Bracketing Algorithms</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Root Bracketing Algorithms">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Root Bracketing Algorithms">
<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-Algorithms-using-Derivatives.html#Root-Finding-Algorithms-using-Derivatives" rel="next" title="Root Finding Algorithms using Derivatives">
<link href="Search-Stopping-Parameters.html#Search-Stopping-Parameters" rel="previous" title="Search Stopping Parameters">
<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-Bracketing-Algorithms"></a>
<div class="header">
<p>
Next: <a href="Root-Finding-Algorithms-using-Derivatives.html#Root-Finding-Algorithms-using-Derivatives" accesskey="n" rel="next">Root Finding Algorithms using Derivatives</a>, Previous: <a href="Search-Stopping-Parameters.html#Search-Stopping-Parameters" accesskey="p" rel="previous">Search Stopping Parameters</a>, Up: <a href="One-dimensional-Root_002dFinding.html#One-dimensional-Root_002dFinding" accesskey="u" rel="up">One dimensional Root-Finding</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Root-Bracketing-Algorithms-1"></a>
<h3 class="section">34.8 Root Bracketing Algorithms</h3>
<p>The root bracketing algorithms described in this section require an
initial interval which is guaranteed to contain a root—if <em>a</em>
and <em>b</em> are the endpoints of the interval then <em>f(a)</em> must
differ in sign from <em>f(b)</em>. This ensures that the function crosses
zero at least once in the interval. If a valid initial interval is used
then these algorithm cannot fail, provided the function is well-behaved.
</p>
<p>Note that a bracketing algorithm cannot find roots of even degree, since
these do not cross the <em>x</em>-axis.
</p>
<dl>
<dt><a name="index-gsl_005froot_005ffsolver_005fbisection"></a>Solver: <strong>gsl_root_fsolver_bisection</strong></dt>
<dd>
<a name="index-bisection-algorithm-for-finding-roots"></a>
<a name="index-root-finding_002c-bisection-algorithm"></a>
<p>The <em>bisection algorithm</em> is the simplest method of bracketing the
roots of a function. It is the slowest algorithm provided by
the library, with linear convergence.
</p>
<p>On each iteration, the interval is bisected and the value of the
function at the midpoint is calculated. The sign of this value is used
to determine which half of the interval does not contain a root. That
half is discarded to give a new, smaller interval containing the
root. This procedure can be continued indefinitely until the interval is
sufficiently small.
</p>
<p>At any time the current estimate of the root is taken as the midpoint of
the interval.
</p>
</dd></dl>
<dl>
<dt><a name="index-gsl_005froot_005ffsolver_005ffalsepos"></a>Solver: <strong>gsl_root_fsolver_falsepos</strong></dt>
<dd><a name="index-false-position-algorithm-for-finding-roots"></a>
<a name="index-root-finding_002c-false-position-algorithm"></a>
<p>The <em>false position algorithm</em> is a method of finding roots based on
linear interpolation. Its convergence is linear, but it is usually
faster than bisection.
</p>
<p>On each iteration a line is drawn between the endpoints <em>(a,f(a))</em>
and <em>(b,f(b))</em> and the point where this line crosses the
<em>x</em>-axis taken as a “midpoint”. The value of the function at
this point is calculated and its sign is used to determine which side of
the interval does not contain a root. That side is discarded to give a
new, smaller interval containing the root. This procedure can be
continued indefinitely until the interval is sufficiently small.
</p>
<p>The best estimate of the root is taken from the linear interpolation of
the interval on the current iteration.
</p>
</dd></dl>
<dl>
<dt><a name="index-gsl_005froot_005ffsolver_005fbrent"></a>Solver: <strong>gsl_root_fsolver_brent</strong></dt>
<dd><a name="index-Brent_0027s-method-for-finding-roots"></a>
<a name="index-root-finding_002c-Brent_0027s-method"></a>
<p>The <em>Brent-Dekker method</em> (referred to here as <em>Brent’s method</em>)
combines an interpolation strategy with the bisection algorithm. This
produces a fast algorithm which is still robust.
</p>
<p>On each iteration Brent’s method approximates the function using an
interpolating curve. On the first iteration this is a linear
interpolation of the two endpoints. For subsequent iterations the
algorithm uses an inverse quadratic fit to the last three points, for
higher accuracy. The intercept of the interpolating curve with the
<em>x</em>-axis is taken as a guess for the root. If it lies within the
bounds of the current interval then the interpolating point is accepted,
and used to generate a smaller interval. If the interpolating point is
not accepted then the algorithm falls back to an ordinary bisection
step.
</p>
<p>The best estimate of the root is taken from the most recent
interpolation or bisection.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Root-Finding-Algorithms-using-Derivatives.html#Root-Finding-Algorithms-using-Derivatives" accesskey="n" rel="next">Root Finding Algorithms using Derivatives</a>, Previous: <a href="Search-Stopping-Parameters.html#Search-Stopping-Parameters" accesskey="p" rel="previous">Search Stopping Parameters</a>, Up: <a href="One-dimensional-Root_002dFinding.html#One-dimensional-Root_002dFinding" accesskey="u" rel="up">One dimensional Root-Finding</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
