1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.analysis;
18
19 import org.apache.commons.math.ConvergenceException;
20 import org.apache.commons.math.FunctionEvaluationException;
21 import org.apache.commons.math.MaxIterationsExceededException;
22 import org.apache.commons.math.complex.Complex;
23
24
25
26
27
28
29
30
31
32
33
34
35
36 public class LaguerreSolver extends UnivariateRealSolverImpl {
37
38
39 private static final long serialVersionUID = -3775334783473775723L;
40
41
42 private PolynomialFunction p;
43
44
45
46
47
48
49
50 public LaguerreSolver(UnivariateRealFunction f) throws
51 IllegalArgumentException {
52
53 super(f, 100, 1E-6);
54 if (f instanceof PolynomialFunction) {
55 p = (PolynomialFunction)f;
56 } else {
57 throw new IllegalArgumentException("Function is not polynomial.");
58 }
59 }
60
61
62
63
64
65
66 public PolynomialFunction getPolynomialFunction() {
67 return new PolynomialFunction(p.getCoefficients());
68 }
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85 public double solve(double min, double max, double initial) throws
86 ConvergenceException, FunctionEvaluationException {
87
88
89 if (p.value(min) == 0.0) { return min; }
90 if (p.value(max) == 0.0) { return max; }
91 if (p.value(initial) == 0.0) { return initial; }
92
93 verifyBracketing(min, max, p);
94 verifySequence(min, initial, max);
95 if (isBracketing(min, initial, p)) {
96 return solve(min, initial);
97 } else {
98 return solve(initial, max);
99 }
100 }
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120 public double solve(double min, double max) throws ConvergenceException,
121 FunctionEvaluationException {
122
123
124 if (p.value(min) == 0.0) { return min; }
125 if (p.value(max) == 0.0) { return max; }
126 verifyBracketing(min, max, p);
127
128 double coefficients[] = p.getCoefficients();
129 Complex c[] = new Complex[coefficients.length];
130 for (int i = 0; i < coefficients.length; i++) {
131 c[i] = new Complex(coefficients[i], 0.0);
132 }
133 Complex initial = new Complex(0.5 * (min + max), 0.0);
134 Complex z = solve(c, initial);
135 if (isRootOK(min, max, z)) {
136 setResult(z.getReal(), iterationCount);
137 return result;
138 }
139
140
141 Complex[] root = solveAll(c, initial);
142 for (int i = 0; i < root.length; i++) {
143 if (isRootOK(min, max, root[i])) {
144 setResult(root[i].getReal(), iterationCount);
145 return result;
146 }
147 }
148
149
150 throw new ConvergenceException();
151 }
152
153
154
155
156
157
158
159
160
161
162 protected boolean isRootOK(double min, double max, Complex z) {
163 double tolerance = Math.max(relativeAccuracy * z.abs(), absoluteAccuracy);
164 return (isSequence(min, z.getReal(), max)) &&
165 (Math.abs(z.getImaginary()) <= tolerance ||
166 z.abs() <= functionValueAccuracy);
167 }
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182 public Complex[] solveAll(double coefficients[], double initial) throws
183 ConvergenceException, FunctionEvaluationException {
184
185 Complex c[] = new Complex[coefficients.length];
186 Complex z = new Complex(initial, 0.0);
187 for (int i = 0; i < c.length; i++) {
188 c[i] = new Complex(coefficients[i], 0.0);
189 }
190 return solveAll(c, z);
191 }
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206 public Complex[] solveAll(Complex coefficients[], Complex initial) throws
207 MaxIterationsExceededException, FunctionEvaluationException {
208
209 int n = coefficients.length - 1;
210 int iterationCount = 0;
211 if (n < 1) {
212 throw new IllegalArgumentException
213 ("Polynomial degree must be positive: degree=" + n);
214 }
215 Complex c[] = new Complex[n+1];
216 for (int i = 0; i <= n; i++) {
217 c[i] = coefficients[i];
218 }
219
220
221 Complex root[] = new Complex[n];
222 for (int i = 0; i < n; i++) {
223 Complex subarray[] = new Complex[n-i+1];
224 System.arraycopy(c, 0, subarray, 0, subarray.length);
225 root[i] = solve(subarray, initial);
226
227 Complex newc = c[n-i];
228 Complex oldc = null;
229 for (int j = n-i-1; j >= 0; j--) {
230 oldc = c[j];
231 c[j] = newc;
232 newc = oldc.add(newc.multiply(root[i]));
233 }
234 iterationCount += this.iterationCount;
235 }
236
237 resultComputed = true;
238 this.iterationCount = iterationCount;
239 return root;
240 }
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255 public Complex solve(Complex coefficients[], Complex initial) throws
256 MaxIterationsExceededException, FunctionEvaluationException {
257
258 int n = coefficients.length - 1;
259 if (n < 1) {
260 throw new IllegalArgumentException
261 ("Polynomial degree must be positive: degree=" + n);
262 }
263 Complex N = new Complex((double)n, 0.0);
264 Complex N1 = new Complex((double)(n-1), 0.0);
265
266 int i = 1;
267 Complex pv = null;
268 Complex dv = null;
269 Complex d2v = null;
270 Complex G = null;
271 Complex G2 = null;
272 Complex H = null;
273 Complex delta = null;
274 Complex denominator = null;
275 Complex z = initial;
276 Complex oldz = new Complex(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
277 while (i <= maximalIterationCount) {
278
279
280 pv = coefficients[n];
281 dv = Complex.ZERO;
282 d2v = Complex.ZERO;
283 for (int j = n-1; j >= 0; j--) {
284 d2v = dv.add(z.multiply(d2v));
285 dv = pv.add(z.multiply(dv));
286 pv = coefficients[j].add(z.multiply(pv));
287 }
288 d2v = d2v.multiply(new Complex(2.0, 0.0));
289
290
291 double tolerance = Math.max(relativeAccuracy * z.abs(),
292 absoluteAccuracy);
293 if ((z.subtract(oldz)).abs() <= tolerance) {
294 resultComputed = true;
295 iterationCount = i;
296 return z;
297 }
298 if (pv.abs() <= functionValueAccuracy) {
299 resultComputed = true;
300 iterationCount = i;
301 return z;
302 }
303
304
305 G = dv.divide(pv);
306 G2 = G.multiply(G);
307 H = G2.subtract(d2v.divide(pv));
308 delta = N1.multiply((N.multiply(H)).subtract(G2));
309
310 Complex deltaSqrt = delta.sqrt();
311 Complex dplus = G.add(deltaSqrt);
312 Complex dminus = G.subtract(deltaSqrt);
313 denominator = dplus.abs() > dminus.abs() ? dplus : dminus;
314
315
316 if (denominator.equals(new Complex(0.0, 0.0))) {
317 z = z.add(new Complex(absoluteAccuracy, absoluteAccuracy));
318 oldz = new Complex(Double.POSITIVE_INFINITY,
319 Double.POSITIVE_INFINITY);
320 } else {
321 oldz = z;
322 z = z.subtract(N.divide(denominator));
323 }
324 i++;
325 }
326 throw new MaxIterationsExceededException(maximalIterationCount);
327 }
328 }