Muutke küpsiste eelistusi

Iterative Methods for Toeplitz Systems [Kõva köide]

4.00/5 (4 hinnangut Goodreads-ist)
(Department of Mathematics, The University of Hong Kong)
  • Formaat: Hardback, 368 pages, kõrgus x laius x paksus: 242x163x24 mm, kaal: 702 g, 18 b/w line, 11 halftones
  • Sari: Numerical Mathematics and Scientific Computation
  • Ilmumisaeg: 14-Oct-2004
  • Kirjastus: Oxford University Press
  • ISBN-10: 0198504209
  • ISBN-13: 9780198504207
Teised raamatud teemal:
Iterative Methods for Toeplitz SystemsSuurem pilt
  • Formaat: Hardback, 368 pages, kõrgus x laius x paksus: 242x163x24 mm, kaal: 702 g, 18 b/w line, 11 halftones
  • Sari: Numerical Mathematics and Scientific Computation
  • Ilmumisaeg: 14-Oct-2004
  • Kirjastus: Oxford University Press
  • ISBN-10: 0198504209
  • ISBN-13: 9780198504207
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780198504207.html
Märksõnad:
Toeplitz and related systems arise in a variety of applications in mathematics and engineering, especially in signal and image processing. For researchers and graduate students as well as practicing engineers and scientists, Ng (U. of Hong Kong) explains primarily iterative methods for solving Toeplitz and related linear systems, discussing both the algorithms and their convergence theories. He assumes readers have a basic knowledge of real analysis, elementary numerical analysis, and linear algebra. After reviewing briefly some terms and results in linear algebra and the conjugate gradient method, he presents the theory of using iterative methods for solving the systems, then presents recent results using the methods. Annotation ©2004 Book News, Inc., Portland, OR (booknews.com)

Toeplitz and Toeplitz-related systems arise in a variety of applications in mathematics and engineering, especially in signal and image processing. This book deals primarily with iterative methods for solving Toeplitz and Toeplitz-related linear systems, discussing both the algorithms and their convergence theories. A basic knowledge of real analysis, elementary numerical analysis and linear algebra is assumed. The first part of the book (chapters one and two) gives a brief review of some terms and results in linear algebra and the conjugate gradient method, which are important topics for handling the mathematics later on in the book. The second part of the book (chapters three to seven) presents the theory of using iterative methods for solving Toeplitz and Toeplitz-related systems. The third part of the book (chapters eight to twelve) presents recent results from applying the use of iterative methods in different fields of applications, such as partial differential equations, signal and image processing, integral equations and queuing networks. These chapters provide research and application-oriented readers with a thorough understanding of using iterative methods, enabling them not only to apply these methods to the problems discussed but also to derive and analyze new methods for other types of problems and applications.

Arvustused

The book gives an excellent overview of the research and results in this area during the last few decades. * EMS Newsletter *

