Skip to the lesson
FixTheRobot Explore Robotics / Linear Algebra / M5 Least Squares and Numerical Methods / M5-T8

Linear Algebra · Theory · M5

M5-T8 — Numerical Conditioning and Stability

The condition number says how much a problem magnifies errors. Knowing it tells you how many digits of an answer you can trust.

  • Lesson 8 of 8
  • Module 5: Least Squares and Numerical Methods
  • Least squares
  • About 9 minutes to read

Every sensor reading has noise and every computer rounds. Whether those small errors stay small or explode depends on the problem, and the number that measures it is the condition number. This lesson closes the module by separating two questions that are easily confused: is the problem sensitive, and is the algorithm careful? It also tells you how many digits to believe.

Learning objectives

After this lesson, you should be able to:

  • Define the condition number κ(A) = σmax/σmin and interpret it as the worst-case error amplification.
  • Derive the bound relative error in x ≤ κ(A) × relative error in b for A x = b.
  • Distinguish ill-conditioned problems from unstable algorithms with examples from this module.
  • Use the condition number to predict the number of correct digits and to decide on a method.

Introduction and motivation

A calibration that returns a rotation with the right shape but wrong values, a pose estimate that jumps by metres between frames, an inverse-kinematics routine that commands absurd joint speeds near a singularity: each is a conditioning story. Learning to measure it, and to tell whether the problem or the code is at fault, is among the most practical skills in numerical robotics. Everything in this module (QR instead of normal equations, regularisation, weights) is a response to conditioning.

The intuition

Two lines in the plane cross at one point. If they cross at a healthy angle, shifting one line a little moves the crossing point a little. If they are almost parallel, the same small shift slides the crossing point a long way. The solution of the system is the crossing point; the data (the right-hand side) set the position of the lines. A well-conditioned problem is the healthy-angle case, an ill-conditioned one is the nearly parallel case.

Interactive figure. Two lines meet at an angle. Shifting one line slightly moves the intersection. When the lines are nearly parallel a tiny shift moves the intersection a long way. The readout gives the condition number and the measured amplification. This figure needs JavaScript to be interactive.

Slide the angle between the two lines toward zero. The same small shift of line 2 (the orange dashed one) moves the solution further each time. The condition number in the readout measures this amplification.
Problem versus algorithmTwo separate sources of error. A well-conditioned problem solved with a stable algorithm gives an accurate answer. An ill-conditioned problem amplifies even the smallest data error, whatever algorithm is used. A well-conditioned problem solved with an unstable algorithm, such as classical Gram-Schmidt, can also give a bad answer.well-conditioned problemsmall data error → small answer error ill-conditioned problemsmall data error → large answer error stable algorithm: error ≈ κ · εunstable algorithm: can be much worse no algorithm can fix it:the question itself is sensitive answer error ≲ κ(A) × (relative error in the data) ε ≈ 10⁻¹⁶ in double precision
Conditioning belongs to the problem; stability belongs to the algorithm. Answer error is bounded by the condition number times the data error.

Geometric and physical interpretation

Geometric view. The matrix A maps the unit circle (or sphere) of inputs to an ellipse (ellipsoid) of outputs. The longest axis has length σmax and the shortest σmin. Solving A x = b reverses the map: a change in b along the short axis needs a change in x that is 1/σmin times as large. The condition number κ = σmax/σmin is the eccentricity of that ellipse: how squashed the map is. Physical view. A nearly squashed measurement map means that two quite different states give almost the same sensor readings. Noise cannot be told apart from a large change of the state in the squashed direction.

The mathematics

σmax, σmin
the largest and smallest singular values of A.
κ(A)
the 2-norm condition number σmax/σmin ≥ 1 (infinite for a singular matrix).
ε
machine precision: about 1.1 × 10⁻¹⁶ for double precision.

Definition

κ(A) = σmax / σmin  =  ‖A‖ ‖A⁻¹‖          κ(Q) = 1 for orthogonal Q

What it means. The ratio of the largest to the smallest stretch of the map. It equals 1 for orthogonal matrices (no direction is stretched more than another) and grows as the map squashes space.

Error amplification

A x = b,   A (x + δx) = b + δb   ⇒   ‖δx‖/‖x‖  ≤  κ(A) · ‖δb‖/‖b‖

What it means. A relative error in the data can be amplified by at most κ(A) in the answer. The bound is attained for the worst direction of the error.

The digits you can trust

correct digits of x  ≈  16 − log10 κ(A)        (double precision, stable algorithm)

What it means. Rounding alone (relative error about 10⁻¹⁶) is amplified by κ. With κ = 10⁶ expect about ten correct digits; with κ = 10¹⁶ expect none.

