logo资料库

Matrix Algorithms.pdf

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：41.26M 资料格式：pdf 举报 版权申诉
第1页 / 共958页
第2页 / 共958页
第3页 / 共958页
第4页 / 共958页
第5页 / 共958页
第6页 / 共958页
第7页 / 共958页
第8页 / 共958页
资料共958页，剩余部分请下载后查看
    MatrixAlgorithmsVolume I:Basic DecompositionsG. W.StewartUniversity of MarylandCollege Park, MarylandSociety for Industrial and Applied MathematicsPhiladelphiasiam
    Copyright ©1998 by the Society for Industrial and Applied Mathematics.1098765432 1All rights reserved. Printed in the United States of America. No part of this book may be reproduced,stored, or transmitted in any manner without the written permission of the publisher. For information, writeto the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia,PA 19104-2688.Library of Congress Cataloging-in-Publication DataStewart, G. W. (Gilbert W.)Matrix algorithms / G. W. Stewart.p. cm.Includes bibliographical references and index.Contents: v. 1. Basic decompositionsISBN 0-89871-414-1 (v. 1 : pbk.)1. Matrices. I. Title.QA188.S714 1998512.9'434-dc21 98-224450-89871-414-1 (Volume I)0-89871-418-4 (set)is a registered trademark.siam
    CONTENTSAlgorithms xiiiNotation xvPreface xvii1 Matrices, Algebra, and Analysis 11 Vectors 21.1 Scalars 2Real and complex numbers. Sets and Minkowski sums.1.2 Vectors 31.3 Operations with vectors and scalars 51.4 Notes and references 7Representing vectors and scalars. The scalar product. Functionspaces.2 Matrices 72.1 Matrices 82.2 Some special matrices 9Familiar characters. Patterned matrices.2.3 Operations with matrices 13The scalar-matrix product and the matrix sum. The matrixproduct. The transpose and symmetry. The trace and thedeterminant.2.4 Submatrices and partitioning 17Submatrices. Partitions. Northwest indexing. Partitioning andmatrix operations. Block forms.2.5 Some elementary constructions 21Inner products. Outer products. Linear combinations. Columnand row scaling. Permuting rows and columns. Undoing apermutation. Crossing a matrix. Extracting and insertingsubmatrices.2.6 LU decompositions 232.7 Homogeneous equations 25v
    vi CONTENTS2.8 Notes and references 26Indexing conventions. Hyphens and other considerations.Nomenclature for triangular matrices. Complex symmetricmatrices. Determinants. Partitioned matrices. TheLU decomposition.3 Linear Algebra 283.1 Subspaces, linear independence, and bases 28Subspaces. Linear independence. Bases. Dimension.3.2 Rank and nullity 33A full-rank factorization. Rank and nullity.3.3 Nonsingularity and inverses 36Linear systems and nonsingularity. Nonsingularity and inverses.3.4 Change of bases and linear transformations 39Change of basis. Linear transformations and matrices.3.5 Notes and references 42Linear algebra. Full-rank factorizations.4 Analysis 424.1 Norms 42Componentwise inequalities and absolute values. Vector norms.Norms and convergence. Matrix norms and consistency. Operatornorms. Absolute norms. Perturbations of the identity. TheNeumann series.4.2 Orthogonality and projections 55Orthogonality. The QR factorization and orthonormal bases.Orthogonal projections.4.3 The singular value decomposition 61Existence. Uniqueness. Unitary equivalence. Weyl's theorem andthe min-max characterization. The perturbation of singularvalues. Low-rank approximations.4.4 The spectral decomposition 704.5 Canonical angles and the CS decomposition 73Canonical angles between subspaces. The CS decomposition.4.6 Notes and references 75Vector and matrix norms. Inverses and the Neumann series. TheQR factorization. Projections. The singular value decomposition.The spectral decomposition. Canonical angles and theCS decomposition.5 Addenda 775.1 Historical 77On the word matrix. History.5.2 General references 78Linear algebra and matrix theory. Classics of matrix
    CONTENTS viicomputations. Textbooks. Special topics. Software. Historicalsources.2 Matrices and Machines 811 Pseudocode 821.1 Generalities 821.2 Control statements 83The if statement. The for statement. The while statement.Leaving and iterating control statements. The goto statement.1.3 Functions 851.4 Notes and references 86Programming languages. Pseudocode.2 Triangular Systems 872.1 The solution of a lower triangular system 87Existence of solutions. The forward substitution algorithm.Overwriting the right-hand side.2.2 Recursive derivation 892.3 A "new" algorithm 902.4 The transposed system 922.5 Bidiagonal matrices 922.6 Inversion of triangular matrices 932.7 Operation counts 94Bidiagonal systems. Full triangular systems. Generalobservations on operations counts. Inversion of a triangularmatrix. More observations on operation counts.2.8 BLAS for triangular systems 992.9 Notes and references 100Historical. Recursion. Operation counts. Basic linear algebrasubprograms (BLAS).3 Matrices in Memory 1013.1 Memory, arrays, and matrices 102Memory. Storage of arrays. Strides.3.2 Matrices in memory 104Array references in matrix computations. Optimization and theBLAS. Economizing memory—Packed storage.3.3 Hierarchical memories 109Virtual memory and locality of reference. Cache memory. Amodel algorithm. Row and column orientation. Level-two BLAS.Keeping data in registers. Blocking and the level-three BLAS.3.4 Notes and references 119The storage of arrays. Strides and interleaved memory. TheBLAS. Virtual memory. Cache memory. Large memories andmatrix problems. Blocking.
    viii CONTENTS4 Rounding Error 1214.1 Absolute and relative error 121Absolute error. Relative error.4.2 Floating-point numbers and arithmetic 124Floating-point numbers. The IEEE standard. Rounding error.Floating-point arithmetic.4.3 Computing a sum: Stability and condition 129A backward error analysis. Backward stability. Weak stability.Condition numbers. Reenter rounding error.4.4 Cancellation 1364.5 Exponent exceptions 138Overflow. Avoiding overflows. Exceptions in the IEEE standard.4.6 Notes and references 141General references. Relative error and precision. Nomenclaturefor floating-point numbers. The rounding unit. Nonstandardfloating-point arithmetic. Backward rounding-error analysis.Stability. Condition numbers. Cancellation. Exponent exceptions.3 Gaussian Elimination 1471 Gaussian Elimination 1481.1 Four faces of Gaussian elimination 148Gauss's elimination. Gaussian elimination and elementary rowoperations. Gaussian elimination as a transformation to triangularform. Gaussian elimination and the LU decomposition.1.2 Classical Gaussian elimination 153The algorithm. Analysis of classical Gaussian elimination. LUdecompositions. Block elimination. Schur complements.1.3 Pivoting 165Gaussian elimination with pivoting. Generalities on pivoting.Gaussian elimination with partial pivoting.1.4 Variations on Gaussian elimination 169Sherman's march. Pickett's charge. Grout's method. Advantagesover classical Gaussian elimination.1.5 Linear systems, determinants, and inverses 174Solution of linear systems. Determinants. Matrix inversion.1.6 Notes and references 180Decompositions and matrix computations. Classical Gaussianelimination. Elementary matrix. The LU decomposition. BlockLU decompositions and Schur complements. Block algorithmsand blocked algorithms. Pivoting. Exotic orders of elimination.Gaussian elimination and its variants. Matrix inversion.Augmented matrices. Gauss-Jordan elimination.2 A Most Versatile Algorithm 185
    CONTENTS ix2.1 Positive definite matrices 185Positive definite matrices. The Cholesky decomposition. TheCholesky algorithm.2.2 Symmetric indefinite matrices 1902.3 Hessenberg and tridiagonal matrices 194Structure and elimination. Hessenberg matrices. Tridiagonalmatrices.2.4 Band matrices 2022.5 Notes and references 207Positive definite matrices. Symmetric indefinite systems. Bandmatrices.3 The Sensitivity of Linear Systems 2083.1 Normwise bounds 209The basic perturbation theorem. Normwise relative error and thecondition number. Perturbations of the right-hand side. Artificialill-conditioning.3.2 Componentwise bounds 2173.3 Backward perturbation theory 219Normwise backward error bounds. Componentwise backwarderror bounds.3.4 Iterative refinement 2213.5 Notes and references 224General references. Normwise perturbation bounds. Artificialill-conditioning. Componentwise bounds. Backward perturbationtheory. Iterative refinement.4 The Effects of Rounding Error 2254.1 Error analysis of triangular systems 226The results of the error analysis.4.2 The accuracy of the computed solutions 227The residual vector.4.3 Error analysis of Gaussian elimination 229The error analysis. The condition of the triangular factors. Thesolution of linear systems. Matrix inversion.4.4 Pivoting and scaling 235On scaling and growth factors. Partial and complete pivoting.Matrices that do not require pivoting. Scaling.4.5 Iterative refinement 242A general analysis. Double-precision computation of the residual.Single-precision computation of the residual. Assessment ofiterative refinement.4.6 Notes and references 245General references. Historical. The error analyses. Condition of
    x CONTENTSthe L- and U-factors. Inverses. Growth factors. Scaling. Iterativerefinement.4 The QR Decomposition and Least Squares 2491 The QR Decomposition 2501.1 Basics 250Existence and uniqueness. Projections and the pseudoinverse.The partitioned factorization. Relation to the singular valuedecomposition.1.2 Householder triangularization 254Householder transformations. Householder triangularization.Computation of projections. Numerical stability. Gradedmatrices. Blocked reduction.1.3 Triangularization by plane rotations 270Plane rotations. Reduction of a Hessenberg matrix. Numericalproperties.1.4 The Gram—Schmidt algorithm 277The classical and modified Gram-Schmidt algorithms. ModifiedGram—Schmidt and Householder triangularization. Error analysisof the modified Gram-Schmidt algorithm. Loss of orthogonality.Reorthogonalization.1.5 Notes and references 288General references. The QR decomposition. The pseudoinverse.Householder triangularization. Rounding-error analysis. Blockedreduction. Plane rotations. Storing rotations. Fast rotations. TheGram—Schmidt algorithm. Reorthogonalization.2 Linear Least Squares 2922.1 The QR approach 293Least squares via the QR decomposition. Least squares via theQR factorization. Least squares via the modified Gram-Schmidtalgorithm.2.2 The normal and seminormal equations 298The normal equations. Forming cross-product matrices. Theaugmented cross-product matrix. The instability of cross-productmatrices. The seminormal equations.2.3 Perturbation theory and its consequences 305The effects of rounding error. Perturbation of the normalequations. The perturbation of pseudoinverses. The perturbationof least squares solutions. Accuracy of computed solutions.Comparisons.2.4 Least squares with linear constraints 312The null-space method. The method of elimination. Theweighting method.
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料