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
|
<html lang="en">
<head>
<title>Minimization Algorithms - GNU Scientific Library -- Reference Manual</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Scientific Library -- Reference Manual">
<meta name="generator" content="makeinfo 4.8">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="One-dimensional-Minimization.html" title="One dimensional Minimization">
<link rel="prev" href="Minimization-Stopping-Parameters.html" title="Minimization Stopping Parameters">
<link rel="next" href="Minimization-Examples.html" title="Minimization Examples">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 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.2 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 freedom to copy and modify this
GNU Manual, like GNU software.''-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<p>
<a name="Minimization-Algorithms"></a>
Next: <a rel="next" accesskey="n" href="Minimization-Examples.html">Minimization Examples</a>,
Previous: <a rel="previous" accesskey="p" href="Minimization-Stopping-Parameters.html">Minimization Stopping Parameters</a>,
Up: <a rel="up" accesskey="u" href="One-dimensional-Minimization.html">One dimensional Minimization</a>
<hr>
</div>
<h3 class="section">33.7 Minimization Algorithms</h3>
<p>The minimization algorithms described in this section require an initial
interval which is guaranteed to contain a minimum—if a and
b are the endpoints of the interval and x is an estimate
of the minimum then f(a) > f(x) < f(b). This ensures that the
function has at least one minimum somewhere in the interval. If a valid
initial interval is used then these algorithm cannot fail, provided the
function is well-behaved.
<div class="defun">
— Minimizer: <b>gsl_min_fminimizer_goldensection</b><var><a name="index-gsl_005fmin_005ffminimizer_005fgoldensection-2271"></a></var><br>
<blockquote>
<p><a name="index-golden-section-algorithm-for-finding-minima-2272"></a><a name="index-minimum-finding_002c-golden-section-algorithm-2273"></a>
The <dfn>golden section algorithm</dfn> is the simplest method of bracketing
the minimum of a function. It is the slowest algorithm provided by the
library, with linear convergence.
<p>On each iteration, the algorithm first compares the subintervals from
the endpoints to the current minimum. The larger subinterval is divided
in a golden section (using the famous ratio (3-\sqrt 5)/2 =
0.3189660<small class="dots">...</small>) and the value of the function at this new point is
calculated. The new value is used with the constraint f(a') >
f(x') < f(b') to a select new interval containing the minimum, by
discarding the least useful point. This procedure can be continued
indefinitely until the interval is sufficiently small. Choosing the
golden section as the bisection ratio can be shown to provide the
fastest convergence for this type of algorithm.
</blockquote></div>
<!-- ============================================================ -->
<div class="defun">
— Minimizer: <b>gsl_min_fminimizer_brent</b><var><a name="index-gsl_005fmin_005ffminimizer_005fbrent-2274"></a></var><br>
<blockquote><p><a name="index-Brent_0027s-method-for-finding-minima-2275"></a><a name="index-minimum-finding_002c-Brent_0027s-method-2276"></a>
The <dfn>Brent minimization algorithm</dfn> combines a parabolic
interpolation with the golden section algorithm. This produces a fast
algorithm which is still robust.
<p>The outline of the algorithm can be summarized as follows: on each
iteration Brent's method approximates the function using an
interpolating parabola through three existing points. The minimum of the
parabola is taken as a guess for the minimum. 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 golden section
step. The full details of Brent's method include some additional checks
to improve convergence.
</p></blockquote></div>
<!-- ============================================================ -->
</body></html>
|
