Chapter 3
Interpolation and Approximation Theory
Rendered from the uploaded full LaTeX source with KaTeX. No PDF, no PDF.js, no image extraction, and no raw LaTeX displayed.
After completing this chapter, the reader should be able to:
construct interpolating polynomials in Lagrange, Newton, and barycentric form;
prove existence and uniqueness of interpolation at distinct nodes;
derive interpolation error formulas and divided-difference identities;
understand the Runge phenomenon and the role of Chebyshev nodes;
use Lebesgue constants to quantify interpolation stability;
derive Hermite interpolation and cubic spline systems;
understand Bernstein polynomial approximation and the Weierstrass theorem;
formulate best uniform approximation and the Chebyshev alternation theorem;
compare polynomial, rational, spline, barycentric, and radial basis approximations;
solve basic, advanced, and research-level approximation problems.
The Approximation Problem
Approximation theory studies how complicated functions can be represented by simpler objects. The simplest and most classical approximation spaces are polynomial spaces: \mathbb P_n = \{p:p(x)=a_0+a_1x+\cdots+a_nx^n\}. Given a function f, one may seek an approximation p\in\mathbb P_n satisfying one of the following conditions:
interpolation: p(x_j)=f(x_j),\qquad j=0,\ldots,n;
least-squares approximation: \|f-p\|_2=\min_{q\in \mathbb P_n}\|f-q\|_2;
best uniform approximation: \|f-p\|_\infty=\min_{q\in \mathbb P_n}\|f-q\|_\infty;
structure-preserving approximation, such as positivity, monotonicity, convexity, or conservation of certain moments.
Interpolation is exact at the prescribed nodes, but exactness at nodes does not guarantee global accuracy. The distribution of nodes, the smoothness of the function, and the numerical stability of the representation are all decisive.
Polynomial Interpolation
Let x_0,x_1,\ldots,x_n be distinct nodes, and let y_j=f(x_j). The polynomial interpolation problem is to find p_n\in\mathbb P_n such that p_n(x_j)=y_j, \qquad j=0,\ldots,n.
Let x_0,\ldots,x_n be distinct real numbers. For arbitrary values y_0,\ldots,y_n, there exists a unique polynomial p_n\in\mathbb P_n such that p_n(x_j)=y_j, \qquad j=0,\ldots,n.
Define the Lagrange basis functions \ell_j(x) = \prod_{\substack{0\le m\le n\\m\ne j}} \frac{x-x_m}{x_j-x_m}. Then \ell_j(x_i)=\delta_{ij}. Hence p_n(x)=\sum_{j=0}^n y_j\ell_j(x) satisfies p_n(x_i)=y_i. This proves existence.
For uniqueness, suppose p,q\in\mathbb P_n interpolate the same data. Then r=p-q\in\mathbb P_n has roots x_0,\ldots,x_n. Thus r has at least n+1 distinct roots. Since \deg r\le n, it follows that r\equiv0. Therefore p=q.
□
The Vandermonde System
Writing p_n(x)=a_0+a_1x+\cdots+a_nx^n leads to the linear system Va=y, where V= \begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n\\ 1 & x_1 & x_1^2 & \cdots & x_1^n\\ \vdots & \vdots & \vdots & & \vdots\\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{pmatrix}. Although this formulation is mathematically natural, it is frequently numerically ill-conditioned.
Solving interpolation problems by explicitly inverting a Vandermonde matrix in the monomial basis is often a poor numerical strategy. Barycentric and Newton forms are usually preferable.
For distinct nodes x_0,\ldots,x_n, \det V = \prod_{0\le i<j\le n}(x_j-x_i). In particular, V is nonsingular if and only if the nodes are distinct.
The determinant is a polynomial in the variables x_0,\ldots,x_n. If x_i=x_j for i\ne j, two rows of V coincide, so the determinant vanishes. Hence every factor x_j-x_i divides \det V. Since both sides have total degree 0+1+\cdots+n=\frac{n(n+1)}2, the determinant must be a constant multiple of \prod_{0\le i<j\le n}(x_j-x_i). The coefficient of the monomial x_0^0x_1^1\cdots x_n^n is 1 on both sides, so the constant is 1.
□
Lagrange Interpolation
The Lagrange form is p_n(x)=\sum_{j=0}^n f(x_j)\ell_j(x), where \ell_j(x)= \prod_{\substack{0\le m\le n\\m\ne j}} \frac{x-x_m}{x_j-x_m}.
Newton Interpolation and Divided Differences
The Newton form is p_n(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1) + \cdots + c_n\prod_{j=0}^{n-1}(x-x_j). The coefficients are divided differences: c_k=f[x_0,\ldots,x_k].
The zeroth divided differences are f[x_j]=f(x_j). For k\ge1, f[x_j,\ldots,x_{j+k}] = \frac{ f[x_{j+1},\ldots,x_{j+k}] - f[x_j,\ldots,x_{j+k-1}] } {x_{j+k}-x_j}.
Let x_0,\ldots,x_n be distinct. The interpolating polynomial is p_n(x) = f[x_0] + f[x_0,x_1](x-x_0) + \cdots + f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j).
Let p_k be the interpolating polynomial through x_0,\ldots,x_k. Since p_k-p_{k-1} vanishes at x_0,\ldots,x_{k-1}, it must have the form p_k(x)-p_{k-1}(x)=c_k\prod_{j=0}^{k-1}(x-x_j). Evaluating at x_k determines c_k. The recursive formula for divided differences shows that c_k=f[x_0,\ldots,x_k]. Summing these increments gives the Newton formula.
□
Caption.
Divided differences
distinct nodes x_0,\ldots,x_n, values f_0,\ldots,f_n
c_j\gets f_j, j=0,\ldots,n
For k=1,\ldots,n:
For j=n,n-1,\ldots,k:
c_j\gets (c_j-c_{j-1})/(x_j-x_{j-k})
Return c_0,\ldots,c_n
Interpolation Error
Let f\in C^{n+1}[a,b], and let p_n interpolate f at distinct nodes x_0,\ldots,x_n\in[a,b]. For every x\in[a,b], there exists \zeta_x\in(a,b) such that f(x)-p_n(x) = \frac{f^{(n+1)}(\zeta_x)}{(n+1)!} \prod_{j=0}^n (x-x_j).
If x=x_j, the result is immediate. Otherwise define \omega_{n+1}(t)=\prod_{j=0}^n(t-x_j), and choose A so that F(t)=f(t)-p_n(t)-A\omega_{n+1}(t) satisfies F(x)=0. Since F(x_j)=0 for j=0,\ldots,n, the function F has n+2 distinct zeros. By repeated Rolle’s theorem, F^{(n+1)} has at least one zero \zeta_x. But F^{(n+1)}(t)=f^{(n+1)}(t)-A(n+1)!. Hence A=\frac{f^{(n+1)}(\zeta_x)}{(n+1)!}. Since F(x)=0, f(x)-p_n(x)=A\omega_{n+1}(x), which proves the formula.
□
Lebesgue Constants and Stability
The interpolation operator I_n:C[a,b]\to\mathbb P_n is I_n f(x)=\sum_{j=0}^n f(x_j)\ell_j(x). Its operator norm in the uniform norm is the Lebesgue constant: \Lambda_n = \|I_n\|_\infty = \max_{x\in[a,b]} \sum_{j=0}^n |\ell_j(x)|.
Let p^\ast\in\mathbb P_n be a best uniform approximation to f. Then \|f-I_n f\|_\infty \le (1+\Lambda_n)\|f-p^\ast\|_\infty.
Since I_np^\ast=p^\ast, f-I_nf = f-p^\ast+I_np^\ast-I_nf = (f-p^\ast)-I_n(f-p^\ast). Therefore \|f-I_nf\|_\infty \le \|f-p^\ast\|_\infty + \|I_n(f-p^\ast)\|_\infty. Using \|I_n\|_\infty=\Lambda_n, we get \|f-I_nf\|_\infty \le (1+\Lambda_n)\|f-p^\ast\|_\infty.
□
The Lebesgue constant measures the stability of interpolation with respect to data perturbations. Even when a good polynomial approximant exists, interpolation may be bad if \Lambda_n is large.
Runge Phenomenon and Chebyshev Nodes
Equally spaced interpolation may diverge for analytic functions. The classical example is Runge’s function f(x)=\frac{1}{1+25x^2}, \qquad x\in[-1,1]. High-degree equally spaced interpolation oscillates severely near the endpoints.
Chebyshev nodes on [-1,1] are x_j=\cos\left(\frac{j\pi}{n}\right), \qquad j=0,\ldots,n, or, in another common convention, x_j=\cos\left(\frac{(2j+1)\pi}{2n+2}\right), \qquad j=0,\ldots,n. They cluster near the endpoints and control the interpolation product.
Among monic polynomials of degree n+1, the scaled Chebyshev polynomial minimizes the uniform norm on [-1,1]. In particular, Chebyshev nodes control \max_{x\in[-1,1]}\left|\prod_{j=0}^n(x-x_j)\right| much better than equally spaced nodes.
Let T_{n+1} be the Chebyshev polynomial T_{n+1}(x)=\cos((n+1)\arccos x). Its leading coefficient is 2^n. Therefore q(x)=2^{-n}T_{n+1}(x) is monic and has uniform norm \|q\|_\infty=2^{-n}. The alternation of T_{n+1} between \pm1 at n+2 extremal points implies that no monic polynomial of degree n+1 can have smaller uniform norm; otherwise the difference would have too many sign changes for its degree. This proves the minimax property.
□
Barycentric Interpolation
The barycentric form is the preferred stable representation of polynomial interpolation. Define weights w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. Then p_n(x)= \frac{\displaystyle \sum_{j=0}^n \frac{w_j f(x_j)}{x-x_j}} {\displaystyle \sum_{j=0}^n \frac{w_j}{x-x_j}}, \qquad x\ne x_j. At a node x=x_j, set p_n(x_j)=f(x_j).
The barycentric formula represents the same interpolating polynomial as the Lagrange formula.
Let \omega(x)=\prod_{m=0}^n(x-x_m). Since \ell_j(x) = \frac{\omega(x)}{(x-x_j)\omega'(x_j)} = \omega(x)\frac{w_j}{x-x_j}, the Lagrange interpolant becomes p_n(x)=\omega(x)\sum_{j=0}^n\frac{w_jf(x_j)}{x-x_j}. Also, 1=\sum_{j=0}^n\ell_j(x) = \omega(x)\sum_{j=0}^n\frac{w_j}{x-x_j}. Dividing the two identities yields the barycentric formula.
□
Caption.
Barycentric interpolation evaluation
nodes x_j, values f_j, barycentric weights w_j, evaluation point x
If x=x_j for some j:
Return f_j
N\gets0, D\gets0
For j=0,\ldots,n:
q\gets w_j/(x-x_j)
N\gets N+q f_j
D\gets D+q
Return N/D
Hermite Interpolation
Hermite interpolation matches both function values and derivatives. The simplest case seeks H\in\mathbb P_{2n+1} satisfying H(x_j)=f(x_j), \qquad H'(x_j)=f'(x_j), \qquad j=0,\ldots,n.
Given distinct nodes x_0,\ldots,x_n, values y_j, and derivative values y'_j, there exists a unique polynomial H\in\mathbb P_{2n+1} satisfying H(x_j)=y_j, \qquad H'(x_j)=y'_j, \qquad j=0,\ldots,n.
The problem imposes 2n+2 linear conditions on the 2n+2-dimensional space \mathbb P_{2n+1}. It is enough to prove uniqueness. If H satisfies the homogeneous conditions H(x_j)=0, \qquad H'(x_j)=0, then every x_j is a root of multiplicity at least 2. Therefore \prod_{j=0}^n(x-x_j)^2 divides H. This product has degree 2n+2, while \deg H\le2n+1. Hence H\equiv0, proving uniqueness and therefore existence.
□
Spline Interpolation
High-degree global polynomials can oscillate. Splines use piecewise polynomials with smoothness constraints.
Let a=x_0<x_1<\cdots<x_n=b. A cubic spline S is a function such that:
S|_{[x_j,x_{j+1}]}\in\mathbb P_3;
S\in C^2[a,b].
If S(x_j)=f(x_j), then S is a cubic interpolating spline.
Let h_j=x_{j+1}-x_j, j=0,\ldots,n-1. The natural cubic spline interpolant is determined by second derivative values M_j=S''(x_j), where M_0=M_n=0 and, for j=1,\ldots,n-1, h_{j-1}M_{j-1} + 2(h_{j-1}+h_j)M_j + h_jM_{j+1} = 6\left[ \frac{f_{j+1}-f_j}{h_j} - \frac{f_j-f_{j-1}}{h_{j-1}} \right].
On each interval [x_j,x_{j+1}], the second derivative S'' is linear and interpolates M_j and M_{j+1}. Integrating twice gives S_j(x) = \frac{M_j(x_{j+1}-x)^3}{6h_j} + \frac{M_{j+1}(x-x_j)^3}{6h_j} + A_j(x_{j+1}-x) + B_j(x-x_j), where A_j and B_j are determined by S_j(x_j)=f_j and S_j(x_{j+1})=f_{j+1}. Enforcing continuity of S' at each interior node x_j gives the stated tridiagonal system. The natural boundary conditions are M_0=M_n=0.
□
Caption.
Natural cubic spline construction
nodes x_0<\cdots<x_n, data f_0,\ldots,f_n
Compute h_j=x_{j+1}-x_j
Assemble the tridiagonal system for M_1,\ldots,M_{n-1}
Set M_0=0, M_n=0
Solve the tridiagonal system
Construct each cubic piece from f_j,f_{j+1},M_j,M_{j+1}
Return spline S
B-Splines
B-splines form stable local bases for spline spaces. The degree-zero B-splines are piecewise constants: B_{i,0}(x)= \begin{cases} 1, & t_i\le x<t_{i+1},\\ 0, & \text{otherwise}. \end{cases} The Cox–de Boor recursion defines B_{i,k}(x) = \frac{x-t_i}{t_{i+k}-t_i}B_{i,k-1}(x) + \frac{t_{i+k+1}-x}{t_{i+k+1}-t_{i+1}}B_{i+1,k-1}(x), with zero terms interpreted when denominators vanish.
Each B-spline has compact support. Therefore changing one coefficient affects only a local region. This is one reason splines are numerically stable and geometrically useful.
Bernstein Polynomials and the Weierstrass Theorem
For f\in C[0,1], the Bernstein polynomial is B_n(f)(x) = \sum_{k=0}^n f\left(\frac{k}{n}\right) \binom{n}{k}x^k(1-x)^{n-k}.
For every f\in C[0,1], \|B_n(f)-f\|_\infty\to0. Consequently, polynomials are dense in C[0,1].
Let X_n be a binomial random variable with parameters n and x. Then B_n(f)(x)=\mathbb E\left[f\left(\frac{X_n}{n}\right)\right]. Since f is uniformly continuous on [0,1], for every \varepsilon>0 there exists \delta>0 such that |u-v|<\delta \quad\Rightarrow\quad |f(u)-f(v)|<\varepsilon. Split the expectation into the events \left|\frac{X_n}{n}-x\right|<\delta and its complement. On the first event the integrand error is below \varepsilon. On the complement it is bounded by 2\|f\|_\infty. Since \operatorname{Var}\left(\frac{X_n}{n}\right)=\frac{x(1-x)}{n}\le\frac{1}{4n}, Chebyshev’s inequality gives \mathbb P\left(\left|\frac{X_n}{n}-x\right|\ge\delta\right) \le \frac{1}{4n\delta^2}. Thus |B_n(f)(x)-f(x)| \le \varepsilon+\frac{2\|f\|_\infty}{4n\delta^2}. Taking n\to\infty and then \varepsilon\to0 proves uniform convergence.
□
Best Uniform Approximation and Chebyshev Alternation
Let f\in C[a,b]. A polynomial p^\ast\in\mathbb P_n is a best uniform approximant if \|f-p^\ast\|_\infty = \min_{p\in\mathbb P_n}\|f-p\|_\infty.
A polynomial p^\ast\in\mathbb P_n is the unique best uniform approximant to f\in C[a,b] if and only if there exist n+2 points a\le x_0<x_1<\cdots<x_{n+1}\le b such that f(x_j)-p^\ast(x_j)=\sigma(-1)^j E, \qquad E=\|f-p^\ast\|_\infty, for some sign \sigma\in\{-1,1\}.
A full proof is lengthy. The key idea is the de la Vallée Poussin alternation argument. If the error does not alternate at n+2 points, one can construct a nonzero polynomial q\in\mathbb P_n with signs arranged to reduce the maximum error. Conversely, if the error alternates at n+2 points, any improvement would require a polynomial difference q=p-p^\ast to alternate signs at n+2 points, forcing at least n+1 zeros. Since q\in\mathbb P_n, this is impossible unless q\equiv0.
□
Least-Squares Approximation and Orthogonal Projection
Let w(x)>0 be a weight on [a,b], and define \langle f,g\rangle = \int_a^b f(x)g(x)w(x)\,dx. The least-squares approximation p_n\in\mathbb P_n satisfies \|f-p_n\|_2=\min_{p\in\mathbb P_n}\|f-p\|_2.
Let \{\phi_0,\ldots,\phi_n\} be a basis of \mathbb P_n. If p_n=\sum_{j=0}^n c_j\phi_j, then p_n is the least-squares approximation if and only if \sum_{j=0}^n c_j\langle \phi_j,\phi_i\rangle = \langle f,\phi_i\rangle, \qquad i=0,\ldots,n. Equivalently, f-p_n\perp \mathbb P_n.
For arbitrary q\in\mathbb P_n, consider \Phi(\varepsilon)=\|f-(p_n+\varepsilon q)\|_2^2. At a minimizer, \Phi'(0)=-2\langle f-p_n,q\rangle=0. Thus f-p_n\perp \mathbb P_n. Taking q=\phi_i gives the normal equations. The converse follows from the Pythagorean identity \|f-p\|_2^2 = \|f-p_n\|_2^2+\|p-p_n\|_2^2.
□
Orthogonal Polynomials
Orthogonal polynomial families satisfy \langle p_i,p_j\rangle=0, \qquad i\ne j. Classical families include Legendre, Chebyshev, Laguerre, and Hermite polynomials. They lead to stable spectral approximations and Gaussian quadrature.
Let \{p_n\} be monic orthogonal polynomials with respect to a positive inner product. Then there exist real coefficients \alpha_n and positive coefficients \beta_n such that p_{n+1}(x) = (x-\alpha_n)p_n(x)-\beta_n p_{n-1}(x).
Since xp_n is a monic polynomial of degree n+1, it can be expanded as xp_n=p_{n+1}+\sum_{j=0}^n a_jp_j. For j\le n-2, \langle xp_n,p_j\rangle = \langle p_n,xp_j\rangle=0, because xp_j has degree at most n-1. Therefore only the p_n and p_{n-1} terms remain: xp_n=p_{n+1}+\alpha_np_n+\beta_np_{n-1}. Rearranging gives the recurrence, with the conventional sign absorbed into \beta_n.
□
Chebyshev Expansions and Spectral Interpolation
Chebyshev polynomials satisfy T_n(\cos\theta)=\cos(n\theta). A function f may be approximated by f(x)\approx \sum_{k=0}^n a_kT_k(x). For analytic functions, Chebyshev coefficients often decay geometrically. This is the foundation of spectral accuracy.
For smooth analytic functions, polynomial approximations at Chebyshev nodes can converge faster than any algebraic power of n. For nonsmooth functions, the coefficient decay slows, and Gibbs-type effects may appear.
Rational Approximation and Padé Approximants
Polynomial approximation is not always optimal. Rational functions can represent poles, layers, and singularities more efficiently.
A Padé approximant R_{m,n} has the form R_{m,n}(x)=\frac{P_m(x)}{Q_n(x)}, \qquad Q_n(0)=1, and matches a Taylor expansion to as high an order as possible: Q_n(x)f(x)-P_m(x)=O(x^{m+n+1}).
Let f(x)=\sum_{k=0}^{\infty}a_kx^k. The Padé approximant P_m/Q_n, with Q_n(0)=1, is determined by a linear system for the denominator coefficients so that Q_n(x)f(x)-P_m(x) has zero coefficients through degree m+n.
Write Q_n(x)=1+q_1x+\cdots+q_nx^n. The coefficients of Q_n(x)f(x) of degrees m+1,\ldots,m+n must vanish, because P_m has degree at most m. These n linear equations determine q_1,\ldots,q_n, provided the associated system is nonsingular. Then P_m is obtained by matching the remaining coefficients of degrees 0,\ldots,m.
□
Floater–Hormann Rational Interpolation
Floater–Hormann interpolation blends local polynomial interpolants into a rational interpolant without poles on the interval. For a blending parameter d, it has the barycentric form r(x)= \frac{\displaystyle \sum_{j=0}^n \frac{\lambda_j f_j}{x-x_j}} {\displaystyle \sum_{j=0}^n \frac{\lambda_j}{x-x_j}}, with carefully chosen weights \lambda_j depending on d. These interpolants often avoid Runge oscillations better than global polynomial interpolation.
Radial Basis Function Interpolation
Given centers x_1,\ldots,x_N\in\mathbb R^d, radial basis interpolation seeks s(x)=\sum_{j=1}^N c_j\phi(\|x-x_j\|), where \phi may be Gaussian, multiquadric, inverse multiquadric, or polyharmonic. The interpolation conditions are s(x_i)=f_i, \qquad i=1,\ldots,N.
Flat radial basis functions can be highly accurate but numerically ill-conditioned. Stable algorithms often require special bases, preconditioning, or local RBF methods.
Algorithms Summary
- Lagrange form.
-
The Lagrange formula is explicit and excellent for theoretical derivations. It is not the preferred form for large-scale numerical evaluation, because direct evaluation is expensive and can be unstable.
- Newton form.
-
The Newton divided-difference form is ideal when nodes are added progressively. Its main advantage is incremental construction; its main weakness is sensitivity to node ordering and divided-difference growth.
- Barycentric form.
-
The barycentric formula is the standard stable form for evaluating polynomial interpolants. With good nodes, especially Chebyshev-type nodes, it is efficient, compact, and numerically reliable.
- Chebyshev interpolation.
-
Chebyshev interpolation controls endpoint oscillations and gives spectral convergence for analytic functions. It is global, so nonsmoothness at one point can contaminate the approximation elsewhere.
- Hermite interpolation.
-
Hermite interpolation incorporates derivative information and is useful when slopes or higher derivatives are known. Its cost is the need for additional data and the possibility of ill-conditioning at high degree.
- Cubic splines.
-
Cubic splines use local cubic pieces connected with smoothness conditions. They are stable, local, and robust, especially for data with moderate smoothness.
- B-splines.
-
B-splines provide a local, compactly supported basis for spline spaces. They are essential in geometric design, finite elements, and stable piecewise-polynomial approximation.
- Bernstein polynomials.
-
Bernstein polynomials are positive, shape-preserving, and give a constructive proof of Weierstrass’ theorem. Their convergence is reliable but often slow.
- Least squares.
-
Least-squares approximation is appropriate for noisy or overdetermined data. The orthogonality principle is powerful, but normal equations may amplify conditioning problems.
- Orthogonal polynomial expansions.
-
Legendre and Chebyshev expansions diagonalize projection problems and lead to stable spectral approximations when the underlying function is smooth.
- Rational and Padé approximation.
-
Rational approximation can capture poles, boundary layers, and nearby singularities much more efficiently than polynomial approximation. The danger is the appearance of spurious poles or pole-zero cancellations.
- Floater–Hormann interpolation.
-
Floater–Hormann interpolation blends local polynomial interpolants into a rational barycentric formula, often reducing Runge oscillations without introducing poles on the interpolation interval.
- Radial basis functions.
-
RBF methods are meshfree and useful for scattered data in several dimensions. Their main numerical challenge is the ill-conditioning caused by flat kernels or poorly distributed centers.
Exercises
The following exercise bank is intentionally large. The basic problems test definitions, hand computations, and the main formulas. The starred problems require proofs and deeper analysis. The problems marked by \star\star and \star\star\star are intended for strong students, graduate work, or a future solutions manual.
Basic problems
Prove that if p\in\mathbb P_n has n+1 distinct zeros, then p\equiv0.
For the nodes x_0=0, x_1=1, x_2=2, compute the Lagrange basis polynomials \ell_0,\ell_1,\ell_2.
Find the polynomial p\in\mathbb P_2 interpolating f(x)=e^x at x=0,1,2.
Let p_1 be the linear interpolant of f at x_0 and x_1. State the error formula for f(x)-p_1(x).
Compute the divided-difference table for the data (0,1),\qquad (1,2),\qquad (2,5).
Using the divided differences from the referenced result, write the interpolating polynomial in Newton form.
Write the Vandermonde system for interpolation at nodes x_0,x_1,x_2.
Compute \det \begin{pmatrix} 1 & x_0 & x_0^2\\ 1 & x_1 & x_1^2\\ 1 & x_2 & x_2^2 \end{pmatrix}.
List the Chebyshev–Lobatto nodes for n=4 on [-1,1].
List the zeros of T_5(x) on [-1,1].
Compute the barycentric weights for the nodes 0,1,2.
Explain why the barycentric formula is usually preferable to directly evaluating the Lagrange formula.
How many interpolation conditions are imposed when H(x_j)=f(x_j) and H'(x_j)=f'(x_j) are required at n+1 nodes? What polynomial degree is sufficient?
What are the boundary conditions defining a natural cubic spline?
What are clamped cubic spline boundary conditions?
Prove that \sum_{k=0}^n \binom{n}{k}x^k(1-x)^{n-k}=1.
Show that the Bernstein basis polynomials are nonnegative on [0,1].
Explain why a least-squares approximant satisfies an orthogonality condition.
Using T_n(\cos\theta)=\cos(n\theta), prove that |T_n(x)|\le 1, \qquad -1\le x\le 1.
Explain the difference between a Taylor polynomial and a Padé approximant.
Intermediate problems \star
Prove existence of the interpolating polynomial using the Lagrange formula.
Prove uniqueness of the interpolating polynomial by applying the root-counting argument to the difference of two interpolants.
Prove the formula \det V=\prod_{0\le i<j\le n}(x_j-x_i) for the Vandermonde determinant.
Derive the divided-difference recursion f[x_j,\ldots,x_{j+k}] = \frac{f[x_{j+1},\ldots,x_{j+k}]-f[x_j,\ldots,x_{j+k-1}]} {x_{j+k}-x_j}.
Prove that f[x_0,\ldots,x_n] is symmetric in its nodes.
Prove the Newton interpolation formula p_n(x)= f[x_0]+f[x_0,x_1](x-x_0)+\cdots + f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j).
Suppose p_n interpolates f at x_0,\ldots,x_n. Derive the update formula for the interpolant p_{n+1} after adding a new node x_{n+1}.
Prove the interpolation error formula f(x)-p_n(x) = \frac{f^{(n+1)}(\zeta_x)}{(n+1)!} \prod_{j=0}^n(x-x_j).
Use the interpolation error formula to bound the error of quadratic interpolation of e^x on [0,2].
Use the interpolation error formula to bound the interpolation error for f(x)=\sin x on [0,\pi].
For nodes -1,0,1, compute \lambda_2(x)=|\ell_0(x)|+|\ell_1(x)|+|\ell_2(x)|.
Prove the Lebesgue inequality \|f-I_nf\|_\infty \le (1+\Lambda_n)\inf_{p\in\mathbb P_n}\|f-p\|_\infty.
Prove that the scaled Chebyshev polynomial is the monic polynomial of degree n with smallest uniform norm on [-1,1].
For Chebyshev nodes, estimate \max_{x\in[-1,1]}\left|\prod_{j=0}^n(x-x_j)\right|.
Prove that the barycentric formula is algebraically identical to the Lagrange interpolating polynomial.
Derive simplified barycentric weights for Chebyshev–Lobatto nodes.
Prove uniqueness of Hermite interpolation by using multiplicities of zeros.
Explain how repeated nodes in divided differences lead to Hermite interpolation.
Derive the tridiagonal system for the second derivatives of a natural cubic spline.
Using the Cox–de Boor recursion, prove that B_{i,k} has compact local support.
Advanced problems \star\star
Analyze why equally spaced interpolation of f(x)=\frac{1}{1+25x^2} on [-1,1] develops endpoint oscillations.
Explain why Lebesgue constants for equally spaced nodes grow rapidly with n.
Show that Chebyshev-type nodes have Lebesgue constants that grow only logarithmically.
Assume f is analytic in a Bernstein ellipse. Derive a geometric convergence bound for Chebyshev interpolation.
Explain why the second barycentric interpolation formula is backward stable for well-chosen nodes.
Derive the Hermite interpolation error formula for matching f and f' at n+1 nodes.
Prove that the natural cubic spline minimizes \int_a^b |S''(x)|^2\,dx among sufficiently smooth interpolants with the same nodal values.
Assume f\in C^4[a,b]. Prove an O(h^4) error estimate for cubic spline interpolation on a uniform mesh.
Prove that normalized B-splines form a partition of unity.
Give a complete proof that Bernstein polynomials converge uniformly to every continuous function on [0,1].
If f is Lipschitz continuous, derive a convergence-rate estimate for B_n(f)\to f.
Prove the Chebyshev alternation theorem for best uniform approximation.
Derive one full iteration of the Remez algorithm for best polynomial approximation.
Derive the normal equations for least-squares approximation in a nonorthogonal basis.
Prove the Pythagorean identity associated with least-squares projection.
Derive the coefficients of the best L^2[-1,1] approximation in the Legendre basis.
Prove the three-term recurrence for monic orthogonal polynomials.
Relate differentiability of f to algebraic decay of Chebyshev coefficients.
Explain why Chebyshev interpolation is spectrally accurate for analytic functions.
Derive the Chebyshev spectral differentiation matrix from barycentric cardinal functions.
Derive the linear equations defining the [m/n] Padé approximant.
Compute the [1/1] and [2/2] Padé approximants of e^x.
Explain how spurious poles may appear in rational interpolation.
Derive the Floater–Hormann barycentric rational interpolant for a small blending parameter d.
Write the interpolation matrix for radial basis interpolation and discuss conditions for nonsingularity.
Explain why Gaussian RBF interpolation becomes ill-conditioned as the shape parameter goes to zero.
Explain why polynomial or Fourier approximations of discontinuous functions exhibit Gibbs-type oscillations.
Compare global polynomial interpolation with piecewise polynomial interpolation for functions with limited smoothness.
Suppose data values are perturbed by |\delta y_j|\le\varepsilon. Show how the Lebesgue constant controls the perturbation in the interpolant.
Relate the condition number of polynomial interpolation in the uniform norm to the Lebesgue constant.
Research-level problems \star\star\star
State and prove Faber’s theorem: for every fixed triangular array of interpolation nodes, there exists a continuous function for which polynomial interpolation diverges.
Explain how logarithmic potential theory describes asymptotically optimal node distributions for polynomial interpolation.
Derive the leading asymptotic term \Lambda_n\sim \frac{2}{\pi}\log n for Chebyshev-type nodes.
Prove Markov’s inequality on [-1,1]: \|p'\|_\infty\le n^2\|p\|_\infty, \qquad p\in\mathbb P_n.
Prove Bernstein’s inequality for polynomials on [-1,1]: \sqrt{1-x^2}|p'(x)|\le n\|p\|_\infty.
State and prove a Jackson-type theorem relating polynomial approximation error to the modulus of continuity of f.
Derive interpolation estimates in Sobolev spaces for piecewise polynomial finite elements.
State the Bramble–Hilbert lemma and explain its role in finite element interpolation error estimates.
Study total positivity of B-spline collocation matrices and explain its numerical consequences.
Develop a spline quasi-interpolation operator and prove an approximation-order estimate.
Compare polynomial minimax approximation and rational minimax approximation for functions with nearby singularities.
Investigate convergence of diagonal Padé approximants and explain pole-zero defects.
Study the AAA algorithm for rational approximation and compare it with classical Padé approximation.
Define the native space of a positive definite radial kernel and prove a native-space error estimate.
Analyze why tensor-product interpolation suffers from the curse of dimensionality and explain how sparse grids reduce the cost.
Compare high-dimensional interpolation by tensor-product grids, sparse grids, and low-rank tensor formats.
Design an adaptive interpolation algorithm that detects nonsmoothness and switches between polynomial, spline, and rational local models.
Develop an interval-arithmetic method for certifying interpolation error bounds when only interval enclosures of derivatives are available.
Analyze stability of barycentric rational interpolation and identify conditions that prevent poles on the interpolation interval.
Study spectral filtering for Chebyshev expansions of nonsmooth functions. Explain how filters reduce Gibbs oscillations and what accuracy is lost.
Exercise solutions
The solutions below are converted from the uploaded LaTeX solution file. Open an accordion to view the full solution.
This chapter gives detailed worked solutions for the exercises in Chapter 3. Each solution includes the problem formulation, the method, the mathematical derivation, the conclusion, and a diagnostic comment.
Exercise 3.1
Problem formulation.
Prove that if p\in\mathbb P_n has n+1 distinct zeros, then p\equiv0.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.2
Problem formulation.
For the nodes x_0=0, x_1=1, x_2=2, compute the Lagrange basis polynomials \ell_0,\ell_1,\ell_2.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The Lagrange cardinal polynomial associated with node x_j is \ell_j(x)= \prod_{\substack{0\le m\le n\\m\ne j}} \frac{x-x_m}{x_j-x_m}. It satisfies \ell_j(x_i)=\delta_{ij}. Therefore the interpolating polynomial is p_n(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). At each node x_i, p_n(x_i)=\sum_{j=0}^{n}f(x_j)\ell_j(x_i)=f(x_i). Thus p_n interpolates f at all nodes.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.3
Problem formulation.
Find the polynomial p\in\mathbb P_2 interpolating f(x)=e^x at x=0,1,2.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.4
Problem formulation.
Let p_1 be the linear interpolant of f at x_0 and x_1. State the error formula for f(x)-p_1(x).
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.5
Problem formulation.
Compute the divided-difference table for the data (0,1),\qquad (1,2),\qquad (2,5).
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.6
Problem formulation.
Using the divided differences from the referenced result, write the interpolating polynomial in Newton form.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 3.7
Problem formulation.
Write the Vandermonde system for interpolation at nodes x_0,x_1,x_2.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.8
Problem formulation.
Compute \det \begin{pmatrix} 1 & x_0 & x_0^2\\ 1 & x_1 & x_1^2\\ 1 & x_2 & x_2^2 \end{pmatrix}.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.9
Problem formulation.
List the Chebyshev–Lobatto nodes for n=4 on [-1,1].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.10
Problem formulation.
List the zeros of T_5(x) on [-1,1].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.11
Problem formulation.
Compute the barycentric weights for the nodes 0,1,2.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The barycentric weights are w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. The barycentric interpolation formula is p_n(x)= \frac{\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}f_j} {\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}}. If x\to x_i, the terms with j=i dominate both numerator and denominator: p_n(x)\to \frac{w_if_i}{w_i}=f_i. Thus the formula interpolates the data. It is usually more stable than directly evaluating the Lagrange basis.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.12
Problem formulation.
Explain why the barycentric formula is usually preferable to directly evaluating the Lagrange formula.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The Lagrange cardinal polynomial associated with node x_j is \ell_j(x)= \prod_{\substack{0\le m\le n\\m\ne j}} \frac{x-x_m}{x_j-x_m}. It satisfies \ell_j(x_i)=\delta_{ij}. Therefore the interpolating polynomial is p_n(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). At each node x_i, p_n(x_i)=\sum_{j=0}^{n}f(x_j)\ell_j(x_i)=f(x_i). Thus p_n interpolates f at all nodes.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.13
Problem formulation.
How many interpolation conditions are imposed when H(x_j)=f(x_j) and H'(x_j)=f'(x_j) are required at n+1 nodes? What polynomial degree is sufficient?
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.14
Problem formulation.
What are the boundary conditions defining a natural cubic spline?
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.15
Problem formulation.
What are clamped cubic spline boundary conditions?
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.16
Problem formulation.
Prove that \sum_{k=0}^n \binom{n}{k}x^k(1-x)^{n-k}=1.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.17
Problem formulation.
Show that the Bernstein basis polynomials are nonnegative on [0,1].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.18
Problem formulation.
Explain why a least-squares approximant satisfies an orthogonality condition.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.19
Problem formulation.
Using T_n(\cos\theta)=\cos(n\theta), prove that |T_n(x)|\le 1, \qquad -1\le x\le 1.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.20
Problem formulation.
Explain the difference between a Taylor polynomial and a Padé approximant.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.21
Problem formulation.
Prove existence of the interpolating polynomial using the Lagrange formula.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The Lagrange cardinal polynomial associated with node x_j is \ell_j(x)= \prod_{\substack{0\le m\le n\\m\ne j}} \frac{x-x_m}{x_j-x_m}. It satisfies \ell_j(x_i)=\delta_{ij}. Therefore the interpolating polynomial is p_n(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). At each node x_i, p_n(x_i)=\sum_{j=0}^{n}f(x_j)\ell_j(x_i)=f(x_i). Thus p_n interpolates f at all nodes.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.22
Problem formulation.
Prove uniqueness of the interpolating polynomial by applying the root-counting argument to the difference of two interpolants.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.23
Problem formulation.
Prove the formula \det V=\prod_{0\le i<j\le n}(x_j-x_i) for the Vandermonde determinant.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.24
Problem formulation.
Derive the divided-difference recursion f[x_j,\ldots,x_{j+k}] = \frac{f[x_{j+1},\ldots,x_{j+k}]-f[x_j,\ldots,x_{j+k-1}]} {x_{j+k}-x_j}.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.25
Problem formulation.
Prove that f[x_0,\ldots,x_n] is symmetric in its nodes.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.26
Problem formulation.
Prove the Newton interpolation formula p_n(x)= f[x_0]+f[x_0,x_1](x-x_0)+\cdots + f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j).
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Verify the stationarity residual, feasibility residual, and descent or curvature condition, not only the final numerical value.
Exercise 3.27
Problem formulation.
Suppose p_n interpolates f at x_0,\ldots,x_n. Derive the update formula for the interpolant p_{n+1} after adding a new node x_{n+1}.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.28
Problem formulation.
Prove the interpolation error formula f(x)-p_n(x) = \frac{f^{(n+1)}(\zeta_x)}{(n+1)!} \prod_{j=0}^n(x-x_j).
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.29
Problem formulation.
Use the interpolation error formula to bound the error of quadratic interpolation of e^x on [0,2].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.30
Problem formulation.
Use the interpolation error formula to bound the interpolation error for f(x)=\sin x on [0,\pi].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.31
Problem formulation.
For nodes -1,0,1, compute \lambda_2(x)=|\ell_0(x)|+|\ell_1(x)|+|\ell_2(x)|.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.32
Problem formulation.
Prove the Lebesgue inequality \|f-I_nf\|_\infty \le (1+\Lambda_n)\inf_{p\in\mathbb P_n}\|f-p\|_\infty.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.33
Problem formulation.
Prove that the scaled Chebyshev polynomial is the monic polynomial of degree n with smallest uniform norm on [-1,1].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.34
Problem formulation.
For Chebyshev nodes, estimate \max_{x\in[-1,1]}\left|\prod_{j=0}^n(x-x_j)\right|.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.35
Problem formulation.
Prove that the barycentric formula is algebraically identical to the Lagrange interpolating polynomial.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The Lagrange cardinal polynomial associated with node x_j is \ell_j(x)= \prod_{\substack{0\le m\le n\\m\ne j}} \frac{x-x_m}{x_j-x_m}. It satisfies \ell_j(x_i)=\delta_{ij}. Therefore the interpolating polynomial is p_n(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). At each node x_i, p_n(x_i)=\sum_{j=0}^{n}f(x_j)\ell_j(x_i)=f(x_i). Thus p_n interpolates f at all nodes.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.36
Problem formulation.
Derive simplified barycentric weights for Chebyshev–Lobatto nodes.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The barycentric weights are w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. The barycentric interpolation formula is p_n(x)= \frac{\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}f_j} {\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}}. If x\to x_i, the terms with j=i dominate both numerator and denominator: p_n(x)\to \frac{w_if_i}{w_i}=f_i. Thus the formula interpolates the data. It is usually more stable than directly evaluating the Lagrange basis.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.37
Problem formulation.
Prove uniqueness of Hermite interpolation by using multiplicities of zeros.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.38
Problem formulation.
Explain how repeated nodes in divided differences lead to Hermite interpolation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.39
Problem formulation.
Derive the tridiagonal system for the second derivatives of a natural cubic spline.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.40
Problem formulation.
Using the Cox–de Boor recursion, prove that B_{i,k} has compact local support.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.41
Problem formulation.
Analyze why equally spaced interpolation of f(x)=\frac{1}{1+25x^2} on [-1,1] develops endpoint oscillations.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.42
Problem formulation.
Explain why Lebesgue constants for equally spaced nodes grow rapidly with n.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.43
Problem formulation.
Show that Chebyshev-type nodes have Lebesgue constants that grow only logarithmically.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.44
Problem formulation.
Assume f is analytic in a Bernstein ellipse. Derive a geometric convergence bound for Chebyshev interpolation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.45
Problem formulation.
Explain why the second barycentric interpolation formula is backward stable for well-chosen nodes.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The barycentric weights are w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. The barycentric interpolation formula is p_n(x)= \frac{\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}f_j} {\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}}. If x\to x_i, the terms with j=i dominate both numerator and denominator: p_n(x)\to \frac{w_if_i}{w_i}=f_i. Thus the formula interpolates the data. It is usually more stable than directly evaluating the Lagrange basis.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Always test the result on the scalar model equation or Fourier mode and verify the amplification factor satisfies the stated stability bound.
Exercise 3.46
Problem formulation.
Derive the Hermite interpolation error formula for matching f and f' at n+1 nodes.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.47
Problem formulation.
Prove that the natural cubic spline minimizes \int_a^b |S''(x)|^2\,dx among sufficiently smooth interpolants with the same nodal values.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.48
Problem formulation.
Assume f\in C^4[a,b]. Prove an O(h^4) error estimate for cubic spline interpolation on a uniform mesh.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.49
Problem formulation.
Prove that normalized B-splines form a partition of unity.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.50
Problem formulation.
Give a complete proof that Bernstein polynomials converge uniformly to every continuous function on [0,1].
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.51
Problem formulation.
If f is Lipschitz continuous, derive a convergence-rate estimate for B_n(f)\to f.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.52
Problem formulation.
Prove the Chebyshev alternation theorem for best uniform approximation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.53
Problem formulation.
Derive one full iteration of the Remez algorithm for best polynomial approximation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.54
Problem formulation.
Derive the normal equations for least-squares approximation in a nonorthogonal basis.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.55
Problem formulation.
Prove the Pythagorean identity associated with least-squares projection.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.56
Problem formulation.
Derive the coefficients of the best L^2[-1,1] approximation in the Legendre basis.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.57
Problem formulation.
Prove the three-term recurrence for monic orthogonal polynomials.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.58
Problem formulation.
Relate differentiability of f to algebraic decay of Chebyshev coefficients.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.59
Problem formulation.
Explain why Chebyshev interpolation is spectrally accurate for analytic functions.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.60
Problem formulation.
Derive the Chebyshev spectral differentiation matrix from barycentric cardinal functions.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The barycentric weights are w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. The barycentric interpolation formula is p_n(x)= \frac{\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}f_j} {\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}}. If x\to x_i, the terms with j=i dominate both numerator and denominator: p_n(x)\to \frac{w_if_i}{w_i}=f_i. Thus the formula interpolates the data. It is usually more stable than directly evaluating the Lagrange basis.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.61
Problem formulation.
Derive the linear equations defining the [m/n] Padé approximant.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.62
Problem formulation.
Compute the [1/1] and [2/2] Padé approximants of e^x.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.63
Problem formulation.
Explain how spurious poles may appear in rational interpolation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.64
Problem formulation.
Derive the Floater–Hormann barycentric rational interpolant for a small blending parameter d.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The barycentric weights are w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. The barycentric interpolation formula is p_n(x)= \frac{\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}f_j} {\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}}. If x\to x_i, the terms with j=i dominate both numerator and denominator: p_n(x)\to \frac{w_if_i}{w_i}=f_i. Thus the formula interpolates the data. It is usually more stable than directly evaluating the Lagrange basis.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.65
Problem formulation.
Write the interpolation matrix for radial basis interpolation and discuss conditions for nonsingularity.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.66
Problem formulation.
Explain why Gaussian RBF interpolation becomes ill-conditioned as the shape parameter goes to zero.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.67
Problem formulation.
Explain why polynomial or Fourier approximations of discontinuous functions exhibit Gibbs-type oscillations.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.68
Problem formulation.
Compare global polynomial interpolation with piecewise polynomial interpolation for functions with limited smoothness.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.69
Problem formulation.
Suppose data values are perturbed by |\delta y_j|\le\varepsilon. Show how the Lebesgue constant controls the perturbation in the interpolant.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.70
Problem formulation.
Relate the condition number of polynomial interpolation in the uniform norm to the Lebesgue constant.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Distinguish forward error from backward error; a small residual does not imply a small forward error when the problem is ill-conditioned.
Exercise 3.71
Problem formulation.
State and prove Faber’s theorem: for every fixed triangular array of interpolation nodes, there exists a continuous function for which polynomial interpolation diverges.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.72
Problem formulation.
Explain how logarithmic potential theory describes asymptotically optimal node distributions for polynomial interpolation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.73
Problem formulation.
Derive the leading asymptotic term \Lambda_n\sim \frac{2}{\pi}\log n for Chebyshev-type nodes.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.74
Problem formulation.
Prove Markov’s inequality on [-1,1]: \|p'\|_\infty\le n^2\|p\|_\infty, \qquad p\in\mathbb P_n.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.75
Problem formulation.
Prove Bernstein’s inequality for polynomials on [-1,1]: \sqrt{1-x^2}|p'(x)|\le n\|p\|_\infty.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.76
Problem formulation.
State and prove a Jackson-type theorem relating polynomial approximation error to the modulus of continuity of f.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.77
Problem formulation.
Derive interpolation estimates in Sobolev spaces for piecewise polynomial finite elements.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.78
Problem formulation.
State the Bramble–Hilbert lemma and explain its role in finite element interpolation error estimates.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.79
Problem formulation.
Study total positivity of B-spline collocation matrices and explain its numerical consequences.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.80
Problem formulation.
Develop a spline quasi-interpolation operator and prove an approximation-order estimate.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.81
Problem formulation.
Compare polynomial minimax approximation and rational minimax approximation for functions with nearby singularities.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.82
Problem formulation.
Investigate convergence of diagonal Padé approximants and explain pole-zero defects.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.83
Problem formulation.
Study the AAA algorithm for rational approximation and compare it with classical Padé approximation.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.84
Problem formulation.
Define the native space of a positive definite radial kernel and prove a native-space error estimate.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.85
Problem formulation.
Analyze why tensor-product interpolation suffers from the curse of dimensionality and explain how sparse grids reduce the cost.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.86
Problem formulation.
Compare high-dimensional interpolation by tensor-product grids, sparse grids, and low-rank tensor formats.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.87
Problem formulation.
Design an adaptive interpolation algorithm that detects nonsmoothness and switches between polynomial, spline, and rational local models.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Exercise 3.88
Problem formulation.
Develop an interval-arithmetic method for certifying interpolation error bounds when only interval enclosures of derivatives are available.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Let p_n interpolate f at x_0,\ldots,x_n. Define \omega_{n+1}(x)=\prod_{j=0}^{n}(x-x_j). For x not equal to a node, choose C so that F(t)=f(t)-p_n(t)-C\omega_{n+1}(t) also vanishes at t=x. Then F has n+2 zeros. By repeated Rolle theorem, there exists \xi such that F^{(n+1)}(\xi)=0. Since p_n^{(n+1)}=0 and \omega_{n+1}^{(n+1)}=(n+1)!, we get f^{(n+1)}(\xi)-C(n+1)!=0, so C=\frac{f^{(n+1)}(\xi)}{(n+1)!}. Therefore f(x)-p_n(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j).
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The order claim should be confirmed by a Taylor expansion or a log-log refinement table using a problem with a known exact solution.
Exercise 3.89
Problem formulation.
Analyze stability of barycentric rational interpolation and identify conditions that prevent poles on the interpolation interval.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
The barycentric weights are w_j=\frac{1}{\prod_{m\ne j}(x_j-x_m)}. The barycentric interpolation formula is p_n(x)= \frac{\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}f_j} {\displaystyle\sum_{j=0}^{n}\frac{w_j}{x-x_j}}. If x\to x_i, the terms with j=i dominate both numerator and denominator: p_n(x)\to \frac{w_if_i}{w_i}=f_i. Thus the formula interpolates the data. It is usually more stable than directly evaluating the Lagrange basis.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
Always test the result on the scalar model equation or Fourier mode and verify the amplification factor satisfies the stated stability bound.
Exercise 3.90
Problem formulation.
Study spectral filtering for Chebyshev expansions of nonsmooth functions. Explain how filters reduce Gibbs oscillations and what accuracy is lost.
Method.
Use interpolation identities, divided differences, basis functions, projection formulas, and interpolation-error representations.
Detailed solution and justification.
Use the interpolation condition p(x_j)=f(x_j),\qquad j=0,\ldots,n, and express p in a convenient basis. In the Lagrange basis, p(x)=\sum_{j=0}^{n}f(x_j)\ell_j(x). In the Newton basis, p(x)=f[x_0]+f[x_0,x_1](x-x_0)+\cdots+ f[x_0,\ldots,x_n]\prod_{j=0}^{n-1}(x-x_j). The error is controlled by f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{j=0}^{n}(x-x_j). Chebyshev nodes reduce the maximum size of the nodal product and therefore improve stability.
Conclusion.
The displayed derivation gives the requested formula, proof, or computation. The final expression should be checked against the assumptions and notation of the corresponding chapter.
Diagnostic comment.
The formula should be verified by substitution into the defining equation and, when possible, by a small numerical test.
Interactive tools
The theory and solutions come first. These tools are for review, laboratories, games, memory cards, and randomized assessment.