User Manual 4.15 Trigonometric Polynomials and Fourier Series
Introduction
Scope
This section presents the Trigonometric Polynomials implemented in PATRIUS as well as Fourier Series.
Javadoc
The trigonometric polynomial (and related) objects are available in the package fr.cnes.sirius.patrius.math.analysis.polynomials and the FFT algorithms in fr.cnes.sirius.patrius.math.transform
| Library | Javadoc |
|---|---|
| Patrius | Package fr.cnes.sirius.patrius.math.geometry.analysis.polynomials |
| Patrius | Package fr.cnes.sirius.patrius.math.transform |
Links
Useful resources for this theme can be found here :
Useful Documents
None.
Package Overview
None.
Features Description
Trigonometric Polynomials
The trigonometric polynomials are defined as :
[math]\forall t \in \mathbb{R}, P(t) = a_0 + \sum_{k=0}^n \left( a_k \cos(kt) + b_k \sin(kt) \right)[/math]
And the primitive of such a function is :
[math]\forall t \in \mathbb{R}, P(t) = a_0 t + c^{te} + \sum_{k=0}^n \left( {-b_k \over k} \cos(kt) + {a_k \over k} \sin(kt) \right)[/math]
Classes that represent these functions are described in this section.
Fourier Series
Let [math]f[/math] be a periodic, real variable, real function with period [math]T[/math]. The partial sums of the Fourier Series of [math]f[/math] are given by
[math] \forall N \in \mathbb{R}^{+*}, \, \left(S_Nf\right)(x) = a_0 + \sum_{n=1}^N\left(a_n\cos\left(n t {2\pi\over T}\right) + b_n\sin\left(n t {2\pi\over T}\right)\right) [/math]
The Fourier coefficients (n > 0) of [math]f[/math] are given by :
[math] a_0 = {1\over T}\int_{-T/2}^{T/2} \! f(t) \, \mathrm{d}t [/math]
[math] a_n = {2\over T}\int_{-T/2}^{T/2} \! f(t) \cos\left(n t {2\pi\over T}\right) \, \mathrm{d}t [/math]
[math] b_n = {2\over T}\int_{-T/2}^{T/2} \! f(t) \sin\left(n t {2\pi\over T}\right) \, \mathrm{d}t [/math]
Classes that allow decomposing functions into finite Fourier series are described.
Fast Fourier Transforms
A fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse. Fourier analysis converts time (or space) to frequency and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors.
Let [math]( X_0, ..., X_{N-1})[/math] be complex numbers. The DFT is defined by the formula
[math]X_k = \sum^{N-1}_{n=0} x_n e^{-2i\pi k n/N}, \quad k=\left\{0, ..., N-1\right\}.[/math]
The class FastFourierTransformer.java owns two methods
transform(final double[] f, final TransformType type)
transform(final Complex[] f, final TransformType type)
where TransformType is an enumeration that defines the type of transform which is to be computed. It can be FORWARD or INVERSE.
Depending on the size, this method will use a radix-2 algorithm if the size is a power-of-two, and the Bluestein algorithm otherwise. Both algorithms are explained above.
The Cooley–Tukey & radix-2 the algorithm
By far the most commonly used FFT algorithm. This is a divide and conquer algorithm that recursively breaks down a DFT of any composite size [math]N = N_1N_2[/math] into many smaller DFTs of sizes [math]N_1[/math] and [math]N_2[/math], along with [math]O(N)[/math] multiplications by complex roots of unity.
The radix-2 algorithme is the most common use of FFT algorithm and is based on the Cooley–Tukey algorithm. It divides the transform into two pieces of size [math]N/2[/math] at each step, and is therefore limited to power-of-two sizes.
The Bluestein algorithm
It is commonly called the chirp z-transform algorithm. It computes the discrete Fourier transform (DFT) of arbitrary sizes (including prime sizes) by re-expressing the DFT as a convolution. For more information, see http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm
Getting Started
Usage of a trigonometric polynomial
- To create the polynomial [math]P(x) =-2 + \cos(x) + 2\sin(3x)[/math], use the following code snippet :
double a0 =-2; double[] a = new double[] {1, 0, 0}; double[] b = new double[] {0, 0, 2}; TrigonometricPolynomialFunction myPol2 = new TrigonometricPolynomialFunction(a0, a, b);
- To get the value of the second derivative at [math]x = 5[/math], use the following snippet :
double result = myPol2.value(2,5); // equivalent to double result = myPol2.polynomialDerivative(2).value(5);
- To get the primitive :
// With an integration constant c = 1 : TrigonometricPolynomialPrimitive result = myPol2.polynomialPrimitive(1.);
- To multiply two trigonometric polynomials [math]p1[/math] and [math]p2[/math] :
TrigonometricPolynomialFunction result = p1.multiply(p2);
Decomposing a UnivariateFunction into a Fourier Series
Given a user function with period T :
UnivariateFunction f = new UnivariateFunction () { public double value(double x) { // ... return result; } };
The user must build an instance of the FourierDecompositionEngine (using an integrator) :
FourierDecompositionEngine engine = new FourierDecompositionEngine( integrator );
And pass the function, period and approximation order to it.NOTE : It is left up to the user to make sure that the specified period is coherent with the function as no internal check is conducted.
engine.setOrder(10); engine.setFunction(f, T);
Then, the user can call the decompose( ) method :
FourierSeriesApproximation approximation = engine.decompose(); FourierSeries fourier = approximation.getFourier();
Example
The following code snippet shows how to decompose a square function of period 2 to the 10th order :
// function definition UnivariateFunction function = new UnivariateFunction() { public double value(final double x) { final double local = x- FastMath.floor(x / 2) * 2; if (local >= 1) { return-1; } else { return 1; } } }; // Engine parameters UnivariateIntegrator integrator = new LegendreGaussIntegrator(5, 1e-14, 1e-14); FourierDecompositionEngine engine = new FourierDecompositionEngine(integrator); engine.setMaxEvals(Integer.MAX_VALUE); // decompose double period = 2; engine.setOrder(10); engine.setFunction(function, period); FourierSeriesApproximation result = engine.decompose(); FourierSeries fourier = result.getFourier();
The function and its approximation are shown hereunder. The parasite undulations are known as the Gibbs Phenomenon :
Contents
Interfaces
| Interface | Summary | Javadoc |
|---|---|---|
| UnivariateDifferentiableFunction | Extension of UnivariateFunction representing a differentiable univariate function. | ... |
| IntegrableUnivariateFunction | Extension of UnivariateRealFunction representing an integrable univariate function. | ... |
| UnivariateFunction | Interface representing an univariate function. | ... |
| IFastFourierTransformer | Interface representing a FFT. | ... |
Classes
| Class | Summary | Javadoc |
|---|---|---|
| FourierDecompositionEngine | Decompose a UnivariateFunction as a Fourier Series using TrigonometricPolynomialFunction representation. | ... |
| FourierSeries | This class represents a finite Fourier Series. | ... |
| FourierSeriesApproximation | Holder for a UnivariateFunction and its FourierSeries approximation. | ... |
| TrigonometricPolynomialFunction | This class is the Trigonometric Polynomial Function class. | ... |
| TrigonometricPolynomialPrimitive | This class represents a Trigonometric Polynomial Primitive. | ... |
| AbstractFastFourierTransformer | Abstract class representing a FFT. | ... |
| FastFourierTransformer | Computes the FFT for real and complex arrays. | ... |
