University Mathematics — Year 3 · Bachelor Year 3

13Hilbert Spaces

A Hilbert space is a Banach space whose norm comes from an inner product — and that single extra structure restores, in infinite dimension, almost all of Euclidean geometry: orthogonal projections exist, every continuous functional is an inner product against a fixed vector (Riesz), and orthonormal bases expand every vector in a convergent series with Pythagorean bookkeeping (Parseval). The chapter’s climax is a debt honored: the trigonometric system is an orthonormal basis of $L^2$ , so Parseval’s identity holds for every square-integrable function — the statement Year 2 could only prove for piecewise $\mathcal C^1$ functions. We end with Lax–Milgram, the workhorse lemma of the variational approach to differential equations.

Throughout, $H$ is a vector space over $K = \R$ or $\C$ .

13.1 Inner products; the projection theorem

Definition 13.1

An inner product is a map $\langle \cdot,\cdot\rangle \colon H\times H \to K$ , linear in the second variable, with $\langle y, x\rangle = \overline{\langle x, y\rangle}$ and $\langle x, x\rangle > 0$ for $x \neq 0$ . It induces the norm $\norm x = \langle x, x\rangle^{1/2}$ , the Cauchy–Schwarz inequality $\abs{\langle x, y\rangle} \leq \norm x\norm y$ (Year 2’s proof — the discriminant — is unchanged), and the parallelogram law

\norm{x + y}^2 + \norm{x - y}^2 = 2\norm x^2 + 2\norm y^2 .

A Hilbert space is an inner-product space complete for this norm. Examples: $\ell^2$ (Problem 8.1) and, the fundamental one, $L^2(\mu)$ with $\langle f, g\rangle = \int\bar fg\,\dd\mu$ — complete by Riesz–Fischer (Theorem 12.4); the inner product is finite by Cauchy–Schwarz ( $=$ Hölder at $p = q = 2$ ).

Theorem 13.2 (Projection onto a closed convex set)

Let $C \neq \varnothing$ be a closed convex subset of the Hilbert space $H$ and $x \in H$ . There is a unique $p_C(x) \in C$ with

\norm{x - p_C(x)} = d(x, C),

characterized by: $\operatorname{Re}\langle x - p_C(x),\ c - p_C(x)\rangle \leq 0$ for all $c \in C$ . The map $p_C$ is $1$ -Lipschitz.

Proof. Let $d = d(x, C)$ and $(c_n) \subseteq C$ with $\norm{x - c_n} \to d$ . Parallelogram on $x - c_n$ and $x - c_m$ :

\norm{c_n - c_m}^2 = 2\norm{x - c_n}^2 + 2\norm{x - c_m}^2 - 4\,\bigl\|x - \tfrac{c_n + c_m}2\bigr\|^2 \leq 2\norm{x{-}c_n}^2 + 2\norm{x{-}c_m}^2 - 4d^2

