24. Lagrange interpolation#

Let \(p_n(t)\) a polynomial interpolation of the points \(\left\{(t_k, y_k) \right\}_{k=0:n}\), with \(y_k = y(t_k)\). Lagrange interpolation of \(n+1\) points requires a polynomial of degree \(n\).

24.1. Lagrangian basis, and polynomial interpolation#

Lagrangian basis. The Lagrangian basis is a set of \(n+1\) functions \(\ell_k(t)\), so that

\[\ell_k(t_j) = \delta_{jk} \ .\]

In order to satisfy these n+1 conditions, the \(k^{th}\) function of the Lagrange basis reads

\[\begin{split}\ell_j(t) = \prod_{\begin{aligned} 0 \le & m \le n \\ m & \ne j \end{aligned}} \frac{t - t_m}{t_j - t_m} \ .\end{split}\]

Properties.

  • \(\ell_k(t_j) = \delta_{jk}\)

  • \(\sum_k \ell_k(t) = 1\) todo Prove it!

Polynomial approximation. The Lagrange interpolating polynomial immediately follows as the linear combination

\[L_n\left\{ y(t) \right\}(t) = \sum_{j = 0}^{n} y_j \ell_j(t) \ .\]

24.2. Low-degree approximations with constant steps#

Constant-step sampling means \(t_k = t_0 + k h\), being \(h\) the step.

  • One-node approximation, \((t_0, y_0)\)

    \[\ell_0(t) = 1\]

    so that the constant approximation reads \(L_0(t) = y_0 \ell_0(t) = y_0\).

  • Two-node approximation, \((t_0, y_0)\), \((t_1, y_1)\)

    \[\begin{split}\begin{aligned} \ell_0(t) & = \frac{t-t_1}{t_0 - t_1} = - \frac{t-t_1}{h} \\ \ell_1(t) & = \frac{t-t_0}{t_1 - t_0} = \frac{t-t_0}{h} \\ \end{aligned}\end{split}\]

    so that the 1-degree approximation reads \(L_1(t) = y_0 \ell_0(t) + y_1 \ell_1(t)\).

  • Three-node approximation, \((t_0, y_0)\), \((t_1, y_1)\), \((t_2, y_2)\)

    \[\begin{split}\begin{aligned} \ell_0(t) & = \frac{(t-t_1)(t-t_2)}{(t_0 - t_1)(t_0 - t_2)} = \frac{(t-t_1)(t-t_2)}{2 h^2} \\ \ell_1(t) & = \frac{(t-t_0)(t-t_2)}{(t_1 - t_0)(t_1 - t_2)} = - \frac{(t-t_0)(t-t_2)}{ h^2} \\ \ell_2(t) & = \frac{(t-t_0)(t-t_1)}{(t_2 - t_0)(t_2 - t_0)} = \frac{(t-t_0)(t-t_1)}{2 h^2} \\ \end{aligned}\end{split}\]

    so that the 2-degree approximation reads \(L_2(t) = y_0 \ell_0(t) + y_1 \ell_1(t) + y_2 \ell_2(t)\).

  • Four-node approximation, \((t_0, y_0)\), \((t_1, y_1)\), \((t_2, y_2)\), \((t_3, y_3)\)

    \[\begin{split}\begin{aligned} \ell_0(t) & = - \frac{(t-t_1)(t-t_2)(t-t_3)}{6 h^3} \\ \ell_1(t) & = \frac{(t-t_0)(t-t_2)(t-t_3)}{2 h^3} \\ \ell_2(t) & = - \frac{(t-t_0)(t-t_1)(t-t_3)}{2 h^3} \\ \ell_3(t) & = \frac{(t-t_0)(t-t_1)(t-t_2)}{6 h^3} \\ \end{aligned}\end{split}\]

    so that the 3-degree approximation reads \(L_3(t) = \sum_{k=0}^{3} y_k \ell_k(t)\).

24.3. Applications#

24.3.1. Lagrange interpolation and multi-step methods for IVPs governed by ODEs#

24.3.1.1. Adams-Bashforth#

AB1. Using \(n=0\) approximation with points \((t_0, f_0)\) to integrate from \(t_0\) to \(t_1\)

\[\begin{split}\begin{aligned} y_{1} - y_{0} & = \int_{t = t_0}^{t_1} f_0 d t = \\ & = h f_0 \end{aligned}\end{split}\]

and thus, AB1 is the explicit Euler method

\[y_{n+1} = y_{n} + h f(t_n, y_n) \ .\]

