Stability and Well-Posedness: Algorithm vs.Problem Fundamentally important to distinguish between the conditioning of the problem and the stability of the algorithm. Even if an algorithm is stable,not all problems can be solved using it. Making the problem well-posed -responsibility of modeller. Making the algorithm stable-responsibility of numerical analyst. A good algorithm is one for which a small change in the input of a well-posed problem causes a small change in the output. Gene Golub/History of Numerical Linear Algebra 10
Stability and Well-Posedness: Algorithm vs. Problem • Fundamentally important to distinguish between the conditioning of the problem and the stability of the algorithm. • Even if an algorithm is stable, not all problems can be solved using it. • Making the problem well-posed → responsibility of modeller. Making the algorithm stable → responsibility of numerical analyst. • A good algorithm is one for which a small change in the input of a well-posed problem causes a small change in the output. Gene Golub / History of Numerical Linear Algebra 10
Solving Linear Systems 1.Gaussian Elimination/the Cholesky decomposition 2.Iterative solution Gene Golub/History of Numerical Linear Algebra 11
Solving Linear Systems 1. Gaussian Elimination/ the Cholesky decomposition 2. Iterative solution Gene Golub / History of Numerical Linear Algebra 11
A Little Bit About Gaussian Elimination Not off to a good start...: The famous statistician Hotelling derived bounds so pessimistic that he recommended not to use it for large problems. But there's a happy end: Goldstine and von Neumann's analysis of the Cholesky method for fixed point arithmetic. Wilkinson's complete round-off error analysis of Gaussian Elimination in 1961. Those developments were turning points for GE and it has become one of the most commonly used algorithms Gene Golub/History of Numerical Linear Algebra 12
A Little Bit About Gaussian Elimination Not off to a good start...: The famous statistician Hotelling derived bounds so pessimistic that he recommended not to use it for large problems. But there’s a happy end: • Goldstine and von Neumann’s analysis of the Cholesky method for fixed point arithmetic. • Wilkinson’s complete round-off error analysis of Gaussian Elimination in 1961. Those developments were turning points for GE and it has become one of the most commonly used algorithms. Gene Golub / History of Numerical Linear Algebra 12
Round-Off Errors:Quiet but Deadly Round-off errors are quietly accumulated in every computation,and should not be overlooked! There is an error inherent in any computer's most basic arithmetic operations: fl(x+y)=x(1+e)+y(1+e)=元+灭. Gaussian Elimination with pivoting is equivalent to performing the decomposition ΠA=L·U, II is a permutation matrix,L and U are lower and upper triangular.This algorithm guarantees that max li.jl =1 >1 and maxu,l≤2n-1. 122 Gene Golub/History of Numerical Linear Algebra 13
Round-Off Errors: Quiet but Deadly Round-off errors are quietly accumulated in every computation, and should not be overlooked! There is an error inherent in any computer’s most basic arithmetic operations: fl(x + y) = x(1 + ε) + y(1 + ε) = ¯x + ¯y. Gaussian Elimination with pivoting is equivalent to performing the decomposition ΠA = L · U. Π is a permutation matrix, L and U are lower and upper triangular. This algorithm guarantees that max i≥j |ℓi,j| = 1 and max j≥i |ui,j| ≤ 2 n−1 . Gene Golub / History of Numerical Linear Algebra 13
Wilkinson's Backward Error Analysis By Wilkinson,GE with pivoting is equivalent to solving （A+Ey=b, where IEl≤8n3GA‖ou+O(2) and u,l≤G. u is the machine roundoff unit. Backward Error Analysis:shows how the original data matrix has been perturbed in the presence of round-off errors. Importance:the error can be bounded. Gene Golub/History of Numerical Linear Algebra 14
Wilkinson’s Backward Error Analysis By Wilkinson, GE with pivoting is equivalent to solving (A + E)y = b, where kEk∞ ≤ 8n 3GkAk∞u + O(u 2 ) and |ui,j| ≤ G. u is the machine roundoff unit. Backward Error Analysis: shows how the original data matrix has been perturbed in the presence of round-off errors. Importance: the error can be bounded. Gene Golub / History of Numerical Linear Algebra 14