Difference between revisions of "Lagrange Interpolation Formula"
m |
(Added proof) |
||
Line 1: | Line 1: | ||
− | For any distinct [[complex number]]s <math> x_0, \ldots , x_n </math> and any complex numbers <math> y_0, \ldots, y_n </math>, there exists a unique [[polynomial]] <math>P(x) </math> of [[degree of a polynomial | degree]] less than or equal to <math>n </math> such that for all [[integer]]s <math> 0 \le i \le n </math>, <math> P(x_i) = y_i </math>, and this polynomial is | + | == Definition == |
+ | |||
+ | The Lagrange Interpolation Formula states that For any distinct [[complex number]]s <math> x_0, \ldots , x_n </math> and any complex numbers <math> y_0, \ldots, y_n </math>, there exists a unique [[polynomial]] <math>P(x) </math> of [[degree of a polynomial | degree]] less than or equal to <math>n </math> such that for all [[integer]]s <math> 0 \le i \le n </math>, <math> P(x_i) = y_i </math>, and this polynomial is | ||
<center> | <center> | ||
<math> | <math> | ||
Line 6: | Line 8: | ||
</center> | </center> | ||
− | |||
This formula is useful for many olympiad problems, especially since such a polynomial is unique. | This formula is useful for many olympiad problems, especially since such a polynomial is unique. | ||
+ | == Proof == | ||
+ | |||
+ | Consider an <math>n</math>th-degree polynomial of the given form | ||
+ | <center> | ||
+ | <math> | ||
+ | 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) | ||
+ | </math>. | ||
+ | </center> | ||
+ | |||
+ | |||
+ | Substituting <math>x = x_0</math> into the given equation yields us | ||
+ | <center> | ||
+ | <math> | ||
+ | f(x_0) = y_0 = A_0(x_0 – x_1)(x_0 – x_2)(x_0 – x_3)…(x_0 – x_n) | ||
+ | </math>, | ||
+ | </center> | ||
+ | Thus | ||
+ | <center> | ||
+ | <math> | ||
+ | A_0 = \frac{y_0}{(x_0 – x_1)(x_0 – x_2)(x_0 – x_3)…(x_0 – x_n)} | ||
+ | </math>. | ||
+ | </center> | ||
+ | |||
+ | |||
+ | Again, substituting <math>x = x_1</math> yields us | ||
+ | <center> | ||
+ | <math> | ||
+ | f(x_1) = y_1 = A_1(x_1 – x_0)(x_1 – x_2)(x_1 – x_3)…(x_1 – x_n) | ||
+ | </math>, | ||
+ | </center> | ||
+ | Thus | ||
+ | <center> | ||
+ | <math> | ||
+ | A_1 = \frac{y_1}{(x_1 – x_0)(x_1 – x_2)(x_1 – x_3)…(x_1 – x_n)} | ||
+ | </math>. | ||
+ | </center> | ||
+ | |||
+ | |||
+ | Repeating this process, by substituting <math>A_0, A_1, ... A_n</math> in <math>f(x)</math> we get the Lagrange Interpolation Formula as: | ||
+ | <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)} | ||
+ | </math>. | ||
+ | </center> | ||
− | + | ||
+ | == 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 <math>n</math> that goes through the points <math>(x_i,y_i)</math> and <math>(x_k,0)</math> for <math>k\neq i</math>. When we add them all together, we end up with a polynomial that interpolates the desired points. |
Revision as of 03:49, 20 November 2023
Definition
The Lagrange Interpolation Formula states that For any distinct complex numbers and any complex numbers
, there exists a unique polynomial
of degree less than or equal to
such that for all integers
,
, and this polynomial is
.
This formula is useful for many olympiad problems, especially since such a polynomial is unique.
Proof
Consider an th-degree polynomial of the given form
.
Substituting into the given equation yields us
,
Thus
.
Again, substituting yields us
,
Thus
.
Repeating this process, by substituting in
we get the Lagrange Interpolation Formula as:
.
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 that goes through the points
and
for
. When we add them all together, we end up with a polynomial that interpolates the desired points.