Skip to main content

Norms, Conditioning, Iterative Methods, and Method Choice

What This Concept Is​

A vector norm is nonnegative, zero only on the zero vector, absolutely homogeneous and satisfies the triangle inequality. The induced matrix norm measures maximum stretch. In particular, ||A||∞ is the maximum absolute row sum; ||A||2 is the largest singular value. Frobenius norm measures the square root of total squared entries. State the norm when reporting an error.

For nonsingular square A, kappa(A)=||A|| ||A^-1|| measures worst-case relative sensitivity of a solve under a specified perturbation model. For fixed A and nonzero b, a perturbation delta-b gives ||delta-x||/||x|| <= kappa(A)*||delta-b||/||b||. This is a bound, not a prediction that every perturbation attains it.

For an approximate solution x-hat, define r=b−A*x-hat. Forward error compares x-hat with the true x. A normwise backward-error measure is eta=||r||/(||A||*||x-hat||+||b||): it measures a relative perturbation to the supplied problem that can explain the computed answer. A small eta does not guarantee a small forward error when the problem is sensitive.

Why It Matters Here​

An exact rational model separates algebra from rounding. Floating arithmetic introduces representation and algorithmic error. Measurement uncertainty exists even with exact arithmetic. Truncation and regularization deliberately change the problem. Keep these four effects separate in every report.

Concrete Examples​

For A=[[1,1],[1,1.0001]], b=(2,2), the exact solution is (2,0). Changing b to (2,2.0001) gives (1,1). In the infinity norm the relative input change is 1/20000 and the relative solution change is 1/2. The exact infinity-norm condition number is 40004.0001. A residual of zero for either supplied system does not resolve uncertainty about which right-hand side is correct.

Take A=diag(1,0.001), b=(1,0.001), x-hat=(1,0). The relative residual is 0.001, but the relative forward error is one in the infinity norm. Multiplying residual by kappa=1000 gives the bound one. Conversely, epsilon*I has condition number one for nonzero epsilon despite a tiny determinant.

Common Confusion / Misconceptions​

  • A condition number near 10^k suggests possible loss of roughly k decimal digits under typical backward-error assumptions. It does not establish the actual digits of every computed solution or a universal precision cutoff.
  • Stable algorithms control backward error under stated conditions; they do not eliminate data uncertainty. Higher precision or refinement may reduce arithmetic error without recovering information absent from measurements.
  • A Hilbert matrix is a useful sensitivity example, not a fixed-size rule that every solve above a certain dimension is meaningless. Record b and the precision.
  • Choosing an L1 objective reduces the quadratic penalty on large residuals; it does not simply ignore every outlier or solve high-leverage contamination.
  • Preconditioning is a method-specific transformation with setup/apply costs. It is not always beneficial, and a generic left preconditioner can destroy the symmetry assumptions needed by an ordinary CG implementation.

How To Use It​

  1. State matrix shape, rank assumptions, field, norm, units and desired accuracy.
  2. For a general nonsingular square system, consider pivoted LU; for SPD, Cholesky; for full-column-rank least squares, QR; for rank deficiency, an appropriate rank-revealing method or SVD with an explicit cutoff.
  3. For large sparse systems, compare storage and fill-in against iterative methods. A sparse matrix-vector product costs order nnz(A), but a complete iteration can also include orthogonalization, preconditioning and growing storage; GMRES is an example where these costs matter.
  4. Check convergence assumptions. Jacobi is not guaranteed by SPD alone. Standard CG assumes SPD; a raw connected graph Laplacian is singular because it annihilates the all-ones vector. Ground a vertex or work on a justified constrained subspace before applying the SPD formulation.
  5. Use a relative and absolute stopping policy appropriate to the application, including b=0. Report iteration limits and nonconvergence. Residual tests need conditioning context before being treated as solution-error guarantees.
  6. Estimate sensitivity at a cost appropriate to the problem. A full SVD just to obtain a condition number may cost more than an estimator or structured bound.
  7. If regularizing or changing units, state the transformed model and verify its effect on the required output. Benchmark only with recorded hardware, precision, sizes and reproducible fixtures.

Check Yourself​

  1. Derive the fixed-A relative error bound using delta-x=A^-1*delta-b.
  2. Explain why a small scaled residual and a large solution change can coexist.
  3. Why does centering/scaling a data set change the meaning of some model choices?
  4. Why does CG need more than “the matrix came from a graph”?
  5. Which costs beyond matrix-vector products occur in an iterative method?

Mini Drill or Application​

Complete P16–P20, then the numerical experiments. Predict the near-parallel solve before executing the exact diagnostic. Compare it with diag(1,0.001), and separate uncertainty from rounding in your explanation.

Read This Only If Stuck​

Use the bounded reading guide and the Strang book index. The book link opens an index; find the named topic in your edition, read a small section and reconstruct one argument with the book closed.

Scaling and sensitivity are part of the interface​

If A and b are both multiplied by a nonzero scalar, the solution and relative condition number stay the same, while the raw residual changes scale. This is why an absolute residual alone is a weak acceptance criterion. State the units of each column and whether a coefficient perturbation matters in those units.

Changing units can also change a ridge penalty unless the penalty is transformed consistently. Report a regularized model as a changed objective, not a numerical repair that leaves every scientific interpretation intact. Transfer: P16–P20, the sensitivity report and the project decision memo.

After an independent attempt, use practice feedback and model contracts to check your reasoning.