# Formula for coefficients of interpolation polynomial

(Question) What is the (conventional) formula for coefficients of interpolation polynomial?

Consider the interpolation problem: find the polynomial through a given set of points $$(x_0,y_0),...,(x_n,y_n)$$. Suppose we want the polynomial in canonical form (monomial basis): coefficients times powers of $$x$$.

Is there a standard solution to this problem? What would be the formula for the coefficients and how is it obtained?

Note: I found my own solutions for this problem, but I would like to know the ‘standard’ solution. Maybe it involves some Linear Algebra that I am not aware of yet.

## 1 Answer

Here is a general way to obtain it. Your unique polynomial will have to be of degree at most $$n$$, so assume we have $$p(x) = a_0 + a_1x + +\ldots + a_nx^n = \sum_{k=1}^n a_k x^k.$$

Then, plugging in your points, you get the equations $$y_i = \sum_{k=1}^n a_k x_i^k, \quad \forall i \in [n].$$ This is a linear system of $$n+1$$ equations in $$n+1$$ unknowns, guaranteed to be invertible due to the nature of the system. Hence, there is a unique solution, which you can find by Gaussian Elimination, for example.

UPDATE - EXAMPLE

Perhaps an example will help. Consider finding the unique linear polynomial through the points $$(0,0)$$ and $$(1,1)$$. We assume the form $$p(x) = a_0 + a_1x$$ which leads to the equations $$\begin{split} 0 = a_0 + a_1 \cdot 0\\ 1 = a_0 + a_1 \cdot 1 \end{split}$$ and the first equation simplifies to $$a_0=0$$, plugging into the second yields $$a_1=1$$, so we have $$p(x) = 0 + 1 \cdot x = x,$$ which is, of course, the unique line through $$(0,0)$$ and $$(1,1)$$, as expected.

• How would you define $a_k$ specifically? – Max Feb 11 at 16:26
• @Max you are not defining $a_k$, they are variables for which you are solving – gt6989b Feb 11 at 16:29
• Indeed, instead of define, I meant how do you get $a_k$ directly (so a formula for $a_k$). – Max Feb 11 at 16:32
• @Max see update for an example. One can use something like Cramer's Rule if you insist on calculating coefficients directly via a formula instead of a general algorithmic procedure. – gt6989b Feb 11 at 16:34
• I would like the formula for $a_k$ in closed form. As used in the link. – Max Feb 11 at 16:38