• https://me.yahoo.com
COST (GBP)
9.60
0.30
0

# Discrete

viewed 5695 times and licensed 60 times
Approximates a discrete function using least squares polynomial fitting.
Controller: CodeCogs

C++

## Class Discrete

This class approximates an arbitrary discrete function using polynomial least squares fitting.

The algorithm finds the coefficients $\inline&space;&space;a_i$, with $\inline&space;&space;0&space;\leq&space;i&space;\leq&space;n$ such that the following polynomial fits the given set of points with minimum error, using leasts squares minimization
$y&space;=&space;a_0&space;+&space;a_1x&space;+&space;a_2x^2&space;+&space;\ldots&space;+&space;a_kx^k$
For this function the residual (or error between y and that calculationed using the coefficients) is given by
$R^2&space;=&space;\sum_{i=1}^{n}&space;\left&space;[&space;y_i&space;-&space;(a_0&space;+&space;a_1&space;x_i&space;+&space;a_2&space;x_i^2&space;+&space;\ldots&space;+&space;a_k&space;x_i^k)&space;\right&space;]^2$

From which the rate of change of this error with respect to each constant are, which ideally we want to make zero:
$\frac{\partial(R^2)}{\partial&space;a_0}&space;=&space;-2&space;\sum_{i=1}^n&space;\left&space;[&space;y_i&space;-&space;(a_0&space;+&space;a_1&space;x_i&space;+&space;a_2&space;x_i^2&space;+&space;\ldots&space;+&space;a_k&space;x_i^k)&space;\right&space;]&space;=&space;0$
$\frac{\partial(R^2)}{\partial&space;a_1}&space;=&space;-2&space;\sum_{i=1}^n&space;\left&space;[&space;y_i&space;-&space;(a_0&space;+&space;a_1&space;x_i&space;+&space;a_2&space;x_i^2&space;+&space;\ldots&space;+&space;a_k&space;x_i^k)&space;\right&space;]&space;x_i&space;=&space;0$
$\frac{\partial(R^2)}{\partial&space;a_k}&space;=&space;-2&space;\sum_{i=1}^n&space;\left&space;[&space;y_i&space;-&space;(a_0&space;+&space;a_1&space;x_i&space;+&space;a_2&space;x_i^2&space;+&space;\ldots&space;+&space;a_k&space;x_i^k)&space;\right&space;]&space;x_i^k&space;=&space;0$

Equating to zero and rearranging to seperate the constants a from y, gives:
$a_o&space;n&space;+&space;a_1&space;\sum_{i=1}^n&space;x_i&space;+&space;\ldots&space;+&space;a_k&space;\sum_{i=1}^n&space;x_i^k&space;=&space;\sum_{i=1}^n&space;y_i$
$a_o&space;\sum_{i=1}^n&space;x_i&space;+&space;a_1&space;\sum_{i=1}^n&space;x_i^2&space;+&space;\ldots&space;+&space;a_k&space;\sum_{i=1}^n&space;x_i^{k+1}&space;=&space;\sum_{i=1}^n&space;x_i&space;y_i$
$a_o&space;\sum_{i=1}^n&space;x_i^k&space;&space;+&space;a_1&space;\sum_{i=1}^n&space;x_i^{k+1}&space;+&space;\ldots&space;+&space;a_k&space;\sum_{i=1}^n&space;x_i^{2k}&space;=&space;\sum_{i=1}^n&space;x_i^k&space;y_i$
which in matrix form, yields
$\left&space;[&space;\begin{array}{ccccccc}&space;n&space;&&&space;\sum_{i=1}^n&space;x_i&space;&&&space;\ldots&space;&&&space;&space;\sum_{i=1}^n&space;x_i^k&space;\\&space;&space;&space;\sum_{i=1}^n&space;x_i&space;&&&space;\sum_{i=1}^n&space;x_i^2&space;&&&space;\ldots&space;&&&space;\sum_{i=1}^n&space;x_i^{k+1}&space;\\&space;&space;&space;\vdots&space;&&&space;\vdots&space;&&&space;\ddots&space;&&&space;\vdots&space;\\&space;&space;\sum_{i=1}^n&space;x_i^k&space;&&&space;\sum_{i=1}^n&space;x_i^{k+1}&space;&&&space;\ldots&space;&&&space;\sum_{i=1}^n&space;x_i^{2k}&space;&space;&space;\end{array}&space;\right&space;]&space;\left&space;[&space;\begin{array}{c}&space;a_0&space;\\&space;a_1&space;\\&space;\vdots&space;\\&space;a_k&space;\end{array}&space;\right&space;]&space;=&space;&space;\left&space;[&space;\begin{array}{c}&space;\sum_{i=1}^n&space;y_i&space;\\&space;\sum_{i=1}^n&space;x_i&space;y_i&space;\\&space;\vdots&space;\\&space;\sum_{i=1}^n&space;x_i^k&space;y&space;\end{array}&space;\right&space;]$
Solving this solutions using a matrix transpose, yields the coefficients a in terms of x and y.

