📢 Updates

Lecture 9: Hermite interpolation available Assignment 3 available Lecture 8 online Lecture 7 online Schedule now available in "Admin" Problem class exercises now online Lecture 6 online Quiz 1 solutions online Lectures 2-3 exercises have solutions! Lecture 1 exercises have solutions!

9  Hermite interpolation

Lecture 9: Chapter 3: Polynomial interpolation

Warning

These lecture notes are mainly a record of what we discussed in class. They should not be used as a replacement for attending lectures or reading books. Please let me know if you find any errors or have any questions about the material.

TipHypothesis

You can use the Hypothesis commenting system available on the right side panel (you can login with your U/Google account). This allows you annotate the notes (private) and leave comments or reply to other people’s comments (public).

Note

I encourage you to download the lecture notes and play around with the Julia code.

Download (.ipynb) Ask a Question ChimeIn (opens in a new tab)

9.1 Previously…..

• Barycentric formula: for \(x \not\in X\), \(I_Xf(x) = \sum_{j=0}^n \frac{\lambda_j f(x_j)}{x - x_j} \Big/ \sum_{j=0}^n \frac{\lambda_j}{x - x_j}\) where \(\lambda_j = \prod_{k\not=j} (x_j - x_k)^{-1}\),
• Barycentric formula requires \(O(n)\) operations per evaluation and is numerically stable for Chebyshev nodes (with weights \((-1)^j\), halved for \(j = 0, n\)),
• Divided differences: \(f[x_0,\dots,x_n]\) is the leading coefficient of \(I_Xf\); it doesn’t depend on the ordering of the nodes and is linear in \(f\),
• Recursion: \(f[x_0,\dots,x_n] = \frac{f[x_1,\dots,x_n] - f[x_0,\dots,x_{n-1}]}{x_n - x_0}\) (Theorem 8.2),
• Newton form: \(I_Xf = \sum_{k=0}^n f[x_0,\dots,x_k] \, \pi_k\) where \(\pi_k(x) = (x-x_0)\cdots(x-x_{k-1})\) (Theorem 8.3),
• The coefficients can be read off from the divided difference table; adding a new node only adds one new term.

Exercise. Exercise 8.6

9.2 Hermite Interpolation

Now consider distinct nodes \(z_0, \dots, z_k\) with multiplicities \(m_0, \dots, m_k \geq 1\) and let \(X = \{\{ x_0, \dots, x_n \}\}\) be the multiset in which each \(z_j\) appears \(m_j\) times (so that \(n+1 = \sum_{j=0}^k m_j\)).

Hermite: find \(p\) such that, for \(j = 0, \dots, k\),

\[ \begin{align} p(z_j) &= f(z_j), \nonumber\\ p'(z_j) &= f'(z_j), \nonumber\\ &\vdots \nonumber\\ p^{(m_j-1)}(z_j) &= f^{(m_j-1)}(z_j). \end{align} \]

When \(m_j = 1\) for all \(j\), this is the Lagrange interpolation problem.

Exercise 9.1 Let \(f(x) = e^x\) and \(X = \{\{0, 0, 1\}\}\) (so that \(z_0 = 0\) with \(m_0 = 2\), \(z_1 = 1\) with \(m_1 = 1\), and \(n = 2\)). Find the Hermite interpolant \(p \in \mathcal P_2\) of \(f\) on \(X\) by writing \(p(x) = a_0 + a_1 x + a_2 x^2\) and solving for the coefficients. Compare \(p\) with the Taylor polynomial of degree \(1\) about \(0\) and with the Lagrange interpolant of \(f\) on \(\{0, 1\}\).

Exercise 9.2 What is the least degree polynomial interpolant on \(X = \{\{x_0, x_0, \dots, x_0\}\}\) (where \(x_0\) is repeated \(n+1\) times)?

Theorem 9.1 There exists a unique polynomial of degree at most \(n\) solving the Hermite interpolation problem.

Proof. See Exercise 9.5.

Again, we define the divided differences (but now for the more general case where we may have repeated interpolation nodes):

