Editing Polynomial interpolation (section)

==Interpolation error: Lagrange remainder formula==
{{confusing section|date=June 2011}}

When interpolating a given function ''f'' by a polynomial <math>p_n</math> of degree {{mvar|n}} at the nodes ''x''<sub>0</sub>,..., ''x''<sub>''n''</sub> we get the error
<math display="block">f(x) - p_n(x) = f[x_0,\ldots,x_n,x] \prod_{i=0}^n (x-x_i) </math>
where <math display="inline">f[x_0,\ldots,x_n,x]</math> is the (''n''+1)<sup>st</sup> [[divided differences|divided difference]] of the data points <blockquote><math>(x_0,f(x_0)),\ldots,(x_n,f(x_n)),(x,f(x)) </math>.</blockquote>Furthermore, there is a ''Lagrange remainder form'' of the error, for a function ''f'' which is {{math|''n'' + 1}} times continuously differentiable on a closed interval <math>I</math>, and a polynomial <math>p_n(x)</math> of degree at most {{mvar|n}} that interpolates ''f'' at {{math|''n'' + 1}} distinct points <math>x_0,\ldots,x_n\in I</math>. For each <math>x\in I</math> there exists <math>\xi\in I</math> such that
<math display="block"> f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i). </math>

This error bound suggests choosing the interpolation points {{math|''x<sub>i</sub>''}} to minimize the product <math display="inline">\left | \prod (x - x_i) \right |</math>, which is achieved by the [[Chebyshev nodes]].

=== Proof of Lagrange remainder ===
Set the error term as <math display="inline"> R_n(x) = f(x) - p_n(x) </math>, and define an auxiliary function:<math display="block"> Y(t) = R_n(t) - \frac{R_n(x)}{W(x)} W(t) \qquad\text{where}\qquad 
W(t) = \prod_{i=0}^n (t-x_i). </math>Thus:<math display="block"> Y^{(n+1)}(t) = R_n^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)! </math>

But since <math>p_n(x)</math> is a polynomial of degree at most {{mvar|n}}, we have <math display="inline"> R_n^{(n+1)}(t) = f^{(n+1)}(t) </math>, and: 
<math display="block"> Y^{(n+1)}(t) = f^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)! </math>

Now, since {{math|''x<sub>i</sub>''}} are roots of <math>R_n(t)</math> and <math>W(t)</math>, we have <math> Y(x)=Y(x_j)=0 </math>, which means {{mvar|Y}} has at least {{math|''n'' + 2}} roots. From [[Rolle's theorem]], <math>Y^\prime(t)</math> has at least {{math|''n'' + 1}} roots, and iteratively <math>Y^{(n+1)}(t)</math> has at least one root {{mvar|ξ}} in the interval {{mvar|I}}. Thus:
<math display="block"> Y^{(n+1)}(\xi) = f^{(n+1)}(\xi) - \frac{R_n(x)}{W(x)} \ (n+1)! = 0 </math>

and:
<math display="block"> R_n(x) = f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) .</math>

This parallels the reasoning behind the Lagrange remainder term in the [[Taylor's theorem|Taylor theorem]]; in fact, the Taylor remainder is a special case of interpolation error when all interpolation nodes {{math|''x<sub>i</sub>''}} are identical.<ref>{{cite web| url=http://www.math.okstate.edu/~binegar/4513-F98/4513-l16.pdf| title=Errors in Polynomial Interpolation}}</ref> Note that the error will be zero when <math>x = x_i</math> for any ''i''. Thus, the maximum error will occur at some point in the interval between two successive nodes.

===Equally spaced intervals===
In the case of equally spaced interpolation nodes where <math>x_i = a + ih</math>, for <math>i=0,1,\ldots,n,</math> and where <math>h = (b-a)/n,</math> the product term in the interpolation error formula can be bound as<ref>{{cite web| url=https://www-users.cselabs.umn.edu/Spring-2021/csci5302/Notes/Classnotes/interp.pdf| title=Notes on Polynomial Interpolation}}</ref>
<math display="block">\left|\prod_{i=0}^n (x-x_i)\right| = \prod_{i=0}^n \left|x-x_i\right| \leq \frac{n!}{4} h^{n+1}.</math>

Thus the error bound can be given as
<math display="block"> \left|R_n(x)\right| \leq \frac{h^{n+1}}{4(n+1)} \max_{\xi\in[a,b]} \left|f^{(n+1)}(\xi)\right| </math>

However, this assumes that <math>f^{(n+1)}(\xi)</math> is dominated by <math>h^{n+1}</math>, i.e. <math>f^{(n+1)}(\xi) h^{n+1} \ll 1</math>. In several cases, this is not true and the error actually increases as {{math|''n'' → ∞}} (see [[Runge's phenomenon]]). That question is treated in the section [[#Convergence properties|''Convergence properties'']].