Numerical Linear Algebra

1 Numerical Linear AlgebraWilliam Layton and Myron SussmanUniversity of PittsburghPittsburgh, Pennsylvaniac 2014 William Layton and Myron Sussman. All rights 978-1-312-32985-0 ContentsContentsiIntroductionviiSources of Arithmetical Error .. xiiMeasuring Errors: The trademarked quantities .. xixLinear systems and finite precision arithmeticxxiiiVectors and Matrices .. xxiiiEigenvalues and singular values.. xxviiiError and residual .. xxxviWhen is a Linear system solvable? .. xliiWhen is an N N matrix numerically singular? .. xlviI Direct Methods11 Gaussian Elimination + Backsubstitution .. Algorithms and pseudocode .. The Gaussian Elimination Algorithm .. Pivoting Strategies .. Tridiagonal and Banded Matrices .. TheLUdecomposition .. 28iiiCONTENTS2 Norms and Error FENLA and Iterative Improvement .. Vector Norms .. Norms.. Error, Residual and Condition Number.

2 Backward Error Analysis .. 65II Iterative Methods793 The MPP and the Curse of Derivation .. 1-D Model Poisson Problem .. The 2d MPP .. The 3-D MPP .. The Curse of Dimensionality .. 1114 Iterative Introduction to Iterative Methods .. Mathematical Tools .. Convergence of FOR .. Better Iterative Methods .. Dynamic Relaxation .. Splitting Methods .. 1615 SolvingAx=bby The connection to optimization .. Application to Stationary Iterative Methods .. Application to Parameter Selection .. The Steepest Descent Method .. 1916 The Conjugate Gradient The CG Algorithm .. Analysis of the CG Algorithm .. Convergence by the Projection Theorem .. Error Analysis of CG .. Preconditioning .. CGN for non-SPD systems .. 2347 Eigenvalue Introduction and Review of Eigenvalues.

3 Gershgorin Circles .. Perturbation theory of eigenvalues .. The Power Method .. Inverse Power, Shifts and Rayleigh Quotient The QR Method .. 264 Bibliography269A An omitted proof271B Tutorial on basic Matlab Objective .. Variables, values and arithmetic .. Variables are matrices .. Matrix and vector Operations .. Flow control .. Script and function files .. Algebra functionality .. Debugging .. Execution speed inMatlab.. 303 Preface It is the mark of an educated mind to rest satis-fied with the degree of precision that the nature of thesubject permits and not to seek exactness when onlyan approximation is possible. - Aristotle (384 BCE)This book presents Numerical Linear Algebra for students froma diverse audience of senior level undergraduates and beginninggraduate students in mathematics, science and engineering. Typi-cal courses it serves include:A one term, senior level class on Numerical Linear , some students in the class will be good pro-grammers but have never taken a theoretical Linear Algebra course;some may have had many courses in theoretical Linear Algebra butcannot find the on/off switch on a computer.

4 Some have been usingmethods of Numerical Linear Algebra for a while but have never seenany of its background and want to understand why methods failsometimes and work of a graduate gateway course on Numerical course gives an overview in two terms of useful methodsin computational mathematics and includes a computer lab teach-ing programming and visualization connected to the of a one term course on the theory of class is normally taken by students in mathemat-ics who want to study Numerical analysis further or to see deeperaspects of multivariable advanced calculus, Linear Algebra and ma-trix theory as they meet wide but highly motivated audience presents an interestingchallenge. In response, the material is developed as follows: Everytopic in Numerical Linear Algebra can be presented algorithmicallyand theoretically and both views of it are important. The earlysections of each chapter present the background material neededfor that chapter, an essential step since backgrounds are methods are developed algorithmically with examples.

5 Con-vergence theory is developed and the parts of the proofs that pro-vide immediate insight into why a method works or how it mightfail are given in detail. A few longer and more technically intricateproofs are either referenced or postponed to a later section of first and central idea about learning is to begin with theend in mind . In this book the end is to provide a modern under-standing of useful tools. The choice of topics is thus made basedon utility rather than beauty or completeness. The theory of al-gorithms that have proven to be robust and reliable receives lesscoverage than ones for which knowing something about the methodcan make a difference between solving a problem and not solvingone. Thus, iterative methods are treated in more detail than directmethods for both Linear systems and eigenvalue problems. Amongiterative methods, the beautiful theory of SOR is abbreviated be-cause conjugate gradient methods are a (currently at least) methodof choice for solving sparse SPD Linear systems.