Definition 9.1 We define the divided difference \(f[x_{0}, \dots, x_n]\) to be the leading coefficient in the polynomial interpolation \(p\in \mathcal P_n\) solving the Hermite interpolation problem for \(f\) on \(X\):

\[ \begin{align} p(x) = f[x_0,\dots,x_n] x^n + q(x) \end{align} \]

where \(q \in \mathcal P_{n-1}\) and \(p^{(l)}(z_j) = f^{(l)}(z_j)\) for \(l = 0,\dots,m_j-1\) and \(j = 0, \dots, k\).

Theorem 9.2 Suppose that \(f\) is sufficiently differentiable (\(f \in C^{m-1}\) where \(m := \max_j m_j\)). Then, we have

\[ \begin{align} f[x_0, \dots, x_n] &= \begin{cases} \frac{f^{(n)}(x_0)}{n!} & \text{if } x_0 = x_1 = \dots = x_n \\ \frac {f[x_1, \dots, x_n] - f[x_0, \dots, x_{n-1}]} {x_n - x_0} &\text{if } x_0 \not= x_n \end{cases} \end{align} \]

If the nodes are not all equal, we can always reorder \(X\) so that \(x_0 \not= x_n\) (the divided difference does not depend on the ordering of the nodes).

Proof

Proof. You have seen above that the Taylor polynomial

\[ \begin{align} T_f(x) =\sum_{j=0}^n \frac{f^{(j)}(x_0)}{j!}(x - x_0)^j \end{align} \]

solves the Hermite interpolation problem on \(X = \{\{x_0,\dots,x_n\}\}\) in the case where \(x_0 = \dots = x_n\). For such \(X\), the leading coefficient in this expression is \(f[x_{0}, \dots, x_n] = \frac{f^{(n)}(x_0)}{n!}\).

For the second case, suppose \(x_0 \not= x_n\). We adapt the proof of Theorem 8.2.

Ordering and linearity. The Hermite interpolation problem (and so, by Theorem 9.1, its unique solution) only depends on the multiset \(X\) and not on how we label its elements. Therefore \(f[x_0,\dots,x_n]\) does not depend on the ordering of the nodes. Moreover, if \(p\) and \(q\) are the Hermite interpolants of \(f\) and \(g\) on \(X\), then \(p + cq \in \mathcal P_n\) satisfies the Hermite conditions for \(f + cg\), and so \((f + cg)[x_0,\dots,x_n] = f[x_0,\dots,x_n] + c\, g[x_0,\dots,x_n]\).

Multiplying by \((x - x_n)\). Let \(p \in \mathcal P_{n-1}\) be the Hermite interpolant of \(f\) on \(X' := \{\{x_0, \dots, x_{n-1}\}\}\) and define \(g(x) := (x - x_n) f(x)\) and \(q(x) := (x - x_n) p(x) \in \mathcal P_n\). We claim that \(q\) is the Hermite interpolant of \(g\) on \(X\). Let \(u := p - f\). By the product rule, \[ q^{(l)}(x) - g^{(l)}(x) = \frac{\mathrm d^l}{\mathrm dx^l} \big[ (x - x_n) u(x) \big] = (x - x_n) u^{(l)}(x) + l \, u^{(l-1)}(x) \] (where the second term is absent when \(l = 0\)). Let \(z\) be a node which appears \(m\) times in \(X'\), so that \(u^{(i)}(z) = 0\) for \(i = 0, \dots, m-1\).

