Polynomial Interpolation and Error Formulas

(20 pts) Consider the ODE, \[ u'(t) = Au + N(t,u), \]

where \(A\) is a fixed matrix and \(N\) is an arbitrary, e.g., nonlinear, function.

1. (6 pts) With initial data \(u(0) = u_0\), show that the solution to this IVP at time \(t > 0\) is given by, \[ u(t) = e^{tA}u_0 + \int _0^t e^{(t-s)A}N(s,u(s))\,ds, \] where \(e^{tA}\) is the matrix exponential of \(tA\).
2. (14 pts) Exponential integrators form a scheme to compute \(u_{n+1}\) in terms of \(u_n\) by integrating the above expression over the interval \([t_n,t_{n+1}]\) (instead of \([0,t]\)), by approximating \(N(u(s))\) with a quadrature rule/polynomial approximation, and by exactly integrating the matrix exponential term. A Forward Euler exponential integrator makes the approximation \(N(u(s)) \approx N(u_n)\). Write out the Forward Euler exponential integrator scheme explicitly (i.e., by eliminating integrals).

(20 pts)

1. (10 pts) Compute coefficients \(A\), \(B\), \(C\) in the 3-point one-sided approximation \[ u''(x) \approx Au(x) + Bu(x+h) + Cu(x+2h) \]

   that has optimal \(h\)-order of accuracy. What is this order of accuracy?

2. (10 pts) Compute weights for the following quadrature rule that makes it exact for all polynomials of degree 2. \[ \int _{-1}^1 f(x)\,dx = w_0 f(0) + w_1 f'(0) + w_2 f''(0), \]

(Numerical Integration). Determine the coefficients \(A_0\), \(A_1\), and \(A_2\) that make the formula \[ \int _0^2 f(x)\,dx \approx A_0 f(0) + A_1 f(1) + A_2 f(2) \] exact for all polynomials of degree 3.

Suppose \(f(x) \in C^{n+1}([a,b])\), and consider the interpolation problem: For \(a \le x_0 < x_1 <\) \(x_2 < \cdots < x_{n-1} < x_n \le b\), find a polynomial \(p(x)\) of degree at most \(n\) for which \(p(x_j) = f(x_j)\), \(j = 0,1,\ldots ,n\).

1. Show that this problem has at most one solution.
2. Show that this problem has a solution.
3. Show, for any \(x \in [a,b]\), that \[ f(x)-p(x)=\frac {f^{n+1}(\xi )}{(n+1)!}(x-x_0)(x-x_1)\cdots (x-x_n), \] for some \(\xi \in [a,b]\).

Numerical Integration

Determine a formula \[ \int _{-\pi }^{\pi } f(x)\cos (x)\,dx \approx A_0 f\left (-\frac {3}{4}\pi \right ) +A_1 f\left (-\frac {1}{4}\pi \right ) +A_2 f\left (\frac {1}{4}\pi \right ) +A_3 f\left (\frac {3}{4}\pi \right ) \] that is exact when \(f\) is a polynomial of degree 3.

Interpolation

Let \(x_0,\ldots ,x_n\) be distinct real points, and consider the following interpolation problem. Choose a function \[ F_n(x)=\sum _{j=0}^{n}a_j e^{jx} \] such that \[ F_n(x_i)=y_i,\qquad i=0,1,\ldots ,n \] with the \(\{y_i\}\) given data. Show there is a unique choice of \(a_0,\ldots ,a_n\).

Let \(f(z)\) be an entire function such that there exists a constant \(M\), an \(R>0\) and an integer \(n\ge 1\) with \(\lvert f(z)\rvert \le M\lvert z\rvert ^n\) for \(\lvert z\rvert >R\). Show that \(f(z)\) is a polynomial of degree at most \(n\).

Lebesgue’s Lemma

Let \(I\) be a closed, bounded interval on the real line and let \(\|f\|_\infty :=\sup _{x\in I}|f(x)|\). Given \(N\) distinct points \(x_1,\ldots ,x_N\in I\) and a continuous function \(f\), consider the Lagrange form of the degree-\((N-1)\) polynomial interpolant of \(f\): \[ I_N f := \sum _{j=1}^{N}f(x_j)\ell _j(x), \]

where \(\{\ell _j(\cdot )\}_{j=1}^{N}\) are cardinal Lagrange polynomials. Show that \[ \sup _{\|g\|_\infty =1}\|I_N g\|_\infty \le \Lambda := \sum _{j=1}^{N}|\ell _j(x)|, \] and that \[ \|f-I_N f\|_\infty \le (1+\Lambda )\inf _{p\in P_{N-1}}\|f-p\|_\infty , \] where \(P_{N-1}=\operatorname {span}\{1,x,\ldots ,x^{N-1}\}\).

Note: In problems 5–8, the notations \(k=\Delta t\) and \(h=\Delta x\) are used.

Quadrature

Consider the quadrature rule \[ \int _{-1}^{1} f(x)\,dx \approx w_{-1}f(-1)+w_0f(0)+w_1f(1)+w_0'f'(0). \] Compute weights \(w_{-1}\), \(w_0\), \(w_1\), and \(w_0'\) such that this quadrature rule is exact for polynomials up to degree 3.

1. State and prove Liouville’s theorem.
2. Show that every polynomial of degree \(n\ge 1\) in the complex plane has at least one root.

Interpolation

a) State the theorem about the existence and uniqueness of interpolating polynomial. Give a proof. (You can consider any proof of your choice).

b) Let \(f(x)=x^3+2x^2+x+1\). Find the polynomial of degree 4 that interpolates the values of \(f\) at \(x=-2,-1,0,1,2\).

Interpolation

a) State the theorem about the existence and uniqueness of interpolating polynomial. Give a proof.