I INTRODUCTION
1 Notations and definitions
3(9)
1.1 Vectors
3(1)
1.2 Matrices
4(3)
1.3 Matrix norms
7(1)
1.4 Eigenvalues
8(2)
1.5 Singular value decomposition
10(1)
1.6 Exercises
10(2)
2 Iterative methods
12(13)
2.1 Stationary iterative methods
12(1)
2.2 Conjugate gradient iterations
13(4)
2.3 Preconditioning
17(1)
2.4 Conjugate gradient least squares
18(2)
2.5 Exercises
20(5)
II THEORY
3 Toeplitz systems
25(23)
3.1 Toeplitz matrices
25(2)
3.1.1 An example of Toeplitz system
25(2)
3.2 Direct methods
27(10)
3.2.1 The Levinson Durbin algorithm
27(2)
3.2.2 The Gohberg Sernencul formula
29(1)
3.2.3 The fast Cholesky factorization
29(1)
3.2.4 Displacement rank
30(1)
3.2.5 The Schur algorithm
31(2)
3.2.6 Superfast direct Toeplitz solvers
33(2)
3.2.7 Look-ahead algorithms
35(1)
3.2.8 Stability
36(1)
3.3 Iterative methods
37(1)
3.4 Toeplitz matrix-vector multiplications
37(3)
3.4.1 Diagonalization of circulant matrices
37(1)
3.4.2 Diagonalization of {ω}-circulant matrices
38(1)
3.4.3 Computation of a Toeplitz matrix
39(1)
3.5 Generating functions
40(5)
3.6 Conjugate gradient methods for Toeplitz systenis
45(1)
3.7 Exercises
46(1)
3.8 Notes
47(1)
4 Circulant preconditioners
48(32)
4.1 Historical remarks
48(1)
4.2 Complexity
48(1)
4.3 Strang's preconditioner
49(7)
4.3.1 Generalized Strang preconditioner
56(1)
4.4 T. Chan's preconditioner
56(6)
4.4.1 Huckle's preconditioners
61(1)
4.5 Other circulant-type preconditioners
62(3)
4.5.1 Preconditioners by embedding
62(1)
4.5.2 Preconditioners by minimization of norms
62(2)
4.5.3 {ω}-circulant preconditioners
64(1)
4.6 A numerical example
65(1)
4.7 Circulant preconditioners from kernel functions
65(6)
4.8 Piecewise continuous generating functions
71(3)
4.9 Non-Hermitian Toeplitz systems
74(2)
4.10 Exercises
76(2)
4.11 Notes
78(2)
5 Non-circulant type preconditioners
80(14)
5.1 Optimal transform-based preconditioners
80(8)
5.1.1 Sine transform-based preconditioner
81(5)
5.1.2 Cosine transform-based preconditioner
86(1)
5.1.3 Hartley transform-based preconditioner
87(1)
5.2 Toeplitz preconditioners
88(3)
5.3 Exercises
91(1)
5.4 Notes
92(2)
6 Ill-conditioned Toeplitz systems
94(40)
6.1 Introduction
94(1)
6.2 Toeplitz-type preconditioners
94(4)
6.3 Circulant-type preconditioners
98(4)
6.4 The best circulant preconditioners
102(10)
6.4.1 Construction of the preconditioner
103(1)
6.4.2 Properties of the kernel function
104(5)
6.4.3 Spectra of the preconditioned matrices
109(3)
6.5 Numerical examples
112(2)
6.6 Multigrid methods
114(16)
6.6.1 Weakly diagonally dominant Toeplitz matrices
119(3)
6.6.2 More general Toeplitz matrices
122(1)
6.6.3 Convergence results for full multigrid method
123(3)
6.6.4 Computational cost
126(1)
6.6.5 Richardson iteration as smoother
127(3)
6.7 Recursive-based PCG methods
130(1)
6.8 Exercises
131(1)
6.9 Notes
132(2)
7 Structured systems
134(45)
7.1 Toeplitz-like systems
134(8)
7.1.1 Normal equations of Toeplitz systems
135(4)
7.1.2 Toeplitz-plus-Hankel systems
139(3)
7.2 Toeplitz-plus-band systems
142(1)
7.3 Block systems
143(13)
7.3.1 Approximation operators for block matrices
143(7)
7.3.2 Block preconditioners for general matrices
150(1)
7.3.3 Quadrantally symmetric matrices
151(3)
7.3.4 Separable matrices
154(1)
7.3.5 Numerical examples
155(1)
7.4 Toeplitz least squares problems
156(16)
7.4.1 1D Toeplitz-block least squares problems
157(3)
7.4.2 2D Toeplitz-block least squares problems
160(10)
7.4.3 Numerical examples
170(2)
7.5 Total least squares methods
172(2)
7.6 Exercises
174(1)
7.7 Notes
175(4)
III APPLICATIONS
8 Applications to ODEs and PDEs
179(32)
8.1 Introduction
179(1)
8.2 Circulaut preconditioners for elliptic problems
180(8)
8.3 Sine transform-based preconditioners
188(5)
8.3.1 Two-dimensional irregular domains
191(1)
8.3.2 Higher dimensional rectangular domains
192(1)
8.4 A numerical example
193(1)
8.5 Domain decomposition
194(1)
8.6 Banded preconditioners for sine Galerkin systems
195(4)
8.7 Numerical solutions of biharmonic equations
199(2)
8.8 Hyperbolic and parabolic equations
201(2)
8.9 Ordinary differential equations
203(7)
8.9.1 Some families of BVMs
204(1)
8.9.2 Preconditioners
205(5)
8.10 Exercises
210(1)
8.11 Notes
210(1)
9 Applications to queueing networks
211(27)
9.1 Introduction
211(1)
9.2 Overflow queueing networks
211(4)
9.3 Queueing networks with batch arrivals
215(4)
9.4 Markov-modulated Poisson processes
219(11)
9.4.1 Failure-prone manufacturing systems
227(3)
9.5 Stochastic automata networks
230(6)
9.5.1 Circulant, preconditioners for SAN
232(4)
9.6 Exercises
236(1)
9.7 Notes
237(1)
10 Applications to signal processing
238(1)
10.1 Introduction
238(1)
10.2 Known statistics solution
239(1)
10.3 Least squares filters
240(4)
10.3.1 Linear phase least squares filters
242(2)
10.4 Recursive least squares computations
244(2)
10.5 Exponentially weighted least squares computation
246(2)
10.6 Exercises
248(1)
10.7 Notes
249(1)
11 Applications to image processing
250(1)
11.1 Introduction
250(1)
11.2 The one-dimensional deblurring problem
250(8)
11.2.1 The zero (Dirichlet) boundary conditions
252(1)
11.2.2 Periodic boundary conditions
252(1)
11.2.3 Neumann boundary conditions
253(2)
11.2.4 Tikhonov regularization
255(1)
11.2.5 A numerical example
256(2)
11.3 High-resolution image reconstruction
258(5)
11.3.1 Preconditioners
263(1)
11.4 Total variation regularization
263(7)
11.4.1 Cosine transform-based preconditioners
266(1)
11.4.2 The product preconditioner
267(2)
11.4.3 Numerical examples
269(1)
11.5 Blind image restoration
270(5)
11.5.1 Alternating minimization algorithm
274(1)
11.5.2 A numerical example
275(1)
11.6 Iterative regularization methods
275(7)
11.6.1 Preconditioners
279(2)
11.6.2 Symmetric indefinite conjugate gradient methods
281(1)
11.6.3 Spatial-variant image restoration
282(1)
11.7 Exercises
282(1)
11.8 Notes
283(2)
12 Applications to integral equations
285(1)
12.1 Introduction
285(1)
12.2 Wiener-Hopf equations
285(7)
12.2.1 Circulant integral operators
286(3)
12.2.2 Other circulant integral operators
289(3)
12.3 Quadrature rules
292(2)
12.3.1 A numerical example
293(1)
12.4 Inverse lout problems
294(1)
12.5 Thermal tomography
295(4)
12.5.1 Regularization by the identity and Laplacian operators
296(1)
12.5.2 Preconditioning
297(2)
12.6 Boundary integral equations
299(12)
12.6.1 The optimal circulant integral operator
303(3)
12.6.2 Condition numbers of the preconditioned systems
306(2)
12.6.3 Galerkin methods
308(1)
12.6.4 A numerical example
309(2)
12.7 Fast dense matrix methods
311(12)
12.7.1 Optimal circulant preconditioners
315(4)
12.7.2 A numerical example
319(4)
12.8 Exercises
323(1)
12.9 Notes
324(1)
References 325(23)
Index 348


Michael K. Ng is an Associate Professor in the Department of Mathematics and also Adjunct Research Fellow in the E-Business Technology Institute at The University of Hong Kong.