Iterative Solution of Large Linear Systems

Iterative Solution of Large Linear Systems

by David M. Young

NOOK Book(eBook)

$17.49 $29.95 Save 42% Current price is $17.49, Original price is $29.95. You Save 42%.
View All Available Formats & Editions
Available on Compatible NOOK Devices and the free NOOK Apps.
LendMe® See Details
Want a NOOK ? Explore Now

Overview

Iterative Solution of Large Linear Systems by David M. Young

This self-contained treatment offers a systematic development of the theory of iterative methods. Its focal point resides in an analysis of the convergence properties of the successive overrelaxation (SOR) method, as applied to a linear system with a consistently ordered matrix. The text explores the convergence properties of the SOR method and related techniques in terms of the spectral radii of the associated matrices as well as in terms of certain matrix norms. Contents include a review of matrix theory and general properties of iterative methods; SOR method and stationary modified SOR method for consistently ordered matrices; nonstationary methods; generalizations of SOR theory and variants of method; second-degree methods, alternating direction-implicit methods, and a comparison of methods. 1971 edition.

Product Details

ISBN-13: 9780486153339
Publisher: Dover Publications
Publication date: 06/26/2013
Series: Dover Books on Mathematics
Sold by: Barnes & Noble
Format: NOOK Book
Pages: 608
Sales rank: 975,052
File size: 47 MB
Note: This product may take a few minutes to download.

Table of Contents

