0
$\begingroup$

(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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How would you define $a_k$ specifically? $\endgroup$ – Max Feb 11 at 16:26
  • $\begingroup$ @Max you are not defining $a_k$, they are variables for which you are solving $\endgroup$ – gt6989b Feb 11 at 16:29
  • $\begingroup$ Indeed, instead of define, I meant how do you get $a_k$ directly (so a formula for $a_k$). $\endgroup$ – Max Feb 11 at 16:32
  • $\begingroup$ @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. $\endgroup$ – gt6989b Feb 11 at 16:34
  • $\begingroup$ I would like the formula for $a_k$ in closed form. As used in the link. $\endgroup$ – Max Feb 11 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.