Average condition number for solving linear equations

DOI10.1016/0024-3795(86)90266-1MaRDI QIDQ1082774zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(86)90266-1

zbMATH Keywords

average condition numberdisturbed systemFrobenius normspectral normworst case

Mathematics Subject Classification ID

Conditioning of matrices (15A12) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Numerical computation of matrix norms, conditioning, scaling (65F35)

Review text

This is a statistical consideration of the condition number of a disturbed system of linear equations \(Ax=b\). For a Lebesgue-measure \(\mu\) it is shown, that the average condition number in \(L_ p\) is comparable with the worst case condition number. For the Frobenius norm one gains about \(\log_ 2n+0.9\) bits on the average as compared to the worst case, n being the dimension of the linear system. Beside the Frobenius norm componentwise perturbations and the spectral norm are considered. Finally it is indicated how the result can be extended for perturbations of both A and b.

Recommendations

• Average number of roots of systems of equations
• Condition numbers for a linear function of the solution of the linear least squares problem with equality constraints
• Approximate Solutions of the Linear Equation
• Approximate solution of systems of linear equations†
• A Partial Condition Number for Linear Least Squares Problems
• scientific article; zbMATH DE number 1179597
• Condition number for weighted linear least squares problem
• Solutions to linear equations depending on a parameter
• Partial condition number for the equality constrained linear least squares problem

Cites work

• Complexity theory of numerical linear algebra
• Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average
• scientific article; zbMATH DE number 3183375 (Why is no real title available?)
• scientific article; zbMATH DE number 3473182 (Why is no real title available?)
• scientific article; zbMATH DE number 3567411 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• Iterative Refinement Implies Numerical Stability for Gaussian Elimination

Cited in

(6)

• Condition numbers of random matrices
• Invertibility of random fredholm operators
• Probabilistic analyses of condition numbers
• Extrapolating from Regularised Solutions for Solving Ill-Conditioned Linear Systems in Machine Learning
• Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems
• Stochastic perturbations and smooth condition numbers

This page was built for publication: Average condition number for solving linear equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082774)