Interpolation error estimate




Demonstration of the method of estimating the upper bound of the constant for the maximum norm of the Lagrange interpolation error.



  • DEMO

About the project

This project demonstrates the method of estimating the $L^\infty$-norm of the linear Lagrange interpolation error.

$L^\infty$ norm error constant estimation for the linear Lagrange interpolation

Let $K$ be a triangular domain with vertices $P_1, P_2, P_3$. Let $\Pi$ be the Lagrange interpolation over triangle $K$, such that for $u \in H^2(K)$, $(\Pi^L u -u )(p) = 0,\quad p=P_1, P_2, P_3$ .

Let us consider the following error estimation for $\Pi^L$ with error constant $C^L(K)$, that is,

$$||u-\Pi^L u||_{\infty} \leq C^L(K) |u|_2$$

where $|u|_2$ denote the $H^2$ seminorm of $u$ and $||u||_{\infty}$ denote the $L^\infty$ norm of $u$.

The optimal estimation of the constant $C^L(K)$ is expressed as

$$C^L(K) = \sup_{u\in H^2(K)}\frac{||u-\Pi^L u||_{\infty}}{|u|_2}$$

This project shows the proposed algorithm to obtain the optimal estimate of $C^L(K)$ for any triangle of arbitrary shape. In this algorithm, we consider the solution of the optimization problem involving the maximum norm:

Find $\lambda$ such that

$$\lambda = \inf_{u\in V^L(K)}\frac{(|u|_2)^2}{(||u||_{\infty})^2}$$

Note that the objective constant $C^L(K)= \lambda^{-1/2}$.

Content Description

The following notebooks are contained in the project.

  1. Maximum Norm Error Estimation

    • Here, the framework of the concept and algorithm is explained. The basic concepts and important results are discussed and the concise code for finding the interpolation constant estimate is presented. Given a uniquely-defined triangle using constants $\alpha$, $h_{med}$ and $\theta$, the optimal interpolation constant is estimated using the technique in solving a quadratic optimization problem with maximum norm constraint. In this notebook, the concise function that implements this algorithm is given.\
  2. Comparison of the upper bounds for different mesh size

    • In this notebook, for a right isosceles triangle $K$, the estimate for $C^L(K)$ is obtained using uniform triangulation. It is demonstrated how the estimate of the interpolation error constant varies as the mesh is refined.\
  3. Lower Bounds of the Constant

    • In this notebook, the lower bound of the constant is also determined to verify sharpness. Here, high-degree polynomials are obtained through interpolation at the given nodes of the triangulation. The, since $C^L$ is the supremum of quotients of the form $\frac{|| f -\Pi^L f ||_{\infty}}{|f|_{2}}$, a lower bound for the interpolation error constant is achieved. \
  4. Contour Lines

    • The upper bound of the constant for a triangle with vertices $P_1(0,0)$, $P_2(1,0)$ and $P_3(x,y)$. As the third vertex varies in the first and second quadrant of the $(x,y)$-plane, the upper bound of the constant also varies. Here, the contour lines of the upper bound are graphed.\
  5. Interpolation Constants for Various Triangles

    • In this notebook, we summarize the estimated interpolation constants, given number of iterations, inner angle, alpha and median length of triangle.\
  6. Interval Computation

    • To employ numerical verification, this notebook incorporates interval computation in the algorithm for estimating the interpolation constant. In the first section, interval computation is first verified for a predefined mesh. Next, the concise code for interval computation is presented. A table containing the summary of computations for the interpolation error constant for a right isosceles triangle is also shown.

% Edited Shirley Mae Galindo 08/09/2022

About the directory

Folders or files beginning with a dot are not displayed by default.

Virtual Machine Setting


You are starting the virtual machine as a visitor to current project. As a visitor, you can change files in the booted virtual machine, but the changed files will be aborted when the server is shut down.

(Please login first to start the virtual machine.)

About Machine Type

The machine with type as "n1-standard-1" has 1 CPU Core and 4GB memory. The Google app compute engine provides a detailed guide of the machine type. For more detailed information, please refer to More detail.
If you need a high-spec machine type, please contact the site manager.