ITERATIVE SOLUTION METHODS OWE AXELSSON Faculty of Mathematics and Informatics University of Nijmegen, The Netherlands 1 CAMBRIDGE UNIVERSITY PRESS Published by the Press Syndicate of the University of Cambridge The Pitt Building, Trumpington Street, Cambridge CB2 IRP 40 West 20th Street, New York, NY 10011-4211, USA 10 Stamford Road, Oakleigh, Melbourne 3166, Australia © Cambridge University Press 1996 First published 1994 Reprinted 1996 First paperback edition 1996 Printed in the United States of America Library of Congress Cataloging-in-Publication Data is available. A catalog record for this book is available from the British Library. ISBN 0-521-44524-8 hardback ISBN 0-521-55569-8 paperback Contents Preface xi Acknowledgments xiii 1 Direct Solution Methods 1 1.1 Introduction: Networks and Structures 2 1.2 Gaussian Elimination and Matrix Factorization 7 1.3 Range and Nullspace 14 1.4 Practical Considerations 18 1.5 Solution of Tridiagonal Systems of Equations 24 Exercises 30 References 44 2 Theory of Matrix Eigenvalues 46 2.1 The Minimal Polynomial 47 2.2 Selfadjoint and Unitary Matrices 54 2.3 Matrix Equivalence (Similarity Transformations) 56 2.4* Normal and //-Normal Matrices 62 Exercises 66 References 82 3 Positive Definite Matrices, Schur Complements, and Generalized Eigenvalue Problems 84 3.1 Positive Definite Matrices 85 3.2 Schur Complements 92 v Contents 3.3 Condition Numbers 95 3.4* Estimates of Eigenvalues of Generalized Eigenvalue Problems 98 3.5 Congruence Transformations 104 3.6 Quasisymmetric Matrices 106 Exercises 107 References 120 Reducible and Irreducible Matrices and the Perron-Frobenius Theory for Nonnegative Matrices 122 4.1 Reducible and Irreducible Matrices 123 4.2 Gershgorin Type Eigenvalue Estimates 127 4.3 The Perron-Frobenius Theorem 134 4.4 Rayleigh Quotient and Numerical Range 136 4.5* Some Estimates of the Perron-Frobenius Root of Nonnegative Matrices 141 4.6 A Leontie