Below you will find the regression graph for a set of points obtained by evaluating the function $\inline&space;&space;f(x)&space;=&space;\sin(x)&space;/&space;x$. The regression polynomial using a variety of orders are displayed (same results are shown in example below)

## References:

### Example 1

The following example displays 10 approximated values (you may change this amount through the N_out variable) for the function $\inline&space;&space;g(x)&space;=&space;\sin(x)&space;/&space;x$ with abscissas equally spaced in the $\inline&space;&space;[&space;\pi/2,&space;4\pi]$ interval. The X and Y coordinate arrays are initialized by evaluating this function for N = 20 points equally spaced in the domain from $\inline&space;&space;\pi/2$ to $\inline&space;&space;4\pi$.

#include <cmath>
#include <stdio.h>
using namespace std;

#define PI  3.1415926535897932384626433832795
#define N   30

int main()
{
// Delvare two arrays to hold the coordinates of initial data points
double x[N], y[N];

// Generate the points
double xx = PI/2;
double step = 2 * PI / (N - 1);

for (int i = 0; i < N; ++i, xx += step)
{
double x2=xx+sin(xx);   // vary x spacing
x[i] = x2;
y[i] = sin(x2)/x2;
}

// Initialize the regression approximation routine with known data points
Maths::Regression::Discrete A(N, x, y, 3);
Maths::Regression::Discrete B(N, x, y, 5);
Maths::Regression::Discrete C(N, x, y, 10);

// Interrogate the regression function to find approximated values
int N_out =50;
xx = PI/2 ;
step = 2 * PI / (N_out - 1);

printf("\nx, exact, discrete_3,  discrete_5,  discrete_10");

for (int i = 0; i < N_out; ++i, xx += step)
{
double x2=xx+sin(xx);
printf("\n%.4lf, %.6lf, %.6lf, %.6lf, %.6lf", x2, sin(x2)/x2, A.getValue(x2), B.getValue(x2),
C.getValue(x2));
}
return 0;
}
Output (first 10 numbers):
x, exact, discrete_3,  discrete_5,  discrete_10
2.5708, 0.210169, 0.235747, 0.210570, 0.210190
2.6908, 0.161909, 0.175569, 0.162336, 0.161899
2.7945, 0.121709, 0.127760, 0.122034, 0.121692
2.8824, 0.088920, 0.090229, 0.089115, 0.088905
2.9550, 0.062769, 0.061196, 0.062848, 0.062759
3.0134, 0.042441, 0.039160, 0.042431, 0.042435
3.0585, 0.027131, 0.022864, 0.027058, 0.027128
3.0919, 0.016071, 0.011248, 0.015955, 0.016070
3.1150, 0.008531, 0.003406, 0.008388, 0.008532
3.1296, 0.003821, -0.001463, 0.003663, 0.003822

### Authors

Lucian Bentea (August 2005)
Will Bateman (Mar 2006)
##### Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

## Members of Discrete

#### Discrete

 Discrete( int n double* x double* y int degree )[constructor]
Initializes the necessary data for following evaluations of the polynomial.
 n Total number of data points to analyse. x An array [0 to n-1] with x-coordinates of points. y An array [0 to n-1] with y-coordinates of points. degree The number of coefficient to be used in the polynomial fitting.

#### ~Discrete

 ~Discrete( )
Detailed Description...

#### GetValue

 doublegetValue( double x )
Returns the approximated ordinate at the given abscissa.
 x The abscissa of the approximation point

#### GetCoefficent

 doublegetCoefficent( int i )
Returns individual coefficient from the computed polynomial, i.e. $\inline&space;a_i$ in the following equation:
$P(x)&space;=&space;a_0&space;+&space;a_1x&space;+&space;a_2x^2&space;+&space;\ldots&space;+&space;a_nx^n$

### Example 2

...
Maths::Regression::Discrete A(N, x, y, 7);
for(int i=0;i<7;i++) printf("\n coefficient %d is %lf", A.getCoefficient(i));
...
 i The ith coefficient, starting at i=0 to degree.

## Discrete Once

 doubleDiscrete_once( int N double* x double* y int degree double a )
This function implements the Discrete class for one off calculations, thereby avoid the need to instantiate the Discrete class yourself.

### Example 3

The following graph is constructed from interpolating the following values:
x = 1  y = 0.22
x = 2  y = 0.04
x = 3  y = -0.13
x = 4  y = -0.17
x = 5  y = -0.04
x = 6  y = 0.09
x = 7  y = 0.11
There is an error with your graph parameters for Discrete_once with options N=7 x="1 2 3 4 5 6 7" y="0.22 0.04 -0.13 -0.17 -0.04 0.09 0.11" a=1:7 degree=5 .input

Error Message:Function Discrete_once failed. Ensure that: Invalid C++

### Parameters

 N The number of initial points x The x-coordinates for the initial points y The y-coordinates for the initial points degree The number of coefficient to be used in the polynomial fitting (the order) a the x-coordinate for the point to be computed

### Returns

the y-coordinate that corresponds to a.
##### Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.