Math 563 Scientific Computing II

Homework 3 Due Jan.22 Hangjie Ji

Problem 6, section 10.6.1

• 1. Show that the points \xi_j , defined in (10.23), are symmetrically placed.
• 2. Use the definition (10.24) to prove that\beta_{0;m,1}(1-\xi)=\beta_{0;m,1}(\xi) whenever the canonical interpolation.
points are symmetrically placed.
• 3. Suppose that continuous piecewise linear interpolation is performed on noisy data f_i=f(x_i)+\epsilon_i.. (For example, the numbers f_i may be the floating-point numbers closest to the function values.) Find an estimate for the \| \cdot \|_{\infty} error in continuous piecewise linear interpolation with this noisy data: how does the error depend on the noise values \epsilon_i ?
• 4. Write a program to perform continuous piecewise linear interpolation to a given function f on a uniform mesh. Then perform a mesh refinement study with Runge's function, to determine how the maximum error in the spline approximation over x\in [-1,1] varies as a function of the mesh width h=\max_{1\le i \le n}x_i-x_{i-1} . Plot the logarithm of the maximum error versus minus the logarithm of h, and determine the power of h evidenced by the graph.
• 5.Repeat the previous exercise with f(x)=\sqrt{x} for x\in [0,1].
• 6. Perform a mesh refinement study for continuous piecewise quadratic interpolation to Runge's function.

Solution:

1. Since $\xi_0+\xi_m=1+0=1$ and for $1\le j\le m-1$ \[\xi_{m-j}+\xi_j=\sin^2(\frac{2m-2j-1}{2m-2}\frac{\pi}{2})+\sin^2(\frac{2j-1}{2m-2}\frac{\pi}{2})\] \[=\cos^2(\frac{2j-1}{2m-2}\frac{\pi}{2})+\sin^2(\frac{2j-1}{2m-2}\frac{\pi}{2})=1,\]

the points $\xi_j$ , defined in (10.23), are symmetrically placed.

2. Since $\xi_m=0$, we have $\beta_{0;m,1}(0)=1$ and $\beta_{0;m,1}(1)=\prod_{k=1}^{m-1}(1-\frac{1}{\xi_k})=1.$ Therefore $\beta_{0;m,1}(1-\xi)=\beta_{0;m,1}$ holds for $\xi = 0$.

When $0< \xi < 1$, since the canonical interpolation points are symmetrically placed, \[ \beta_{0;m,1}(1-\xi)=\prod_{k=1}^{m-1}(1-\frac{1-\xi}{\xi_k})=\prod_{k=1}^{m-1} \frac{\xi_k-1+\xi}{\xi_k}=\prod_{k=1}^{m-1} \frac{-\xi_{m-k}+\xi}{\xi_k} \] \[ =\frac{\prod_{k=1}^{m-1}(-\xi_k+\xi)} {\prod_{k=1}^{m-1} \xi_k}=\beta_{0;m,1}(\xi)(-1)^{m-1}. \] Thus when m is odd, $ \beta_{0;m,1}(1-\xi)=\beta_{0;m,1}(\xi).$

3. Suppose that f is twice continuously differentiable in [a,b], and the splines $s_{1,1}(x) $ perform the continuous piecewise linear interpolation on noisy data $f_i=f(x_i)+\epsilon_i.$ For $1\le i \le m$, suppose that $p_i$ is a linear polynomial that interpolates f at points $x_i$ and $x_{i-1}$. Then by Lemma 10.2.2, for all $x \in [x_{i-1},x_i]$ there exists $\eta \in (x_{i-1},x_i)$ such that \[f(x)-p_i(x)=\frac{f''(\eta)}{2}(x-x_{i-1})(x-x_i).\] If we set \[\xi = \frac{x-x_{i-1}}{x_i-x_{i-1}},\] then \[s_{1,1}(x)=(f(x_{i-1})+\epsilon_{i-1})(1-\xi)+(f(x_i)+\epsilon_i)\xi=p_i(x)+\epsilon_{i-1}(1-\xi)+\epsilon_i \xi.\] Then \[f(x)-s_{1,1}(x)=\frac{f''(\eta)}{2}(x-x_i)(x-x_{i-1})-\epsilon_{i-1}(1-\xi)-\epsilon_i \xi, \forall x \in [x_{i-1},x_i].\] Therefore \[\|f(x)-s_{1,1}(x)\|_{\infty}\le \max_{x_{i-1}\le x \le x_i}|\frac{f''(x)}{2}|\frac{(x_i-x_{i-1})^2}{4}+\max\{\epsilon_i,\epsilon_{i-1}\},\forall x \in [x_{i-1},x_i].\] Finally for all $x \in [a,b]$, \[\|f(x)-s_{1,1}(x)\|_{\infty}\le \max_{a\le x \le b}|\frac{f''(x)}{2}|\max_i\{\frac{(x_i-x_{i-1})^2}{4}\}+\max_i\{\epsilon_i\}.\] The error is linearly dependent on the largest value of the noise $\epsilon_i.$

4.I wrote a program to perform the continuous piecewise linear interpolation to Runge's function. The interpolation result is shown in Figure 1, with the distribution of the error presented in Figure 2. The logarithm of the maximum error versus minus the logarithm of h is plotted in Figure 3. It can be observed from the graph that $\max{error}=o(h^2).$

