Possible function y=f(x) if data points are given.

[s0ft]

How could one obtain a function $y=f(x)$ that satisfies a number of data points $(x_{i},y_{i})$. That is how would it be possible to get a function if some points that are to lie on it have been given? I've seen some lectures on interpolation but all I've gotten is only the way to solve problems, not the exact 'why' or 'how' these tecnhiques work.
Things like direct interpolation are straightforward but Lagrange's method, Newton's Divided Difference etc are the things I'm talking about.

 

[arildno]

Let's take Lagrange's Method for interpolating polynomials.
What are we after? A polynomial of degree N that at (N+1) Points yields the prescribed y-values.

Let us think as follows:
If our polynomial consists of N+1 TERMS, each term having the property that they are Equal to zero at N of the prescribed Points, and Equal to a prescribed y-value, then it is easy to construct the Whole polynomial.

Suppose N=2
By Construction, we get p(x) easily as:
$$p(x)=\frac{(x-x_{2})(x-x_{3})}{(x_{1}-x_{2})(x_{1}-x_{3})}y_{1}+\frac{(x-x_{1})(x-x_{3})}{(x_{2}-x_{1})(x_{2}-x_{3})}y_{2}+\frac{(x-x_{1})(x-x_{2})}{(x_{3}-x_{1})(x_{3}-x_{2})}y_{3}$$

If you focus on what each term here actually does, it is simple to generate the similar polynomials for other degrees of N

 

[s0ft]

$$p(x)=\frac{(x-x_{2})(x-x_{3})}{(x_{1}-x_{2})(x_{1}-x_{3})}y_{1}+\frac{(x-x_{1})(x-x_{3})}{(x_{2}-x_{1})(x_{2}-x_{3})}y_{2}+\frac{(x-x_{1})(x-x_{2})}{(x_{3}-x_{1})(x_{3}-x_{2})}y_{3}$$

Yes, I don't understand how that expression comes.

 

[chiro]

Hey s0ft.

You might want to consider a linear algebra version of the problem and then derive the inverse matrix.

Remember that if you are solving for a polynomial with n points, you will have n linearly independent equations to solve.

 

[HallsofIvy]

Yes, I don't understand how that expression comes.

More generally, Lagrange's method for a n- 1 polynomial interpolating n given data points, $(x_i, y_i)$, requires calculating n terms
$$\frac{(x- x_1)(x- x_2)\cdot\cdot\cdot(x-x_{i-1})(x- x_{i+1}\cdot\cdot\cdot(x- x_{n-1})(x- x_n)}{x_i- x_1)(x_i- x_2)\cdot\cdot\cdot(x_i- x_{i- 1})(x_i- x_{i+1}\cdot\cdot\cdot(x_i- x_{n-1})(x- x_n)}y_i$$
with i from 1 to n, and adding them.

Look closely at that fraction. The numerator has the variable "x" minus each $x_j$ except the ith one. The denominator then has that $x_i$ minus each of the other $x_j$. For x equal to each $x_j$ except $x_i$ that fraction will be 0 because there will be a factor of 0 in the numerator. For $x= x_i$ that fraction will be 1 because each factor in the numerator has an identical factor in the denominator.

That means that at $x= x_i$ will will have $y_i$ times 1 and all other y values times 0.

In the three point example arildno gave,
$$\frac{(x- x_2)(x- x_3)}{(x_1- x_2)(x_1- x_3)}y_1+ \frac{(x- x_1)(x- x_3)}{(x_2- x_1)(x_2- x_3)}y_2+ \frac{(x- x_1)(x- x_2)}{(x_3- x_1)(x_3- x_2)}y_3$$
when $x= x_1$, the second and third fractions are 0 because of the $x_1- x_1$ in the numerator while the first fraction is
$$\frac{x_1- x_2)(x_1- x_3)}{(x_1- x_2)(x_1- x_3)}y_1= y_1$$
and similarly for $x= x_2$ and $x= x_3$.

 

[s0ft]

HallsOfIvy, probably you are thinking I know the general expression and presenting an explanation as to how what arildno posted came. Thank you for your effort but if I understood you correctly, it is the most general expression for the Lagrange's polynomial whose derivation I'm after.