6 Algorithms aregiven in pseudocode based on the widely used MATLAB pseudocode transparently presents algorithmic steps and, atthe same time, serves as a framework for computer implementationof the material in this book is constantly evolving. Welcome!IntroductionThere is no such thing as the Scientific Revolution,and this is a book about Steven Shapin,The Scientific book presents Numerical Linear Algebra . The presentationis intended for the first exposure to the subject for students frommathematics, computer science, engineering. Numerical Linear al-gebra studies several problems: Linear Systems:Ax=b: Solve theN Nlinear Problems:A = : Find all the eigenvaluesand eigenvectors or a selected problems and least squares:Find a uniqueusefulsolution (that is as accurate as possible given the data errors) ofa Linear system that is undetermined, overdetermined or nearlysingular with noisy focus on the first, treat the second lightly and omit thethird.

7 This choice reflects the order the algorithms and theory arebuilt, not the importance of the three. Broadly, there are two typesof subproblems: small to medium scale and large scale. large inlarge scale problems can be defined as follows: a problem is large ifmemory management and turnaround time are central , a problem is not large if one can simply call a canned lin-ear Algebra routine and solve the problem reliably within time andviiviiiINTRODUCTION resource constraints with no special expertise. Small to mediumscale problems can also be very challenging when the systems arevery sensitive to data and roundoff errors and data errors are sig-nificant. The latter is typical when the coefficients and RHS comefrom experimental data, which always come with noise. It also oc-curs when the coefficients depend on physical constants which maybe known to only one significant origin of Numerical Linear Algebra lies in a 1947 paper ofvon Neumann and Goldstine [VNG47].

8 Its table of contents, givenbelow, is quite modern in all respects except for the omission ofiterative methods:ixNUMERICAL INVERTING OF MATRICES OF HIGHORDERJOHN VON NEUMANN AND H. H. GOLDSTINEANALYTIC TABLE OF CONTENTSPREFACECHAPTER I. The sources of errors in a The sources of errors.(A) Approximations implied by the mathematical model.(B) Errors in observational data.(C) Finitistic approximations to transcendental and im-plicit mathematical formulations.(D) Errors of computing instruments in carrying out el-ementary operations: Noise. Round off errors. Analogy and digital computing. The Discussion and interpretation of the errors (A)-(D). Analysis of stability. The results of Courant, Friedrichs,and Analysis of noise and round off errors and their rela-tion to high speed The purpose of this paper. Reasons for the selection ofits Factors which influence the errors (A)-(D).

9 Selection ofthe elimination Comparison between analogy and digital computingmethodsxINTRODUCTIONCHAPTER II. Round off errors and ordinary algebraical Digital numbers, pseudo-operations. Conventions re-garding their nature, size and use: (a), (b) Ordinary real numbers, true operations. Precision ofdata. Conventions regarding these: (c), (d) Estimates concerning the round off errors:(e) Strict and probabilistic, simple precision.(f) Double precision for expressions ni= The approximative rules of Algebra for Scaling by iterated halvingCHAPTER III. Elementary matrix The elementary vector and matrix Properties of|A|,|A|`andN(A). Symmetry and Diagonality and Pseudo-operations for matrices and vectors. The rele-vant IV. The elimination Statement of the conventional elimination Positioning for size in the intermediate Statement of the elimination method in terms of factor-ing A into semidiagonal factorsC,B Replacement ofC,B byB,C, Reconsideration of the decomposition theorem.

10 Theuniqueness theoremCHAPTER V. Specialization to definite Reasons for limiting the discussion to definite Properties of our algorithm (that is, of the eliminationmethod) for a symmetric matrix A. Need to considerpositioning for size as Properties of our algorithm for a definite matrix Detailed matrix bound estimates, based on the resultsof the preceding sectionCHAPTER VI. The pseudo-operational Choice of the appropriate pseudo-procedures, by whichthe true elimination will be Properties of the The approximate decomposition ofA, based on the The inverting ofBand the necessary scale Estimates connected with the inverse Continuation. The estimates connected with the The generalAI. Various Continuation. The estimates connected with the VII. Evaluation of the Need for a concluding analysis and Restatement of the conditions affectingAandAI: (A) (D). Discussion of (A), (B): Scaling Discussion of (C): Approximate inverse, Discussion of (D) : Approximate Restatement of the computational prescriptions.