• If \(z \not= x_n\), then \(z\) also appears \(m\) times in \(X\). For \(l \leq m - 1\), we have \(u^{(l)}(z) = u^{(l-1)}(z) = 0\), and so \(q^{(l)}(z) = g^{(l)}(z)\).
• If \(z = x_n\), then \(z\) appears \(m + 1\) times in \(X\) (with \(m = 0\) if \(x_n \not\in X'\)). For \(l \leq m\), the first term vanishes because \(z - x_n = 0\), and the second term vanishes because \(l - 1 \leq m - 1\) (or \(l = 0\)). Therefore \(q^{(l)}(x_n) = g^{(l)}(x_n)\) for \(l = 0, \dots, m\).

So \(q\) satisfies all of the Hermite conditions for \(g\) on \(X\) and, by Theorem 9.1, it is the Hermite interpolant of \(g\) on \(X\). Comparing leading coefficients, the coefficient of \(x^n\) in \(q\) is both \(g[x_0, \dots, x_n]\) and the coefficient of \(x^{n-1}\) in \(p\), that is, \(f[x_0,\dots,x_{n-1}]\). Therefore \[ \big( (x - x_n) f \big)[x_0, \dots, x_n] = f[x_0, \dots, x_{n-1}]. \] Applying this to the reordered multiset \(\{\{x_1, \dots, x_n, x_0\}\}\) gives \(\big( (x - x_0) f \big)[x_0, \dots, x_n] = f[x_1, \dots, x_n]\).

Conclusion. Since \((x - x_0) f(x) - (x - x_n) f(x) = (x_n - x_0) f(x)\), linearity gives \[ (x_n - x_0) f[x_0,\dots,x_n] = \big( (x - x_0) f \big)[x_0, \dots, x_n] - \big( (x - x_n) f \big)[x_0, \dots, x_n] = f[x_1, \dots, x_n] - f[x_0, \dots, x_{n-1}]. \] Dividing by \(x_n - x_0 \not= 0\) gives the result.

For distinct nodes, this is exactly the proof of Theorem 8.2 (where only the case \(l = 0\) appears).

9.3 Newton form and divided difference table with repeated nodes

The Newton form from Theorem 8.3 still holds when nodes are repeated. As before, let \(\pi_0(x) = 1\) and \(\pi_k(x) = (x - x_0)(x-x_1)\cdots(x - x_{k-1})\), where repeated nodes now give repeated factors (e.g. for \(X = \{\{0,0,\pi,\pi\}\}\) we have \(\pi_2(x) = x^2\) and \(\pi_3(x) = x^2 (x - \pi)\)).

Theorem 9.3 Let \(X = \{\{x_0,\dots,x_n\}\}\) be a multiset and \(f\) sufficiently differentiable. Then the Hermite interpolant of \(f\) on \(X\) is \[ p(x) = \sum_{k=0}^n f[x_0,\dots,x_k] \, \pi_k(x). \]

Proof. The same as for Theorem 8.3: let \(p_k \in \mathcal P_k\) be the Hermite interpolant of \(f\) on \(\{\{x_0,\dots,x_k\}\}\). Then \(p_k - p_{k-1} \in \mathcal P_k\) satisfies the Hermite conditions with zero data on \(\{\{x_0,\dots,x_{k-1}\}\}\), and so it has a zero of order \(m\) at every node appearing \(m\) times in \(\{\{x_0,\dots,x_{k-1}\}\}\) (see Exercise 9.5, part 1). Therefore \(p_k - p_{k-1} = c_k \pi_k\) and comparing the coefficients of \(x^k\) gives \(c_k = f[x_0,\dots,x_k]\).

To compute the divided difference table, list the nodes so that equal nodes are next to each other. Then every entry \(f[x_j,\dots,x_{j+k}]\) is computed using Theorem 9.2: if \(x_j = x_{j+k}\) (so that all of the nodes involved are equal), it is \(\frac{f^{(k)}(x_j)}{k!}\); otherwise it is the usual difference quotient of its two neighbours in the previous column. In particular, the first column contains \(f[x_j, x_{j+1}] = f'(x_j)\) whenever \(x_j = x_{j+1}\).

Exercise 9.3 Return to Exercise 9.1: compute the Hermite interpolant of \(f(x) = e^x\) on \(\{\{0, 0, 1\}\}\) again, this time using the divided difference table and Theorem 9.3.

Exercise 9.4 What is the Hermite interpolant of \(f(x) = \sin x\) on \(\{\{ 0,0,\pi, \pi\}\}\)? Hint: you can compute the divided difference tables in the same way as before.

TipTO-DO

• Exercises throughout the notes,
• (Sign-up to office hours if you like)

9.4 Extra exercises

Exercise 9.5 In this exercise, we prove Theorem 9.1. As in the notes, let \(z_0, \dots, z_k\) be distinct nodes with multiplicities \(m_0, \dots, m_k \geq 1\), and let \(n + 1 = \sum_{j=0}^k m_j\).

1. Let \(r \in \mathcal P_n\) and suppose that \(r^{(l)}(z) = 0\) for \(l = 0, \dots, m-1\). Show that \(r(x) = (x - z)^m s(x)\) for some polynomial \(s\).
2. Suppose that \(r \in \mathcal P_n\) satisfies \(r^{(l)}(z_j) = 0\) for all \(l = 0,\dots,m_j - 1\) and \(j = 0,\dots,k\). Show that \(r = 0\).
3. Deduce that the Hermite interpolation problem has at most one solution in \(\mathcal P_n\).
4. Consider the map \(L : \mathcal P_n \to \mathbb R^{n+1}\) defined by \(L p := \big( p^{(l)}(z_j) \big)_{j = 0,\dots,k, \; l = 0, \dots, m_j - 1}\). Show that \(L\) is linear and injective, and conclude that the Hermite interpolation problem has exactly one solution in \(\mathcal P_n\).

For 1, write \(r\) as its Taylor polynomial about \(z\) (which is exact because \(r\) is a polynomial). For 2, apply 1 at \(z_0\) and then show that \(s\) still has zeros of order \(m_j\) at \(z_j\) for \(j \geq 1\). For 4, recall that an injective linear map between vector spaces of the same finite dimension is also surjective.

1. Since \(r \in \mathcal P_n\), Taylor’s theorem is exact: \(r(x) = \sum_{l=0}^n \frac{r^{(l)}(z)}{l!} (x - z)^l = \sum_{l=m}^n \frac{r^{(l)}(z)}{l!} (x - z)^l = (x-z)^m s(x)\) where \(s(x) := \sum_{l=m}^n \frac{r^{(l)}(z)}{l!} (x - z)^{l-m}\).

2. By 1, \(r(x) = (x - z_0)^{m_0} s_0(x)\). Fix \(j \geq 1\) and write \(u(x) := (x - z_0)^{m_0}\) (so that \(u(z_j) \not= 0\) because the nodes are distinct). By the Leibniz rule, \[ r^{(l)}(z_j) = \sum_{i=0}^l \binom{l}{i} u^{(l-i)}(z_j) \, s_0^{(i)}(z_j) = u(z_j) \, s_0^{(l)}(z_j) + \sum_{i=0}^{l-1} \binom{l}{i} u^{(l-i)}(z_j) \, s_0^{(i)}(z_j). \] By induction on \(l = 0, \dots, m_j - 1\), we obtain \(s_0^{(l)}(z_j) = 0\). Therefore, \(s_0\) satisfies the same conditions at \(z_1, \dots, z_k\) and, repeating the argument, we have \[ r(x) = (x - z_0)^{m_0} (x - z_1)^{m_1} \cdots (x - z_k)^{m_k} s(x) \] for some polynomial \(s\). If \(s \not= 0\), then \(r\) has degree at least \(\sum_j m_j = n+1\), which contradicts \(r \in \mathcal P_n\). Therefore \(s = 0\) and \(r = 0\).

3. If \(p, q \in \mathcal P_n\) both solve the Hermite interpolation problem, then \(r := p - q \in \mathcal P_n\) satisfies \(r^{(l)}(z_j) = f^{(l)}(z_j) - f^{(l)}(z_j) = 0\) for all \(j\) and \(l = 0, \dots, m_j-1\). By 2, \(r = 0\) and so \(p = q\).

4. Differentiation and evaluation are linear and so \(L\) is linear. If \(L p = 0\), then \(p = 0\) by 2, and so \(L\) is injective. Since \(\dim \mathcal P_n = n + 1 = \dim \mathbb R^{n+1}\), the rank-nullity theorem shows that \(L\) is also surjective. In particular, there exists \(p \in \mathcal P_n\) with \(L p = \big( f^{(l)}(z_j) \big)_{j,l}\), which is exactly a solution to the Hermite interpolation problem. By 3, this solution is unique.

Exercise 9.6 In this exercise, we prove the error estimate for Hermite interpolation (compare with the Lagrange case in Lecture 6). We say that \(g\) has a zero of order \(m\) at \(z\) if \(g(z) = g'(z) = \dots = g^{(m-1)}(z) = 0\).

1. (Rolle’s theorem with multiplicities) Suppose that \(g \in C^1([a,b])\) has zeros at distinct points \(w_1 < \dots < w_r\) in \([a,b]\) of orders \(k_1, \dots, k_r\), and let \(N := k_1 + \dots + k_r\). Show that \(g'\) has zeros in \([w_1, w_r]\) whose orders add up to at least \(N - 1\).
2. Let \(f \in C^{n+1}([a,b])\), let \(X = \{\{x_0, \dots, x_n\}\} \subset [a,b]\) be a multiset, and let \(p \in \mathcal P_n\) be the Hermite interpolant of \(f\) on \(X\). Define the node polynomial \(\ell_X(x) := (x - x_0)(x - x_1) \cdots (x - x_n)\) (so repeated nodes give repeated factors). Show that, for every \(x \in [a,b]\), there exists \(\xi_x \in [\min (\{x\} \cup X), \max (\{x\} \cup X)]\) with \[ f(x) - p(x) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!} \ell_X(x). \]

Exercise 9.7 (Cubic Hermite interpolation) Let \(X = \{\{0, 0, 1, 1\}\}\) and suppose that we know \(f(0) = y_0\), \(f'(0) = s_0\), \(f(1) = y_1\) and \(f'(1) = s_1\).

1. Compute the divided difference table and show that the Hermite interpolant of \(f\) on \(X\) is \[ p(x) = y_0 + s_0 x + (d - s_0) x^2 + (s_0 + s_1 - 2d) \, x^2 (x - 1), \qquad \text{where } d := y_1 - y_0. \]
2. Write down \(p\) for \(f(x) = e^x\) and compare it with Exercise 9.1.
3. Use Exercise 9.6 to show that \(\max_{x \in [0,1]} |e^x - p(x)| \leq \frac{e}{384}\).
4. More generally, suppose that \(p\) is the Hermite interpolant of \(f\) on \(\{\{a, a, b, b\}\}\). Show that \(\max_{x \in [a,b]} |f(x) - p(x)| \leq \frac{(b-a)^4}{384} \max_{[a,b]} |f^{(4)}|\). What does this tell you about approximating \(f\) on \([a,b]\) by a cubic Hermite interpolant on each of \(N\) subintervals of length \(h = \frac{b-a}{N}\)?

Exercise 9.8  

1. Let \(f \in C^n([a,b])\) and let \(X = \{\{x_0, \dots, x_n\}\} \subset [a,b]\) be a multiset. Show that there exists \(\xi \in [\min X, \max X]\) with \[ f[x_0, \dots, x_n] = \frac{f^{(n)}(\xi)}{n!}. \]
2. Deduce that \(f[x_0, x_0 + h] \to f'(x_0)\) and, more generally, \(f[x_0, x_0 + h, \dots, x_0 + nh] \to \frac{f^{(n)}(x_0)}{n!}\) as \(h \to 0\). Explain why this makes the first case of Theorem 9.2 a natural definition.

Exercise 9.9  

1. Write a Julia function hermite_dd(x, df) which takes a vector of nodes x (sorted so that equal nodes are next to each other) and a function df(l, z) returning \(f^{(l)}(z)\), and returns the Newton coefficients \(f[x_0], f[x_0,x_1], \dots, f[x_0,\dots,x_n]\) using the divided difference table.
2. Write a function newton_eval(c, x, t) which evaluates \(\sum_{k=0}^n c_k \pi_k(t)\) using \(O(n)\) operations.
3. Check your code against Exercise 9.1, Exercise 9.4, and Exercise 9.7, and compute \(\max_{t \in [0,1]} |e^t - p(t)|\) for the cubic Hermite interpolant of \(e^x\) on \(\{\{0,0,1,1\}\}\).