Conserving Confluence Curbs Ill-Condition
Abstract
Certain problems are ill-conditioned, in the sense that their solutions are hypersensitive to small changes in data, only because a slight change in data could cause those solutions to exhibit singular behaviour associated with various kinds of confluence. For example, an over- or under- determined linear system solved by least-squares can be ill-conditioned only if there exists some small perturbations to its matrix which increase its nullity (i.e. diminish its rank); zeros of a polynomial can be ill-conditioned only if their multiplicities can be increased by very small perturbations of the polynomial's coefficients; eigenvalues of a non-Hermitian matrix can be ill- conditioned only if their algebraic multiplicities can be increased by very small perturbations of the matrix. When perturbations constrained to a small neighborhood can be further constrained to maximize confluence, i.e. to maximize nullity (minimize rank) or maximize multiplicity, and when that maximized confluence can be increased again only by perturbations far beyond the small neighborhood, then the slightly perturbed problems exhibit well-conditioned confluent solutions. Beyond these vague statements lie the shadows of numerical methods which may either eliminate ill-condition or, when ill-condition is persistent, illuminate its cause.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 04, 1972
- Accession Number
- AD0766916
Entities
People
- W. Kahan
Organizations
- University of California, Berkeley