Error term in equally spaced nodes

Question

Given a function $f(x)$ and a sequence of $n+1$ distinct nods, let $p_n(x)$ to be a polynomial interpolant of degree at most $n$, if we've been given equally spaced nodes then show that the error term is as follows: $$\prod_{i=0}^{n}\left|x-x_{i}\right|\le\frac{h^{\left(n+1\right)}n!}{4}$$ where $x_{i}=a+ih=a+i\left(\frac{b-a}{2}\right)$ and $0\le i\le n$. I tried to use this page to follow the steps , but still I'm not able to get what I want since I really hard tried for this object so knowing the proof is so valuable for me and any help is greatly appreciated.

Answer 1

Although Dr. Lutz Lehmann's answer was adequate, I have been pinged in the companion question and a bounty has been offered so I provide a proof similar to my answer there.

For $a<b$, $n\in\mathbb{Z}^+$, let $h=(b-a)/n$ and $x_i=a+ih$. We want a bound on $\prod_{i=0}^n\left|x-x_i\right|$. The first part will show that this product takes on its maximum for some $a\le x\le a+h/2$.
For $x\in[a,b]$ divide $x-a$ by $h$ for quotient and remainder to get $x-a=hi+r$ with $i\in\mathbb{Z}^+$, $0\le i\le n$, and $0\le r<h$. Three cases:

Case $1$: $i=n$, so $r=0$ and $x=b=x_n$ and $$\prod_{j=0}^n\left|x-x_j\right|=0$$ satisfies any valid error bound.

Case $2$: $0\le i\le n-1$, $0\le r\le h/2$. Then $$\begin{align}x&=a+hi+r\le a+hi+h/2\\ &\le a+h(n-1)+h/2=a+hn-h/2\end{align}$$ Taking the sum of these two inequalities we get $2x\le2a+h(n+i)$ which expands to $x-a-hn+hk\le hk+hi+a-x$ for any $k\in\mathbb{Z}^+$. Then $$\begin{align}\prod_{j=0}^n\left|x-x_j\right|&=-\prod_{j=0}^{i-1}\left(x-a-hj\right)\prod_{j=i}^n\left(a+hj-x\right)\\ &=-\prod_{k=n-i+1}^n\left(x-a-hn+hk\right)\prod_{k=0}^{n-i}\left(a+hk+hi-x\right)\\ &\le-\prod_{k=n-i+1}^n\left(hk+hi+a-x\right)\prod_{k=0}^{n-i}\left(a+hk+hi-x\right)\\ &=-\prod_{k=0}^n\left(hk-h\xi\right)=h^{n+1}\xi\prod_{k=1}^n\left(k-\xi\right)\end{align}$$ In the above we set $j=n-k$ in the first product and $j=k+i$ in the second and used the fact that every factor except the first factor in the second product is positive and let $h\xi=x-a-hi$ so that $0\le\xi\le1/2$.

Case $3$: $0\le i\le n-1$, $h/2<r<h$. Then $$\begin{align}x&=a+hi+r>a+hi+h/2\\ &\ge a+h/2\end{align}$$ Taking the sum of these two inequalities we get $2x>2a+hi+h$ which expands to $a+hk-x<x-a-hi-h+hk$ for any $k\in\mathbb{Z}^+$. Then $$\begin{align}\prod_{j=0}^n\left|x-x_j\right|&=-\prod_{j=0}^{i+1}\left(x-a-hj\right)\prod_{j=i+2}^n\left(a+hj-x\right)\\ &=-\prod_{k=0}^{i+1}\left(x-a-hi-h+hk\right)\prod_{k=i+2}^n\left(a+hk-x\right)\\ &<-\prod_{k=0}^{i+1}\left(x-a-hi-h+hk\right)\prod_{k=i+2}^n\left(x-a-hi-h+hk\right)\\ &=-\prod_{k=0}^n\left(hk-h\xi\right)=h^{n+1}\xi\prod_{k=1}^n\left(k-\xi\right)\end{align}$$ This time we set $j=i+1-k$ in the first product and $j=k$ in the second while this time every factor except the last factor in the first product was positive and let $h\xi=a+hi+h-x$ so that again $0<\xi<1/2$.

