Appendix

Lagrange interpolation formula

If you are given \(n\) points \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\) (with the \(x_i\) all distinct) and want to find the unique polynomial of degree \(n-1\) whose graph goes through those points, there is a formula for it, called the Lagrange interpolation formula.

The idea behind the Lagrange interpolation formula is quite interesting. We first find a polynomial \(p_1 (x)\) such that \(p_1 (x_1) = y_1\), but for which \(p_1(x_2) = p_1(x_3) = \dots = p_1(x_n) = 0\). That is, the graph of \(p_1(x)\) goes through \((x_1, y_1)\) but has \(x\)-intercepts at \(x_2, x_3, \dots, x_n\): we single out the first point and get \(p_1(x)\) to go through it. Then we find a polynomial \(p_2 (x)\) which goes through \((x_2, y_2)\) but has \(x\)-intercepts at all the other points \(x_1, x_3, x_4, \dots, x_n\). And then a \(p_3(x)\) which goes through \((x_3, y_3)\) and so on. The trick is that, once we have worked out all of these polynomials going through one point each, we can just add them up. That is, we can take \(f(x) = p_1 (x) + p_2 (x) + \dots + p_n (x)\) and then \(f(x_1) = y_1\), \(f(x_2) = y_2\), \(\dots\), \(f(x_n ) = y_n\) as desired.

Now, let's find \(p_1 (x)\). As in the previous examples, the \(x\)-intercepts at \(x_2, x_3, \dots, x_n\) tell us factors. We have

\[ p_1 (x) = c (x-x_2) (x-x_3) \dotsm (x-x_n), \]

where \(c\) is a constant. Since \(p_1 (x_1) = y_1\), we can work out \(c\):

\[ y_1 = c (x_1 - x_2) (x_1 - x_3) \dotsm (x_1 - x_n), \qquad \text{so} \quad c = \frac{y_1}{(x_1 - x_2) (x_1 - x_3) \dotsm (x_1 - x_n)}. \]

A formula for \(p_1(x)\) is then, using product notation,

\[ p_1(x) = \frac{y_1 (x-x_2) (x-x_3) \dotsm (x-x_n)}{(x_1 - x_2) (x_1 - x_3) \dotsm (x_1 - x_n)} = y_1 \prod_{j \neq 1} \frac{x-x_j}{x_1 - x_j}. \]

To get the other polynomials \(p_k(x)\) going through \((x_k, y_k)\), we can use exactly the same method and we end up with a similar formula

\[ p_k (x) = y_k \prod_{j \neq k} \frac{x - x_j}{x_k - x_j}, \]

and adding these up to obtain \(f(x)\) gives us the Lagrange interpolation formula

\[ f(x) = \sum_{k=1}^n y_k \prod_{j \neq k} \frac{x-x_j}{x_k-x_j}. \]

Next page - Appendix - Rational root test