History of Numerical Linear Algebra, a Personal View Gene H.Golub Stanford University Gene Golub History of Numerical Linear Algebra
History of Numerical Linear Algebra, a Personal View Gene H. Golub Stanford University Gene Golub / History of Numerical Linear Algebra
What is Numerical Analysis? .Webster's New Collegiate Dictionary (1973): "The study of quantitative approximations to the solutions of mathematical problems including consideration of the errors and bounds to the errors involved." .The American Heritage Dictionary(1992): "The study of approximate solutions to mathematical problems,taking into account the extent of possible errors." Gene Golub/History of Numerical Linear Algebra
What is Numerical Analysis? • Webster’s New Collegiate Dictionary (1973): ”The study of quantitative approximations to the solutions of mathematical problems including consideration of the errors and bounds to the errors involved.” • The American Heritage Dictionary (1992): ”The study of approximate solutions to mathematical problems, taking into account the extent of possible errors.” Gene Golub / History of Numerical Linear Algebra 1
Numerical Linear Algebra Numerical Linear Algebra (NLA)is a small but active area of research:a couple of hundred active,committed persons.But the community involves many scientists. Gene Golub/History of Numerical Linear Algebra 2
Numerical Linear Algebra Numerical Linear Algebra (NLA) is a small but active area of research: a couple of hundred active, committed persons. But the community involves many scientists. Gene Golub / History of Numerical Linear Algebra 2
How It All Started Numerical analysis motivated the development of the earliest computers. ●Ballistics ●Solution of PDE's ●Data Analysis Early pioneers included: J.von Neumann A.M.Turing In the beginning.·. von Neumann Goldstine (1947): "Numerical Inversion of Matrices of High Order" Gene Golub/History of Numerical Linear Algebra
How It All Started Numerical analysis motivated the development of the earliest computers. • Ballistics • Solution of PDE’s • Data Analysis Early pioneers included: J. von Neumann A. M. Turing In the beginning... von Neumann & Goldstine (1947): “Numerical Inversion of Matrices of High Order” Gene Golub / History of Numerical Linear Algebra 3
Top Ten Algorithms in Science (Dongarra and Sullivan,2000) 1.Metropolis Algorithm (Monte Carlo method) 2.Simplex Method for Linear Programming 3.Krylov Subspace Iteration Methods 4.The Decompositional Approach to Matrix Computations 5.The Fortran Optimizing Compiler 6.QR Algorithm for Computing Eigenvalues 7.Quicksort Algorithm for Sorting 8.Fast Fourier Transform 9.Integer Relation Detection Algorithm 10.Fast Multipole Method Red:Algorithms within the exclusive domain of NLA research. Blue:Algorithms strongly (though not exclusively) connected to NLA research. Gene Golub/History of Numerical Linear Algebra 4
Top Ten Algorithms in Science (Dongarra and Sullivan, 2000) 1. Metropolis Algorithm (Monte Carlo method) 2. Simplex Method for Linear Programming 3. Krylov Subspace Iteration Methods 4. The Decompositional Approach to Matrix Computations 5. The Fortran Optimizing Compiler 6. QR Algorithm for Computing Eigenvalues 7. Quicksort Algorithm for Sorting 8. Fast Fourier Transform 9. Integer Relation Detection Algorithm 10. Fast Multipole Method • Red: Algorithms within the exclusive domain of NLA research. • Blue: Algorithms strongly (though not exclusively) connected to NLA research. Gene Golub / History of Numerical Linear Algebra 4
Three important components in solving NLA problems Development and analysis of numerical algorithms ●Perturbation theory ●Software Gene Golub/History of Numerical Linear Algebra
Three important components in solving NLA problems • Development and analysis of numerical algorithms • Perturbation theory • Software Gene Golub / History of Numerical Linear Algebra 5
A Fundamental Problem Problem:Suppose Ax=b+r, where A is an m x n matrix,and b is a given vector. Goal:Determine r such that rll min. Gene Golub/History of Numerical Linear Algebra 6
A Fundamental Problem Problem: Suppose Ax = b + r, where A is an m × n matrix, and b is a given vector. Goal: Determine r such that krk = min . Gene Golub / History of Numerical Linear Algebra 6
Important Parameters The relationship between m and n: overdetermined vs.'square'vs.underdetermined Uniqueness of solution The rank of the matrix A(difficult to handle if a small perturbation in A will change rank) 。Choice of norm ·Structure of A: -Sparsity Specialized matrices such as Hankel or Toeplitz Origin of problem:ideally,can make use of this in developing an algorithm. Gene Golub/History of Numerical Linear Algebra
Important Parameters • The relationship between m and n: – overdetermined vs. ‘square’ vs. underdetermined – Uniqueness of solution • The rank of the matrix A (difficult to handle if a small perturbation in A will change rank) • Choice of norm • Structure of A: – Sparsity – Specialized matrices such as Hankel or Toeplitz • Origin of problem: ideally, can make use of this in developing an algorithm. Gene Golub / History of Numerical Linear Algebra 7
Some Perturbation Theory Given Ax=6. and the perturbed system (A+△A)y=b+6, it can be shown that if N△AL≤e, deltal≤e, IA‖ b then lz-<2E·(A), Iz≤1-p where p=△A·IA-1‖=I△A‖·(A)/A‖<1， and (A)=‖A‖·‖A-1 Gene Golub/History of Numerical Linear Algebra 8
Some Perturbation Theory Given Ax = b, and the perturbed system (A + ∆A)y = b + δ, it can be shown that if k∆Ak kAk ≤ ε, kdeltak kbk ≤ ε, then kx − yk kxk ≤ 2ε 1 − ρ · κ(A), where ρ = k∆Ak · kA −1 k = k∆Ak · κ(A)/kAk < 1, and κ(A) = kAk · kA −1 k. Gene Golub / History of Numerical Linear Algebra 8
The Condition Number The quantity (A)=‖A‖·‖A-1‖ is called the condition number of A(or the condition number of the linear system). Note: even if s is small,a large k can be destructive a special relationship between A and 6 may further determine the conditioning of the problem A detailed theory of condition numbers: John Rice,1966. Gene Golub/History of Numerical Linear Algebra
The Condition Number The quantity κ(A) = kAk · kA −1 k is called the condition number of A (or the condition number of the linear system). Note: • even if ε is small, a large κ can be destructive • a special relationship between A and b may further determine the conditioning of the problem A detailed theory of condition numbers: John Rice, 1966. Gene Golub / History of Numerical Linear Algebra 9