1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.analysis.polynomials;
18
19 import java.util.ArrayList;
20
21 import org.apache.commons.math.fraction.BigFraction;
22
23
24
25
26
27
28
29 public class PolynomialsUtils {
30
31
32 private static final ArrayList<BigFraction> CHEBYSHEV_COEFFICIENTS;
33
34
35 private static final ArrayList<BigFraction> HERMITE_COEFFICIENTS;
36
37
38 private static final ArrayList<BigFraction> LAGUERRE_COEFFICIENTS;
39
40
41 private static final ArrayList<BigFraction> LEGENDRE_COEFFICIENTS;
42
43 static {
44
45
46
47 CHEBYSHEV_COEFFICIENTS = new ArrayList<BigFraction>();
48 CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);
49 CHEBYSHEV_COEFFICIENTS.add(BigFraction.ZERO);
50 CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);
51
52
53
54 HERMITE_COEFFICIENTS = new ArrayList<BigFraction>();
55 HERMITE_COEFFICIENTS.add(BigFraction.ONE);
56 HERMITE_COEFFICIENTS.add(BigFraction.ZERO);
57 HERMITE_COEFFICIENTS.add(BigFraction.TWO);
58
59
60
61 LAGUERRE_COEFFICIENTS = new ArrayList<BigFraction>();
62 LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);
63 LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);
64 LAGUERRE_COEFFICIENTS.add(BigFraction.MINUS_ONE);
65
66
67
68 LEGENDRE_COEFFICIENTS = new ArrayList<BigFraction>();
69 LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);
70 LEGENDRE_COEFFICIENTS.add(BigFraction.ZERO);
71 LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);
72
73 }
74
75
76
77
78 private PolynomialsUtils() {
79 }
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94 public static PolynomialFunction createChebyshevPolynomial(final int degree) {
95 return buildPolynomial(degree, CHEBYSHEV_COEFFICIENTS,
96 new RecurrenceCoefficientsGenerator() {
97 private final BigFraction[] coeffs = { BigFraction.ZERO, BigFraction.TWO, BigFraction.ONE };
98
99 public BigFraction[] generate(int k) {
100 return coeffs;
101 }
102 });
103 }
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119 public static PolynomialFunction createHermitePolynomial(final int degree) {
120 return buildPolynomial(degree, HERMITE_COEFFICIENTS,
121 new RecurrenceCoefficientsGenerator() {
122
123 public BigFraction[] generate(int k) {
124 return new BigFraction[] {
125 BigFraction.ZERO,
126 BigFraction.TWO,
127 new BigFraction(2 * k)};
128 }
129 });
130 }
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145 public static PolynomialFunction createLaguerrePolynomial(final int degree) {
146 return buildPolynomial(degree, LAGUERRE_COEFFICIENTS,
147 new RecurrenceCoefficientsGenerator() {
148
149 public BigFraction[] generate(int k) {
150 final int kP1 = k + 1;
151 return new BigFraction[] {
152 new BigFraction(2 * k + 1, kP1),
153 new BigFraction(-1, kP1),
154 new BigFraction(k, kP1)};
155 }
156 });
157 }
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172 public static PolynomialFunction createLegendrePolynomial(final int degree) {
173 return buildPolynomial(degree, LEGENDRE_COEFFICIENTS,
174 new RecurrenceCoefficientsGenerator() {
175
176 public BigFraction[] generate(int k) {
177 final int kP1 = k + 1;
178 return new BigFraction[] {
179 BigFraction.ZERO,
180 new BigFraction(k + kP1, kP1),
181 new BigFraction(k, kP1)};
182 }
183 });
184 }
185
186
187
188
189
190
191
192 private static PolynomialFunction buildPolynomial(final int degree,
193 final ArrayList<BigFraction> coefficients,
194 final RecurrenceCoefficientsGenerator generator) {
195
196 final int maxDegree = (int) Math.floor(Math.sqrt(2 * coefficients.size())) - 1;
197 synchronized (PolynomialsUtils.class) {
198 if (degree > maxDegree) {
199 computeUpToDegree(degree, maxDegree, generator, coefficients);
200 }
201 }
202
203
204
205
206
207
208
209
210
211 final int start = degree * (degree + 1) / 2;
212
213 final double[] a = new double[degree + 1];
214 for (int i = 0; i <= degree; ++i) {
215 a[i] = coefficients.get(start + i).doubleValue();
216 }
217
218
219 return new PolynomialFunction(a);
220
221 }
222
223
224
225
226
227
228
229 private static void computeUpToDegree(final int degree, final int maxDegree,
230 final RecurrenceCoefficientsGenerator generator,
231 final ArrayList<BigFraction> coefficients) {
232
233 int startK = (maxDegree - 1) * maxDegree / 2;
234 for (int k = maxDegree; k < degree; ++k) {
235
236
237 int startKm1 = startK;
238 startK += k;
239
240
241 BigFraction[] ai = generator.generate(k);
242
243 BigFraction ck = coefficients.get(startK);
244 BigFraction ckm1 = coefficients.get(startKm1);
245
246
247 coefficients.add(ck.multiply(ai[0]).subtract(ckm1.multiply(ai[2])));
248
249
250 for (int i = 1; i < k; ++i) {
251 final BigFraction ckPrev = ck;
252 ck = coefficients.get(startK + i);
253 ckm1 = coefficients.get(startKm1 + i);
254 coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])).subtract(ckm1.multiply(ai[2])));
255 }
256
257
258 final BigFraction ckPrev = ck;
259 ck = coefficients.get(startK + k);
260 coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])));
261
262
263 coefficients.add(ck.multiply(ai[1]));
264
265 }
266
267 }
268
269
270 private static interface RecurrenceCoefficientsGenerator {
271
272
273
274
275
276
277 BigFraction[] generate(int k);
278 }
279
280 }