0

I have $n+1$ data points $(x,y)$, and I want to create an interpolating polynomial as described here https://en.wikipedia.org/wiki/Polynomial_interpolation.

enter image description here

However there is a twist, I want to ensure $a_0$ is some real rational number. Basically what I am looking for is a way to interpolate and solve for $a_n, a_{n-1}, ..., a_1$ given that $a_0=k$ for some known value of k. For example k can be 0 or 1. For my purpose, the error or complexity does not matter.

Does anyone know if this is possible to do?

Thanks.

Daniel Doz
  • 87
omega
  • 751
  • 1
    Suppose you want a polynomial that passes through $(0,0)$ and $a_0=1$. – Asinomás Jan 17 '16 at 19:33
  • Does that mean that if it passes through (0,0), $a_0$ must be 0? – omega Jan 17 '16 at 19:34
  • That's just another point $(0,k)$ that your polynomial shall go through ... – Hagen von Eitzen Jan 17 '16 at 19:35
  • yes${}{}{}{}{}{}{}{}$ – Asinomás Jan 17 '16 at 19:37
  • But that increases the degree by $1$. – Bernard Jan 17 '16 at 19:39
  • Is there a way to do it without increasing the degree by 1? – omega Jan 17 '16 at 19:39
  • Actually k can be a real rational number. – omega Jan 17 '16 at 19:43
  • Wait, you want $a_0$ to be a particular given constant? That changes the problem: it means you have an overdetermined system of linear equations, which means you need to choose some error measure in order to select a "solution". For instance the error measure could be $\sum_{i=1}^n |p(x_i)-y_i|^2$, where $p$ is your approximant interpolant and $(x_i,y_i)$ are the interpolation nodes. Then the problem is of the least squares type. – Ian Jan 17 '16 at 19:45
  • So if you know the value of $a_0$ beforehand, so its a given constant, and its an overdetermined system of linear equations, does that mean regardless of the error, you can still make a polynomial that passes through all n+1 points? – omega Jan 17 '16 at 19:46
  • @HagenvonEitzen So if you are saying that it needs to go through $(0,k)$, then does that mean in general if I have n+1 points and create an interpolating polynomial of degree n, where 1 of those n+1 points is $(x_p, y_p)$ where $x_p=0$, then instead of all that, I could just interpolate the n points (without the point $(x_p, y_p)$), and then in this problem, just set $a_0=y_p$ which gives me the same polynomial but 1 degree less? – omega Jan 17 '16 at 19:53
  • @omega If $a_0$ is prespecified and you have $n+1$ points, then in general you need a polynomial of degree $n+1$ (not $n$) to pass through the $n+1$ points exactly. – Ian Jan 17 '16 at 19:59
  • But what if one of those n+1 points, have a x value that is 0? Then couldn't I remove that point, and use its y value as $a_0$, when interpolating the remaining n points to make a polynomial of degree n? – omega Jan 17 '16 at 20:01
  • 1
    @omega That's why I said "in general". It could so happen that you chose $a_0=k$ and $(0,k)$ is also one of the interpolation nodes. Then a polynomial of degree $n$ will do the job. – Ian Jan 17 '16 at 20:03

2 Answers2

2

Essentially, when you build an interpolation polynomial of degree $n$ using $n+1$ points $(x_i,y_i)$ with $x_i\ne x_j$ whenever $i\ne j$, you obtain a well-defined system of $n+1$ linear equations on $n+1$ unknowns (the coefficients of your interpolation polynomial).

When you impose an additional constraint $a_0=k$ (this will be your $n+2$nd equation), your system becomes overdetermined.

If this value $a_0=k$ agrees with the $n+1$ previous equations, everything is ok. If it does not, then the system does not have any solutions.

A viable approach would be to increase the degree of the polynomial. If $\forall i\, x_i\ne 0$, then you just add another interpolation point $(0,k)$ and now on $n+2$ points you can build an interpolation polynomial of degree $n+1$; as a consequence, for such a polynomial $a_0=k$.

However, if one of interpolation points is already of the form $(0,s)$, then in the case $s=k$, you can build your polynomial of degree $n$. In the case $s\ne k$, you can not build such a polynomial, whatever you do. You will need to resort to approximations, least square problem, etc.

TZakrevskiy
  • 22,980
1

In general you will not be able to find a polynomial of degree $n$ that interpolates $n+1$ points if you fix one of the coefficients beforehand.

The problem of finding an interpolating polynomial $p(x) = a_nx^n + \dotsb a_1x + a_0$ for $n+1$ points $(x_i, y_i)$ is in general solved by solving the linear system obtained from the equations

$$p(x_i) = a_nx_i^n + \dotsb a_1x_i + a_0 = y_i, \quad i = 1, \dotsc, n+1$$

for the values of the coefficients $a_j$.

If however you fix the value of $a_0$, the equations now become

$$p(x_i) = a_nx_i^n + \dotsb a_1x_i= y_i - a_0, $$

which gives the system

$$ \pmatrix{ x_1^n & x_1^{n-1} & \cdots & x_1 \\ \vdots & \ddots & \ddots & \vdots \\ x_{n+1}^n & x_{n+1}^{n-1} & \cdots & x_{n+1} } \pmatrix{a_n \\ \vdots \\ a_1} = \pmatrix{y_1 - a_0 \\ \vdots \\ y_{n+1} - a_0}.$$

This is an overdetermined system (i.e. one with more constraints than variables), hence has no exact solution in general. In this case one can obtain a least squares approximation to the interpolation using QR decomposition or something similar.

Josh
  • 2,539
  • the least square $\min_{x} ||Ax-b||^2$ is obtained by the pseudo inverse $x = (A^T A)^{-1}A^T b$ – reuns Jan 17 '16 at 21:03