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
|
<!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: Overview of Multidimensional Root Finding</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Overview of Multidimensional Root Finding">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Overview of Multidimensional Root Finding">
<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="Initializing-the-Multidimensional-Solver.html#Initializing-the-Multidimensional-Solver" rel="next" title="Initializing the Multidimensional Solver">
<link href="Multidimensional-Root_002dFinding.html#Multidimensional-Root_002dFinding" rel="previous" title="Multidimensional 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="Overview-of-Multidimensional-Root-Finding"></a>
<div class="header">
<p>
Next: <a href="Initializing-the-Multidimensional-Solver.html#Initializing-the-Multidimensional-Solver" accesskey="n" rel="next">Initializing the Multidimensional Solver</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="Overview-2"></a>
<h3 class="section">36.1 Overview</h3>
<a name="index-multidimensional-root-finding_002c-overview"></a>
<p>The problem of multidimensional root finding requires the simultaneous
solution of <em>n</em> equations, <em>f_i</em>, in <em>n</em> variables,
<em>x_i</em>,
</p>
<div class="example">
<pre class="example">f_i (x_1, ..., x_n) = 0 for i = 1 ... n.
</pre></div>
<p>In general there are no bracketing methods available for <em>n</em>
dimensional systems, and no way of knowing whether any solutions
exist. All algorithms proceed from an initial guess using a variant of
the Newton iteration,
</p>
<div class="example">
<pre class="example">x -> x' = x - J^{-1} f(x)
</pre></div>
<p>where <em>x</em>, <em>f</em> are vector quantities and <em>J</em> is the
Jacobian matrix <em>J_{ij} = d f_i / d x_j</em>.
Additional strategies can be used to enlarge the region of
convergence. These include requiring a decrease in the norm <em>|f|</em> on
each step proposed by Newton’s method, or taking steepest-descent steps in
the direction of the negative gradient of <em>|f|</em>.
</p>
<p>Several root-finding algorithms are available within a single framework.
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 evaluation of the Jacobian matrix can be problematic, either because
programming the derivatives is intractable or because computation of the
<em>n^2</em> terms of the matrix becomes too expensive. For these reasons
the algorithms provided by the library are divided into two classes according
to whether the derivatives are available or not.
</p>
<a name="index-Jacobian-matrix_002c-root-finding"></a>
<p>The state for solvers with an analytic Jacobian matrix is held in a
<code>gsl_multiroot_fdfsolver</code> struct. The updating procedure requires
both the function and its derivatives to be supplied by the user.
</p>
<p>The state for solvers which do not use an analytic Jacobian matrix is
held in a <code>gsl_multiroot_fsolver</code> struct. The updating procedure
uses only function evaluations (not derivatives). The algorithms
estimate the matrix <em>J</em> or <em>J^{-1}</em> by approximate methods.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Initializing-the-Multidimensional-Solver.html#Initializing-the-Multidimensional-Solver" accesskey="n" rel="next">Initializing the Multidimensional Solver</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>
|