Least squares and the squared condition number

κ(AᵀA) = κ(A)²        QR: the solve faces κ(A);  normal equations: κ(A)²

What it means. Forming AᵀA squares the problem sensitivity. For a least-squares problem with a large residual the sensitivity also contains a κ² term, so conditioning matters even more.

κ = σmax/σmin measures how much a problem amplifies errors: answer error ≲ κ × data error. Algorithms can add error on top; QR and pivoting keep them near the unavoidable amount.

Step-by-step derivation: the sensitivity bound, and the 2 × 2 line example

The bound. Let A x = b and A(x + δx) = b + δb. Subtracting gives A δx = δb, so δx = A⁻¹δb.

  1. Take norms: ‖δx‖ ≤ ‖A⁻¹‖ ‖δb‖, using that a matrix cannot stretch a vector by more than its norm.
  2. From A x = b: ‖b‖ ≤ ‖A‖ ‖x‖, so 1/‖x‖ ≤ ‖A‖/‖b‖.
  3. Divide: ‖δx‖/‖x‖ ≤ ‖A⁻¹‖ ‖δb‖ · ‖A‖/‖b‖ = ‖A‖‖A⁻¹‖ · ‖δb‖/‖b‖ = κ(A) · ‖δb‖/‖b‖.
  4. For the 2-norm, ‖A‖ = σmax and ‖A⁻¹‖ = 1/σmin, so κ = σmax/σmin.

The two-line example. Let line 1 be x = 1 (unit normal (1, 0)) and line 2 have unit normal (cos α, sin α): x cos α + y sin α = c₂. The solution has y = (c₂ − cos α)/sin α. A shift ε of c₂ changes y by ε/sin α: an amplification of 1/sin α, which is huge for small α. The matrix of unit rows has singular values √(1 + cos α) and √(1 − cos α), so κ = √((1 + cos α)/(1 − cos α)) = cot(α/2), and for small α this is about 2/α, consistent with the observed 1/sin α ≤ κ.

Why the normal equations square it. The eigenvalues of AᵀA are σi², so κ(AᵀA) = σmax²/σmin² = κ(A)².

Problem versus algorithm. A backward stable algorithm returns the exact answer to a slightly perturbed problem (perturbation of relative size about ε). The bound above then says its answer error is about κ ε: as good as can be hoped. An unstable algorithm (classical Gram-Schmidt on the Hilbert matrix; elimination without pivoting) has error much larger than κ ε, which is a defect of the method, not of the problem.

A worked example: conditioning in numbers

  • Rotation. κ(R(θ)) = 1: no amplification, whatever the angle.
  • Scaling. diag(100, 1) has κ = 100. A relative error of 10⁻³ in the second component of the data can become a relative error up to 0.1 in the answer.
  • Nearly parallel lines. For lines at an angle of 12°, κ = cot(6°) = 9.51; at 1°, κ = cot(0.5°) = 114.6. A shift of 0.1 in c₂ moves the crossing point by 0.1/sin 12° = 0.48 in the first case and 0.1/sin 1° = 5.7 in the second.
  • The ill-conditioned matrix of the last lesson. [[1, 1], [1, 1.001]] has singular values 2.0005 and 0.0005, so κ = 4002. A data change of 0.001 gave an answer change of 1.4 (a relative change of 100% for a data change of 0.05%): consistent with the bound.
  • Digits. The Hilbert matrix of size 8 has κ = 1.5·10¹⁰: expect about 16 − 10 = 6 correct digits from a stable solver, and fewer from the normal equations whose conditioning is κ² = 2.3·10²⁰, beyond the precision of double arithmetic.

Robotics application

Calibration quality. Compute κ of the calibration design matrix before collecting data and again afterwards. A value above about 10⁴ means the data barely excite some parameter combination: the calibration will be unreliable however long you run it. Choose calibration motions to minimise κ (rotate about all axes, not one).

Manipulator Jacobians. The condition number of the Jacobian is a measure of dexterity: near 1 the arm moves its hand equally easily in all directions; large near a singularity. Many planners keep κ(J) below a threshold. Module 8 uses this directly.

Localisation geometry. The condition number of the matrix of directions to landmarks (or to satellites, via dilution of precision in GNSS) measures how well the geometry determines position. A cluster of landmarks in one direction is the nearly-parallel-lines case. The UAV track discusses it for GNSS positioning.

Choosing a solver. Use κ to decide between normal equations (small κ), QR (moderate), SVD with truncation (large, or unknown rank). The SLAM track's nonlinear least squares lesson relies on damped iterations because the linearised problem can be ill-conditioned.

