Overdetermined system
[1][citation needed] An overdetermined system is almost always inconsistent (it has no solution) when constructed with random coefficients.
The terminology can be described in terms of the concept of constraint counting.
Each equation introduced into the system can be viewed as a constraint that restricts one degree of freedom.
For every variable giving a degree of freedom, there exists a corresponding constraint.
The overdetermined case occurs when the system has been overconstrained — that is, when the equations outnumber the unknowns.
Consider the system of 3 equations and 2 unknowns (X and Y), which is overdetermined because 3 > 2, and which corresponds to Diagram #1:
Diagrams #2 and 3 show other configurations that are inconsistent because no point is on all of the lines.
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.
For example, Y = X + 1 and 2Y = 2X + 2 are linearly dependent equations because the second one can be obtained by taking twice the first one.
The previous system of equations (in Diagram #1) can be written as follows:
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.
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.
The informal discussion of constraints and degrees of freedom above relates directly to these more formal concepts.
The homogeneous case (in which all constant terms are zero) is always consistent (because there is a trivial, all-zero solution).
But with M ≥ N the number of independent equations could be as high as N, in which case the trivial solution is the only one.
These results may be easier to understand by putting the augmented matrix of the coefficients of the system in row echelon form by using Gaussian elimination.
Putting it another way, according to the Rouché–Capelli theorem, any system of equations (overdetermined or otherwise) is inconsistent if the rank of the augmented matrix is greater than the rank of the coefficient matrix.
If, on the other hand, the ranks of these two matrices are equal, the system must have at least one solution.
The solution is unique if and only if the rank equals the number of variables.
All exact solutions can be obtained, or it can be shown that none exist, using matrix algebra.
See System of linear equations#Matrix solution.
The method of ordinary least squares can be used to find an approximate solution to overdetermined systems.
exists (that is, provided A has full column rank).
However, to achieve good numerical accuracy, using the QR factorization of A to solve the least squares problem is preferred.
one should do a run of backsubstitution on the right-triangular system The Singular Value Decomposition (SVD) of a (tall) matrix
is then given as In finite dimensional spaces, a system of equations can be written or represented in the form of
[5][6] As an effective method for solving overdetermined systems, the Gauss-Newton iteration locally quadratically converges to solutions at which the Jacobian matrices of
