Higham - Accuracy and Stability of Numerical Algorithms (523152), страница 4
Текст из файла (страница 4)
In this book I have used notation that I find nearly always to be the most convenient for error analysis:the key ingredient is the symbol γ n = nu/(1 - nu), explained in §3.1. I havealso summarized many basic error analysis results (for example, in Chapters 3and 8) and made use of them throughout the book. I like to think of thesebasic results as analogues of the Fortran BLAS (Basic Linear Algebra Subprograms): once available in a standard form they can be used as black boxesand need not be reinvented.A number of the topics included here have not been treated in depth in previous numerical analysis textbooks. These include floating point summation,block LU factorization, condition number estimation. the Sylvester equation,powers of matrices.
finite precision behaviour of stationary iterative methods,Vandermonde systems, and fast matrix multiplication, each of which has itsown chapter. But there are also some notable omissions. I would have likedto include a chapter on Toeplitz systems, but this is an area in which stability and accuracy are incompletely understood and where knowledge of theunderlying applications is required to guide the investigation. The importantproblems of updating and downdating matrix factorizations when the matrixundergoes a “small” change have also been omitted due to lack of time andspace. A further omission is analysis of parallel algorithms for all the problemsconsidered in the book (though blocked and partitioned algorithms and oneparticular parallel method for triangular systems are treated).
Again, thereare relatively few results and this is an area of active research.Throughout the history of numerical linear algebra, theoretical advanceshave gone hand in hand with software development. This tradition has continued with LAPACK (1987-), a project to develop a state-of-the-art Fortranpackage for solving linear equations and eigenvalue problems. LAPACK hasenjoyed a synergy with research that has led to a number of important breakthroughs in the design and analysis of algorithms, from the standpoints ofboth performance and accuracy.
A key feature of this book is that it provides the material needed to understand the numerical properties of many ofthe algorithms in LAPACK, the except ions being the routines for eigenvalueand singular value problems. In particular, the error bounds computed bythe LAPACK linear equation solvers are explained, the LAPACK conditionestimator is described in detail, and some of the software issues confronted byXX111the LAPACK developers are highlighted.
Chapter 25 examines the influenceof floating point arithmetic on general numerical software, offering salutarystories, useful techniques, and brief descriptions of relevant codes.This book has been written with numerical analysis courses in mind, although it is not designed specifically as a textbook. It would be a suitablereference for an advanced course (for example, for a graduate course on Numerical Linear Algebra following the syllabus recommended by the ILAS Education Committee [601, 1993]), and could be used by instructors at all levelsas a supplementary text from which to draw examples, historical perspective,statements of results, and exercises.
The exercises (actually labelled “problems”) are an important part of the book, and many of them have not, to myknowledge, appeared in textbooks before. Where appropriate I have indicatedthe source of an exercise; a name without a citation means that the exercisecame from private communication or unpublished notes. Research problemsgiven at the end of some sets of exercises emphasize that most of the areascovered are still active.In addition to surveying and unifying existing results (including some thathave not appeared in the mainstream literature) and sometimes improvingupon their presentation or proof, this book contains new results. Some ofparticular note are as follows.1. The error analysis in §5.3 for evaluation of the Newton interpolatingpolynomial.2. The forward error analysis for iterative refinement in §11.1.3.
The error analysis of Gauss-Jordan elimination in §13.4.4. The unified componentwise error analysis of QR factorization methodsin Chapter 18, and the corresponding analysis of their use for solvingthe least squares problem in Chapter 19.5.
Theorem 20.3, which shows the backward stability of the QR factorization method for computing the minimum 2-norm solution to an underdetermined system.The Notes and References are an integral part of each chapter. In addition to containing references, historical information, and further details, theyinclude material not covered elsewhere in the chapter, and should always beconsulted, in conjunction with the index, to obtain the complete picture.I have included relatively few numerical examples except in the first chapter. There are two reasons. One is to reduce the length of the book. Thesecond reason is because today it so easy for the reader to perform experiments in MATLAB* or some other interactive system.
To this end I have made*MATLAB is a registered trademark of The Math Works, Inc.xxivPREFACEavailable the Test Matrix Toolbox, which contains MATLAB M-files for manyof the algorithms and special matrices described in the book; see Appendix E.This book has been designed to be as easy to use as possible. There arethorough name and subject indexes, page headings show chapter and sectiontitles and numbers, and there is extensive cross-referencing.
I have adoptedthe unusual policy of giving with (nearly) every citation not only its numericallocation in the bibliography but also the names of the authors and the year ofpublication. This provides as much information as possible in a citation andreduces the need for the reader to turn to the bibliography.Adatabase acc-stab-num-alg.bib containing all the referencesin the bibliography is available over the Internet from the bibnet project(which can be accessed via netlib, described in §C.2).Special care has been taken to minimize the number of typographical andother errors, but no doubt, some remain. I will be happy to receive notificationof errors, as well as comments and suggestions for improvement.AcknowledgementsThree books, in addition to Wilkinson’s, have strongly influenced my researchin numerical linear algebra and have provided inspiration for this book: Goluband Van Loan’s Matrix Computations [470, 1989] (first edition 1983), Parlett’sThe Symmetric Eigenvalue Problem [820, 1980], and Stewart’s Introductionto Matrix Computations [941, 1973].
Knuth’s The Art of Computer Programming books [666, 1973-1981] have also influenced my style and presentation.Jim Demmel has contributed greatly to my understanding of the subjectof this book and provided valuable technical help and suggestions.
The firsttwo chapters owe much to the work of Velvel Kahan; I am grateful to himfor giving me access to unpublished notes and for suggesting improvements toearly versions of Chapters 2 and 25. Des Higham read various drafts of thebook, offering sound advice and finding improvements that had eluded me.Other people who have given valuable help, suggestions, or advice areZhaojun Bai, Brad Baxter, Åke Björck, Martin Campbell-Kelly,Shivkumar Chandrasekaran, Alan Edelman, Warren Ferguson, PhilipGill, Gene Golub, George Hall, Sven Hammarling, Andrzej Kielbas, Philip Knight, Beresford Parlett, David Silvester, MichaelSaunders, Ian Smith, Doron Swade, Nick Trefethen, Jack Williams,and Hongyuan Zha.David Carlisle provided invaluable help and advice concerning.Working with SIAM on the publication of this book was a pleasure.
Specialthanks go to Nancy Abbott (design), Susan Ciambrano (acquisition), Ed Cilurso (production), Beth Gallagher (copy editing), Corey Gray (production),XXVMary Rose Muccie (copy editing and indexing), Colleen Robishaw (design),and Sam Young (production).Research leading to this book has been supported by grants from theEngineering and Physical Sciences Research Council, by a Nuffield ScienceResearch Fellowship from the Nuffield Foundation, and by a NATO Collaborative Research Grant held with J.
W. Demmel. I was fortunate to be ableto make extensive use of the libraries of the University of Manchester, theUniversity of Dundee, Stanford University, and the University of California,Berkeley.This book was typeset inusing the book document style. Thereferences were prepared inand the index with MakeIndex. It is difficult to imagine how I could have written the book without these wonderfultools. I used the “big” software from thedistribution, running on a486DX workstation. I used text editors The Semware Editor (Semware Corporation) and GNU Emacs (Free Software Foundation) and checked spellingwith PC-Write (Quicksoft).ManchesterApril 1995Nicholas J.
HighamAbout the DedicationThis book is dedicated to the memory of two remarkable English mathematicians, James Hardy Wilkinson (1919-1986), FRS, and Alan Mathison Turing(1912-1954), FRS, both of whom made immense contributions to scientificcomputation.Turing’s achievements include his paper “On Computable Numbers, withan Application to the Entscheidungsproblem”, which answered Hilbert’s decidability question using the abstract device now known as a Turing machine[1025, 1936]; his work at Bletchley Park during World War II on breakingthe ciphers of the Enigma machine; his 1945 report proposing a design forthe Automatic Computing Engine (ACE) at the National Physical Laboratory [1026, 1945]; his 1948 paper on LU factorization and its rounding erroranalysis [1027, 1948]; his consideration of fundamental questions in artificialintelligence (including his proposal of the “Turing test”); and, during the lastpart of his life, spent at the University of Manchester, his work on morphogenesis (the development of structure and form in an organism).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
