Condition Number History

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Optimization Methods in Numerical Perturbation Analysis:Joseph F. Grcar Lawrence Berkeley Laboratory jfgrcar@lbl.gov Stanford University May 24, 2004revised May 30

Condition Numbers from Optimal Backward Errors with Applications to Inde nite Least Squares (ILS)1

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Outline Condition Number History Condition Number Background Condition Number Formulas Inde nite Linear Least Squares Discussion

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Condition Number Historybackward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine matrix condition number 1948 Turing matrix condition number 1949 Todd backward error analysis 1954 Givens matrix condition number 1958 Newman, Todd matrix condition number 1958 Householder backward error analysis 1960 Wilkinson condition numbers as derivatives 1960 Bauer backward error bounds 1961 Wilkinson condition numbers as coe cients 1963 Wilkinson optimal backward errors 1964 Oettli, Prager condition numbers as limits 1966 Rice optimal backward errors 1967 Rigal, Gaches condition numbers as lim sup 1978 Gautschi condition numbers as lim sup 1979 Skeel 3

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Bibliography

¨ H. Wittmeyer. Ein uß der Anderung einer Matrix auf der L¨sung des zugeh¨rigen o o Gleichungssystems, sowie auf die charakteristischen Zahlen und die Eigenvektoren. Zeitschrift f¨r angewandte Mathematik und Mechanik, 16:287–300, 1936. u J. von Neumann and H. H. Goldstine. Numerical inverting of matrices of high order. Bulletin of the American Mathematical Society, 53(11):1021–1099, November 1947. A. M. Turing. Rounding-o errors in matrix processes. The Quarterly Journal of Mechanics and Applied Mathematics, 1(3):287–308, September 1948. J. Todd. The condition of certain matrices, I. The Quarterly Journal of Mechanics and Applied Mathematics, 2(4):469–472, December 1949. J. W. Givens. Numerical computation of the characteristic values of a real symmetric matrix. Report ORNL-1574, Oak Ridge National Laboratory, Oak Ridge, Tennessee, 1954. M. Newman and J. Todd. The evaluation of matrix inversion programs. Journal of the Society of Industrial and Applied Mathematics, 6(4):466–476, December 1958. A. S. Householder. A class of methods for inverting matrices. Journal of the Society for Industrial and Applied Mathematics, 6(2):189–195, 1958. J. H. Wilkinson. Rounding errors in algebraic processes. In Information Processing, pages 44–53. Published by R. Oldenbourg, Munich and Butterworths, London, 1960. Proceedings of the International Conference on Information Processing, UNESCO, Paris, 15–20 June 1959. 4

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Bibliography, cont.F. L. Bauer. On the de nition of condition numbers and their relation to closed methods for solving linear systems. In Information Processing, pages 109–110. Published by R. Oldenbourg, Munich and Butterworths, London, 1960. Proceedings of the International Conference on Information Processing, UNESCO, Paris, 15–20 June 1959. J. H. Wilkinson. Error analysis of direct methods of matrix inversion. Journal of the Associati

on of Computing Machinery, 8(3):281–330, July 1961. J. H. Wilkinson. Rounding Errors in Algebraic Processes. Prentice Hall, Englewood Cli s, New Jersey, 1963. W. Oettli and W. Prager. Compatibility of approximate solution of linear equations with given error bounds for coe cients and right-hand sides. Numerische Mathematik, 6:405–409, 1964. J. R. Rice. A theory of condition. SIAM Journal on Numerical Analysis, 3(2):287–310, 1966. J. L. Rigal and J. Gaches. On on the compatibility of a given solution with the data of a linear system. Journal of the Association of Computing Machinery, 14(3):543–548, 1967. W. Gautschi. Questions of numerical condition related to polynomials. In C. De Boor and G. H. Golub, editors, Recent Advances in Numeerical Analysis, pages 45–72, New York, 1978. University of Wisconsin Mathematics Research Center, Academic Press. Proceedings of a Symposium May 22–24, 1978. R. D. Skeel. Scaling for numerical stability in Gaussian elimination. Journal of the Association for Computing Machinery, 26(3):494–526, July 1979. 5

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Outline Condition Number History Condition Number Background Condition Number Formulas Inde nite Linear Least Squares Discussion

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Usual ApproachNumerical problem data y∈ Rm solutions x∈ Rn true solution x0 for data y0 Derive ad hoc backward error bound x x0≤ C y y0+···

Condition number is coe cient in boundχ(y0)= C What is wrong with this? (Wilkinson 1963)7

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Condition Number De nitionNumerical problem data y∈ Rm solutions x∈ Rn solution branch f: Rm→ Rn through x0= f (y0) Condition number isχ(y0)= lim supy→y0

f (y) f (y0) y y0

Depends on solution branch and norms (Rice 1966, Gautschi 1978, Skeel 1979)8

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldstine

Derivative and SharpnessIf f is (Fr´chet) di erentiable at y0 eχ(y0)= Df (y0) This is the smallest possible coe cient in f (y) f (y0)≤χ(y0) y y0+ o ( y y0 )

Derivative gives sharp error bounds lim sup derivative sharp Seldom proved in textbooks9

backward error bounds 1936 Wittmeyer backward errors 1947 von Neumann and Goldsti …… 此处隐藏：6257字，全部文档内容请下载后查看。喜欢就下载吧 ……