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
|
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.math3.analysis.solvers;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.exception.NoBracketingException;
import org.apache.commons.math3.exception.TooManyEvaluationsException;
/**
* Implements the <em>Secant</em> method for root-finding (approximating a
* zero of a univariate real function). The solution that is maintained is
* not bracketed, and as such convergence is not guaranteed.
*
* <p>Implementation based on the following article: M. Dowell and P. Jarratt,
* <em>A modified regula falsi method for computing the root of an
* equation</em>, BIT Numerical Mathematics, volume 11, number 2,
* pages 168-174, Springer, 1971.</p>
*
* <p>Note that since release 3.0 this class implements the actual
* <em>Secant</em> algorithm, and not a modified one. As such, the 3.0 version
* is not backwards compatible with previous versions. To use an algorithm
* similar to the pre-3.0 releases, use the
* {@link IllinoisSolver <em>Illinois</em>} algorithm or the
* {@link PegasusSolver <em>Pegasus</em>} algorithm.</p>
*
*/
public class SecantSolver extends AbstractUnivariateSolver {
/** Default absolute accuracy. */
protected static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
/** Construct a solver with default accuracy (1e-6). */
public SecantSolver() {
super(DEFAULT_ABSOLUTE_ACCURACY);
}
/**
* Construct a solver.
*
* @param absoluteAccuracy absolute accuracy
*/
public SecantSolver(final double absoluteAccuracy) {
super(absoluteAccuracy);
}
/**
* Construct a solver.
*
* @param relativeAccuracy relative accuracy
* @param absoluteAccuracy absolute accuracy
*/
public SecantSolver(final double relativeAccuracy,
final double absoluteAccuracy) {
super(relativeAccuracy, absoluteAccuracy);
}
/** {@inheritDoc} */
@Override
protected final double doSolve()
throws TooManyEvaluationsException,
NoBracketingException {
// Get initial solution
double x0 = getMin();
double x1 = getMax();
double f0 = computeObjectiveValue(x0);
double f1 = computeObjectiveValue(x1);
// If one of the bounds is the exact root, return it. Since these are
// not under-approximations or over-approximations, we can return them
// regardless of the allowed solutions.
if (f0 == 0.0) {
return x0;
}
if (f1 == 0.0) {
return x1;
}
// Verify bracketing of initial solution.
verifyBracketing(x0, x1);
// Get accuracies.
final double ftol = getFunctionValueAccuracy();
final double atol = getAbsoluteAccuracy();
final double rtol = getRelativeAccuracy();
// Keep finding better approximations.
while (true) {
// Calculate the next approximation.
final double x = x1 - ((f1 * (x1 - x0)) / (f1 - f0));
final double fx = computeObjectiveValue(x);
// If the new approximation is the exact root, return it. Since
// this is not an under-approximation or an over-approximation,
// we can return it regardless of the allowed solutions.
if (fx == 0.0) {
return x;
}
// Update the bounds with the new approximation.
x0 = x1;
f0 = f1;
x1 = x;
f1 = fx;
// If the function value of the last approximation is too small,
// given the function value accuracy, then we can't get closer to
// the root than we already are.
if (FastMath.abs(f1) <= ftol) {
return x1;
}
// If the current interval is within the given accuracies, we
// are satisfied with the current approximation.
if (FastMath.abs(x1 - x0) < FastMath.max(rtol * FastMath.abs(x1), atol)) {
return x1;
}
}
}
}
|