Prefacexiii
Acknowledgmentsxvii
Notationxix
List of Fundamental Matrix Propertiesxxi
List of Iterative Methodsxxiii
1.Introduction1
1.1.The Model Problem2
Supplementary Discussion6
Exercises6
2.Matrix Preliminaries7
2.1.Review of Matrix Theory7
2.2.Hermitian Matrices and Positive Definite Matrices18
2.3.Vector Norms and Matrix Norms25
2.4.Convergence of Sequences of Vectors and Matrices34
2.5.Irreducibility and Weak Diagonal Dominance36
2.6.Property A41
2.7.L-Matrices and Related Matrices42
2.8.Illustrations48
Supplementary Discussion53
Exercises55
3.Linear Stationary Iterative Methods63
3.1.Introduction63
3.2.Consistency, Reciprocal Consistency, and Complete Consistency65
3.3.Basic Linear Stationary Iterative Methods70
3.4.Generation of Completely Consistent Methods75
3.5.General Convergence Theorems77
3.6.Alternative Convergence Conditions80
3.7.Rates of Convergence84
3.8.The Jordan Condition Number of a 2 X 2 Matrix89
Supplementary Discussion94
Exercises95
4.Convergence of the Basic Iterative Methods106
4.1.General Convergence Theorems106
4.2.Irreducible Matrices with Weak Diagonal Dominance107
4.3.Positive Definite Matrices108
4.4.The SOR Method with Varying Relaxation Factors118
4.5.L-Matrices and Related Matrices120
4.6.Rates of Convergence of the J and GS Methods for the Model Problem127
Supplementary Discussion132
Exercises133
5.Eigenvalues of the SOR Method for Consistently Ordered Matrices140
5.1.Introduction140
5.2.Block Tri-Diagonal Matrices141
5.3.Consistently Ordered Matrices and Ordering Vectors144
5.4.Property A148
5.5.Nonmigratory Permutations153
5.6.Consistently Ordered Matrices Arising from Difference Equations157
5.7.A Computer Program for Testing for Property A and Consistent Ordering159
5.8.Other Developments of the SOR Theory162
Supplementary Discussion163
Exercises163
6.Determination of the Optimum Relaxation Factor169
6.1.Virtual Spectral Radius170
6.2.Analysis of the Case Where All Eigenvalues of B Are Real171
6.3.Rates of Convergence: Comparison with the Gauss-Seidel Method188
6.4.Analysis of the Case Where Some Eigenvalues of B Are Complex191
6.5.Practical Determination of [Omega subscript b]: General Considerations200
6.6.Iterative Methods of Choosing [Omega subscript b]209
6.7.An Upper Bound for [mu]211
6.8.A Priori Determination of [mu]: Exact Methods216
6.9.A Priori Determination of [mu]: Approximate Values222
6.10.Numerical Results224
Supplementary Discussion227
Exercises228
7.Norms of the SOR Method233
7.1.The Jordan Canonical Form of L[subscript Omega]234
7.2.Basic Eigenvalue Relation239
7.3.Determination of [double vertical line] L[subscript Omega double vertical line subscript D superscript 1/2]245
7.4.Determination of [double vertical line] L[superscript m subscript Omega b double vertical line subscript D superscript 1/2]248
7.5.Determination of [double vertical line] L[subscript Omega double vertical line subscript A superscript 1/2]255
7.6.Determination of [double vertical line] L[superscript m subscript Omega b double vertical line subscript A superscript 1/2]258
7.7.Comparison of [double vertical line] L[superscript m subscript Omega b double vertical line subscript D superscript 1/2] and [double vertical line] L[superscript m subscript Omega b double vertical line subscript A superscript 1/2]264
Supplementary Discussion265
Exercises266
8.The Modified SOR Method: Fixed Parameters271
8.1.Introduction271
8.2.Eigenvalues of L[subscript Omega, Omega']273
8.3.Convergence and Spectral Radius277
8.4.Determination of [double vertical line] L[subscript Omega, Omega' double vertical line subscript D superscript 1/2]283
8.5.Determination of [double vertical line] L[subscript Omega, Omega' double vertical line subscript A superscript 1/2]288
Supplementary Discussion291
Exercises291
9.Nonstationary Linear Iterative Methods295
9.1.Consistency, Convergence, and Rates of Convergence295
9.2.Periodic Nonstationary Methods300
9.3.Chebyshev Polynomials301
Supplementary Discussion304
Exercises304
10.The Modified SOR Method: Variable Parameters306
10.1.Convergence of the MSOR Method307
10.2.Optimum Choice of Relaxation Factors307
10.3.Alternative Optimum Parameter Sets311
10.4.Norms of the MSOR Method: Sheldon's Method315
10.5.The Modified Sheldon Method319
10.6.Cyclic Chebyshev Semi-Iterative Method321
10.7.Comparison of Norms327
Supplementary Discussion340
Exercises341
11.Semi-Iterative Methods344
11.1.General Considerations345
11.2.The Case Where G Has Real Eigenvalues347
11.3.J, JOR, and RF Semi-Iterative Methods355
11.4.Richardson's Method361
11.5.Cyclic Chebyshev Semi-Iterative Method365
11.6.GS Semi-Iterative Methods367
11.7.SOR Semi-Iterative Methods374
11.8.MSOR Semi-Iterative Methods376
11.9.Comparison of Norms383
Supplementary Discussion385
Exercises386
12.Extensions of the SOR Theory: Stieltjes Matrices391
12.1.The Need for Some Restrictions on A391
12.2.Stieltjes Matrices395
Supplementary Discussion401
Exercises401
13.Generalized Consistently Ordered Matrices404
13.1.Introduction404
13.2.CO(q, r)-Matrices, Property A[subscript q,r], and Ordering Vectors405
13.3.Determination of the Optimum Relaxation Factor413
13.4.Generalized Consistently Ordered Matrices418
13.5.Relation between GCO(q, r)-Matrices and CO(q, r)-Matrices419
13.6.Computational Procedures: Canonical Forms422
13.7.Relation to Other Work428
Supplementary Discussion429
Exercises430
14.Group Iterative Methods434
14.1.Construction of Group Iterative Methods435
14.2.Solution of a Linear System with a Tri-Diagonal Matrix441
14.3.Convergence Analysis445
14.4.Applications452
14.5.Comparison of Point and Group Iterative Methods454
Supplementary Discussion456
Exercises457
15.Symmetric SOR Method and Related Methods461
15.1.Introduction461
15.2.Convergence Analysis463
15.3.Choice of Relaxation Factor464
15.4.SSOR Semi-Iterative Methods: The Discrete Dirichlet Problem471
15.5.Group SSOR Methods474
15.6.Unsymmetric SOR Method476
15.7.Symmetric and Unsymmetric MSOR Methods478
Supplementary Discussion480
Exercises481
16.Second-Degree Methods486
Supplementary Discussion493
Exercises493
17.Alternating Direction Implicit Methods495
17.1.Introduction: The Peaceman-Rachford Method495
17.2.The Stationary Case: Consistency and Convergence498
17.3.The Stationary Case: Choice of Parameters503
17.4.The Commutative Case514
17.5.Optimum Parameters518
17.6.Good Parameters525
17.7.The Helmholtz Equation in a Rectangle531
17.8.Monotonicity534
17.9.Necessary and Sufficient Conditions for the Commutative Case535
17.10.The Noncommutative Case545
Supplementary Discussion547
Exercises548
18.Selection of Iterative Method553
Bibliography556
Index565

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews