An example in two dimensions ), no solutions Consider the system of 3
equations and 2 unknowns ( and ), which is overdetermined because 3 > 2, and which corresponds to Diagram #1: \begin{align} Y&=-2X-1\\ Y&=3X-2\\ Y&=X+1. \end{align} There is one solution for each pair of linear equations: for the first and second equations (0.2, −1.4), for the first and third (−2/3, 1/3), and for the second and third (1.5, 2.5). However, there is no solution that satisfies all three simultaneously. Diagrams #2 and 3 show other configurations that are inconsistent because no point is on all of the lines. Systems of this variety are deemed
inconsistent. The only cases where the overdetermined system does in fact have a solution are demonstrated in Diagrams #4, 5, and 6. These exceptions can occur only when the overdetermined system contains enough
linearly dependent equations that the number of independent equations does not exceed the number of unknowns. Linear dependence means that some equations can be obtained from linearly combining other equations. For example,
Y =
X + 1 and 2
Y = 2
X + 2 are linearly dependent equations because the second one can be obtained by taking twice the first one.
Matrix form Any system of linear equations can be written as a
matrix equation. The previous system of equations (in Diagram #1) can be written as follows: \begin{bmatrix} 2 & 1 \\ -3 & 1 \\ -1 & 1 \\ \end{bmatrix} \begin{bmatrix} X \\ Y \end{bmatrix} = \begin{bmatrix} -1 \\ -2 \\ 1 \end{bmatrix} Notice that the rows of the
coefficient matrix (corresponding to equations) outnumber the columns (corresponding to unknowns), meaning that the system is overdetermined. The
rank of this matrix is 2, which corresponds to the number of
dependent variables in the system. A linear system is consistent
if and only if the coefficient matrix has the same rank as its
augmented matrix (the coefficient matrix with an extra column added, that column being the column vector of constants). The augmented matrix has rank 3, so the system is inconsistent. The
nullity is 0, which means that the
null space contains only the zero vector and thus has no
basis. In
linear algebra the concepts of
row space,
column space and
null space are important for determining the properties of matrices. The informal discussion of constraints and
degrees of freedom above relates directly to these more formal concepts.
Homogeneous case The homogeneous case (in which all constant terms are zero) is always consistent (because there is a trivial, all-zero solution). There are two cases, depending on the number of linearly dependent equations: either there is just the
trivial solution, or there is the trivial solution plus an infinite set of other solutions. Consider the system of linear equations:
Li = 0 for 1 ≤
i ≤
M, and variables
X1,
X2, ...,
XN, where each
Li is a weighted sum of the
Xis. Then
X1 =
X2 = ⋯ =
XN = 0 is always a solution. When
M i=
ci for 1 ≤
i ≤
M, in variables
X1,
X2, ...,
XN the equations are sometimes linearly dependent; in fact the number of linearly independent equations cannot exceed
N+1. We have the following possible cases for an overdetermined system with
N unknowns and
M equations (
M>
N). •
M =
N+1 and all M equations are
linearly independent. This case yields no solution. Example:
x = 1,
x = 2. •
M >
N but only
K equations (
K A \mathbf x = \mathbf b, the least squares formula is obtained from the problem \min_{\mathbf x}\lVert A \mathbf x - \mathbf b \rVert, the solution of which can be written with the
normal equations, \mathbf x = \left(A^{\mathsf{T}}A\right)^{-1}A^{\mathsf{T}}\mathbf b, where \mathsf{T} indicates a
matrix transpose,
provided \left(A^{\mathsf{T}}A\right)^{-1} exists (that is, provided
A has full
column rank). With this formula an approximate solution is found when no exact solution exists, and it gives an exact solution when one does exist. However, to achieve good numerical accuracy, using the
QR factorization of
A to solve the least squares problem is preferred.
Using QR factorization The
QR decomposition of a (tall) matrix A is the representation of the matrix in the product form, : A=QR , where Q is a (tall) semi-orthonormal matrix that spans the
range of the matrix A, and where R is a (small) square right-triangular matrix. The solution to the problem of minimizing the norm \| A x - b \|^2 is then given as : x = R^{-1}Q^T b , where in practice instead of calculating R^{-1} one should do a run of
backsubstitution on the right-triangular system : R x = Q^T b .
Using Singular Value Decomposition The
Singular Value Decomposition (SVD) of a (tall) matrix A is the representation of the matrix in the product form, : A=USV^T , where U is a (tall) semi-orthonormal matrix that spans the
range of the matrix A, S is a (small) square
diagonal matrix with non-negative singular values along the diagonal, and where V is a (small) square orthonormal matrix. The solution to the problem of minimizing the norm \| A x - b \|^2 is then given as : x = VS^{-1}U^T b . == Overdetermined nonlinear systems of equations ==