Polynomial regression: Difference between revisions

{{out}}

{{out}}

The code listed below is good for up to 10000 data points

and fits an order-5 polynomial, so the test data for this task

is hardly challenging!

{{out}}

{{out}}

{{out}} (lower powers first, so this seems the opposite of the Python output):

{{out}}

{{out}} (lowest order coefficient first)

{{out}} in GHCi:

{{out}}

<pre>SOLVE performs a (nonlinear) least-square fit (Levenberg-Marquardt):

p(1)=2.997135145; p(2)=2.011348347; p(3)=0.9906627242; iterations=19;</pre>

Note that this implementation does not use floating point numbers,

so we do not introduce floating point errors.

Using exact arithmetic has a speed penalty,

but for small problems like this it is inconsequential.

The above solution fits a polynomial of order 11.

If the order of the polynomial is known to be 3

(as is implied in the task description)

then the following solution is probably preferable:

The least-squares fit problem for a degree <i>n</i>

can be solved with the built-in backslash operator:

<lang julia>function polyfit(x, y, n)

{{out}}

<pre>julia> x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3.0</pre>

Matlab has a built-in function "polyfit(x,y,n)" which performs this task.

The arguments x and y are vectors which are parametrized by the index suck that <math>point_{i} = (x_{i},y_{i})</math> and the argument n is the order of the polynomial you want to fit.

The output of this function is the coefficients of the polynomial which best fit these x,y value pairs.

{{out}}

Find max absolute error:

Thus we confirm once more that for already sorted sequences

the considered quick sort implementation has

quadratic dependence on sequence length

(see [[Query Performance|'''Example''' section for Python language

on ''Query Performance'' page]]).

The easiest (and most robust) approach to solve this in R

is to use the base package's ''lm'' function

which will find the least squares solution via a QR decomposition:

{{out}}

<pre>

</pre>

{{out}}

{{out}}

<!-- This implementation from Emiliano Gavilan;

posted here with his explicit permission -->

<code>seq(''expr'',''var'',''low'',''high'')</code> evaluates ''expr'' with ''var'' bound to integers from ''low'' to ''high'' and returns a list of the results. <code> →</code> is the assignment operator.

<code>QuadReg</code>, "quadratic regression", does the fit and stores the details in a number of standard variables, including <var>regeq</var>, which receives the fitted quadratic (polynomial) function itself.

We then apply that function to the (undefined as ensured by <code>DelVar</code>) variable x to obtain the expression in terms of x, and display it.

{{out}}

<code>3.·x² + 2.·x + 1.</code>

The fit function defined below returns the coefficients

of an nth-degree polynomial in order of descending degree

fitting the lists of inputs x and outputs y.

Ursala provides a simplified interface to this library

whereby the data can be passed as lists rather than arrays,

and all memory management is handled automatically.

{{out}}