Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Lagrange Interpolation Formula"

m
m (typo)
 
(3 intermediate revisions by 2 users not shown)
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>
  
−
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.
 
  
 
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>
  
  
−
{{stub}}
+
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>
 +
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 ==
 +
 
 +
 
 +
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.

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Lagrange_Interpolation_Formula&oldid=204770"