In mathematics, a system of linear equations is considered overdetermined if there are more equations than unknowns.The terminology can be described in terms of the concept of counting constants. Each unknown can be seen as an available degree of freedom. Each equation introduced into the system can be viewed as a constraint that restricts one degree of freedom.
Therefore the critical case occurs when the number of equations and the number of independent variables are equivalent. For every degree of freedom, there exists a corresponding restraint. The overdetermined case occurs when the system has been overconstrained. i.e. The number of equations outnumbers the number of the unknowns.
Consider the system of 3 equations and 2 unknowns (x1 and x2)
Note: equations above correspond to picture #1 such that x1=x and x2=y in the Cartesian coordinate plane
There are three "solutions" to the system as can be determined from the graph's intersections, one for each two linear equations. between one and two (0.2,-1.4), between one and three (-2/3,1/3), between two and three (1.5,2.5). However there is no solution that satisfies all three simultaneously.Systems of this variety are deemed inconsistent.
The only case where the overdetermined system does in fact have a solution is demonstrated in pictures four, five, and six. These exceptions occur when the overdetermined set contains linearly dependent equations. Linear dependence means that the elements of a set can be described in terms of existing equations. For example y=x+1 and 2y=2x+2 are linearly dependent equations.
Any system of linear equations can be written as a matrix equation. The previous system of equations can be written as follows:
Notice that the number of rows outnumber the number of columns. 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 relate directly to these more formal concepts.
The homogeneous case is always consistent (because there is a trivial, all-zero solution). There are two cases, in rough terms: there is just the trivial solution, or the trivial solution plus an infinite set of solutions, of nature determined by the number of linearly dependent equations.
Consider the system of linear equations:
is always a solution. When
the system is underdetermined and there are always further solutions. In fact the dimension of the space of solutions is always at least
For M ≥ N, there may be no solution other than all values being 0. There will be other solutions just when the system of equations has enough dependencies (linearly dependent elements), so that the number of effective constraints is less than the apparent number M; more precisely the system must reduce to at most N − 1 equations. All we can be sure about is that it will reduce to at most N.
the equations Li are sometimes linearly dependent. These dependent equations (often described in terms of vectors) lead to three possible cases for an overdetermined system.
Note:(*Equations and unknowns can correspond to the rows and columns of a matrix respectively)
The discussion is more convincing, perhaps, when translated into the geometric language of intersecting hyperplanes. The homogeneous case applies to hyperplanes through a given point, taken as origin of coordinates. The inhomogeneous case is for general hyperplanes, which may therefore exhibit parallelism or intersect. A sequence of hyperplanes
gives rise to intersections of the first k, which are expected to drop in dimension 1 each time. If M > N, the dimension of the ambient space, we expect the intersection to be empty, and this is precisely the overdetermined case.
The method of least squares can be used to find an approximate solutions to overdetermined systems.For the system , the least squares formula can be written with this formula an approximate solution is found.
The concept can also be applied to more general systems of equations, such as partial differential equations.