(convexity puts the midpoint in $C$ ): the right side tends to $0$ , so $(c_n)$ is Cauchy, and its limit $p \in C$ (closed) attains $d$ . Uniqueness: two minimizers give, by the same identity, $\norm{p - p'}^2 \leq 2d^2 + 2d^2 - 4d^2 = 0$ .

Characterization: for $c \in C$ , $t \in \intoc01$ , the vector $p + t(c - p) \in C$ , so

d^2 \leq \norm{x - p - t(c-p)}^2 = d^2 - 2t\operatorname{Re}\langle x - p, c - p\rangle + t^2\norm{c-p}^2 ;

divide by $t \to 0^+$ : $\operatorname{Re}\langle x - p, c - p\rangle \leq 0$ . Conversely this inequality gives $\norm{x - c}^2 = \norm{x - p}^2 - 2\operatorname{Re}\langle x - p, c - p\rangle + \norm{p - c}^2 \geq \norm{x-p}^2$ . Lipschitz: for $x, y$ with projections $p, q$ , add the two variational inequalities (with $c = q$ , resp. $c = p$ ): $\operatorname{Re}\langle x - y - (p - q), p - q\rangle \geq 0$ , so $\norm{p - q}^2 \leq \operatorname{Re}\langle x - y, p - q\rangle \leq \norm{x - y}\norm{p - q}$ . ∎

Theorem 13.3 (Orthogonal decomposition)

Let $F$ be a closed subspace of $H$ . Then $p_F$ is linear, $x - p_F(x) \perp F$ for all $x$ , and

H = F \oplus F^\perp, \qquad F^\perp = \{y : \langle y, f\rangle = 0\ \forall f\in F\}, \qquad (F^\perp)^\perp = F .

For a general subspace, $(F^\perp)^\perp = \bar F$ ; in particular $F$ is dense iff $F^\perp = \{0\}$ .

Proof. For a subspace, the variational characterization with $c = p_F(x) \pm f$ ( $f \in F$ , both signs, and $\iu f$ in the complex case) forces $\langle x - p_F(x), f\rangle = 0$ : the residual is orthogonal to $F$ . Decomposition $x = p_F(x) + (x - p_F(x))$ with $F \cap F^\perp = \{0\}$ ( $\langle y, y \rangle = 0$ ); linearity of $p_F$ follows from uniqueness of such decompositions (both sides linear in them). $(F^\perp) ^\perp \supseteq F$ always; conversely if $x \perp F^\perp$ , write $x = f + g$ : $g = x - f \in F^\perp$ and $\langle g, g\rangle = \langle x, g\rangle - \langle f, g\rangle = 0$ : $x = f \in F$ . For a general subspace $F$ : $F^\perp = \bar F^{\,\perp}$ (continuity of the inner product), so $(F^\perp)^\perp = \bar F$ by the closed case; density iff $\bar F = H$ iff $F^\perp = 0$ . ∎

Theorem 13.4 (Riesz representation)

For every continuous linear functional $\varphi \in H'$ there is a unique $a \in H$ with

\varphi(x) = \langle a, x\rangle \quad (x \in H), \qquad \norm\varphi_{H'} = \norm a .

Proof. If $\varphi = 0$ : $a = 0$ . Otherwise $F = \ker\varphi$ is a closed proper subspace; pick $u \in F^\perp$ , $\norm u = 1$ (Theorem 13.3: $F^\perp \neq 0$ since $F \neq H$ ). For any $x$ , the vector $\varphi(x)u - \varphi(u)x \in \ker\varphi$ , hence $\perp u$ :

0 = \langle u, \varphi(x)u - \varphi(u)x\rangle = \varphi(x) - \varphi(u)\langle u, x\rangle : \qquad \varphi(x) = \langle \overline{\varphi(u)}\,u,\ x\rangle .

So $a = \overline{\varphi(u)}u$ works. Uniqueness: $\langle a - a', x\rangle = 0$ for all $x$ , test $x = a - a'$ . Norms: $\abs{\varphi(x)} \leq \norm a\norm x$ (Cauchy–Schwarz) with equality at $x = a$ . ∎

Example 13.5 (A projection, computed to the end)

In $H = L^2(\intcc01)$ , what is the best approximation of $f(x) = x^2$ by an affine function? The subspace $F = \operatorname{Vect}(1, x)$ is closed (finite-dimensional), and $p_F(f) = a + bx$ is characterized by orthogonality of the residual to $1$ and to $x$ :

\int_0^1(x^2 - a - bx)\,\dd x = 0, \qquad \int_0^1x\,(x^2 - a - bx)\,\dd x = 0,

i.e. $\frac13 = a + \frac b2$ and $\frac14 = \frac a2 + \frac b3$ : $a = -\frac16$ , $b = 1$ . So $p_F(x^2) = x - \frac16$ , and the error is

d(f, F)^2 = \int_0^1\Bigl(x^2 - x + \frac16\Bigr)^2\dd x = \frac1{180}, \qquad d(f, F) = \frac1{6\sqrt5} .

Two remarks worth internalizing. First, the computation is nothing but a $2\times2$ linear system — the normal equations; for the monomial basis their matrix $\bigl(\frac1{i+j+1}\bigr)$ is the notoriously ill-conditioned Hilbert matrix, and orthogonalizing first (Legendre polynomials, Problem 13.1) is the cure. Second, the best uniform approximation of $x^2$ by affine functions is different ( $x - \frac18$ , by equioscillation): each norm has its own geometry, and only the Hilbertian one answers with a linear system.

13.2 Orthonormal bases

Definition 13.6

A family $(e_i)_{i\in I}$ is orthonormal if $\langle e_i, e_j\rangle = \delta_{ij}$ , and a Hilbert basis (orthonormal basis) if moreover its finite linear combinations are dense in $H$ (the family is total). We treat the countable case $I = \N$ , which by Gram–Schmidt covers every separable $H$ (Proposition 13.8).

Theorem 13.7 (Bessel, Parseval)

Let $(e_n)_{n\in\N}$ be orthonormal in $H$ , and $c_n(x) = \langle e_n, x\rangle$ .

(Bessel) $\sum_n\abs{c_n(x)}^2 \leq \norm x^2$ , and the series $\sum_nc_n(x)e_n$ converges in $H$ , with sum $p_F(x)$ , $F = \overline{\operatorname{Vect}}(e_n)$ .
The following are equivalent: (i) $(e_n)$ is a Hilbert basis; (ii) $x = \sum_nc_n(x)e_n$ for every $x$ ; (iii) Parseval: $\norm x^2 = \sum_n\abs{c_n(x)}^2$ for every $x$ ; (iv) the only vector orthogonal to all $e_n$ is $0$ .
If $(e_n)$ is a Hilbert basis, $x \mapsto (c_n(x))_n$ is an isometric isomorphism $H \to \ell^2$ (every infinite-dimensional separable Hilbert space “is” $\ell^2$ ), and $\langle x, y\rangle = \sum_n\overline{c_n(x)}c_n(y)$ .

Proof. (1) For finite $N$ : $x - \sum_{n\leq N}c_ne_n \perp e_k$ ( $k \leq N$ ), so Pythagoras gives $\norm x^2 = \sum_{n\leq N}\abs{c_n}^2 + \norm{x - \sum_{n\leq N}c_ne_n}^2$ : Bessel. The partial sums $S_N = \sum_{n\leq N}c_ne_n$ are Cauchy: $\norm{S_N - S_M}^2 = \sum_{M<n\leq N}\abs{c_n}^2$ , tail of a convergent series; the limit lies in $F$ , and $x - \lim S_N \perp$ each $e_k$ (continuity), hence $\perp F$ : by uniqueness of the orthogonal decomposition, $\lim S_N = p_F(x)$ .

(2) (i) $\Rightarrow$ (ii): $F = H$ , so $p_F = \mathrm{id}$ . (ii) $\Rightarrow$ (iii): Pythagoras in the limit ( $\norm{S_N}^2 = \sum_{n \leq N}\abs{c_n}^2 \to \norm x^2$ ). (iii) $\Rightarrow$ (iv): $x \perp$ all $e_n$ gives $\norm x^2 = 0$ . (iv) $\Rightarrow$ (i): $F^\perp = \{0\}$ (orthogonality to all $e_n$ is orthogonality to $F$ ), so $F$ is dense by Theorem 13.3; but $F$ , a closure, is already closed: $F = H$ .

(3) The map is linear, isometric by (iii) (hence injective), and surjective: given $(c_n) \in \ell^2$ , the series $\sum c_ne_n$ converges (Cauchy as in (1)) to a preimage. The inner product formula is polarization from (iii), or a direct limit computation. ∎

Proposition 13.8 (Gram–Schmidt)

Let $(x_n)$ be a linearly independent sequence. Setting inductively $\tilde e_n = x_n - \sum_{k<n}\langle e_k, x_n\rangle e_k$ and $e_n = \tilde e_n/\norm{\tilde e_n}$ produces an orthonormal $(e_n)$ with the same finite spans: $\operatorname{Vect}(e_1, \dots, e_n) = \operatorname{Vect} (x_1, \dots, x_n)$ . Consequently every separable Hilbert space (one with a countable dense subset) has a Hilbert basis.

Proof. Induction: $\tilde e_n \perp e_k$ ( $k < n$ ) by construction, and $\tilde e_n \neq 0$ by independence; the spans match at each stage (triangular change of basis). For a separable $H$ : from a dense sequence extract a linearly independent subfamily with dense span (discard each vector in the span of its predecessors — the span is unchanged), orthonormalize: the result is total. ∎

Theorem 13.9 (The trigonometric system; Parseval at last)

In $L^2(\intcc{-\pi}\pi)$ with $\langle f, g\rangle = \frac1{2\pi}\int_{-\pi}^\pi \bar fg$ , the family $e_n(t) = \eu^{\iu nt}$ , $n \in \Z$ , is a Hilbert basis. Consequently, for every $f \in L^2$ — in particular every piecewise continuous $2\pi$ -periodic $f$ — with $c_n(f) = \frac1{2\pi}\int_{-\pi}^{\pi}f(t)\eu^{-\iu nt}\dd t$ :

f = \sum_{n\in\Z}c_n(f)\,\eu^{\iu nt} \ \ \text{in } L^2, \qquad \frac1{2\pi}\int_{-\pi}^{\pi}\abs f^2 = \sum_{n\in\Z}\abs{c_n(f)}^2 .

This proves, in full generality, the Parseval identity that Year 2 admitted.

Proof. Orthonormality is a direct computation (Year 2). Totality: let $f \in L^2$ be $\perp$ all $e_n$ , i.e. all Fourier coefficients vanish. Continuous $2\pi$ -periodic functions are dense in $L^2(\intcc{-\pi}\pi)$ : indeed $\mathcal C_c(\intoo{-\pi}\pi)$ is dense (Theorem 12.6(2)) and such functions extend periodically and continuously. Trigonometric polynomials are $\norm\cdot_\infty$ -dense among continuous periodic functions (Stone–Weierstrass, Corollary 7.16(c)), and $\norm\cdot_2 \leq \norm\cdot_\infty$ : trigonometric polynomials are dense in $L^2$ . But $f \perp$ every trigonometric polynomial, hence $f \perp$ a dense subspace: $f \in (\text{dense})^\perp = \{0\}$ (Theorem 13.3). Criterion (iv) of Theorem 13.7 concludes; (ii) and (iii) unpack to the display (reindexing the countable $\Z$ ; the double-ended series converges unconditionally — the partial sums over any exhausting family converge, by the $\ell^2$ tail argument). ∎

Theorem 13.10 (Lax–Milgram)

Let $H$ be a real Hilbert space and $a \colon H\times H \to \R$ bilinear, continuous ( $\abs{a(u,v)} \leq M\norm u\norm v$ ) and coercive ( $a(u, u) \geq \alpha\norm u^2$ , $\alpha > 0$ ). Then for every $\varphi \in H'$ there is a unique $u \in H$ with

a(u, v) = \varphi(v) \qquad \text{for all } v \in H .

Proof. For fixed $u$ , $v \mapsto a(u, v)$ is continuous linear: Riesz gives a unique $Au \in H$ with $a(u,v) = \langle Au, v\rangle$ ; $A$ is linear with $\norm{Au} \leq M\norm u$ (uniqueness of representatives, then bound). Coercivity: $\alpha\norm u^2 \leq a(u,u) = \langle Au, u\rangle \leq \norm{Au}\norm u$ , so $\norm{Au} \geq \alpha\norm u$ : $A$ is injective with closed range (a Cauchy image sequence $Au_n$ forces $u_n$ Cauchy). The range is dense: $w \perp \operatorname{im}A$ gives $0 = \langle Aw, w\rangle \geq \alpha\norm w^2$ . Closed and dense: $A$ is bijective. Given $\varphi$ , let $f$ represent it (Riesz) and $u = A^{-1}f$ : $a(u, v) = \langle f, v\rangle = \varphi(v)$ , uniquely ( $a(u - u', \cdot) = 0$ and coercivity). ∎

Remark 13.11

When $a$ is symmetric, Lax–Milgram’s solution is the unique minimizer of the energy $J(v) = \frac12a(v,v) - \varphi(v)$ (Exercise 13.9): existence of solutions to variational problems in one stroke. Applied to suitable function spaces (the Sobolev spaces of a later course), this solves boundary value problems for differential equations — the modern entry point to partial differential equations.

13.3 Exercises

Exercise 13.1 ★

(a) Prove the polarization identities (real: $4\langle x, y\rangle = \norm{x+y}^2 - \norm{x-y}^2$ ; complex: the four-term version). (b) Show that $\norm\cdot_1$ on $L^1(\intcc01)$ and $\norm\cdot_\infty$ on $\mathcal C(\intcc01)$ violate the parallelogram law: these norms come from no inner product.

Solution

Solution of Exercise 13.1.

(a) Real: expand $\norm{x \pm y}^2 = \norm x^2 \pm 2\langle x,y\rangle + \norm y^2$ and subtract. Complex (inner product linear in the second slot): expanding as above,

\langle x, y\rangle = \frac14\sum_{k=0}^{3} \iu^k\,\bigl\|\iu^kx + y\bigr\|^2,

each term contributing $\iu^k\cdot2\operatorname{Re}\bigl( (-\iu)^k\langle x,y\rangle\bigr)$ , whose sum is $4\langle x,y\rangle$ (check the four values of $k$ ; the $\sum\iu^k (\norm x^2 + \norm y^2) = 0$ ).

(b) $L^1$ : $f = \mathbf 1_{\intcc0{1/2}}$ , $g = \mathbf 1_{\intcc{1/2}1}$ : $\norm{f\pm g}_1^2 = 1$ each, sum $2$ ; $2\norm f_1^2 + 2\norm g_1^2 = 1 \neq 2$ . Sup norm: $f = \mathbf 1$ , $g(t) = t$ on $\intcc01$ : $\norm{f + g}_\infty^2 + \norm{f-g}_\infty^2 = 4 + 1 = 5 \neq 4 = 2 + 2$ . Failing the parallelogram law, these norms are induced by no inner product (which would force it by direct expansion).

Exercise 13.2 ★

In $H = L^2(\intcc01)$ (real): (a) compute the projection of $f$ onto the subspace of constant functions, and interpret; (b) compute the projection onto $\{g : g = 0 \text{ a.e.\ on } \intcc0{1/2}\}$ ; (c) compute $d\bigl(x \mapsto x,\ \operatorname{Vect}(\mathbf 1)\bigr)$ .

Solution

Solution of Exercise 13.2.

(a) $p(f) = \bigl(\int_0^1f\bigr)\mathbf 1$ : indeed $f - \int f \perp$ constants ( $\int(f - \int f)c = 0$ ). The best constant approximation of $f$ in mean square is its average — the first instance of conditional expectation (Chapter 22).

(b) $p(f) = f\,\mathbf 1_{\intcc{1/2}1}$ : the difference $f\mathbf 1_{\intcc0{1/2}}$ is orthogonal to every $g$ vanishing on $\intcc0{1/2}$ .

Exercise 13.3 ★★

(a) Show that for a subspace $F$ : $F$ dense $\iff$ $F^\perp = \{0\}$ , and give an example in $\ell^2$ of a proper dense subspace (so $F^\perp = 0$ without $F = H$ : the decomposition theorem genuinely needs $F$ closed). (b) Show that if $x_n \to x$ and $y_n \to y$ in norm, then $\langle x_n, y_n\rangle \to \langle x, y\rangle$ , and locate two places where the chapter used this continuity.

Solution

Solution of Exercise 13.3.

(a) The equivalence is Theorem 13.3 ( $\bar F = (F^\perp)^\perp$ , and $\bar F = H \iff F^\perp = \{0\}$ ). Example: the space $F$ of finite sequences is dense in $\ell^2$ (truncation) and proper: $F^\perp = \{0\}$ yet $F \neq \ell^2$ — for a non-closed subspace, $H = F \oplus F^\perp$ fails blatantly ( $F \oplus \{0\} \neq H$ ).

(b) $\abs{\langle x_n, y_n\rangle - \langle x, y\rangle} \leq \abs{\langle x_n - x, y_n\rangle} + \abs{\langle x, y_n - y\rangle} \leq \norm{x_n - x}\sup_n\norm{y_n} + \norm x\,\norm{y_n - y} \to 0$ (convergent sequences are bounded). Used: in Theorem 13.7(1) to see $x - \lim S_N \perp e_k$ , and in Theorem 13.3 to see $F^\perp = \bar F^{\,\perp}$ .

Exercise 13.4 ★★

Apply Gram–Schmidt to $1, x, x^2$ in $L^2(\intcc{-1}1)$ (Lebesgue measure): obtain the first three normalized Legendre polynomials, and verify they match $\sqrt{n + \frac12}\,P_n$ for the Rodrigues polynomials $P_n$ of Problem 13.1.

Solution

Solution of Exercise 13.4.

$e_0 = \frac1{\sqrt2}$ . Next, $x \perp \mathbf 1$ already ( $\int_{-1}^1x = 0$ ), and $\int_{-1}^1x^2 = \frac23$ : $e_1 = \sqrt{\tfrac32}\,x$ . Then $x^2 - \langle e_0, x^2\rangle e_0 = x^2 - \frac13$ (and $\perp e_1$ by parity), with

\int_{-1}^1\Bigl(x^2 - \frac13\Bigr)^2\dd x = \frac25 - \frac49 + \frac29 = \frac{8}{45}: \qquad e_2 = \sqrt{\tfrac{45}8}\,\Bigl(x^2 - \frac13\Bigr).

Comparison: $P_0 = 1$ , $P_1 = x$ , $P_2 = \frac{3x^2 - 1}2$ , and $\sqrt{n + \tfrac12}\,P_n$ gives $\frac1{\sqrt2}$ , $\sqrt{\frac32}x$ , $\sqrt{\frac52}\,\frac{3x^2-1}2 = \sqrt{\frac{45}8}\bigl(x^2 - \frac13\bigr)$ : exactly $e_0, e_1, e_2$ .

Exercise 13.5 ★★

Apply Parseval (Theorem 13.9) to $f(t) = t$ and $f(t) = t^2$ on $\intcc{-\pi}\pi$ — now legitimately for these (continuous, but previously the identity needed piecewise- $\mathcal C^1$ care at the wrap-around discontinuity): recover

\sum_{n\geq1}\frac1{n^2} = \frac{\pi^2}6, \qquad \sum_{n\geq1}\frac1{n^4} = \frac{\pi^4}{90} .

Solution

Solution of Exercise 13.5.

For $f(t) = t$ : $c_0 = 0$ and, integrating by parts, $c_n = \frac{\iu(-1)^n}{n}$ for $n \neq 0$ : $\abs{c_n}^2 = \frac1{n^2}$ . Parseval:

\frac1{2\pi}\int_{-\pi}^\pi t^2\dd t = \frac{\pi^2}3 = \sum_{n\neq0}\frac1{n^2} = 2\sum_{n\geq1}\frac1{n^2} \ \Longrightarrow\ \sum_{n\geq1}\frac1{n^2} = \frac{\pi^2}6 .

For $f(t) = t^2$ : $c_0 = \frac{\pi^2}3$ , $c_n = \frac{2(-1)^n}{n^2}$ ( $n \ne 0$ ). Parseval:

\frac1{2\pi}\int_{-\pi}^{\pi}t^4\dd t = \frac{\pi^4}5 = \frac{\pi^4}9 + \sum_{n\neq0}\frac4{n^4} \ \Longrightarrow\ \sum_{n\geq1}\frac1{n^4} = \frac18\Bigl(\frac{\pi^4}5 - \frac{\pi^4}9\Bigr) = \frac{\pi^4}{90} .

No piecewise- $\mathcal C^1$ caveats are needed: Theorem 13.9 covers every $L^2$ function.

Exercise 13.6 ★★

(a) Find $a \in L^2(\intcc01)$ with $\int_0^{1/2}f = \langle a, f\rangle$ for all $f$ ; compute $\norm\varphi$ for this functional. (b) Show that the evaluation $f \mapsto f(\frac12)$ , defined on the subspace $\mathcal C(\intcc01) \subseteq L^2(\intcc01)$ , is not continuous for $\norm\cdot_2$ : no Riesz representative exists (evaluation is not an $L^2$ notion).

Solution

Solution of Exercise 13.6.

(a) $\varphi(f) = \int_0^{1/2}f = \langle\mathbf 1_{\intcc0{1/2}},\ f\rangle$ : the representative is $a = \mathbf 1_{\intcc0{1/2}}$ , and $\norm\varphi = \norm a_2 = \frac1{\sqrt2}$ (Theorem 13.4).

(b) Take the tent functions $f_n$ with peak $1$ at $\frac12$ and support of width $\frac2n$ : $f_n(\tfrac12) = 1$ while $\norm{f_n}_2^2 \leq \frac2n \to 0$ : no constant $C$ can give $\abs{f(\frac12)} \leq C\norm f_2$ . Point evaluation is meaningless in $L^2$ — elements are classes modulo null sets — and this computation is the quantitative reason.

Exercise 13.7 ★★★

Let $H$ be separable with Hilbert basis $(e_n)$ , and $(x_k)$ a bounded sequence. (a) Show that some subsequence converges weakly: there is $x$ with $\langle y, x_{k_j}\rangle \to \langle y, x\rangle$ for every $y \in H$ . (Diagonal extraction on the coefficients $\langle e_n, x_k\rangle$ ; assemble $x$ via Bessel and uniform boundedness of norms.) (b) Show $e_n \rightharpoonup 0$ but $\norm{e_n} = 1$ : weak limits can lose norm. Show $\norm x \leq \liminf\norm{x_{k_j}}$ in (a).

Solution

Solution of Exercise 13.7.

(a) Let $M = \sup_k\norm{x_k}$ . The scalar sequences $(\langle e_n, x_k\rangle)_k$ are bounded by $M$ : a diagonal extraction yields $x_{k_j}$ with $\langle e_n, x_{k_j}\rangle \to \gamma_n$ for every $n$ . For each $N$ : $\sum_{n\leq N}\abs{\gamma_n}^2 = \lim_j\sum_{n\leq N}\abs{\langle e_n, x_{k_j}\rangle}^2 \leq M^2$ (Bessel), so $(\gamma_n) \in \ell^2$ and $x = \sum_n\gamma_ne_n \in H$ (Theorem 13.7(3)). For $y \in H$ :

\abs{\langle y, x_{k_j} - x\rangle} \leq \Bigl|\sum_{n\leq N}\overline{c_n(y)}\bigl(\langle e_n, x_{k_j}\rangle - \gamma_n\bigr)\Bigr| + 2M\Bigl(\sum_{n>N}\abs{c_n(y)}^2\Bigr)^{1/2},

using the expansion $\langle y, z\rangle = \sum\overline{c_n(y)}c_n(z)$ and Cauchy–Schwarz on the tail; choose $N$ then $j$ : weak convergence to $x$ .

(b) $\langle y, e_n\rangle = c_n(y) \to 0$ for every $y$ ( $\ell^2$ tails): $e_n \rightharpoonup 0$ , yet $\norm{e_n} = 1$ : the norm is not weakly continuous. In (a): $\norm x^2 = \sum\abs{\gamma_n}^2 \leq \liminf_j\norm{x_{k_j}}^2$ (finite sections and Bessel again): weak limits can only lose norm.

Exercise 13.8 ★★

(Adjoints) For $T \in \mathcal L(H)$ , show there is a unique $T^* \in \mathcal L(H)$ with $\langle Tx, y\rangle = \langle x, T^*y\rangle$ (Riesz), and $\vertiii{T^*} = \vertiii T$ . Compute the adjoint of the shift $S$ on $\ell^2$ , and prove $\ker T^* = (\operatorname{im}T)^\perp$ — deduce $\overline{\operatorname{im}T} = (\ker T^*)^\perp$ .

Solution

Solution of Exercise 13.8.

For fixed $y$ , $x \mapsto \langle y, Tx\rangle$ is a continuous linear functional; Riesz gives a unique $T^*y$ with $\langle y, Tx\rangle = \langle T^*y, x\rangle$ for all $x$ — conjugating, $\langle Tx, y\rangle = \langle x, T^*y\rangle$ . Uniqueness makes $T^*$ linear;

\norm{T^*y} = \sup_{\norm x = 1}\abs{\langle T^*y, x\rangle} = \sup_{\norm x=1}\abs{\langle y, Tx\rangle} \leq \vertiii T\,\norm y,

so $\vertiii{T^*} \leq \vertiii T$ , and $T^{**} = T$ gives equality. Shift: $\langle Sx, y\rangle = \sum_{n\geq1} x_n\bar y_{n+1} = \langle x, S^*y\rangle$ with $(S^*y)_n = y_{n+1}$ : the backward shift. Kernel–image: $T^*y = 0$ iff $\langle x, T^*y\rangle = 0$ for all $x$ iff $\langle Tx, y\rangle = 0$ for all $x$ iff $y \perp \operatorname{im}T$ : $\ker T^* = (\operatorname{im}T)^\perp$ ; taking $\perp$ and using Theorem 13.3, $\overline{\operatorname{im}T} = (\ker T^*)^\perp$ .

Exercise 13.9 ★★

Let $a$ be as in Lax–Milgram and moreover symmetric. Show that $u$ solves $a(u, \cdot) = \varphi$ iff $u$ minimizes $J(v) = \frac12a(v, v) - \varphi(v)$ , and that the minimum is attained at exactly one point. (Complete the square: $J(u + w) - J(u) = \frac12a(w,w) \geq \frac\alpha2\norm w^2$ .) Application: re-derive the projection theorem for closed subspaces from Lax–Milgram.

Solution

Solution of Exercise 13.9.

If $a(u, \cdot) = \varphi$ : for any $w$ ,

J(u + w) - J(u) = a(u, w) - \varphi(w) + \tfrac12a(w,w) = \tfrac12a(w,w) \geq \tfrac\alpha2\norm w^2,

strictly positive for $w \neq 0$ : $u$ is the unique minimizer. Conversely, at a minimizer the function $t \mapsto J(u + tw)$ (a quadratic polynomial in $t$ ) has vanishing derivative at $0$ : $a(u, w) - \varphi(w) = 0$ for every $w$ . Projection re-derived: for a closed subspace $F$ , apply Lax–Milgram on the Hilbert space $F$ with $a(u,v) = \langle u, v\rangle$ ( $M = \alpha = 1$ ) and $\varphi(v) = \langle x, v\rangle$ : a unique $p \in F$ with $\langle p, v\rangle = \langle x, v\rangle$ for all $v \in F$ , i.e. $x - p \perp F$ — and by the symmetric case, $p$ minimizes $\frac12\norm v^2 - \langle x, v\rangle = \frac12\norm{v - x}^2 - \frac12\norm x^2$ over $F$ : the projection.

Exercise 13.10 ★★★

(The Haar system) On $\intcc01$ , let $h_{0} = \mathbf 1$ , and for $n = 2^j + k$ ( $j \geq 0$ , $0 \leq k < 2^j$ ):

h_n = 2^{j/2}\Bigl(\mathbf 1_{[k2^{-j},\,(k + \frac12)2^{-j})} - \mathbf 1_{[(k+\frac12)2^{-j},\,(k+1)2^{-j})} \Bigr).

Show that $(h_n)_{n\geq0}$ is orthonormal in $L^2(\intcc01)$ , and total. (Orthogonality: disjoint or nested supports; totality: finite spans contain all dyadic step functions, which are dense — via Theorem 12.6(1) and dyadic approximation of intervals.) The Haar system is the ancestor of wavelets.

Solution

Solution of Exercise 13.10.

Normalization: $\int h_n^2 = 2^j\cdot 2^{-j} = 1$ . Orthogonality: two distinct Haar functions have either disjoint (interiors of) supports (product zero a.e.), or the support of the finer is contained in a half-interval where the coarser is constant — then the integral of the product is that constant times $\int h_{\text{finer}} = 0$ ; against $h_0 = \mathbf 1$ , again $\int h_n = 0$ . Totality: the span of $\{h_0, \dots, h_{2^J-1}\}$ consists of step functions on the dyadic grid of step $2^{-J}$ ; both spaces have dimension $2^J$ and the Haar functions are independent (orthonormal): the span is all such step functions. Dyadic step functions are dense in $L^2(\intcc01)$ : simple functions are dense (Theorem 12.6(1)), measurable sets are approximated by finite unions of intervals (Exercise 9.7), and intervals by dyadic ones (endpoints move by $\leq 2^{-J}$ ). By Theorem 13.7, the Haar system is a Hilbert basis.

Exercise 13.11 ★★

(Orthogonal projections, characterized) Let $H$ be a Hilbert space and $P \in \mathcal L(H)$ with $P^2 = P$ , $P \neq 0$ . Show the equivalence of: (i) $P$ is the orthogonal projection onto $\operatorname{im}P$ ; (ii) $P = P^*$ (Exercise 13.8); (iii) $\vertiii P = 1$ . (For (iii) $\Rightarrow$ (i): if some $x \in (\ker P)^\perp$ had $Px \neq x$ , consider $x + t(Px - x)$ — or directly: for $u \in \operatorname{im}P$ and $v \in \ker P$ , expand $\norm{P(u + tv)}^2 \leq \norm{u + tv}^2$ for all $t \in \R$ and conclude $\langle u, v\rangle = 0$ .) Exhibit a non-orthogonal projection on $\R^2$ and compute its norm.

Solution

Solution of Exercise 13.11.

(i) $\Rightarrow$ (ii): for the orthogonal projection, $\langle Px, y\rangle = \langle Px, Py\rangle = \langle x, Py\rangle$ (insert the decompositions $x = Px + (x - Px)$ etc. and kill cross terms). (ii) $\Rightarrow$ (iii): $\norm{Px}^2 = \langle P^2x, x\rangle = \langle Px, x\rangle \leq \norm{Px}\norm x$ , so $\vertiii P \leq 1$ , and $Pu = u$ on the nonzero image: $= 1$ . (iii) $\Rightarrow$ (i): $H = \operatorname{im}P \oplus \ker P$ (algebraically, from $P^2 = P$ ); take $u = Pu \in \operatorname{im}P$ , $v \in \ker P$ , $t \in \R$ : $\norm{P(u + tv)}^2 = \norm u^2$ must be $\leq \norm{u + tv}^2 = \norm u^2 + 2t\operatorname{Re}\langle u, v\rangle + t^2\norm v^2$ for every $t$ , forcing $\operatorname{Re}\langle u, v\rangle = 0$ (compare the linear terms as $t \to 0^\pm$ ); replacing $v$ by $\iu v$ kills the imaginary part too: $\operatorname{im}P \perp \ker P$ , which is exactly orthogonality of the projection. Example: $P(x, y) = (x + y, 0)$ on $\R^2$ : $P^2 = P$ , image the $x$ -axis, kernel the line $y = -x$ , and $\vertiii P = \sup\frac{\abs{x+y}}{\norm{(x,y)}} = \sqrt2$ (attained at $(1,1)/\sqrt2$ ): an oblique projection has norm $> 1$ . (For the record, (ii) also gives (i) directly: $\ker P = \ker P^* = (\operatorname{im}P)^\perp$ by Exercise 13.8.)

Exercise 13.12 ★★★

(Von Neumann’s ergodic theorem) Let $U \in \mathcal L(H)$ be unitary ( $U^*U = UU^* = I$ ), $F = \ker(U - I)$ the fixed space, $P$ the orthogonal projection onto $F$ , and $A_n = \frac1n\sum_{k=0}^{n-1}U^k$ . (a) Show $\ker(U - I) = \ker(U^* - I)$ (from $\norm{Ux - x}^2 = 2\norm x^2 - 2\operatorname{Re}\langle Ux, x\rangle$ and unitarity), and deduce $\overline{\operatorname{im}(U - I)} = F^\perp$ . (b) Show that $A_nx \to x$ for $x \in F$ , and $A_nx \to 0$ for $x \in \operatorname{im}(U - I)$ (telescoping), then for $x \in \overline{\operatorname{im}(U - I)}$ (uniform bound $\vertiii{A_n} \leq 1$ ). (c) Conclude: $A_nx \to Px$ for every $x \in H$ — time averages converge to the projection on the invariants. (d) Spell it out for $H = L^2(\R/\Z)$ and $Uf = f(\cdot + \alpha)$ with $\alpha$ irrational: identify $F$ (use Fourier series, Theorem 13.9) and deduce that $\frac1n\sum_{k<n}f(x + k\alpha) \to \int_0^1f$ in $L^2$ : the $L^2$ equidistribution of irrational rotations.

Solution

Solution of Exercise 13.12.

(a) For unitary $U$ : $\norm{Ux - x}^2 = 2\norm x^2 - 2\operatorname{Re}\langle Ux, x\rangle$ and $\norm{U^*x - x}^2 = 2\norm x^2 - 2\operatorname{Re}\langle x, Ux\rangle$ : the two vanish together, so $\ker(U - I) = \ker(U^* - I)$ . Then, using $\ker T^* = (\operatorname{im}T)^\perp$ (Exercise 13.8) with $T = U - I$ and $T^* = U^* - I$ :

\overline{\operatorname{im}(U - I)} = \bigl(\ker(U^* - I)\bigr)^\perp = F^\perp .

(b) On $F$ : $U^kx = x$ , so $A_nx = x$ . For $x = (U - I)y$ : $A_nx = \frac1n(U^ny - y)$ , of norm $\leq \frac2n\norm y \to 0$ . For $x$ in the closure: given $\varepsilon$ , pick $x' = (U - I)y$ with $\norm{x - x'} < \varepsilon$ ; since $\vertiii{A_n} \leq \frac1n\sum\vertiii{U^k} = 1$ , $\norm{A_nx} \leq \norm{A_n(x - x')} + \norm{A_nx'} \leq \varepsilon + o(1)$ .

(c) Decompose $x = Px + (x - Px)$ with $Px \in F$ and $x - Px \in F^\perp = \overline{\operatorname{im}(U - I)}$ (part (a)): $A_nx = Px + A_n(x - Px) \to Px + 0$ .

(d) In the Fourier basis $e_m(x) = \eu^{2\iu\pi mx}$ : $Ue_m = \eu^{2\iu\pi m\alpha}e_m$ , so $Ue_m = e_m$ iff $m\alpha \in \Z$ iff $m = 0$ ( $\alpha$ irrational): $F = \C\mathbf 1$ and $Pf = \langle\mathbf 1, f\rangle\mathbf 1 = \int_0^1f$ . The theorem reads $\frac1n\sum_{k<n}f(\cdot + k\alpha) \to \int_0^1f$ in $L^2(\R/\Z)$ : the orbit averages of an irrational rotation equidistribute — the $L^2$ shadow of Weyl’s equidistribution theorem, obtained by pure Hilbert geometry.

13.4 Problem: orthogonal polynomials

Problem 13.1

Weekend problem — Legendre, Hermite, and Gauss quadrature

Let $I \subseteq \R$ be an interval and $w > 0$ a continuous weight on the interior of $I$ such that $\int_I \abs t^nw(t)\dd t < \infty$ for all $n$ ; work in $H = L^2(I, w\,\dd\lambda)$ with $\langle f, g\rangle = \int_I \bar fg\,w$ . Gram–Schmidt applied to $1, t, t^2, \dots$ produces the orthogonal polynomials $(p_n)$ for $w$ (monic normalization: $p_n = t^n + \cdots$ ).

Part I — General theory.

Show that $p_n$ is orthogonal to every polynomial of degree $< n$ , and that $(p_0, \dots, p_n)$ is a basis of $\R_n[t]$ .
(Three-term recurrence) Show there are reals $a_n, b_n$ with

$p_{n+1}(t) = (t - a_n)\,p_n(t) - b_n\,p_{n-1}(t), \qquad b_n = \frac{\norm{p_n}^2}{\norm{p_{n-1}}^2} > 0 .$

(Expand $t\,p_n$ in the basis $(p_k)_{k \leq n+1}$ and kill coefficients by orthogonality, using $\langle tp_n, p_k\rangle = \langle p_n, tp_k\rangle$ .)
(Roots) Show that $p_n$ has $n$ distinct roots, all interior to $I$ . (Let $t_1 < \dots < t_m$ be the interior sign changes of $p_n$ ; if $m < n$ , test $p_n$ against $\prod_{i\leq m}(t - t_i)$ and contradict orthogonality.)

Part II — Legendre ( $I = \intcc{-1}1$ , $w = 1$ ). Define $P_n(t) = \frac{1}{2^nn!}\,\frac{\dd^n}{\dd t^n}\bigl[(t^2 - 1)^n\bigr]$ (Rodrigues).

Show $\deg P_n = n$ with leading coefficient $\frac{(2n)!}{2^n(n!)^2}$ , and, integrating by parts $n$ times, that $\langle P_n, Q\rangle = 0$ for every polynomial $Q$ of degree $< n$ : the $P_n$ are (up to normalization) the orthogonal polynomials for $w = 1$ .
Compute $\norm{P_n}_2^2 = \frac{2}{2n+1}$ (integrate by parts $n$ times against itself and reduce to a Beta/Wallis integral, Exercise 11.8).
Show that the normalized Legendre polynomials form a Hilbert basis of $L^2(\intcc{-1}1)$ (Weierstrass, Corollary 7.16, plus density of $\mathcal C$ in $L^2$ ), and expand $f(t) = \abs t$ up to degree $2$ : compute the best quadratic $L^2$ -approximation of $\abs t$ .

Part III — Hermite ( $I = \R$ , $w(t) = \eu^{-t^2}$ ). Define $H_n(t) = (-1)^n\eu^{t^2}\frac{\dd^n}{\dd t^n}\eu^{-t^2}$ .

Show that $H_n$ is a polynomial of degree $n$ with leading coefficient $2^n$ , that $H_{n+1} = 2tH_n - H_n'$ , and that $\langle H_m, H_n\rangle_w = \delta_{mn}\,2^nn!\sqrt\pi$ (parts again).
Show that the Hermite family is total in $L^2(\R, \eu^{-t^2}\dd t)$ , admitting one result from Chapter 14: if $g \in L^1(\R)$ has $\int g(t)\eu^{-\iu\xi t}\dd t = 0$ for all $\xi$ , then $g = 0$ a.e. (For $f \perp$ all $H_n$ , i.e. $\perp$ all polynomials: show $z \mapsto \int f(t)\eu^{-t^2}\eu^{-\iu zt}\dd t$ is well defined, expand the exponential as a series, justify the interchange by domination, and conclude that the Fourier transform of $f\eu^{-t^2}$ vanishes.)

Part IV — Gauss quadrature. Fix $n$ , let $t_1 < \dots < t_n$ be the roots of $p_n$ (Part I), and define the weights $w_i = \int_I \ell_i(t)\,w(t)\dd t$ where $\ell_i$ are the Lagrange interpolation basis polynomials at the $t_i$ .

Show that the quadrature rule $Q(f) = \sum_iw_if(t_i)$ is exact on all polynomials of degree $\leq n - 1$ (interpolation), and in fact — the miracle — on all polynomials of degree $\leq 2n - 1$ : write $P = qp_n + r$ and use orthogonality on the quotient $q$ .
Show that the weights are positive (apply the rule to $\ell_i^2$ , of degree $2n - 2$ ), and deduce from Polya’s theorem (Exercise 8.9) that Gauss quadrature converges: $Q_n(f) \to \int_I fw$ for every continuous $f$ on a compact $I$ .
For $n = 2$ , $I = \intcc{-1}1$ , $w = 1$ : compute the nodes $\pm\frac1{\sqrt3}$ and weights $1, 1$ , and verify exactness on $1, t, t^2, t^3$ by hand. Compare with the trapezoid rule on the same two evaluation points.

Part V — Chebyshev: the polynomials that oscillate best. Now $I = \intcc{-1}1$ and $w(t) = \frac1{\sqrt{1 - t^2}}$ .

Show that $T_n(\cos\theta) = \cos n\theta$ defines a polynomial $T_n$ of degree $n$ (establish $T_{n+1} = 2t\,T_n - T_{n-1}$ from a trigonometric identity), with leading coefficient $2^{n-1}$ for $n \geq 1$ ; and that the substitution $t = \cos\theta$ gives

$\langle T_m, T_n\rangle_w = \int_0^\pi\cos m\theta\,\cos n\theta\,\dd\theta = 0 \ (m \neq n), \qquad \norm{T_0}_w^2 = \pi,\ \ \norm{T_n}_w^2 = \frac\pi2 :$

the $T_n$ are the orthogonal polynomials for this weight, and Chebyshev expansions are Fourier cosine series in disguise.
Locate explicitly the $n$ roots $t_k = \cos\frac{(2k-1)\pi}{2n}$ and the $n + 1$ extrema $s_j = \cos\frac{j\pi}n$ of $T_n$ on $\intcc{-1}1$ , where $T_n(s_j) = (-1)^j$ : the graph equioscillates between $\pm1$ .
(Minimax) Show that among all monic polynomials of degree $n$ , the polynomial $2^{1-n}T_n$ has the smallest sup-norm on $\intcc{-1}1$ , namely $2^{1-n}$ — and it is the unique minimizer. (If a monic $P$ had $\sup\abs P < 2^{1-n}$ , the difference $2^{1-n}T_n - P$ , of degree $\leq n-1$ , would alternate in sign at the $n+1$ equioscillation points.)
Application to interpolation: for nodes $t_1 < \dots < t_n$ in $\intcc{-1}1$ , the error of Lagrange interpolation of a $\mathcal C^n$ function involves $\omega(t) = \prod_i(t - t_i)$ . Show that choosing Chebyshev roots as nodes minimizes $\sup_{\intcc{-1}1}\abs\omega$ , and give the resulting bound $\norm{f - L_nf}_\infty \leq \frac{\norm{f^{(n)}}_\infty} {2^{n-1}\,n!}$ — compare with equally spaced nodes (state Runge’s phenomenon as the cautionary tale).
Verify $\abs{T_n'(\pm1)} = n^2$ (differentiate $T_n(\cos\theta) = \cos n\theta$ and take limits $\theta \to 0, \pi$ ): polynomials bounded by $1$ on $\intcc{-1}1$ can have derivative as large as $n^2$ at the edge (Markov’s inequality says no larger — statement only). Where in the interval is the derivative bound only $O(n)$ ?
(Chebyshev–Gauss quadrature) Show that the Gauss rule for the weight $w$ at the $n$ Chebyshev roots has equal weights $w_i = \frac\pi n$ (exactness on $T_0, \dots, T_{n-1}$ plus the trigonometric sums $\sum_{k=1}^n\cos\bigl(j\tfrac{(2k-1)\pi}{2n}\bigr) = 0$ for $1 \leq j \leq n - 1$ ): the most uniform of all quadratures. Write it out for $n = 3$ .

Part VI — Christoffel–Darboux, interlacing, and the Jacobi matrix. Back to a general weight; $h_k = \norm{p_k}^2$ (monic $p_k$ ), $b_k = h_k/h_{k-1}$ .

(Least norm) Show that among all monic polynomials of degree $n$ , the orthogonal $p_n$ is the unique one of minimal $L^2(w)$ -norm — identify the minimization as an orthogonal projection onto $\R_{n-1}[t]$ (Theorem 13.2 or the finite-dimensional projection of Year 2). The minimax property of question 14 is the same statement with $L^\infty$ in place of $L^2$ : same hero, two norms.
(Christoffel–Darboux) Prove, by induction on $n$ using the three-term recurrence, the identity

$\sum_{k=0}^{n}\frac{p_k(x)\,p_k(y)}{h_k} = \frac{p_{n+1}(x)\,p_n(y) - p_n(x)\,p_{n+1}(y)}{h_n\,(x - y)} \qquad (x \neq y),$

and its confluent form ( $y \to x$ ): $\sum_{k\leq n}\frac{p_k(x)^2}{h_k} = \frac{p_{n+1}'(x)p_n(x) - p_n'(x)p_{n+1}(x)}{h_n}$ .
Deduce that $p_n$ and $p_{n+1}$ have no common root, and that at every root $x_0$ of $p_{n+1}$ : $p_n(x_0)\,p_{n+1}'(x_0) > 0$ . Conclude the interlacing of roots: between two consecutive roots of $p_{n+1}$ lies exactly one root of $p_n$ .
(Jacobi matrix) Let $J_n$ be the $n\times n$ symmetric tridiagonal matrix with diagonal $a_0, \dots, a_{n-1}$ and off-diagonal entries $\sqrt{b_1}, \dots, \sqrt{b_{n-1}}$ . Show by induction that $\det(tI_n - J_n) = p_n(t)$ , so the roots of $p_n$ are the eigenvalues of a real symmetric matrix — re-proving in one line that they are real, and (with the interlacing above) tying orthogonal polynomials to the spectral world of Chapter 15.
(Synthesis) Assemble the dictionary for the three classical families (Legendre, Hermite, Chebyshev): interval, weight, defining formula, three-term recurrence, norm, and the natural habitat of each (quadrature and approximation on compacta; Gaussian analysis; minimax and Fourier-cosine methods). One sentence on what the general theory (Parts I, VI) gave that no individual computation could.

Part VII — The error term, and the kernel behind the weights. Here $I$ is compact and $f \in \mathcal C^{2n}(I)$ .

(Gauss error formula) Let $Hf$ be the Hermite interpolant of degree $\leq 2n - 1$ matching $f$ and $f'$ at the nodes $t_1, \dots, t_n$ (prove its existence and the pointwise error

$f(t) - Hf(t) = \frac{f^{(2n)}(\xi_t)}{(2n)!}\;p_n(t)^2$

by the usual auxiliary-function argument). Deduce, by integrating this identity against $w$ and squeezing between the extrema of $f^{(2n)}$ , that

$\int_I f\,w - Q_n(f) = \frac{f^{(2n)}(\xi)}{(2n)!}\,h_n \qquad\text{for some } \xi \in I,$

with $h_n = \norm{p_n}^2$ as in Part VI: Gauss quadrature errs by one $2n$ -th derivative, weighted by the squared norm of the monic orthogonal polynomial.
(The weights are Christoffel values) Using the reproducing kernel $K_n(x, y) = \sum_{k=0}^{n-1} \frac{p_k(x)p_k(y)}{h_k}$ of $\R_{n-1}[t]$ and the exactness of $Q_n$ up to degree $2n - 2$ , prove

$w_i \;=\; \Bigl(\,\sum_{k=0}^{n-1} \frac{p_k(t_i)^2}{h_k}\Bigr)^{\!-1} :$

each weight is the value at its node of the Christoffel function — positivity of the weights (question 10) again, now with an exact formula. Verify it recovers $w_1 = w_2 = 1$ for $n = 2$ , $I = \intcc{-1}1$ , $w = 1$ .
(Everything checks on one integral) For the Chebyshev weight and $n = 3$ nodes, compute both sides of

$\int_{-1}^{1}\frac{t^6}{\sqrt{1 - t^2}}\,\dd t = \frac{5\pi}{16}, \qquad Q_3(t^6) = \frac{9\pi}{32},$

so the quadrature error is exactly $\frac{\pi}{32}$ ; then check that the error formula of question 23 predicts precisely this value (here $f^{(6)} = 6!$ is constant, and $h_3 = \norm{2^{-2}T_3}_w^2 = \frac\pi{32}$ ): theory and computation agree to the last digit.

Solution

Solution of Problem 13.1.

1. Gram–Schmidt guarantees $\operatorname{Vect}(p_0, \dots, p_n) = \operatorname{Vect}(1, \dots, t^n) = \R_n[t]$ and $p_n \perp p_k$ ( $k < n$ ), hence $p_n \perp \R_{n-1}[t]$ . The $p_k$ , of strictly increasing degrees, are independent: a basis.

2. $t\,p_n$ is monic of degree $n + 1$ : expand $t\,p_n = p_{n+1} + \sum_{k\leq n}c_kp_k$ with $c_k = \langle p_k, tp_n\rangle/\norm{p_k}^2$ . For $k \leq n - 2$ : $\langle p_k, tp_n\rangle = \langle tp_k, p_n\rangle = 0$ (degree $k + 1 < n$ ). So $tp_n = p_{n+1} + a_np_n + b_np_{n-1}$ , the stated recurrence, with

b_n = \frac{\langle p_{n-1}, tp_n\rangle}{\norm{p_{n-1}}^2} = \frac{\langle tp_{n-1}, p_n\rangle}{\norm{p_{n-1}}^2} = \frac{\langle p_n + (\text{lower}),\ p_n\rangle}{\norm{p_{n-1}}^2} = \frac{\norm{p_n}^2}{\norm{p_{n-1}}^2} > 0 .

3. Let $t_1 < \dots < t_m$ be the points interior to $I$ where $p_n$ changes sign, and $q = \prod_{i\leq m}(t - t_i)$ (with $q = 1$ if $m = 0$ ). Then $p_nq$ has constant sign on $I$ and is not a.e. zero: $\int_Ip_nq\,w \neq 0$ . If $m < n$ , this contradicts $p_n \perp \R_{n-1}[t]$ . So $m = n$ : $p_n$ has $n$ distinct interior roots (it has at most $n$ roots in all).

4. $(t^2 - 1)^n$ has degree $2n$ ; $n$ derivatives leave degree $n$ , with leading coefficient $\frac{(2n)(2n-1)\cdots(n+1)}{2^nn!} = \frac{(2n)!}{2^n(n!)^2}$ . For $\deg Q < n$ , integrate by parts $n$ times: all boundary terms contain a derivative of order $< n$ of $(t^2-1)^n$ , which vanishes at $\pm1$ (root of order $n$ ); after $n$ steps the integrand carries $Q^{(n)} = 0$ .

5. With $u = (t^2 - 1)^n$ :

(2^nn!)^2\norm{P_n}^2 = \int_{-1}^1(u^{(n)})^2 = (-1)^n\int_{-1}^1 u\,u^{(2n)} = (2n)!\int_{-1}^1(1 - t^2)^n\dd t ,

( $u^{(2n)} = (2n)!$ ; boundary terms vanish as in question 4). And $\int_{-1}^1(1-t^2)^n\dd t = B(\tfrac12, n+1) = \frac{\Gamma(\frac12)\Gamma(n+1)}{\Gamma(n + \frac32)} = \frac{2\cdot4^n(n!)^2}{(2n+1)!}$ (Exercise 11.8). Combining: $\norm{P_n}^2 = \frac{2}{2n + 1}$ .

6. Polynomials are $\norm\cdot_\infty$ -dense in $\mathcal C(\intcc{-1}1)$ (Weierstrass, Corollary 7.16), continuous functions are $L^2$ -dense (Theorem 12.6), and $\norm\cdot_2 \leq \sqrt2\norm\cdot_\infty$ : polynomial spans are total, so the normalized $P_n$ form a Hilbert basis. Expansion of $\abs t$ : the coefficient against $P_0$ is $\frac{\langle P_0, \abs t\rangle}{\norm{P_0}^2} = \frac12$ ; against $P_1$ : $0$ (parity); against $P_2$ : $\frac{\int_{-1}^1\abs t\,\frac{3t^2-1}2\dd t}{2/5} = \frac{1/4}{2/5} = \frac58$ . Best quadratic approximation:

\abs t \approx \frac12 + \frac58\,P_2(t) = \frac{3}{16} + \frac{15}{16}\,t^2 .

7. From $\frac{\dd^{n+1}}{\dd t^{n+1}}\eu^{-t^2} = \frac{\dd^n}{\dd t^n}(-2t\,\eu^{-t^2})$ and Leibniz, $H_{n+1} = 2tH_n - H_n'$ ; induction gives degree $n$ and leading coefficient $2^n$ . For $m < n$ , integrate by parts $n$ times in $\int H_m H_n\eu^{-t^2} = (-1)^n\int H_m\,\bigl(\eu^{-t^2} \bigr)^{(n)}$ : boundary terms (polynomial $\times$ $\eu^{-t^2}$ ) vanish at $\pm\infty$ , leaving $\int H_m^{(n)}\,\eu^{-t^2} = 0$ . For $m = n$ : $H_n^{(n)} = 2^nn!$ , so $\norm{H_n}_w^2 = 2^nn!\int\eu^{-t^2} = 2^nn!\sqrt\pi$ .

8. Let $f \in L^2(\R, \eu^{-t^2}\dd t)$ be orthogonal to every polynomial, and $g = f\eu^{-t^2}$ . Then $g \in L^1$ : $\int\abs f\eu^{-t^2} \leq \bigl(\int\abs f^2\eu^{-t^2}\bigr)^{1/2}\bigl(\int\eu^{-t^2}\bigr)^{1/2}$ (Cauchy–Schwarz). For $\xi \in \R$ , expand $\eu^{-\iu\xi t}$ : the partial sums are dominated since

\sum_k\frac{\abs\xi^k}{k!}\int\abs f\,\abs t^k\eu^{-t^2}\dd t \leq \Bigl(\int \abs f^2\eu^{-t^2}\Bigr)^{1/2} \sum_k\frac{\abs\xi^k}{k!}\Bigl(\int t^{2k}\eu^{-t^2}\Bigr)^{1/2} < \infty

(the last series converges: $\int t^{2k}\eu^{-t^2} = \Gamma(k+\frac12) \leq k!\,\sqrt\pi$ , so the terms are $O(\abs\xi^k/\sqrt{k!})$ ). Term-by-term integration (Corollary 10.7 applied to the absolute series, then Fubini for series) gives

\int_\R g(t)\,\eu^{-\iu\xi t}\dd t = \sum_k\frac{(-\iu\xi)^k}{k!}\int f(t)\,t^k\,\eu^{-t^2}\dd t = 0 ,

each integral being $\langle t^k, f\rangle_w$ -type $= 0$ . By the admitted injectivity of the Fourier transform (Chapter 14), $g = 0$ a.e., so $f = 0$ a.e.: the Hermite family (whose spans are the polynomials) is total.

9. Exactness to degree $n - 1$ : for such $P$ , $P = \sum_iP(t_i)\ell_i$ exactly, so $\int Pw = \sum_iP(t_i)\int \ell_iw = Q(P)$ . Degree $\leq 2n - 1$ : divide $P = qp_n + r$ , $\deg q \leq n - 1$ , $\deg r \leq n-1$ ; then $\int Pw = \int qp_nw + \int rw = 0 + Q(r)$ ( $p_n \perp \R_{n-1}[t]$ ), while $Q(P) = \sum_iw_i\bigl(q(t_i)\,p_n(t_i) + r(t_i)\bigr) = Q(r)$ since the nodes are the roots of $p_n$ . Equal.

10. $\ell_i^2$ has degree $2n - 2 \leq 2n - 1$ and $\ell_i^2(t_j) = \delta_{ij}$ : $0 < \int\ell_i^2w = Q(\ell_i^2) = w_i$ . Polya (Exercise 8.9, transported to $I$ with weight): condition (i) holds — each polynomial is integrated exactly once $2n - 1 \geq$ its degree; condition (ii): $\sum_i\abs{w_{i}} = \sum_iw_i = Q(\mathbf 1) = \int_Iw$ , bounded: $Q_n(f) \to \int fw$ for every $f \in \mathcal C(I)$ , $I$ compact.

11. Monic $p_2 = t^2 - \frac13$ (from Exercise 13.4): nodes $\pm\frac1{\sqrt3}$ . Weights: $\ell_1(t) = \frac{t - \frac1{\sqrt3}}{-\frac2{\sqrt3}}$ , and $w_1 = \int_{-1}^1\ell_1 = 1$ ; by symmetry $w_2 = 1$ . Exactness: $\int 1 = 2 = 1 + 1$ ; $\int t = 0 = -\frac1{\sqrt3} + \frac1{\sqrt3}$ ; $\int t^2 = \frac23 = \frac13 + \frac13$ ; $\int t^3 = 0$ . The two-point trapezoid rule (nodes $\pm1$ , weights $1, 1$ ) is exact only to degree $1$ : on $t^2$ it returns $2$ instead of $\frac23$ . Same cost, two extra degrees of exactness: the payoff of orthogonal nodes.

12. From $\cos(n{+}1)\theta + \cos(n{-}1)\theta = 2\cos\theta\cos n\theta$ : $T_{n+1} = 2tT_n - T_{n-1}$ with $T_0 = 1$ , $T_1 = t$ ; induction gives polynomials of degree $n$ with leading coefficient $2^{n-1}$ ( $n \geq 1$ ). Substituting $t = \cos\theta$ ( $w(t)\dd t \mapsto \dd\theta$ ): $\langle T_m, T_n\rangle_w = \int_0^\pi\cos m\theta\cos n\theta\,\dd\theta = 0$ for $m \neq n$ , $= \pi$ for $m = n = 0$ , $= \frac\pi2$ otherwise (product-to-sum). Degrees and pairwise orthogonality identify the $T_n$ with the Gram–Schmidt output up to scalars; a Chebyshev expansion of $f$ is exactly the Fourier cosine series of $\theta \mapsto f(\cos\theta)$ .

13. $T_n(t) = 0$ iff $\cos n\theta = 0$ iff $\theta = \frac{(2k-1)\pi}{2n}$ : the $n$ distinct roots $t_k = \cos\frac{(2k-1)\pi}{2n} \in \intoo{-1}1$ . Extrema: $\abs{T_n} \leq 1$ on $\intcc{-1}1$ , with $T_n(s_j) = (-1)^j$ at the $n + 1$ points $s_j = \cos\frac{j\pi}n$ : perfect equioscillation.

14. $2^{1-n}T_n$ is monic with sup-norm $2^{1-n}$ . If a monic $P$ of degree $n$ had $\sup\abs P < 2^{1-n}$ , the difference $D = 2^{1-n}T_n - P$ would have degree $\leq n - 1$ (leading terms cancel) yet alternate in sign at $s_0 > \dots > s_n$ (there $2^{1-n}T_n = \pm2^{1-n}$ dominates $P$ ): at least $n$ zeros — $D \equiv 0$ , contradiction. For uniqueness at equality, the same $D$ satisfies $(-1)^jD(s_j) \geq 0$ ; a nonzero polynomial of degree $\leq n-1$ cannot have $n$ weakly alternating extremal constraints without $n$ roots counted properly (if $D(s_j) = 0$ for some interior $s_j$ , that zero is double in the counting since $D$ keeps a sign locally): again $D \equiv 0$ .

15. The Lagrange error formula (Rolle, Year 2) gives $f - L_nf = \frac{f^{(n)}(\xi_t)}{n!}\,\omega(t)$ , so the uniform error is at most $\frac{\norm{f^{(n)}}_\infty} {n!}\,\sup\abs\omega$ , and $\omega$ is monic of degree $n$ : by question 14, $\sup_{\intcc{-1}1}\abs\omega \geq 2^{1-n}$ with equality iff the nodes are the Chebyshev roots. Hence the optimal bound $\norm{f - L_nf}_\infty \leq \frac{\norm{f^{(n)}}_\infty}{2^{n-1}n!}$ . With equally spaced nodes, $\sup\abs\omega$ is exponentially larger near the endpoints, and interpolating even $\frac1{1 + 25t^2}$ diverges there as $n \to \infty$ (Runge’s phenomenon); Chebyshev nodes are the cure.

16. Differentiating $T_n(\cos\theta) = \cos n\theta$ : $T_n'(\cos\theta) = \frac{n\sin n\theta} {\sin\theta}$ , which tends to $n^2$ as $\theta \to 0$ and to $(-1)^{n+1}n^2$ as $\theta \to \pi$ : $\abs{T_n'(\pm1)} = n^2$ . At interior points, $\abs{T_n'(t)} \leq \frac{n}{\sqrt{1 - t^2}} = O(n)$ : the quadratic blow-up lives only at the edges (Bernstein’s interior bound versus Markov’s global one).

17. Let $\theta_k = \frac{(2k-1)\pi}{2n}$ and $S_j = \sum_{k=1}^n\cos(j\theta_k)$ for $1 \leq j \leq n-1$ . Then

S_j = \operatorname{Re}\Bigl[\eu^{\iu j\pi/2n} \sum_{k=0}^{n-1}\eu^{\iu jk\pi/n}\Bigr] = \operatorname{Re}\Bigl[\eu^{\iu j\pi/2n}\, \frac{\eu^{\iu j\pi} - 1}{\eu^{\iu j\pi/n} - 1}\Bigr] .

For $j$ even the numerator vanishes: $S_j = 0$ . For $j$ odd the numerator is $-2$ , and $\eu^{\iu j\pi/n} - 1 = \eu^{\iu j\pi/2n}\cdot2\iu\sin\frac{j\pi}{2n}$ , so the whole expression is $\frac{-2}{2\iu\sin(j\pi/2n)} = \frac{\iu}{\sin(j\pi/2n)}$ : purely imaginary, $S_j = 0$ again. Hence the equal-weight rule $\frac\pi n\sum_kf(t_k)$ integrates $T_0$ ( $\sum w_i = \pi = \int w$ ) and kills $T_1, \dots, T_{n-1}$ exactly as $\int T_jw = 0$ does: it is exact to degree $n - 1$ . Weights exact to degree $n-1$ at given nodes are unique (Lagrange basis): the Gauss weights are all $\frac\pi n$ . For $n = 3$ : nodes $\pm\frac{\sqrt3}2, 0$ and

\int_{-1}^1\frac{f(t)}{\sqrt{1 - t^2}}\,\dd t \approx \frac\pi3\Bigl[f\Bigl(\tfrac{\sqrt3}2\Bigr) + f(0) + f\Bigl(-\tfrac{\sqrt3}2\Bigr)\Bigr],

exact through degree $5$ .

18. For monic $P$ of degree $n$ : $P = p_n + r$ with $r \in \R_{n-1}[t]$ , and $p_n \perp \R_{n-1}[t]$ (question 1), so $\norm P^2 = \norm{p_n}^2 + \norm r^2 \geq \norm{p_n}^2$ , with equality iff $r = 0$ : $p_n$ is the orthogonal projection residue of $t^n$ onto $\R_{n-1}[t]^\perp$ , i.e. the monic polynomial closest to the subspace it must avoid. Chebyshev’s $2^{1-n}T_n$ answers the same question for the sup-norm: least deviation from zero, once in $L^2(w)$ , once in $L^\infty$ .

19. Write $K_n(x, y) = \sum_{k=0}^n\frac{p_k(x)p_k(y)}{h_k}$ . Base $n = 0$ : $(x - y)\frac1{h_0} = \frac{p_1(x)\cdot1 - 1\cdot p_1(y)}{h_0}$ since $p_1 = t - a_0$ . Step: assuming the identity for $n - 1$ ,

(x - y)\,K_n(x,y) = \frac{p_n(x)p_{n-1}(y) - p_{n-1}(x)p_n(y)}{h_{n-1}} + \frac{(x - y)\,p_n(x)p_n(y)}{h_n} ;

substitute $x\,p_n(x) = p_{n+1}(x) + a_np_n(x) + b_np_{n-1}(x)$ and $y\,p_n(y) = p_{n+1}(y) + a_np_n(y) + b_np_{n-1}(y)$ in the second term: the $a_n$ contributions cancel, and the $b_n = \frac{h_n}{h_{n-1}}$ contributions cancel the induction term; what survives is $\frac{p_{n+1}(x)p_n(y) - p_n(x)p_{n+1}(y)}{h_n}$ . The confluent form follows by letting $y \to x$ (both sides are polynomials in $y$ ).

20. The confluent form gives $p_{n+1}'p_n - p_n'p_{n+1} = h_n\sum_{k\leq n}\frac{p_k^2}{h_k} \geq \frac{h_n}{h_0} > 0$ everywhere. At a root $x_0$ of $p_{n+1}$ : $p_{n+1}'(x_0)\,p_n(x_0) > 0$ , so $p_n(x_0) \neq 0$ (no common roots). Between consecutive roots $x_0 < x_1$ of $p_{n+1}$ (all simple, Part I), $p_{n+1}'$ has opposite signs, hence so does $p_n$ : a root of $p_n$ lies in each of the $n$ gaps — and that exhausts its $n$ roots: interlacing.

21. Expanding $D_n(t) = \det(tI_n - J_n)$ along the last row: $D_n = (t - a_{n-1})D_{n-1} - b_{n-1}D_{n-2}$ , with $D_0 = 1$ , $D_1 = t - a_0$ : the recurrence and seeds of the monic $p_n$ , so $D_n = p_n$ . Roots of $p_n$ = eigenvalues of the symmetric $J_n$ : real, and simple by question 19 — Gauss quadrature is the spectral theory of a tridiagonal matrix in disguise, the finite-dimensional shadow of Chapter 15.

22. Dictionary:

	Legendre	Hermite	Chebyshev
interval	$\intcc{-1}1$	$\R$	$\intcc{-1}1$
weight	$1$	$\eu^{-t^2}$	$(1-t^2)^{-1/2}$
formula	Rodrigues	$(-1)^n\eu^{t^2} \frac{\dd^n}{\dd t^n}\eu^{-t^2}$	$\cos(n\arccos t)$
norm $^2$	$\frac2{2n+1}$	$2^nn!\sqrt\pi$	$\pi, \frac\pi2$
habitat	quadrature	Gaussian calculus	minimax

(each with its three-term recurrence: general form for Legendre, $H_{n+1} = 2tH_n - 2nH_{n-1}$ , $T_{n+1} = 2tT_n - T_{n-1}$ ). The general theory supplied what no single family shows: reality and interlacing of roots, positivity of quadrature weights, the mere existence of the recurrence and of Christoffel–Darboux — consequences of orthogonality alone, uniform in the weight.

23. Existence: the linear map $\R_{2n-1}[t] \to \R^{2n}$ , $P \mapsto (P(t_1), P'(t_1), \dots, P(t_n), P'(t_n))$ , is injective (a $P$ in the kernel has $n$ double roots and degree $\leq 2n - 1$ , so $P = 0$ ) between spaces of equal dimension $2n$ : bijective. Pointwise error: fix $t$ not a node and choose $K$ so that $g(s) = f(s) - Hf(s) - K\,p_n(s)^2$ vanishes at $s = t$ . Then $g$ vanishes at the $n + 1$ distinct points $t, t_1, \dots, t_n$ , and $g'$ vanishes at each $t_i$ too (both $f - Hf$ and $p_n^2$ have double zeros there). Rolle gives $n$ zeros of $g'$ strictly between consecutive zeros of $g$ — distinct from the nodes — so $g'$ has $2n$ distinct zeros; applying Rolle $2n - 1$ more times produces $\xi_t$ with $g^{(2n)}(\xi_t) = 0$ . Since $\deg Hf \leq 2n - 1$ and $p_n^2$ is monic of degree $2n$ , $g^{(2n)} = f^{(2n)} - K\,(2n)!$ , whence $K = f^{(2n)}(\xi_t)/(2n)!$ — and the identity is trivial at the nodes. Integration: $Q_n(f) = Q_n(Hf)$ ( $Hf$ matches $f$ at the nodes) and $Q_n(Hf) = \int Hf\,w$ by exactness up to degree $2n - 1$ (question 9), so the quadrature error is $\int(f - Hf)\,w$ . With $m, M$ the extrema of $f^{(2n)}$ on $I$ , the pointwise identity squeezes

\frac{m\,h_n}{(2n)!} \;\leq\; \int_I(f - Hf)\,w \;\leq\; \frac{M\,h_n}{(2n)!} ,

and the intermediate value theorem applied to the continuous $f^{(2n)}$ delivers $\xi$ . (For Legendre with $n = 2$ : $h_2 = \int_{-1}^1(t^2 - \frac13)^2\dd t = \frac8{45}$ , so the error is $f^{(4)}(\xi)/135$ .)

24. The kernel reproduces $\R_{n-1}[t]$ : expanding $q = \sum_k\frac{\langle p_k, q\rangle}{h_k}p_k$ gives $\int_I K_n(t_i, t)\,q(t)\,w(t)\dd t = q(t_i)$ for every $q$ of degree $\leq n - 1$ . Take $q = \ell_i$ : the left side equals $\ell_i(t_i) = 1$ . But $t \mapsto K_n(t_i, t)\,\ell_i(t)$ is a polynomial of degree $\leq (n - 1) + (n - 1) = 2n - 2$ , on which $Q_n$ is exact (question 9), and it vanishes at every node $t_j \neq t_i$ (factor $\ell_i$ ), so

1 = \int_I K_n(t_i, t)\,\ell_i(t)\,w(t)\dd t = w_i\,K_n(t_i, t_i) = w_i\sum_{k=0}^{n-1}\frac{p_k(t_i)^2}{h_k} .

The sum is $> 0$ (its $k = 0$ term is $1/h_0 > 0$ ): the stated formula, and positivity again. Check ( $n = 2$ , Legendre): $p_0 = 1$ , $h_0 = 2$ , $p_1 = t$ , $h_1 = \frac23$ ; at $t_i = \pm\frac1{\sqrt3}$ ,

K_2(t_i, t_i) = \frac12 + \frac{1/3}{2/3} = 1, \qquad w_i = 1,

as found in question 11.

25. Substituting $t = \cos\theta$ , the integral is $\int_0^\pi\cos^6\theta\,\dd\theta = \pi\,\frac{5\cdot3\cdot1}{6\cdot4\cdot2} = \frac{5\pi}{16}$ (Wallis, Exercise 11.8). The $n = 3$ Chebyshev–Gauss rule (question 17) has nodes $\cos\frac\pi6 = \frac{\sqrt3}2$ , $\cos\frac\pi2 = 0$ , $\cos\frac{5\pi}6 = -\frac{\sqrt3}2$ and equal weights $\frac\pi3$ :

Q_3(t^6) = \frac\pi3\Bigl(2\cdot\Bigl(\frac{\sqrt3}2 \Bigr)^{6}\Bigr) = \frac\pi3\cdot\frac{54}{64} = \frac{9\pi}{32}, \qquad \frac{5\pi}{16} - \frac{9\pi}{32} = \frac\pi{32} .

Prediction: the monic degree- $3$ orthogonal polynomial is $2^{-2}T_3 = t^3 - \frac34t$ , with $h_3 = \frac1{16}\norm{T_3}_w^2 = \frac1{16}\cdot\frac\pi2 = \frac\pi{32}$ ; and $f = t^6$ has constant $f^{(6)} = 720 = 6!$ , so question 23 gives error $\frac{6!}{6!}\,h_3 = \frac\pi{32}$ — with no dependence on $\xi$ left, the formula is forced to be exact, and it is.

Terms defined in this chapter

See all 395 terms in the glossary