polynomial interpolation
1 theorem:
Given a set of \(n+1\) points \(\{(x_0,y_0),...,(x_n,y_n)\}\), there is a unique polynomial of degree at most \(n\) that passes through all points.
This polynomial is: \[ f(x) = \sum_{i} y_{i} \prod_{j\neq i} \frac{x - x_j}{x_i - x_j} \]
1.1 quick check: does this actually pass through all points?
Check that it actually passes through \(x_a\): look at each one of the terms in the sum. If \(i=a\), then \(\prod_{j\neq i} \frac{x - x_j}{x_i - x_j} = \prod_{j\neq a} \frac{x_a - x_j}{x_a - x_j} = 1\). So \(y_a\) gets multiplied by a 1. If \(i = b\neq a\), then \(\prod_{j\neq i}\frac{x-x_j}{x_i - x_j} = \prod_{j\neq b}\frac{x_b - x_j}{x_b - x_j}\). Take a closer look at the terms of this product. In particular, for \(j=a\), we have \(\frac{x_a - x_a}{x_b - x_j} = 0\). So, \(y_b\) gets multiplied by a 0. So, \(f(x_a) = y_a\).
1.2 uniqueness
Assume that there is some other polynomial \(q\) of degree at most \(n\) that passes through all \(n+1\) points. Then \(f\) and \(q\) match at all these points and \(p-f\) is a polynomial with \(n+1\) zeros. But \(p-f\) has degree at most \(n\).