C*-ALGEBRAS AND NUMERICALANALYSIS
PURE
AND APPLIED
MATHEMATICS
A Program of Monographs, Textbooks, and Lecture Not...
25 downloads
989 Views
15MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
C*-ALGEBRAS AND NUMERICALANALYSIS
PURE
AND APPLIED
MATHEMATICS
A Program of Monographs, Textbooks, and Lecture Notes
EXECUTIVE EDITORS Zuhair Nashed University of Delaware Newark, Delaware
EarlJ. Taft Rutgers University New Brunswick, New Jersey
EDITORIAL M. S. Baouendi University of California, San Diego Jane Cronin Rutgers University
Georgia Institute
Jack K. Hale of Technology
BOARD Anil Nerode Cornell University Donald Passman University of Wisconsin, Madison Fred S. Roberts Rutgers University
S. Kobayashi University of California, Berkeley
David L. Russell Virginia Polytechnic Institute and State University
Marvin Marcus University of California, Santa Barbara
Walter Schempp Universitgit Siegen
W. S. Masse)) Yale University
Mark Teply University of Wisconsin, Milwaukee
MONOGRAPHS AND TEXTBOOKS IN PURE AND APPLIED MATHEMATICS 1. K. Yano,Integral Formulas in Riemannian Geometry (1970) 2. S. Kobayashi,HyperbolicManifoldsandHolomorphic Mappings (1970) of Mathematical Physics(A. Jeffrey, ed.; A. Littlewood, 3. V. S. Vladimirov,Equations trans.) (1970) 4. B. N. Pshem’chnyi, Necessary Conditionsfor an Extremum (L. Neustadt,translation ed.; K. Makowski, trans.) (1971) 5. LoNarici et al., Functional AnalysisandValuation Theory(1971) Infinite GroupRings(1971) 6. S.S. Passman, 7. L. Domhoff,GroupRepresentation Theory.Part A: OrdinaryRepresentation Theory. Part B: ModularRepresentation Theory(1971,1972) W. Boothby and G. L. Weiss, eds., Symme~c Spaces (1972) 8. 9. Y. Matsushima, DifferentiableManifolds (E. T. Kobayashi, trans.) (1972) 10. L. E. Ward,Jr., Topology (1972) 11. A. Babakhanian, Cohomological Methods in GroupTheory(1972) t2. R. Gilmer,Multiplicative Ideal Theory(1972) 13. J. Yeh,StochasticProcesses andthe WienerIntegral (1973) 14. J. Barros-Neto, Introductionto the Theoryof Distributions(1973) 15. R. Larsen,FunctionalAnalysis(1973) 16. K. YanoandS. Ishihara, TangentandCotangent Bundles(1973) 17. C. Procesi,Ringswith Polynomial Identities (1973) 18. R. HetTnann,Geometry, Physics, andSystems (1973) 19. N.R. Wallach, HarmonicAnalysis on Homogeneous Spaces(1973) 20. J. Dieudonnd, Introductionto the Theoryof FormalGroups (1973) 21. I. Vaisman, Cohomology andDifferential Forms(1973) 22. B.-Y. Chert, Geometry of Submanifolds (1973) 23. M.Marcus,Finite Dimensional MultilinearAlgebra(in twoparts) (1973,1975) 24. R. Larsen,Banach Algebras(1973) 25. R. O. KujalaandA. L. Vitter, eds., ValueDistributionTheory:Part A; Part B: Deficit andBezoutEstimatesby WilhelmStoll (1973) 26. K.B. Stolarsky, AlgebraicNumbers andDiophantineApproximation (1974) Rings(1974) 27. A.R. Magid,TheSeparableGalois Theoryof Commutative Finite Ringswith Identity (1974) 28. B.R. McDonald, 29. J. Satake,LinearAlgebra(S. Kohet al., trans.) (1975) Rings(1975) 30. J.S. Go/an,Localization of Noncommutative 31. G. Klambauer, Mathematical Analysis(1975) 32. M. K, Agoston,AlgebraicTopology(1976) 33. K.R. Goodear/,Ring Theory(1976) 34. L.E. Mansfield,LinearAlgebrawith Geometric Applications(1976) 35. N.J. Pullman,MatrixTheoryandIts Applications(1976) 36. B.R. McDonald, GeometricAlgebraOverLocal Rings(1976) 37. C. W.Groetsch,Generalized Inversesof LinearOperators(1977) andJ, L. Gersting,AbstractAlgebra(1977) 38. J. E. Kuczkowski 39. C. O. Chdstenson andW.L. Voxman, Aspectsof Topology(1977) 40. M. Nagata,Field Theory(1977) 41. R.L. Long,Algebraic Number Theory(1977) 42. W.F, Pfeffer, Integrals andMeasures (1977) 43. R.L. Wheeden andA. Zygmund, MeasureandIntegral (1977) of a Complex Variable(1978) 44. J.H. Curtiss, Introductionto Functions 45. K. Hrbacek andT. Jech,Introductionto Set Theory(1978) 46. W.S. Massey,Homology andCohomology Theory(1978) 47. M. Marcus,Introduction to Modem Algebra(1978) 48. E.C. Young,VectorandTensorAnalysis(1978) 49. S.B.Nadler,Jr., Hyperspaces of Sets(1978) 50. S.K. Segal,Topicsin GroupKings(1978) 51. A. C. M. van Rooij, Non-Archimedean FunctionalAnalysis(1978) 52. L. CorwinandR. Szczarba,Calculusin VectorSpaces(1979) 53. C. Sadosky, Interpolationof Operators andSingularIntegrals(1979) 54. J. Cronin,DifferentialEquations (1980) 55. C. W.Groetsch,Elements of ApplicableFunctionalAnalysis(1980)
56. 57. 58. 59. 60. 61. 62.
L Vaisman,Foundations of Three-Dimensional EuclideanGeometry (1980) H, I. Freedan,DeterministicMathematical Modelsin PopulationEcology(1980) S.B. Chae,Lebesgue Integration (1980) C.S.Reeset al., TheoryandApplicationsof Fouder Analysis(1981) L. Nachbin, Introductionto FunctionalAnalysis(R. M.Aron,trans.) (1981) G. OrzechandM. Ot-zech,PlaneAlgebraicCurves(1981) R. Johnsonbaugh and W.E. Pfaffenberger, Foundationsof MathematicalAnalysis (1981) 63. W.L. Voxman andR.H. Goetschel,AdvancedCalculus (1981) 64. L. J. CorwinandR. H. Szczarba,MultivariableCalculus(1982) 65. V.I. Istr~tescu,Introductionto LinearOperatorTheory(1981) 66. R.D.J~rvinen,Finite andInfinite Dimensional LinearSpaces (1981) 67. J. K. Beem andP. E. Ehrlich, GlobalLorenlzianGeomet~ (1981) 68. D.L. Armacost,TheStructure of Locally Compact AbelianGroups(1981) 69. J. W.BrewerandM. K. Smith, eds,, Emmy Noether:A Tribute (1981) 70. K.H. K/m,BooleanMatrix TheoryandApplications(1982) 71. T. W. Wieting, TheMathematicalTheoryof ChromaticPlaneOmaments (1982) 72. D. B.Gau/d,Differential Topology (1982) 73. R. L. Faber,Foundations of EuclideanandNon-Euclidean Geometry (1983) 74. M. Carmeli,Statistical TheoryandRandom Matrices(1983) 75. J.H. Canutheta/., TheTheoryof TopologicalSemigroups (1983) 76. R.L. Faber,Differential Geometq/and Relativity Theory(1983) 77. S. Bamett,PolynomialsandLinear ControlSystems (1983) 78. G. Karpilovsky, Commutative GroupAlgebras(1983) 79. F. VanOystaeyen andA.Verschoren,Relative Invadantsof Rings(1983) 80. /. Vaisman, A First Course in Differential Geometry (1964) 81. G. W.Swan,Applicationsof OptimalControlTheoryin Biomedicine (1964) 82. T. PetdeandJ.D. Randa/I,Transformation Groupson Manifolds(1984) andNonexpansive 83. K. GoebelandS. Reich, UniformConvexity,HyperbolicGeomet~, Mappings(1964) RelativeFinitenessin ModuleTheory(1984) 84. T. AlbuandC. N~st~sescu, 85. K. Hrbacek andT. Jech,Introductionto Set Theory:Second Edition (1964) andA.Verschoren, Relative Invariants of Rings(1964) 86. F. VanOystaeyen 87. B.R. McDonald,LinearAIgebraOverCommutative Rings(1964) Geometry of Projective AlgebraicCurves(1984) 88. M. Namba, 89. G.F. Webb,Theoryof NonlinearAge-Dependent PopulationDynamics (1985) et al., Tablesof Dominant WeightMultiplicities for Representations of 90. M. R. Bremner SimpleLie Algebras(1985) 91. A. E. Fekete,RealLinearAlgebra(1985) andCalculus in Normed Spaces(1985) 92. S.B. Chae,Holomorphy 93. A.J. Je~,Introductionto Integral Equations with Applications(1985) 94. G. Karpi/ovsky,ProjectiveRepresentations of Finite Groups (1985) 95. L. Nar~ciandE. Beckenstein, TopologicalVectorSpaces(1985) 96. J. Weeks,The Shapeof Space(1985) of OperationsResearch (1985) 97. P.R. GdbikandK. O. Kortanek,ExtremalMethods 98. J.-A. Chaoand W.A. Woyczynski,eds., Probability TheoryandHarmonicAnalysis (1986) 99. G.D.Crowneta/., AbstractAlgebra(1986) 100. J.H. Carruthet al., TheTheoryof TopologicalSemigroups, Volume 2 (1986) 101. R. S. DoranandV. A. Belfi, Characterizations of C*-Algebras (1986) 102. M. W. Jeter, Mathematical Programming (1986) 103. M. Airman,A Unified Theoryof Nonlinear Operatorand Evolution Equationswith Applications(1986) 104. A. Verschoren, Relative Invadantsof Sheaves (1987) 105. R.A. Usmani,AppliedLinear Algebra(1987) andDifferential Equations in Characteristicp > 106. P. B/assandJ. Lang,Zariski Surfaces 0 (1987) 107. J.A. Reneke et al., StructuredHereditarySystems (1987) and B. B. Phadke,Spaceswith DistinguishedGeodesics (1987) 108. H. Busemann LinearOperators (1988) 109. R. Harte,Invertibility andSingularityfor Bounded 110. G. S. Laddeet al., Oscillation Theoryof Differential Equationswith DeviatingArguments(1987) 111. L. Dudkinet al., Iterative Aggregation Theory (1987) (1987) 112. T. Okubo,Differential Geometry
113.D. L. StandandM. L. Stancl, RealAnalysiswith Point-SetTopology (1987) 114.T. C. Gard,Introductionto Stochastic Differential Equations (1988) 115. S. S, Abhyankar,Enumerative Combinatodcs of YoungTableaux(1988) 116. H. StradeandR. Famsteiner,ModularUeAlgebrasandTheir Representations (1988) 117. J.A. Huckaba,Commutative Ringswith Zero Divisors (1988) 118. W.D.Wallis, CombinatorialDesigns(1988) 119. W.Wi~slaw,TopologicalFields (1988) 120. G. Karpilovsky,Field Theory(1988) 121. S. Caenepeel andF. VanOystaeyen,BrauerGroupsand the Cohomology of Graded Rings(1989) 122. W.Kozlowski,ModularFunctionSpaces(1988) 123. E. Lowen-Colebunders, FunctionClassesof Cauchy Continu6usMaps(1989) of PattemRecognition(1989) 124. M. Pavel,Fundamentals 125. V. Lakshmikantham et al., Stability Analysisof NonlinearSystems (1989) 126. R. Sivaramakdshnan, TheClassicalTheoryof Arithmetic Functions(1989) 127.N. A, Watson, ParabolicEquations onan Infinite Strip (1989) 128. K.J. Hastings,Introductionto the Mathematics of Operations Research (1989) 129. B. Fine, AlgebraicTheoryof the BianchiGroups (1989) 130. D. N. Dikranjanet aL, TopologicalGroups (1989) 131. J. C. Morgan II, Point Set Theory(1990) 132. P. BilerandA.Witkowski,Problems in Mathematical Analysis(1990) 133. H.J. Sussmann, NonlinearControllability andOptimalControl(1990) 134.J.-P. Florenset al., Elements of Bayesian Statistics (1990) 135. N. Shell, TopologicalFieldsandNearValuations(1990) 136. B. F. Doolin andC. F. Martin, Introduction to Differential Geometry for Engineers (1990) 137. S.S. Holland,Jr., AppliedAnalysisby the Hilbert Space Method (1990) 138. J. Okninski,Semigroup Algebras(1990) 139. K. Zhu,OperatorTheoryin FunctionSpaces(1990) 140. G.B.Pdce,AnIntroduction to Multicomplex SpacesandFunctions(1991) 141. R.B. Darst, Introductionto LinearProgramming (1991) 142.P.L. Sachdev, NonlinearOrdinaryDifferential Equations andTheir Applications(1991) 143. T. Husain,OrthogonalSchauder Bases(1991) 144. J. Foran,Fundamentals of RealAnalysis(1991) 145. W.C.Brown,Matdcesand Vector Spaces(1991) 146. M. M. RaoandZ. D. Ren,Theoryof OdiczSpaces(1991) 147. J.S. GolanandT, Head,Modules andthe Structuresof Rings(1991) 148.C. Small,Arithmeticof Finite Fields(1991) 149. K. Yang,Complex Algebraic Geometry (1991) 150. D. G. Hoffman et al., CodingTheory(1991) 151. M. O. Gonz~lez, Classical Complex Analysis (1992) 152. M. O. Gonzdlez,Complex Analysis (1992) 153. L. W.Baggett,FunctionalAnalysis(1992) 154. M. Sniedovich, DynamicProgramming (1992) 155. R. P. Agarwal,DifferenceEquations andInequalities (1992) 156.C. Brezinski,Biorthogonality andIts Applicationsto Numerical Analysis(1992) 157. C. Swartz,AnIntroductionto FunctionalAnalysis(1992) 158. S.B. Nadler,Jr., Continuum Theory(1992) 159. M.A.AI-Gwaiz,Theoryof Distributions (1992) 160. E. Perry, Geometry: Podomatic Developments with Problem Solving(1992 161. E. Castillo andM. R. Ruiz-Cobo, FunctionalEquationsandModellingin Scienceand Engineering(1992) 162. A. J. Jerd, Integral andDiscrete Transforms with ApplicationsandError Analysis (1992) 163.A. CharlieretaL, Tensors andthe Clifford Algebra(1992) 164.P. BilerandT. Nadzieja,Problems andExamples in Differential Equations(1992) 165.E. Hansen, GlobalOptimizationUsingInterval Analysis(1992) 166. S. Guerre-Delabfi~re,Classical Sequences in Banach Spaces(1992) 167. Y.C. Wong,Introductory Theoryof TopologicalVectorSpaces (1992) 168. S.H. KulkamiandB. V. Limaye,Real Function Algebras(1992) 169. W.C. Brown,MatdcesOverCommutative Rings(1993) 170. J. LoustauandM. Dillon, Linear Geometry with Computer Graphics(1993) 171. W.V. Petryshyn,Approximation-Solvability of NonlinearFunctionalandDifferential Equations(1993)
172. E. C. Young,VectorandTensorAnalysis:Second Edition (1993) 173. T.A. Bick, ElementaryBoundary ValueProblems(1993) 174. M. PaveI, Fundamentals of PattemRecognition:Second Edition (1993) 175. S. A. Albevedo et aL, Noncommutative Distributions (1993) 176. W.Fulks, Complex Variables(1993) 177. M.M.Rao,ConditionalMeasures andApplications (1993) 178. A. Janicki andA. Weron,SimulationandChaotic Behaviorof s-Stable Stochastic Processes(1994) 179. P. Neittaanm~ki andD. ~ba,OptimalControlof NonlinearParabolicSystems (1994) Edition 180. J. Cronin,Differential Equations:IntroductionandQualitativeTheory,Second (1994) 181. S. Heikkil~ andV. Lakshmikantham, Monotone Iterative Techniques for Discontinuous Nonlinear Differential Equations (1994) 182. X. Mao,Exponential Stability of Stochastic Differential Equations (1994) 183. B.S. Thomson, Symmetric Propertiesof RealFunctions(1994) 184. J.E. Rubio,OptimizationandNonstandard Analysis(1994) 185. J.L. Bueso et al., Compatibility,Stability, andSheaves (1995) 186. A. N. MichelandK. Wang,Qualitative Theoryof Dynamical Systems (1995) (1995) 187. M.R.Dame/,Theoryof I.attica-Ordered Groups 188. Z. NaniewiczandP. D. Panagiotopoulos,MathematicalTheoryof Hemivadational InequalitiesandApplications(1995) 189. L.J. CorwinandR. H. Szczarba,Calculusin VectorSpaces:Second Edition (1995) for Functional Differential Equations (1995) 190. L.H.Erbeet al., OscillationTheory 191. S. Agaianet al., BinaryPolynomial Transforms andNonlinearDigital Filters (1995) 192. M.I. Gil’, NormEstimationsfor Operation-Valued FunctionsandApplications(1995) 193. P.A. Gdllet, Semigroups: AnIntroductionto the StructureTheory(1995) 194. S. Kichenassamy, NonlinearWaveEquations(1996) 195. V.F. Krotov, GlobalMethods in OptimalControlTheory(1996) Identities (1996) 196. K.I. Beidaret al., RingswithGeneralized 197. V. I. Amautov et al., Introduction to the Theoryof TopologicalRingsandModules (1996) 198. G. Sierksma,Linear andInteger Programming (1996) 199. R. Lasser,Introductionto FourierSedes (1996) 200. V. Sima,Algorithms for Linear-Quadratic Optimization(1996) 201. D. Redmond, NumberTheory(1996) 202. J.K. Beem et al., GlobalLorentzianGeometry: Second Edition (1996) 203. M. Fontanaet al., Pr0fer Domains (1997) 204. H. Tanabe, FunctionalAnalyticMethods for Partial Differential Equations (1997) 205. C. Q. Zhang,Integer FlowsandCycleCoversof Graphs (1997) 206. E. SpiegelandC. J. O’Donnell,Inddence Algebras(1997) 207. B. JakubczykandW. Respondek, Geometry of Feedback and OptimalControl (1998) et al., Fundamentals of Domination in Graphs (1998) 208. T. W.Haynes eta/., Domination in Graphs:Advanced Topics(1998) 209. T. W.Haynes 210. L. A. D’Alotto et al., A Unified SignalAlgebraApproach to Two-Dimensional Parallel Digital SignalProcessing (1998) 211. F. Halter-Koch,Ideal Systems (1998) 212. N.K. Govilet al., Approximation Theory(1998) 213. R. Cross,MultivaluedLinearOperators(1998) 214. A. A. Martynyuk,Stability by Liapunov’sMatrix FunctionMethodwith Applications (1998) 215. A. Favini andA. Yagi, Degenerate Differential Equationsin Banach Spaces (1999) 216. A. I/lanes andS. Nadler, Jr., Hyperspaces:Fundamentals and RecentAdvances (1999) 217. G. KatoandD.Struppa,Fundamentals of AlgebraicMicrolocalAnalysis(1999) 218. G.X.-Z.Yuan,KKM TheoryandApplicationsin NonlinearAnalysis(1999) 219. D. MotreanuandN. H. Pave/, Tangency,FlowInvadancefor Differential Equations, andOptimizationProblems(1999) 220. K. Hrbacek andT. Jech,Introductionto Set Theory,Third Edition (1999) 221. G.E. Kolosov,OptimalDesignof Control Systems(1999) 222. N. L. Johnson,SubplaneCoveredNets(2000) 223. B. Fine andG. Rosenberger, AlgebraicGeneralizations of DiscreteGroups (1999) 224. M.V~th,Volterra andIntegral Equations of VectorFunctions(2000) 225. S. S. Miller andP. T. Mocanu, Differential Subordinations (2000)
226. R. Li et aL, Generalized DifferenceMethods for Differential Equations:Numerical Analysisof Finite Volume Methods (2000) 227. H. Li andF. VanOystaeyen, A Pdmer of AlgebraicGeometry (2000) 228. R. P. Agarwal,DifferenceEquationsandInequalities: Theory,Methods,andApplications, Second Edition (2000) 229. A.B.KharaTJshvi/i, StrangeFunctionsin RealAnalysis(2000) 230. J.M.Appellet al., Partial Integral.Operators andIntegro-DifferentialEquations (2000) 231. A. I. Pdlepkoe! al., Methods for SolvingInverse Problems in Mathematical Physics (2O00) AlgebraicGeometry for AssociativeAlgebras(2000) 232. F. VanOystaeyen, 233. D. L. Jagennan, DifferenceEquations with Applicationsto Queues (2000) 234. D. R, Hankerson, D. G. Hoffman,D. A. Leonard,C.C. Lindner, K.T. Phelps,C. A. Rodger, J. R. Wall Coding Theoryand Cryptography: The Essentials, Second Edition, RevisedandExpanded (2000) 235. S. D~sc~lescu et al. HopfAlgebras:AnIntroduction(2001) 236. R. Hagen et al. C*-Algebras andNumericalAnalysis(2001) 237. Y. Talpaert, Differential Geometry:With Applications to Mechanics and Physics (2001") Additional Volumes in Preparation
C*-ALGEBRAS AND NUMERICALANALYSIS Roland Hagen Freies Gymnasium Penig Penig, Germany
Steffen Roch TechnicalUniversity of Darmstadt Darmstadt, Germany
BerndSilbermann TechnicalUniversity of Chemnitz Chemnitz, Germany
MARCEL DEKKER, INC.
NEW YORK- BASEL
To the memoryof Siegfried PrSBdorf (1939 - 1998)
ISBN: 0-8247-0460-6 This bookis printed on acid-free paper. Headquarters Marcel Dekker,Inc. 270 Madison Avenue, NewYork, NY10016 tel: 212-696-9000;fax: 212-685-4540 Eastern HemisphereDistribution Marcel Dekker AG Hutgasse 4, Postfach 812, CH-4001Basel, Switzerland tel: 41-61-261-8482;fax: 41-61-261-8896 World Wide Web http://www.dekker.com Thepublisher offers discounts on this bookwhenordered in bulk quantities. For moreinformation, write to Special Sales/Professional Marketingat the headquartersaddress above. Copyright© 2001 by Marcel Dekker, Inc. All Rights Reserved. Neither this book nor any part maybe reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying,microfilming, and recording, or by any information storage and retrieval system, without permission in writing from the publisher. Currentprinting (last digit): 109 8 765 4 3 2 l PRINTED IN THE UNITED STATES OF AMERICA
Preface This book is devoted to C*-algebras as a tool in numerical analysis. Some readers might consider the use of C*-algebras to study properties of approximation methods as unusual and exotic. Wewould like to encourage them to read and see for themselves the powerof such techniques both for the investigation of very concrete discretization proceduresand for establishing the theoretical foundation of numerical analysis. For a general overview of the fruitful interplay between C*-techniques, concrete operator theory, and numericalanalysis and, thus, of the contents of this book, we refer the reader to the Introduction. The book is adressed to a wide audience. Wehope that it proves to be of use both for the student whowants to see applications of functional analysis and to learn numerical analysis, and for the mathematician and the engineer interested in theoretical aspects of numericalanalysis. Wewish to express our sincere appreciation to our friends and colleagues, Albrecht Btittcher, Torsten Ehrhardt, Peter Junghanns, and MarkoLindner, who read the bulk of the manuscript very carefully and not only made many corrections but also offered constructive criticism to improve the book substantially. Our students, Michael Ehrenberger and Florian Meyer, did an excellent job in drawingthe figures and performingthe test calculations. Oneof the authors (S. R.) was supported by a DFGHeisenberg grant while working the manuscript. He is grateful to the GermanResearch Foundation for this support, as well as to Bernd Kirstein and WolfgangWendlandand their staffs for their hospitality during that time. Finally, we are pleased to express our gratitude to the publisher, Marcel Dekker, Inc., and to the mathematicsseries editor, Prof. Zuhair Nashed,for inviting us to write this monograph and for their careful work on the book. Roland Hagen Steffen Roch Bernd Silbermann
Contents Preface
3
0
Introduction analysis ....................... 0.1 Numerical 0.2 Operator chemistry ....................... 0.3 The algebraic language of numerical analysis ........ 0.4 Microscoping .......................... 0.5 A few remarks on economy .................. of the contents ................ 0.6 Brief description
11 11 14 15 18 21 22
1
The algebraic language of numerical analysis 1.1 Approximation methods .................... 1.1.1 Basic definitions .................... 1.1.2 Projection methods .................. 1.1.3 Finite section method ................. 1.2 Banach algebras and stability ................. 1.2.1 Algebras, ideals and homomorphisms ......... 1.2.2 Algebraization of stability ............... Small perturbations .................. 1.2.3 1.2.4 Compact perturbations ................ 1.3 Finite sections of Toeplitz operators with continuous generating function .......................... 1.3.1 Laurent, Toeplitz and Hankel operators ....... 1.3.2 Invertibility and Fredholmnessof Toeplitz operators 1.3.3 The finite section method ............... C*-algebras of approximation sequences ........... 1.4 1.4.1 C*-algebras, their ideals and homomorphisms.... 1.4.2 The Toeplitz C*-algebra and the C*-algebra of the finite section method for Toeplitz operators .....
25 25 26 28 31 34 35 36 39 39 45 45 48 49 52 53 56
CONTENTS Stability of sequences in the C*-algebra of the finite section method for Toeplitz operators ........ 1.4.4 Symbolof the finite section method for Toeplitz operators ........................ 1.5 Asymptotic behaviour of condition numbers ......... of an operator ............. 1.5.1 The condition of norms ................. 1.5.2 Convergence 1.5.3 Condition numbersof finite sections of Toeplitz operators ........................ 1.6 Fractality of approximation methods ............. 1.6.1 Fractal homomorphisms,fractal, algebras, fractal sequences ........................ 1.6.2 Fractal algebras, and convergence of norms ..... Notes and references ...................... 1.4.3
60 61 62 63 64 65 66 67 71 73
Regularization of approximation methods 75 76 2.1 Stably regularizable sequences ................. 2.1.1 Moore-Penrose inverses and regularizations of matrices ......................... 76 2.1.2 Moore-Penrose inverses and regularization of operators ........................ 80 85 2.1.3 Stably regularizable approximation sequences .... 2.2 Algebraic characterization of stably regularizable sequences 89 89 2.2.1 Moore-Penrose invertibility in C*-algebras ...... 2.2.2 Stable regularizability, and Moore-Penroseinvertibility in ~/G ........................ 92 2.2.3 Finite sections of Toeplitz operators and their stable regularizability ..................... 97 100 2.2.4 Convergence of generalized condition numbers .... with Moore-Penrose stability ....... 103 2.2.5 Difficulties 104 Notes and references ...................... Approximation of spectra 105 105 3.1 Set sequences .......................... 3.1.1 Limiting sets of set functions ............. 106 3.1.2 Coincidence of the partial and uniform limiting set . 108 3.2 Spectra and their limiting sets ................ 110 3.2.1 Limiting sets of spectra of norm convergent sequences ........................ 112 3.2.2 Limiting sets of spectra: the general case ...... 114 sequences ............. 3.2.3 The case of fractal 117 3.2.4 Limiting sets of singular values ............ 119
CONTENTS
4
7
3.3 Pseudospectra and their limiting sets ............. ...................... 3.3.1 e-invertibility 3.3.2 Limiting sets of pseudospectra ............ sequences ............. 3.3.3 The case of fractal 3.3.4 Pseudospectra of operator polynomials ........ 3.4 Numerical ranges and their limiting sets ........... 3.4.1 Spatial and algebraic numerical ranges ........ 3.4.2 Limiting sets of numerical ranges ........... 3.4.3 The case offractal sequences ............. Notes and references ......................
119 119 125 127 128 134 134 136 140 143
Stability 4.1 Local 4.1.1 4.1.2 4.1.3
145 146 146 149
4.2
4.3
4.4
4.5
4.6
analysis for concrete approximation methods principles ......................... Commutative C*-algebras ............... The local principle by Allan and Douglas ...... Fredholmness of Toeplitz operators with piecewise continuous generating function ............ Finite sections of Toeplitz operators generated by a piecewise continuous function ....................... 4.2.1 The lifting theorem ................... 4.2.2 Application of the local principle ........... 4.2.3 Galerkin methods with spline ansatz for singular integral equations ..................... Finite sections of Toeplitz operators generated by a quasicontinuous function ....................... 4.3.1 Quasicontinuous functions ............... 4.3.2 Stability of the finite section method ......... 4.3.3 Someother classes of oscillating functions ...... Polynomial collocation methods for singular integral operators with piecewise continuous coefficients .......... 4.4.1 Singular integral operators .............. 4.4.2 Stability of the polynomial collocation method . . . 4.4.3 Collocation versus Galerkin methods ......... Paired circulants and spline approximation methods .... 4.5.1 Circulants and paired circulants ........... theorem ................. 4.5.2 The stability Finite sections of band-dominated operators ......... 4.6.1 Multidimensional band dominated operators .... 4.6.2 Fredholmness of band dominated operators ..... 4.6.3 Finite sections of band dominated operators ..... Notes and references ......................
151 158 158 163 167 169 169 173 175 177 178 183 187 188 190 191 197 197 198 200 204
CONTENTS Representation theory 207 5.1 Representations ......................... 208 5.1.1 The spectrum of a C*-algebra .............. 208 ideals ..................... 5.1.2 Primitive 210 5.1.3 The spectrum of an ideal and of a quotient ..... 212 5.1.4 Representations of some concrete algebras ...... 213 5.2 Postliminal algebras ...................... 222 algebras ........... 5.2.1 Liminal and postliminal 223 5.2.2 Dual algebras ...................... 226 5.2.3 Finite sections of Wiener-Hopfoperators with almost periodic generating function .............. 230 theory ......... 5.3 Lifting theorems and representation 238 5.3.1 Lifting one ideal .................... 238 5.3.2 The lifting theorem ................... 239 5.3.3 Sufficient families of homomorphisms ......... 243 Structure of fractal lifting homomorphisms ..... 249 5.3.4 Notes and references ....................... 254 6
Fredholm sequences 255 6.1 Fredholm sequences in standard algebras ........... 256 6.1.1 The standard model .................. 256 sequences ................. 6.1.2 Fredholm . 258 6.1.3 Fredholm sequences and stable regularizability . . . 259 6.1.4 Fredholm sequences and Moore-Penrose stability . . 260 6.2 Fredholm sequences and the asymptotic behavior of singular values .............................. 264 265 6.2.1 The main result .................... 6.2.2 A distinguished element and its range dimension . . 266 of dimImII,~ ............. 269 6.2.3 Upper estimate 270 6.2.4 Lower estimate of dimImII~ ............. 6.2.5 Some examples ..................... 276 Fredholm theory .................. 6.3 A general 282 6.3.1 Centrally compact and Fredholm sequences ..... 282 6.3.2 Fredholmness modulo compact elements ....... 288 6.3.3 Fredholm sequences in standard algebras ...... 297 6.4 Weakly Fredholm sequences .................. 305 6.4.1 Sequences with finite splitting property . ...... 305 6.4.2 Properties of weakly Fredholm sequences ...... 305 6.4.3 Strong limits of weakly Fredholm sequences ..... 307 6.4.4 Weakly Fredholm sequences of matrices ....... 313 ....................... 6.5 Some applications 314 6.5.1 Numerical determination of the kernel dimension... 314
CONTENTS 6.5.2 Around the finite section method for Toeplitz operators ........................ 6.5.3 Discretization of shift operators ............ Notes and references ......................
9
315 317 322
Self-adjoint approximation sequences 323 The spectrum of a self-adjoint approximation sequence . . . 323 7.1 7.1.1 Essential and transient points ............. 323 Fractality of self-adjoint sequences .......... 327 7.1.2 7.1.3 Arveson dichotomy: band operators ......... 333 7.1.4 Arveson dichotomy: standard algebras ........ 338 7.2 SzegS-type theorems ...................... 339 7.2.1 F¢lner and Szeg5 algebras ............... 340 7.2.2 SzegS’s theorem revisited ............... 346 7.2.3 A further generalization of SzegS’s theorem ..... 348 7.2.4 Algebras with unique tracial state .......... 352 Notes and references ...................... 354 Bibliography
357
Index
373
Chapter 0
Introduction 0.1
Numerical
analysis
The goal of functional analysis is to solve equations with infinitely many variables, and that of linear algebra to solve equations in finitely many variables. Numerical analy§is builds a bridge between these fields. The subject of numerical analysis - as we understand it - is the investigation and theoretical foundation of approximation methods for operator equations. An operator is a mapping A which associates with every element of a set X one element of a set Y, A:X~x
~Ax
E Y.
Wewill exclusively consider linear operators, that is we suppose X and Y to be linear spaces over the complexfield ~2 and require that A(~lxl ÷c~2x2) (~lAxl ÷ ~2Ax2 for all elements xl,x2 of X and complex numbers ~,~. Manyof the concrete applications of mathematics in science and technology lead finally to one of the following three basic problems for linear operator equations. Problem A. To solve equations Ax = y which are uniquely solvable. Thus, we are given an operator A : X -~ Y as well as an element y E Y, and we have to find the element x ~ X which satisfies the equality Ax = y.
(1)
If the solution of (1) exists and is unique for every right hand side y ~ Y, then A is invertible, and the solution of (1) is given by x = A-~y. 11
12
CHAPTER O.
INTRODUCTION
Problem B. To solve equations Ax =-- y which are not. uniquely solvable. Thus, either there is no x E X solving Ax = y, or there are too many solutions. In both cases, one can look for elements x E X which are generalized or weak solutions of (1) in a certain sense which has to specified. For example, if X = Y are Hilbert spaces, then a distinguished generalized solution of Ax = y, the least square solution, can be obtained as follows: amongall x ~ X which minimize IIAx-yll choose that one with minimal Ilxll. Again, the least square solution does not exist in general, but the conditions for its existence are evidently much weaker than that one for the unique solvability of (1) for all y. Indeed, if A is bounded, then the equation Ax = y has a unique least square solution for every, right hand side y if and only if the range Im A = AX of A is closed. In this case, A possesses a generalized inverse, its Moore-Penroseoinverse A+, such that the least square solution of Ax = y is given by x = A+y. Problem C. To compute eigenvalues and eigenvectors o] A. Here X = Y, and one looks for all £ ~ (2 - the eigenvalues of A - for which there exist non-zero solutions - the associated eigenvectors - of the equation Ax = Ax. A related problem is to computethe spectrum of A, i.e., the set of all A ~ C for which A - AI (with I referring to the identity operator on X) is not invertible. Clearly, every eigenvalue belongs to the spectrum. Other related problems are the computation of pseudospectra, singular values, numerical ranges, or operator determinants. A direct solution of Problems A - C (which would require knowledge of A-1 or A+, for instance) is impossible for most of the problems of practical relevance, but it is often possible (at least this will be our point of view here) for operators acting betweenlinear spaces of finite dimension, i.e. for matrices. Consequently, we will try to solve Problems A - C approximately by replacing the operator A by matrices An in a suitable manner. In order to be able to speak about approximate solutions or approximation of operators, we have to be able to measure distances in X and Y. Hence, we assume X and Y to be normed spaces, and we also suppose that the operator A maps bounded subsets of X onto bounded subsets of Y, i.e. that A is bounded. The boundedness (or continuity) of A does not automatically imply that of A-1, but if the normed spaces X and Y are complete, i.e. Banach spaces, then it does, as a theorem by Banach asserts. Observe that the boundedness of A and A-1 (and, thus, the choice of appropriate norms in X and Y) is of fundamental importance also for numerical purposes: it guarantees that small errors (caused, e.g., by the finite accuracy of the computer) remain small also after application of -1. or A
0.1.
NUMERICAL ANALYSIS
13
For the approximate solution of Ax = y, one chooses a sequence (Yn) Y of vectors which approximate the right hand side y, and a sequence (An) of operators which approximate the operator A, and one replaces (1) the approximation equations Anxn = Yn, n = 1, 2, ...,
(2)
the solutions Xn of which are sought in X (or in certain subspaces Xn of X) again. Approximation of y by Yn usually means that [[y - Yn[[v -~ 0 as n --~ oo. It is tempting to suppose that the operators An also approximate A in the norm: ][A - An][L(X,y) --~ 0 as n --~ c~, but this assumption does not work in practice. The point is that usually A acts between infinitedimensional spaces, whereas one will, of course, try to choose the An as acting between spaces of finite dimension, i.e. as finite matrices. But the only operators which can be approximated in the operator norm by finite rank operators, are the compactones, and so the restriction to norm convergence would exclude many important operator equations (and, in fact, almost all equations we will discuss in this book). The kind of approximation which fits much better to the purposes of numerical analysis is that of pointwise or strong convergence. The sequence (An) converges strongly to the operator A if I[Ax - Anx[[y -~ 0 for every x E X. This notion of convergence is on the one hand weak enough to include most of the approximations of practical interest, and it is on the other hand strong enough to make the connections between A and An not too loose. In place of the Problems A - C for the operator A, we now obtain analogues of these problems for the approximation operators An: Problem A’. Are the equations (2) uniquely solvable, and do their solutions xn converge to a solution x of equation (1)? Observe that the invertibility of (2) for small n will be without any importance since the approximation of A by An will be quite coarse for these n. So, a more precise formulation of Problem A’ would be: Does there exist an no such that the equations (2) are uniquely solvable for all n _> no and all right hand sides y, and do their solutions converge to a solution of (1)? Related questions are: Do the condition numbers condAn := IIAnll IIA~lll remain uniformly bounded? Do they even converge? Problem B~ Do the equations (2) possess unique least square solutions for all sufficiently large n and for all right hand sides y, and do these solutions converge to the least square solution of (1)? A related question is: What can be said about the convergence of the generalized condition numbers condAn:= IlAnll IIA+~II?
14
CHAPTER O.
INTRODUCTION
Problem C’ Do the eigenvalues of An (or the singular values, the points in the pseudospectrum, the Rayleigh quotients ...) approximate the eigenvalues (singular values, points in the pseudospectrum, Rayleigh quotients ...) of A? Or: What is the asymptotic behavior of the determinants of the matrices A,~? To avoid any misunderstandings, our objective here is not to ask whether, say, A127is invertible, and also not to compute the inverse of A127 on a computer, but we will ask whether Anis invertible for all sufficiently large n, and whether A~1 converges to A-1 strongly. Our objective will not be the determination of the eigenvalues of A127, but we will ask what happens if we plot all eigenvalues of At, A~,A3,... onto a commonsheet of paper. Aroundwhich sets these eigenvalues will cluster? Is this cluster set related with the spectrum of A? In which way? In other words: we are not interested in the properties of a single approximation operator An, we are only interested in the properties of the sequence (An) of approximation operators as a whole. Thus, we define: Definition 0.1 An approximation method for a linear bounded operator A : X ~ Y is a sequence (An) of operators A,~ : X -~ Y which converges to A strongly. Definition 0.2 Let (An) be an approximation method for A. This method is applicable i] there is an no such that the equations Anxn = y,~ possess unique solutions ]or all n >_ no and all convergent sequences (Yn) with limit y, and i] their solutions x,~ converge to a solution x o] Ax = y.
0.2
Operator
chemistry
In chemistry, one splits molecules into their elementary parts - the atoms - in order to create newmolecules. Similarly, it is often useful to think of a ’complicated’ operator (an operator molecule) as being composed by more elementary operators (the operator atoms). Here ’being composed’ means that the complicated operator arises by addition, multiplication, inversion, taking limits, or by other operations from the elementary operators. Consider, for example, the singular integral operator (Au)(t)
= a(t)u(t)
1 /_~ b(s)u(s) + ~r-’~ oo -~---~ ds, t e
(3)
(which is called singular due to the singularity of the kernel for s = t). It is convenient to think of A as the composed operator A = aI + SbI, where aI and bI are the operators of multiplication by the functions a and
0.3.
ALGEBRAIC LANGUAGE OF NUMERICAL ANALYSIS
15
b, and where S is the operator of singular integration along the real line: oo ~8-t ds, t E (-c~, o~). The latter operator can be further (Su)(t) = ~ 1f~-~o decomposedinto S -- FsF-1 , where F is the operator of Fourier transform on L2(IR) and s refers to the sign function. This decomposition provides a lot of information almost at once: So it is immediate for instance that $2=I. ¯ A system of operators which is closed with respect to addition and multiplication of operators and to multiplication with complex numbers is called an algebra. Thus, the singular integral operator (3) is an element of the algebra whose atoms (or, as we will say now, whose generating elements) are the multiplication operators and the operator S. But the very same operator can also be viewed of as an element of the algebra which is generated by the multiplication operators and the operators of direct and inverse Fourier transform or (if a and b are bounded functions) as element of the algebra L(L2(IR)) of all linear boundedoperators on L2(IR). The appropriate choice of the algebra is decisive. Clearly, the algebra should not be too large, but on the other hand the application of certain techniques (see Section 0.4 below) often requires algebras which are not too small (it is seldom wise to consider the operator A as an element of the algebra whoseonly generator is the operator A itself).
0.3
The algebraic language of numerical analysis
Weconsider again the singular integral operator, but nowwith integrating against the unit circle ~’. If a and b are boundedon ~’, the operator aI÷SbI is boundedon L2(~’). For the approximate solution of the integral equation
(4)
Au := (aI + Sbl)u =
we choose an orthogonal basis of L2(~?), the functions {zn}nez say, and seek approximate solutions u,~ of (4) of the form un = ~-~]k[
_
(5)
This is the prototype of what is called a Galerkin method. On introducing the orthogonal projections Pn : L2(~’) --> span {z-n,...,zn},
f ~’~ E (f’ zk) zk’
16
CHAPTER O.
INTRODUCTION
we can rewrite the linear system (5) Anun := PnAPnun = Pn(aI + SbI)Pnun
= PaY.
Hence, we can think of the approximation operators An as being composed again, e.g. by A and Pn. Since we already agreed upon considering the whole sequence (An) as the basic object (and not the single operator An), we are thus led to the idea of considering the sequence (An) as being composed, e.g. by the ’atomic’ sequences (Pn) and (A), or by (Pn), (aI), (bI) and (S): ( n)n=l
"-~
(Pn)n=l(A)~n-l(Pn)n_=l
:
(Pn)[(aI)
T (S)(bI)]
(Pn).
(6)
It is thus natural to define algebraic operations for approximation sequences, as well as to introduce algebras of approximation sequences. The following definitions are suggested by (6): For arbitrary sequences (An), (Bn) and complex numbers a we set (An)+(Bn) := ~An+Bn), (An)(Bn)
:= (AnBn),
a(An) := (aAn).
(7)
Let 9~ denote the set of all boundedsequences of operators on a fixed Banach space X. Provided with the operations (7), ~ will becomean algebra and, if a normon ~" is defined by II(An)ll := sup IIAnll, even a Banachalgebra. If (An) is an approximation method for an operator A, then the BanachSteinhaus theorem implies the boundedness of the sequence (An). Thus the algebra ~" contains every approximation method. Nevertheless, it is not yet the algebra which is adequate for the purposes of numerical analysis. The point is that the first few elements of an approximation sequence do not influence the asymptotic behavior of the sequence. Thus, it would be desirable to identify, for instance, the sequences (A1, A~, ...,
A~:~, 0, 0, ...)
and (0, 0, ...).
(8)
Algebraically seen, this requires putting all of these sequences into one ideal of $" which then has to be factored out. More precisely: The set Go of all sequences (An) with only finitely manynon-zero entries An is an ideal the algebra ~’, i.e. it is a subalgebra and every product of a sequence in Go with a sequence in ~ belongs to Go again. Modulo 60, the sequences in (8) indeed coincide. Since the ideal Go is a linear subspace of ~-, one can form the quotient space ~/6o which is a linear space again. Moreover, in ~’/60, there is a natural definition of the multiplication of cosets by ((An) + 60)((Bn) + (AnBn) + 60, whi ch makes 9 ~’/6o to an a lge bra, the quotient algebra of ~" by 60. (The independence of this definition from
0.3.
ALGEBRAIC LANGUAGE OF NUMERICAL ANALYSIS
17
the concrete choice of representives of the coset is a consequence of the ideal property.) In order to introduce a norm on a quotient algebra, and to verify the completeness of the quotient algebra with respect to this norm, one needs the closedness of the ideal factored out. In our setting, the ideal Co is not ¯ closed in ~, but it is an easy exercise to determine its closure G, which consists of all sequences (An) with IIA~II -~ 0 as n --~ oo. Clearly, ~ is again an ideal of ~, one can form the quotient algebra ~/~, and II(An)
Gll :=~.)einfg II (An) - (Gn)lly = inf su IlAn- G~II (
(~,,)e~
is a norm on ~-/G which makes the latter to a Banach algebra. It is one purpose of the present book to convince the reader on the fact that the algebra 5r/G indeed provides the adequate frame in which many of the problems of numerical analysis find their natural place. (Of course, not all problems: for instance the speed of convergence of the approximate solutions to the solution x of Ax = y does not only depend on the coset (An) + ~ (and the right hand side y) and can therefore not be reflected within ~-/6.) So, in a sense the role of ~-/G in numerical analysis can be compared with that of the algebra L(X) in operator theory. Wewant to mention here at least one point which makes this adequacy evident. For, we introduce the notion of a stable sequence. Definition 0.3 A sequence (An) E a~ is stable if the operators An are invertible, beginning with a certain no, and if the norms of their inverses are uniformly bounded. Stability of an approximation methodis closely related to the applicability of this methodas the following b~sic result shows. Theorem 0.4 (Polski’s theorem) Let A ~ L(X) be an invertible operator and (An) C_ L(X) be an approximation method for A. This method applicable if and only if the sequence (An) is stable. The next result relates invertibility problem:
the stability
problem for a sequence (An) to an
Theorem 0.5 (Kozak’s theorem) A bounded sequence (An) is stable if and only if the coset (An) + ~ is invertible in the quotient algebra jz/~. Thus, the applicability of an approximation method (An) is essentially equivalent to the invertibility of the coset (An) + G in the Banach algebra
y/a.
18
0.4
CHAPTER O.
INTRODUCTION
Microscoping
The translation of stability problems into invertibility problems in Banach algebras offers the possibility of employinggeneral invertibility theories (such as Gelfand’s theory for commutative Banach algebras) to study the applicability of numerical methods and, actually, this has been the main reason for introducing algebraic concepts into the world of numerical analysis. To explain what is meant, consider once more the Galerkin method (P,~(aI+SbI)Pn) for the singular integral operator on the unit circle ~, and suppose first that a and b are continuous functions on ~?. Wewill think of this approximation sequence as an element of the smallest closed subalgebra of the algebra :~ (consisting nowof all boundedsequences (A,~) of operators on L2(~I’)) which contains the sequences (Pn), (S) and all sequences (cI) with c E C(~). Clearly, this algebra also encloses all sequences of the form (Pn(aI
+ ~S)P,~)
with a,~ E C
(9)
which correspond to the Galerkin method for singular integral operators with constant coefficients. Naturally, it proves to be mucheasier to study the stability of the sequences (9) with constant coefficients rather than the stability of sequences with arbitrary continuous coefficients. This leads to the obvious idea to try to reduce the study of approximation methods for operators with continuous coefficients to that of approximation methods for operators with constant coefficients, possibly by freezing in the coefficients, i.e. by replacing the functions a and b by their values a(A) and b(A), which has to be done for every point A ~ "~. Is it possible in this way to replace a complicated stability problem (that for the sequence (P,~(aI + SbI)Pn) for instance) by a whole family of much simpler stability problems (those for the sequences (Pn(a(A)I + b(A)S)P,~) with A running through ~ in our setting)? This idea (which has its origins in operator theory) proves to be x;ery fruitful. It is indeed possible (although not obvious) that this programme can be carried out for large classes of approximation methods for large classes of operators (including the Galerkin method for singular integral operators with continuous coefficients). In simple situations, an elementary partition of unity will suffice to decomposea complicated ’global’ invertibility (or stability) probleminto a family of ’local’ problems, and glue the results for the local problems together to obtain the solution for the global problem. This quite naive decomposing and glueing ’by hand’ denies for more complicated sequences. If, for example, the coefficients a, b of the singular integral are discontinuous at some points A ~ ~ (if they have jumps or
0.4.
MICROSCOPING
19
oscillations there), then it is already not clear what the ’right local representations at A’ should look like (but it is clear that simple evaluation at A will not provide local representatives). Roughlyspeaking, one has to consider two coefficient functions as locally equivalent at the point ~ E ~7, if they appear as almost equal whenlooking through a microscope directed to the point )~, and if the coincidence gets better whenever we increase the magnification. For example, the ’very different’ functions f and g in Figure 1, which both have a jump at ~ E ~, coincide locally at A.
10x
1000x
Figure 1: Microscoping Also the functions ] and g in Figure 2 coincide locally at ~ (which becomesevident by taking into account that the difference of coefficient functions is measured in the supremum norm), whereas the functions and g in Figure 3 are not locally equivalent at A.
Figure 2: Locally equivalent functions Moreover,it turns out that certain kinds of oscillating functions (quasicontinuous functions e.g.; see Section 4.3) behave locally as constant func-
2O
CHAPTER O.
INTRODUCTION
Figure 3: Not locally equivalent functions
tions again. But to see this, one needs a much stronger instrument than a commonlight microscope, an electron microscope say, which shows that a quasicontinuous function (which can oscillate at the points of ~) can identified with a continuous function on a certain ’balk’ (Figure 4) and, thus, localizing over this balk (and no longer over the unit circle) provides constant functions as local representatives.
Figure 4: Localization of quasicontinuous functions It is obvious that one needs a machinery which formalizes the intuitive notion of local equivalence and which can take the place of the ’decomposing and gluing by hand’. Such machineries are well known, and the most convenient and elegant of them are formulated in the language of Banach algebras. Here is one of these machineries: Theorem 0.6 (Allan’s local principle) Let ~4 be a Banach algebra with identity e, and let B be a closed subalgebra in the center o].4 which contains e. For every maximal ideal x o] l~, let Is denote the smallest closed ideal o] A which encloses x. Then an element a E ,4 is invertible in A if and
0.5. A FEW REMARKS
ON ECONOMY
21
only i] the cosets a + Ix are invertible in A/I~ ]or all maximalideals x with I~A. The whole Chapter 4 is devoted to this theorem and its several applications. Here we only reveal that the maximalideals x just correspond to the points of the unit circle (for coefficients with jump discontinuity) or to the ’balk’ (for quasicontinuous coefficients), that two approximation sequences coincide locally at x if and only if their difference belongs to the ideal Is, and that the cosets moduloIs are the ’right’ local representatives.
0.5
A few remarks
on economy
As a rule, every Banach algebra of approximation sequences will contain manymore sequences than those which we were previously interested in and which gave rise to the construction of the algebra. So, in manyapplications the concrete sequences we want to examine are just the generators of the algebra, but the algebra obviously also contains sums of products of its generators. Moreover, new elements will arise in the process of completing the algebra (or of closing it within a larger algebra), and these newelements are often of a quite different nature than their generators. To have an example: the smallest closed subalgebra of 3v which contains all Galerkin sequences (Pn(aI + SbI)Pn) with a,b E C(T) contains not only all sums of products ~i I’Ij(Pn(aiJ I + SbijI)P,~), but also all sequences (P,~KP,~) where K is compact on L2 (T). Since we need complete algebras in order apply Allan’s local principle, we cannot avoid these new and (at the first glance) unwelcomeelements. Hence, in order to obtain stability results for a few special sequences, we will require whole Banachalgebras of sequences, in which most elements lie outside our previous interests. So one might ask whether there are other, more economic, approaches which only deal with the sequences we are really interested in. The first answer is that there are manystability problems for approximation methods which can actually be investigated only by the algebraic approach via local principles; so there is indeed no other choice of approaches at the moment. The second answer is that the very same approach which allows us to study the stability of the generators of the algebra, in manysituations also allows us to examinethe stability of an arbitrary sequence in the algebra. In other words: we often comeinto a situation which allows us to be able to compute the spectrum with respect to invertibility in 9r/~ of an arbitrary coset (An) ÷ of thealge bra of a pproximation methodswe are considering. So one often gets stability criteria for other interesting approximation sequences almost automatically. For some typical instances see [77] where, based on approximation sequences for singular
22
CHAPTER O. INTRODUCTION
integral operators with piecewise continuous coefficients, a Banachalgebra is defined and studied, which besides its generators also contains approximation methods such as quadrature or collocation methods for Mellin operators, and where the derived stability criteria are of a form which applies both to the parents of the algebra and to the new membersof the family. But the real importance of the latter facts only becomes clear if one considers C*-algebras of approximation sequences. A Banach algebra is C* if there is an involution a ~ a* on the algebra such that [[aa*l] = I[a[I 2 for every element a. The algebra ~- of all bounded sequences (An) of operators on the Hilbert space L2(~") is a C*-algebra with respect to the involution (An)* := (A~), and also its smallest closed subalgebra A containing all sequences (Pn(aI + SbI)Pn) with a, b E C(~’) is C*. The point of the C*-setting is that the knowledgeof a suitable invertibility (-- stability) criterion will enable us to describe the algebra completely in the following sense: Wecan construct a mapping from the algebra into another, in some sense simpler, C*-algebra which preserves the algebraic and metric structure, i.e. the mappingis a so-called *-isomorphism. In the case of the algebra .4 defined above, the algebra .A/G proves to be *-isomorphicto a C*-algebra, the elements of which are triples (B1, B2, B3) of operators on L2(~I’). So, instead of working with cosets of (infinite) sequences, one can simply deal with triples of operators! This isomorphy also opens a way to tackle a whole series of other problems (including the problems B’ and C’ mentioned above). Thus, the description of concrete algebras of approximation sequences will occupy a main place in this book.
0.6 Brief description
of the contents
Weconclude this introduction by a short description of the contents of the several chapters of the book. The first three chapters are devoted to the problems A’-C’ for approximation sequences, respectively. Their main goal is to point out the close relationship between these problems and certain properties of the coset (An) + in the quotient alge bra 5v/G, thus highl ighting the o utst anding role of this algebra in numerical analysis. For problem A’ this connection is roughly explained above. Parallel to this we single out a special class of subalgebras of 9v which we call fractal. The reason for this notion is that whenever (An) belongs to a fractal algebra A then every infinite subsequence of (An) contains all essential information about the sequence (An) itself or - more precisely the knowledgeof an infinite subsequence of (An) allows us to reconstruct (An) within .4 up to a sequence in
0.6.
BRIEF DESCRIPTION OF THE CONTENTS
23
The property of fractality proves to be of a similar fundamental importance as that of stability. Particularly, it guarantees that several approximations can be done uniformly. This will be illustrated for the convergence of the condition numbers in Section 1.6, for the approximation by generalized invertible matrices in Chapter 2, and for the asymptotic behavior of eigen- and singular values in Chapter 3. The applicability of the results of Chapters 1-3 to a concrete approximation method (A,~) depends essentially on the possibility of embedding (An) into a C*-subalgebra of ~- which can be described completely. Weare thus led in a natural way to the investigation of concrete C*-subalgebras of ~’, and this will be our subject in Chapter 4. The heart of this chapter is the construction of symbol mappingswhich, for instance, associate with every sequence in the C*-algebra generated by the Galerkin method for singular integral operators with continuous coefficients a certain triple of operators, in such a waythat the stability of a sequence, or its eigenvalue asymptotics, only depend on the symbol of the sequence. In the fifth chapter we consider these concrete examples once more, now in the light of the general representation theory of C*-algebras. Particularly we will point out that some features of the concrete algebras which seem to be incidental at the first glance, are actually consequencesof somequite general hypotheses on approximation algebras. The sixth chapter is devoted to a more special but fascinating property of many concrete algebras of approximation sequences, namely the existence of a Fredholmtheory with index calculus for the elements of the algebra. For this goal we introduce such notions as ’kernel dimension’ or ’cokernel dimension’ as well as ’index’ for approximation sequences (An) and then point out howthese notions are related to the asymptotics of the singular values of A,~ as n tends to infinity. In Chapter 7 we deal with a finer analysis of the eigenvalue distribution in case of self-adjoint sequences (An). Particularly, we present Arveson’s results culminating in a generalization of the Szeg5 limit theoremfor finite sections of self-adjoint Toeplitz operators to self-adjoint operators which are almost band operators with respect to the selected basis for the finite section method. The logical dependenceof the several chapters is as follows: Since this is a book about the interplay between functional analysis (operator theory, C*-algebras) on the one hand, and numerical analysis the other hand, but neither a book about functional nor numerical analysis, somebasic knowledgeof the latter is assumed(although all needed facts are cited exactly and are provided with references). The assumed material from functional analysis is completely covered by Cryer [39] (the view of which is very close to that we take), Douglas [50] (in which the use of Banach
CHAPTER O.
24
INTRODUCTION
5
Figure 5: Dependence of the contents algebra techniques in operator theory is explained), Reed/Simon[127], or Rudin [154], and for the numerical side of the coin we recommendGohberg/Feldman [64], Lebedev [101], or Tyrtyshnikov [175]. A presentation on a quite elementary level of the finite section methodfor Toeplitz operators (which serves as one main model throughout the present book) as well as related questions can be found in the recent text book BSttcher/Silbermann [27].
Chapter 1
The algebraic language numerical analysis
of
Numericalproblemsinvolving infinite dimensional operatorsrequire a formulationin terms of C*-algebras. WilliamArveson The goals of this chapter are to makethe readers familiar with the algebraic language and its dialect spoken in numerical analysis and to introduce two fundamental notions: the stability and the fractality of an approximation sequence. Further we present an approximation method which will accompany us throughout this book and which is without any doubt the most natural and most important approximation method for bounded linear operators on a separable Hilbert space: the finite section method.
1.1
Approximation
methods
Westart with a brief description of the basic subject of this book, approximation sequences, and proceed with two concrete approximation methods. The present and forthcoming section are the only places where we deal with operators acting on (arbitrary) Banach spaces. 25
26
CHAPTER 1.
1.1.1
Basic
THE LANGUAGE OF NUMERICAL ANALYSIS
definitions
Let X be a Banach space over the complex field C. Given a linear bounded operator A on X and an element f of X, consider the operator equation
Au= I.
(1.1)
For the approximate solution of this equation, we first choose appropriate closed subspaces Xn of X in which the approximate solutions un of (1.1) will be sought. In practice, the Xn usually have a finite dimension, but we will not require this at that point. Our only assumption for the moment is .that the Xn are ranges of certain projection operators Ln : X -+ Xn, and that these projections converge strongly (i.e. pointwise) to the identity operator: s-limn-~Ln = I. Recall that a projection is an operator L such that L2 = L. The strong convergence of Ln to I implies that the union t~=lXn is dense in X. Having fixed the subspaces Xn, we choose linear operators An : Xn ~ Xn and consider in place of (1.1) the equations Anun = Lnf,
n = 1,2,3,...
(1.2)
with their solutions sought in Xn = Im L,~. Of course, we have to assume some consistence between the operator A and its ’approximations’ An. The weakest requirement we will impose is that the sequence (An)nCX)=l is an approximation method for A in the following sense: Definition 1.1 A sequence (An) of operators An L(Im Ln) is an approximation method for A e L(X) if AnLn converges strongly to A Even if (An) is an approximation method for A, then we do not yet know anything about the solvability of the equations (1.2) and about the relations between (possible) solutions un of (1.2) and the (possible) solution (1.1). Thus, we distinguish the special class of applicable approximation methods. Definition 1.2 The approximation method (A,~) for A is applicable i] there exists a number no such that the equations (1.2) possess unique solutions Un ]or every n >_ no and every right hand side f ~ X and i] these solutions converge in the norm of X to a solution of (1.1). For an equivalent characterization of applicable approximation methods we still introduce the notion of stability of a sequence of operators.
1.1.
APPROXIMATION METHODS
27
Definition 1.3 A sequence (An) of operators there exists a numberno such that the operators ANare invertible for every n >_ no and if the norms of their inverses are uniformly bounded: sup ~__~n 0
The following b~ic result connects these notions. Theorem 1.4 (Polski) Let (Ln) be a sequence of projections which converge strongly to the identity operator, and let (A,) with A~ L(Im Ln) be an approximation method for the operator A e L(X). This method applicable if and only ff the operator A is invertible and the sequence (An) is stable. ProoL Let A be invertible and let (A~) be stable. Then, for all sufficiently large n and all x ~ X,
+ ~]Lnd-lx - A-~z~], which implies the strong convergence of A~Ln to A-~ and, thus, the applicability of the method (An). Let, conversely, (A~) be an applicable approximation method for Then, by definition, the operators A~ are invertible for large n, and the sequence (A~IL~) of their inverses is strongly convergent. So, the BanachSteinhaus theorem (= the uniform boundedness principle) entails the stability of the sequence (An). In order to check the invertibility of A recall first that the definition of an applicable methodrequires the solvability of the equation Au = f for every right h~d side f. Hence, A is onto. For the injectivity of A observe that, for all sufficiently large n and all x ~ X
Since the norms ]]A~Ln~] are uniformly bounded, one obtains the convergence A~LuAx ~ x for every x ~ X. If, in particul~, x ~ Ker A then necessarily x = 0. Thus, for a sequence (A~) to be an applicable approximation method for an operator A, three points are decisive: ¯ strong convergence of A,~L,~ to A,
28
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
¯ invertibility of A, ¯ stability of (An). In manyapplications, the strong convergence of A,~L,~ to A is more or less evident (see the following subsections), and the invertibility of operators belongs to the topics of operator theory which will concern us only in as muchas we will cite the needed results. So, our main attention will be paid to the stability problem. Let us still mention that, whenever(An) is an applicable approximation method for an operator A and (fn) is any sequence of elements fn E Im Ln which converges to f, then the equations Anun = fn are uniquely solvable for all sufficiently large n, and their solutions converge to the solution of Au = f. This follows from the estimate
the right hand side of which tends to zero as n ~ ~. 1.1.2
Projection
methods
Let X be a Banach space, A a bounded linear operator on X, and (L~) a sequence of projections converging strongly to the identity I ~ L(X). The idea of any projection method for the approximate solution of (1.1) is to choose a further sequence (R~) of projections which also converge strongly to the identity and which satisfy Im Rn = Im L~ (of course, one can take Rn = Ln also), and to choose A~ = R,~AL~ : ImL~ -~ ImL~ as approximate operators of A. That (RnALn) is indeed an approximation methodfor A is a consequence of assertion (a) of the following lemma, the proof of whichis left as an exercise. Lemma1.5 Let X be a Banach space and A, B, C, An, Cn be bounded linear operators on X. (a) If A,~ -+ A and Cn -+ C strongly, then A,~BC,~ -~ ABCstrongly. (b) If A~ -~ A and C~ --~ C* strongly and i~ B is compact, then IIAnBC,~ ABCII ~ 0 as n ~ o~. Assertion (b) of the preceding lemmaimplies a first stability result. Theorem 1.6 Let X be a Banach space, and let (Ln) and (Rn) be quences of projections on X with Im R~ =Im L,~ and L~ ~ I, L~ -~ I* and R,~ --~ I strongly as n --~ o~. If A is the operator aI + K with K compact on X and a ~ C~, then the projection method (RnALn) applies A if and only if A is invertible.
1.1.
29
APPROXIMATION METHODS
Proof. Weonly consider the case where X has infinite dimension. If A is invertible, then a ~ 0, and it is evident that the sequences (RnALn) (aLn + RnKLn), consisting of operators acting on Im Ln, and (RnAL,~ a(I - L,~)), consisting of operators on X, are stable or not only simultaneously. The stability of the latter sequence is an immediate consequence of the equality [[A - R~AL~- a(I - L~)[[
= IlaX + K -
aL~ - RnKL~- a(I -
L~)II = IlK - R~KL~II,
of Lemma1.5(b), and of a Neumannseries ~gument applied to the invertible operator A. The converse statement follows from Polski’s theorem. Example 1.7 Let X be the Lebesgue space LP[O, ~) with 1 < p < ~, I the identity operator on X, K the integral operator (Ku)(t)
=
k(t,s)u(s)ds,
[0,~ ),
and let A = aI + K with some a 6 C. If a ¢ 0 and K is compact, then A is a ~edholm operator of second kind. In particular, K is compact on LP[0, ~) if the kernel function k satisfies Ik(t,s)lqds
dt < ~
(1.3)
with l/p+ 1/q = 1, in which case K is a so-called Hille-Tamarkin operator For n = 1, 2,... let L~ stand for the operator on LP[0, co) of multiplication by the function Xl0.nl which is 1 on [0, n] and 0 on (n, oo). Evidently, L~ is a projection operator, and Ln -~ I, L~ -~ I* strongly as n -~ oo. By Theorem1.6, the projection method (L,~AL~) is applicable to A if and only if A is invertible. Hence, for invertible A, the equations aun(t) + k(t,s)u~(s)
= f (t ), t e
[O,n
(1.4)
are uniquely solvable for all sufficiently large n and all f E LP[O,oo), and their solutions converge in the normof LP[O, oo) to the solution of
au(t) + k(t,s)u(s) = ](t ), t e [0,~ In this example, the spaces Im Ln = L~[O, n] still have infinite dimension, and so a further discretization (e.g. by a quadrature rule) is needed solve (1.4) numerically.
30
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
Example 1.8 Weconsider the same operators as in Example 1.7, but now on the Hilbert space L2[0, c~) with standard inner product/., .). In the case p = 2, condition (1.3) reduces
~o
~ ~o°~ Ik(t, s)l 2 dsdt < c~,
(1.5)
and integral operators K with kernel functions k satisfying (1.5) are called Hilbert-Schmidt operators. The functions en(t) = e-t/2 ],~(t), n 0, where t fn(t) =e [~~jd ~n(t’ne--t ~ j refers to the n th Laguerre polynomial, constitute an orthonormal basis of the Hilbert space L2[0, c~). Thus, if we let Ln denote the orthogonal projection from L2[0, ~x~) onto the span of the functions co,el,... ,e,~_~, then L,~ = L~ -~ I as n --~ oo, and (LnAL,~) is an approximation methodfor A which is applicable if and only if A is invertible. In this setting, we look for an approximate solution un in the form A~) and the nth approximation equation for ~t n ~_ c(on) eo -~ ... -~ (~n_l~n_l, Au = f is just the linear n x n system n--1
~(Aei,ej)cl’O
= (f,
ei),
j=O,
1,...,n-1
i=O
with the unknowns -(~) . Here we chose f~ = Lnf as an approximation of t; i the right hand side. ¯ Example 1.9 Let ID = {z ~ C, Izl < 1} denote the unit disk, and consider the Hilbert space L2 (lI)) of all functions f on I~ with
Ilfll ~ = If(z)[2dA(z)
If(rei~)lerdrdt < c~.
The Bergman space A2(~) consists of all functions in L2(ll)) which analytic on I~. The Bergmanspace is a closed subspace of L2(I~), i.e. Hilbert space again. One can show that the functions kek(z) = kv~--~-~z with k = 0, 1, 2,... form an orthonormal basis of A~(I~). Let L~ denote the orthogonal projection from A2(~) onto the span of eo,e~,...,e,~. Further, for n _> 0 set ~,~ := exp(2ri/(n 1)), an choose p ~ (0, 1). Then the interpolation projection R,~ from A~(D) onto span{co,.., e~} is the operator which associates with every function f A~(ll)) a function Rnf e span{co,..., e,~} such that (R,~f)(p~k~) for k = O, 1,...,n. It is again obvious that Ln = L~ -+ I. Moreover, in this special setting one even has IIL~- n,~ll --~ 0 as n-+ (x)
(1.6),
1.1.
APPROXIMATION
METHODS
31
which implies that Rn -~ I. (Observe that (1.6) is a peculiarity of Bergmanspace projections Ln and Rn which, in general, is not typical for the relations between orthogonal and interpolation projections.) Consequently, if K is compact on A2(]~) and A aI+K with so me a ¯ C\{0} then the collocation method (RnALn) is an approximation method for A, and this methodapplies if and only if A is invertible. The solution u~ = ?-,i=0 ci ei of the equation R~AL~u~= R~f can be determined by solving the (n + 1) x (n + 1) linear system ~(Ae~)(p¢~)c~ ~) =
f(pe~), j = o, 1,...,n
for the unknowns’~) c~ 1.1.3
Finite
section
method
The finite section methodis a special projection methodwhich we will only consider on a Hilbert space. Let H be an infinite-dimensional separable Hilbert space with inner product (., ./and normIlxll~/= (x, x). For a given orthonormal basis (en)n>o of H, let P,~ denote the orthogonal projection oo from H onto span{eo,... ,e,~}. Thus, if x ¯ H and if x = ~k=o(X, ek)ek is the Fourier series expansion of x, then P~x = ~kn__o(X, ek)e~. Clearly, P~ = P,~ -~ I strongly. The approximation method (P~APn) is called the finite section method for A ¯ L(H) (with respect to the given basis To visualize the notion ’finite section method’ recall that, due to the Parseval identity [[xl[ 2 = ~°=0 [(x, ea)l 2, every element of H can be identified with the sequence of its Fourier coefficients. Moreprecisely: If 12 denotes the Hilbert space of all sequences (xk)~=o of complex numbers with norm[[(Xk)[I = (~-]~ Ixk[2) 1/2, then the mappingC: x ~, ((X, ek))~°=O is an isometry from H onto 12. Further, the operator equation Au = f on H is translated by this -1 Cu = Cf on 12: isometry into the equation CAC (Aeo,el)
(Ae~,el)
(u,e~)
__ (f,:e~)
.
(1.7)
The same correspondence transfers the approximate equations P~APnu~-Pnf into the equations Anun -- ]~ where , Ao = ((Aeo,eo)),
, ((Aeo,eo) A1 = (Aeo,e~)
(Ael,el)
32
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
and , , ( If, e0) f~ = ((f,eo)),fl = \ If,~1). Thus, the A~ are indeed the ’finite
sections’ of the system matrix -1 CAC
of(1.7). Theorem 1.10 Let H be an infinite-dimensional separable Hilbert space. (a) If A is an invertible operator on H, then there exists an orthonormal basis of H such that the finite section method with respect to this basis applies to A. (b) IrA = B+iS where B is positive definite and S is self-adjoint, then the finite section method with respec* to every orthonormal basis of H applies to A. Proof. A proof of (a) can be found in [64], Chapter II, Theorem4.1. For a proof of (b), let {ei} be an orthonormal basis of H, and let Pn denote the orthogonal projection from H onto span{e0,...,en}. For all x E H one has (PnAPnz, Pnx) = (APnx, Pnx) = (BPnx, Pnx) + i(SPnx, Since (BPnx, Pax) and (SPnx, P,~x) are real, this identity implies ](P~APnx, P,,x)] >_ I(ePnx, Pnx)[. Further, due to the positive definiteness of B, there is a C > 0 such that ](P~APnx, P~x)] >_ I[P,:ll z
for al l z E H,
which, via the Cauchy-Schwarzinequality, yields ]IPnAPnxl] ~ C]lPnxl] for all x e H. Hence, all matrices PnAP,~ are invertible, and the norms of their inverses are uniformly bounded by 1/C. ¯ Assertion (a) of the preceding theorem gives rise to at least two basic problems: ¯ Given an invertible operator A on H, determine a basis of H such that the finite section methodwith respect to this basis applies to A. ¯ Given an invertible operator A on H and a basis of H, does the finite section method with respect to this basis apply to A ? Wewill exclusively discuss the second question; mainly for the following reason: many operators (among them most of the concrete operators appearing in this book) possess their own ’natural’ basis, and any essential change of this basis woulddestroy the ’structure’ of the operator. A trivial exa~nple is provided by the diagonal matrices on l 2. Here is a less obvious example.
1.1.
APPROXIMATION
33
METHODS
Example 1.11 An operator S on a Hilbert space H is called a shi]t operator if it is an isometry and if (S*) j -~ 0 strongly as j -~ c~. Let K := Ker S*. One can show that SJK ± SkK whenever j ~ k and, moreover, that every x E H allows a unique representation as a sum ~-~j=o SJkJ with elements kj E K. Thereby, kj = Po(S*)Jx, where Po = I - SS* is the 2orthogonal projection from H onto K, and [[x[[ = ~’]~j~--o []kJ[[ Nowsuppose in addition that dimK= 1, let e0 be a unit vector in K, and set ej := SJeo. Then {ej}j~=0 is an orthonormal basis of H which is, in a sense, the ’natural’ one for S. The ’translation’ of S into an operator on -1, acts via (xo,xl,x2,...) 12, i.e. the operator CSC ~ (O, xo,xl,x2,...), which emphasizes the naturalness of this basis and also explains whyS is called a shift. Let us further mentionthat the ’translation’ of the operator polynomial ~-~-1_ k cj(S*) -j + ~=o c~Sj is the matrix ~Co
C--I
C--2
...
C--k
Cl
CO
C--I
¯¯
C~k+l
C2
Cl
CO
¯.
C-k+2
:
:
Ck
Ck-i
0
ck
C--k+l
: Ok-2
C--1
c~-1
which is the simplest exampleof what is called an infinite or a Toeplitz operator on 12.
Toeplitz matrix ¯
Further realizations of the finite section methodare the sequences (L,~AL,~) where L~ is as in Examples 1.8 and 1.9. If A is an invertible operator of the form aI ÷ K with K compact, then these finite section methods are even applicable. The applicability of the ’natural’ finite section methodto Toeplitz operators will be studied in the forthcoming Section 1.3. Let us consider one more example. Example 1.12 The operator
Ao
~
[0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 1 0 0 :
0 0 1 0 0 0
0 0 0 0 0 1
0 .. 0 0 0 1 0
.. .. .. .. --
2) C L(l
34
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
is selfadjoint and unitary, but its finite sections PoAoPo,P2AoP2,P4AoP,~, ... (with respect to the standard basis (e~)~=o of/2) all contain a zero row and are therefore not invertible. Nowmodify Ao as follows: let ~ = (Ca), be a sequence of positive numbers with limit 0, and set ~o 1 0 0 A~ = 0 0 :
1 0 So 0 0 ~1 1 0 0 0 0 0 :
:
0 0 0 0 0 0 0 0 ¢2 1 1 ~2 :
:
¯ L(/2).
..
If we further assume that en _< 1/2 then, since 1 en
=
1 _ 1 < 2, max(1 + ~n, 1 - ca) 1 - cn -
the operator A~is invertible, and I]A[1 I] -< 2. Moreover,’all finite sections PnA~Pnof A~ are invertible, and ]](P,~A¢P~)-IPnl] _< 2 whenevern is odd, but the normsI](P,~A.~P,~)-IP,~I] are are at least 1/¢,~ in case n is even. Thus, although both A~ and all its finite sections are invertible, one has supn ]](P,~A~P,~)-~P,~I] = c~, and the finite section methodwith respect to (en) is not applicable to A~. Observe on the other hand, that the finite section method for Ao with respect to the basis (f~)~=0 with f2n = (e2n + e2,~+~)/x/~, f2n+~ = (e2,~ e2,~+~)/x/~ applies; the matrix representation of Ao with respect to this basis is the diagonal matrix diag (1, -1, 1, -1,...). It is its simplicity and universality which, distinguishes the f’mite section method from other approximation methods. Mainly for this reason, the investigation of the finite section methodfor several classes of operators has ever played a pioneering role in the development of (algebraic methods in) numerical analysis. Also in the present book, the finite section methodwill serve both as a source of inspiration and as a basic examplefor illustrating the abstract theory.
1.2 Banach algebras
and stability
As indicated in the introduction, we will study stability problems by translating them into invertibility problems in Banach algebras. The present section provides the fundamentals for this.
1.2. BANACH ALGEBRAS AND STABILITY 1.2.1
Algebras,
ideals
and
35
homomorphisms
An algebra is a complexlinear space B with an additional operation B x B -~ B, (a, b) ~ ab, called multiplication, which satisfies the following axioms for all a, b, c E B and A E C: (ab)c = a(bc) (associativity), (a+b) c = ac+bc, a(b+c) = ab+ac (distributivity), (Aa) b = a ()~b) = )~ An element e ~ B is called unit element or identity if ae = ea = a for all a ~ B. The unit element is unique if it exists. Algebras which possess a unit element are called unital. If B is a unital algebra with unit element e, then an element a ~ B is invertible if there is an element b E B such that ab = ba = e. -1. The element b is unique and will be denoted by a Obviously, (a-l) -I -- a, (ab) -1 -~. = b-la The set of all A ~ C such that e - Aa is not invertible is called the spectrum of a in B and is denoted by a~(a) or, simply, by a(a). A subset of an algebra whichis (with respect to the inherited operations) an algebra again, is called a subalgebra of the given algebra. A subalgebra ~ of an algebra B is an ideal if bk ~/~ and kb ~/~ for all b ~ B and k ~ ]C. The algebra B and the set (0} are the trivial ideals of B. Given an algebra B and an ideal ]C of B, one can form the quotient B//~, which is the set of all cosets of elements of/~ modulo~. There is a natural linear structure on B/~ which makes this quotient to a linear space. Moreover, provided with the multiplication (a + ]~)(b ÷/~) := ÷ ~, thi s lin ear spa ce becomes an algebra again, and e ÷/(: is the identity element of B/tg if e is the identity of B. Let B~, B2 be algebras. A homomorphism W from B1 into B2 is a mappingwhich reflects the algebraic structure, i.e. Wis a linear mapping, and W(ab) = W(a)W(b)for all a, b e B~. In case B1 and B~. are unital with unit elements el and e2, respectively, the homomorphismW: B1 -~ B2 is said to be unital if Wel = e2. A homomorphismwhich is invertible is an isomorphism, and algebras with an isomorphism between them are called isomorphic. Note that there is a close connection between ideals and homomorphisms: The kernel Ker W= {a E B~ : Wa = 0} of every homomorphism is an ideal of B] and, conversely, given an ideal ]C of an algebra ~, there is an algebra B2 as well as a homomorphismWfrom/~1 onto B~ such that E is the kernel of W. For, choose/~2 := B]//~, and let Wbe the canonical homomorphism W : B~ --~ B]//C, a ~-~ a + tC.
CHAPTER 1.
36
THE LANGUAGE OF NUMERICAL ANALYSIS
An algebra B is normedif it is a normed linear space, and if
Ilabll ~ Ilallllbll forall a,
beI~
(continuity of the multiplication). If B is unital with unit element e then we require in addition that lie[] = 1. If the underlying linear space of a normed algebra is a Banach space, then the algebra is called a Banach algebra. The perhaps most important property of a unital Banach algebra is that the spectrum of an element is a compact and non-empty subset of the complex plane. The natural substructures of Banach algebras are its closed subalgebras and closed ideals, and its natural morphisms are the continuous homomorphisms. Observe that the duality between ideals and homomorphisms discussed above involves a duality between closed ideals and continuous homomorphisms.Further, if B is a Banach algebra and K: is a closed ideal of B, then the quotient algebra becomes a Banach algebra on defining a normvia []a + K:]] := infke~: []a + k[]. Clearly, the canonical homomorphism from B onto B/]~ is continuous and has norm 1 in this case. A prominent example of a Banach algebra is the algebra L(X) of all bounded linear operators on some Banach space X. This algebra is unital, and its unit element is the identity operator I. If X is infinite-dimensional, then the set K(X) of the compact operators on X is an example of a nontrivial closed ideal of L(X), whereas the operators of finite rank form a non-trivial non-closed ideal. The quotient algebra L(X)/K(X) is called the Calkin algebra of X. An operator A e L(X) is invertible in L(X) if and only if Im A = X and Ker A = {0) (Banach’s theorem), whereas the coset A + K(X) is invertible in the Calkin algebra L(X)/K(X) if and only if A is a Fredholm operator, i.e. if the range Im A of A is closed, and if dim Ker A < oo and dim (X/Im A) < o~ (Calkin’s theorem). 1.2.2
Algebraization
of stability
Let X be a Banach space and (Ln) be a sequence of projections on X with strong limit I as n -~ c~. Let ~- refer to the set of all sequences A( ~o n)n=o of operators An E L(ImL,~) which are uniformly bounded: supn>0 [[AnLn[I < oo. The natural operations (An)+ (B~) := (A,~ + B,~),
(An)(Bn) := (AnB,~), A(An) := (AAn)
make 5r to an algebra. This algebra is unital with identity (I[ImL,), and can be normedon defining II(A~)ll:-- supn_>0IIA~L~ll.
37
1.2. BANACH ALGEBRAS AND STABILITY Proposition 1.13 9~ is a Banach algebra: Proof. Let ((A~m))n>0),~>o be a Cauchy sequence in ~-, that is, e > 0 there is an N such that supllA(~m)Ln-A(~k)L~ll~_¢
forall
k,m>_N.
(1.8)
n
In particular, (A(~m)),~_>0is a Cauchysequence for every fixed n and, thus, convergent. Set An~ := limm-~oA(~m). Letting m go to infinity in (1.8) one obtains sup~ IIA~Ln - A~)Lnll <_ ~ for all k _> N. This shows that the sequence (A~) belongs to ~ and t hat t he s equences (A(nk))n>o converge t o (A~) as k -~ ~o in the norm of v. ¯ Since every approximation method is a bounded sequence by the BanachSteinhaus theorem, we can regard every approximation method as an element of the algebra ~’. As indicated in the introduction, there are good reasons for identifying sequences in Y which differ in a finite numberof entries only. For this goal we introduce the set 6 of all sequences(Gn)in ~" with limn-~ooI IGn Ln I I = Clearly, 6 is an ideal in ~-. Proposition 1.14 6 is a closed ideal in ~. Proof. Let ((G(nm))n>o)m>obe a sequence of elements of G which converge to the sequence (G~)n>0 E ~ in the norm of ~ as n -~ c~. Thus, given ~ > 0 there is an m0such that supn IIG~L,~ - G(~m°)Lnll < ~/2. Choose N such that IIG(~m°)L,~II < ~/2 for all n _> g. Then, for all n _> N, tlG~Lnll < IIG(n’n°)Lnll + ]IG~Ln- G(n’~°)Lnll _< ~, from which it follows that (G~) belongs to 6. Consider the quotient algebra 9~/G, the elements of which are the cosets (An) ÷ 6 of sequences (An) E $’. This algebra is a Banach algebra due Propositions 1.13 and 1.14. The following theorem reveals that the algebra ~’/6 indeed provides a perfect frame to study stability problems in an algebraic way. Theorem1.15 (Kozak) A sequence (An) ~ J: is stable i] and only i] its coset (An) + 6 is invertible in the quotient algebra Proof. If (A,~)n>o is a stable sequence, then the sequence (A~l)n>_~o is bounded for some sufficiently large no by definition. Wemake to a sequence (Bo, B~,..., Bno- 1, A~o~, A~o~+l,...) in ~" by freely choosing
38
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
operators Bi E Im Li. It is evident that this sequence is an inverse of (An) modulo G. Let, conversely, (An) + ~ be an invertible coset in 9~/~. Then there are sequences (Bn) E ~" as well as (Gn) and (Hn) in 6 such AnBn = In + Gn and B,~An = In + Hn with In = IlImL". If n is large enough, then IIGnll < 1/2 and IIHnll < 1/2, and a Neumann series argument yields the invertibility of the operators In + Gn and In + Hn as well as the uniform boundedness of the norms of their inverses by 2. Hence, AnBn(In + Gn) -1 = In, (In + Hn)-lBnAn = In, and the norms of Bn(In + Gn)-1 and of (In + Hn)-lBn are uniformly hounded. Thus, the operators An are invertible for all sufficiently large n, and their inverses are uniformly bounded. ¯ Weclose our first acquaintance with the algebra ~/~ by a nice expression for the norm of a coset (An) + in~’/ ~. Recall tha t, by definition,
It(An)+GII=(a~)~g inf II(An)+ (Gn)ll~ = (a.)~a inf suPllA,~Ln Proposition
÷GnL,dlL(X)
1.16 For all (An)
II(A~)+ ~ll~/g= limsup IIAnLnll. Proof. Let (An) ~ Y. Then, for every sequence (Gn) ~
limsupIIAnLnll - lira supIIAnLn + GnL,~II _< supIIAnLn + whencethe estimate lim sup IIAnLnll~ II(An)+ ~ll follows. For the reverse inequality, let ¢ > 0, and choose no such that IIAnL~I I _< lira sup for all n > no. If we set Gn:=
-An 0
if if
n<no n>_no,
then the sequence (Gn) belongs to G, and
II(A~)÷ GII~
I1(0,... 0, Ano,Ano+a,...)ll sup IIAnLnll < limsupllAnLnll
Letting e go to zero yields the desired result.
¯
1.2. BANACH ALGEBRAS AND STABILITY 1.2.3
Small
39
perturbations
As a rule, the approximate operators An of a given operator A are affected with small errors. For example, the application of the finite section method to an operator A requires the computation of the scalar products (Aei, which in most cases can be done only approximately (by a quadrature rule, say). So, as a first application of Kozak’s theorem, we consider small perturbations of stable sequences. Notice that, by Proposition 1.16, a sequence (S~) e ~ is small if lim sup [[SnLn[[ is small. Theorem 1.17 Let (A,~) E ~ be a stable sequence and let (Sn) be a quence such that limsup IISninll < liminf IIA~linl1-1.
(1.9)
Then the sequence (An + Sn) is stable. Proof. If B is an arbitrary unital Banachalgebra and a E B is invertible, -1 then the element a + s is invertible for every s E B with [[s[[ < [[a-l[[ (Neumannseries). Let now (An) ~ bea s ta Sle seq uence. The n the coset (An) + 6 is invertible in ~’/~. The above remark, applied to the Banach algebra 9r/6, yields the invertibility of every coset (An) + (Sn) (a nd thus, the stability of every sequence (An + Sn)) if only II(Sn) +61l < 1/[I((An)
~- ~)--lll"
The inequalities (1.9) and (1.10) coincide due to Proposition 1.16.
(1.10) ¯
Let (Ln) and (Rn) be sequences of projections on a Banach space X as in Section 1.1.2. As a corollary to Theorem1.17 we obtain that the set of all operators A ~ L(X) for which the projection method (RnALn) applies is open in L(X). 1.2.4
Compact
perturbations
The Fredholm integral operators of second kind, A = I + K, introduced in Section 1.1.2, are the sum of a ’good’ operator (in this case, the identity) and a compact perturbation, K. Thus, the projection method (RnALn) for A is also the sum of a ’good’ sequence (in this case, the approximation method (RnILn) = (Ln) for the identity operator, which is obviously stable), and a ’compact’ perturbation, (RnKL,~). The goal of the present section is a perturbation theorem which describes the behavior of sequences under compact perturbations (Theorem 1.20 and its corollary below). The desired perturbation theorem does not hold for arbitrary approximation methods (see Theorem5.50 in Section 5.3.4 for one reason showing
40
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
why). So we have to start with introducing an appropriate subclass of approximation sequences. For, let again (Ln) be a sequence of projections on a Banach space X with strong limit I, but suppose moreover that the adjoint projections L~ also converge strongly to the identity operator I* on the dual X* of X. Clearly, this involves no further restriction if the Ln are orthogonal projections on a Hilbert space. In what follows, we will only consider sequences (An) of operators An E L(Im Ln) for which both sequences (AnLn) and (A~L~) are strongly convergent in X and X*, respectively. The set of all of these sequences will be denoted by .T C, and the strong limit of a sequence (An) ~ jrc by W(An). (We prefer this short notation to the more correct but cumbersomenotation W((An)n>_o).) Evidently, W(A~) = (W(An))* for all (A,~) ~ jrc. Theorem1.18 (a) The set jre is a closed subalgebra o] jr which contains the unit element of (b) The mapping W re -~L(X), (A, ~) ~-~ W(An) is a conti nuous unita homomorphism with norm 1. Proof. Strongly convergent sequences are uniformly bounded due to the Banach-Steinhaus theorem, thus, ~c is a subset of ~-. Recalling assertion (a) of Lemma 1.5 in Section 1.1.2 one easily checks that ~-c is a subalgebra of jr and that Wis a homomorphism. Further we conclude from Ln -~ I and L~ -~ I* that (IlimL~) ~ jrC and W(IlImLn) = and, co nsequently, jrc and Ware unital. Invoking the Banach-Steinhaus theorem once more, we get IIW(An)II <_liminf llAnLnll <_sup llAnLnll = II(An)ll,
(1.11)
which shows that W is continuous and has norm 1. It remains to verify the closedness of ~c in .T. Let ((A(~m))~>_o)m>o be a sequence of elements of ~-c which converges in the norm of jr to the sequence (A~) ~ ~-. Then ((An(m) )n>O)m>Ois a Cauchy sequence jr which, via (1.11), implies that (W(A(~m)))m>O is a Cauchy sequence in the Banach space L(X). Thus, the latter sequence converges to a certain operator A ~ L(X). Weclaim that A is just the strong limit of the sequence (A~Ln). Indeed, for all x E X and m, n _> 0, IIAx - A~ Lnxll <_IIAx - W(A(~m))xll + <_IIA - W(A(~’~))]I +I[m(~’~)n,~
1.2. BANACH ALGEBRAS AND STABILITY
41
Given ¢ > 0, choose ml and m2 such that IIA - W(A(~’~))I I < ¢ for all m >_ ml and II(A(, "0) - (A~)II~: = supllA~m)nn - A~L,~II < ¢ for all ra _> m2. n
Now fix m0 >_ max{m~,m2} and choose N such that IIW(A(~’~°))xA(,m°)Lnxll < ¢ for all n _> g. Then, for all n >_ N, 2¢11xll + ¢, which proves our claim. The strong convergence of the adjoint sequence can be checked analogously. Hence, the limit sequence (A~) belongs to ~c. ¯ Clearly, the ideal G of 9v is contained in the algebra 9rc, and it closed ideal of ~-c. But this algebra possesses a muchlarger ideal roughly speaking, consists of all possible compactperturbations of imation sequences. Theorem 1.19 The set GC o/all sequences (LnKLn+Gn)n>owith
forms a which, approx(Gn)
G and K compact on X is a closed ideal o/ Proof. It is easy to see that every sequence (LnKLn + Gn) belongs to ~-c and that W(LnKLn+ Gn) = K. It is further clear that Gc is a linear space. For a proof of the ideal property, observe that for every sequence An(nngnn + Gn) = (Annn - LnW(An))KLn + LnW(An)KLn Evidently, the sequence (AnGn) lies in G, and since W(An)Kis again compact for compact K, one has (LnW(An)KLn) e Gc. Finally, AnLn LnW(An) -4 st rongly, fr om which, vi a Le mma 1.5 (b ), fo llows th [I(AnLn - LnW(An))KII -~ and, he nce, (( dnLn - nnW(An))Knn) Thus, (An)(LnKLn + Gn) C,and simi larly one checks that (LnKLn +
an)(An)c.
For a proof of the closedness of G°, let ((LnK(m)L,~ + G(~m))n>_o)m>_o be a sequence of elements in Gc which converges in the norm of ~’. Then K(’~) = W(LnK(m)Ln+G(~’~)), and from (1.11) we infer that the sequence (K(ra)) converges in the operator norm to an operator K°%Being the norm limit of compact operators, the operator K¢~ is compact again, hence, the sequence (LaK~°Lu) belongs to Gc. With this sequence, we have [I(LnK(~)Ln) - (LnK°°in)[]z = sup I]Ln(g (’0 - KC~)Lnll n
where C := sup IIL,~II. Consequently, the sequence ((LnK(m)Ln)n>o)m>o converges in the norm of ~" to (LnK°°Ln) as m --~ ~o, which implies
42
CHAPTER 1.
THE LANGUAGE, OF NUMERICAL ANALYSIS
that the sequence ((G(nm))n_>o)m_>0is convergent, too. Its limit belongs to G by Proposition 1.14. It is now evident that the sequence ((LnK(m)Ln G(nm))n_>0)~nk0 co nverges to (LnK°°L~ + G~)which belongs to the ideal Gc as we have seen. . That it is possible to include all compactperturbations into one ideal (although in the smaller algebra 9re rather than in ,T) shows that the compact perturbations form indeed a quite natural class of perturbations. The following theorem is a key result. It does not only describe the influence of compact perturbations, but is moreover a first step on a way which will finally lead us to an important tool of analyzing algebras of concrete approximation methods: the so-called lifting theorems (see Chapter 4 and Section 5.3). Theorem 1.20 Let the approximation method (An) belong to the algebra 3:c. The sequence (An) is stable if and only i] its strong limit W(An) invertible and i] its coset (An) + ~c is invertible in the quotient ~zc /6c. Weprepare the proof of Theorem1.20 by a lemma. Recall that an operator A E L(X) is normally solvable if its range is closed, and that A is bounded below or an operator of regular type if there is a C > 0 such that Ilxll _~ C IIAxll for all x E X. Lemma 1.21 Let X be a Banach space. The operator A E L(X) boundedbelow if and only i/it is normally solvable and i/its kernel consists o/the zero element only. The assertion of Lemma1.21 becomes obvious if X has finite dimension, and we already used it in this special form in the proof of Theorem1.10. Proof. If Im A is closed and Ker A = {0}, then A is invertible as operator from X onto Im A. By Banach’s theorem, there is a bounded linear operator B : Im A -~ X such that BA -- I on X. Thus, for every x E X,
Let, conversely, A be bounded below, and let (Yn) C_ Im A be a convergent sequence. Choose elements Xn ~- X with Axn -~ Yn. The inequalities
imply that (Xn) is a Cauchy sequence in X, hence convergent. Set x lira xn. Since A is continuous, one has y,~ = Axn ~. Ax, i.e. the limit of (Yn) belongs to Im A. Thus, A is normally solvable, and the injectivity of A is obvious. ¯
1.2. BANACH ALGEBRAS AND STABILITY
43
Proof of Theorem 1.20. Let (An) E re be a st able se quence an d se t C := supn>,~o IIA~ILnlI. Then, for every x E X and all sufficiently large n, IILnxll = IVA’(~IAnLnxll <_ C IIAnLaxlI. Letting n go to infinity we obtain Ilxll < C I]W(An)xll for all x ~ X, i.e. the operator W(A,~) has a closed range and a trivial kernel by Lemma1.21. Repeating these arguments with the adjoint sequence (A~) in place of (An), we get that the kernel of W(A~) = W(An)* is trivial, too. This implies that the range of W(An) is all of X. Indeed, otherwise there would exist an x0 ~ X as well as a linear bounded functional .f ~ X* such that ](x0) = 1 and f = 0 Im W(An) (Hahn-Banach theorem). Clearly, ] belongs to the kernel W(An)*, which is a contradiction. Thus, Im W(An) = X, and W(An) is invertible. Our next goal is the invertibility of the coset (An) + ~c. As in the proof of Kozak’s theorem, let (Bn) ~ ~" be a sequence with Bn = ~ for al l sufficiently large n. Since we already knowthat (Bn) + G is the inverse the coset (An) + G, and since G _C Gc, it remains to check whether (Bn) belongs to Given y E X set x = W(A,~)-~y. Then, for all sufficiently large n, I[BnLny - W(An)-lyll <_ IIA’(~iLny - LnW(An)-lyll + I1(I - Ln)W(An)-~y[I <- I]A’~Lnll IlY - AnL,~W(An)-IYl] + II( I - Ln)W(A,~)-IYl] IIW(An)x - Aninxll I1(I -
=.]lA’~iinl[
which shows the strong convergence of (Bn) to W(A,~) -1. The strong convergence of (Bn)* can be seen analogously. Thus, indeed, (Ba) and -1. W(Bn) = W(An) Let now, conversely, the operator W(An)as well as the coset be invertible. Then there are sequences (Cn) ~ ~-c and (Gn) ~ ~ and compact operator K such that AnCn = ~]ImL~ -b LnKLn + Gn. Set Dn := Cn - LnW(An)-IKLn. The operator W(An)-~K is compact, hence (LnW(A,~)-~KLn) belongs to GC, and (Dn) lies in yc again. Further one has AnD,~
’b LnKLn + G,~ - AnLnW(An)-~ KLn = II~mL ~ + (L,~ - AnLnW(An)-~) KLn + The sequence (Ln - AnLnW(An)-~) converges strongly to 0 as n --+ and Lemma1.5 implies that even = IIlmL,,
II(gn-AnLnW(An)
-I)KII-~O
as
n~
44
CHAPTER 1.
THE LANGUAGE, OF NUMERICAL ANALYSIS
Consequently, AnDn= IIX~.L. + G’~with (G~) E ~, i.e. the coset (A,~) is invertible in ~’/~ from the right hand side. Its invertibility from the left side follows analogously. Thus, (A,~) is stable by Kozak’s theorem. Corollary 1.22 Let (An) ~ C bea s ta ble seq uence and K bea compact operator on X. Then the sequence (A,~ + L,~KL,~) is stable if and only the operator W(An) + K is invertible. For a proof observe that the cosets (An) + c and ( An +LnKL~) + C coincide, and apply Theorem 1.20. . Weare going to illustrate
the perturbation theorem by a few examples.
Example 1.23 Let X be a Banach space and let (L,~) and (Rn) be sequences of projections on X which are as in Section 1.1.2. The projection method (RnILn) = (Ln) for the identity operator is clearly stable. Consider the projection method (R~ALn) for the operator A = I + K with K compact. Since RnALn = Ln + RnKLn = Ln
+ LngLn-b
Cn
with IICnL,~II --+ 0 due to Lemma1.5, we can think of (R~AL,~) as compact perturbation of the stable sequence (Ln). Applying Theorem1.20 and its corollary to this special situation, we arrive at Theorem1.6 again. Example 1.24 Let H be a separable infinite-dimensional Hilbert space with orthonormal basis (el), let P,~ refer to the orthogonal projection from H onto the span of {e0,..., e,~}, and let A be the operator a(B + iS) + where B is positive definite, S is self-adjoint, K is compact, and a ~ ~2. Specification of Corollary 1.22 to this context yields: Corollary 1.25 The finite section method (PnAPn) applies to the operator A = a(B + iS) + K if and only if A is invertible. Proof. If A is invertible, then necessarily a ~ 0. From Theorem 1.10(b) we infer that the finite section method(P~(a(B + iS))Pn) for the operator a(B + iS) is stable, thus, (PnAPn) is a compact perturbation of a stable sequence. . It is surprising that also a certain converse of Corollary 1.25 is valid: Theorem 1.26 (Markus/Vainikko) Let A ~ L(H) be an invertible operator on a Hilbert space H. If the finite section method with respect to an arbitrary orthonormal basis of H applies to A, then A is necessarily of the form a(B + iS) + K with a, B, S, K as above.
1.3.
FINITE
SECTIONS OF TOEPLITZ OPERATORS
45 ¯
For a proof, see [64], Chapter II, Theorem5.1.
Further applications of the perturbation theoremare given in Sections 1.3.3 and 4.3.2 below.
1.3
Finite sections of Toeplitz operators with continuous generating function
Wehave already met Toeplitz operators as representations of polynomials of the shift operator with respect to the ’natural’ basis in Example1.11. Here we will consider Toeplitz operators which are generated by continuous functions. In contrast to the Toeplitz operators generated by polynomials, these operators are no longer band matrices. After recalling some basic facts on Toeplitz operators, we will apply the perturbation theorem to study the finite section method for Toeplitz operators, again with respect to the ’natural’ basis. One reason for the permanent interest in Toeplitz operators is that these operators constitute one of the best-studied and simplest classes of non-normal operators (and are thus beyond the classes of operators usually considered in courses on functional analysis). 1.3.1
Laurent,
Toeplitz
and Hankel
operators
Westart with the definition of Toeplitz operators with arbitrary bounded generating function. Let a E L~(~’), and denote by ak the k th Fourier coefficient of a: 1 ~02~a(ei~)e_ik Od~, k ~ Z. Then the Laurent operator L(a) on /2(Z), the Toeplitz operator T(a) on /2(Z+), and the Hankel operator H(a) on/2(Z+) are given via their matrix representations with respect to the standard bases of/2(Z) and/2(Z+)
L(a)
¯ ¯ ao
a-1
a-2
a-3
"*
¯ ¯ al
ao
a-1
a-2
"¯
¯ - a2
al
ao
a-1
a3
a2
al
ao
46
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
and
T(a)=
al a2 3
ao al a2
a-1 a0 al
a-2
...
a-1
’-"
ao
..-
a2 a3 U(a)=
a3
a4
4 a5
a4 a5 a6
a5 a6 a7
k respectively. Observe that in case a is the polynomial t ~ ~-~j=-k cjt j, the Toeplitz operator T(a) coincides with the operator considered in Example 1.11. Theorem 1.27 I] a E L~(~), then the Laurent operator L(a) is bounded on/2(Z), and I]L(a)ll- I]allo~. Proof. Let M(a) denote the operator of multiplication by a. Thought of as acting on the Lebesgue space L2(’I~), the operator M(a) is bounded, and IIM(a)ll = Ilall~. Further, the functions ek(eit) = (2~r)-l/2eikt, k e form an orthogonal basis of L2(31"). It is not hard to see that, actually, L(a) is the matrix representation of M(a) with respect to the basis (ek)aez from which the assertions immediately follow. ¯ For the boundedness of Toeplitz and Hankel operators one has the following results: Theorem 1.28 (a) (Brown/Halmos) I] a e L°°(~), then the Toeplitz operator T(a) is boundedon/2(~,+), IlT(a)lI -- I lal lo~(b) (Nehari) I1 a ~ L°¢(~), then the Hankel operator H(a) is bounded /2(Z+), and IIH(a)ll = dlStL~(T)(a,H Here, ~ stands for the algebra of all functions in L~(~") which possess analytic extensions into the exterior of ~. For a proof of Theorem1.28 see, for example, [26], Theorems 2.7 and 2.11. ¯ Toeplitz and Hankel operators can be viewed as the building stones of Laurent operators. For, we identify the Hilbert space/2(Z) with the direct sum/2(Z+) (9/2(Z+) via the mapping
Under this identification, ’block operator’
the Laurent operator L(a) corresponds to the
L(a) ~ ( H(a)T(5) H(5))T(a) ’
(1.12)
1.3. FINITE
SECTIONS
OF TOEPLITZ
47
OPERATORS
where h refers to the function 5(t) := a(1/t). ") (Observe that 5 is in L~(~ again, and that 5k ---- a-k for k E Z.) In the sequel we will need somealgebraic properties of Laurent, Toeplitz and Hankel operators. If a, b E L~(~’), then a + b and ab ") are in L°°(~l again, and one obviously has L(a) -t- L(b) = L(a A- b), T(a) ÷ T(b) = T(a ÷ b), U(a) ÷ U(b) Further, taking into account that L(a) is the matrix representation of the operator of multiplication by a, one gets L(a) L(b) = L(ab).
(1.13)
The situation is a little bit more involved for products of Toeplitz and Hankel operators. From (1.12), we obtain that L(a)L(b)
/’T(a) H(5)~ (T(~) ~ ik H(a) T(a) ]\ H(b)
{’T(5)T(~_) +H(5)H(b) T(h)H(~.) (1.14) = ~.H(a)T(b) + T(a)H(b) g(a)g(b) + as well as L(abl e--~ ~.H(ab) T(ab)
(1.15)
Due to (1.13), the matrices in (1.14) and (1.15) coincide, and comparison of their south-east resp. south-west corners yields T(ab) = T(a)T(b) + H(a)U(~), H(ab) = T(a)U(b) (1 .16) Similarly, if a ~ Lc°(~’), then the function ~(t) a(t ) is in L°°(~) again, and ~k = a_k for every k. Hence, L(a)* L(~), wh ence, by (1. 12), L(a)*
[ T(5) g(5)~* ~ \ H(a) T(a)
= \U(a)*
T(a)* = ~,U(~) T(~)
and, thus, T(a)*
T( ~),
U(a)* =
Westill mention a result which facilitates essentially.
H(~).
(1.17)
the work with Toeplitz operators
Theorem 1.29 (Coburn) Let a ~ L°°(T) (0 }. Then at lea st one o] t he spaces KerT(a) and/2/clos (ImT(a)) consists o] the zero element only. For a proof see [26], Theorem2.3s, or [27], Theorem1.10.
48 1.3.2
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
Invertibility ators
and Fredholmness
of Toeplitz
oper-
A linear and bounded operator A on a Banach space X is invertible in L(X) if (and only if) its kernel is {0} and its range is all of X (Banach’s theorem). Thus, an operator A is invertible if (and only if) both its kernel Ker A and its cokernel CokerA := X/clos(ImA) are linear spaces with dimension zero. Coburn’s theorem simplifies this condition essentially in case T(a) is a non-zero Toeplitz operator. Indeed, in this case it is sufficient to know that the difference indT(a) := dimKerT(a) di mCokerT(a) is zer o in order to guarantee the invertibility of T(a). In particular, a Fredholm Toeplitz operator is invertible wheneverits index vanishes. The following result describes the Fredholm properties of Toeplitz operators with continuous generating function (compare Figure 1.1). Theorem 1.30 Let a E C(’~). The Toeplitz operator T(a) is Fredholm on 12 if and only if O ~ a(~). In this case, indT(a) = -winda(~) where wind a(’l~) refers to the winding number of the curve a(~), provided with the orientation inherited by the usual counter-clockwise orientation of the unit circle, aroundthe origin. For a proof see [26], Theorem2.42, and compare also Section 4.1.3 where we will derive a more general result holding for Toeplitz operators with piecewise continuous generating function. Combining Theorem 1.30 with
a
ind T(a)
-= 0 ind T(a)
=
Figure 1.1: Fredholmness of Toeplitz operators Coburn’s theorem we get Theorem 1.31 Let a ~ C(~). The Toeplitz operator T(a) is invertible 12 if and only if 0 ¢ a(V) and if wind a(~’) = Figure 1.2 illustrates
this theorem.
1.3.
FINITE SECTIONS OF TOEPLITZ OPERATORS
T(a) not invertible
T(a) invertible
Figure 1.2: Invertibility 1.3.3
The finite
section
49
T(a) invertible
of Toeplitz operators
method
Weconsider the applicability of the finite section methodwith respect to the standard basis of 12, i.e. we let OO ~ Pn : ( Xk)k=O
(Xo,Xl,"
¯ . ,Xn-l,0,0,’"
")
Theorem 1.32 Let a E C(~). The finite section method (P,~T(a)P,~) plies to the Toeplitz operator T(a) if and only if T(a) is invertible. From Polski’s theorem we know that invertibility of T(a) is a necessary condition for applicability of the finite section method. In the case at hand this condition is also sufficient, whichis clearly the best-possible result. The proof of Theorem1.32 relies on the perturbation theorem from Section 1.2.4 and on the following elementary lemmata. Lemma1.33 If a ~ C(~), then the Hankel operator H(a) is compact. Proof. Approximate the continuous function a by a sequence (p,~) trigonometric polynomials in the supremumnorm. Then, by Theorem 1.27 and (1.12), [[H(a)- H(pn)[[ = [[H(a- Pn)[[ _~ [[L(a- Pn)[[ [[a-pn[[oo -+O, and the assertion follows from the (obvious) compactness of the Hankel operators H(pn) and from the closedness of the ideal of compact operators with respect to norm convergence. ¯ Lemma1.34 (Kozak) Let X be a linear space, P a projection on X, Q the complementary projection I - P, and let A be an invertible operator on X. Then the compression PAPIImpof A onto Im P is invertible if and only if the compression QA-1Q[ImQof A-1 onto ImQ is invertible, and one has (pAp)-IP
= pA-1p
_ pA-1Q(QA-IQ)-~QA-~p.
50
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
The proof is straightforward. Lemma1.35 Let a E L°°(~) and suppose T(a) is invertible. Then -1 finite . section method applies to the inverse Toeplitz operator T(a) Proof. Set Qn = I - Pn. Kozak’s formula implies that the sequence (PnT(a)-IP~) of operators on Im Pn is stable if and only if the sequence (Q~T(a)Q~) of operators acting on Im Qn is stable. Since the operators T(a) and QnT(a)Q~IImQnhave the same matrix representation with respect to the standard basis of 12, the stability of the latter sequence is obvious. ¯ Proof of Theorem 1.32. If the finite section method applies to T(a) then this operator is invertible (Polski’s theorem). Let, conversely, T(a) be an invertible operator. Then, by Theorem1.31, 0 ~ a(~’) and, hence, -1 exists and belongs to C(’F) again. From (1.16) we know I = T(aa -1) = T(a)T(a -1) + H(a)H(a-~). Invoking Theorem 1.31 once more we see that T(a-~) is invertible hence, T(a) = T(a-1) -1 - -~ H(a)H(a-I)T(a-~)
and,
whence PnT(a)Pn = PnT(a-i)-lPn
- PnH(a)H(a-i)T(a-1)-iPn.
The operator H(a)H(a-1)T(a-1) -1 is compact due to Lemma1.33, and the sequence (P~T(a-~)-~Pn) is stable by Lemma1.35, thus, the perturbation theorem yields the assertion. ¯ Nowconsider the finite section method for compactly perturbed Toeplitz operators A = T(a) + with a E C(~). If A i s invertible the n, cle arly, ind A = 0, and the invariance of the index under compact perturbations implies that ind T(a) = O. Then, by Coburn’s theorem, T(a) is invertible, and Theorem1.32 entails the stability of the sequence (P,~T(a)P,~). So, (P,~AP~) is actually a compact perturbation of a stable sequence, which yields, via the perturbation theorem, the following criterion. Corollary 1.36 Let a ~ C(~2) and K ~ L(l 2) compact. Then the finite section methodapplies to T(a) + K i] and only i] this operator is invertible. Wewill come back to this result from another point of view in the next section. Here we still mention two related applications.
1.3. FINITE
SECTIONS
OF TOEPLITZ
51
OPERATORS
Example 1.37 The finite section method for Laurent operators. For the approximation of Laurent operators we need finite sections of twosided infinite matrices. The appropriate orthogonal projections Rn on/2(Z) are Rn : (Xk)k6Z
(. n_2,xn-l,O ..,0,0, X,x
n,X-n-bl,-.,O,...).
Evidently, Rn -~ I strongly as n -~ oo and, thus, the finite section method (RnARn) is an approximation method for every operator A 6 L(/2(Z)). Corollary 1.38 If a 6 C(T), then the finite section method (RnL(a)R,~) applies to the Laurent operator L(a) if and only i] the Toeplitz operator T(a) is invertible. Proof. The matrices in the sequence (R,~L(a)Rn) coincide with those in the sequence (P2nT(a)P2n). Hence, both sequences are simultaneously stable or not. But stability of (P2nT(a)P2n)involves invertibility of T(a) (Polski’s theorem). Conversely, if the operator T(a) is invertible, then the sequence (P,~T(a)Pn) is stable by Theorem1.32 and, thus, its subsequence (P2,~T(a)P2,~) is stable. . Since Laurent operators are essentially nothing else but multiplication operators, the Laurent operator L(a) with a E C(T) is invertible if and only if 0 ¢ a(T) whereas, by Theorem1.31, the invertibility of the Toeplitz operator T(a) in addition requires that wind a = 0. Thus, one consequence of Corollary 1.38 is that the invertibility of the Laurent operator L(a) is not sufficient for the stability of the finite section method(RnL(a)Rn). Let us emphasize still another remarkable aspect: Whereis the ’center’ of the (doubly infinite) Laurent matrix
’.
0
1
4
2
0
0
0
0
0 0
1
4
0
1
2 4
0 2
0 ". 0 .
0
,
and which of its diagonals is the ’main diagonal’ ? Israel Gohberg’s answer is that ’it is every diagonal’s right to claim to be the main one’. So one might consider each of
A~’--")----
0 1 4
--o)
0
1
4
2
52
CHAPTI~R 1.
=
THE LANGUAGE OF NUMERICAL ANALYSIS
42000
4200
as reasonable approximation matrices, and the generating function of the associated Laurent operator is invertible in any case. But the four sequences (A(n/))n>o correspond to the finite section method for Toeplitz operators T(a(~)-) with generating functions a(~)(t) = t ~-3(t ÷ 4 + 2t-1). Since only one of these operators, namely T(a(3)), is invertible, we see (A(n3)) is the only stable approximation methodamongthe sequences (A(n/)). Consequently, there is a good reason to consider ..., 4, 4, ... as the main diagonal. Example 1.39 The finite section method for Toeplitz operators on the Bergman space. Let the notations be as in Example 1.9. The orthogonal projection P from L2(I~) onto its subspace A2(D) is given (Pf)(z)
f~
(1
.f(w)
dA(w)
Given a function a E L°~(I])), the Bergmanspace Toeplitz operator TS(a) is defined as T B(a) : Ae(~)-~A~(D), f~Paf. 2 This operator is bounded on A (~)). Let now a E L~ (It)) be a function which is continuous on D and possesses a continuous extension onto the closure clos I~ = 1~ t_J q~ of I~. We denote this extension by a again and write b for the restriction of a onto q~. One can prove that the matrix representation of TB(a) with respect to the basis {ek}k°°=o, ek(Z) : kV/~--~zk, is CTB(a)C -~ = T(b)
+
where T(b) is the usual (l 2-) Toeplitz operator and K is compact on l 2. So Corollary 1.36 and property (1.6) immediately involve Corollary 1.40 Let a ~ C(closl~). Then the invertibility of TS(a) necessary and sufficient both for the applicability of the finite section method (L,~TB(a)L,~) and of the collocation method (RnTS(a)nn).
1.4 C*-algebras To study stability study invertibility
of approximation
sequences
problems of approximation sequences is the same as to problems in the Banach algebra ~’/G of all bounded
1.4. C*-ALGEBRAS
OF APPROXIMATION
SEQUENCES
53
sequences modulo the zero sequences. In many concrete situations, one might desire to consider this invertibility problem in a suitable subalgebra of ~’/G rather than in ~-/6 itself. (Say, because one has a precise knowledge about this subalgebra from former investigations, or because one wants to employ something like Gelfand’s theory to study the invertibility problem, which only works in commutative algebras.) This simple idea involves someserious technical difficulties since, if is a closed subalgebra of a Banach algebra A, and b belongs to/3, then the spectrum of b in/3 can be strictly larger than the spectrum of b in In particular, the stability of a boundedsequence (An) is, in general, not equivalent to the invertibility of the coset (An) ÷ G in a certain subalgebra of ~-/G. In this section, we are going to introduce a special class of Banach algebras, one advantage of which is that it doesn’t matter whether invertibility problemsare studied in the algebra itself or in one of its subalgebras: viz. the C*-algebras. It would be, however, more than wrong to reduce the role of C*-algebras to that one of a useful tool for solving invertibility problems. It has rather become more and more clear in the last decades that C*-algebras provide a natural language for many fields in ’non-commutative’ mathematics and physics (which is comparable with the role of complex numbers in ’commutative’ mathematics). For getting an impression on these developments, have a look at Connes’ book [38]. Although we will apply C*-algebras on a quite elementary level only, we will nevertheless see that they can really do a lot of work for us.
1.4.1 C*-algebras, their ideals and homomorphisms Let /3 be a Banach algebra. A mapping a ~-~ a* of/3 into itself involution if, for all a, b E/3 and all (a*)*
=a,
(ha+#b)*
is an
=Xa*+~b* (ab) * =b’a
A Banach algebra/3 with an involution * is called a C*-algebra if Ila*all = ][al] 2 for all a e/3.
(1.18)
In C*-algebras, the involution is an isometry: Example 1.41 Let X be a compact subset of IRn (or, more general, a compact Hausdorff space) and let C(X) be the set of all continuous complexvalued functions on X. Provided with pointwise operations, the maximum norm, and the involution f*(t) = f(t), C(X) becomes a commutative and unital C*-algebra.
54
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
Example 1.42 If H is a Hilbert space, then the Banach algebra L(H) of the bounded linear operators on H is a C*-algebra with A ~4 A* (= the Hilbert space adjoint of A) as involution. Let us check axiom (1.18): A ¯ L(H),
IIAll2 --
sup((Ax, Ax):x ¯ H, Ilxll = 1} sup((A*gx, x) :x ¯ H, Ilxll 1) <_ sup(lld*dxll:x ¯ H, Ilxl] = 1} = IIA*AII, =
e. and conversely,IlA*dll <_ HA*IIlldll -- IIAII Example 1.43 Let H be a Hilbert space, (P,~) be a sequence of orthogonal projections on H which converge strongly to the identity, and let ~ be the associated Banach algebra of bounded approximation sequences. Then (A,~)* := (A~) defines an involution v which makes ~" t o aC*-al g,ebra. Since (Gn)* belongs to the ideal 6 of ~" again whenever (Gn) is in 6, see that ~ is also a C*-algebra. An ideal ]C of an involutive Banach algebra ‘4 is called symmetric or a *-ideal if k ¯ ]C implies k* ¯ ]C. If ]C is a *-ideal of .4 then
(a + ~:)*:= a*+~: defines an involution on the quotient algebra A/1C Finally, a homomorphism W: A1 --> .42 between involutive Banach algebras .41 and .42 is symmetric or a *-homomorphism, if W(a*) = W(a)* for every a ¯ .41. The following results summarize some basic facts about C*-algebras and show in particular, that working in C*-algebras is much more convenient than in general Banach algebras. All proofs can be found in the standard textbooks about C*-algebras. Theorem 1.44 Let .4 be a C*-algebra. (a) Every closed ideal of A is symmetric. (b) If ]C is a closed ideal of A, then the Banachalgebra A/]C is C* again. (c) If W is a *-homomorphism from A into a C*-algebra B, then W is continuous and ]IWII <_ 1. (d) If Wis moreover one-to-one, then it is an isometry. Parts of the following isomorphy theorems are well known from general ring theory; their important new aspect is that all occuring algebras are C*-algebras again, i.e. that Im Wis closed, ]C is an ideal of .4, and B + ]C is closed in Theorems1.45, 1.46 and 1.47, respectively.
1.4. C*-ALGE,
BRAS OF APPROXIMATION SEQUENCES
55
Theorem 1.45 (First isomorphy theorem) Let A and 13 be C*-algebras and W : A --~ 1~ a *-homomorphism. Then WA is a C*-subalgebra o] 13, and the C*-algebras A/Ker W and Im W = WA are *-isomorphic: A/Ker W--- Im W. Theorem 1.4{I (Second isomorphy theorem) Let A be a C*-algebra, ff a closed ideal of .4, and IC a closed ideal of ft. Then I~ is a closed ideal of A, and there is a natural *-isomorphy (A/IC)/(ff /E) ~ A/ft. Theorem 1.47 (Third isomorphy theorem) Let A be a C*-algebra, I3 a C*-subalgebraof A, and ]~ a closed ideal of A. Then B+I~ (= the algebraic sum) is a C*-subalgebra of A, and there is a natural *-isomorphy (B
Let us further recall two famous results due to Gelfand, Naimarkand Segal which state that the C*-algebras considered in Examples 1.41 and 1.42, together with their C*-subalgebr~s, do already exhaust the classes of all C*-algebras respective of all commutative C*-algebras. Theorem 1.48 (a) (General GNS-theorem) For every C*-algebra A, there exists a Hilbert space H such that .4 is *-isomorphic to a C*-subalgebraof L(H). (b) (Commutativecase) For every commutative C*-algebra A with identity, there exists a Hausdorff compact X such that A is *-isomorphic to C(X). For a more detailed explanation of assertion (b) we refer to Section 4.1. Finally, we mention two results concerning invertibility in C*-algebras. Theorem1.49 (Inverse closedness) Let A be a C*-algebra with identity e, and let 13 be a C*-subalgebra of .4 containing e. Then an element b E B is invertible in !~ if and only if it is invertible in ‘4. In other words, aA(b) al~(b) for every Thus, one can switch to appropriate C*-subalgebras of a given C*-algebra when dealing with invertibility problems. Theorem 1.50 (Semi-simplicity) Let ,4 be a unital C*-algebra and r ~ A be an element having the property that, whenever an element a ~ ‘4 is invertible, then a + r is also invertible. Thenr = O. Equivalently, the Jacobsonradical of a unital C*-algebra, i.e. the intersection of all maximalleft ideals of that algebra, consists of the zero element only.
56
1.4.2
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
The Toeplitz C*-algebra and the C*-algebra of the finite section method for Toeplitz operators
Weare going now to examine two concrete examples of C*-algebras. The Toeplitz algebra T(C) is the smallest closed subalgebra of L(/2) which contains all Toeplitz operators with continuous generating function. Since T(a)* T(a), th is al gebra is symmetric and henc e a C* -a lgebra. The formula (1.16) for the product of Toeplitz operators together with Lemma 1.33 indicate that T(C) does not only contain Toeplitz operators but also operators of the form T(a) ÷ with K compact. Wewil l sho w tha t the se operators already exhaust the algebra T(C). Theorem 1.51 T(C) {T(a) +
K : a E C(T), g
co mpact on
Proof. Let, for a moment, ‘4 abbreviate the set on the right hand side of the asserted equality. For the inclusion .4 C_ 7-(C) it is enoughto verify that every compact operator belongs to T(C). The reverse inclusion will follow once we have shown that A itself is an algebra (which is a consequence of formula (1.16) and Lemma1.33 again) and that A is closed. In the next step we show that the ideal K(/2) of the compact operators on 12 is contained in T(C). Let K ~ K(12). Since IIPrgPr - KII -+ 0 by Lemma1.5 and since 7"(C) is closed by definition, it remains to check whether PrKPr E T(C) for all r. Let V and V-1 denote the forward and backwardshift operators on 12, oo oo ~ (X~,X2,...), (0, the Xo,Xl,. .), representation V-1 : (X~)k=O (1.19) and Vlet: (Xk)k=O (kij)i,j=o ~ be matrix of P~KP~IImp ~ with respect r--1
to the standard basis of 12. A little
thought reveals that r--1
P~KPr = ~ kijViP~VJ_~ which gives the assertion because P1 = I - VV_I and V, V-1 are the Toeplitz operators T(a), T(a_~) with a(t) = t, a_~ (t) -~, res pectively. For the proof of the closedness of .4 we use the following formula (where Q, := I - P,), which holds for every A E L(/2): IIA + K(l~)ll
li m ]I QnAQnll
(1.20)
(its proof is left as an exercise). If K is compact, then IIQ~KQ~II-~ 0 due to Lemma1.5, and if A = T(a) is a Toeplitz operator then IIQnT(a)Qnll IIT(a)l I because T(A) and QnT(a)Q~I~n~Q.have the same matrix representation. Thus, I[T(a)[[ _< liT(a) + g[I (1.21)
1.4. C*-ALGEBRAS
OF APPROXIMATION SE~QUENCES
57
which even holds for arbitrary a ¯ LC°(~") and K ¯ K(12). From (1.21) we infer that, if (T(a (m)) + K(m))m>l is a norm convergent sequence operators in A, then the sequence (T(~(m))),~_>l is also convergent, and easily checks that its limit is a Toeplitz operator T(a) with a ¯ C(~’) again. This finally implies that (K(m))m>_lis a convergent sequence, and its limit is a compact operator K. Thus, limm_,oo(T(a(’~))÷ (’~)) =T(a)+ K ¯ ,4 ¯
Our next goal is a similar description of the smallest closed subalgebra of the algebra ~" which contains all sequences (PnT(a)Pn) with continuous functions a. Since (P,~T(a)P,~)* = (PnT(~)Pn), this algebra is symmetric and, hence, a C*-algebra. The desired description requires a formula for the product of two finite section sequences (PnT(a)Pn) and (PnT(b)Pn). To this end, introduce the reflection operators Rn:l 2-~1~, (xO, Xl,...)~(xn-l,x~-2,...,x~,xo, Lemma1.52 (Widom’s formula) PnT(ab)Pn = PnT(a)PnT(b)P,~
Let a,b ¯ L°°(~).
0,0,...). Then
q- PnH(a)H(~)Pn ÷ RnH(h)H(b)Rn.
Proof. From (1.16) we know that P~T(ab)P,~ = P,~T(a)T(b)P,~ + P,~H(a)H([~)P,~ = PnT(a)PnT(b)Pn + PnH(a)H(~)Pn + PnT(a)Q~T(b)Pn. It is elementary to check that RnT(a)V_~ P,~H(5), V~T(b)Rn = H(b)Pn, where V,~ := V~, V_,~ := (V_I) "~ and V, V-1 are the shift operators (1.19). Hence, PnT(a)Q,~T(b)P,~ -- R,~RnT(a)V-,~VuT(b)R,~R~ = RnH(5)H(b)Rn, which yields the assertion.
¯
If a and b are continuous functions, then H(a)H([~) and H(h)H(b) are compact (Lemma1.33). Thus, one might conjecture that S(C) consists all sequences (PnT(a)Pn + PnKPn+ RnLR,~) where a is continuous and K and L are compact. As the following theorem shows, this is almost correct. Theorem1.53 The algebra ~q(C) coincides with the set of all sequences (PnT(a)Pn
+ P~KPn + RnLR~ +
where a ¯ C(~), the operators K, L are compact on 12, and where (Gn)
58
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
Proof. Denote the set of all sequences of the specified form by 81 for a moment. Westart with verifying that the set $1 indeed forms an algebra. Let al, a2 be continuous functions and K1, K2, L1, L2 be compact operators, and set Q~ = I - Pn. A straightforward calculation employing Widom’s. formula as well as the identity RnT(a)R,~ = PnT(5)Pn with ~(t) := a(1/t) for every a e L°~(~") (1.22) yields (PnT(al)Pn + PnK~P~ + RnL1Rn) (PnT(a~)Pn + P~K~Pn + = P~T(ala2)P,~ + P~KP~ + R~LRn where K = K1K2 + K1T(a2) + T(al)K2 - H(al)H(~2), L = LIL2 + L1T(5~) + T(51)L2 H(5~)H(a2), Gn = P~KIR~L2R~ + R~LIRnK2Pn - PnT(a~)QnK~Pn -PnK1Q~T(a~)P~ - R~(R~T(al)R~ - T(a~))LeR~ -R~L1 (R~T(a~)Rn T(5~))R,~ -P~KIQ,~KuPn - RnL~Q,~L2R,~. The function ala2 is continuous, and the operators K and L are compact again, and Lemma1.5 involves that IIGn]] -~ 0 as n -~ oo, which gives our claim. Nowwe proceed in full analogy to the proof of Theorem 1.51: we show that all sequences (PnKPn+RnLRn+G,~)with K, L compact and (Gn) ~ belong to $(C), and then we verify the closedness of the set 81. Let V and V-1 denote the forward and backward shifts on 12 again. The arguments given in in the proof of Theorem1.51 yield that, to prove the inclusion (PnKPn) ~ $(C) for every compact K, it is enough to verify that (P,~ViP~V~_~P~)~ S(C) for every i,j >_O. Clearly, (PnV~P~ V~_, P,) = (PnV’P,)(P, P1Pn)(P~V~_,P~), and the sequences (P~V~P~) and (PnV~_IP~) belong to 8(C) since V~ = T(a~) and V_Jl = T(aJ__l) where a(t) = and a-l(t) = -1 . Further, P~V = P~VP~ and V-~Pn = PnV-1Pn, which implies that (PnPIPn) = (Pn(I - VV-~)Pn) = (Pn) -- (PnVPn)(PnV-1Pn) is in 8(C), too.
1.4. C*-ALGI~BRAS
59
OF APPROXIMATION SEQUENCES
Similarly, to prove that (R,~LR,~) is in S(C) for every compact L, we have to check whether RnV~P1V~_IR,~)e ,9(C) for every i,j >_ O. In this case one has (R,~V~P1VJ_IR,~)= (R,~V~P,~P1P,~V~_IR,~) = (RnV~Rn)(RnP1Rn)(RnVJ_IRn), and the sequences (R,~V~Rn) and (RnVJ_IRn) are in $(C) since RnViRn = RnT(ai)Rn and R,~VJ_IRr~ = RnT(aJ__I)R,~ (also recall (1.22)). Furthermore, (R,~P~R,~) = (P,~) - (R,~VV_IR,~) = (P,~) - (R,~VP,~V_IR,~) = (Pn) - (RnVRn)(R,~V-~Rn) ¯ Finally, a little thought showsthat, to verify the inclusion G _C S(C), it sufficient to showthat, for every fixed no, every se.quence of the form where Cn = 0 for n ¢ no and C,~o = P,~oVIP1V~_IP,~owith 0 _< i,j < no belongs to $(C). But this is a consequence of the identity
and of what has already been shown. It remains to prove the closedness of the set $1- First observe that, given a sequence (An) ¯ ,~, the strong limits W(A~) := s-lim AnPn and lYd(A~) := s-lim RnAR,~exist and that W(PnT(a)Pn + P,~KP,~ + R,~LR~ + G,~) = T(a)
(1.23)
17V(P,~T(a)P,~ + P,~KP,~ + RnLRn+ Gn) = T(a)
(1.24)
Indeed, for (1.23) one has to show that R,~LR,~ ~ 0 strongly if L is compact
(1.25)
which can be most easily seen by approximating L by a linear combination of operators of the form ViPIV~_~; then (1.24) is a consequence of (1.22) and (1.25). Thus, if ((PnT(a(m))P,~ + P,~K(m)Pn+ R,~L(m)R,~ + G(nrn))n>_o)ra>_ois a sequence of elements of S~ which converges in ~’, then the sequences (T(a(m)) + K(rn))m>_Oand (T(5(m)) + L(m))m>_oare convergent, too. From Theorem1.51 we knowthat there is a continuous function a as well as compact operators K, L such that limr,-~oo T(a(’~))) + K(’~) = T(a) + and limm-~ooT(?z(m)) + L(m) = T(~t) + L. Thus, the sequence ( (PnT(a(’~))Pn
60
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
PnK(m) pn + RnL(m) R,~)n>_o)m>_otends to (PnT(a)Pn + PnKPn+ RnLRn), which shows that the sequence ((G(nm))n>_o),~_>0 is also convergent. limit (Gn) of this sequence belongs to ~ because ~ is closed in $" (Proposition 1.14). Nowit is clear that the limit of the sequence under consideration is just (PnT(a)P,~ + PnKPn+ R~LRn + Gn) which belongs to 81. Hence, S1 is closed, and S1 = S(C).
1.4.3
Stability of sequences in the C*-algebra of the finite section method for Toeplitz operators
Nowwe are going to examine the stability of an arbitrary sequence in the algebra 8(C). At the first glance, it might seem to be quite strange to consider something like (PnT(a)Pn ÷ RnLRn) with compact L as an approximation sequence for the Toeplitz operator T(a). But observe that many difference methods lead to Toeplitz matrices which are perturbed in the left upper and right lower corner. The perturbations of the right lower corner correspond exactly to the sequences (RnLTln) with compact L, whereas the sequences (P,~I(Pn) with compact K describe perturbations in the left upper corner. The importance of the following result for the purpose of describing the algebra $(C) will becomeclear in the next section. Theorem1.54 Let (An) e ~(C). The sequence (An) is stable if and i] both operators W(An) := s-lim AnPn and I~V(An) := s-lim RnAnRnare invertible. Proof. The necessity of the invertibility of W(An) and l/~d(An) can shown as in the proof of Theorem 1.20. Here is yet another proof, which takes advantage of the C*-property of $(C). If the sequence (An) S(C) is stable the n the coset (An) +~ is i nvertible in 9~/~ (Kozak’s theorem). Since S(C) is a C*-algebra which contains the closed ideal 6 (Theorem 1.53) we find that 8(C)/6 is a C*-subalgebra of ~/~. From the inverse closedness (Theorem 1.49) we further infer that (An) + 6 is even invertible in 3(C)/6. In other words: there are sequences (Bn) E $(C) (Gn), (Ha) such th at (AnBn) = (IlIrnP~)
+ (Gn), (Bndn) = (IlImP~) + (Hn).
Applying both homomorphismsWand l~d to these equalities, we obtain the invertibility of W(An)and I?d(An). (Recall that the existence of strong limits W(Bn) and I~(Bn) for arbitrary (Bn) S(C) was ve rified in the proof of Theorem1.53.) Now let (An) (PnT(a)Pn + PnKPn + R, ~LRn + Gn) ~ ,S and su ppose that the operators W(An) = T(a) + andI~V(An) = T(a)+ L are in -
1.4. C*-ALGEBRAS
OF APPROXIMATION
61
SEQUENCES
vertible. The invertibility of T(a) ÷ implies vi a Corollary 1. 36 the st ability of (PnT(a)Pn + PnKPn). Then, clearly, the sequence (Rn(PnT(a)Pn PnKPn)Rn) = (PnT(5)Pn + RnKRn) is stable, too. For the sequence (PnT(5)Pn + RnKRn+ PnLPn), which is nothing but a compact perturbation of (PnT(h)Pn+RnKRn), we have W(PnT(a)P~+RnKRn+PnLPn) T(5) +L. The invertibility of this operator together with the (perturbation) Theorem 1.20 yields the stability of the sequence (PnT(5)Pn + RnKRn PnLPn), which is evidently equivalent to the stability of (An). 1.4.4
Symbol of the operators
finite
section
method
for
Toeplitz
Let us start with reformulating the stability result of the preceding section. Write L(/2) × L(/2) for the product of the C*-algebra L(/2) with itself, for the set of all ordered pairs (B1, B2) of operators B1,B2 E L(12). Provided with elementwise operations, elementwise involution, and the maximumnorm II(B1,B2)II := max{llBlll , IIB~II}, this product becomes a C*algebra. Next take the *-homomorphismsW, l~d : S(C) -~ L(/2) and glue them together to obtain one homomorphism,say smb°, acting via smb°: S(C) --~ L(l 2) × L(12), (An) ~+ (W(A,~), IYV(An)). It is furthermore clear that the ideal G of 8(C) lies in the kernel of the homomorphism smb°. Thus, the quotient homomorphism smb : 8(C)/6 -~ L(l ~) × L(l~),
(An) + ~ ~ smb°(A~)
(1.26)
is correctly defined, and we can restate Theorem1.54 as follows: Theorem 1.55 Let (An) ~ S(C). The coset (An) + ~ is invertible S(C)/G i] and only i] smb((An)+ is invertible in L(/2) x L(12). Thus, smb is a symbol mapping for S(C)/~ in the following sense. Definition 1.56 Let A, B be unital Banach algebras and S : A -~ B a unital homomorphism.S is a symbol mappingfor A if, for arbitrary a ~ A, the invertibility o] S(a) in B implies the invertibility o] a in ,4. I] S is symbol mapping, then S(a) is called the symbol o] a. Since the invertibility of a ~ A implies the invertibility of S(a) in B for every unital homomorphismS : ,4 -~ B, one can also characterize symbol mappings as homomorphismswhich preserve spectra. In the general (Banach algebra) case, this is almost all what can be said about symbol
62
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
mappings, and the construction of a symbol mapping is often the ultimate goal of any analysis of Banach algebras of approximation sequences. But in the C*-case, and when S is a *-symbol mapping (i.e. a symmetric homomorphism),then the symbol mapping is not only responsible for invertibility, but moreoverreflects the algebraic and metric properties of the algebra A exactly. Theorem 1.57 Let A and be a *-symbol mapping. Then S is a *-isomorphism (hence, an isometry) from A onto the C*-algebra Im Proof. In view of Theorems 1.44(d) and 1.45, it remains to verify that every *-symbol mapping is one-to-one. Let a E ,4 and Sa = O. Then, by the C*-axiom, 0 --lISa[[ 2 = I[(Sa)*(Sa)[] = I[S(a*a)[[~
(1.27)
For selfadjoint elements b of a C*-algebra/3, the norm []b][ and the spectral radius p(b) coincide. Hence, by (1.27), p(S(a*a)) = 0: But S preserves spectra and, in particular, spectral radii, which implies that p(a*a) ~- 0, too. Nowwe get as in (1.27) that 0 = p(a*a) = I[a*a[[ = [[a[[ 2, i.e. a = 0. ¯ Combining Theorems 1.55 and 1.57 we obtain: Corollary 1.58 The mapping smb in (1.26) is a *-isomorphism (and, hence, an isometry) from $(C)/6 onto the C*-subalgebra L(/ 2) x L (/ which consists of all pairs (W(An),IV(An)) with (An) running
s(c). Thus, one need not distinguish between the algebra ~q(C)/g and its image in L(/2) x L(/2) and, consequently, instead of working with the elements S(C)/6 (i.e. with cosets of infinite sequences of approximation operators), we will simply deal with their symbols (i.e. with pairs of operators), which is much more pleasant. For applications of the description of 8(C)/~ via its symbol mapping we refer to Chapters 2 and 3 and also to the forthcoming section, whereas the whole Chapter 4 is devoted to the construction of symbol mappings for more involved subalgebras of
1.5
Asymptotic bers
behaviour
of condition
num-
As a first application of the complete description of the algebra $(C)/~ obtained in the previous section via constructing a symbol mapping, we are
1.5.
ASYMPTOTIC BEHAVIOUR OF CONDITION NUMBERS
63
nowgoing to prove that the sequence of the condition numbersof the finite sections of an invertible Toeplitz operator in S(C) is convergent. (That this sequence remains bounded is evident from the stability of the finite section method.) The proof of this fact motivates the introduction of the notion of a ]ractal approximation sequence in the forthcoming section. 1.5.1
The condition
of an operator
The condition number condA := IIAII IIA-Xll of an invertible operator A is a measure for the sensitivity of the dependenceof the solution u of the equation Au = f from the right hand side f. Namely, if u +/~u is the solution of the equation A(u +/ku) = f +/kf with perturbated right hand side, then the relative errors of u resp. f satisfy the estimate [[/ku[[
< condA
Clearly, cond A is never less than 1, and for selfadjoint and positive definite operators A one has condA = sup{A:A E a(A)} inf {A: A E a(A)} Let now (An) be an approximation method for the operator A. For computational purposes, the asymptotic behaviour of the condition numbers cond An as n tends to infinity is of great interest. If (An) is a stable sequence, then the sequence (cond An) is bounded: sup condAn= sup [[An[[ [[A~X[] _< sup [IA,[[ sup [[A~I[] < cx~. As we shall see later (Corollary 1.72), there are additional but quite natural conditions for the sequence (An) which guarantee that the sequence (cond A,~) is even convergent. For the moment,we restrict our attention a first example, namely, to the behavior of the condition numbers cond An for sequences (An) in the algebra $(C) of the finite section method for Toeplitz operators. The sequence of the norms[IPnT (a) Pn [[ is monotonically increasing and bounded from above by []T(a)[[. Hence, lim [[P,~T(a)Pn[[ exists. Further, the Banach-Steinhaus theorem gives the estimate [[T(a)[[ = [[s-lim PnT(a)P,~[[<_ liminf[[PnT(a)P,~[[ whencelira [[P,~T(a)Pn[[ = [[T(a)[[. (These arguments remain valid for finite sections of every operator A.)
64
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
Thus, the sequence of the condition numbers cond (P,~T(a)Pn) for an invertible Toeplitz operator with continuous generating function converges if and only if the sequence of the norms [[(PnT(a)Pn)-l[I converges. This convergenceis less obvious than that of the sequence I]PnT (a) Pn [], since the only thing we know about ((PnT(a)Pn)-1) is that this sequence belongs to the algebra ,S(C) again (inverse closedness). So we are led to the problem of verifying that the norms [IAnl] converge for any sequence (A,~) E S(C), and to compute their limit.
1.5.2
Convergence
of norms
Here is the desired result on the convergence of the norms. Theorem1.59 Let (A,~) ~ $(_C). Then the limit lim ][A~P,~[I exists, it is equal to max{l[W(A~)[[,[[W(A~)[[}.
and
Proof. From Corollary 1.58 we know that max{[lW(d~)[[,I[l~Z(An)[[} = I[(dn)
(1.28)
and Proposition 1.16 tells us that [[(An) + 61[ = limsup []AnPn[[. Finally,
(1.29)
by the Banach-Steinhaus theorem,
[]W(A~)][ ~ liminf []A~P~[[,
[[$(A~)[[ li minf[[R~A~R~[[
whence m~ {~[W(An)[], []~(A~)[I } ~ liminf []A~Pn~[.
¯
Thus, the Banach-Steinhaus theorem is powerful enough to finish the proof in shortest time but, in the form the proof stands, it seems not to explMn the reM re,on for the existence of the limits under consideration. So we add a second, somewhat longer and more detailed, proof of Theorem 1.59 (recMling some ~guments of the proof of the Banach-Steinhaus theorem), which indicates that the main point is the special form of the homomorphisms W and W: Since the operators W(A~) and ~(A~) are strong limits, every infinite subsequence (A~) of (A~) can reproduce them. Second proof. Again we have (1.28) and (1.29), and it remains to verify the existence of the limits. Assumethere is a sequence (A~) e 8(C) that lim inf [[A~P~[[ < lira sup []A~P~[[. Choose an infinite subsequence (A~)~0 of (A~) such that lim [[A~P~[[ exists as k ~ ~ and is equal to liminf [[A~Pn~[. The sequence ~ = (n ~)k=o ~
1.5.
ASYMPTOTIC BEHAVIOUR OF CONDITION NUMBERS
65
gives rise to a natural modification of the algebra ~: we let ~’n stand for the C*-algebra of all sequences (A,~,)k~__0with (A,~) r, and defi ne S(C) and Gn similarly. Obviously, if (An) S(C) (a nd th us (An~) ~ 8( ), then the strong limits Wn(An~) = s-lim k-~o~An~P,~ and 12Vn(An~) s-lim k~Rn, A~Rn~exist. A little thought shows that the stability of sequences in 8(C)n can be studied in the very same manner as that of sequences in S(C). What results is that the homomorphismsWn and ISdn can be glued together to produce a symbol mapping for the algebra 8(C)n/G n. The analogues of (1.28) and (1.29) limsupllA~,P~l I = max{lIWn(A~)ll, 1112dn(An~)ll}.
(1.30)
But evidently, Wn(An~) = W(An) and IZVn(An~) = ITV(An) for every sequence (An) S(C). Thus, pu tting (1 .28), (1 .29) an d (1 .30) to gether, we arrive at lim inf [[A°nPn[[
lirasupIIA°=Pnll -- max{llW(A°~)ll, max {lIWn(A°~)ll, Ill~n(A°n.)ll} =limsup liminf[]A°.P~II
which is a contradiction.
1.5.3
Condition numbers of finite operators
sections
of Toeplitz
An immediate consequence of Theorem1.59 is the following. Corollary 1.60 (a) If (An) ~ 8(C) is a stable sequence, then the lim cond An exists, and it is equal to max{llW(An)ll, III~(An)II} max{llW(An)-ill, which is just the condition numberof smb ((An) + ~). (b) In particular, a ~ C(~) and T(a) is invertible, lira cond PnT(a)Pn = cond T(a). To derive (b) from (a) one has to prove I]T(a)ll = I]T(fi)]l
IIT( a)-all = II T(a)-a[].
(1.31)
The validity of (1.31), even for arbitrary a E L°°(~’), is a consequence the identity T(a) = CT(a)* C (1.32)
66
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
where C is the anti-linear operator of conjugation C : 12 -~ 12, (Xk) ~-+ (’Zk). Let us mention that the explicit determination of the norm of T(a) -1 (or at least of an upper estimate for this norm) can be quite complicated in general (in contrast to the normof T(a) itself, which is available thanks to the Brown-Halmostheorem). The following theorem presents an estimate for liT(a) -1 [I in special cases. Let conv Mdenote the convex hull of a set MC_ C, and write dist (0, M) :-- inf{Iml,m ¯ M} for the distance between Mand the point 0. Theorem1.61 Let a ¯ L~°(’~) and d := dist (0, conva(’l~)) > Then the Toeplitz operator T(a) is invertible, and IIT(a)-~ll ~_ (1 + V/1 - d2/llall2~)/d < 2/d.
(1.33)
Proof. There is a ~/¯ ~" such that ~a(~l’) is contained in the set {z¯C: Rez>_d, Iz]<_l]alloo }. Multiplying the latter set by A :----- d/[]al]~, we obtain a set which is contained in the disk {z¯C : Iz-11
with
r:=v/1-d2/llall~.
Hence, which implies the invertibility of T(a) and yields (via an estimate using the Neumannseries) the desired inequality (1.33).
1.6 Fractality
of approximation
methods
The topic of this section is another fundamental notion of numerical analysis - that of a fractal approximation method. Roughly speaking, fractality of a sequence (An) means that the knowledge of any infinite subsequence of (An) allows us to reconstruct the complete sequence (An) modulo a sequence or, in other words, the whole information about the coset (An)+~ is already stored in any subsequence of (An). As we shall see, the fractality of a sequence is responsible for the uniformity of certain limiting processes. At this place, we will only mention some basic properties of fractal sequences, and we will illustrate the applicability of this concept for proving once more the convergence of the condition numbers for stable sequences in S(C). Further applications (to the determination of the limiting set of the eigenvalues of the approximation operators, for instance) will be given in the forthcoming chapters.
1.6.
1.6.1
FRACTALITY
OF APPROXIMATION
67
METHODS
Fractal homomorphisms,fractal sequences
algebras,
fractal
It is not important in this section that the elements of the sequences under consideration are operators. So we will use slightly generalized definitions of the C*-algebras iT and G. Given unital C*-algebras Cn (n = 0, 1, 2, ...) with identity elements en, let iT stand for the set of all boundedsequences (c0,cl,c2,...) with cn E Cn, and let 6 refer to the set of all sequences (co, cl, c2, ...) in iT with [[cn[I -~ 0 as n -+ oo. Defining elementwiseoperations and an elementwise involution, and taking the supremumnorm, we make iT to a C*-algebra and 6 to a closed ideal of iT (compare Propositions 1.13 and 1.14). Clearly, with the special choice Cn = L(ImPn), we actually get the previous definitions of iT and 6. The algebras iT and 6 are also called the product and the restricted product of the C*-algebras Cn, and the quotient algebra iT/6 is sometimesreferred to as the ultraproduct of the Cn (and as the ultrapower of C in case Co = C1 .... = C). Given a strongly monotonically increasing sequence r/: N -+ N, let iT, and G, denote the product and the restricted product of the C*-algebras Cn(0), Cn(~), ..., respectively, and let R, stand for the restriction mapping Rn : iT -+ iTn, (an) (a n(n)). Th e mapping R nis a * -homomorphism from iT onto ~’n which moreover maps ~ onto 67. Given a C*-subalgebra A of iT, let A, refer to the image of .4 under Rn. By the first isomorphy theorem, A,~ is a C*-subalgebra of iTo. Definition 1.62 Let A be a C*-subalgebra of iT. (a) A *-homomorphism W : A -~ B o] A into a C*-algebra B is fractal if, for every strongly monotonically increasing sequence ~l, there is a *homomorphism Wn :n. Ao -~ I3 such that W = WnR (b) The algebra A is fractal, if the canonical homomorphism~r : A --~ A/(.4 f~ 6) is fractal. (c) A sequence (an) e iT fra ctal/] thesmallest C*-s ubalgebra of i T which contains (an) is ~ractal. Thus, given a subsequence (an(n)) of a sequence (an) which belongs fractal algebra .4, it is possible to reconstruct the original sequence (an) from its subsequence modulo sequences in .4 V) 6. This assumption is quite natural for sequences arising from discretization procedures. Example 1.63 Let Cn = L(ImPn), and let iTw refer sequences (An) ~ iT for which the strong limits
to the set of all
W(An) := ~-lim AnPn and ITV(An) := s-lim
RnAnRn
as well as the strong limits W(A~) and I/;V(A~) exist. The set iTw is
68
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
C*-subalgebra of ~ (compare the proof of Theorem 1.18(a)), and S(C) a C*-subalgebra of ~-w as we have checked in the proof of Theorem1.53. The *-homomorphismsW, l~: ~-w _~ L(I 2) prove to be fractal: given a strongly monotonically increasing sequence r~, we can define W~, lPd, : .TnW-~ L(l ~) via W,(A,(n)) s-l im A,( n)P,(n) andl~n( A,(,)) := s Then, obviously, W = W~R~and l~ = I~R,. Further, the algebra ~-w itself is not fractal, but its subalgebra $(C) is. These facts will become evident once we have established somecriteria for fractality of algebras (see Corollary 1.70 and the discussion before). Lemma1.64 Let A be a C*-subalgebra o] ~:, and let B be a C*-algebra. I] W: A ~ B is a ]ractal *-homomorphism, then A fq 6 c_ Ker W. Proof. Let (g,~) e A Cl 6. Given ~ > 0 there is an no such that for n > no. Consider the sequence r/(n) := n + no. Because Wis fractal,
=
=
=
and, consequently,
(recall that assertion.
IlWoll_<1 by Theorem1.44).
Letting e go to zero we get the ¯
Thus, for every fractal *-homomorphismW : A --~ B, the element W(a,~) does only depend on the coset rr(an) = (an) + A ¢3 LetW" denote the (correctly defined) quotient homomorphism W" : A/(A n 6) -~ I3, 7r(a,)
~+ W(a,).
(1.34)
Lemma 1.65 Let ~4 be a fractal C*-subalgebra of if: and 13 be a C*-algebra. A * -homomorphismW: A --~ 13 is fractal if and only if A fq 6 C Ker W. Proof. If Wis fractal, then A fq 6 C_ Ker Wby Lemma1.64. Let, conversely, A f’l 6 C_ Ker W, and define the quotient mapping W" by (1.34). Then, clearly, W= W’Tr.Further, since 7r is fractal by assumption, for every strongly monotonically sequence ~ there is a *-homomorphismr o such that 7r = ~roRo. Thus, which shows the fractality
of W.
The following two theorems provide equivalent characterizations subalgebras of ~-.
¯ of fractal
1.6. FRACTALITY
OF APPROXIMATION
METHODS
69
Theorem 1.66 A C*-subalgebra A of ~ is fractal if and only if the following implication holds for every element (an) E ‘4 and every strongly monotonically increasing sequence 7:
Proof. Let .4 be fractal, and assume there is a strongly monotonically increasing sequence y as well as an element (an) ~ A with Ru(an) ~ 6~, for which(an) is not in A n 6, i.e.
II~(a,~)ll =II(’~n)+‘4 ~611c>o with some constant C. Since R,(a,~) ~ 67, there is an no such that Ila,(n)ll <_ C/2 for n >_ no. Define a sequence # by #(n) ;-- ~(n + no). Then IIR~(an)ll <_ C/2. On the other hand, the fractality of A entails that
(1.35) which is a contradiction. Hence, (an) belongs to .4 A 6. For the reverse direction, let (an), (bn) E A be sequences with R~(an) R~(b~). By our hypotheses, then (an) - (bn) ~ A N 6, and so it is correct to define a *-homomorphismru via
Evidently, ~%/~ = r, which shows that r is a fractal A is a fractal algebra.
homomorphismand ¯
Corollary 1.67 (a) If .4 is a ]ractal C*-subalgebra of jr, then every C*subalgebraof ‘4 is also ]ractal. (b) A C*-subalgebraA of jr is fractal if and only if each of its elements fractal. Proof. (a) Let B be a C*-subalgebra of.4, and let (b,~) ~ B be an element with R,(bn) e 67. Since A is fractal, Theorem1.66 entails that (b,~) A N 6. Then, clearly, (bn) E B ~ 6, and invoking Theorem1.66 once more one gets the fractality of B. (b) If A is a fractal C*-subalgebraof ~’, then each of its elements is fractal due to assertion (a). For the reverse assertion we claim that, whenever is not fractal, then it contains a non-fractal sequence. Indeed, if .4 fails to be fractal, then, by Theorem1.66, there is an element (an) ~ ,4 as well as a sequence ~ such that R,(a~) ~ 6,, i.e. [la,(n)ll -~ 0 as n -~ ~, but (an) it .4~6, i.e. Ilan]l ~ 0 as n -~ ~x). Applying Theorem1.66 once again this shows that the C*-subalgebra of .4 which is generated by the sequence (an) cannot be fractal. Hence, the sequence (an) is not fractal. ¯
70
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
Corollary 1.68 I] A is a ]ractal C*-subalgebra of J:, then
(.4 n 6),. To motivate the following criterion for fractality,
recall Theorem1.55.
Theorem 1.69 Let A be a unital C*-subalgebra of i7:. Then .4 is fractal if and only if there exists a family (Wt}teT of unital and ]ractal* homomorphismsW~from A into unital C*-algebras Bt such that the following equivalence holds ]or every sequence (an) E A: The coset (an)+ is invertible in A/(An6) if and only if W~(a.) is invertible in Bt ]or every tET. Proof. If A is fractal, then the canonical homomorphism~r : A -~ AI(An 6) provides a ’family’ (~r} with the desired properties. Let, conversely, (W~}~eTbe a family of unital and fractal *- homomorphisms which is subject to the conditions of the theorem. Given a strongly monotonically increasing sequence ~/, define the operator Tv by
T, : A/(An0) -~ A,I(AnG),, (an) +An6~ R,(a~) One easily checks that this definition is correct and that T. is a *- homomorphismfrom A/(-4 N 6) onto A~/(-4 n 6)7. Weclaim that T, is an isomorphism. In accordance with Theorem1.57, it is sufficient to show that T. is a symbolmapping,i.e. that if (an) ~ .4, and if R, (a,~) + (An6), is invertible, then (an)÷-4N6 is invertible. So, let (an) be an element of.4 for which coset R~(an) + (.4 N 6)7 is invertible. Then there are a sequence (b~) e as well as sequences (gn), (hn) e A n 6 such
(1.36) (e~) referring to the identity element of ~. The h omomorphisms W ~ a re fractal by assumption, i.e. there are homomorphismsWt,, such that Wt = Wt,,R,. Applying Wt,~ to the equalities (1.36) we get Wt(an)Wt(bn) = Wt(e,~) + Wt(gn), Wt(b~)Wt(a,~)
= Wt(en)
Since Wt(en) is the identity element of Bt and Wt(g,~) = Wt(h~) (Lemma1.64), we conclude that all elements Wt(a,~) are invertible in Thus, the coset (an)+.4n6 is invertible, and T. is indeed a symbol mapping and, thus, a *-isomomorphism between .4/(.4 n 6) and A,/(.4 Let finally II, denote the canonical homomorphismfrom .47 onto the quotient algebra .47/(.4 N 6)7. Then, evidently, T~II.R. = ~, i.e. r is fractal (with ~. = T~-~I-I.), and we are done.
1.6. FRACTALITY
OF APPROXIMATION
METHODS
71
Let us return to Example1.63 once more. The se~luence (A,~) with A2n = 0 and A2n+l = diag(0,... 0, 1, 0,..., 0) (with the 1 standing in the center this diagonal matrix) belongs to the algebra ~-w, and W(An) s- lim AnPn = 0, I~d(An) = s -l im RnAnRn = s -l im AnPn = O . The sequence (An) does not belong to ~-w N G = G, but for the special choice y(n) = 2n one obtains that Rv(An) (A2n) ¯ ~. As a c onsequence of Theorem1.66, the algebra ~-w cannot be fractal. On the other hand, if (An) ¯ ,~(C) and if W(An) and I~V(An) are invertible operators, then the coset (An) + is invertible in S(C)/G. Since Wand 12d are fractal homomorphisms,Theorem1.69 implies the following result: Corollary 1.70 The algebra 8(C) is #actal. 1.6.2
Fractal
algebras,
and
convergence
of norms
Here we consider once again the problem whether limllanll exists for a sequence (an) E r. W e will p oint o ut t hat t he f ractality o f ( an) i ndeed guarantees the existence of this limit. Theorem1.71 Let A be a fractal C*-subalgebra of ~. (a) If (an) ~ .4 and ~ is a strongly monotonically increasing sequence,
(b) I] (an) ¯ .4, then the limit lim ]lanll exists andis equal to II(a,~) Proof. (a) The third isomorphy theorem for C*-algebras states that, is a C*-subalgebra of ~- and (bn) ~ B, then II(bn) + ~ll~:/g = I[(bn) + ~ll(’+g)/g = [l(bn) + B N ~lIB/(,n~).
(1.37)
Let now (an) ¯ A and (gn) ¯ ,4 ~ g. I](an) + ~[]:r/g
I](an) +-4~ 611A/(A~g) = I]~(an ÷gn)l]A/(A~g) = Ilr~R,(a~ +gn)IIA/(A~g) <- II(a,(n) + gv(n))%ollA,
(by (1.37)) (definition of (fractality of.4) (Theorem 1.44 (c)).
Taking the infimum over all (gn) ¯ .4 ~ ~, and invoking Corollary 1.68, obtain a II( n)+ll /o < I1( ,(n))n--0 +
72
CHAPTER 1.
THE LANGUAGE, OF NUMERICAL ANALYSIS
and a further application of (1.37) gives
II(a)
-
¯
(1.38)
On the other hand, the lira sup-formula for the normin 5c/6 (i.e. Proposition 1.16, which also holds in the present, slightly more general situation) yields II(a~(n)) + ~ll~:~/~ = limsup which together with (1.38) proves the assertion. (b) Assume(an) e is a s equence such tha t lim inf ~lanl~ < l imsup I~an~l. Then there is a strongly monotonically sequence ~ such that the limit lim ~lan(n)~l exists and is equal to liminf Ilanl~. By part (a) of this the~ rem and by the lim sup - formula again, we have limsup Ilan~ = ~(an) = lim sup which is a contradiction. As a simple consequence we get: Corollary 1.72 Let A be a ~actal C*-subalgebra o] ~, and let (an) e be a stable sequence. Then the limit limcondan = limllanll ]la~ll exists
to
ona +
What concerns the convergence of the norms S(C), we see now that our previous result (Theorem 1.59) is a simple combination of two basic observations: ¯ the fractality of S(C) (Corollary 1.70) which yields that the limit lim I~AnPnll exists and is equal to ~l(An) + ~ll for every sequence (An) e S(C) (Theorem 1.71), and ¯ the description of S(C)/6 as an algebra of ordered pairs (Corollary 1.58) which shows that ~l(g~) + 611 = ~lsmb((An) It is also clear that the decisive point in this approach is a precise knowledge on stability in S(C): it is both important to have a criterion for the stability of an arbitrary sequence in S(C) and that this criterion h~ the ’right form’, i.e. via a fractal mapping. In Chapter 4 we will derive simil~ stability criteria for sequences in more involved subNgebras of ~, and in all these cases, Theorem1.71 will automatically yield the convergence of the norms or of the condition numbers of the approximation operators.
1.6.
FRACTALITY
OF APPROXIMATION
METHODS
73
Notes and references Sections 1.1 - 1.4: The elementary theory of abstract projection methods can be found in the textbooks Gohberg/Feldman [64], PrSssdorf/Silbermann[122], [123], BSttcher/Silbermann [24], [26] and Hagen/Roch/Silbermann [77], for instance. Weespecially recommendBSttcher’s review papers [16, 18] as well as the recent textbooks BSttcher/Silbermann [27] and BSttcher/Grudsky [21] , which can, together with [64], also serve as excellent introductions to the theory of Toeplitz operators. As basic references for Banach and C*-algebras we mention Bonsall/Duncan [30], Bratteli/Robinson [32], Dixmier [49], Douglas [50] (which also can be read as textbook on Toeplitz operators), Davidson [44] (an approach to C*-algebras via examples), Kadison/Ringrose [91] (a monumentaltreatise in four volumes), and Pedersen [114]. Polski (1963) [117] was perhaps the first to realize the meaning of the stability of a projection method. A fundamental meta-theorem of numerical analysis is usually stated as consistence + stability -~ convergence, where consistence of a sequence (An) with an operator A means in our terminology that (An) is an approximation method for A. Polski’s Theorem 1.4 is the concrete specification of this meta-theorem we will employ on what follows. In the context of the numerical integration of ordinary differential equations, the phenomenonof a numerical instability was first observed by Todd (1950) [169] and later explained by Dahlquist (1956) [41] by establishing his celebrated root condition; see also the review paper Dahlquist [42]. The fact that stability of a sequence is equivalent to the invertibility af a coset of that sequence in a suitably constructed Banach algebra goes back to and was first employed by Kozak (1974) [95] who considered the finite section method for higher dimensional analogues of Toeplitz operators. The idea of a symbol was brought forth by Michlin in 1936 [105], [106], who associated with every two-dimensional singular integral operator a certain function the invertibility of which is responsible for the Fredholm property of the operator. Gohberg (1953) [62] showed then that Michlin’s symbol calculus actually coincides with the Gelfand transform (see Chapter 4 below) applied to the algebra generated by all singular integral operators with continuous coefficients, factored by the compact operators. Since that time, the distinguished role of a symbol calculus for several important classes of operators has been pointed out by several mathematicians, which in the sequel led to such highlights as the calculus of pseudo-differential operators due to Kohn/Nirenberg and HSrmander.
74
CHAPTER 1.
THE LANGUAGE OF NUMERICAL ANALYSIS
It was, nevertheless, quite surprising when it became obvious that one can also assign a symbol function to certain approximation methods such that the invertibility of the symbol is nowresponsible for the stability of the method. In 1983, BSttcher and Silbermann [25] succeeded in establishing a symbol calculus for certain approximation methods for quarter plane Toeplitz operators. Nowadays,symbol calculi are available for broad varieties of approximation methods for pseudodifferential operators, including Galerkin and collocation methods with polynomial or spline ansatz functions for singular integral and Wiener-Hopf operators. Here we only mention PrSssdorf/Schneider [121] and Hagen/Roch/Silbermann [77], where also further references are given. The Examples1.8, 1.9, 1.12 and 1.39 are taken from .[64], [28], [16] and [28], respectively, and the limsup formula (Proposition 1.16) is from [15], whereas we have learnt formula (1.20) for the essential aorm of an Hilbert space operator from W. Arveson. The elegant approach to the finite section methodfor Toeplitz operators presented in Section 1.3.3 is taken from [16], and the description of the algebra $(C) (Theorem 1.53) is from [25]. Sections 1.5 - 1.6-" Theorem 1.59 on the convergence of the norms of the approximation operators is due to BSttcher [15] and it was one of the ingredients needed to prove the convergence of the ~-pseudospectra of the finite sections of Toeplitz matrices (Sections 3.3.2 - 3.3.3 below). Theorem 1.61 and its proof are taken from [20], where muchmore delicate results on the asymptotic behaviour of condition numbersof finite sections of Toeplitz operators on/P-spaces are derived. The notion of fractality was introduced in Roch/Silbermann [147] in order to verify the uniformity of certain limiting processes. Most of the results in Section 1.6.1 are taken from [141].
Chapter 2
Regularization approximation
of methods Never computea generalized inverse of a matrix whose rank can change under small perturbations. This moral has dominated the literature and practice of generalized inverse computations. But there is also the second side of the coin whichsays that perhapswe are not asking the right question in this case. That is, if B approximates A, but rank B ¢ rank A, then B+ is not the matrix to seek as an approximation to A+. Instead we should develop ~ procedure to compute a variant B~ (of +) + which is a good approximationto the true A and which has in an approximate sense the properties o] a true generalized inverse. M. Zuhair Nashed
In this chapter we turn over to the second of the basic problems mentioned in the introduction: If (An) is an approximation method for the operator A, but A or the An are not invertible, do then the least square solutions of the equations A,~xn = Yn converge to the least square solution of Ax = y? We will see that this question indeed has a positive answer in some cases, but we will also point out that the posed question is the wrong one in some sense: The point is that the computation of least square solutions is instable with respect to small perturbations. So, even in case we can 75
CHAPTER 2.
76
REGULARIZATION
prove convergence, any perturbation be it ever so small can disturb this convergence drastically. A much better question seems to be the following more general one which was perhaps first raised by Moore and Nashed: Is it possible to replace the approximation operators A,~ by certain regularizations, A~ say, which also approximate A, for which the least square solutions of Anx,~ = Yn converge to the least square solution of Ax = y, and for which this convergence is in some sense stable? Wewill verify that this problem is equivalent to a generalized invertibility problem in the C*-algebra and, thus, accessible to algebraic techniques.
2.1 Stably regularizable
sequences
Westart with recalling some basic facts concerning generalized inverses and regularizations of matrices and linear operators. The main goal of this section is to define stably Moore-Penroseinvertible and stably regularizable approximation sequences, and to establish theorems of Polski type for these sequences. 2.1.1
Moore-Penrose matrices
inverses
and
regularizations
of
Let A E ~×~ be a non-invertible matrix. Then the equation Au = f is not solvable for every right hand side f, and if a solution exists, then it is not unique. It is appropriate to replace such linear systems by an equivalent extremal problem: determine vectors fi E Cn such that
(2.1) (Here and in what follows the norm of a vector resp. of a matrix is the Euclidean resp. the spectral norm.) It is knownfrom elementary analysis that the minimization problem (2.1) possesses solutions for arbitrary A and f, but it turns out that these solutions are not unique in general. Indeed, wheneverfi solves (2.1), then fi + k with k ~ Ker A is also a solution. What can be shownis that amongall vectors fi which solve (2.1) there is exactly one vector u+ solving a further minimization problem
Ilu+ll= min {1111:
satisfies
(2.1)}.
(2.2)
This vector is called the least square solution of Au = f. Wewill see in Theorem2.1 that the least square solution u+ depends linearly on f. The matrix A+ defined by A+f = u+ is the called the Moore-Penrose inverse
2.1. STABLY
REGULARIZABLE
SEQUENCES
77
of A. Clearly, if A is invertible, then u+ is the exact solution of Au = f, and A+ coincides with the commoninverse of A. Besides this constructive definition, there is also one way to introduce Moore-Penrose inverses axiomatically, and it is this way which we will go later in order to define Moore-Penrose inverses of operators on Hilbert spaces and of elements in C*-algebras. Theorem 2.1 Given a matrix A E Cn×n, there is a unique matrix B ~ Cnxn such that ABA = A, BAB = B, (AB)*
= AB and (BA)*
= (2.3
and this matrix is the Moore-Penroseinverse of A. This result remains valid for rectangular matrices, which, however, will not be considered here. For a proof of Theorem2.1 we will employ the singular value decomposition of a matrix. Recall that the singular values of a matrix A are the non-negative square roots of the eigenvalues of A*A. Theorem 2.2 (Singular value decomposition) nxn, Given a matrix A ~ C there are unitary matrices U and V such that A = U~V*, where ~ is the diagonal matrix diag (al, ¯ .., an) with the ordered singular values 0 al ~_ ... ~_ an of A as its entries. Note that the matrices U and V in the singular value decomposition of A are not unique: they are unique only up to a unitary operator which leaves every eigenspace of ~ invariant. So one rather should speak about a singular value decomposition of the matrix A. The proof of Theorem2.2 can be found in every textbook on linear algebra. Proof of Theorem 2.1. Let A = U~V*with F~ = diag (a~, ..., singular value decomposition of A, define ~ :=
01/ai
an) be
if = 0 if a~ ai>0,
and set ~ := diag (71, ..., a-n). Then the matrix B := V~U*satisfies the axioms (2.3). For a proof of uniqueness suppose that both B~ and B2 satisfy (2.3) place of B. Then B1 = Sl AB1 = B1 (ABI)* = B~ B~ A* = BIB~ (A* B~ = BI(B~A )(B2A ) B~(AB~)*(AB2)* = BI (ABIA)B2 =
BL
CHAPTER 2.
78
REGULARIZATION
and, similarly, B2 = BLAB2, whence B1 = B2. It remains to check whether B = V~U* coincides with the MoorePenrose inverse of A = UEV*,i.e. whether Bf is the least square solution of Au = f. By the unitarity of U and V, one has [IABf - f[I = [IUEV* Y~U*f - fl[
= [[E~V*f - U’f[ I.
(2.4)
Clearly, E~ is an orthogonal projection matrix, and for every orthogonal projection P E C~×’~ and arbitrary x,y E C~ the estimate IIPx - xl] _< IIPy - xll holds. With P := E~, x := U*f and y := EV*u this gives
IIABf - fll -
IIAu- fll = IlY, V*u- U*fll= IlY,(W*u - ~U*f)- (I which together with (2.4) yields
II~,(W*u - ~,f*f) - (I ~,)f*:ll = II(Z - Y,~,)U*flI. (2 Since E = E~E, and E~. is an orthogonal projection, the vector E(V*u ~.U*f) is orthogonal to (I - E~)U*f. Thus, as we have learned from Pythagoras, the equality (2.5) holds (or, equivalently, u solves (2.1)) only if EV*u = E~U*f. (2.6) Nowit is easy to see that Bf also solves (2.2). Indeed, if u is any solution of (2.1), then it satisfies (2.6), and we
IIBfll--IIY~V*fll = II~,V*ftl= II~V*fll= II~Y,V*ull _
¯
Corollary 2.3 The matrix AA+ is the orthogonal projection from C~~ onto Im A and I - A+Ais the orthogonal projection from Cn onto Ker A. Proof. The axioms (2.3) imply that the operators orthogonal projections and that further
AA+ and A+A are
Im A = Im AA+AC_ Im AA+ C_ Im A, KerA C_ Ker A+A C_ KerAA+A = KerA.
2.1. STABLY
REGULARIZABLE
SEQUENCES
Hence, ImA = ImAA+ and KerA = Ker A+A = Im(I - A+A).
79 ¯
A further immediate consequence of the equality A+ = V~U*is the identity IIA+II = max{l/,~ : ~ e a2(A) {0}} (2.7) where a2 (A) refers to the set of the singular values of In contrast to commoninvertibility, the mapping A ~ A+ is no longer continuous. Here is an elementary example: if A and A,~ are the 1 × 1 matrices (0) and (l/n), respectively, then IIAn - All --+ 0 but + - A+II = The concept of Moore-Penroseinversion allows us to define the condition number for an arbitrary (not necessarily invertible) matrix A condA := IIAll This number plays the same significant role for the solution of the minimization problems (2.1) and (2.2) as the usual condition number does the exact solution of Au = f. If u is the least square solution of Au = f, and u+Au is the least square solution of the equation A(u÷Au) = f+Af with perturbed right hand side then, in case AA+] ~ O, [[Au[[ < condA [[Af[[
Itull -
IIAA+.fII"
(2.8)
Seen with a computer’s eyes, an invertible matrix with large condition numberis as bad as a non-invertible matrix. Because of (2.7), the reasons for large norms of A-1 or A+ are very small positive singular values of A (whereas those singular values of A which are zero do not influence the norm of A+). This observation suggests to regularize ill-conditioned matrices A as follows: Find a singular value decomposition A = UEV*, choose a (small) cutting-off parameter ¢ > 0 and define ~.~ := diag (al.~,...,an,e) by 0 if ai < e ~i,e :----
ai
if
-ai > e.
The matrix Ae := U~,~V*, which is independent of the choice of U and V, is called the e-regularization of A. For small ~, it lies close to A: [IA-A~II = liE-E~II _< e, but its condition is better than those of A since IIA~+II < 1/~. The price one has to pay is a loss of accuracy: even if the matrix A and its ~-regularization A~ are close to each other, their Moore-Penrose inverses A+ and A~+ can have a large distance since Moore-Penrose inversion is not continuous. Let us finally mentionthat there are other possibilities of regularizing illconditioned matrices. The Tychonov regularization, for example, is based
80
CHAPTER 2.
REGULARIZATION
on the idea of shifting all singular values by a certain positive number~ to the right. For details we refer to [81]. 2.1.2
Moore-Penrose erators
inverses
and regularization
of op-
Let H be an infinite-dimensional Hilbert space with inner product (., .). An operator A E L(H) is said to be Moore-Penroseinvertible if there is an operator B ~ L(H) satisfying together with A the axioms (2.3). If such an operator B exists, then it is unique (see the proof of Theorem2.1), and we denote it by A+ again. Clearly, Corollary 2.3 remains valid also in this context. For infinite-dimensional spaces H there exist (in contrast to the finitedimensional setting) operators which are not Moore-Penrose invertible. An example is provided by the operator A = diag(1, 1/2, 1/3,...) E L(/2). (The only possible candidate for the Moore-Penrose inverse of A is the operator B = diag (1,2, 3,...), which is unbounded.) Here are two criteria for the Moore-Penroseinvertibility of an operator. Theorem 2.4 Let H be a Hilbert space. An operator A ~ L(H) is MoorePenroseinvertible if and only if it is normally solvable (i.e. if and only if its range is closed). + Proof. If A is Moore-Penrose invertible then the ranges of A and AA coincide by (the infinite-dimensional analogue of) Corollary 2.3. Since + AA is an orthogonal projection, it has a closed range. Thus, Im A is closed, too. Let, conversely, Im A be closed, and denote by HKand HI the orthogonal complements of Ker A and Im A in H. The restriction of A to HK is an invertible operator from HKonto Im A, and the inverse B of this restriction is bounded since Im A is closed and, hence, a Banach space. Weextend B to a bounded operator on all of H by setting B = 0 on the complementHx of Im A. It is easy to check that this extension is actually the Moore-Penrose inverse of A. ¯ A more detailed examination of Moore-Penrose invertible Example 2.16 below.
operators is in
Theorem 2.5 Let H be a Hilbert space. An operator A ~ L(H) is MoorePenroseinvertible if and only if A*Ais invertible or if 0 is an isolated point in the spectrum of A*A. In this case, [IA+II = sup{l/a:
a ~ a2(A) {0}}/
2.1. STABLY
REGULARIZABLE
SEQUENCES
81
Wewill prove this result in a more general situation in Section 2.2. If A E L(H) is Moore-Penroseinvertible, then we call A+f the least square solution of the equation Au = f. Thus, in the case of infinite dimension, least-square solutions are exclusively defined for normally solvable operator equations. Our next goal is to explain how to construct e-regularizations for operators which act on an infinite-dimensional Hilbert space. ’This requires some basic knowledge from the spectral theory of self-adjoint operators, which we will recall first. In what follows, we will exclusively apply the v-regularization to the approximation operators An, not to the operator A ~ L(H) itself. Thus, everyone who is only interested in (the practically relevant) approximation sequences (An) with finite matrices A,~ can ignore the remainder of this section. Let, for a moment, A be a bounded linear operator acting on a Banach space X, and let E be a closed subset of the complex plane. A closed linear subspace Mof X is called A-invariant if AMC_ M, and an A-invariant subspace Mof X is said to be a E-spectral subspace of A if (i) a(AIM) C_ ~, and (ii)
N C_ Mfor every A-invariant subspace N of X with a(AIN) C_ E.
Observe that a E-spectral subspace of an operator A ~ L(H) does not necessarily exist. On the contrary, one knowsexamples of linear operators on Banach spaces without any non-trivial invariant subspace, and it is still an open problem whether every bounded linear operator on a Hilbert space has a non-trivial invariant subspace. But if a E-spectral subspace of A ~ L(X) exists, then it is uniquely determined. The following result states that for self-adjoint operators on Hilbert spaces there is even an abundance of E-spectral subspaces. Theorem 2.6 Let H be a Hilbert space and A ~ L(H) be a self-adjoint operator. Given numberss, t ~ ~ with s < t, the Is, t]-spectral subspace o] A exists, and it is equal to Ker (A - sI) clos Im~s,~ ¯ K er(A - tI) where as,~
= ~ (t-
z)(s-
and Fs,~ is the curve in Figure 2.1.
z)(A-
-l dz
82
CHAPTER 2.
0
REGULARIZATION
t
-i
Figure 2.1: Integration path in Theorem2.6 If s or t belong to the spectrum of A, then the integral in the definition of ~8,t exists as a Cauchyprincipal value: ¯
-l 1 dz fr (t-z)(s-z)(A-~I)
where F~s,t is that part of Ps,t which lies outside the disks {z : and {z : [z For a proof of this and the following results we refer to [65], Chapter V. There the interested reader will also find a detailed study of the operators The following result is a consequence of Theorem2.6. Let [re(A), M(A)] denote the smallest closed interval which contains the spectrum of the selfadjoint operator A E L(H). Theorem 2.7 Let H be a Hilbert space and A ~ L(H) be a sel]-adjoint operator. Given a numbert ~ ~, the (-oc, t]-spectral subspace o] A exists, and it is equal to L := closIm ~t ® Ker (A - tI) where f~t
= ~ (t-
z)(A-
-l dz
t
and Ft is the rectangle with vertices t:ki and t-1-[t-m(A)[+i. Moreover, ((A- tI)x,x I <_ 0 whenever x ~ L, and ((A- tI)x,x) >_ 0 if x ±. Given a fixed self-adjoint operator A ~ L(H), let E(t) refer to the orthogonal projection from H onto the (-oc, t]-spectral subspace of A, and E(t-O) to the orthogonal projection onto the smallest closed subspace of H which contains Im E(s) for all s < t. Theorem 2.8 Let A ~ L(H) be a self-adjoint operator and s, t ~ ~ with s ~_ t. Then the Is, t]-spectral subspace L of A is equal to the range of
2.1. STABLY
REGULARIZABLE
83
SEQUENCES
E(t) - E(s - 0), a(AIL) N (s,t) = a(A) g~ (s,t). Thus, the spectrum of the restriction of A to its Is, t]-spectral subspace is essentially (with the possible exception of the boundaries s and t) equal the part of the spectrumof A whichlies in Is, t]. This is actually the result we need to define the e-regularization of a self-adjoint operator. Let us still mentionthat the (-oc, t]-spectral subspaces lead directly to a central result of functional analysis: the spectral theoremfor self-adjoint operators. Namely, the family {E(t)}teR forms what is called a partition of the identity on the interval Ira(A), M(A)]in the following sense: (i) Im E(s) C_ Im E(t) for all s _< t, (ii) Im E(s) = ¢~t>sImE(t), (iii)
E(t) : if t <m(A)
(iv) E(t) = if t > M(A) Property (i) is equivalent to E(s) = E(t)E(s) = E(s)E(t) for all s _< t, i.e. any two elements of {E(t)} commutewith each other, and property (ii) equivalent to the strong continuity of the partition {E(t)} from the right hand side: E(s)x li mt%sE(t)x for al l x E H. The following spectral theorem states that a self-adjoint operator does not only give rise to a partition of identity, but conversely, that every selfadjoint operator can be rediscovered from its partition of identity. This is a far reaching generalization of the fact that every self-adjoint matrix can be diagonalized. Theorem 2.9 (Spectral theorem) Let A ~ L(H) be a self-adjoint and {E(t)} the associated partition of identity. Then A
:
fM(A)+O
operator
z dE(z),
dm(A)-O
the integral taken in the Stieltjes sense. Nowwe are in a position to define the e-regularization self-adjoint non-negative operator A ~ L(H) by
(with ~ > 0) of
A~ := (I - E(~)) A = A (I - E(s)). Taking into account Theorems 2.5 and 2.8 one easily checks that A~ is Moore-Penrose invertible and that lid- A~I[ = ][AE(~)I[ _< ~ and []A~+II _< 1/e.
(2.9)
84
CHAPTER 2.
REGULARIZATION
One cannot exclude the equality sign in the latter estimate since Theorem 2.8 says nothing about the boundary e of the interval (-~x~,~]. In order to introduce the ~-regularization of an arbitrary operator A E L(H) we recall the notion of a partial isometry as well as the polar decomposition of an operator (which has its origins in writing a complex number as ur where lul = 1 and r _> 0). A partial isometry is an operator U e L(H) such that I]Uxll = [Ixll ±. for all xe(KerV) An equivalent characterization of partial isometries is the equality UU*U = U, which in particular shows that every partial isometry U is MoorePenrose invertible and that U+ = U*. Recall further that an operator R ~ L(H) is non-negative if (Ax, x) >_ for al l x ~ X. Theorem 2.10 (Polar decomposition) For every A ~ L(H), there exists a partial isometry U as well as a non-negative operator R such that A = UR and closImR = (KerU) ±. Both operators U and R are unique, and ~. A*A = R If A is an operator with polar decomposition URwhere R is Moore-Penrose += invertible, then A is Moore-Penrose invertible, too, and A+ = R+U *. R+U For checking this, take into account that U*Uacts on closIm R as the identity operator. Let nowA ~ L(H) be a not necessarily self-adjoint operator with polar decomposition A = UR, and let ¢ > 0. Then we define the ~-regularization A~ of A by A~ = UR~where R~ is the ~-regularization of R as defined above. Theorem 2.11 Let A ~ L(H) and e > O. Then the e-regularized operator Ae is Moore-Penroseinvertible, [IA- Ae[I <_ e and [[(Ae)+[I _< l/e, and moreover, A~Ae = R~. Proof. Westart with showing that A is Moore-Penrose invertible with Moore-Penroseinverse (RE)+ U*. Let (E(t)) denote the partition of identity associated with the self-adjoint operator R. Then A~A+~A~ = UR~(R~)+U*UR~---
UR~(R~)+U*UR(I- E(~)).
Since U*Uacts on closIm R as the identity operator, the right hand side of this equality coincides with UR~(R~)+R(I - E(~)) = UR~R+~R~ = UR~ The other axioms of Moore-Penrose invertibility Further we have
can be checked similarly.
II(A~)+II = II(R~)+U*II < II(R~)+II _< ~/¢,
2.1. STABLY
as well as
REGULARIZABLE
SEQUENCES
85
II(A~- A)*(A~ - I = [](Re - R)U*U(R -IR 2IIR-RelI I]E(¢)RU*URE(¢)II = I]E(¢)ReE(¢)II (2.1o)
A~A~ = R~U*UR~ = (I-
E(¢))RU*UR(I-
Z(¢))
e~
(2.11)
which finishes the proof. 2.1.3
Stably
regularizable
approximation
sequences
Let again H be a Hilbert space and (P,) be a sequence of orthogonal projections which converges strongly to the identity operator. Let further A E L(H) and An e L(Im P,) be operators such that AnP, and A~P, converge strongly to A and A*, respectively. Whatwe are interested in in this chapter is situations where (AN) is not an applicable approximation method for A. According to Polski’s theorem, the reasons for non-applicability might be (i) that A is not invertible, (ii) that infinitely manyof the An are not invertible, (iii) that the An are invertible for all sufficiently large n, but sup IIA~I]I = The wayout is obvious: in cases (i) or (ii) one will replace the usual inverses of A or An by their Moore-Penrose inverses (if they exist), and then one has to consider the problem whether A~+ -~ A+ strongly
as n -+ oo
(2.12)
(i.e. whether the least square solutions of Anun = In converge tothe least square solution of Au = f for every f). In case (iii) one will choose a cutting-off parameter ¢ > 0 and replace the operators An by their ¢regularizations A,~,~. Theorem2.11 guarantees that the operators A,~,~ are Moore-Penroseinvertible and that sup, IIA~+,~II < oo. The question in this case is whether A~+,~ -~ A+ strongly as n -~ o~ (2.13) (i.e. whether the least square solutions of the C-regularized equations A,~,~un,~ = fn converge to the least square solution of Au = f for every f). In addition we will require that IIAn,~ - A,~II -~ 0 in order to
86
CHAPTER 2.
REGULARIZATION
guarantee that (A~,~) is an approximation method for the same operator
as(An). Clearly, the approach via regularization can alsos be applied in cases (i) and (ii) or if sup ]IA~+II = oo and, as we shall see later, it yields in sense more satisfactory results and proves to be more natural in these cases than (2.12). For both problems (2.12) and (2.13), there are theorems of Polski type. Theorem2.12 Let H, Pn, A, A,~ be as above, and suppose that AnPn --~ A and A~Pn --~ A* strongly as n -~ oc. Then the following assertions are equivalent: (a) The equations Anu,~ = Pnf possess least square solutions un for all right handsides f and all sufficiently large n, and the sequence (Un) of these solutions converges in the norm of H. (In other words: the operators An are Moore-Penroseinvertible for all sufficiently large n, and the sequence (A+nPn)of their Moore-Penroseinverses converges strongly.) (b) The operators A,~ are Moore-Penroseinvertible for all sufficiently large n, and supn IIA+~P~II< If one of these conditions is satisfied, then A is Moore-Pcnroseinvertible, and A+nPn-~ A+ strongly as n ~ o~. Theorem 2.13 Let H, P,~, A, A,~ be as above, and suppose that AnPn -+ A and A~P,~ --~ A* strongly as n --~ oo. Then the following assertions are equivalent: (a) There is a parameter ~ > 0 such that ]IAn,~ - Anll -+ 0 as n -+ oo and such that the least square solutions of the regularized equations A,~,~u~,~ P,~f form a convergent sequence for every right hand side f E H. (b) There is a parameter ~ > 0 such that IIA~,e - Anll -~ 0 as n -~ oo and
supIId+,Pnll< If one of these conditions is satisfied, and A+~,~P,~~ A+ strongly as n
then A is Moore-Penroseinvertible,
Observe that in case H has infinite dimension, not every operator in L(H) is Moore-Penroseinvertible, and so we have to require the existence of least square solutions in Theorem2.12. If the An are finite matrices, one can obviously drop this assumption. On the other hand, e-regularized operators are Moore-Penrose invertible in any case, and so the regularized equations An,~u,~,~ = Pnf are always least square solvable. To prove Theorems 2.12 and 2.13 we still need a few more results on Moore-Penrose inverses in C*-algebras, which will be presented in Section 2.2.1. The analogy between Theorems 2.12 and 2.13 on the one hand and Polski’s theorem for stable approximation sequences on the other hand
2.1.
STABLY REGULARIZABLE SEQUENCES
87
suggests to call a boundedsequence (An) of operators Moore-Penrosestable if it satisfies condition (b) of Theorem2.12 and stably regularizable if it is subject to condition (b) of Theorem 2.13. Thus, Theorems 2.12 and 2.13 reveal that it is again a (generalized) stability property of the sequence (An) which is essential for the (generalized) applicability of the approximation method (An). To have a few trivial examples, consider the n x n matrices (i) An = diag(1,1,...,1,1), (ii) An = diag(0,1,...,1,1), (iii) An = diag (l/n, 1,..., 1, 1), (iv) An = diag (l/n, 1/(n - 1),...,
1/2, 1).
The sequence (An) is stable in case (i), Moore-Penrose stable (but stable) in case (ii), stably regularizable (but not Moore-Penrosestable) case (iii), and not stably regularizable in case (iv). At the same time, these elementary examples already provide a good picture of the behaviour of the singular values of (generalized) stable approximation sequences (An) (compare Figure 2.2): Theorem 2.14 A bounded sequence (An) o] operators An E L(Hn) (a) stable if and only if there is a numberd > 0 such that a2(An) (b) Moore-Penrosestable if and only if there is a number d > 0 such that a2(An) C_ {0} U [d, ~), (c) stably regularizable if and only if there are numbersd > 0 and ¢n >_ with limCn= 0 such that a2(An) C_ [0, en] U [d, ~x)) for all n.
a2(A,~) V/’/’,-"/ d
(An) stable
Moore -Penrose
stable d a2(An)
(An) stably regularizable
0
d
Figure 2.2: Location of the singular values Proof. Assertions (a) and (b) are immediate consequences of Theorem 2.5. For a proof of (c), let first (An) be a stably regularizable sequence,
88
CHAPTER 2.
REGULARIZATION
and let An = UnRnbe the polar decomposition of An. Observe that, A~An = R2~ by Theorem 2.10, a2(An)
= V/a(A~An)
since
= ~ = a(Rn)
and, analogously by Theorem 2.11, a2(An,~) a(Rn,~) for ev ery ~ > 0. Set Cn := IIAn,~ - Anll and 1/d := supn IIAn+,~ll. Then d > 0 and ¢n -} 0 as n -~ cx~, and it remains to showthat a2(An) C_ [0,~n] (A [d, o~). From(2.10) we conclude that ~n = [[An,~ - An[[ = [[Rn,~ - Rn[[ = [[E(¢)Rn[[ = sup{ A: A e a(E(~)Rn)} which in combination with Theorem 2.8 yields a(Rn) [0,¢] = a~(An) N [0,¢] C_[0, ¢n].
(2.14)
Further we infer from Theorem 2.5 that
IIA+~,AI: sup(l/a: a e a2(A,~,e) \ {0} <_.lid respective inf{ a : a E a2(An,~) \ {0} } _> d, and since a:(An,~) -- ae(Rn,~) = a((I-E(e))R,~)
C_ a(Rn)V~[¢,~) :- a2(An)N[~,cx~)
by Theorem2.8 again, we finally arive at ae(An)N [~, oo) C_[d, oo).
(2.15)
From (2.14) and (2.15) we obtain the desired inclusion a2(An)C_[0, en] f~ [d, oo).
(2.16)
If, conversely, (2.16) is satisfied with certain numbers d > 0, and en _> tending to zero then choose ~ E [0, d) arbitrarily, and let A,~,~ denote the e-regularization of An. By repeating the above arguments it is not hard to check that [[A,~,, - An[[ _< en and [[A~+,~[I _< l/d, which implies the stable regularizability of (An). ¯ Let us once more emphasize that the stable regularizability of a sequence (An) is equivalent to the splitting of the set a2(An) into two parts: tending to zero with n going to infinity, and one remaining bounded away from zero by a positive constant for all n. For a deeper investigation of this splitting property (which will concern the numberof the singular values in [0, cn]) we refer to Chapter 6.
2.2. ALGEBRAIC
2.2
CHARACTERIZATION
89
Algebraic characterization ularizable sequences
of stably reg-
The main result of this section relates the stable regularizability of a sequence (A,~) E ~ with a property of thecoset (An) +~ E 9v/G, viz. with its Moore-Penroseinvertibility. Westart with recalling some facts concerning Moore-Penroseinvertibility in C*-algebras. 2.2.1
Moore-Penrose
invertibility
in
C*-algebras
Let /~ be a C*-algebra. An element a ~ B is said to be Moore-Penrose invertible if there is a b ~ B such that aba = a, bab-~ b, (ab)* = ab, and (ba)* = ba. (2.17) The proof of Theorem2.1 shows that the element b is unique (if it exists) and we call b the Moore-Penroseinverse of a and denote it by a+. One easily checks that a and a* are Moore-Penroseinvertible only simultaneously and that (a*) + = (a+) * and (a’a) + = a+(a*) +, (2.18) + + whereas the identity (ab) = b+a is wrong in general. The following theorem summarizes some equivalent conditions for the Moore-Penrose invertibility in unital C*-algebras. Recall that an element p of a C*-algebra is a projection if it is idempotent(i.e. p2 = p) and self-adjoint. Theorem2.15 Let I~ be a C*-algebra with identity e. The ]ollowing conditions are equivalent for every element a o] B: (a) The element a is Moore-Penroseinvertible. (b) The element a*a is invertible or 0 is an isolated point o] a(a*a). (c) There is a projection p in alg (e, a’a) (--- the smallest closed subalgebra o] B which contains e and a’a) such that a*ap = 0 and a*a+pis invertible. (d) There is a projection q in l~ such that aq = 0 and a*a ÷ q is invertible. I] one o] these conditions is satisfied, then q is uniquely determined, and
a+ = + as well as II +ll = sup{1/ : e \ {0} }.
Proof. (a) ~ (b): Let a be Moore-Penrose invertible and set b +. If a = 0, then 0 is an isolated point ofa(a*a). Ifa ~ 0, then b ~ 0, and e-)~bb* is invertible in/~ for every complex A with 0 < ]~1 < Ilbb*l1-1 (Neumann series). A straightforward calculation shows that (e-)~bb*)-lbb * - 1/A(e ba) is the inverse of a’a- Ae, i.e. either 0 ~ a(a*a) or 0 is an isolated point of that spectrum. (b) ~ (c): a*ais i nvertible, choo se p = 0. Solet 0 b e an is olated
9O
CHAPTER 2.
REGULARIZATION
point of a(a*a). The C*-algebra alg (e, a’a) is commutative; thus, by the Gelfand-Naimark theorem, this algebra is *-isomorphic to the C*-algebra C(X) where X is a certain compact, and every element c E alg (e, a’a) corresponds to a certain continuous function ~ on X. Thereby, at3(c) aalg(e,a*~)(c) = ac(x)(~) = ~(Z) for every c e alg(e,a*a). Set X0 := {x e X : (a*a)(x) = 0} and X1 := X \ X0. Assumption (b) guarantees that sets X0 and X1 are both open and closed subsets of X. Hence, :
X--+C
x~
0 [
if
x~X1 1 if x~Xo
defines a continuous function on X. Let p denote the (uniquely determined) element of aig (e, a’a) which corresponds to this function. One easily checks (by considering functions instead of elements again) that p is subject to the condition (c). (c) ~ (d): a*ap = 0, then 0 = ]]pa*ap]l = ]] (ap)*(ap)ll = Ha 2, hence one can choose q := p. (d) =~ (a): It is straightforward to Check that (a*a + q)-la* is the MoorePenrose inverse of a. Let us show the uniqueness of q. From aq = 0 we obtain that (a* a + q)q = and, he nce, (a * a + q)-i q =
(2.19)
whereas the identity a + = (a*a + q)-la* involves (a*a + q)-la*a -= a+a.
(2.20)
Addition of (2.19) and (2.20) yields e = q + a+a or q = e - a+a, which shows the uniqueness. Finally, the norm identity follows from
2 = Ila÷(a÷)*ll Ila÷ll2 = II(a÷)*ll = Ila÷(a*)÷ll _-II(a*a)÷ll by employing the *-isomorphy (which is actually aig (e, a’a) and C(X) again.
an isometry) between ¯
Wedenote the (uniquely determined) projection q in (d) n, and call a rI the Moore-Penroseprojection associated with a. Example 2.16 Operators on Hilbert space. Let A be a bounded linear operator on a Hilbert space H, and suppose that A is Moore-Penrose invertible (i.e. Moore-Penroseinvertible as element of the C*-algebra L(H)). Let B ~ L(H) be the Moore-Penrose inverse of A, and denote the orthogonal projections AB and BA by P and I - Q, respectively. From Im A = Im ABA C_ Im AB C_ Im A,
2.2. ALGEBRAIC
CHARACTERIZATION
91
Ker A _C Ker BA C_ Ker ABA = Ker A we conclude that ImA=ImP
and
KerA=Ker(I-Q)
which in particular showsthat the range of A is closed and that the MoorePenrose projection of A is actually the orthogonal projection from H onto the kernel of A. If, conversely, A E L(H) is an operator with closed range and with orthogonal projection Q from H onto the kernel of A, then AQ = 0, and the operator A*A+ Q is invertible which can be seen as follows: Let x belong to the kernel of A*A ÷ Q. Then, since AQ = 0 and QA* = O, one has (I - Q)A*A(I - Q)x + Qx whic h immediately give s Qx =0 and (I - Q)A*A(I - Q)x = Thelatt er equa lity impl ies ((I Q)A*A(I Q)x, x) = (A(I - Q)x, A(I - = 0, i. e. A(I - Q)x = 0. S in ce Q is the orthogonal projection onto the kernel of A, one has (I - Q)x -- 0 and, consequently, x -- 0. Further, A*A÷ Q is self-adjoint and, hence, Ker (A*A + Q) Im(A*A + Q) = H So it remains to show that the range of A*A+Qis closed. From A*A+Q= (I - Q)A*A(I - Q) and the fact that proje ctions are n ormally solva ble we conclude that A*A ÷ Q is normally solvable if and only if A*A is so. Thus, let z = lim A*Ax,~. Since A* is normally solvable whenever A is so, the vector z must belong to the range of A*, that is, z = A*y with some y E H. If further P denotes the orthogonal projection onto the (closed) range of A then PA = A and A*P = A*. Consequently, there is an x ~ H such that y = Ax and z = A*Ax. The closedness of Im A*A implies that of Im (A*A ÷ Q), which, via the preceding theorem, yields the Moore-Penrose invertibility of A. . Example 2.17 Self-adjoint elements. A self-adjoint element a of a unital C*-algebra B is Moore-Penroseinvertible if and only if it is invertible or if 0 is an isolated point of the spectrum of a. This follows from the equivalence of (a) and (b) in the preceding theorem and from the identity a(a*a) = a(a2) = a(a) 2. Further, repeating the arguments of the implication (b) =~ (c) with the Moore-Penroseinvertible element a in place a’a, one obtains the existence of a projection p in alg (e, a) such that ap = 0 and a ÷ p is invertible. Conversely, if p is a projection possessing these properties, then it is straightforward to check that (a + p)-i (e - p) is Moore-Penrose inverse of a. Combiningthese observations with those from Example 2.16 above, one easily gets that the Moore-Penrose inverse of a self-adjoint and normally solvable operator A ~ L(H) is A+ (A+P~/er -1
92
CHAPTER 2.
RE, GULARIZATION
As we have already observed, one peculiarity of C*-algebras is their inverse closedness with respect to usual invertibility, which simplifies the study of invertibility problems in C*-algebras essentially. It is an immediate consequence of Theorem2.15 that C*-algebras are also inverse closed with respect to Moore-Penroseinvertibility. Corollary 2.18 Let B be a C*-algebra with identity and C be a C*- subalgebra o] 13 which contains the identity. If c E C is Moore-Penroseinvertible in 13, then c + ~ C. Indeed, the inverse closedness of C*-algebras with respect to the usual invertibility gives a~(c*c) = ac(c*c), and the equivalence of (a) and (b) Theorem 2.15 yields the assertion. ¯ As a first application verified analogously.
we will prove Theorem 2.12. Theorem 2.13 can be
Proof of Theorem 2.12 . The implication (a) :=~ (b) is an immediate consequence of the Banach-Steinhaus theorem. For the reverse implication, consider the C*-algebra ~ of all bounded sequences (A,~) of operators A,~ L(Hn), and let "C denote it s su bset co nsisting of all sequences (An)for which the strong limits s-lim AnPnand solim A~Pnexist. The set 5re is a C*-subalgebra of ~- which contains the identity of ~’. Without loss of generality we now suppose that (An) is a sequence such that all An are Moore-Penrose invertible and sup IIAn+ll < ~. Then (An) belongs to ~-c, and the sequence (An+) belongs to 9t- and is just the Moore-Penrose inverse of (An) in ~’. From Corollary 2.18 we infer that (An+) also belongs to ~-c, i.e. the strong limits B s-lim A+~P, and B* := s-lim (An+)*Pnexist. Letting in AnAn+A~= A,~, An+A,~A+,~= A+~, (A,~A+~)* = A,~A+~, (A+~An)* = A+~A,~ n go to infinity we obtain ABA = A, BAB = B, (AB)* +. i.e. A is Moore-Penroseinvertible, 2.2.2
Stable regularizability, vertibility in ~’/G
---
AB and (BA)*
= BA, ¯
and B --- A and
Moore-Penrose
in-
Let H be a Hilbert space, (Hn) be a sequence of subspaces of H, v t he C*-algebra of all bounded sequences (An) of operators A,~ ~ L(Hn), and the ideal of all sequences (An) ~ ~ tending to zero in the norm. The goal this section is to prove the following characterization of stably regularizable sequences in ~’.
2.2. ALGEBRAIC
CHARACTERIZATION
93
Theorem2.19 A sequence (A~) E jz is stably regularizable i] and only the coset (An)+ G is Moore-Penroseinvertible in the quotient algebra i.e. i] there is a sequence (Bn) ~ if: such that IIA,~B,~An- A,~II ~ O, IIB,~A,~B,~ - B,~II ~ O, II(A,~B~)* - A,~B,~II -~ O, II(B,~A,~)* - BnA,~II--+ The proof of Theorem2.19 requires some additional statements. The first asserts that every ’almost projection’ has a projection in its neighborhood. Proposition 2.20 Let B be a C*-algebra with identity e, and let a ~ B be a self-adjoint element with Ila - a211 < 1/4 (an ’almost projection’). Then there is a self-adjoint element g ~ t3 such that a + g is a projection and
Ilgll-<2Ila- a~ll. Proof. Wewill prove that g can be found in alg (e, a), the smallest closed subalgebra of B which contains e and a. Since alg (e, a) is a commutative C*-algebra, it is *-isomorphic to the algebra C(X) with a certain compact X by the Gelfand-Naimark theorem, and every element b ~ alg (e, a) can be identified with a continuous function/~ on X. Set s := Ila -aell < 1/4. Since the mappingb ~-~ ~ preserves involutions, we conclude that 5 is a real-valued function, and the isometry of the mapping b ~/~ yields that
Ila - a211-- 115- 521t=~ I~(x)- ~(x)2] =s < 1/4. Hence, the compact X decomposes into two both open and compact sets X0 := { x e X: 5(x) E [1/2 - ~/VqTT~, 1/2 - VqT~- s] Xl:={xeX:
5(x)
e[1/2+~,1/2+~]},
which implies that the function 15 : X-+C ’
x~ { 01 if if
x~Xo x~X1
is continuous on X. Let p E alg (e, a) be the element which corresponds the function 15. One easily checks (by operating with functions instead of elements) that p is a projection in B and that .Ila-pll--maxla(x)-p(x)l x~X
< s--Ila-aZll --
Hence, choosing g :-- a - p, we get the assertion.
¯
94
CHAPTER 2.
REGULARIZATION
Let B be a C*-algebra and ~ be a closed two-sided ideal of/3. One says that lC lifts projections if, for every coset a + lCE /3/1~ which is a projection in /3//C, there is a representative a + k of the coset a + ~ which is projection in/3. Observe that not every closed ideal of a C*-algebra lifts projections, and that the ’solution’ a + k of the lifting problem is not necessarily unique. Elementary examples can be found already among the algebras of continuous functions. Proposition 2.21 The ideal ~ of 3: lifts
projections.
Proof. Let (An) + ~ be a projection in ~. Since every self-adjoint coset contains (at least one) self-adjoint representative, we can suppose (An) be self-adjoint in 9v, i.e. we have A~= Anfor all n, and IIAn - A2nll -~ 0. If n is sufficiently large, say n _> no, then HAn-A~nll < 1/4, and Proposition 2.20 entails the existence of self-adjoint operators Gn ~ L(Hn) such that An + Gn is a projection and IIGnll <_ 2 IIAn - A~II. If we define Gn = -An for n < no, then A,~ + Gn becomes a projection for every n and, hence, (An + Gn) is a projection in r. Finally, t he s equences (An) and ( An) + belong to the same coset modulo6 because IIG,~II _~ 2 IIA,~ - A~II --~ 0 as n --~ (x).
¯
Given a sequence (An) ~ ~- such that (An)+~ is a Moore-Penrose invertible coset in ~-/~, we denote by II(An) tile set of all projections in ~" which are representatives of the Moore-Penrose projection ((An)+ n associated with (An) + ~. By Proposition 2.21, H(An) is not empty. The following result states that the set H(An) always contains an (essentially unique) sequence (Hn) such that A~AnIIn = [inA~An for all n. This observation will be employed later on in order to diagonalize the matrices A~Anand [I n simultaneously. Theorem 2.22 Let (An) ~ J:, and suppose (An) + 6 to be Moore-Penrose invertible in J:/~. Then there is a sequence (1-In) ~ H(An)such that Hn alg (A~An, IIHn) (= the smallest closed subalgebra o] L(Hn) which contains A~Anand the identity IIHn) ]or all n. The sequence ([In) is unique in the and ]ollowing sense: I] Hi(n), (II~) IX(An) E IIn,~ n2 ~al g(A~An,IIHn) ]o all n, then [i~ = II~ ]or all sufficiently large n. Proof. Let (Rn) be a sequence in II(An), i.e. the Rn are projections, (Rn) + ~ = ((An) + ~)II. By Theorem 2.15 (c), (Rn) + ~ ~ alg~:/6((A~A~) (I [H.) + 6). Thus, one can find polynomials Q~, Q~,... in one variable such that liQ~((A~An) + ~) - ((Rn) ~)[[:r/~ "-
~ 0 ask -
and
2.2. ALGEBRAIC
CHARACTERIZATION
95
With the limsup formula for the norm in ~’/G (Proposition 1.16) this gives lim limsup IIQk(A~A~) - Rnll = which together with the obvious estimate 0 ~ diStL(H.)(Rn, alg (A~An, I~H.)) ~ ~[Qk(A~An)yields lim~ diStL(H~)(Rn, alg (A~An, I[H~)) : Lete~ denote the distance between the operator Rn and the algebra alg (A~An, I[H.), and let B~ be operators in this algebra such that I]B~ - R~[] < 2en. These operators can be chosen to be selhadjoint; indeed, if [[Bn - R~[[ < 2~, then ~B~ - Rn~l = ~B~ - R~ < 2~, whence
II(B~+ B~)/~- R~II~ (IIB~- R~II+ IIB~- R~II)/~ ~. ~rther
one h~
B~ - B. = n.(~.
- R.) + (B. - R.)n.
+ (~. = - (S.
which gives
Choose n0 such that 6~u + 4s~ < 1/4 for ~l n ~ no. Then B~ is an almost projection in sense of Proposition 2.20 for n ~ n0, and the same proposition yields the existence of selhadjoint operators G. in alg (A~A., I]~.) such that Bn + Gn is a projection and
Set Hn := I~g. for n < n0 and Ha := Bn + G. for n ~.no. The sequence (Hu) is a projection in ~ by construction, every H. belongs alg (A~An, IJg.), and the estimate
IIR.- ~.11~ IIR.- B.II+ I1¢-II< 1~.+ for n ~ no shows that (Rn) and (Hn) belong to the s~e coset modulo Hence, (Ha) e H(An). For a proof of the uniqueness, let (H~), (H~) be two sequences of 2 jections which are subject to the conditions of the theorem. Then 1H.H n = 2 1 H.H., hence (H~ - H~)2 is a projection for every n. On the other hand, ~$(H~- H~)e]] ~ ~JH~ - H~]Je ~ 0 as n ~ ~, and the only projection with norm less than one is the zero operator. Consequently, H1n -Hn2 is nilpotent for all sufficiently large n. Since H~ - H~is self-adjoint, this gives H~= H~
CHAPTER 2.
96
REGULARIZATION
for all large n.
¯
Let SII(An) denote the set of all sequences (1-In) in II(An) such that belongs to alg(A~A,~,IIg., ) for every n. By Theorem 2.22, SII(An) ~ As we have just observed, any two sequences in SH(An) can differ only in finitely manyelements. Proof of Theorem 2.19. To start with, let (An) + G be Moore-Penrose invertible and (H,~) e SH(An). Then, by Theorem 2.15(c), ((A~,An) G)((Hn) + ~) = 0, and the coset ((A~An) + ~) (( IIn) + ~)is inv ertible. Equivalently, IIA~A~IIn ][ ~ 0 as n ~ oo, and the sequence (A~A,~+II,~)n~__I is stable. Choose d such that
lid > limsup II(A~An+ IIn)-IlILCH,,~= II((A~An+ IIn) set ~n := I]A~AnIInl], and fix no such that ]](A~An + IIn)-IIIL(H,)
1/ d for al l n k no
(2.21)
and en
all
n_>no.
(2.22)
For n k no, consider the commutative C*-algebra alg (A~A,~, IIH.). This algebra is *-isomorphic to C(X) for some compact X by the GelfandNaimark theorem, and we let ~ and/5 refer to the continuous functions on X corresponding to A~A,, and Hn, respectively. From (2.21) and the fact that *-isomorphisms are isometries we conclude that 5(x) + ~(x) for all x ~ X, whereas the choice of ~,~ implies that 5(x)ih(x) _< en for x ~ X. The function 15 is a projection and can take the values 0 and 1 only. Thus, if 5(x) < d, then necessarily 15(x) = 1, and if ~(x) > en, necessarily 15(x) = 0. By (2.22), this involves that (e,~, d)~5(X) = the spectrum of A~A,~ resp. the singular values of An show the splitting behaviour discussed at the end of the preceding section, which is equivalent to the stable regularizability of (An). For the reverse implication we start with the splitting property of the spectrum of A~An, i.e. we let d > 0 and en k 0 be numbers with limen = 0 such that a(A~An)C_ [0, en] U [d, oo). (It obviously doesn’t matter whether we assume the splitting property for the spectra of A~A, or for the singular values of An.) Choose no so that en < d for n _> no. Given n k no we represent the commutative C*-algebra alg (A~An, I]~,) as the algebra of all continuous functions on some compact X, and we denote by ~ the function which corresponds to the operator A~,An. Our assumptions guarantee that the
2.2. ALGEBRAIC
CHARACTERIZATION
97
function 15:
X-4C,
1 if a(x)~[O, x~ 0 if a(x) E[d,~)
is continuous on X, and one easily checks that 0 < a(x)15(x)
< Cn for all
x EX
(2.23)
and a(x) + 15(x) > max{1, d} for all
x e X.
(2.24)
For n > no, let Hn ~ alg (A~An, IIH.) be the operator which is associated with 15. Then IIn is a projection, IIA~AnIInll <_ en -4 0 as n -4 ~ by (2.23), and the operator A~An+ l-In is invertible and satisfies the estimate II(A~An + IIn)-lll _< min{1,1/d} by (2.24). On defining Hn = 0 for n < no, we thus obtain a sequence (Ha) which is a projection in v s uch t hat 11 ((A~An) ~)((Hn) + ~)II = 0 (( A~An ) + ~) +(( Ha)+ ~) is in vertib Theorem2.15(c) yields the Moore-Penroseinvertibility ¯
As a consequence of this proof, one has Corollary 2.23 Let (An) ~ J: be a stably regularizable sequence with a(A~An) C_ [0, en] U [d,~x~) where d > 0 and en > 0 are numbers with limen = 0, and let (l’In) ~ SII(An). Then 1-In is the [O, en]-spectral projection of A~Anfor all sufficiently large n.
2.2.3
Finite sections of Toeplitz operators and their stable regularizability
The first application of the characterization of the stable regularizability of a sequence as the Moore-Penroseinvertibility of the coset of that sequence modulo~ concerns the stable regularizability of the sequence (P~T(a)Pn) of the finite sections of a Toeplitz operator T(a) with continuous generating function. In Section 1.4.2 we introduced the C*-algebra S(C), which is the smallest C*-subalgebra of 5r containing all of these sequences, and we proved that S(C) contains the ideal ~ of the zero sequences and that S(C)/~ is *-isomorphic to a subalgebra of L(l 2) x L(/2), the isomorphism sending the coset (A,~) + 6 to the ordered pair (W(An), IV(An)).. Let (An) be an arbitrary sequence in S(C). This sequence is stably regularizable if and only if the coset (An) ÷ ~ is Moore-Penroseinvertible in 5r/~ (Theorem 2.19), and the latter is equivalent to the Moore-Penrose invertibility of (An) + in S(C)/~ (in verse clo sedness, Cor ollary 2.1 8). Finally, by Theorems1.55 and 1.57 (and inverse closedness again), the coset
CHAPTER 2.
98
REGULARIZATION
(An) + 6 is Moore-Penrose invertible in S(C)/~ if and only if the symbol of this coset, i. e. the pair (W(A,~), IYV(An)), is Moore-Penroseinvertible in L(/2) L(12). So, to gether wi th th e ch aracterization of Moore-Penrose invertible operators given in Theorem2.4 we get: Theorem 2.24 The sequence (An)_ E S(C) is stably regularizable only if both operators W(An) and W(An) are normally solvable. A more explicit 1.53.
if
form of this result can be obtained by invoking Theorem
Theorem 2.25 Let a be a continuous function, K and L be compact operators, and (Gn) be a sequence tending to zero in the norm. The sequence (PnT(a)Pn + PnKPn+ RnLRn+ Gn) is stably regularizable if and only the operators T(a) + K and T(5) + L are normally solvable. The operators T(a) + and T( 5) + L belong to the alge bra T(C)which is the smallest closed subalgebra of L(l ~) containing all Toeplitz operators with continuous generating function and, moreover, the operators of the form T(a) + al ready ex haust T( C) (Theorem 1. 51). Fo r th e no rmal solvability of operators belonging to T(C) one has the following result. Proposition 2.26 Let a be a continuous function on ~ and K ~ K(/2). Then the operator T(a) + K is normally solvable if and only if one of the following alternatives holds:
(i) a(t) # o for all t V, (ii) a(t) = 0 for all t e 7~, and g has finite rank. Proof. From (1.21) we know that a Toeplitz operator T(a) is compact if and only if a -- 0. Thus, the mapping T(C) -~ C(T), T(a) + g ~-~
(2.25)
is correctly defined, and with (1.16) and (1.17) and the compactness the Hankel operators H(a) and H(5) (Lemma1.33) one easily checks (2.25) is a *-homomorphism. Let now T(a) ÷ K ~ 7-(C) be normally solvable. Then T(a) + is Moore-Penrose invertible, and (T(a) + + belongs to T(C) again (in verse closedness, Corollary 2.18). Hence, (T(a) + + = T(b) + with b ~ C(~’) and R ~ K(l:), and applying the homomorphism (2.25) to each of the identities (T(a) + K)(T(b) + R)(T(a) + K) (T(b) + R)(T(a) + g)(T(b) + R)
2.2.
ALGEBRAIC CHARACTERIZATION
99
and ((T(a) + K)(T(b) + R))* = (T(a) +
((T(b) + n)(T(a) + (T(b)n)(T(a) one arrives at the Moore-Penroseinvertibility of the function a in C(~). By Theorem2.15(b) this implies that either a has no zero on ~, or vanishes at every point. If, conversely, a(t) ~ for ev ery t E ~, the n T(a) + Kis a Fredholm operator (Theorem 1.30) and, hence, normally solvable, whereas in case a = 0 the operator T(a) + K = is normally sol vable if andonlyif K has finite rank. ¯ So we obtain a third equivalent formulation of Theorem2.24: Theorem 2.27 Let a be a continuous function, K and L be compact operators, and (Gn) be a sequence tending to zero in the norm. The sequence (PnT(a)Pn + PnKPn+ RnLRn+ Gn) is stably regularizable i] and only either (i) a(t) # O.for all t E ~£ (ii) a =_ O, and K and L have finite rank. Wewould like to emphasize two points. The first one concerns the way of proving Theorems2.24-2.27. Observe that the only things we utilized were the characterization of the stably regularizable sequence (An) via the Moore-Penrose invertibility of the coset (A,~) + ~ in ~’/~ (which is true for arbitrary bounded sequences (An)), then an inverse closedness argument which allows us to consider this Moore-Penrose invertibility problem in any C*-subalgebra of ~/~ which contains (An) + ~, and finally an exact description of a certain C*-subalgebra of ~’/~ which contains the coset (P,~T(a)Pn) (andwhichis the res ult of a de tai le d analysi s of the stability problem for the sequences (PnT(a)Pn)). Thus, the ’right’ answer to the usual stability problem for sufficiently manysequences will almost automatically also solve the problem of stable regularizability for these sequences. In Chapter 4, we will examinea lot of (partially muchmore involved) usual stability problems for concrete approximation methods, and we will solve them ’in the right manner’, so that the above analysis also applies. The second remark concerns the stability with respect to small perturbations of stably regularizable approximation sequences. Since stable regularizability is equivalent to Moore-Penroseinvertibility, and MoorePenrose invertibility fails to be stable with respect to small perturbations, one cannot expect stability under small perturbations for stably regularizable sequences. But, in contrast to Moore-Penrosestable sequences, stably regularizible sequences are stable at least under perturbations tending to
100
CHAPTI~R
2.
REGULARIZATION
zero as n tends to infinity. Moreover,in the only interesting case of Theorem 2.24 (when W(An) and l~(An) are Fredholm operators), stably regularizable sequences behave stably with respect to small perturbations (since Fredholmness is a property which is stable under small perturbations, and this property carries over to the corresponding approximation sequences via symbol calculus). Wewill pick up this observation in Chapter 6.
2.2.4
Convergence
of
generalized
condition
numbers
The (generalized) condition number of a Moore-Penrose invertible element of a C*-algebra is defined as conda := Ilall Ila+ll. In this section we are going to examine the convergence of the condition numbers cond An,~ for stably regularizable approximation methods (An). Wewill make use the somewhat more general frame introduced in Section 1.6.1, i.e. we let Cn (n = 0, 1,...) denote unital C*-algebras and consider their product v respective their restricted product 6 which is an ideal in 9r. Also, given a strongly monotonically increasing sequence ~/ : N --~ N, let Rn stand for the restriction operator (an) (a n(n)) an d de fine An:= Rn() for every subalgebra A of ~’. Motivated by Theorem 2.19, we call a sequence (an) E ~ stably regularizable if the coset (an) + 6 is Moore-Penroseinvertible in ~-/6. Theorem 2.28 z. Let A be a fractal C*-subalgebra of :7 (a) A sequence (an) ~ A is stably regularizable if and only if it possesses an infinite stably regularizable subsequence. (b) Let (an) ~ -A be a stably regularizable sequence, and let (bn) ~ jz sequence such that (bn) + 6 is the Moore-Penroseinverse o] (an) + 6. the limit lim,~ ]]anll Hbn]lexists and is equal to ]](an) + 61111(bn)+ 611Proof. (a) If (a,~) ~ A is stably regularizable then, clearly, every finite subsequence of (an) is also stably regularizable. Let, conversely, ~? be a monotonically increasing sequence such that (an(,~)) = Rn(an) is a stably regularizable sequence. By definition, this is equivalent to the Moore-Penroseinvertibility of Rn(a=) + 6n in th e quotient algebra J:n/6n. The inverse closedness property with respect to Moore-Penrose invertibility (Corollary 2.18) entails that Rn(an) + 6n is already Moore-Penrose invertible in (-An + 67)/6n, which, by the third isomorphy theorem, implies the Moore-Penroseinvertibility of Rn(an) + An f3 6n in An/(An ~3 67). Finally, from Corollary 1.68 we infer that .A7 f3 67 = (.A t3 6)7, which involves the Moore-Penroseinvertibility of the coset Rn(a,~) + (.A f3 6)n in An/(A N 6)7. Thus, there is a sequence (b,~) ~ A as well as sequences
2.2. ALGEBRAIC (g(~l)),...,
101
CHARACTERIZATION
(g(n4)) e A n 6 such
(2.26)
By hypothesis, the canonical homomorphism~r from A onto A/(A ~ ~) is fractal, i.e. there is a homomorphism% such that 7r = ~r~ Rv. Applying ~rv to the identities (2.26) gives the Moore-Penroseinvertibility of the coset zr(an) with the Moore-Penrose inverse ~r(an) + = ~r(bn). Hence, (an) stably regularizable. (b) Let (a,~) + ~ be Moore-Penrose invertible in ~’/~, and (bn) ((an) + + with a sequence (b n) E v. Repeating the arguments of p art (a) of this proof, we see that (an) + A N ~ is Moore-Penroseinvertible A/(‘4 N ~). Let (b~) E .4 be a sequence such that (b~) + .4 ~ G is Moore-Penrose inverse of (an) + A ~ G in A/(A N ~). From Theorem 1.71 we know that
and from the uniqueness of the Moore-Penrose inverse in ~’/~ we conclude that [[bn - b~l[ --~ 0. Hence,
which finishes the proof. To illustrate the efficiency of this theorem for a concrete approximation method we consider once more the finite section method for Toeplitz operators, i.e. we specify 5r and ~ accordingly and choose .4 = S(C). This algebra is fractal as we have seen in Corollary 1.70. Theorem 2.29 Let (An) ~ S(C) be st ably re gularizable se ~ > 0 is sufficiently small, then the limit lim condA~ = lim IIAn,~IIIIA~+,~II exists, and it is equal to
max{llW(An)ll, II (A)II}" max{llW(An)+ll,
quence. I]
102
CHAPTER 2.
REGULARIZATION
Proof. As IIAn - An,s]l ~ 0 (by definition) and 6 C_ $(C) (by Theorem 1.53) we see that the sequence (An,s) belongs to the fractal algebra S(C) and, hence, by Theorem 2.28, lim condAn,s = lim IIAn,~ll IIA+~,~II = II(An,s) In Section 1.4.2 we saw that H(A~,~) + ~H = max{HW(A-,~)~, H~(A~,~)~),
Since IIA~,~- A.II ~ 0, it is ~(A~,~) = ~(An), and applying of the identities A~,eA~,~A.,~
immediate that W(An,~) ~ W(A~) the *-homomorphisms W and ~ to
+ ~ + = A~,~, A~,~An,~A.,¢
=A ~,~,
(An,~A~,~)* = An,eA~,~, (A~,~An,¢)* = A~,~ An,~ (which is justified since (An,e) belongs to 6(C)) we W(A~,~) = W(A~,~) + = W(A~) + + and ~(A~,~)
= ~(A~)
which yield8 the assertion. For a further specification, we denote the e-regularizations of the Toeplitz matrices P~T(a)Pa by Tn,~(a). Corollary 2.30 Let a be a continuous ]unction on ~ with a(t) ~ 0 ]or all t ~ ~. I] e > 0 is su~ciently small, then the limit lira condTn,e(a) = lira IIT~,¢(~)II
Proof. If 0 ~ a($) then the sequence (PnT(a)Pn) is stably regularizable by Theorem2.27, and thus the existence of the limit ~ well as the equality lim condTn,e(a) with ~(t) = a(1/t)
m~ (llT(~)ll, II T(a)ll}" ma x(llT(~)+ll, are consequences of Theorem 2.29. The equalities
IIT(~)II : IIT(a)ll~ndIIT(~)+II = IIT(a)+t f~om theiae~titiesT(~) I foUo~ CT(U)C ~ CT(a)*C and
+ = C(T(a)*)+C= C(T(~)+)*~, T(a)+ = (CT(~)*C) where C is the operator (xu) ~ (~) of conjugation
2.2. ALGEBRAIC 2.2.5
Difficulties
CHARACTERIZATION with
Moore-Penrose
103 stability
Weconclude this chapter by a few - partially already mentioned - examples to illustrate somepeculiarities of Moore-Penroseinvertible elements of C*algebras and of Moore-Penrose stable approximation sequences. Example 2.31 A continuous function f : [0, 1] -~ C is invertible (in C[0, 1]) if and only if f(t) is invertible (in C) for every t E [0, 1]. In that sense, invertibility in C[0, 1] (and in every commutativeC*-algebra) is local property. On the other hand, all values of the function f(t) = are Moore-Penrose invertible in C, whereas the function ] fails to be MoorePenrose invertible in C[0, 1]. Thus, even in the commutativesetting, MoorePenrose invertibility is not a local property. ¯ Example 2.32 Consider the n × n diagonal matrices An := diag(0,1,1,...,1),
Bn := (1/n,l,1,...,1).
The sequence (An) is Moore-Penrose stable, whereas (Bn) fails to be so. Since both sequences belong to the same coset modulo G, we conclude that Moore-Penrosestability of a sequence (An) is not an invariant o] the coset (An) + 6. Example2.33 For r E (0, 1), let T(ar) be the Toeplitz operator with erating function at(t) = -1 -r. Obviously, all fini te sect ions PnT(a,.)Pn are invertible, and T(ar) and T(dr) are Fredholm operators. But T(ar) not invertible (the sequence (1,r, r2,...) ~ 12 lies in the kernel of T(ar)). So, Polski’s theorem implies that the sequence (ll(PnT(ar)Pn)-IPnll) is unbounded and, hence, (P,~T(ar)Pn) is not a Moore-Penrose stable sequence. On the other hand, if ao(t) := -~, t hen neither T(ao) nor PnT(ao)P,~ are invertible (the sequence(1, 0, 0,...) ~ 12 resp. the vectors (1, 0,..., Cn lie in the kernels of T(ao) resp. PnT(ao)Pa), but both T(ao) and P~T(ao)Pn are Moore-Penrose invertible with T(a~~) and PnT(a~i)Pn their Moore-Penrose inverses, respectively. Thus we have (PnT(ao)Pn)+ ~ T(ao)+ strongly, i.e. the sequence (P,~T(ao)Pn) is Moore-Penrose stable. What results is that, in every neighbourhood of the Moore-Penrose stable sequence (PnT(ao)Pn), there is a sequence of the form (P~T(a~)Pn) with r > 0 which fails to be Moore-Penrose stable. Thus, Moore-Penrose stability is not stable with respect to small perturbations. ¯ These examples indicate that, concerning Moore-Penrosestability, one cannot expect results of the same generality as for stable regularizability or usual stability. Only in Section 6.1.4 we will formulate some sufficient conditions for Moore-Penrosestability.
104
CHAPTER 2.
REGULARIZATION
Notes and references Basic facts on generalized inversion of matrices and linear operators can be found in the monographs Mitra/Rao [108] and Nashed [111] (from where we also took the motto of the chapter). For generalized invertible elements in C*-algebras and Banach algebras we refer to the papers Harte/Mbekhta [82], [83] and Roch/Silbermann[150], respectively. For the idea of regularization of ill-posed problems see H~mmerlin/Hoffmann[81] and Hofmann [87], for example. All the enclosed material on the spectral theory of selfadjoint operators on Hilbert space we took from the excellent monograph Gohberg/Goldberg/Kaashoek [65]. The idea of considering stably regularizable approximation sequences instead of Moore-Penrose stable sequences goes (as far as we know) back to the 1974 paper Moore/Nashed [109], where norm-convergent approximations of Fredholm integral equations of second kind are studied. In [163], one of the authors raised the analogous problem for the finite section method for Toeplitz operators, and he succeeded in deriving Theorem 2.24. In the forthcoming papers [147], [148] and [149], the approach of [163] has been extended to further classes of approximation methods (finite section methodand polynomial collocation for singular integral operators, for instance), and the connection between the stable regularizability of a sequence and the Moore-Penroseinvertibility of the coset of that sequence in the algebra ~/G as presented in Section 2.2.2 was established. The results of Section 2.2.4 are new.
Chapter 3
Approximation
of spectra Having discussed linear equations and least squares, we now direct our attention to the third major problem area in matrix computations, the algebraic eigenvalue problem. Gene H. Golub, Charles F. Van Loan
The main theme of this chapter is the determination of the cluster or limiting sets of the eigenvalues of the approximation operators, thus answering the question whether the spectrum of a given operator A can be determined approximately by computing the eigenvalues of certain approximations A,~ of A. Wewill see that this is in general possible if A and the A~ are selfadjoint, whereasthis idea can fail drastically in case A is a non-self-adjoint operator. Wewill not spend much time with the self-adjoint case here since this will be the subject of Chapter 7. Rather we want to examine two alternative approaches to the approximation of spectra, namely via pseudospectra and via numerical ranges. Both pseudospectra and numerical ranges can be viewed as approximants of the usual spectra, and both exhibit a muchbetter asymptotic behaviour than the latter.
3.1
Set
sequences
Westart with recalling some basic and elementary facts on set functions. As a general reference we recommendSection 28 in Hausdorff’s classical monograph [84]. 105
106
CHAPTER 3.
APPROXIMATION
OF SPECTRA
3.1.1 Limiting sets of set functions A set function is a mapping which is defined on a metric space and takes values in the set of all subsets of the complex plane C. Especially, a set sequence is a set function which is defined on the natural numbers. If (An) is an approximation sequence, then the mapping n ~+ a(An), which assigns with every n the spectrum of An, is a set sequence in this sense. Definition 3.1 (a) Let (M,~),~=I be a set sequence. The partial limiting set or limes superior lim sup Mn (resp. the uniform limiting set or limes inferior lim inf Mn) of the sequence (M,~) consists of all points m E C which are a partial limit (resp. the limit) of a sequence (ran) of points mn~ (b) Let M be a set function defined on a metric space S. The function is upper semi-continuous at so ~ S if, for every open set U C C containing M(so), there is a neighborhood V of so such that M(s) C_ U for each s Observe that the partial limiting set lim sup Mnis non-emptyif infinitely many of the M~ are non-empty and if tOnM~ is bounded, whereas the uniform limiting set can be empty even under these restrictions as the trivial example M~= {(-1) ~} shows. Proposition 3.2 Both the partial and the uniform limiting sequence are closed.
set of a set
Proof. Let us check this.for the uniform limiting set. Suppose z* belongs to clos liminfMn. Then, for every positive integer k, there are points zk ~ lim inf Mn such that Iz*-zkl < 1/k. Choose sequences (m(nk))~=l with r~t(n k) e M~and lim~-~ m(nk) = Zk, and fix numbers N1 < N2 < N3 < ... such that
I-~) - z~l < 1/k for a~l n _> g~.
Define a sequence (m~) by choosing m,~ ~ Mn arbitrarily if n < N1 and by setting m~ := m(nk) in case Nk ~ n < Nk+~. Then, for all n ~ [N~, N~+I), Iz* - m,~l <_ Iz* - zk] + Iz~ - m~)l < 2/k showing that z* belongs to lim inf Mn.
¯
The following result relates the two notions introduced in Definition 3.1. Theorem 3.3 Let S be a metric space, T be a compact subset of the complex plane, and let M be a set ]unction on S taking values in the closed subsets of T. Then M is upper semi-continuous at s ~ S if and only if limsup~_~oM(s,~) C_ M(s) for every sequence (s,~) C_ S tending
3.1.
SET SEQUENCES
107
Proof. Let M be upper semi-continuous at s E S and U be an open neighborhood of M(s) in sC. Then, for every sequence (s,~) tending to s, the sets M(s,~) are contained in U for sufficiently large n, hence, lim sup M(s,~) C_ clos U. Thus, the partial limiting set is contained in the intersection of the closures of all open neighbourhoods of M(s) in C. Because M(s) is compact, this intersection coincides with M(s) itself. Let, conversely, lim sup M(s,~) C_ M(s) for every sequence sn -~ s, but assume Mto be not upper semi-continuous. Then there is an open subset U of C which contains M(s), and there is a sequence (sn) tending to s such that M(sn) ~_ for al l n. Choose poi nts mn ~ M(s n) \ U These points lie in T, and since T is compact, the sequence (mn) possesses a convergent subsequence (m,~) with limit m. Clearly, m ~ limsupM(sn) but, on the other hand, m ¢ U which implies that m ~. M(s). This contradiction proves the reverse implication. ¯ Given a subset M of C we denote its radius sup{[m[ "m ~ M} by radM. If M is the spectrum of some operator A, then rada(A) is nothing than the spectral radius p(A). Proposition 3.4 Let (Mn) be a set sequence such that supn rad M,~ < co. Then lim sup rad Mn<_ rad (lim sup Mn) and rad (lim inf M~)_< lim inf rad Mn. Proof. For the first assertion, assume that lim sup rad Mn> rad (lim sup Mn).
(3.1)
Let ( n~)k=l be a sequence of points mn~ ~ Mn~such that [m,~ I converges to lim sup rad M,~. The boundedness condition ensures that (m,~) has convergent subsequence with limit m. Thus, m ~ limsup M,~ on the one hand, and [rn I = lim sup rad M~on the other hand, which contradicts (3.1). To prove the second assertion, given ~ > 0 choose m E lim inf Mnsuch that tad (liminf Mn) <_ [m[ + ~. Then, for every Sequence (ran) of points m,~ ~ Mn which converges to m, [m[ +~ = lim [m,~ I +~ _< liminfrad(Mn)
+~.
Letting ~ go to zero in rad (liminf M,~) _< liminfrad(Mn) + ~ yields assertion.
.
Weconclude this subsection by an alternative characterization of the partial and the uniform limiting set. For, denote by Ni the set of all infinite subsets I of the natural numberssuch that N \ I is infinite, too.
108
CHAPTER 3.
Proposition
3.5 Let (
n)n=l
APPROXIMATION
OF SPECTRA
be a set sequence. Then
lim sup M,~ = ~IkClOS (U,~_>kMn) and liminf Mn = ~31e~clos(UnelM,~). Proof. Let m E lim sup Mn. Then there are a monotonically increasing subsequence ( n~)~=1 of N as well as points m~ E t su ch th at m~--~ m as l --~ cx~. Fix k ~ N and choose n~o > k. Then, for every n~ > nt0, ml ~ (-Jn>kMn, hence, m = limmt ~ clos(U,>kM,). Since k is arbitrary, this proves the inclusion Conversely, let m ~ NkClOs (U,>kM,~). Then m E clos (U,~>kMn) every k, hence, one can find points mk ~ Un>_kMn such that [m- ink[ 1/2 k. Set rhl := ml, and choose a subsequence (rhk) of (ink) as follows: if nk is the smallest number n with (rh~) ~ M,~, then set ~hk+l := mn~+~. What results is an infinite subsequence (nk) _C N and points ~hk such that rhk -+ m, whence m ~ lim sup Mn. The proof of the second assertion is similar. ¯ 3.1.2
Coincidence set
of the
partial
and uniform
limiting
Let C~ denote the set of all non-empty and compact subsets of the complex plane. A criterion for the coincidence of the partial and uniform limiting sets of a set sequence taking values in C~ can be given in terms of the C convergence . of that sequence with respect to the Hausdorff metric on C The Hausdorff distance of two elements A and B of CC is defined as h(A, B):= max{amea~dist(a, B), r~ dist(b, where dist(a, B) = minbeBla - b]. The function h is actually a metric Cc . Wedenote limits with respect to this metric by h-lim. Proposition 3.6 Let (M~) be a set sequence taking values in c. Then lim sup Mn and liminf Mn coincide if and only if the sequence (Mn) convergent as a sequence on the metric space (Cc, h). In that case, lim sup M~= lim inf M~= h-lim Mn. Proof. Let (M,~) be a sequence which converges in C, h)to a s et M. W claim that lim sup MnC_ M C_ lim inf M=.For the first inclusion suppose that (av(~)) with an(n) ~ Mn(n) is a convergent sequence with limit a ¢ M. Then dist (an(n) , M) is greater than some positive constant for all n, which is impossible. Further, for every a ~ Mwe have by definition dist (a, Mn) -~ 0 as n tending to infinity, which shows that a actually belongs to lim inf M,~.
3.1. SET SEQUENCES
109
For the reverse implication we check that max dist
(an,
limsupMn) -~ 0 and
a~ EM,~
max dist
aElim inf
Mn
(a, Mn) -~ O. (3.2)
Then, if lim sup Mn= lim inf Mn=: Mfor some set sequence, we get max{ max dist (an, M), maxdist (a, Mn)} -} 0, an ~ Mn
a~ M
i.e.
h-lim Mn = M. Suppose the first assertion of (3.2) to be wrong. Then there are 6 > 0, a subsequence y of the natural numbers, and elements a?(n) ¯ Mn(~) such that dist (an(n), limsupMn) _> 6. The sequence (an(n)) convergent subsequence with limit a, say. By definition, a belongs to the partial limiting set, whereasdist (a, lim sup M,~)_> 6 by construction. Similarly, if the second assertion of (3.2) would be wrong, then one could find an 6 > 0, a subsequence y of the naturals, as well as a point a ¯ liminf Mnsuch that dist (a, Mr(n)) >_ 6. In this case, a cannot belong to the uniform limiting set of the Mn, which is a contradiction, too. ¯ The only substantial result of this section is the following. Theorem 3.7 Every bounded set sequence (Mn) in C possesses a subsequence (M~) such that lim sup Mn~ °. = lira inf M~ Thus, every bounded subset of Cc is relatively compact with respect to the Hausdorff metric. Proof. Without loss, suppose that UnM,~is contained in the square Q0,1 := [0, 1] x [0, 1]. Given N _> 0, subdivide [0, 1] into 2g intervals of length 2-N, which involves a subdivision of Qo,1 into 4N congruent squares. Enumerate these squares by QN,1, QN,2,...,QN,4N in any way and, given N > 0 and 1 _< k _< 4N, define Q(4~_i)/3+~ := Qg,k. What results is a sequence of squares Q~(=[0, 1] x [0, 1]), Q2, Q3,... such that diam Qn = y/-~2-N for all (4 ~ - 1)/3 < n _< (4 N+I - 1)/3 and {-J(4~v--1)/3
Q,~= [-.)l
Set Mn~ := Mnfor all n, and suppose that a subsequence (Mnk) of (Mn) is given for some k _> 1. Then construct a new subsequence (M~) k+~ (Mn) as follows: If (lim sup M~\ lim inf k) ¢~Q} ~ ~, the n choose and k) ~ Qk, and let (M~TM) be a fix an element z k ¯ (limsupM~k \ liminf M~
110
CHAPTER 3.
APPROXIMATION
OF SPECTRA
subsequence of (M~k) such that zk belongs to lira inf Mnk+l. Otherwise set k+l := M~ k for all n. Finally, for k _> 0 and all n, set M(nk) := 4~+’-1)/3 Mn M(~ n) and M~ := M(n . If (Mn(~)) is an arbitrary subsequence of (M,~), lim inf MnC_ lim inf Mn(,~) C_ lim sup Mn(n ) C_ lim sup Mn. Thus, since (M~) is a subsequence of every sequence (Mn(k)), and limiting sets are closed, one has k) C_ lim inf M~C_ lim sup M~C_ CI~ lim sup M(~ k) . (3.3) clos Uklim inf M~ Nowlet a E nk>0 limsup Mn(k). Then, for every N, a belongs to some N) r’IQN,k is not empty. Hence, square Q~v,k and, by construction, lim inf M(~ dist (a, liminf Mn(N)) <_ diam -~, Qg,k = X/’~2 which implies that a belongs to clos Uk>Olim inf M(~k). Together with (3.3), this yields the coincidence of lim sup M~and lim inf M~. ¯ Weconclude with the observation that uniform limiting sets are more uniform that their definition suggests. Proposition i}.8 Let (Mn) be a bounded sequence of subsets of the complex plane with limsupM,~ = liminfMn, and let U ~ C be an open set which contains lim inf M,~. Then M,~C_ U for all suJ:ficiently large n. Proof. Suppose there exists an open neighborhood U of lim inf M,~ as well as a sequence (n~) C_ N such that M,~ ~ZU for allk. Choose points m~ ~ istence of a partial limsupMm hence, by hand, m* ¢ U due to
Mnk \ U. The boundedness of UMnimplies the exlimit m* of the sequence (mk). By definition, m* ~ hypothesis, m* ~ liminf M,~ C_ U. On the other the choice of the sequence (m~). Contradiction.
3.2 Spectra and their
limiting
sets
Here we deal with the limiting sets of spectra of approximation operators and with their relation with the spectrum of the limit operator. Clearly, if (A,~) is an approximation methodfor an operator A, then lim inf a(A,~) lim sup a(A,~). For the other possible inclusions we consider a few examples.
3.2. SPECTRA AND THEIR LIMITING
SETS
111
Example 3.9 Weconsider approximation sequences (An) for an operator nxn we obt ain an approxiA E L(/2). With An = diag(1,1,...,1,0) mation sequence for the identity operator A = I, where {0, 1} = liminfa(An)
= limsupa(An) q~ a(A) {1},
whereas the choice diag(1,1,...,1,1) An = diag(1,1,..,1,0)
ifniseven ifnisodd
yields {1} = liminf a(An) _C limsup a(An) = {0, Example 3.10 Let
/°1° )
1 0 n×n
Then, evidently, a(An) {0} an d hence, li m sup a(An) -- liminf a(An) = {0}. On the other hand, the sequence (An) converges strongly to the shift operator
V:~2_~12,(zo, z~, :c~, ...) ~ (0, zo, z~,...), and since V is nothing but the Toeplitz operator with generating function a(t) = t, we conclude from Theorem 1.31 that the spectrum of V is the closed unit disc lI~ t~ ~. Thus, ~ U ~£ = a(V) li m sup a( An) = li m inf a(An) = {0}. ¯ Example 3.11 Let An be as in the previous example, and let Gn be the n x n matrix having 1In in its north-eastern corner and zeros at all other places. Then the eigenvalues A of An + Gn satisfy the equality An = 1In and are, hence, equal to (l/n) 1/n exp(2~rij/n) where j = 0, 1,..., n - 1. Thus, the spectra of An + Gn approach the unit circle in the sense that lim sup a(An + Gn) = lim inf a(An + G~) = q2. Example 3.12 Let K be a compact operator on/2, and let PnKPnrefer to the finite sections of K with respect to a fixed basis of 12. In this setting, it is well known(see also the following subsection) that lim sup a(I + PnKPn) = lim inf a(I + PnKPn) = a(I + K).
112
CHAPTER 3.
APPROXIMATION
OF SPECTRA
Thus, in general lira inf a(A~) can be a proper subset of lim sup a(An), and none of the inclusions a(A) C_ limsupa(An) or liminf a(An) C_ a(A) need hold. Moreover, limiting sets of spectra can change drastically already under perturbations which tend to zero in the norm (Example 3.11). the other hand, in some instances one even has continuity of the mapping a ~-+ a(a) in the sense that limsupa(A,~) = a(limAn).
3.2.1
Limiting quences
sets
of spectra
of norm convergent
se-
Weare going to examine limiting sets of spectra of approximation operators in more detail and start with the simplest case, the norm convergent approximation sequences. Theorem 3.13 Let .4 be a Banach algebra with identity function a ~-~ a(a) is upper semi-continuous. Proof. Wefirst
e. Then the set
show that limsupa(a,~)
C_ a(a) if [[an - all ~
o,
(3.4)
Indeed, let s E lim sup a(an), and let s,~ with s~ ~ a(a=~) be a sequence which converges to s. Then an~ -- Sn~e converges to a -- se in the norm of A. Assume s ~[ a(a). Then a - se were invertible, and a Neumannseries argumentwouldimply the invertibility of a,~ - s,~ e for sufficiently large k. This contradiction proves (3.4), and it remains to apply Theorem3.3 with S := {a e A : I]all _< r} and T := {z e C : Izl _< r} for some sufficiently large r to get the assertion. ¯ Observe that the inclusion in (3.4) is proper in general. A famous example by Kakutani moreover shows that there exist limpotent operators (i.e. operators with spectrum strictly larger than {0} which are the uniform limit of operators with spectrum {0}) already in the C*-algebra L(/2). For completeness we present Kakutani’s construction here, where we follow [130]. Recall for this examplethat the spectral radius of an element a of a unital Banach algebra can be computed via #(a)
li m ~,
(3.5)
which is a very remarkable formula since it connects algebraic (p(a)) and metric (lla’~ll) quantities of
3.2.
SPECTRA AND THEIR LIMITING
SETS
113
Kakutani’s limpotent operator. Let (em)~=l be an orthonormal basis of l ~ and define numbers a,~ := e-k where m = 2k(2/+ 1) and k,l _> Let A denote the weighted shift operator on/2, Aem
=
amem+l , m = 1,2,
....
The operator A is bounded on 12, and IIAII = suplaml. From Anel = al... an en+l one further concludes that IIAnll > ala2.., aN. By the definition of the am, one has ~--1
*-j-~) ala2...a2,-1
= exp(- Z j2 j--1
which implies that ~-1 (ala2...
a2,_1)
1/(2’-1)
> ((ala2...
a21_1)1/2’-’)
2 = (exp
(--
2. ~-~ j2-J)) j=l
If we set /~ := ~j=~ j2-J, then the formula (3.4) for the spectral radius yields p(A) >_ -~. This s hows in particular t hat a(A) cannot c onsist o f the zero element only. Nowdefine operators Ak for k k 0 by Ak em :=
0 if m = 2k(2/+ 1) amem+1 if m~2k(2/+l).
Then A~~+~ = 0, hence a(Ak) = {0}, and furthermore
{
e-aem+l (A - Ak) em := 0
if m=2~(2/+1) if m # 2k(2/+ 1)
which yields ]IA - Ak]l = e -~, hence A = lim Ak.
¯
There are two special instances being relevant to our purposes where equality of lim sup a(A,~) and a(lim An) can be guaranteed: Theorem 3.14 (a) Let .4 be a unital Banach algebra and (an) a sequence o] elements o~ .4 which converge to an element a ~ A with totally disconnected spectrum, or (b) let .4 be a unital C*-algebra and (an) a sequence o~ normal elements ‘4 which converge to an element a ~ ‘4. Then, in both cases, lim sup a(an) = a(a). ’Recall that a metric space X is totally disconnected if every singleton (x} C_ X is open in X and that an element a of a C*-algebra is normalif a*a = aa*. The proof of Theorem3.14(a) is based on the following lemmawhich is its owninterest.
114
CHAPTER 3.
APPROXIMATION
OF SPECTRA
Lemma3.15 Let A be a unital Banach algebra and (an) C_ A a convergent sequence with limit a E ~4. Then every open neighbourhood o] every connected componento] a(a) contains points ]rom a(an) if only n is su~ciently large. For proofs of Lemma3.15 and Theorem3.14 see [113] or [130], Chapter 1, Section 6. As an application we will derive the result cited in Example 3.12 on the convergence of the spectra of the finite sections of a Fredholmintegral equation of second kind. Lemma3.16 Let H be a Hilbert space, (Pn) be a sequence of orthogonal projections on H converging strongly to the identity operator on H, and K be a compact operator on H. Then lim sup a(I + PnKPn)-- lim inf a(I PnKPn) = a(I + K). Proof. The inclusion lim sup a(I + PnKPn)C_ a(I + is a c onsequence of Theorem 3.3 because I1(I + PngPn) - (I ÷ I --~ 0 asn -+ c~. T he reverse inclusion follows from Lemma3.15 since the spectrum of a compact operator consists of at most countably manypoints the only possible cluster point of which is 0 E C. The equality lim sup a(I ÷ PnKPn)li m inf(I ÷ PnKPn)will be established in a more general context in Section 3.2.3. ¯ 3.2.2
Limiting
sets
of spectra:
the
general
case
Our next goal is the asymptotic behaviour of the spectra a(An) for arbitrary bounded sequences (An) of operators, or, slightly more general, elements of certain C*-algebras. That is, we let (Cn) be again a family C*-algebras with identities en and let ~ resp. G refer to their product resp. their restricted product. Let (an) ~ ~-. It turns out that the partial limiting set limsupa(an) related to a new stability notion which might be called ’spectral’ stability (in contrast to the conventional ’normal’ stability introduced in Section 1.1.1). A sequence (an) spectrally sta ble if its entr ies an a re invertible for all sufficiently large n and if the spectral radii p(a~1) of their inverses are uniformly bounded (whereas conventional stability requires uniform boundedness of the norms Ila~lll). Clearly, every conventionally stable sequence is also spectrally stable. Theorem 3.17 Let (an) ~ J~. Then s E C~ belongs to the partial limiting set limsupa(an) if and only if the sequence (an - Sen) is not spectrally stable.
3.2.
SPECTRA AND THEIR LIMITING
SETS
115
Proof. Let (an - sen) be a spectrally stable sequence, i.e. sup p((an - sen) -1) =: m < oc for a certain no. Then, for all n _> no, sup
It[
= sup It[ -1 -1, ----tEa(an--se,~)
( inf [tD tEa(an
--sen)
whence l/m<
inf Itl= ist(s - I--d t~(~n)-s
inf
It-s
Hence, s cannot belong to lim sup a(an). For the reverse direction suppose (an - sen) is a sequence which fails to be spectrally stable. Then either there is an infinite subsequence (an~ sen~ ) whichconsists of non-invertible elements only, or all elements an - Sen with sufficiently large n are invertible, but p((an~ - sen~)-1) -~ oo as k -~ o~ for some subsequence. In the first case one has s ¯ a(an~) for every k and, thus, s ¯ limsupa(an). In the second case one can find numbers tn~ ¯ a(an~) such that Itn~ - s1-1 --~ oo resp. Itn~ - s I -~ 0 as k -+ oc which also implies that s ¯ lim sup a(an). Thus, the determination of the partial limiting set lim sup a(an) requires to investigate the spectral stability of the sequences (an - sen). This problem proves to be muchmore involved than the investigation of normal stability. Even in the (seemingly well understood) case of the finite section method for Toeplitz operators with continuous generating function one is able to determine lim sup a(PnT(a)Pn) only in case a is a polynomial. There is a result by Schmidtand Spitzer ([156] or [27]) whichsays that, in this special situation, lim sup a(PnT(a)Pn)is the union of so-called analytic arcs which mimics - as a skeleton - the shape of a(T(a)). Sometypical pictures are shownin Figure 3.1 where -- resp .... mark the ’boundary’ a(T) of a(T(a)) resp. the partial limiting set lim sup a(PnT(a)Pn). These difficulties disappear if we restrict our attention to sequences for which conventional and spectral stability coincide. Corollary 3.18 If (an) ¯ i7: is a sequence of normal elements, then lim sup a(an) = a~/g((an) Proof. The spectral radius and the norm of a normal element of a C*algebra coincide. Hence, the sequence (an -- sen) is spectrally stable if and only if it is conventionally stable which, by Theorem3.17 and Kozak’s
116
CHAPTER 3.
APPROXIMATION
OF SPECTRA
Figure.3.1: Limiting sets of eigenvalues of Toeplitz matrices theorem, implies that s E limsupa(a~) if and only if s ~ ay/g((a,~) + Weconjecture that this assertion remains valid if the sequence (a,~) is only supposed to be essentially normal in the sense that Ilana~ - a~anll --~ 0 as n -~ oo. In case the an are n × n matrices (i.e. when C = C~×~), then Lin’s theorem tells us that the sequence (an) is essentially normal if and only if a~ = b,~ + g,~ where the b,~ are normal matrices and IIg,~ll -+ 0 as n -~ oo (see [104], Chapter 19). Even in this case the conjecture is open. Let us return once more to the context of in general non-normal sequences. Examples 3.10 and 3.11 indicate that, for every sequence (an) 9v, the partial limiting set limsupa(an) is a subset of a~/g((an) + 6) that one might get different parts of the latter spectrum if one considers the limiting sets of perturbed sequences (an + g,~) with (g,~) ~ 6 as well. The following result showsthat one will indeed obtain all of a:~/g ((an) + if one takes into account all perturbations of (an) by a zero sequence, least in case the a,~ are n by n matrices. Theorem 3.19 Let C,~ = C, n×n and (An) ~ J~. Then U(a,)cg limsup a(A~ + G,~) a~:/g((A,~) + Proof. For the inclusion _C, let A ¢( a:~/g ((A,~)+ 6). Then (An- AIn) (with In referring to the identity matrix) is a conventionally stable sequence,
3.2.
SPECTRA AND THEIR LIMITING
SETS
117
hence, all sequences (An + Gn - Mn) with (G,~) E 6 are conventionally stable, too. But every conventionally stable sequence is spectrally stable, whence, by Theorem 3.17, Thus, ‘k does not belong to the left hand side of the asserted equality. For the reverse inclusion, let ‘k E a:~/g((An) + 6), i.e. suppose the sequence (An - ‘kin) fails to be conventionally stable. Then, either there an infinite subsequence (nk) of the naturals such that none of the matrices An~- ‘kln~ is invertible, in which case (An - ,kin) is not spectrally stable by definition and, hence, ‘k belongs to the partial limiting set lim sup a(An) due to Theorem3.17, or the matrices An - ,kin are invertible for all sufficiently large n, but limsup In the latter case there is a subsequence (n~) of N as well as vectors xn~ E Cn~ with IIx,~ll = 1 such that for k =- l, 2, ... . Set Yn~:= (An~ -‘kIn~)--lXn~ (which is clearly non-zero), and define linear mappings G~ :(~ -+Cn~, 2. Z~--~(z, yn~)Xn~/llyn~[[ Then,
llan~ll =sup[I II~,~II
(An~- an~- ‘k-~,~)y,,~ = (An~ - ‘kIn~)yn~ - an~Y,~ = ~,~- ~n~ This shows that the sequence (An - Gn - Mn)is not spectrally stable and, consequently, ‘k belongs to limsupa(A, - G,~) for that special (Gn). Applied to the finite section method for Toeplitz operators, this theorem in combination with Corollary 1.36 says that t~(a,~)~g limsupa(P,~(T(a) + g)Pn + Gn) = a(T(a) for every continuous function a and every compact operator K. 3.2.3
The case
of fractal
sequences
The following result provides a condition for the equality of partial and uniform limiting set of spectra. Recall in this connection that, due to Theorem3.7, every sequence in ~" possesses a subsequence for which the partial and the uniform limiting set of the spectra coincide.
118
CHAPTER 3.
APPROXIMATION
OF SPECTRA
Theorem3.20 Let J~ be as in the previous section, and let .A be a fractal C*-subalgebraof ~: which contains the identity. (a) A sequence (an) E Mis conventionally stable i] and only i] it possesses a conventionally stable (infinite) subsequence. (b) If (a,~) ~ ,4 is normal, then lim sup a(an) = lim inf a(an). (c) If (an) ~ M is normal, then the limit lira p(an) exists and is equal
+ 6). Proof. (a) Let the notations be as in Section 1.6.1. Suppose~ is a strongly monotonically increasing sequence such that the sequence (an(N)) = Rn(a~ ) is stable. Clearly, ~/can be chosenin such a waythat all an(,~) are invertible. Then, by the inverse closedness of An in 9vn, there is a sequence (b,~) ~ such that R~(a,~) . R~(bn) = R~(bn) " Rn(an) =
(3.6)
The canonical homomorphism r : A -> A/ ( A [q 6) is fractal by hypothesis, i.e. ~r = ~rnRv with a certain homomorphism r n. Applying rn to (3.6) one gets the invertibility of n(an) = (an) + A in A/(A ~ g), whencethe stability of (an) follows. (b) Assume, there is a t ~ limsupa(a,~) \ liminfa(an). Then one can a 5 > 0 as well as a strongly monotonically increasing sequence ~ such that dist (t, a(an(~))) >_ 5 for all n. The normality of the an(,~ ) guarantees that (an(, 0 - ten(,~)) is a conventionally stable sequence (with the norms of the inverses being bounded above by 1/5). Then, by part (a), the quence (a,~ - ten) itself is conventionally stable. Hence, t f[ a((an) + 6) limsup a(a~) by Corollary 3.18 which is a contradiction. Assertion (c) is an immediate consequence of part (b) and Proposition ¯
As an application, consider once more the finite section methodfor Toeplitz operators, i.e. specify ~- and 6 appropriately and choose .A -- $(C), which is a fractal algebra by Corollary 1.70. Theorem 3.21 Let (An) ~ $(C) be a normal sequence. liminfa(An) = limsupa(A,~) = a(W(A,~)) t~ a(I;V(A,~)) and lira p(A,~) = max{p(W(A,~)), p(l~d(A~))}. The proof follows immediately from the previous theorem and Corollary 1.58. If, in particular, a E C is real-valued and K ~ K(/2) is self-adjoint then, by Corollary 1.36, liminf
a(Pn(T(a) + K)P~) = limsupa(Pn(T(a)
+ K)Pn) =
3.3. PSEUDOSPECTRA AND THEIR LIMITING
SETS
119
3.2.4 Limiting sets of singular values Let B be a unital C*-algebra and a E B. The set a2(a) of the singular values of a is defined as {A E If{ + : A2 E a(a*a)}. Since the determination of the singular values is equivalent to the determination of the spectrum of a self-adjoint element, the results of the preceding section have the following evident analogues for the singular value sets of arbitrary bounded sequences. The notations are as in Section 3.2.3. Theorem3.22 /~ (an) ~ ~’, then limsupa2(an) = a2((an) Theorem3.23 If A is a fractal C*-subalgebra of ~: containing the identity, and if (an) e .4, then lim sup a2(an) = lim inf a2(a,~), and the sequence (rad a2(an)) converges to rad ((an) + Theorem3.24 /~f (An) e $(C), lim inf a2 (An) = lim sup a2 (An) = (W(An)) t9 a~ (If V(An)) and limrad a2(An) = max {tad a2(W(An)), rad a2(l~(An))}.
3.3 Pseudospectra
and their
limiting
sets
In contrast to commonspectra, the s-pseudospectra which we are going to introduce now are distinguished by a much nicer asymptotic behavior, which allows to approximate the ~-pseudospectrum of an operator A by ~-pseudospectra of approximation operators An also in cases where A is non-normal. 3.3.1
e-invertibility
A computer working with finite accuracy cannot distinguish between a noninvertible matrix and an invertible matrix the inverse of which has a very large norm. This suggests the following definition reflecting finite accuracy. Definition 3.25 Let I3 be a Banach algebra with identity e and let e be a positive constant. An element a ~ 13 is e-invertible if it is invertible and if Ila-lll < lie. The e-pseudospectruma(~)(a) o] a consists of all )~ ~ which a - he is not e-invertible. The usual invertibility and the usual spectrum follow from their e- counterparts by letting e formally go to zero. To be more precise: an element
120
CHAPTER 3.
APPROXIMATION OF SPECTRA
a E B is invertible if and only if it is ¢-invertible for all sufficiently small ¢, (e) (a). and a(a) = V~>0a In analogy to the usual invertibility, one can showthat the ¢-invertible elements of a Banach algebra form an open set, and that ¢-pseudospectra are compact and non-empty subsets of the complex plane. As the following theorem shows, the upper semi-continuity of spectra also has its analogue for pseudospectra. Theorem 3.26 Let 13 be a unital Banach algebra and ¢ > O. (a) If (an) C_ B is a norm-convergent sequence, then limsupa (~)(an) C_ a(~) (lim an). (b) The mapping13 ~ a ~-~ (~) (a) C_ Cis upper semi-continuous. Proof. (a) Set a := liman. Given h ii msupa(~)(an), choose a sequence (nk) as well as numbers hn~ ~ a(e)(an~) such that hn~ ~ h as k -~ oo. Thus [l(a,,~ - hn~e)- (a - he)l[ -~ 0 as k -~ ~, (3.7) where e denotes the identity element of B. If there are infinitely manyof the an~ - h~ e which are not invertible then a - he cannot be invertible (the set of the invertible elements is open), thus h a(a) C a(~) (a So suppose that there are only finitely many of the an~ - hn~ e which are not invertible. Then (a,~ - ~n~e)-1 exists for all sufficiently large k, and [](a~- ~,~e)-~ll >_ 1/~. (3.8) If nowa - he is invertible, then (3.7) and the continuity of the inversion imply -~-(a-he)-~ll-~0 II(a~-h,~e) as k--~o~ which in conjunction with (3.8) and the continuity of the norm shows that II(a-)~e)-~ll 1/~, i.e . tha t h b elongs to a(~)(a). If a-his not i nvertible, then evidently h is also in a(~) (a). Assertion (b) follows via Theorem ¯ Nowwe move from general Banach to C*-algebras. In this setting, the following equivalent description of pseudospectra.
we have
Theorem 3.27 Let B be a unital C*-algebra and ~ > O. Then, ]or every a ~ B, the ~-pseudospectrum o] a is equal to a(~) (a) = [.Jpel3,
Ilpll~_¢
a(a+p).
(3.9)
Proof. Abbreviate a(~)(a) to S~. and t~peB, Ilpll<_~ a(a +p) to $2. Our first claim is the inclusion S~ C_ $1.
3.3. PSEUDOSPECTRA AND THEIR LIMITING
SETS
121
Given t E $2, there is a p in B with IlPll -~ z such that a +p - te is not invertible. If t lies in a(a), then it also belongs to $1, and we are done. So suppose t ~ a(a). Then a - te is invertible, and the identity
a + p - te = (a - te)(~ + (a - t~)-lp) yields that e + (a - te)-lp cannot be invertible. Hence, I[(a - te)-lp[I >_ (otherwise invertibility would follow via Neumann’sseries). Because 1 _< [[(a-te)-~p[I <_ [[(a-te)-~[[ ¯ [[p[[, one has II(a-te)-~ll
_> 1/llpll
>
i.e. t E s~ in this case, too. For the reverse inclusion $1 C_ $2 assume there is a t E $1 such that a + p - te is invertible for all p E B with Ilpll _<e. Choosingp = 0 we get the invertibility of a-te -~ and, hence, of a*-~e and, choosing p = 1(a*-~e) with a certain complex number,~ which satisfies
o < I~l _<elll(a*-~e)-~ll, we obtain the invertibility
(3.10)
of
a- te + A(a* - ~e)-~ = A(a- te)(~e + (a- te)-~(a * - -1) ~e) (observe that Ilpll < e in both cases). Hence, ½e + (a - te)-l(a * -~e) -~ is invertible for all A satisfying (3.10). This gives p((a - te)-~(a * - ~e)-1) < I](a* -
~e)-lll/e,
whence, by the self-adjointness of (a- te) -~ (a* -~e) -~ (implying the coincidence of spectral radius and norm),
II(a - te)-~ll2 = II(a -
te)-~(a * -
ie)-~ll < II(a*- ~e)-~ll/e.
-~ II, whichyieldsII(a-te)-lll < 1/e Finallyone has II(a-te)-~ll= II(a*-~e) in contrast to t ~ S~. This contradiction verifies the inclusion S~ Observe that $2 _C $1 in the Banach algebra case, too, whereas the reverse inclusion fails for Banachalgebras in general. Theorem 3.27 also offers a-way for the numerical computation of pseudospectra in case B = C~x’~ by randomly choosing n x n matrices p ~xn with. IlPll -< e and then plotting the eigenvalues of a + p for a ~ C
122
CHAPTER 3.
APPROXIMATION
OF SPECTRA
Observe furthermore that if B is a unital Banach algebra and A a closed subalgebra of B which contains the identity and which is inverse closed with respect to commoninvertibility, then it is also inverse closed with respect to e-invertibitity, and a(~)(a)=a(~)(a)
for every
In particular, this equality holds if B is a unital C*-algebra and ,4 a C*subalgebra of B which contains the identity element. The remaining part of this subsection is devoted to a further characterization of e-invertibility of linear boundedoperators A on a Hilbert space H. Banach’s theorem on the inverse operator says that A is invertible if and only if Ker A = {0} and Im A = H. In what follows we are going to introduce the e-kernel KereA as well as the e-range ImeA of A E L(H) which share many of their properties with the commonkernel and range of A. Especially we will prove an e-version of Banach’s theorem: A is einvertible if and only if KereA = {0} and Im~A= H. These considerations will not be needed in the sequel and can be ignored without loss. Westart with defining the e-kernel and the e-range for self-adjoint nonnegative operators. As already remarked, an operator A _> 0 is invertible if and only if re(A) := inf{A : ,~ E a(A)} > 0, and in this case IIA-111 re(A) -~. Thus, A _> 0 is e-invertible if and only if m(A) > e. This suggests the following definition: The e-kernel KereA of A is the (-oo, el-spectral subspace of A. Thus, the orthogonal projection from H onto KereA is nothing but the spectral projection E(e) where {E(t)}teR is the partition of identity associated with A (compare Section 2.1.2). By Theorem2.7, (3.11)
Ker~A= clos Im fte (9 Ker (A - eI). : In order to motivate the definition of the e-range of A, recall that (KerA) ± = clos for every self-adjoint
Im A and (ImA) ± = KerA
(3.12)
operator A ~ L(H), and that
(M+N) ± = M±NN± and
(M~IN) ± = clos(M
±+N±)
(3.13)
for arbitrary closed subspaces M, N of H. Thus, taking the orthogonal complement of the decomposition (3.11) yields ± (Ker~A)
= = =
(clos Im f~e ¯ Ker(A- ± eI)) (clos Im f~E)±.r3 (Ker (A- el)) ± (by (3.13)) Kerf~e r3 clos Im (A-el) (by (3.12))
3.3.
PSEUDOSPECTRA AND THEIR LIMITING
SETS
123
whichjustifies to call Im~A:= Ker fl~ N Im (A- eI) the e-range of A. Observe that Im~Ais not necessarily a closed subspace of H. Proposition 3.28 Let H be a Hilbert space, A E L(H), A >_ O, and e > Then the ]ollowing analogues o] (3.12) hold: (Ker~A) ± = closIm~A
and (Im~A) ± = KereA.
Proof. For every linear (not necessarily (M±)± -- clos M. Hence,
closed) subspace of H one has
clos Im~A---- clos (Ker ~ N Im (A - el)) = ((Ker ~ (A- e I)) ±, which is equal to (clos ((Ker fl~)±÷(Im (A-eI))±) ± by (3.13) and coincides with (clos (clos Im fl~ + Ker (A - el))) ± (3.14) by (3.12). Since the subspaces clos Im f~ and Ker (A - el) are orthogonal to each other by (3.11), their sum is closed, and hence, (3.14) is equal (closIm f~ @Ker (A - el)) ± ±. = (Ker~ A) The second assertion is a simple consequence of the first one.
¯
For introducing the e-kernel and the e-range of an arbitrary operator A E L(H), let A = URstand for the polar decomposition of A (compare Theorem 2.10). Then one has KerA -- KerR and Im A -- UIm R for the commonkernels and ranges (for the first equality observe that if Ax = 0 then Rx = 0 because 0 = (Ax, Ax) = (RU*URx, x) = (R2x, x) = (Rx, and so the following definition makessense. Definition 3.29 Let H be a Hilbert space, A ~ L(H), and e > O. Then the e-kernel Ker~Aand the e-range Im~Ao] A are defined by KereA = KereR and ImeA = UImeR, where A = UR is the polar decomposition o] A and Ker~R and ImeR are defined as above.
124
CHAPTER 3.
APPROXIMATION OF SPECTRA
Theorem 3.30 Let H be Hilbert space, A E L(H), and ~ > O. Then A ~-invertible i] and only if Ker~A = {0} and ImeA = H. Proof. Weprove that the following assertions are equivalent: (i) KereA ----- {0} and ImeA= (ii) Ker~R = (0}, ImeR = H, and U is unitary. (iii) is ¢-invertible, and U isunita ry. (iv) is ¢-invertible. Westart with the equivalence (i) ¢~ (ii). If KereA = {0} and Im~A= H then, by definition, KereR = {0} and UImeR = H. Since Ker~R is the (-cx),¢]-spectral subspace of R and ¢ > 0, we have Ker R C_ Ker~R and, hence, Kerr = {0}. Since R is self-adjoint, this implies by (3.12) that clos Im R = H, and since R and U are specified in such a way that clos Im R = (Ker U)± (see Theorem 2.10), we conclude that KerU = {0}. Moreover, as we have already seen, Im U = H, hence, U is unitary. This finally yields ImeR=U*ImeA= H. The reverse implication (ii) :¢ (i) is evident. For the implication (ii) ~ (iii), suppose R to be a self-adjoint and nonnegative operator with Ker~R = {0} and Im~R = H. The kernel condition implies via the Spectral Theorem 2.7 that ((R- el)x, x) >_ for ev ery x E (Ker~R)± = H, whence (Rx, x) >_ ¢ Ilxll 2 and thus IIRxll
_>ellxll
for every x e H.
(3.15)
By Lemma1.21, this gives that Kerr = {0} and ImR is closed, which, due to the self-adjointness of R and by (3.12), involves the invertibility of R. Setting x = R-ly in (3.15) we obtain [lYll > ¢[IR-lYll resp. IIR-lyll <_ (1/¢)llyll for all y ~ H, i.e. IIR-111 _< 1/¢. It remains show that I]R-111 cannot be equal to 1/¢. Assumethe contrary, that is, IIR-111 = 1/¢. Because R-1 is non-negative, one then has p(R-1) = 1/e and 1/~ ~ a(R-~), hence, R -¢I cannot be invertible. On the other hand, the hypotheses Ker~R = clos Im f~e @Ker (R- el) = {0}, Im~R = Kerf~ fq Im (R- el)
=
imply Ker (R - ¢I) = {0} and Im (R - eI) = H, i.e. the invertibility of R - ¢I. This contradiction shows that IIR-111 < 1/~, i.e. that R is ¢-invertible. Let, conversely, R be a non-negative ¢-invertible operator. Then, as we have already remarked, ¢ < re(R) := min{,k : ,k ~ a(R)}, which immediately implies that the (-cx~, el-spectral subspace of R (i.e. Ker~R)consists
3.3.
PSEUDOSPECTRA AND THEIR LIMITING
SETS
125
of the zero element only. By Theorem 2.7 we then have Ker~R = clos Im f~ @ Ker (R-~I)
= {0},
which shows that f~ is the zero operator. Consequently, Im~R= Ker ~ t3 Im (R - ~I) = H C~ Im (R - ~I), and Im (R- ¢I) = H because ~ m(R). Hence, R- ¢I is inv ertible. Thu s, (ii) and (iii) are equivalent. Finally, we have to check whether (iii) ¢* (iv). Observe that if A is invertible and A = URis the polar decomposition of A, then U is unitary and R is invertible, and conversely. Further, for invertible A one has [[A-I[[ 2 = [[(A-1)*A-I[[ = [[UR-1R-1U*[[= 2, [[R-2[[ = I[R-I[[ thus, A and R are ¢-invertible only simultaneously. 3.3.2
Limiting
sets
¯
of pseudospectra
Let again (Cn) be a family of unital C*-algebras with product ~ and restricted product G. The main result of this section identifies the limes superior of the ~-pseudospectra of the elements of a sequence (an) E with the ~-pseudospectrum of the coset (an) + in ~/~. Theorem 3.31 Let (an) E ~ and ~ > O. Then lim sup a~) (an)
=
+
Recall that in case ¢ -- 0, i.e. for common spectra, this result does not hold in general. The proof of Theorem3.31 is based on the following result. Theorem3.32 (Daniluk) Let 13 be a C*-algebra with identity e, let a ~ B, and suppose a - Ae to be invertible for all A in some open subset U of the complex plane. /f [[(a- Ae)-ll] <_ C for all A e U, then [[(a - Ae)-ll[ < for all A ~ U. In other words: the analytic function U --~ B, A ~ (a - Ae)-1 satisfies the maximum principle. This is a surprising result since - in contrast to complex-valued analytic functions - the maximumprinciple for operatorvalued analytic functions does not hold in general as the simple example
°1)
126
CHAPTER 3.
APPROXIMATION
OF SPECTRA
reveals. For a proof of Theorem3.32 in a more general context see Section 3.3.4. Proof of Theorem 3.31. Let ~ E a(~g((an) -t- Theneithe r (an hen) ÷ G is not invertible, or the inverse of this coset exists, but II((an
~e~)+ 6)-1II > 1/~. In the first case, the sequence (an - £en) fails to be stable, and follows easily the existence of an infinite subsequence (nk) of N such that ~ ~ a(~)(an~) for every k. In particular, ~ e limsupa(e)(an) in this case. In the second case, we infer from Daniluk’s theorem that, in every open neighbourhoodU of A, there is a ~0 such that II((an Aoen) + ~)-1 II > 1/~ (Otherwise we would have II((an-~oen)+6)-lll <_ 1/~ for all ~0 e U involves via Theorem3.32 that II((an- Aoen)÷6)-111 < 1/~ for all ~o ~ U including ~0 = A.) Thus, for all sufficiently large k, there are numbersAk with £k --~ ~ as k -~ ~ such that
II((a~Ak e~) +G)-~I[ > 1/(e -
l/ k).
By Proposition 1.16, this is equivalent to the inequality lim sup II(an- )~ken)-~ll >_1/(e- Ilk) (the invertibility of an- )~ken for all sufficiently large n being a consequence of a Neumannseries argument). Since 1/e < 1/(e- l/k), there are numbers nk tending to infinity as k -+ cx~ such that II(a~ - ~ken~)-lll _> 1/~ for all in other words, )~k ~ (~) (an~) for every sufficiently l arge k, which i mplies that ,k = lim ,~ E lim sup a(~) (a~). For the reverse inclusion, let A ~ limsupa(e)(a,~), but assume in the contrary that ,~ ¢ e2/~((an) -(~ + ~). Thus, (a,~ - Ae~) + G is invertible ~r/6 and II((an - )~en) 6)- 11= 1/e- 25< 1/e with s ome 5> 0. By Polski’s theorem, the an - ;~en are invertible for sufficiently large n, and by Proposition 1.16 again, lim sup [[(an - Aen)-ll[ = 1/¢ whenceII(an - Aen)-~[I < 1/e - 5 for n sufficiently large, say n _> no. If n > no and [A - #1 < e~(1/e - 5)-1 then one gets, using Neumann’sseries again, II(a~ -,e~)-lll
< -
a~II( 1 - I,~ -/t[ [[(an -- &en)-lll
3.3.
PSEUDOSPECTRA AND THEIR LIMITING
SETS
127
1 - e5(1/e - 6) -1 (1/e - 6) and hence ~ ¢ aCe) (an) for all/~ belonging to a certain open neighbourhood of A and for all sufficiently large n. But then A cannot belong to the partial limiting set of the e-pseudospectra a(¢) (an), which is a contradiction. For a more general result, see Section 3.3.4. 3.3.3
The case
of fractal
sequences
In presence of a fractal sequence (an), one will expect equality between the partial and the uniform limiting sets of the pseudospectra of the an and, indeed, this equality is true as we will see now. Weagree upon calling a sequence (a,~) E c ~-stable i f t he coset ( an) +G is ~-invertible in .~/ Theorem 3.33 Let A be a fractal C*-subalgebra of yr which contains the identity of J:, and let ~ > O. (a) A sequence (an) ~ ‘4 is e-stable if and only if it possesses an e-stable subsequence. (b) If (an) ~ ‘4, then limsupa(e)(an) liminf a(e )(an). (c) If (an) ~ .4, then limrada(e)(an) exists and is equal to rada(e)((an) Proof. (a) Let the notations be as in Section 1.6.1. Suppose~/is a strongly monotonically increasing sequence such that (an(n)) = Rn(an) is an ~-stable subsequence of (an). Then the sequence (an) is stable by Theorem3.20(a), and Theorem 1.71 implies that 1/~ >
II((an(n )) + G)-lll/a = II((an)
i.e. (an) is ~-stable. (b) Assumea numbert belongs to lim sup (~) (an) \ li ra in f a( ~) (a n). Th there is a subsequence~/of N such that t ¢ lim sup a(~) (an(,~)). By Theorem 3.31, the sequence (an(n) te n(n)) is ~-stable, whence by assertion (a) the e-stability of the complete sequence (a~ - ten) follows. Again by Theorem 3.31 , this implies t ¢ lira sup a(~) (an), which contradicts the assumption. Assertion (c) is an immediate consequence of part (b) and Proposition As an application, we consider once more the finite section method for Toeplitz operators, i.e. we specify 2- and G accordingly and let .4 = S(C), which is a fractal algebra by Corollary 1.70.
128
CHAPTER 3.
APPROXIMATION
OF SPECTRA
Theorem 3.34 Let (An) e S(C) and ~ > O. lira sup a(~) (An) li m inf a (~) (An) -- (~)(W(An )) (~ a (~) (IYV(An)) and lim tad a(~) (An) = max{tad (~) (W(A,~)), t(~) (I2V (An)) In particular, i] a E C, then limsupa(~)(PnT(a)Pn) and
= liminfa(~)(PnT(a)Pn)
lim rad a (~) (PnT(a)Pn) = rad a (~) (T(a)). Proof. The first assertion is a consequence of Theorem3.33 and Corollary 1.58, and the second assertion follows from identity (1.32) which implies that IIT(5- A)-lll = I]T(a- .~)-11[ for all A e C \ a(T(a)). Beautiful plots of pseudospectra of several operators (including Toeplitz operators) as well as of limiting sets of pseudospectra can be seen in [129], [172], [171] and in [27], Chapter 3. In the proof of the previous theorem, we employed the obvious fact that, for every ordered pair (A, B) viewed of as an element of the algebra L(l 2) x L(12), one has a(~)(A, B) = a(~)(A)t~a(~)(B). An analogous result is valid for finitely manyoperators. As a corollary of Theorem5.39 below we will derive a generalization to the case of infinitely manyoperators. 3.3.4
Pseudospectra
of
operator
polynomials
Weare now going to extend the results of the previous subsections to the case of operator polynomials. Let B be a C*-algebra with identity e, and let b0, bl .... ,bm elements of B. Then, for every complex number )~, the expression L(A) = bo + b~A +... + bmAm is well-defined, and L is (not quite correctly) called an operator polynomial with coefficients in B. The spectrum of L is the set a(L) of all A ~ C for which L(A) is not invertible; similarly, for ~ > 0, the ~-pseudospectrumof L is the set a(~) (L) of all ~ ~ C such that either L(A) is not invertible II(L(A))-lll >_ 1/~. Evidently, if L()~) -- b - )~e, then the spectrum ~-pseudospectrum of the polynomial L coincide with the commonspectrum and ~-pseudospectrum of the element b ~ B, respectively. The following theorem is the analogue of Theorem3.27, and it can be proved in the very same way. So, we omit the proof.
3.3. PSEUDOSPECTRA AND THEIR LIMITING
SETS
129
Theorem 3.35 Let B be a unital C*-algebra and ~ > O. Then, for every operator polynomial L with coe~cients in B, a(e) (L) = t3peB a(L+p). ’ i1~11_<~, Clearly, L+p refers to the polynomial (L+p)( A) = (bo+p)+blA+. . TM. Let now C1, C2,... be a family of unital C*-algebras. Denote by ~ and G their product and their resticted product, respectively, and let (a~)), (a~l)), ..., (a~m)) be sequences in ~. Wesuppose that m > 0 and that the sequence (a~m)) is stable. For every n, consider the polynomial with coefficients in Cn given by TM .a~’)A + ... Ln(A) := a~°) + + a~)~
(3.16)
As for the commonspectra, we would like to identify the limiting set of the pseudospectra of the polynomials L~ with the pseudospectrum of something in the quotient algebra ~/G. It turns out that this is indeed possible, and that the something is the polynomial n(x) := ((a~)) + G) ’) ) + G)X +... + ((a~ m)) + G)$m (3. 17). with coefficients in ~/~. Theorem3.36 Let m > O, let (a~)), (a~)), ..., ~)) be sequences in ~ with (a~m)) being stable, and let L~ and L be the polynomials (3.16) and (3.17). Then, ]or eve~ e > lim supa(~)~ rc. ,~=a~}g(L)" For the proof, we need a generalization we will present and prove now.
of Daniluk’s Theorem3.32, which
Theorem 3.37 Let B be a C*-algebra with identity e, let m > O, and let L be the polynomial L(A) = bo + b~A + ... + bm~m wi¢h coe~cients in B. Let the coe~cient bm be invertible. Assume there is an open subset U of the complex plane such that L(A) is inve~ible and ~](L(A))-~]] ~ M ]or all ~ ~ U. Then ]](L(A))-’]] < M ]or all ~ e U. Proo£ Wesubdivide the proof into several steps; the third one being identical with Daniluk’s original proof of Theorem3.32. Step 1. Suppose there exists a A0 ~ U such that L(A0) = M. For the shifted polynomial ~, Q(~)
:= L(~+~o)
= a0 +a~+...+a~
130
CHAPTER 3.
APPROXIMATION
OF SPECTRA
one easily checks that Q(A)is invertible, H(Q(A))-ill -~ Mfor all A E U-A0 (= the algebraic difference), and that II(Q(0))-IH = M. Moreover, a,~ = b,~ and a0 = Q(0) are invertible. Further, let (~ refer to the monic polynomial defined by Q(A) O,(A)am. Clearly, (~ (A) is inv ertible if only if so is Q(A). Step 2. Here we recall some facts concerning a special representation called linearization of the inverse of a monic operator polynomial. For details see [152], Chapter 2, Theorem2.5.2. For the desired representation, we introduce the following vectors of length m and matrices of order m x m with entries in the algebra B: Xo := (e
Y :=
0 0 ...
0),
, T :=
I := diag (e e e ...
e),
0 0
0 0
e 0
-.. -..
--a a~n1 --ala~n 1 --a2a~n ~ ....
,
1am_la~n
i.e. T is the companionmatrix of the monic polynomial (~. Then, for all which are not in the spectrum of 8, ~)(~)-1 = Xo(~I - T)-IY. Since Q(A)-1 = a~(A)-1, this yields the representation Q(A)-~ = X(AI - T)-IY
(3.18)
with X = a~nlXo = (a~n 1 0 0 "- 0), which holds for all A such that Q(A)is invertible. Step 3. Beginning with this step, we think of B as an algebra of linear bounded operators acting on some Hilbert space H, which is possible due to the GNSconstruction (Theorem 1.48 (a)). Thus, T is actually an operator acting on the orthogonal sum of m copies of H. Since Q(0) is invertible, the operator T is invertible; hence, for all A the disk [AI _< r with sufficiently small radius r, (T
- AI) -1
: E "~JT-J-I’ j=o
whence X(T - AI)-~Y
= E AJXT-J-~Y" j=O
3.3.
PSEUDOSPECTRA AND THEIR LIMITING
131
SETS
Thus, for all f E H and IAI _< r,
IIQ(A)-~fll~ = IIX(T-AI)-~Y fll ~ = ~ AJ~k (XT-J-~Y f, XT-k-~y f). j,k>_o Integrating this identity with respect to ,k against the circle IAI = r yields
1 fl~ IIQ(A)-~fllzldAI = ~-~rU~IIXT-~-xYflIU. 27rr i= r
j>o
Because IIQ(~)-lfll~ MllYllby hypothesis, this yields for all j _> 1 the estimate
IIXT-IYfll ~ ÷ r2~llST-J-~Yfll2 <_~ r2~IIXT-~-~Y flI~ <_~. M211fll j>o Let e > 0. Since, by assumption, IIQ(0)-~II II XT-~YII = M,there is fe in H with norm 1 such that
(3.19) an
ilXT-~Yf~ll~ > Me _ ¢2, which together with estimate (3.19) shows that M2 _ ~2 +
r~llXT-~-~yf~llZ < 2M
or, equivalently, IIXT-J-~Yf~II
< er -~ for all
j > 1.
Step 4. For brevity, set cj = -aia~n~. The operator Co is invertible, and it is easy to check that the inverse of the companionmatrix T is a companion matrix again:
i
0 e
... ...
0 0
0 0
0
...
e
0
.
Computingstep by step the last columns of the operator matrices T -2, T -~ -~, + c~lc~T T-I(T -2 + c~lcl T-l) T= 2, T-3 + c’~lcl -3 -2 -~ , T A- c~c~T + c~c2T
132
CHAPTER 3.
APPROXIMATION
OF SPECTRA
we obtain
1(i
~ cg 0 0
respectively, what finally shows that the last columnsof the matrices T -m + c~c~T -m+l -~ + ,... + c~Cm_~T -m-~ -m -2 T + c~lc~T + ... + c~cm_~T are as follows:
Consequently, X(T-’~-~ + c~clT -’~ +...
+ c~ICm_IT-2)Y = a~nlc~ 2 ~. --~ a~la,~a~
(3.21) Step 5. Identity (3.21) implies that Ila~a.~a~f~ll
= IIX(T -m-~ + c~oT -m +...
+
and since Xc~cj -- a~c~cja,~X for all j, we further
= II(XT-m-~y
+ a~n~c~clamXT-~Y
conclude that
+...
m lain
~ ::C~
with a constant C depending on the polynomial Q and the radius r only. Letting e go to zero in 1 = IIAII <_ Ilaoa~lao[I " Ila~ama~IA[I <_ Cllaoa~aolle
3.3.
PSEUDOSPECTRA AND THEIR LIMITING
SETS
we arrive at a contradiction.
133 ¯
Having this result at our disposal, we can prove Theorem3.36 by repeating the arguments of the proof of Theorem3.31. Also the proof of the following result proceeds completely analogously to that of its counterpart for commonspectra, Theorem 3.33. Theorem3.38 Let ,4 be a fractal C*-subalgebra of jr which contains the identity, let ~ > O, and let the polynomials Ln be as in (3.16) with the additional requirement that all coefficient sequences (a(n j)) belong to A. Then lim sup a(~) (Ln) = lim inf (~) (Ln). Weconclude by applying these results to our standard example, the finite section method for Toeplitz operators. Let f0, fl, ..., f,~ be continuous functions and suppose that the Toeplitz operator T(f,~) is invertible. Consider the matrix resp. operator polynomials "~, Ln(A) := T~(f0) + Tn(f~))~ +... + Tn(f,~)~ P(A) := m. T(fo) + T(f~))~ +... + T(f,~)A Theorem 3.39 Let the functions fj and the polynomials Ln and P be as above. Then, for every ~ > O, lim sup a(~) (n,~) = lim inf (e) (L,~) =(e) (P) Proof. Let L stand for the polynomial L(~) := ((Tn(fo)) Due to the fractality
+ ~) + ((Tn(fl))
+ ~)~ +... + ((Tn(fm))
of the algebra S(C), and by Theorems3.36 and 3.38,
lira sup a(e) (Ln) = lira inf a(~) (Ln) = a(~)g For the image of L under the homomorphismsWand IYVone easily finds W(L(A)) = T(fo) + T(fl)A +... + ~ = P(A), I~(L(A)) = T()~) T( fl)A +. .. + T( fm)A"~ =: which, together with Corollary 1.58 and the inverse closedness of S(C)/G in )r/6, yields lim sup a(~) (L,~) = lim inf (~) (L,~) =(~) (P)kl a(~)(/5). Finally, from identity (1.32) we infer that "~ D(A) = CT(fo)*C + CT(f~)*C)~ +... +CT(fm)*CA = C(T(]o) T(fl),~ +. .. + T(.f,~)~")*C = CP(~)*C and, hence, a (~) (P) = (~) ( /5).
134
CHAPTER 3.
APPROXIMATION
3.4 Numerical ranges and their
OF SPECTRA
limiting
sets
The (several kinds of) numerical ranges provide further examples of (upper) spectral approximants which share their good asymptotic behavior for all approximation sequences with the e-pseudospectra. 3.4.1
Spatial
and
algebraic
numerical
ranges
Let H be a (complex) Hilbert space with inner product (., .), and let a linear bounded operator on H. The spatial numerical range SNH(A) of A is the set SNH(A):= ( (Ax, x) : x e H, Ilxll = Thus, SNH(A)consists of all Rail