# Difference between revisions of "Example Polynomial Fitting"

In this example it is shown how EJML can be used to fit a polynomial of arbitrary degree to a set of data. The key concepts shown here are; 1) how to create a linear using LinearSolverFactory, 2) use an adjustable linear solver, 3) and effective matrix reshaping. This is all done using the procedural interface.

First a best fit polynomial is fit to a set of data and then a outliers are removed from the observation set and the coefficients recomputed. Outliers are removed efficiently using an adjustable solver that does not resolve the whole system again.

External Resources:

# PolynomialFit Example Code

```/**
* <p>
* This example demonstrates how a polynomial can be fit to a set of data.  This is done by
* using a least squares solver that is adjustable.  By using an adjustable solver elements
* can be inexpensively removed and the coefficients recomputed.  This is much less expensive
* than resolving the whole system from scratch.
* </p>
* <p>
* The following is demonstrated:<br>
* <ol>
*  <li>Creating a solver using LinearSolverFactory</li>
*  <li>reshaping</li>
* </ol>
*
* @author Peter Abeles
*/
public class PolynomialFit {
// Vandermonde matrix
DMatrixRMaj A;
// matrix containing computed polynomial coefficients
DMatrixRMaj coef;
// observation matrix
DMatrixRMaj y;

// solver used to compute

/**
* Constructor.
*
* @param degree The polynomial's degree which is to be fit to the observations.
*/
public PolynomialFit( int degree ) {
coef = new DMatrixRMaj(degree + 1, 1);
A = new DMatrixRMaj(1, degree + 1);
y = new DMatrixRMaj(1, 1);

// create a solver that allows elements to be added or removed efficiently
}

/**
* Returns the computed coefficients
*
* @return polynomial coefficients that best fit the data.
*/
public double[] getCoef() {
return coef.data;
}

/**
* Computes the best fit set of polynomial coefficients to the provided observations.
*
* @param samplePoints where the observations were sampled.
* @param observations A set of observations.
*/
public void fit( double[] samplePoints, double[] observations ) {
// Create a copy of the observations and put it into a matrix
y.reshape(observations.length, 1, false);
System.arraycopy(observations, 0, y.data, 0, observations.length);

// reshape the matrix to avoid unnecessarily declaring new memory
// save values is set to false since its old values don't matter
A.reshape(y.numRows, coef.numRows, false);

// set up the A matrix
for (int i = 0; i < observations.length; i++) {

double obs = 1;

for (int j = 0; j < coef.numRows; j++) {
A.set(i, j, obs);
obs *= samplePoints[i];
}
}

// process the A matrix and see if it failed
if (!solver.setA(A))
throw new RuntimeException("Solver failed");

// solver the the coefficients
solver.solve(y, coef);
}

/**
* Removes the observation that fits the model the worst and recomputes the coefficients.
* This is done efficiently by using an adjustable solver.  Often times the elements with
* the largest errors are outliers and not part of the system being modeled.  By removing them
* a more accurate set of coefficients can be computed.
*/
public void removeWorstFit() {
// find the observation with the most error
int worstIndex = -1;
double worstError = -1;

for (int i = 0; i < y.numRows; i++) {
double predictedObs = 0;

for (int j = 0; j < coef.numRows; j++) {
predictedObs += A.get(i, j)*coef.get(j, 0);
}

double error = Math.abs(predictedObs - y.get(i, 0));

if (error > worstError) {
worstError = error;
worstIndex = i;
}
}

// nothing left to remove, so just return
if (worstIndex == -1)
return;

// remove that observation
removeObservation(worstIndex);

// update A
solver.removeRowFromA(worstIndex);

// solve for the parameters again
solver.solve(y, coef);
}

/**
* Removes an element from the observation matrix.
*
* @param index which element is to be removed
*/
private void removeObservation( int index ) {
final int N = y.numRows - 1;
final double[] d = y.data;

// shift
for (int i = index; i < N; i++) {
d[i] = d[i + 1];
}
y.numRows--;
}
}
```