b) Let \(f(x)=5x^2+x+1\). Find the polynomial of degree 3 that interpolates the values of \(f\) at \(x=-1,0,1,2\).

Interpolation Suppose \(f\) is arbitrarily often differentiable and let \(p\) be the unique polynomial of degree \(d\) satisfying \[ p(x_i)=f(x_i),\qquad i=0,\ldots ,n \] where the abscissas \(x_i\) are distinct. Derive a suitable expression for the error \(f(x)-p(x)\) and discuss its properties.

Consider the quadrature rule \[ \int _a^b w(x)f(x)dx = \sum _{j=1}^n w_jf(x_j)+E_n. \] Assume that \(w\) is a positive weight function. Discuss how to pick the knots \(x_1,\ldots ,x_n\) and weights \(w_1,\ldots ,w_n\) to make the error \(E_n\) zero for all polynomials \(f\) up to a degree as high as possible.

Consider the variational principle: \[ I(u)=\int _0^1 \left (u'(x)\right )^2+k^2\left (u(x)\right )^2 dx=\min \qquad \text {subject to}\qquad u(0)=u(1)=1. \] Suppose you want to use the Ritz Method to approximate the solution of this problem by a polynomial of degree \(n\). Derive a linear system for the coefficients of that polynomial.

Interpolating Polynomial

Define \(l_{i,n}(x)\) - Lagrange basis functions with \(x_0,x_1,\ldots ,x_n\). Prove that for any \(n\geq 1\), \[ \sum _{i=0}^n l_{i,n}(x)=1 \] for all \(x\).

Existence and Uniqueness of the Interpolating Polynomial

State the theorem about the existence and uniqueness of the interpolating polynomial.

Give the proof. (You can consider any proof of your choice.)

The Companion Matrix Show that \[ \begin {aligned} &\det \left ( \begin {bmatrix} \alpha _{n-1} & \alpha _{n-2} & \cdots & \alpha _1 & \alpha _0\\ 1 & 0 & \cdots & 0 & 0\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end {bmatrix} - \lambda I \right ) \\ &\qquad = (-1)^n\left [\lambda ^n-\sum _{j=0}^{n-1}\alpha _j\lambda ^j\right ]. \end {aligned} \tag {1} \] Describe how this fact can be used to find the roots of a polynomial. Also briefly describe why the reverse process, finding the eigenvalues of a matrix by computing the characteristic polynomial, and finding its roots, is not generally viable.

The interpolant to symmetric data is symmetric Suppose you are given symmetric data \[ (x_i,y_i),\qquad i=-n,-n+1,\cdots ,n-1,n, \tag {3} \] such that \[ x_{-i}=-x_i,\qquad \text {and}\qquad y_{-i}=y_i\qquad i=0,1,\cdots ,n. \tag {4} \] What is the required degree of the interpolating polynomial \(p\)? Show that the interpolating polynomial is even, i.e., \[ p(x)=p(-x) \tag {5} \] for all real numbers \(x\).

Polynomial Interpolation Let \(I=[a,b]\), let \(x_i\), \(i=0,\ldots ,n\), be \(n+1\) distinct points in \(I\), and let \(y_i\), \(i=0,\ldots ,n\), be \(n+1\) given real numbers. Show that there exists a unique polynomial \[ p(x)=\sum _{i=0}^n \alpha _i x^i \] such that \[ p(x_i)=y_i,\qquad i=0,\ldots ,n. \]

Interpolation error Let \(I=[a,b]\) and \(f\in C^\infty [a,b]\). Let \(x_i\), \(i=0,\ldots ,n\) be \(n+1\) distinct points in \(I\). Let \(p(x)\) be the unique polynomial of degree at most \(n\) satisfying \(p(x_i)=f(x_i)\), \(i=0,\ldots ,n\). Given \(x\) in \([a,b]\), show that there exists some point \(\xi \in [a,b]\) such that \[ f(x)-p(x) = \frac {\prod _{i=0}^n(x-x_i)}{(n+1)!}\,f^{(n+1)}(\xi ). \tag {3} \]

Interpolation and Integration

a) Consider equally spaced points \(x_j=a+jh\), \(j=0,\ldots ,J+1\) on the interval \([a,b]\), where \((J+1)h=b-a\). Let \(f(x)\) be a function defined on \([a,b]\). Consider the problem of finding a cubic spline approximation \(s(x)\) to \(f(x)\) that interpolates \(f\) at the points \(x_j\), is twice continuously differentiable, and satisfies \(s''(a)=s''(b)=0\). Does this problem always have a solution? If your answer is yes, derive formulas by which to determine the spline. If your answer is no, explain your reasoning.

b) Let \(I_n(f)\) denote the result of using the composite Trapezoidal rule to approximate \[ I(f)=\int _a^b f(x)\,dx \] using \(n\) equally sized subintervals of length \(h=(b-a)/n\). It can be shown that the integration error \(E_n(f)=I(f)-I_n(f)\) satisfies \[ E_n(f)=d_2h^2+d_4h^4+d_6h^6+\cdots \] where \(d_2,d_4,d_6,\ldots \) are numbers that depend only on the values of \(f\) and its derivatives at \(a\) and \(b\). Suppose you have a black-box program that, given \(f\), \(a\), \(b\), and \(n\) calculates \(I_n(f)\). Show how to use this program to obtain an \(O(h^4)\) approximation and an \(O(h^6)\) approximation to \(I(f)\).

