2
$\begingroup$

I have 4 points: $(x_i,y_i),\quad i=1,2,3,4$
and $x_i=x_1+i-1,\quad i=2,3,4$
(so these x-coordinates are evenly spaced)

I want to find a polynomial interpolation of these points, having the following form: $$y=a_4(x-b)^4+a_2(x-b)^2+c$$

I don't know how to solve the parameters. Could you please give me a help?

Edit

Sorry for the incorrect usage of "coefficient".
I need to solve 4 unknown parameters, especially $b$ and $c$.

$\endgroup$
2
$\begingroup$

For simplicity, I'll adjust your indices down by one. Also, I'll define $z_i := x_i-b$. Finally, I'll write $a_0$ for $c$, for the sake of consistency. Then we have four equations in four unknowns $a_0$, $a_2$, $a_4$, and (the hidden) $b$: $$y_i = a_4z_i^4+a_2z_i^2+a_0 \qquad i=0,1,2,3 \tag{1}$$

Viewing the first three equations (for $i=0,1,2$) as a linear system in the $a_i$, we can solve to get

$$\begin{align} a_0 &= -\frac{ y_0 z_1^2 z_2^2 (z_1^2 - z_2^2) + y_1 z_2^2 z_0^2 (z_2^2 - z_0^2) + y_2 z_0^2 z_1^2 (z_0^2 - z_1^2)}{ (z_0^2 - z_1^2) (z_1^2 - z_2^2) (z_2^2 - z_0^2)} \tag{2}\\[6pt] a_2 &= \phantom{-}\frac{ y_0 (z_1^4 - z_2^4) + y_1 (z_2^4 - z_0^4) + y_2 (z_0^4 - z_1^4)}{ (z_0^2 - z_1^2) (z_1^2 - z_2^2) (z_2^2 - z_0^2)} \tag{3}\\[6pt] a_4 &= -\frac{ y_0 (z_1^2 - z_2^2) + y_1 (z_2^2 - z_0^2) + y_2 (z_0^2 - z_1^2)}{ (z_0^2 - z_1^2) (z_1^2 - z_2^2) (z_2^2 - z_0^2)} \tag{4} \end{align}$$ (Note that the denominators put restrictions on allowable values of some parameters.) Substituting these into the $i=3$ equation, we find after dust settles: $$\begin{align} 0 &=y_0 (z_1^2 - z_2^2) (z_2^2 - z_3^2) (z_3^2 - z_1^2) \tag{5}\\ &-y_1 (z_2^2 - z_3^2) (z_3^2 - z_0^2) (z_0^2 - z_2^2) \\ &+y_2 (z_3^2 - z_0^2) (z_0^2 - z_1^2) (z_1^2 - z_3^2) \\ &-y_3 (z_0^2 - z_1^2) (z_1^2 - z_2^2) (z_2^2 - z_0^2) \end{align}$$

Now, upon substituting back $z_i \to x_i-b$, we see that $$z_i^2 - z_j^2 = (z_i-z_j)(z_i+z_j) = (x_i-x_j)(x_i+x_j-2b) \tag{6}$$ so that, for general $x_i$, each term of $(5)$ has three factors involving $b$ and therefore contributes some multiple of $b^3$ to the overall sum. This makes solving for $b$ possible via the Cubic Formula, but the algebra is messy.

Luckily, for equally-spaced $x_i$ (that is, for $x_i = x_0 + i d$ for some $d$), each term of $(5)$ has a factor of $2x_0+3d-2b$, from the $z_i^2-z_j^2$ factor with $i+j=3$; since the denominators of the $a_i$ also have such a factor, we may assume the value is non-zero. This allows us to divide-through by that factor, as well as $d$s that accumulate from $x_i-x_j$ factors, turning $(5)$ into the following quadratic: $$ \begin{align} 0 &=2 b^2\;(y_0 - 3 y_1 + 3 y_2 - y_3) \\[4pt] &-\phantom{2}b\phantom{^2}\left(\begin{array}{l} \phantom{+3}y_0(4x_0+9 d) - 3y_1(4x_0+7 d) \\[4pt] +3y_2( 4x_0+5 d) - \phantom{3}y_3(4x_0+3 d) \end{array}\;\right) \\[4pt] &+\phantom{3}y_0 (x_0 + 2 d) (2 x_0 + 5 d) - 3 y_1 (2 x_0 + 5 d) (\phantom{2}x_0 + d) \\[4pt] &+ 3 y_2 (x_0 + 2 d) (2 x_0 + \phantom{5}d) - \phantom{3}y_3 (\phantom{2}x_0 + \phantom{9}d) (2 x_0 + d) \end{align} \tag{7}$$