In all three cases we have established that $$\prod_{j=0}^n\left|x-x_j\right|\le h^{n+1}\xi\prod_{k=1}^n\left(k-\xi\right)=h^{n+1}y(\xi)$$ for some $0\le\xi\le1/2$. separating the first factor out of the product, we want to minimize $$g(\xi)=\xi\left(1-\xi\right)$$ Taking derivatives, we set $1-2\xi=0$ so $\xi=1/2$ is the critical point and $g(1/2)=1/4$. Since $0<k-\xi\le k$ for $0\le\xi\le1/2$, we have $$\prod_{j=0}^n\left|x-x_j\right|\le h^{n+1}(1/4)\prod_{k=2}^nk=\frac{h^{n+1}n!}4$$ The equality is only nonstrict for $n=1$. Otherwise, taking the logarithm of the whole expression, $$\ln\left[\prod_{j=0}^n\left|x-x_j\right|\right]\le\ln\left(h^{n+1}y(\xi)\right)=(n+1)\ln h+\ln\xi+\sum_{k=1}^n\ln\left(k-\xi\right)$$ So we take derivatives to find the critical point: $$g(\xi)=\frac d{d\xi}\ln y(\xi)=\frac1{\xi}-\sum_{k=1}^n\frac1{k-\xi}=0$$ If $n$ is large and $\xi$ is small, then $$\frac1{\xi_0}\approx\sum_{k=1}^n\frac1k\approx\ln n+\gamma$$ where we have used the definition of the Euler-Mascheroni constant $$\gamma=\lim_{n\rightarrow\infty}\left(\sum_{i=1}^n\frac1i-\ln n\right)$$ and $\xi_0$ is the first-order approximation to $\xi_{max}$ and then $$\begin{align}\ln y\left(\xi_0\right)&=\ln\xi_0+\sum_{k=1}^n\ln\left(k-\xi_0\right)\approx\ln\xi_0+\sum_{k=1}^n\ln k-\xi_0\sum_{k=1}^n\frac1k\\ &\approx-\ln\left(\ln n+\gamma\right)+\ln\left(n!\right)-1\end{align}$$ So $$y\left(\xi_{max}\right)\approx\frac{n!}e\xi_0$$ EDIT: We can improve the approximation via a round of Newton's method: $$g\left(\xi_0\right)=\frac1{\xi_0}-\sum_{k=1}^n\frac1{k-\xi_0}=\frac1{\xi_0}-\sum_{k=1}^n\frac1k-\xi_0\sum_{k=1}^n\frac1{k^2}+O\left(\xi_0^2\right)=-\frac{\pi^2}6\xi_0+O\left(\xi_0^2\right)$$ And $$g^{\prime}\left(\xi_0\right)=-\frac1{\xi_0^2}-\sum_{k=1}^n\frac1{\left(k-\xi_0\right)^2}=-\frac1{\xi_0^2}+O(1)$$ So $$\xi_1=\xi_0-\frac{g\left(\xi_0\right)}{g^{\prime}\left(\xi_0\right)}=\xi_0-\frac{\pi^2}6\xi_0^3$$ And then $$\begin{align}\ln y\left(\xi_1\right)&=\ln\left(\xi_0-\frac{\pi^2}6\xi_0^3\right)+\sum_{k=1}^n\ln\left(k-\xi_0+\frac{\pi^2}6\xi_0^3\right)\\ &=\ln\xi_0-\frac{\pi^2}6\xi_0^2+\sum_{k=1}^n\ln k-\left(\xi_0-\frac{\pi^2}6\xi_0^3\right)\sum_{k=1}^n\frac1k-\frac{\xi_0^2}2\sum_{k=1}^2\frac1{k^2}+O\left(\xi_0^3\right)\\ &=\ln\xi_0-\frac{\pi^2}6\xi_0^2+\ln\left(n!\right)-\left(\xi_0-\frac{\pi^2}6\xi_0^3\right)\left(\frac1{\xi_0}\right)-\frac{\xi_0^2}2\left(\frac{\pi^2}6\right)+O\left(\xi_0^3\right)\\ &=\ln\xi_0+\ln\left(n!\right)-1-\frac{\pi^2}{12}\xi_0^2+O\left(\xi_0^3\right)\end{align}$$ So now we have $$y\left(\xi_{max}\right)\approx\frac{n!}e\xi_0\left(1-\frac{\pi^2}{12}\xi_0^2\right)$$ I have made plots of the optimal $\xi_{max}$ and $y\left(\xi_{max}\right)/n!$ along with the above approximations:

% Runge2.m

