1 /*
2 * Licensed to the Hipparchus project under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The Hipparchus project licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.hipparchus.analysis.polynomials;
18
19 import org.hipparchus.CalculusFieldElement;
20 import org.hipparchus.Field;
21 import org.hipparchus.analysis.CalculusFieldUnivariateFunction;
22 import org.hipparchus.exception.LocalizedCoreFormats;
23 import org.hipparchus.exception.MathIllegalArgumentException;
24 import org.hipparchus.exception.NullArgumentException;
25 import org.hipparchus.util.FastMath;
26 import org.hipparchus.util.MathArrays;
27 import org.hipparchus.util.MathUtils;
28
29 /**
30 * Immutable representation of a real polynomial function with real coefficients.
31 * <p>
32 * <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a>
33 * is used to evaluate the function.</p>
34 * @param <T> the type of the field elements
35 * @since 1.5
36 *
37 */
38 public class FieldPolynomialFunction<T extends CalculusFieldElement<T>> implements CalculusFieldUnivariateFunction<T> {
39
40 /**
41 * The coefficients of the polynomial, ordered by degree -- i.e.,
42 * coefficients[0] is the constant term and coefficients[n] is the
43 * coefficient of x^n where n is the degree of the polynomial.
44 */
45 private final T[] coefficients;
46
47 /**
48 * Construct a polynomial with the given coefficients. The first element
49 * of the coefficients array is the constant term. Higher degree
50 * coefficients follow in sequence. The degree of the resulting polynomial
51 * is the index of the last non-null element of the array, or 0 if all elements
52 * are null.
53 * <p>
54 * The constructor makes a copy of the input array and assigns the copy to
55 * the coefficients property.</p>
56 *
57 * @param c Polynomial coefficients.
58 * @throws NullArgumentException if {@code c} is {@code null}.
59 * @throws MathIllegalArgumentException if {@code c} is empty.
60 */
61 public FieldPolynomialFunction(final T[] c)
62 throws MathIllegalArgumentException, NullArgumentException {
63 super();
64 MathUtils.checkNotNull(c);
65 int n = c.length;
66 if (n == 0) {
67 throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
68 }
69 while ((n > 1) && (c[n - 1].isZero())) {
70 --n;
71 }
72 this.coefficients = MathArrays.buildArray(c[0].getField(), n);
73 System.arraycopy(c, 0, this.coefficients, 0, n);
74 }
75
76 /**
77 * Compute the value of the function for the given argument.
78 * <p>
79 * The value returned is </p><p>
80 * {@code coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]}
81 * </p>
82 *
83 * @param x Argument for which the function value should be computed.
84 * @return the value of the polynomial at the given point.
85 *
86 * @see org.hipparchus.analysis.UnivariateFunction#value(double)
87 */
88 public T value(double x) {
89 return evaluate(coefficients, getField().getZero().add(x));
90 }
91
92 /**
93 * Compute the value of the function for the given argument.
94 * <p>
95 * The value returned is </p><p>
96 * {@code coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]}
97 * </p>
98 *
99 * @param x Argument for which the function value should be computed.
100 * @return the value of the polynomial at the given point.
101 *
102 * @see org.hipparchus.analysis.UnivariateFunction#value(double)
103 */
104 @Override
105 public T value(T x) {
106 return evaluate(coefficients, x);
107 }
108
109 /** Get the {@link Field} to which the instance belongs.
110 * @return {@link Field} to which the instance belongs
111 */
112 public Field<T> getField() {
113 return coefficients[0].getField();
114 }
115
116 /**
117 * Returns the degree of the polynomial.
118 *
119 * @return the degree of the polynomial.
120 */
121 public int degree() {
122 return coefficients.length - 1;
123 }
124
125 /**
126 * Returns a copy of the coefficients array.
127 * <p>
128 * Changes made to the returned copy will not affect the coefficients of
129 * the polynomial.</p>
130 *
131 * @return a fresh copy of the coefficients array.
132 */
133 public T[] getCoefficients() {
134 return coefficients.clone();
135 }
136
137 /**
138 * Uses Horner's Method to evaluate the polynomial with the given coefficients at
139 * the argument.
140 *
141 * @param coefficients Coefficients of the polynomial to evaluate.
142 * @param argument Input value.
143 * @param <T> the type of the field elements
144 * @return the value of the polynomial.
145 * @throws MathIllegalArgumentException if {@code coefficients} is empty.
146 * @throws NullArgumentException if {@code coefficients} is {@code null}.
147 */
148 protected static <T extends CalculusFieldElement<T>> T evaluate(T[] coefficients, T argument)
149 throws MathIllegalArgumentException, NullArgumentException {
150 MathUtils.checkNotNull(coefficients);
151 int n = coefficients.length;
152 if (n == 0) {
153 throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
154 }
155 T result = coefficients[n - 1];
156 for (int j = n - 2; j >= 0; j--) {
157 result = argument.multiply(result).add(coefficients[j]);
158 }
159 return result;
160 }
161
162 /**
163 * Add a polynomial to the instance.
164 *
165 * @param p Polynomial to add.
166 * @return a new polynomial which is the sum of the instance and {@code p}.
167 */
168 public FieldPolynomialFunction<T> add(final FieldPolynomialFunction<T> p) {
169 // identify the lowest degree polynomial
170 final int lowLength = FastMath.min(coefficients.length, p.coefficients.length);
171 final int highLength = FastMath.max(coefficients.length, p.coefficients.length);
172
173 // build the coefficients array
174 T[] newCoefficients = MathArrays.buildArray(getField(), highLength);
175 for (int i = 0; i < lowLength; ++i) {
176 newCoefficients[i] = coefficients[i].add(p.coefficients[i]);
177 }
178 System.arraycopy((coefficients.length < p.coefficients.length) ?
179 p.coefficients : coefficients,
180 lowLength,
181 newCoefficients, lowLength,
182 highLength - lowLength);
183
184 return new FieldPolynomialFunction<>(newCoefficients);
185 }
186
187 /**
188 * Subtract a polynomial from the instance.
189 *
190 * @param p Polynomial to subtract.
191 * @return a new polynomial which is the instance minus {@code p}.
192 */
193 public FieldPolynomialFunction<T> subtract(final FieldPolynomialFunction<T> p) {
194 // identify the lowest degree polynomial
195 int lowLength = FastMath.min(coefficients.length, p.coefficients.length);
196 int highLength = FastMath.max(coefficients.length, p.coefficients.length);
197
198 // build the coefficients array
199 T[] newCoefficients = MathArrays.buildArray(getField(), highLength);
200 for (int i = 0; i < lowLength; ++i) {
201 newCoefficients[i] = coefficients[i].subtract(p.coefficients[i]);
202 }
203 if (coefficients.length < p.coefficients.length) {
204 for (int i = lowLength; i < highLength; ++i) {
205 newCoefficients[i] = p.coefficients[i].negate();
206 }
207 } else {
208 System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
209 highLength - lowLength);
210 }
211
212 return new FieldPolynomialFunction<>(newCoefficients);
213 }
214
215 /**
216 * Negate the instance.
217 *
218 * @return a new polynomial with all coefficients negated
219 */
220 public FieldPolynomialFunction<T> negate() {
221 final T[] newCoefficients = MathArrays.buildArray(getField(), coefficients.length);
222 for (int i = 0; i < coefficients.length; ++i) {
223 newCoefficients[i] = coefficients[i].negate();
224 }
225 return new FieldPolynomialFunction<>(newCoefficients);
226 }
227
228 /**
229 * Multiply the instance by a polynomial.
230 *
231 * @param p Polynomial to multiply by.
232 * @return a new polynomial equal to this times {@code p}
233 */
234 public FieldPolynomialFunction<T> multiply(final FieldPolynomialFunction<T> p) {
235 final Field<T> field = getField();
236 final T[] newCoefficients = MathArrays.buildArray(field, coefficients.length + p.coefficients.length - 1);
237
238 for (int i = 0; i < newCoefficients.length; ++i) {
239 newCoefficients[i] = field.getZero();
240 for (int j = FastMath.max(0, i + 1 - p.coefficients.length);
241 j < FastMath.min(coefficients.length, i + 1);
242 ++j) {
243 newCoefficients[i] = newCoefficients[i].add(coefficients[j].multiply(p.coefficients[i-j]));
244 }
245 }
246
247 return new FieldPolynomialFunction<>(newCoefficients);
248 }
249
250 /**
251 * Returns the coefficients of the derivative of the polynomial with the given coefficients.
252 *
253 * @param coefficients Coefficients of the polynomial to differentiate.
254 * @param <T> the type of the field elements
255 * @return the coefficients of the derivative or {@code null} if coefficients has length 1.
256 * @throws MathIllegalArgumentException if {@code coefficients} is empty.
257 * @throws NullArgumentException if {@code coefficients} is {@code null}.
258 */
259 protected static <T extends CalculusFieldElement<T>> T[] differentiate(T[] coefficients)
260 throws MathIllegalArgumentException, NullArgumentException {
261 MathUtils.checkNotNull(coefficients);
262 int n = coefficients.length;
263 if (n == 0) {
264 throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
265 }
266 final Field<T> field = coefficients[0].getField();
267 final T[] result = MathArrays.buildArray(field, FastMath.max(1, n - 1));
268 if (n == 1) {
269 result[0] = field.getZero();
270 } else {
271 for (int i = n - 1; i > 0; i--) {
272 result[i - 1] = coefficients[i].multiply(i);
273 }
274 }
275 return result;
276 }
277
278 /**
279 * Returns an anti-derivative of this polynomial, with 0 constant term.
280 *
281 * @return a polynomial whose derivative has the same coefficients as this polynomial
282 */
283 public FieldPolynomialFunction<T> antiDerivative() {
284 final Field<T> field = getField();
285 final int d = degree();
286 final T[] anti = MathArrays.buildArray(field, d + 2);
287 anti[0] = field.getZero();
288 for (int i = 1; i <= d + 1; i++) {
289 anti[i] = coefficients[i - 1].multiply(1.0 / i);
290 }
291 return new FieldPolynomialFunction<>(anti);
292 }
293
294 /**
295 * Returns the definite integral of this polymomial over the given interval.
296 * <p>
297 * [lower, upper] must describe a finite interval (neither can be infinite
298 * and lower must be less than or equal to upper).
299 *
300 * @param lower lower bound for the integration
301 * @param upper upper bound for the integration
302 * @return the integral of this polymomial over the given interval
303 * @throws MathIllegalArgumentException if the bounds do not describe a finite interval
304 */
305 public T integrate(final double lower, final double upper) {
306 final T zero = getField().getZero();
307 return integrate(zero.add(lower), zero.add(upper));
308 }
309
310 /**
311 * Returns the definite integral of this polymomial over the given interval.
312 * <p>
313 * [lower, upper] must describe a finite interval (neither can be infinite
314 * and lower must be less than or equal to upper).
315 *
316 * @param lower lower bound for the integration
317 * @param upper upper bound for the integration
318 * @return the integral of this polymomial over the given interval
319 * @throws MathIllegalArgumentException if the bounds do not describe a finite interval
320 */
321 public T integrate(final T lower, final T upper) {
322 if (Double.isInfinite(lower.getReal()) || Double.isInfinite(upper.getReal())) {
323 throw new MathIllegalArgumentException(LocalizedCoreFormats.INFINITE_BOUND);
324 }
325 if (lower.getReal() > upper.getReal()) {
326 throw new MathIllegalArgumentException(LocalizedCoreFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND);
327 }
328 final FieldPolynomialFunction<T> anti = antiDerivative();
329 return anti.value(upper).subtract(anti.value(lower));
330 }
331
332 /**
333 * Returns the derivative as a {@link FieldPolynomialFunction}.
334 *
335 * @return the derivative polynomial.
336 */
337 public FieldPolynomialFunction<T> polynomialDerivative() {
338 return new FieldPolynomialFunction<>(differentiate(coefficients));
339 }
340
341 }