Taking $x_0=0$, this simplifies to $$\begin{align} 0 = 2 b^2&\;(\phantom{10}y_0 - \phantom{1}3 y_1 + 3 y_2 - y_3) \\ -3bd &\;(\phantom{1}3y_0 - \phantom{1}7 y_1+5y_2 - y_3) \\ +d^2&\;(10y_0 - 15 y_1 + 6 y_2 - y_3) \end{align}\tag{8}$$

This quadratic in $b$ is readily solved. Substituting the resulting value(s) into the formulas for the $a_i$ is left as an exercise to the reader.


Example. If we have points $(0,3)$, $(1,1)$, $(2,4)$, $(3,1)$ (so that $d=1$), we find $$(b,a_0,a_2,a_4) = \left(2,4,-\frac{47}{12},\frac{11}{12}\right) \quad\text{or}\quad \left(\frac{19}{22}, \frac{101789}{108416}, \frac{1109}{336}, -\frac{121}{168}\right) \tag{9}$$ The corresponding polynomials have the following graphs:

enter image description here

$\endgroup$
4
  • 1
    $\begingroup$ Thank you. The last step is so amazing. A perfect quadratic equation, no $b^4$, no fractions. I'll try to derive it by myself. $\endgroup$ – kevinjwz Dec 5 '19 at 10:04
  • 1
    $\begingroup$ With $z_i$, it's much clearer now. Great! $\endgroup$ – kevinjwz Dec 7 '19 at 18:55
  • $\begingroup$ The expression for $a_2$ seems a little wrong. There should be no minus sign before $y_1$. $\endgroup$ – kevinjwz Dec 13 '19 at 9:00
  • $\begingroup$ @kevinjwz: Fixed! Thanks. $\endgroup$ – Blue Dec 13 '19 at 9:45
1
$\begingroup$

For each $x_i$ you have an independent equation, getting to solve $$ \begin{bmatrix} (x_1 - b)^4 & (x_1-b)^2 & 1 \\ (x_2 - b)^4 & (x_2-b)^2 & 1 \\ (x_3 - b)^4 & (x_3-b)^2 & 1 \\ (x_4 - b)^4 & (x_4-b)^2 & 1 \end{bmatrix} \begin{bmatrix}a_4 \\ a_2 \\ c \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{bmatrix} $$ which is a basic Gaussian Elimination exercise once the elements of the matrix on the LHS are computed.

UPDATE

If $b$ is also unknown, and you can do this in code or in Excel, I would do the following. Using the above equation, define the error function $$ f(b) = \|b - Ax\|_2^2 = \sum_{k=1}^4 \left( y_k - a_4(x_k-b)^4 - a_2(x_k-b)^2-c\right)^2 $$ where the $a_4,a_2,c$ are (numerically) calculated by Gaussian Elimination for any fixed value of $b \in \mathbb{R}$. Now minimize $f(b)$ and you are done.

In other words, for each iteration of the minimizer, given a fixed value of $b$,

  1. Solve for $a_4,a_2,c$ using Gaussian Elimination
  2. Compute the error $f(b)$
$\endgroup$
7
  • $\begingroup$ You can use three of the equations (say, for $i=1, 2, 3$) to solve for $a_4$, $a_2$, $c$ in terms of the $x_i$, $y_i$, and $b$. Then use these in the fourth equation ($i=4$) to get an equation for $b$; namely, a quartic with two linear factors and a quadratic. $\endgroup$ – Blue Dec 4 '19 at 5:56
  • $\begingroup$ @gt6989b $b$ is an unknown parameter, so I can't just solve it like a ordinary linear equations. $\endgroup$ – kevinjwz Dec 4 '19 at 14:45
  • $\begingroup$ @Blue Thank you. I tried to calculate the inverse of the first 3 rows of the matrix, using WolframAlpha, and I replaced $x_i$ with $x_1+i-1$. Here is the result: link $\endgroup$ – kevinjwz Dec 4 '19 at 15:02
  • $\begingroup$ @Blue Am I really able to solve for $b$? $\endgroup$ – kevinjwz Dec 4 '19 at 15:06
  • $\begingroup$ @kevinjwz please see the update $\endgroup$ – gt6989b Dec 4 '19 at 15:34

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.