Figure 1

Figure 2

Figure 3

5. Then repeat the previous steps with $f(x)=\sqrt{x}$ for $x \in [0,1].$ The interpolation result is shown in Figure 4, with the distribution of the error presented in Figure 5. The logarithm of the maximum error versus minus the logarithm of h is plotted in Figure 6. The mesh refinement study shows that $\max{error}=o(h^{0.5})$ in this case.

Figure 4

Figure 5

Figure 6

6. Finally we perform a mesh refinement study for continuous piecewise quadratic interpolation to Runge's function. The interpolation result is shown in Figure 7, and the distribution of the error is presented in Figure 8. Besides the logarithm of the maximum error versus minus the logarithm of h is plotted in Figure 9. The mesh refinement study shows that $\max{error}=o(h^{3})$ in this case.

Figure 7

Figure 8

Figure 9

% Perform continuous piecewise linear interpolation
% and a mesh refinement study to Runge's function.

close all;

n = 50; % number of interpolation points
h = 2/n;

x = linspace(-1,1,n+1);
f = 1./(1+25*x.^2);

xx = linspace(-1,1,100);
s = zeros(1,100);
j = 1;
for i = 1 : 100
    if xx(i) <= (x(j+1)+1e-5)
        s(i) = f(j)*(1-(xx(i)-x(j))/h)+f(j+1)*(xx(i)-x(j))/h;
    else j = j+1;
        s(i) = f(j)*(1-(xx(i)-x(j))/h)+f(j+1)*(xx(i)-x(j))/h;
    end
end
figure(1),plot(x,f,'b-',xx,s,'ro-'),title('Piecewise linear interpolation','FontSize',14);

err = 1./(1+25*xx.^2)-s;
figure(2),plot(xx,err),title('Error','FontSize',14);

err_max = zeros(40,1);
for t = 1:40
    n = 5*t;
    h = 2/n;
    x = linspace(-1,1,n+1);
    f = 1./(1+25*x.^2);

    xx = linspace(-1,1,1000);
    s = zeros(1,1000);
    j = 1;
    for i = 1 : 1000
        if xx(i) <= x(j+1)
            s(i) = f(j)*(1-(xx(i)-x(j))/h)+f(j+1)*(xx(i)-x(j))/h;
        else j = j+1;
            s(i) = f(j)*(1-(xx(i)-x(j))/h)+f(j+1)*(xx(i)-x(j))/h;
        end
    end
    err_max(t) = max(1./(1+25*xx.^2)-s);
end
 n = 5:5:200;
 h = 2./n;
 figure(3),plot(-log(h),log(err_max)),xlabel('-log(h)','fontsize',14);
 ylabel('log(maximum error)','fontsize',14);

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % repeat the above for f(x)=\sqrt(x).

err_max = zeros(40,1);
for t = 1:40
    n = 5*t;
    h = 2/n;
    x = linspace(0,1,n+1);
    f = sqrt(x);

    xx = linspace(0,1,1000);
    s = zeros(1,1000);
    j = 1;
    for i = 1 : 1000
        if xx(i) <= x(j+1)
            s(i) = f(j)*(1-(xx(i)-x(j))/h)+f(j+1)*(xx(i)-x(j))/h;
        else j = j+1;
            s(i) = f(j)*(1-(xx(i)-x(j))/h)+f(j+1)*(xx(i)-x(j))/h;
        end
    end
    err_max(t) = max(sqrt(xx)-s);
end
 n = 5:5:200;
 h = 2./n;
 figure(4),plot(x,f,'b-',xx,s,'ro-'),title('Piecewise linear interpolation','FontSize',14);
 figure(6),plot(xx,sqrt(xx)-s),title('Error','FontSize',14);

 figure(5),plot(-log(h),log(err_max)),xlabel('-log(h)','fontsize',14);
 ylabel('log(maximum error)','fontsize',14);

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % a mesh refinement study for continuous piecewise quadratic interpolation
 % to Runge's function.

 err_max = zeros(40,1);
for t = 1:40
    n = 5*t;
    h = 2/n;
    x = linspace(-1,1,2*n+1);
    f = 1./(1+25*x.^2);

    xx = linspace(-1,1,1000);
    s = zeros(1,1000);
    j = 1;
    for i = 1 : 1000
        temp = (xx(i)-x(j))/(x(j+2)-x(j));
        if xx(i) <= x(j+2)
            s(i) = f(j)*(1-temp)*(1-2*temp)+4*f(j+1)*temp*(1-temp)+f(j+2)*temp*(2*temp-1);
        else j = j+2;
            temp = (xx(i)-x(j))/h;
            s(i) = f(j)*(1-temp)*(1-2*temp)+4*f(j+1)*temp*(1-temp)+f(j+2)*temp*(2*temp-1);
        end
    end
    err_max(t) = max(1./(1+25*xx.^2)-s);
end
 n = 5:5:200;
 h = 2./n;
 figure(7),plot(x,f,'b-',xx,s,'ro-'),title('Piecewise quadratic interpolation','FontSize',14);
 figure(8),plot(xx,sqrt(xx)-s),title('Error','FontSize',14);

 figure(9),plot(-log(h),log(err_max)),xlabel('-log(h)','fontsize',14);
 ylabel('log(maximum error)','fontsize',14);

Last modified: