Liesen J. Krylov subspace methods: principles and analysis (Oxford, 2013). - ОГЛАВЛЕНИЕ / CONTENTS
Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаLiesen J. Krylov subspace methods: principles and analysis / J.Liesen, Z.Strakos. - Oxford: Oxford University Press, 2013. - xv, 391 p.: ill. - (Numerical mathematics and scientific computation). - Ref.: p.349-384. - Indexes: p.385-391. - ISBN 978-0-19-965541-0
 

Место хранения: 02 | Отделение ГПНТБ СО РАН | Новосибирск

Оглавление / Contents
 
1  Introduction ................................................. 1
   1.1  Solving Real-world Problems ............................. 2
   1.2  A Short Recollection of Ideas ........................... 7
   1.3  Specification of the Subject and Basic Notation ........ 10
2  Krylov Subspace Methods ..................................... 12
   2.1  Projection Processes ................................... 12
   2.2  How Krylov Subspaces Come into Play .................... 19
   2.3  Mathematical Characterisation of Some Krylov Subspace
        Methods ................................................ 22
   2.4  The Arnoldi and Lanczos Algorithms ..................... 26
        2.4.1  Arnoldi and Hermitian Lanczos ................... 26
        2.4.2  Non-Hermitian Lanczos ........................... 31
        2.4.3  Historical Note: The Gram-Schmidt Method ........ 33
   2.5  Derivation of Some Krylov Subspace Methods ............. 36
        2.5.1  Derivation of CG Using the Hermitian Lanczos
               Algorithm ....................................... 36
        2.5.2  CG and the Galerkin Finite Element Method ....... 42
        2.5.3  CG and the Minimisation of a Quadratic
               Functional ...................................... 47
        2.5.4  Hermitian Indefinite Matrices and the SYMMLQ.
               Method .......................................... 54
        2.5.5  Minimising the Residual Norm: MINRES and GMRES .. 57
        2.5.6  Further Krylov Subspace Methods ................. 61
        2.5.7  Historical Note: A N. Krylov and the Early
               History of Krylov Subspace Methods .............. 64
   2.6  Summary and Outlook: Linear Projections and Nonlinear
        Behaviour .............................................. 69
3  Matching Moments and Model Reduction View ................... 71
   3.1  Stieltjes' Moment Problem .............................. 73
   3.2  Model Reduction via Orthogonal Polynomials ............. 76
        3.2.1  Derivation of the Gauss-Christoffel Quadrature .. 77
        3.2.2  Moment Matching and Convergence Properties of
               the Gauss-Christoffel Quadrature ................ 84
        3.2.3  Historical Note: Gauss' Fundamental Idea, an
               Early Application, and Later Developments ....... 87
   3.3  Orthogonal Polynomials and Continued Fractions ......... 89
        3.3.1  Three-term Recurrence and the Interlacing
               Property ........................................ 89
        3.3.2  Continued Fractions ............................. 96
        3.3.3  The Gauss-Christoffel Quadrature for Analytic
               Functions ...................................... 101
        3.3.4  Summary of the Previous Mathematical
               Development .................................... 103
        3.3.5  Historical Note: Chebyshev, Markov,
               Stieltjes, and the Moment Problem .............. 104
        3.3.6  Historical Note: Orthogonal Polynomials and
               Three-term Recurrences ......................... 107
   3.4  Jacobi Matrices ....................................... 108
        3.4.1  Algebraic Properties of Jacobi Matrices ........ 109
        3.4.2  The Persistence Theorem, Stabilisation of
               Nodes and Weights in the Gauss-Christoffel
               Quadrature ..................................... 121
        3.4.3  Historical Note: The Origin and Early
               Applications of Jacobi Matrices ................ 130
   3.5  Model Reduction via Matrices: Hermitian Lanczos and
        CG .................................................... 136
   3.6  Factorisation of the Matrix of Moments ................ 142
   3.7  Vorobyev's Moment Problem ............................. 145
        3.7.1  Application to the Hermitian Lanczos
               Algorithm and the CG Method .................... 146
        3.7.2  Application to the Non-Hermitian Lanczos
               Algorithm ...................................... 148
        3.7.3  Application to the Arnoldi Algorithm ........... 151
        3.7.4  Matching Moments and Generalisations of the
               Gauss-Christoffel Quadrature ................... 153
   3.8  Matching Moments and Projection Processes ............. 156
   3.9  Model Reduction of Large-scale Dynamical Systems ...... 160
        3.9.1  Approximation of the Transfer Function ......... 161
        3.9.2  Estimates in Quadratic Forms ................... 165
