Solving Linear Systems Numerically

Linear Systems & Direct Methods

Solving $A\mathbf{x} = \mathbf{b}$ powers simulations and data fitting with millions of unknowns. Theory uses Gaussian elimination, reducing $A$ to triangular form before back-substitution.

The cost is about $\frac{2}{3}n^3$ operations for an $n \times n$ system. Because it is cubic, doubling $n$ multiplies the work eightfold. For huge sparse systems, iterative methods (Jacobi, Gauss-Seidel, conjugate gradient) refine guesses step-by-step instead.

Plain elimination fails on a zero pivot and amplifies round-off error on a small one. Partial pivoting swaps rows to place the largest available entry on the pivot, making the method numerically stable and safe for real-world use.

Conditioning & Pitfalls

Even stable solvers fail if a system is inherently fragile. The condition number of $A$ measures solution sensitivity to input errors.

Common pitfall: Blaming the algorithm when the problem is ill-conditioned. A large condition number means the solution is hyper-sensitive. Even a perfect solver cannot rescue imprecise data; error lives in the problem, not the method.