AB2. Using \(n=1\) approximation with points \((t_0, f_0)\), \((t_1, f_1)\) to integrate from \(t_1\) to \(t_2\)

\[\begin{split}\begin{aligned} y_{2} - y_{1} & = \int_{t = t_1}^{t_2} \left\{ - f_0 \frac{t-t_1}{h} + f_1 \frac{t-t_0}{h} \right\} d t = \\ & = \frac{1}{h} \left.\left\{ - f_0 \frac{(t-t_1)^2}{2} + f_1 \frac{(t-t_0)^2}{2} \right\}\right|_{t_1}^{t_2} = \\ & = \frac{1}{h} \left\{ - f_0 \frac{h^2}{2} + f_1 \frac{3 h^2}{2} \right\} \ , \end{aligned}\end{split}\]

and thus

\[y_{n+1} = y_{n} + h \left( \frac{3}{2} f(t_{n}, y_{n}) - \frac{1}{2} f(t_{n-1}, y_{n-1}) \right)\]

24.3.1.2. Adams-Moulton#

AM1. Using \(n=0\) approximation with points \((t_1, f_1)\) to integrate from \(t_0\) to \(t_1\)

\[\begin{split}\begin{aligned} y_{1} - y_{0} & = \int_{t = t_0}^{t_1} f_1 d t = \\ & = h f_0 \end{aligned}\end{split}\]

and thus, AB1 is the implicit Euler method

\[y_{n+1} = y_{n} + h f(t_{n+1}, y_{n+1}) \ .\]

AM2. Using \(n=1\) approximation with points \((t_1, f_1)\), \((t_2, f_2)\) to integrate from \(t_1\) to \(t_2\)

\[\begin{split}\begin{aligned} y_{2} - y_{1} & = \int_{t = t_1}^{t_2} \left\{ - f_1 \frac{t-t_2}{h} + f_2 \frac{t-t_1}{h} \right\} d t = \\ & = \frac{1}{h} \left.\left\{ - f_1 \frac{(t-t_2)^2}{2} + f_2 \frac{(t-t_1)^2}{2} \right\}\right|_{t_1}^{t_2} = \\ & = \frac{1}{h} \left\{ f_1 \frac{h^2}{2} + f_2 \frac{h^2}{2} \right\} \ , \end{aligned}\end{split}\]

and thus

\[y_{n+1} = y_{n} + h \left( \frac{1}{2} f(t_{n+1}, y_{n+1}) + \frac{1}{2} f(t_{n}, y_{n}) \right)\]

24.3.1.3. Backward Differentiation Formulas#

BDF1 Using \(n=1\) approximation

\[\begin{split}\begin{aligned} f_1 & = \left.\frac{d}{dt} y(t) \right|_{t=t_1} \simeq \\ & = \left.\frac{d}{dt} \left[ - y_0 \frac{t-t_1}{h} + y_1 \frac{t-t_0}{h} \right]\right|_{t=t_1} = \\ & = \frac{1}{h} \left( - y_0 + y_1 \right) \ , \end{aligned}\end{split}\]

and thus, BDF1 is the implicit Euler method,

\[y_{n+1} = y_{n} + h f(t_{n+1}, y_{n+1}) \ .\]

BDF2 Using \(n=2\) approximation

\[\begin{split}\begin{aligned} f_2 & = \left.\frac{d}{dt} y(t) \right|_{t=t_2} \simeq \\ & = \left.\frac{d}{dt} \left[ y_0 \frac{(t-t_1)(t-t_2)}{2 h^2} - y_1 \frac{(t-t_0)(t-t_2)}{h^2} + y_2 \frac{(t-t_0)(t-t_1)}{2 h^2} \right]\right|_{t=t_2} = \\ & = \frac{1}{h^2} \left.\left[ \frac{y_0}{2} ( 2 t - t_1 - t_2 ) - y_1 ( 2 t - t_0 - t_2 ) + \frac{y_2}{2} ( 2 t - t_0 - t_1 ) \right]\right|_{t=t_2} = \\ & = \frac{1}{h^2} \left[ \frac{y_0}{2} h - y_1 \cdot 2 h + \frac{y_2}{2} \cdot 3 h \right] \ , \end{aligned}\end{split}\]

and thus

\[\frac{3}{2} y_{n+1} - 2 y_{n} + \frac{1}{2} y_{n-1} = h f(t_{n+1}, y_{n+1})\]

i.e.

\[y_{n+1} - \frac{4}{3} y_{n} + \frac{1}{3} y_{n-1} = \frac{2}{3} h f(t_{n+1}, y_{n+1}) \ .\]