Thread: Writing Matices... I know it looks daunting...

1. Writing Matices... I know it looks daunting...

...but any help is much appreciated!

Our aim is to find a polynomial of minimal degree passing through N
points Pi. All our constructions should depend on N.
The basic data is two matrices X:=matrix(1,N,[...]);
Y:=matrix(1,N,[...]), whose entries X[1,i] and Y[1,i] are the
coordinates of the point Pi, for 1 <= i <= N.
Assume that the the N points lie on the graph of the polynomial
T(X) = A1 + . . .ANX^(N−1). The coefficients Ai satisfy a system of
linear equations that can be written M.x = b where M and b depend
on the coordinates of the points Pi.

A. Write the matrix M as a function of the matrices X and Y .
B. Write the matrix b as a function of the matrices X and Y .

2. This is called Lagrange interpolation.

Let $p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$ be the polynomial which satisfies $p(x_i)=y_i$ for $0 \leq j \leq n$. Then you have

$a_nx_0^n+a_{n-1}x_0^{n-1}+...+a_0=y_0$

$a_nx_1^n+a_{n-1}x_1^{n-1}+...+a_0=y_1$

...

$a_nx_n^n+a_{n-1}x_n^{n-1}+...+a_0=y_n$

The values $x_0,...x_n$ are known, and this is a linear system of equations in the $n+1$ unknown parameters $a_n,...,a_0$. Solving for those will give you the polynomial you seek.

Note that the matrix of coefficients of the system is a Vandermonde matrix, whose inverse is known explicitly. I suspect that with a bit of cleverness, the inverse of the Vandermonde matrix may be retreived from Lagrange's form of the interpolating polynomial.