Linear equations

A system of m equations in n unknowns

can be written in matrix notation as

with the coefficient matrix:

We have to distinguish the following three cases:

overdetermined	exactly determined	underdetermined
m>n	m = n	m < n

Such systems can be consistent and have solutions, or inconsistent and then have no solution, as shown in the following figure representing three equations with three unknowns (three planes). The two systems in the top row are consistent: system a has one point as the unique solution and system b has all points of a straight line as solutions. The three systems in the bottom line (c, d, e) are inconsistent and have no solution.

An underdetermined system (m < n) does not have a unique solution; it can be consistent with infinitely many solutions or inconsistent, with no solution, as can be seen in the above picture. If one removes in the above picture one plane, then all systems will have infinitely many solutions except for system c, which has no solution.

In the case of more equations than unknowns (m > n) the system is usually inconsistent and does not have any solution. Adding more planes to the plots in the above picture could leave the systems a and b consistent only if they pass exactly through the intersecting point or line. In some inconsistent (overdetermined) cases, approximate solutions can be found, if additional criteria are introduced (

Error creating thumbnail: Unable to save thumbnail to destination

Fitting).

To solve Ax = b, one can choose between many different methods depending on A. If A

is

	Error creating thumbnail: Unable to save thumbnail to destination upper (lower) triangular	:	backward (forward) substitution
	Error creating thumbnail: Unable to save thumbnail to destination symmetric and positive definite	:	Error creating thumbnail: Unable to save thumbnail to destination Cholesky Decomposition
	Error creating thumbnail: Unable to save thumbnail to destination not triangular	:	Error creating thumbnail: Unable to save thumbnail to destination Gaussian Elimination
	Error creating thumbnail: Unable to save thumbnail to destination square and many right sides	:	Error creating thumbnail: Unable to save thumbnail to destination LU Decomposition
	Error creating thumbnail: Unable to save thumbnail to destination non square	:	Error creating thumbnail: Unable to save thumbnail to destination QR Decomposition
	Error creating thumbnail: Unable to save thumbnail to destination any matrix (e.g. ill-conditioned)	:	Error creating thumbnail: Unable to save thumbnail to destination Singular Value Decomposition.

The computing time increases in the above order. The advantage of orthogonalization methods (QR and SVD) is that they can be applied to all systems, producing stable solutions without accumulation of rounding errors (see Golub89).