3

I want to find a (preferably polynomial) function that passes through the following twelve points:

  • $(1, 0)$
  • $(2, 3)$
  • $(3, 3)$
  • $(4, 6)$
  • $(5, 1)$
  • $(6, 4)$
  • $(7, 6)$
  • $(8, 2)$
  • $(9, 5)$
  • $(10, 0)$
  • $(11, 3)$
  • $(12, 5)$

The values outside these points do not matter. Obviously, there are infinitely many functions that pass through all these points.

Given any one point and the two zeroes, I can calculate a quadratic function to pass through them. For example, the function that passes through $(0, 1)$, $(0, 10)$, and $(6, 4)$ is found with

$$ \begin{align} c(6 - 1)(6 - 10) &= 4\\ (5)(-4)c &= 4\\ c &= -\frac{1}{5}\\ f(x) &= -\frac{1}{5}(x - 1)(x - 10) \end{align} $$

But I have no idea how to calculate this for the multiple points I need.

Selme
  • 33

3 Answers3

6

There are lots of ways to collocate points through those points. Lagrange is one of them. I have calculated it for you in case you require the answer. Here it is in Horner form for quick computation.

$$y=-519+x \left(\frac{4798141}{3960}+x \left(-\frac{50014963}{50400}+x \left(\frac{34689413}{113400}+x \left(\frac{3930023}{120960} \right.\right.\right.\right.$$ $$+ \left.\left.\left.\left. x\left(-\frac{19645147}{362880}+x \left(\frac{1065259}{57600}+x\left(-\frac{586327}{172800} +x \left(\frac{3781}{10080}+x\left(-\frac{2269}{90720} \right.\right.\right.\right.\right.\right.\right.\right.\right.$$ $$\left. \left. \left. \left. \left. \left. \left. \left. \left. +x \left(\frac{1123}{1209600}-x\frac{589 }{39916800}\right) \right)\right)\right)\right)\right)\right)\right)\right)\right)$$

enter image description here

Henry
  • 157,058
bobbym
  • 2,546
  • What tool did you use to put under Horner form ? I guess you did not do it by hand ! ;) – jibe Jun 30 '14 at 10:14
  • @jibe although it is possible to do it by hand it is much more accurate to let a program do it. I used Mathematica but I suppose Wolfram Alpha could do it just as well. – bobbym Jun 30 '14 at 10:16
  • I didn't know Mathematica already had HornerForm and InterpolatingPolynomial : great ! – jibe Jun 30 '14 at 10:20
  • A difference table could have done it too. – bobbym Jun 30 '14 at 10:32
5

There is a unique polynomial of degree at most $11$ which passes through these $12$ points. If you denote your points by $(x_1,y_1),\ldots,(x_{12},y_{12})$, this polynomial is $$\sum_{k=1}^{12}y_k\frac{P_k}{Q_k}\ ,$$ where

  • $P_k$ is the product of the factors $x-x_j$, where $j$ takes all values from $1$ to $12$ except k;
  • $Q_k$ is the product of the numbers $x_k-x_j$, where $j$ takes all values from $1$ to $12$ except k.

If you are lucky, this will actually turn out to have a fairly small degree. If you are not lucky, it won't ;-)

David
  • 82,662
4

Use Lagrange interpolation: Idea is as follows: Suppose you want your function to pass through the following distinct points: $(a,A), (b,B)$ and $(c,C)$ (note: $a \neq b \neq c$) then we first construct the polynomials $$L_1(x)=\frac{(x-b)(x-c)}{(a-b)(a-c)}$$ Observe that $L_1(c)=L_1(b)=0$ and $L_1(a)=1$. Likewise construct $L_2(x)$ and $L_3(x)$. Once you have this then define $$f(x)=AL_1(x)+BL_2(x)+CL_3(x).$$

Anurag A
  • 41,067
  • Not quite right. It does guarantee to give the lowest degree polynomial. It does not guarantee to give a polynomial of degree $N-1$ (the degree will be at most $N-1$ but could be lower). – Gina Jun 30 '14 at 04:54
  • you are right my mistake. I have edited it. – Anurag A Jun 30 '14 at 05:01