Overdetermined system: Difference between revisions

Browse history interactively ← Previous edit Next edit →Content deleted Content addedVisual WikitextInline

Revision as of 07:30, 22 March 2007 editCharles Matthews (talk \| contribs)Autopatrolled, Administrators360,382 editsmNo edit summary← Previous edit		Revision as of 15:51, 30 May 2007 edit undoCronholm144 (talk \| contribs)Extended confirmed users6,380 edits HUGE edit, too much to for an edit summaryNext edit →
Line 1:		Line 1:
	In ], a ] is considered '''overdetermined''' if there are more equations than unknowns.<ref></ref>		In ], a ] is considered '''overdetermined''' if there are more equations than unknowns.<ref></ref>The terminology can be described in terms of the concept of ]. Each ] can be seen as an available ]. 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 the unknowns.
	The terminology is justified in terms of a simple concept idea of ]. Each equation to satisfy as a constraint can be seen as using up one ]. Therefore the critical case, according to this kind of commonsense approach, is when the number of equations and the number of independent variables is the same.
			==Systems of equations==
			===An example in two dimensions===
			], all linearly independent]]]), two intersections]]]), no intersections]]]), one intersection, one linearly dependent]]]]
			Consider the system of 3 ]s and 2 unknowns (x<sub>1</sub> and x<sub>2</sub>)

			<math>2x_1+x_2=-1</math>
	==Discussion==

			<math>-3x_1+x_2=-2</math>
	In mathematical detail, it requires more careful discussion to get accurate statements. Considering a system of linear equations

			<math>-x_1+x_2=1</math>
	:''L''<sub>''i''</sub> = 0

			'''Note:''' equations above correspond to picture #1 such that x<sub>1</sub>=x and x<sub>2</sub>=y in the ]
	for 1 ≤ ''i'' ≤ ''M'', in variables

			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 ].

			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 ] 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=x+2 are linearly dependent equations.

			===Matrix form===

			Any system of liner equations can be written as a ].
			The previous system of equations can be written as follows:

			: <math> \begin{bmatrix}
			2 & 1 \\
			-3 & 1 \\
			-1&1\end{bmatrix}</math><math>\begin{bmatrix}
			X_1 \\
			X_2 \end{bmatrix}</math><math> = \begin{bmatrix}
			-1 \\
			-2 \\
			1\end{bmatrix}</math>

			Notice that the number of rows outnumber the number of columns. In ] the concepts of ], ] and ] are important for determining the properties of matrices. The informal discussion of constraints and ] above relate directly to these more formal concepts.







			----------------------------------------------------------------------------------------------------

			==General cases==
			===] case===

			It is important to remember that the homogeneous case is always consistent and can only have two solutions, the ] solution, or both the trivial solution and an infinite solution determined by the number of ] equations.

			Consider the system of linear equations:

			:''L''<sub>''i''</sub> = 0 for 1 ≤ ''i'' ≤ ''M'',

			and variables

	:''X''<sub>1</sub>, ''X''<sub>2</sub>, ..., ''X''<sub>''N''</sub>,		:''X''<sub>1</sub>, ''X''<sub>2</sub>, ..., ''X''<sub>''N''</sub>,
Line 25:		Line 69:
	:''N'' − ''M''.		:''N'' − ''M''.

	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 an adequate number of dependencies, 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''~~. This deals with the ] case~~.		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 an adequate number of 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''.

			===Inhomogeneous case===
	The ''inhomogeneous'' case
			:When studying systems of linear equations, L<sub>i</sub>=c<sub>i</sub> for 1 ≤ ''i'' ≤ ''M'',

			and variables
	:''L''<sub>''i''</sub> = ''c''<sub>''i''</sub>

			:''X''<sub>1</sub>, ''X''<sub>2</sub>, ..., ''X''<sub>''N''</sub>
	with any constants on the ] is slightly different. Here there is no solution to be found by inspection; and there is another phenomenon of incompatible equations, such as

			the equations L<sub>i</sub> are sometimes ]. These dependent equations (often described in terms of ]) lead to three possible cases for an overdetermined system.
	:''X''<sub>''1''</sub> = 1, with
	:''X''<sub>''1''</sub> = 2.

	If ''M~~'' > ''N'', the excess~~ equations ~~must~~ ~~reduce~~ to ~~ones~~ that ~~already~~ ~~follow~~ ~~from~~ ~~''N''~~ of ~~them,~~ ~~for~~ ~~there~~ to be ~~any~~ solution ~~at all~~.		* M equations* and N unknowns*, such that M>N and all M are ]. This case yields no solution.


	The discussion is more convincing, perhaps, when translated into the geometric language of intersecting ]s. 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 form ]s. A sequence of hyperplanes
			* M equations and N unknowns, such that M>N but all M are not linearly independent.

			:There exist three possible subcases of this second case:

			::*M equations and N unknowns, such that M>N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M-D>N. This case yields no solutions.
			::*M equations and N unknowns, such that M>N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M-D=N. This case yields a single solution.
			::*M equations and N unknowns, such that M>N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M-D<N. This case yields infinitely many solutions. Which can be described as F which is the entirety of the field in which the equations are operating.

			'''Note:'''(*Equations and unknowns can correspond to the rows and columns of a matrix respectively)

			* M equations and N unknowns, such that M>N and all M are linearly dependent. This case yields infinitely many solutions.

			The discussion is more convincing, perhaps, when translated into the geometric language of intersecting ]s. 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

	:''H''<sub>1</sub>, ''H''<sub>2</sub>, ..., ''H''<sub>''M''</sub>		:''H''<sub>1</sub>, ''H''<sub>2</sub>, ..., ''H''<sub>''M''</sub>

	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.		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 ], and this is precisely the overdetermined case.

			==Approximate solutions to overdetermined systems==

			The method of ] can be used to find an approximate solutions to overdetermined systems.For the system AX=B, the least squares formula can be written
			X=(A<sup>t</sup>A)<sup>-1</sup>A<sup>t</sup>B<ref>{{Citation \| last=Howard Anton \| first=Chris Rorres,\| title= Elementary Linear Algebra \| edition=9th \| year=2005 \| publisher= John Wiley and Sons, Inc. \| isbn=978-0-471-66959-3}}
			</ref>

			with this formula the example case mentioned earlier can be "solved."

			A= <math> \begin{bmatrix}
			2 & 1 \\
			-3 & 1 \\
			-1&1\end{bmatrix}</math>, X=<math>\begin{bmatrix}
			X_1 \\
			X_2 \end{bmatrix}</math>, B=<math> \begin{bmatrix}
			-1 \\
			-2 \\
			1\end{bmatrix}</math>

	==In general use==		==In general use==

	The concept is also applied to ~~other~~ systems of equations, such as ].		The concept can also be applied to more general systems of equations, such as ].

	==See also==		==See also==