Bernstein-Bezier Form Let \(T\) be a non-degenerate triangle with vertices \(V_1\), \(V_2\), and \(V_3\). The barycentric coordinates \(b_1\), \(b_2\), and \(b_3\) of a point \(x\in \mathbb {R}^2\) with respect to \(T\) are defined by \[ x=\sum _{i=1}^3 b_i V_i \qquad \text {where}\qquad \sum _{i=1}^3 b_i=1. \tag {6} \] A polynomial \(p\) of degree \(d\) can be written uniquely in its Bernstein-Bezier form as \[ p(x)=\sum _{i+j+k=d}\frac {d!}{i!j!k!}c_{ijk}b_1^i b_2^j b_3^k. \tag {7} \] Assuming you know the coefficients \(c_{ijk}\) of \(p\) as a polynomial of degree \(d\), show how to write \(p\) as a polynomial of degree \(d+1\) in Bernstein-Bezier form. What are the coefficients of \(p\) if \(p(x)=1\)?

Spline Spaces Let \(T\) be a triangulation of a domain \(\Omega \), and \(S\) the linear space of functions on \(T\) that are continuous on \(\Omega \) and that on each triangle in \(T\) can be written as a (bivariate) polynomial of degree \(d\). Derive the dimension of \(S\).

Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=0}^n \alpha _i f(\xi _i)+E. \tag {1} \] \(w\) is a given positive weight function. The knots \(\xi _i\) and the weights \(\alpha _i\) are at your disposal. How do you choose them so that the error \(E\) is 0 for all polynomials \(f\) of degree as high as possible? How high is possible? Give reasons for your answers.

Spline Spaces Let \(T\) be a triangulation of a domain \(\Omega \), and \(S\) the linear space of functions on \(T\) that are continuous on \(\Omega \) and that on each triangle in \(T\) can be written as a (bivariate) polynomial of degree \(d\). Derive the dimension of \(S\)?

Interpolation. Suppose you are given an arbitrarily smooth function \(f\) of a single variable \(x\), and points \[ x_0<x_1<\cdots <x_n. \] Let \(p\) be the interpolating polynomial of degree \(n\) satisfying \[ p(x_i)=f(x_i),\qquad i=0,1,\ldots ,n. \] Derive an expression for the error \[ f(x)-p(x) \] for a general value of \(x\), in terms of the derivatives of \(f\).

a) Show that the best uniform (\(L^\infty [-1,1]\)) approximation of an even polynomial \(p_n(x)\) of (even) degree \(n\) by polynomials of degree \(\le n-2\) on \([-1,1]\), is given by \(p_n(x)-c_nT_n(x)\), where \(T_n\) is the Tchebyshev polynomial of degree \(n\), and \(c_n\) is an appropriately chosen constant. Hint: First find the best approximation by polynomials of degree \(\le n-1\).

b) What are the zeroes of \(T_n\) and what are their significance in interpolation. In particular, estimate the error of interpolation at Tchebyshev nodes.