Engineering implications and limitations

Practical rules

  • Compute and log the condition number. A singular-value decomposition of a small matrix is cheap. For large sparse problems, estimate it (a condition estimator, or the ratio of extreme diagonal entries of a factor).
  • Digits budget: expect about 16 − log₁₀ κ correct digits (double). Compare to the accuracy you need; if κ·ε is larger than your tolerance, change the problem (more data, better geometry, regularisation), not the code.
  • Fix badly scaled data first. Centre and normalise columns and use consistent units; many large condition numbers are artefacts of scaling and vanish when you rescale (column scaling can change κ a lot, though it cannot remove true near-dependence).
  • Prefer orthogonal factorisations (QR, SVD) and pivoting; avoid forming AᵀA, explicit inverses and determinant tests.
  • Do not trust tiny residuals. A backward-stable solver returns a small residual even for ill-conditioned problems, while the answer itself can be wrong by κ times the data error. Small residual does not imply small error in x.

Limits

The condition number gives a worst-case bound for a linear system under norm-wise perturbations. Actual errors are often smaller, and for specific structure (a few sensitive directions of no interest to you) the practical sensitivity can be lower. Conversely, nonlinear problems have conditioning that depends on where you evaluate them.

Common misconceptions

“A small determinant means ill-conditioned.”

Conditioning is about the ratio of singular values, not the determinant. 0.01·I has a tiny determinant and κ = 1; a matrix with columns (1, 0) and (1, 10⁻¹⁰) has a determinant of 10⁻¹⁰ and κ near 10¹⁰.

“If the residual is tiny, the answer is accurate.”

A stable solver always gives a small residual. The error in x can still be κ times larger than the error in the data.

“A better algorithm can fix an ill-conditioned problem.”

It can only avoid adding extra error. If κ is 10¹⁵, no algorithm in double precision can recover the answer to more than about one digit.

“Conditioning only matters for huge matrices.”

A 2 × 2 system with nearly parallel lines is already ill-conditioned (the figure shows it). It is a question of geometry, not size.

Engineering takeaways

  1. κ(A) = σmax/σmin measures the worst-case amplification of relative errors: ‖δx‖/‖x‖ ≤ κ ‖δb‖/‖b‖.
  2. Conditioning belongs to the problem; stability belongs to the algorithm. Stable algorithms give error about κ ε.
  3. Expect about 16 − log₁₀ κ correct digits in double precision.
  4. κ(AᵀA) = κ(A)²: use QR, not normal equations, when κ is large.
  5. Improve conditioning by scaling, better data geometry, regularisation or more informative measurements.

References and further reading

Primary papers and authoritative documentation.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

A 2 × 2 system has singular values 5 and 0.0005. Compute κ and estimate how many correct digits to expect in double precision.

Explanation

κ = 5/0.0005 = 10⁴. Expect about 16 − 4 = 12 correct digits from a stable method. A data error of relative size 10⁻⁶ could change the answer by up to 10⁴ × 10⁻⁶ = 1%, so the sensor accuracy, not the arithmetic, is what matters in practice.

Question 2

A colleague reports “the solver’s residual is 10⁻¹⁵, so the calibration is accurate to 15 digits”. What is wrong with this reasoning?

Explanation

A backward-stable solver always returns a tiny residual, even for ill-conditioned problems. The error in the parameters can be as large as κ times the relative error in the data (or rounding): if κ = 10⁸, the parameters may be accurate to only a few digits even though the residual is minute. Check the condition number (and the parameter uncertainty), not the residual alone.

Question 3

A GNSS receiver sees four satellites all clustered near one direction in the sky. Explain, using conditioning, why its position estimate is poor even though each range measurement is accurate.

Explanation

The rows of the measurement matrix are the unit directions to the satellites; if they are nearly parallel, the matrix is nearly singular (like the nearly parallel lines in the figure). Its condition number is large, so small range errors are amplified into large position errors, especially along the line of sight. This is the dilution of precision; good geometry (satellites spread across the sky) gives a condition number near 1.

What’s next

Module 5 has taught you to find the best answer, to compute it accurately, and to know how far to trust it. Module 6 introduces the tool that reveals all of this at once: the singular value decomposition.

Practice this lesson

LiDAR Plane Fitting

Fit the ground plane to a noisy LiDAR scan, find out why a naive fit fails on a wall, and fix it with a stable method.

Next lesson

M6-T1 — Eigenvalues and Eigenvectors

Find the directions a matrix only stretches, and use eigenvalues to read scaling and stability.

Nothing below is required to finish this lesson.