Overdetermined system

<h2 id="overdetermined-linear-systems-of-equations">Overdetermined linear systems of equations</h2>
<h3>An example in two dimensions</h3>

Consider the system of 3 <a href="/facts/Equation/pxFzLAVR">equations</a> and 2 unknowns (X and Y), which is overdetermined because 3 > 2, and which corresponds to Diagram #1:

Y
              
              
                
                =
                −
                2
                X
                −
                1
              
            
            
              
                Y
              
              
                
                =
                3
                X
                −
                2
              
            
            
              
                Y
              
              
                
                =
                X
                +
                1.
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}Y&=-2X-1\\Y&=3X-2\\Y&=X+1.\end{aligned}}}

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 <a href="/facts/Consistent_and_inconsistent_equations/vQ5DCd3a">inconsistent</a>.
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 <a href="/facts/Linearly_dependent/8JrHfIIa">linearly dependent</a> 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 2Y = 2X + 2 are linearly dependent equations because the second one can be obtained by taking twice the first one.

<h3>Matrix form</h3>
Any system of linear equations can be written as a <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> equation.
The previous system of equations (in Diagram #1) can be written as follows:

[
            
              
                
                  2
                
                
                  1
                
              
              
                
                  −
                  3
                
                
                  1
                
              
              
                
                  −
                  1
                
                
                  1
                
              
            
            ]
          
        
        
          
            [
            
              
                
                  X
                
              
              
                
                  Y
                
              
            
            ]
          
        
        =
        
          
            [
            
              
                
                  −
                  1
                
              
              
                
                  −
                  2
                
              
              
                
                  1
                
              
            
            ]
          
        
      
    
    {\displaystyle {\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 <a href="/facts/Coefficient_matrix/S5JmDEW6">coefficient matrix</a> (corresponding to equations) outnumber the columns (corresponding to unknowns), meaning that the system is overdetermined. The <a href="/facts/Rank_(linear_algebra)/Yp9b5LK3">rank</a> of this matrix is 2, which corresponds to the number of <a href="/facts/Dependent_variables/dINfzIF2">dependent variables</a> in the system.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> A linear system is consistent <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> the coefficient matrix has the same rank as its <a href="/facts/Augmented_matrix/Ds7y6Myf">augmented matrix</a> (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 <a href="/facts/Kernel_(linear_algebra)/adhGUYa0">nullity</a> is 0, which means that the <a href="/facts/Null_space/adhGUYa0">null space</a> contains only the zero vector and thus has no <a href="/facts/Basis_(linear_algebra)/89IPoN6c">basis</a>.
In <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a> the concepts of <a href="/facts/Row_space/INXbQVNI">row space</a>, <a href="/facts/Column_space/INXbQVNI">column space</a> and <a href="/facts/Null_space/adhGUYa0">null space</a> are important for determining the properties of matrices. The informal discussion of constraints and <a href="/facts/Degrees_of_freedom_(statistics)/fvwKCU86">degrees of freedom</a> above relates directly to these more formal concepts.

<h3>Homogeneous case</h3>
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 <a href="/facts/Trivial_(mathematics)/AqzUxokN">trivial</a> 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 < N the system is underdetermined and there are always an infinitude of further solutions. In fact the dimension of the space of solutions is always at least N − M.
For M ≥ N, there may be no solution other than all values being 0. There will be an infinitude of other solutions only when the system of equations has enough dependencies (linearly dependent equations) that the number of independent equations is at most N − 1. 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.

<h3>Non-homogeneous case</h3>
In systems of linear equations, Li=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).

<ul><li>M = N+1 and all M equations are <a href="/facts/Linearly_independent/8JrHfIIa">linearly independent</a>. This case yields no solution. Example: x = 1, x = 2.</li>
<li>M > N but only K equations (K < M and K ≤ N+1) are linearly independent. There exist three possible sub-cases of this:
<ul><li>K = N+1. This case yields no solutions. Example: 2x = 2, x = 1, x = 2.</li>
<li>K = N. This case yields either a single solution or no solution, the latter occurring when the coefficient vector of one equation can be replicated by a weighted sum of the coefficient vectors of the other equations but that weighted sum applied to the constant terms of the other equations does not replicate the one equation's constant term. Example with one solution: 2x = 2, x = 1. Example with no solution: 2x + 2y = 2, x + y = 1, x + y = 3.</li>
<li>K < N. This case yields either infinitely many solutions or no solution, the latter occurring as in the previous sub-case. Example with infinitely many solutions: 3x + 3y = 3, 2x + 2y = 2, x + y = 1. Example with no solution: 3x + 3y + 3z = 3, 2x + 2y + 2z = 2, x + y + z = 1, x + y + z = 4.</li></ul></li></ul>
These results may be easier to understand by putting the <a href="/facts/Augmented_matrix/Ds7y6Myf">augmented matrix</a> of the coefficients of the system in <a href="/facts/Row_echelon/U9LQHBYq">row echelon</a> form by using <a href="/facts/Gaussian_elimination/23Rvf4ht">Gaussian elimination</a>. This row echelon form is the augmented matrix of a system of equations that is equivalent to the given system (it has exactly the same solutions). The number of independent equations in the original system is the number of non-zero rows in the echelon form. The system is inconsistent (no solution) if and only if the last non-zero row in echelon form has only one non-zero entry that is in the last column (giving an equation 0 = c where c is a non-zero constant). Otherwise, there is exactly one solution when the number of non-zero rows in echelon form is equal to the number of unknowns, and there are infinitely many solutions when the number of non-zero rows is lower than the number of variables.
Putting it another way, according to the <a href="/facts/Rouch%C3%A9%E2%80%93Capelli_theorem/mdkcFrFd">Rouché–Capelli theorem</a>, any system of equations (overdetermined or otherwise) is inconsistent if the <a href="/facts/Rank_(linear_algebra)/Yp9b5LK3">rank</a> of the augmented matrix is greater than the rank of the <a href="/facts/Coefficient_matrix/S5JmDEW6">coefficient matrix</a>. 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. Otherwise the general solution has k free parameters where k is the difference between the number of variables and the rank; hence in such a case there are an infinitude of solutions.

<h3>Exact solutions</h3>
All exact solutions can be obtained, or it can be shown that none exist, using <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix algebra</a>. See <a href="/facts/System_of_linear_equations/fk9CFdgp">System of linear equations#Matrix solution</a>.

<h3>Approximate solutions</h3>
The method of <a href="/facts/Ordinary_least_squares/q7H9k5vM">ordinary least squares</a> can be used to find an approximate solution to overdetermined systems. For the system 
 
 
 
 A
 
 x
 
 =
 
 b
 
 ,
 
 
 {\displaystyle A\mathbf {x} =\mathbf {b} ,}
 
 the least squares formula is obtained from the problem

min
          
            
              x
            
          
        
        ‖
        A
        
          x
        
        −
        
          b
        
        ‖
        ,
      
    
    {\displaystyle \min _{\mathbf {x} }\lVert A\mathbf {x} -\mathbf {b} \rVert ,}

the solution of which can be written with the <a href="/facts/Normal_equations/dKctFUCV">normal equations</a>,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

x
        
        =
        
          
            (
            
              
                A
                
                  
                    T
                  
                
              
              A
            
            )
          
          
            −
            1
          
        
        
          A
          
            
              T
            
          
        
        
          b
        
        ,
      
    
    {\displaystyle \mathbf {x} =\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}\mathbf {b} ,}

where 
 
 
 
 
 
 T
 
 
 
 
 {\displaystyle {\mathsf {T}}}
 
 indicates a <a href="/facts/Matrix_transpose/8wmsagGS">matrix transpose</a>, provided 
 
 
 
 
 
 (
 
 
 A
 
 
 T
 
 
 
 A
 
 )
 
 
 −
 1
 
 
 
 
 {\displaystyle \left(A^{\mathsf {T}}A\right)^{-1}}
 
 exists (that is, provided A has full <a href="/facts/Matrix_rank/Yp9b5LK3">column rank</a>). 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 <a href="/facts/QR_factorization/NswfKLGY">QR factorization</a> of A to solve the least squares problem is preferred.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h4>Using QR factorization</h4>
The <a href="/facts/QR_decomposition/NswfKLGY">QR decomposition</a> of a (tall) matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
 is the representation of the matrix in the product form,

A
        =
        Q
        R
        ,
      
    
    {\displaystyle A=QR,}

where 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
 is a (tall) semi-orthonormal matrix that spans the <a href="/facts/Row_and_column_spaces/INXbQVNI">range</a> of the matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
, and where 
 
 
 
 R
 
 
 {\displaystyle R}
 
 is a (small) square right-triangular matrix.
The solution to the problem of minimizing the norm 
 
 
 
 ‖
 A
 x
 −
 b
 
 ‖
 
 2
 
 
 
 
 {\displaystyle \|Ax-b\|^{2}}
 
 is then given as

x
        =
        
          R
          
            −
            1
          
        
        
          Q
          
            T
          
        
        b
        ,
      
    
    {\displaystyle x=R^{-1}Q^{T}b,}

where in practice instead of calculating 
 
 
 
 
 R
 
 −
 1
 
 
 
 
 {\displaystyle R^{-1}}
 
 one should do a run of <a href="/facts/Backsubstitution/qjXSFMM3">backsubstitution</a> on the right-triangular system

R
        x
        =
        
          Q
          
            T
          
        
        b
        .
      
    
    {\displaystyle Rx=Q^{T}b.}

<h4>Using Singular Value Decomposition</h4>
The <a href="/facts/Singular_Value_Decomposition/8t3v6wk3">Singular Value Decomposition</a> (SVD) of a (tall) matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
 is the representation of the matrix in the product form,

A
        =
        U
        S
        
          V
          
            T
          
        
        ,
      
    
    {\displaystyle A=USV^{T},}

where 
 
 
 
 U
 
 
 {\displaystyle U}
 
 is a (tall) semi-orthonormal matrix that spans the <a href="/facts/Row_and_column_spaces/INXbQVNI">range</a> of the matrix 
 
 
 
 A
 
 
 {\displaystyle A}
 
, 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is a (small) square diagonal matrix with non-negative singular values along the diagonal, and where 
 
 
 
 V
 
 
 {\displaystyle V}
 
 is a (small) square orthonormal matrix.
The solution to the problem of minimizing the norm 
 
 
 
 ‖
 A
 x
 −
 b
 
 ‖
 
 2
 
 
 
 
 {\displaystyle \|Ax-b\|^{2}}
 
 is then given as

x
        =
        V
        
          S
          
            −
            1
          
        
        
          U
          
            T
          
        
        b
        .
      
    
    {\displaystyle x=VS^{-1}U^{T}b.}

<h2 id="overdetermined-nonlinear-systems-of-equations">Overdetermined nonlinear systems of equations</h2>
In finite dimensional spaces, a system of equations can be written or represented in the form of

 
 
 
 
 {
 
 
 
 
 
 f
 
 1
 
 
 (
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 )
 
 
 =
 
 
 0
 
 
 
 
 ⋮
 
 
 ⋮
 
 
 ⋮
 
 
 
 
 
 f
 
 m
 
 
 (
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 )
 
 
 =
 
 
 0
 
 
 
 
 
 
 
 
 {\displaystyle \left\{{\begin{array}{ccc}f_{1}(x_{1},\ldots ,x_{n})&=&0\\\vdots &\vdots &\vdots \\f_{m}(x_{1},\ldots ,x_{n})&=&0\end{array}}\right.}

or in the form of 
 
 
 
 
 f
 
 (
 
 x
 
 )
 =
 
 0
 
 
 
 {\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} }
 
 with

 
 
 
 
 f
 
 (
 
 x
 
 )
 =
 
 [
 
 
 
 
 
 f
 
 1
 
 
 (
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 )
 
 
 
 
 ⋮
 
 
 
 
 
 f
 
 m
 
 
 (
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 )
 
 
 
 
 ]
 
 
 
 
 
 
 and
 
 
 
 
 
 
 0
 
 =
 
 [
 
 
 
 
 0
 
 
 
 
 ⋮
 
 
 
 
 0
 
 
 
 
 ]
 
 
 
 {\displaystyle \mathbf {f} (\mathbf {x} )=\left[{\begin{array}{c}f_{1}(x_{1},\ldots ,x_{n})\\\vdots \\f_{m}(x_{1},\ldots ,x_{n})\end{array}}\right]\;\;\;{\mbox{and}}\;\;\;\mathbf {0} =\left[{\begin{array}{c}0\\\vdots \\0\end{array}}\right]}

where 
 
 
 
 
 x
 
 =
 (
 
 x
 
 1
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 )
 
 
 {\displaystyle \mathbf {x} =(x_{1},\ldots ,x_{n})}
 
 is a point in 
 
 
 
 
 R
 
 n
 
 
 
 
 {\displaystyle R^{n}}
 
 or 
 
 
 
 
 C
 
 n
 
 
 
 
 {\displaystyle C^{n}}
 
 and 
 
 
 
 
 f
 
 1
 
 
 ,
 …
 ,
 
 f
 
 m
 
 
 
 
 {\displaystyle f_{1},\ldots ,f_{m}}
 
 are real or complex functions. The system is overdetermined if 
 
 
 
 m
 >
 n
 
 
 {\displaystyle m>n}
 
. In contrast, the system is an <a href="/facts/Underdetermined_system/N5UDXYeE">underdetermined system</a> if 
 
 
 
 m
 <
 n
 
 
 {\displaystyle m<n}
 
.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 
As an effective method for solving overdetermined systems, the <a href="/facts/Gauss%E2%80%93Newton_algorithm/7c5en5cU">Gauss-Newton</a> iteration locally quadratically converges to solutions at which the Jacobian matrices of 
 
 
 
 
 f
 
 (
 
 x
 
 )
 
 
 {\displaystyle \mathbf {f} (\mathbf {x} )}
 
 are injective.

<h2 id="in-general-use">In general use</h2>
The concept can also be applied to more general systems of equations, such as <a href="/facts/Systems_of_polynomial_equations/1456MrT2">systems of polynomial equations</a> or <a href="/facts/Partial_differential_equations/DyPsBlv7">partial differential equations</a>. In the case of the systems of polynomial equations, it may happen that an overdetermined system has a solution, but that no one equation is a consequence of the others and that, when removing any equation, the new system has more solutions. For example, 
 
 
 
 (
 x
 −
 1
 )
 (
 x
 −
 2
 )
 =
 0
 ,
 (
 x
 −
 1
 )
 (
 x
 −
 3
 )
 =
 0
 
 
 {\displaystyle (x-1)(x-2)=0,(x-1)(x-3)=0}
 
 has the single solution 
 
 
 
 x
 =
 1
 ,
 
 
 {\displaystyle x=1,}
 
 but each equation by itself has two solutions.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Compressed_sensing/aR5DQm3n">Compressed sensing</a></li>
<li><a href="/facts/Consistency_proof/IHkdnA9M">Consistency proof</a></li>
<li><a href="/facts/Integrability_condition/PKp57zwz">Integrability condition</a></li>
<li><a href="/facts/Least_squares/50jIwbxC">Least squares</a></li>
<li><a href="/facts/Moore%E2%80%93Penrose_pseudoinverse/CU73tntq">Moore–Penrose pseudoinverse</a></li>
<li><a href="/facts/Rouch%C3%A9%E2%80%93Capelli_theorem/mdkcFrFd">Rouché-Capelli (or, Rouché-Frobenius) theorem</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Gentle, James E. (2012-12-06). Numerical Linear Algebra for Applications in Statistics. Springer. ISBN 9781461206231. <a href="9781461206231" target="_blank">9781461206231</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Stevens, Scott A. "System Analysis - Rank and Nullity" (PDF). Math 220 - Matrices Handouts. Pennsylvania State University. Retrieved 3 April 2017. <a href="http://math.bd.psu.edu/faculty/stevens/MATH220/Handouts/Rank%20and%20Nullity.pdf" target="_blank">http://math.bd.psu.edu/faculty/stevens/MATH220/Handouts/Rank%20and%20Nullity.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Anton, Howard; Rorres, Chris (2005). Elementary Linear Algebra (9th ed.). John Wiley and Sons, Inc. ISBN 978-0-471-66959-3. <a href="978-0-471-66959-3" target="_blank">978-0-471-66959-3</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Trefethen, Lloyd; Bau, III, David (1997). Numerical Linear Algebra. ISBN 978-0898713619. <a href="978-0898713619" target="_blank">978-0898713619</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">J.M. Ortega and W.C. Rheinboldt (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic Press and SIAM 2000 reproduction. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">D.J. Bates, A.J. Sommese, J.D. Hauenstein and C.W. Wampler (2013). Numerically Solving Polynomial Systems with Bertini. SIAM.{{cite book}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/Template:Cite_book" target="_blank">/wiki/Template:Cite_book</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Overdetermined system open-in-new

Overdetermined system