File: Root-Finding-Overview.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 (120 lines) | stat: -rw-r--r-- 5,901 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
<!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 Overview</title>

<meta name="description" content="GNU Scientific Library &ndash; Reference Manual: Root Finding Overview">
<meta name="keywords" content="GNU Scientific Library &ndash; Reference Manual: Root Finding Overview">
<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-Caveats.html#Root-Finding-Caveats" rel="next" title="Root Finding Caveats">
<link href="One-dimensional-Root_002dFinding.html#One-dimensional-Root_002dFinding" rel="previous" title="One dimensional Root-Finding">
<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-Overview"></a>
<div class="header">
<p>
Next: <a href="Root-Finding-Caveats.html#Root-Finding-Caveats" accesskey="n" rel="next">Root Finding Caveats</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="Overview"></a>
<h3 class="section">34.1 Overview</h3>
<a name="index-root-finding_002c-overview"></a>

<p>One-dimensional root finding algorithms can be divided into two classes,
<em>root bracketing</em> and <em>root polishing</em>.  Algorithms which proceed
by bracketing a root are guaranteed to converge.  Bracketing algorithms
begin with a bounded region known to contain a root.  The size of this
bounded region is reduced, iteratively, until it encloses the root to a
desired tolerance.  This provides a rigorous error estimate for the
location of the root.
</p>
<p>The technique of <em>root polishing</em> attempts to improve an initial
guess to the root.  These algorithms converge only if started &ldquo;close
enough&rdquo; to a root, and sacrifice a rigorous error bound for speed.  By
approximating the behavior of a function in the vicinity of a root they
attempt to find a higher order improvement of an initial guess.  When the
behavior of the function is compatible with the algorithm and a good
initial guess is available a polishing algorithm can provide rapid
convergence.
</p>
<p>In GSL both types of algorithm are available in similar frameworks.  The
user provides a high-level driver for the algorithms, and the library
provides the individual functions necessary for each of the steps.
There are three main phases of the iteration.  The steps are,
</p>
<ul>
<li> initialize solver state, <var>s</var>, for algorithm <var>T</var>

</li><li> update <var>s</var> using the iteration <var>T</var>

</li><li> test <var>s</var> for convergence, and repeat iteration if necessary
</li></ul>

<p>The state for bracketing solvers is held in a <code>gsl_root_fsolver</code>
struct.  The updating procedure uses only function evaluations (not
derivatives).  The state for root polishing solvers is held in a
<code>gsl_root_fdfsolver</code> struct.  The updates require both the function
and its derivative (hence the name <code>fdf</code>) to be supplied by the
user.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Root-Finding-Caveats.html#Root-Finding-Caveats" accesskey="n" rel="next">Root Finding Caveats</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>