4  Short Recurrences for Generating Orthogonal Krylov
   Subspace Bases ............................................. 168
   4.1  The Existence of Conjugate Gradient Like Descent
        Methods ............................................... 169
   4.2  Cyclic Subspaces and the Jordan Canonical Form ........ 172
        4.2.1  Invariant Subspaces and the Cyclic
               Decomposition .................................. 173
        4.2.2  The Jordan Canonical Form and the Length of
               the Krylov Sequences ........................... 185
        4.2.3  Historical Note: Classical Results of Linear
               Algebra ........................................ 188
   4.3  Optimal Short Recurrences ............................. 189
   4.4  Sufficient Conditions ................................. 193
   4.5  Necessary Conditions .................................. 196
   4.6  Matrix Formulation and Equivalent Characterisations ... 204
   4.7  Short Recurrences and the Number of Distinct
        Eigenvalues ........................................... 209
   4.8  Other Types of Recurrences ............................ 211
        4.8.1  The Isometric Arnoldi Algorithm ................ 211
        4.8.2  (s + 2,t)-term Recurrences ..................... 215
        4.8.3  Generalised Krylov Subspaces ................... 219
   4.9  Remarks on Functional Analytic Representations ........ 222
5  Cost of Computations Using Krylov Subspace Methods ......... 227
   5.1  Seeing the Context is Essential ....................... 228
   5.2  Direct and Iterative Algebraic Computations ........... 238
        5.2.1  Historical Note: Are the Lanczos Method and
               the CG Method Direct or Iterative Methods? ..... 241
   5.3  Computational Cost of Individual Iterations ........... 245
   5.4  Particular Computations and Complexity ................ 248
   5.5  Closer Look at the Concept of Convergence ............. 250
        5.5.1  Linear Stationary Iterative Methods ............ 250
        5.5.2  Richardson Iteration and Chebyshev
               Semi-iteration ................................. 252
        5.5.3  Historical Note: Semi-iterative and Krylov
               Subspace Methods ............................... 254
        5.5.4  Krylov Subspace Methods: Nonlinear Methods
               for Linear Problems ............................ 257
   5.6  CG in Exact Arithmetic ................................ 258
        5.6.1  Expressions for the CG Errors and Their Norms .. 260
        5.6.2  Eigenvalue-based Convergence Results for CG .... 265
        5.6.3  Illustrations of the Convergence Behaviour of
               CG ............................................. 271
        5.6.4  Outlying Eigenvalues and Superlinear
               Convergence .................................... 275
        5.6.5  Clustered Eigenvalues and the Sensitivity of
               the Gauss-Christoffel Quadrature ............... 280
   5.7  GMRES in Exact Arithmetic ............................. 285
        5.7.1  Ritz Values and Harmonic Ritz Values ........... 286
        5.7.2  Convergence Descriptions Based on Spectral
               Information .................................... 289
        5.7.3  More General Approaches ........................ 294
        5.7.4  Any Nonincreasing Convergence Curve is
               Possible with Any Eigenvalues .................. 297
        5.7.5  Convection-diffusion Example ................... 303
        5.7.6  Asymptotic Estimates for the GMRES
               Convergence .................................... 306
   5.8  Rounding Errors and Backward Stability ................ 308
        5.8.1  Rounding Errors in Direct Computations ......... 311
        5.8.2  Historical Note: Wilkinson and the Backward
               Error Concept .................................. 315
        5.8.3  The Backward Error Concept in Iterative
               Computations ................................... 316
   5.9  Rounding Errors in the CG Method ...................... 320
        5.9.1  Delay of Convergence ........................... 320
        5.9.2  Delay of Convergence can Invalidate Composite
               Convergence Bounds ............................. 326
        5.9.3  Maximal Attainable Accuracy .................... 328
        5.9.4  Back to the Poisson Model Problem .............. 331
   5.10 Rounding Errors in the GMRES Method ................... 338
        5.10.1 The Choice of the Basis Affects Numerical
               Stability ...................................... 338
        5.10.2 Does the Orthogonalisation Algorithm Matter? ... 340
        5.10.3 MGS GMRES is Backward Stable ................... 343
   5.11 Omitted Issues and an Outlook ......................... 345
        References ............................................ 349
Index of Historical Personalities ............................. 385
Index of Technical Terms ...................................... 388


Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск]
  Пожелания и письма: branch@gpntbsib.ru
© 1997-2024 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Wed Feb 27 14:25:56 2019. Размер: 13,290 bytes.
Посещение N 1584 c 19.11.2013