Solving Linear Systems Numerically

Linear Systems at Scale

Solving $A\mathbf{x} = \mathbf{b}$ is one of the most common tasks in scientific computing — arising in simulations, data fitting, and optimization, often with thousands or millions of unknowns. The theory (Unit 3) says to use Gaussian elimination; making it work reliably at scale is the numerical challenge.

The direct method row-reduces $A$ to triangular form and back-substitutes, at a cost of about $\frac{2}{3}n^3$ operations for an $n \times n$ system — cubic, so doubling $n$ multiplies the work eightfold. For very large or sparse systems, iterative methods (Jacobi, Gauss–Seidel, conjugate gradient) instead refine an approximate solution step by step, often far cheaper.

A crucial numerical refinement is pivoting. Plain Gaussian elimination divides by the pivot element; if a pivot is zero, it fails, and if a pivot is merely small, dividing by it amplifies round-off error catastrophically. Partial pivoting — swapping rows to put the largest available entry on the pivot — avoids both, making the elimination numerically stable. It is essential in practice, not optional.

Even with a perfect algorithm, some systems are inherently hard. The condition number of $A$ measures how sensitive the solution is to small changes in $A$ or $\mathbf{b}$:

• A well-conditioned system (small condition number) has a solution robust to input errors.
• An ill-conditioned system (large condition number) has a solution that swings wildly with tiny input changes — geometrically, its equations are nearly parallel, so their intersection point is poorly determined.

For an ill-conditioned system, no algorithm can deliver an accurate answer from imprecise data — the problem itself amplifies error. Recognizing conditioning tells you whether a computed solution can be trusted.

Common pitfall: blaming a wildly wrong solution on the algorithm when the problem is ill-conditioned. A large condition number means the solution is intrinsically hyper-sensitive to input error — nearly parallel equations whose intersection shifts enormously with tiny data changes. Even a perfect, stable solver cannot rescue an ill-conditioned system from imprecise inputs; the error lives in the problem, not the method. (And use pivoting — dividing by a small pivot is a self-inflicted instability.)

Two nearly parallel lines whose accent intersection point slides far along the lines when one is nudged slightly, beside two perpendicular lines whose intersection barely moves — ill- versus well-conditioning.

$$\text{large condition number} \Rightarrow \text{sensitive solution}$$