The conditioning of a problem determines how strongly its solution responds to small changes in the input. A well-conditioned problem produces relatively predictable changes in its solution when the input is perturbed. An ill-conditioned problem can be highly sensitive, so even small measurement or rounding errors may lead to substantial differences in the result. This distinction is particularly important in numerical linear algebra, polynomial evaluation and inverse problems. For example, a linear system with a matrix having a large condition number may produce a solution that is very sensitive to small changes in the matrix or right-hand-side vector.
Well-Conditioned and Ill-Conditioned Problems
Well-conditioned problems are relatively insensitive to small input changes, whereas ill-conditioned problems may amplify small input disturbances into large solution changes.
κ(A) = ‖A‖ ‖A⁻¹‖
Explanation
Variables
| Symbol | Meaning |
|---|---|
κ(A) | Condition number of a nonsingular matrix A under the chosen norm. |
A | A nonsingular matrix. |
A⁻¹ | Inverse of matrix A. |
‖A‖ | A matrix norm. |
Example or application
A linear system whose coefficient matrix has a very large condition number may produce significantly different solutions when its coefficients are changed by a very small amount.
Definition
A well-conditioned problem has relatively low sensitivity to input perturbations, while an ill-conditioned problem has high sensitivity to small input changes.
Purpose
To classify mathematical problems according to their sensitivity and explain the consequences of poor conditioning in numerical calculations.
Importance
Recognizing ill-conditioned problems prevents users from assuming that every inaccurate result is caused by a faulty algorithm. It also guides the selection of higher-precision arithmetic, improved formulations or specialized numerical techniques.
Learning Objectives
Distinguish well-conditioned and ill-conditioned problems.
Understand the role of condition numbers.
Interpret the matrix condition number.
Explain how input errors affect sensitive problems.
Recognize possible strategies for handling ill-conditioning.
Key Concepts
Well-conditioned problem
Ill-conditioned problem
Matrix condition number
Matrix norm
Input sensitivity
Perturbation
Numerical reliability
Working Principle
The sensitivity of a problem is analyzed by measuring how much its solution can change relative to a small change in the input. For nonsingular matrices, a condition number based on matrix norms provides a standard sensitivity measure.
Process
Identify the mathematical problem.
Determine the relevant input and solution quantities.
Choose an appropriate norm or sensitivity measure.
Estimate or calculate the condition number.
Interpret the size of the condition number.
Select a numerical strategy appropriate to the problem's sensitivity.
Applications
Solving linear systems
Inverse problems
Scientific parameter estimation
Numerical optimization
Engineering modelling
Polynomial computation
Worked Example
Problem
Calculate the 1-norm condition number of A = [[1, 0], [0, 2]].
Steps
The inverse is A⁻¹ = [[1, 0], [0, 0.5]].
The matrix 1-norm is the maximum absolute column sum.
‖A‖₁ = max(1, 2) = 2.
‖A⁻¹‖₁ = max(1, 0.5) = 1.
κ₁(A) = ‖A‖₁‖A⁻¹‖₁ = 2 × 1 = 2.
Answer
The 1-norm condition number is κ₁(A) = 2.
Common Misconceptions
An ill-conditioned problem is not necessarily mathematically unsolvable.
A large condition number does not prove that the algorithm is incorrectly implemented.
Changing the algorithm may improve numerical stability but cannot change the inherent conditioning of the original problem without changing its formulation.
Condition numbers depend on the chosen norm and scaling.
Practice Questions
| Question | Answer |
|---|---|
What does a small condition number generally indicate? | The problem is relatively insensitive to small input perturbations. |
Write the matrix condition-number formula for a nonsingular matrix. | κ(A) = ‖A‖‖A⁻¹‖. |
Can a problem be ill-conditioned even if the algorithm is implemented correctly? | Yes. Ill-conditioning is an inherent sensitivity of the mathematical problem. |
Key Takeaway
Condition numbers help determine whether a mathematical problem is naturally sensitive to small input changes, independently of the numerical algorithm used.
Prerequisites
SCI-MAT-014-021
SCI-MAT-014-011
SCI-MAT-004-059
SCI-MAT-004-086
Reference
Trefethen, L. N., and Bau, D. Numerical Linear Algebra.
Higham, N. J. Accuracy and Stability of Numerical Algorithms.
Related Topics
SCI-MAT-014-021
SCI-MAT-014-023
SCI-MAT-014-024
SCI-MAT-014-101
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.