Line 52:		Line 127:
	*]		*]
	*]		*]
			*]
			*]
			*]

	==References==		==References==
Line 57:		Line 135:
	<references/>		<references/>

	{{math-stub}}
	]		]
	]		]

Revision as of 15:51, 30 May 2007

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 the unknowns.

Systems of equations

An example in two dimensions

Consider the system of 3 equations and 2 unknowns (x₁ and x₂)

$2x_{1}+x_{2}=-1$

$-3x_{1}+x_{2}=-2$

$-x_{1}+x_{2}=1$

Note: equations above correspond to picture #1 such that x₁=x and x₂=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=x+2 are linearly dependent equations.

Matrix form

Any system of liner equations can be written as a matrix. The previous system of equations can be written as follows:

{\begin{bmatrix}2&1\\-3&1\\-1&1\end{bmatrix}}

{\begin{bmatrix}X_{1}\\X_{2}\end{bmatrix}}

={\begin{bmatrix}-1\\-2\\1\end{bmatrix}}

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.

General cases

Homogeneous case

It is important to remember that the homogeneous case is always consistent and can only have two solutions, the trivial solution, or both the trivial solution and an infinite solution determined by the number of linearly dependent equations.

Consider the system of linear equations:

L_i = 0 for 1 ≤ i ≤ M,

and variables

X₁, X₂, ..., X_N,

then

X₁ = X₂ = ... = X_N = 0

is always a solution. When

M < N

the system is underdetermined and there are always 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 other solutions just when the system of equations has an adequate number of 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.

Inhomogeneous case

When studying systems of linear equations, L_i=c_i for 1 ≤ i ≤ M,

and variables

X₁, X₂, ..., X_N

the equations L_i are sometimes linearly dependent. These dependent equations (often described in terms of vectors) lead to three possible cases for an overdetermined system.

M equations* and N unknowns*, such that M>N and all M are linearly independent. This case yields no solution.

M equations and N unknowns, such that M>N but all M are not linearly independent.

There exist three possible subcases of this second case:

M equations and N unknowns, such that M>N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M-D>N. This case yields no solutions.
M equations and N unknowns, such that M>N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M-D=N. This case yields a single solution.
M equations and N unknowns, such that M>N but all M are not linearly independent, but when the linearly dependent equations(D) are removed M-D<N. This case yields infinitely many solutions. Which can be described as F which is the entirety of the field in which the equations are operating.

Note:(*Equations and unknowns can correspond to the rows and columns of a matrix respectively)

M equations and N unknowns, such that M>N and all M are linearly dependent. This case yields infinitely many solutions.

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

H₁, H₂, ..., H_M

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.

Approximate solutions to overdetermined systems

The method of least squares can be used to find an approximate solutions to overdetermined systems.For the system AX=B, the least squares formula can be written X=(AA)AB

with this formula the example case mentioned earlier can be "solved."

A= ${\begin{bmatrix}2&1\\-3&1\\-1&1\end{bmatrix}}$ , X= ${\begin{bmatrix}X_{1}\\X_{2}\end{bmatrix}}$ , B= ${\begin{bmatrix}-1\\-2\\1\end{bmatrix}}$

In general use

The concept can also be applied to more general systems of equations, such as partial differential equations.

References

Overdetermined equations at planetmath.org
Howard Anton, Chris Rorres, (2005), Elementary Linear Algebra (9th ed.), John Wiley and Sons, Inc., ISBN 978-0-471-66959-3{{citation}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)

Categories: