Difference between revisions of "Lagrange Interpolation Formula"

Latest revision as of 02:50, 20 November 2023

Definition

The Lagrange Interpolation Formula states that For any distinct complex numbers $x_0, \ldots , x_n$ and any complex numbers $y_0, \ldots, y_n$ , there exists a unique polynomial $P(x)$ of degree less than or equal to $n$ such that for all integers $0 \le i \le n$ , $P(x_i) = y_i$ , and this polynomial is

$P(x) = \sum_{i=0}^{n}y_i \frac{(x-x_0) \cdots (x-x_{i-1}) (x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1}) (x_i - x_{i+1}) \cdots (x_i - x_n)}$ .

This formula is useful for many olympiad problems, especially since such a polynomial is unique.

Proof

Consider an $n$ th-degree polynomial of the given form

$f(x) = A_0(x – x_1)(x – x_2)(x – x_3)…(x – x_n) + A_1(x – x_0)(x – x_2)(x – x_3)…(x – x_n) + … + A_{n-1}(x – x_1)(x – x_2)(x – x_3)…(x – x_n)$ .

Substituting $x = x_0$ into the given equation yields us

$f(x_0) = y_0 = A_0(x_0 – x_1)(x_0 – x_2)(x_0 – x_3)…(x_0 – x_n)$ ,

Thus

$A_0 = \frac{y_0}{(x_0 – x_1)(x_0 – x_2)(x_0 – x_3)…(x_0 – x_n)}$ .

Again, substituting $x = x_1$ yields us

$f(x_1) = y_1 = A_1(x_1 – x_0)(x_1 – x_2)(x_1 – x_3)…(x_1 – x_n)$ ,

Thus

$A_1 = \frac{y_1}{(x_1 – x_0)(x_1 – x_2)(x_1 – x_3)…(x_1 – x_n)}$ .

Repeating this process, by substituting $A_0, A_1, ... A_n$ in $f(x)$ we get the Lagrange Interpolation Formula as:

$f(x) = \sum_{i=0}^{n}y_i \frac{(x-x_0) \cdots (x-x_{i-1}) (x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1}) (x_i - x_{i+1}) \cdots (x_i - x_n)}$ .

Trivia

While this formula may appear intimidating, it's actually not so difficult to see what is going on: for each term in the sum, we are finding a polynomial of degree $n$ that goes through the points $(x_i,y_i)$ and $(x_k,0)$ for $k\neq i$ . When we add them all together, we end up with a polynomial that interpolates the desired points.

@@ Line 52: / Line 52: @@
 <center>
 <math>
-P(x) = \sum_{i=0}^{n}y_i \frac{(x-x_0) \cdots (x-x_{i-1}) (x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1}) (x_i - x_{i+1}) \cdots (x_i - x_n)}
+f(x) = \sum_{i=0}^{n}y_i \frac{(x-x_0) \cdots (x-x_{i-1}) (x-x_{i+1}) \cdots (x-x_n)}{(x_i-x_0) \cdots (x_i-x_{i-1}) (x_i - x_{i+1}) \cdots (x_i - x_n)}
 </math>.
 </center>
 == Trivia ==

Page

Toolbox

Search

Difference between revisions of "Lagrange Interpolation Formula"

Latest revision as of 02:50, 20 November 2023

Definition

Proof

Trivia