clear all;
close all;
nmax = 50; % Maximum degree to be considered
P = [1 0]; % prod([0:n]-x)
Q = [1 0]; % Coefficients of derivative
F = 1; % n factorial
x_exact = []; % Exact location of maximum
M_n = []; % Exact value of maximum
eulergamma = 0.577215664901533; % Euler-Mascheroni constant
for n = 1:nmax,
    % Compute new product, coefficients, and factorial
    P = conv(P,[1 -n]);
    Q = [n+1 Q];
    F = n*F;
    R = P.*Q; % x*P'(x)
    % Get location...
    x = min(roots(R(1:end-1)));
    x_exact(n) = x;
    % ... and value of max
    M = polyval(P,x);
    M_n(n) = M/F;
    x0 = 1/(log(n)+eulergamma); % Initial approximation of location
    % Print out second approximation of x and P(x)/n!
    fprintf('x ~ %.10f, M/n! ~ %.10f ',x0-pi^2/6*x0^3, ...
        x0/exp(1)*(1-pi^2/12*x0^2))
    % Print out exact values
    fprintf('n = %d, x = %.10f, M = %e, M/n! = %.10f\n',n,x,M,M/F);
end
npts = 4*nmax+1; % Number of points of approximation curves
m = linspace(1,nmax,npts); % x-values of approximation curves
x0 = 1./(log(m)+eulergamma); % First-order approimation
figure;
% Plot exact, first- and third-order approximations to max locations
plot([1:nmax],x_exact,'k.',m,x0,'b-',m,x0-pi^2/6*x0.^3,'r-');
axis([0,nmax,0,0.5]);
title('Location of Maximum');
xlabel('n');
ylabel('x(n)');
legend('Exact','First-order','Third-order')
figure;
% Plot exact, first- and third-order approximations to max values
plot([1:nmax],abs(M_n),'k.',m,x0/exp(1),'b-', ...
    m,x0/exp(1).*(1-pi^2/12*x0.^2),'r-');
axis([0,nmax,0,0.3]);
title('Value of maximum');
xlabel('n');
ylabel('M(n)/n!');
legend('Exact','First-order','Third-order')

So we can see that $$\prod_{i=0}^n\left|x-x_i\right|\le\frac{h^{n+1}n!}{e\left(\ln n+\gamma\right)}$$ Or even $$\prod_{i=0}^n\left|x-x_i\right|\le\frac{h^{n+1}n!}{e\left(\ln n+\gamma\right)}\left(1-\frac{\pi^2}{12\left(\ln n+\gamma\right)^2}\right)$$ Is a better estimate, although we haven't actually proved that it is always an upper bound for sufficiently large $n$.

Answer 2

If $i$ is determined so that $x\in[x_i,x_{i+1}]$, $x=x_i+sh$, $s\in[0,1]$, split the product into

• terms for index $j=0,...,i-1$ where $|x-x_j|<(i-j+1)h$, then
• the middle terms $|(x-x_i)(x-x_{i+1})|=h^2|s(1-s)|\le \frac14h^2$ , and then
• terms for indices $j=i+2,...,n$ where $|x-x_j|\le(j-i)h$.

Multiplying this all together and then considering the worst case gives your bound. More precisely, you get upper and lower bounds \begin{multline} h^{n+1}i!(n-i-1)!\cdot s(1-s)\le h^{n+1}(i+s)...(1+s)s(1-s)(2-s)...(n-i-s) \\ =\prod_{j=0}^n|x-x_j|\le h^{n+1}(i+1)!(n-i)!\cdot s(1-s) \end{multline} The factorial product is largest when $i=0$ or $i=n-1$, so that the maximum upper bound by this method is indeed $\frac14h^{n+1}n!$

---

You can do better if you consider the index $i$ with $|x-x_i|\le\frac h2$. Then with $x=x_i+sh$ you can separate out the middle product of the three neighboring terms $$ (x-x_{i-1})(x-x_i)(x-x_{i+1})=h^3(s^3-s) $$ and compute its extrema over the interval $[-1/2,1/2]$. One again gets upper and lower bounds for $1\le i\le n-1$ \begin{multline} h^{n+1}(i-1)!(n-i-1)!\cdot |s-s^3|\le h^{n+1}(i+s)...(2+s)(1+s)|s|(1-s)(2-s)...(n-i-s) \\ =\prod_{j=0}^n|x-x_j|\le \frac14h^{n+1}(i+1)!(n-i+1)!\cdot |s-s^3| \end{multline} The maximum for the upper bound inside these sub-intervals is at $|s|=\pm\frac12$ with $|s-s^3|=\frac38$

At the boundary, for instance for $|x-x_0|<h/2$, this bound requires to take $i=1$, $s\in [-1,-\frac12)$. Then the maximum is at $s=\pm\frac1{\sqrt3}$ with value $\frac2{3\sqrt3}$ so that the overall maximum of the upper bound is $\frac1{3\sqrt3}h^{n+1}n!$, which is a little smaller than the first bound.

Take extra care for the boundary cases where $i\le 1$ or $i\ge n-1$.