stella.math
Class Extrapolation

java.lang.Object
  stella.math.Extrapolation

Direct Known Subclasses:

LinearExtrapolation, ParabolicExtrapolation

public abstract class Extrapolation
extends Object

A class to predict sensor readings for at least 120 sec. A very specific part of mathematics, probably only useful for STELLA. The idea is that we take evenly spaced measurements (sensor datas) and extrapolate them 120 sec into the future to properly trace clouds swapping over the building. In fact, actual measurements show that the rise time in the humidity can be close to 200 sec., so fast detection of a rise is inevitable. Linear Prediction LinearPrediction proved insufficient.

The idea is now, and at the time of this writing I have no clue if this will be successful, to take a bunch of measurements (say, 100) and try either a linear or parabolic regression. Due to the evenly spaced measurement intervalls, the calculation of the design matrix can be skipped, the formulars get rather simple.

Assuming a fit to the y_k data points according to

       yk ≈ a+bt+ct²
   

with

       t=kΔt, Δt=1,
   

we have to minimize the deviation

       χ² = ∑(a+bk+ck²-yk)².
   

Differentiation with respect to a, b, and c and setting this derivative zero immediately gives you the parameters (n … number of points):

       a = 3[3n²S+3n(S-4Sk)+2(S-3Sk+5Skk)]/(n(n²-3n+2))
       b = (6S-6na-c(2n³+3n²+n))/(3n(n+1))
       c = 30[n²S+3n(S-2Sk)+2(S-3(Sk-Skk))]/(n(n4-5n²+4)),

       S   := ∑yk
       Sk  := ∑kyk
       Skk := ∑k²yk.
   

A simply linear fit a+bk yields:

       a = S/n-b(n+1)/2
       b = 12(Sk-S(n+1)/2)/n³
   

This abstract base class only provides common properties to both, linear and parabolic extrapolation. The actual extrapolating polynom is defined in non-abstract subclasses.

Field Summary

private int	brink An index pointer to allow proper update of data array and sums.
protected Polynom	extrapolate The polynom that is the extrapolator.
protected double[]	sum The different data sums.
protected double[]	yk The data array of values to extrapolate.
protected double	yk2sum The sum of the squares of the data points.

Constructor Summary

protected	Extrapolation() Constructs a new extrapolation object.
protected	Extrapolation(double[] data) Constructs a new extrapolation object.

Method Summary

protected abstract Polynom	calcPolynom() The abstract method returning the extrapolating polynom.
protected void	calcSum(int degree) Calculates the data sums according to the following schema: First, the ∑yk is calculated and stored in sum[0]. Now, as long as j is less or equal the argument, ∑kjyk is evaluated and stored at sum[j].
abstract double	getChi2() Returns an estimate of the goodness-of-fit.
int	getN() Returns the length of the data set.
Polynom	getPolynom() Returns the extrapolating polynom of the extrapolator.
double	predict(int step) Uses the extrapolating polynom to predict one value in the future, exactly spaced at the argument steps ahead.
void	setData(double[] data) Sets the measurment points of the extrapolator.
double	shiftBackward(double addyk) Shifts the entire data set backward for one point.
double	shiftForward(double addyk) Shifts the entire data set forward for one point.
protected abstract Polynom	updatePolynom() The abstract method returning an updated polynom if data has changed.
private void	updateSum(double out, double in, double step) Updates the data sums after shifting forward or backward for one index.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

extrapolate

protected Polynom extrapolate

The polynom that is the extrapolator.

yk

protected double[] yk

The data array of values to extrapolate.

sum

protected double[] sum

The different data sums. Array dimension equals polynom degree.

yk2sum

protected double yk2sum

The sum of the squares of the data points.

brink

private int brink

An index pointer to allow proper update of data array and sums.

Constructor Detail

Extrapolation

protected Extrapolation()

Constructs a new extrapolation object. Data can be set either later using setData(double[]).

Extrapolation

protected Extrapolation(double[] data)

Constructs a new extrapolation object. The data is immediately evaluated. Use of this constructor equlas the use of the default constructor and calling the setData(double[]) method with the array argument.

Method Detail

setData

public void setData(double[] data)

Sets the measurment points of the extrapolator. In the STELLA case these are the raw sensor values. Additionally, the extrapolating polynom is calculated, using the abstract method calcPolynom(). To allow one-step index shifting of the data, the brink index pointer is set to zero, indicating that the next data element that drops out is on index zero.

getN

public int getN()

Returns the length of the data set.

shiftForward

public double shiftForward(double addyk)

Shifts the entire data set forward for one point. This means that the value handed over is stored at the brink index, the element there is the element that drops out of the extrapolator's base. These two elements are also used to update the extrapolator's sums accordingly. At last, the extrapolating polynom is updated with a call to the updatePolynom() method that may possibly fork into the calcPolynom() method of the daugther class, but is intended for speed-up calculus.
To avoid round-off error accumulation, the sums are recunstructed on index flips.

Returns:

The data value that drops out from the extrapolator base.

shiftBackward

public double shiftBackward(double addyk)

Shifts the entire data set backward for one point. This means that the value handed over is stored at the brink-1 index, the element there is the element that drops out of the extrapolator's base. These two elements are also used to update the extrapolator's sums accordingly. At last, the extrapolating polynom is updated with a call to the updatePolynom() method that may possibly fork into the calcPolynom() method of the daugther class, but is intended for speed-up calculus.
To avoid round-off error accumulation, the sums are recunstructed on index flips.

Returns:

The data value that drops out from the extrapolator base.

predict

public double predict(int step)

Uses the extrapolating polynom to predict one value in the future, exactly spaced at the argument steps ahead.

Parameters:

step - The index of the future value to predict, 0=now.

Returns:

The extrapolated value, or NaN if undefined.

getPolynom

public Polynom getPolynom()

Returns the extrapolating polynom of the extrapolator. Null if no data was set.

getChi2

public abstract double getChi2()

Returns an estimate of the goodness-of-fit. This method should calculate χ² of the residuals. Again this simplifies for evenly spaced data. Note that this method does not return an estimate per point, so sometimes you'll have to divide the returned number by the square of the data set length.

calcPolynom

protected abstract Polynom calcPolynom()

The abstract method returning the extrapolating polynom. In most cases, non-abstract daugther classes will use the calcSum(int) method.
Note that the only data available at the entry point of this method are the measurements.

updatePolynom

protected abstract Polynom updatePolynom()

The abstract method returning an updated polynom if data has changed. This method may savely assume that not only the data has been updated, but also the different data sums sum are up-to-date.
May fork to calcPolynom() if no speed-gain can be achieved.

calcSum

protected void calcSum(int degree)

Calculates the data sums according to the following schema:

• First, the ∑y_k is calculated and stored in sum[0].
• Now, as long as j is less or equal the argument, ∑k^jy_k is evaluated and stored at sum[j].

Parameters:

degree - The degree of the extrapolating polynom, 1=linear

updateSum

private void updateSum(double out,
                       double in,
                       double step)

Updates the data sums after shifting forward or backward for one index. Using the binomical law it is possible to spare calculating of the entire sums by simply using the old sums and adding a few terms according to:

       Skm = ∑m over j (±1)m-j Skj+…
       

The maximum degree m of the sums is deduced from the array size of the sum array.

Parameters:

out - The value that drops out from the data set.

in - The value that newly enters the data set.

step - Either 1 or -1, for backward/forward update.