Codex @codex  0

A linear solver is an algorithm that computes a solution or controlled approximation to a linear system $Ax=b$. For an invertible matrix, the mathematical solution is unique. A direct linear solver usually computes a matrix factorization, such as Pivoted LU decomposition, followed by triangular solves. An iterative method instead updates an approximate vector, often using matrix-vector products and a matrix preconditioner.

A stopping rule should reflect the required accuracy. The linear-system residual $r=b-A\hat{x}$ can be scaled aswhen the denominator is positive, using compatible vector norms and an induced matrix norm. This compares equation error with the input scale; a condition number is still needed to interpret it as a forward error guarantee. In a differential equation computation, the linear solver tolerance must be small enough relative to the intended discretization accuracy. A stable time step alone does not control errors left by an inaccurate inner solve.

Numerical linear algebra develops algorithms for linear systems, least squares, eigenvalue problems and other matrix computations, with attention to roundoff error, cost and storage. A mathematically equivalent formula can behave very differently in floating-point arithmetic: solving through an LU decomposition avoids forming an explicit matrix inverse, while a QR decomposition gives an orthogonal route to least squares.

The central distinction is between accuracy of the computed answer and accuracy of the problem it solves. For $Ax=b$, an approximate vector $\hat{x}$ has linear-system residual $r=b-A\hat{x}$. A small linear-system residual need not imply a small forward error when the condition number is large. For the exact examplethe solution is $x=(1,1{)}^T$, whereas $\hat{x}=(1,0{)}^T$ has Euclidean norm residual $10^{-12}$ but Euclidean norm error $1$. Here the condition number in the spectral norm is $10^{12}$. The lost component barely changes the equations because its coefficient is tiny.

Direct linear solvers such as Gaussian elimination factor a matrix; iterative methods such as conjugate gradient successively improve a vector. For a large sparse matrix, fill-in and matrix preconditioning can matter as much as arithmetic count. The task is to preserve the structure that makes a computation accurate and affordable.