133VIII. Compact perturbations of the identityThis is the first of several chapters in which the basic knowledge accumulated in thepreceding chapters is used for the analysis of various numerical procedures.Projection methodsThe (Rayleigh-)Ritz method consists in minimizing the quadratic functionalΦλ: x 7→ kxk2A− 2Reλxover a sufficiently large lss F of the ips X. The minimizer f is the representer of the linearfunctional λFwith respect to the inner product h, iA:= h·,A·i, hence an approximationto the solution u of the Euler equationA?=yassociated with Φλ,inwhichh·,yi = λ. In fact, f is the best approximation to u from Fwrto the A-norm, hence computable by interpolation, since it solves the LIP? ∈ F, u−? ⊥AF.This means that the interpolation functionals are of the special formvcA = hv, A·i,v∈ F.Galerkin noticed that this procedure is capable of vast generalization. There is reallyno reason to insist that A be positive definite, i.e., that h, iAbe an inner product. We canuse this LIP even when A is just any old lm. The price we pay for this is that we cannotbe sure any more that the LIP is correct.Further generalizations were offered by others to the point that interpolation is nowa standard approach to solving functional equations of all kinds. The idea is this: LetA ∈ L(X, Y ). To approximate the solution u of the equationA?=y,pick some V ∈ L(IFn,X) and some Λ ∈ L(IFn,Y0) and look for f ∈ F := ran V that solvesΛtA?=Λty.In other words, we approximate the solution u by an interpolant, i.e., by the solution tothe LIP(ran V,ran A0Λ), making use of the fact that we are given y, i.e., Au, hence cancompute (A0λ)u =(λA)u for any particular λ we care to (at least in principle), hence maytry to match that information.examplesc2002 Carl de Boor134 VIII. Compact perturbations of the identity** examples **(1) ODE-Example Consider the m-th order ODEAu := Dmu −Xj<majDju = y,for which a solution u is sought in X := C(m)[a..b] ∩ ker Mt, with Mt∈ bL(C(m−1), IRm)the data map that specifies the m (homogeneous) side conditions needed to select a uniquesolution from the m-dimensional solution set available for the ODE in C(m)[a..b]. ThenY = C[a..b] is an appropriate choice. Let F be some n-dimensional lss of X.In collocation, one chooses Λt: f 7→ fUfor some n-set U in [a..b]. In effect, theapproximation f from F is chosen so as to satisfy the ODE exactly at the points of U.In Galerkin’s method, ran Λ consists of the lfl’sx 7→Zbaz(t)x(t)dt, all z ∈ F.This means that the residual y − Af is made orthogonal to F .In the least-squares method, one uses the lfl’sx 7→Zba(Az)(t)x(t)dt, all z ∈ Finstead. This means that the residual is minimized (over F)intheL2sense.In the moment method, one uses the linear functionalsx 7→Zbatjx(t)dt, j =0,...,n− 1,thereby making the first n moments of the residual equal to zero. etc.** residual reduction **These methods are also called “residual reduction methods”, since they can beviewed as an attempt to make the residual zero in a certain sense. Precisely, the residualis made to vanish on certain lfl’s.These methods are also called projection methods.Thisisnot because they arebased on interpolation, i.e., the approximation f to u is given as f = Pu, with P thelprojector given by F and L := ran A0Λ. Rather, they got this name since f is sought asthe solution in F of the projected equation QAf = Qy, with Q any l.projector on Ywhose interpolation functionals are ran Λ.** analysis by perturbation from a simple case **In each instance, one has to settle the correctness of the LIP, bound the resultingprojector in suitable norms and then leave it to Lebesgue’s Inequality and ApproximationTheory to provide a priori error bounds. Correctness and norm bounds are usually ob-tained for a very simple instance A0of A. The general A is treated as a perturbation ofthe simple A0, under the assumption that A − A0is “small” in some sense.analysis by perturbation from a simple casec2002 Carl de BoorCompact linear maps 135In the simplest case, one tries to use A0−1as an approximate inverse for A.Thisrequires, practically speaking, (cf. (III.15)Prop.) thatkA − A0k < 1/kA0−1k,hence has only limited applicability. As it turns out, it is often sufficient to assume thatA − A0be compact, without any assumption on the norm of A − A0.Compact linear maps(2) Definition. K ∈ L(X,Y ) is compact (or, completely continuous, or better butunconventional, totally bounded):=K carries bounded sets to totally bounded sets,i.e., KB is totally bounded. I denote the collection of all compact linear maps from X toY bycL(X, Y ).In particular, a compact lm is bounded. While this definition makes sense in moregeneral topological spaces, we restrict attention to nls’s X, Y .** examples **Any bounded finite-rank lm is compact (since any bounded set in a finite dimensionalls is totally bounded).The (norm) limit K of any sequence (Kn) of compact lm’s is compact. Indeed, KB ⊆(K − Kn)B + KnB, and, for r>0, can choose n so that (K − Kn)B ⊆ Br/2and, for thatn, can choose a finite r/2-net for KnB.In particular, all (norm) limits of bounded finite-rank lm’s are compact, i.e., compactmaps are the only maps uniformly (i.e., norm-) approximable by finite-rank maps, hencetheir importance in Numerical Analysis.H.P.(1) Prove that, if k ∈ C(R × T ) for R, T compact in IRnand 1 ≤ p ≤∞,thenK : Lp(T ) → C(R):f 7→RTk(·,t)f (t)dt is compact.Any finite linear combination of compact maps is compact, i.e., cL(X, Y )isalssofL(X, Y ). If K is compact and A is bounded, then AK and KA are compact. (In particular,cL(X) is a (closed) two-sided ideal in bL(X).)** compactness and convergence **The compactness of a map is used to force convergence or improve the mode of con-vergence: If (xn) is a bounded sequence, then, by compactness of K,(Kxn)isatotallybounded sequence, hence (cf. H.P.(II.31)) has a Cauchy subsequence. Consequently, if Yis complete, then some subsequence of (Kxn) converges. This fact is usually used in thefollowing form:(3) Proposition (AGTASMAT). If K ∈ cL(X, Y ) with Y a Bs, and (xn) is bounded,then, After Going To ASubsequence, May Assume That (Kxn) converges.We also use the following consequence of the fact (cf. H.P.(V.3)) that bounded strongconvergence is uniform on totally bounded sets:compactness and convergencec2002 Carl de Boor136 VIII. Compact perturbations of the identity(4) Proposition. K