|
|
| (642 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| {{More footnotes|date=June 2012}}
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| [[Image:Secretsharing-3-point.png|thumb|right|A linear system in three variables determines a collection of [[plane (mathematics)|planes]]. The intersection point is the solution.]]
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| In [[mathematics]], a '''system of linear equations''' (or '''linear system''') is a collection of [[linear equation]]s involving the same set of [[variable (math)|variable]]s. For example,
| | * Only registered users will be able to execute this rendering mode. |
| :<math>\begin{alignat}{7} | | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
| 3x &&\; + \;&& 2y &&\; - \;&& z &&\; = \;&& 1 & \\
| |
| 2x &&\; - \;&& 2y &&\; + \;&& 4z &&\; = \;&& -2 & \\
| |
| -x &&\; + \;&& \tfrac{1}{2} y &&\; - \;&& z &&\; = \;&& 0 &
| |
| \end{alignat}</math>
| |
| is a system of three equations in the three variables {{math|''x'', ''y'', ''z''}}. A '''solution''' to a linear system is an assignment of numbers to the variables such that all the equations are simultaneously satisfied. A [[Equation solving|solution]] to the system above is given by
| |
| :<math>\begin{alignat}{2} | |
| x & = & 1 \\
| |
| y & = & -2 \\
| |
| z & = & -2
| |
| \end{alignat}</math>
| |
| since it makes all three equations valid.<ref>Linear algebra, as discussed in this article, is a very well established mathematical discipline for which there are many sources. Almost all of the material in this article can be found in Lay 2005, Meyer 2001, and Strang 2005.</ref>
| |
|
| |
|
| In mathematics, the theory of linear systems is the basis and a fundamental part of [[linear algebra]], a subject which is used in most parts of modern mathematics. Computational [[algorithm]]s for finding the solutions are an important part of [[numerical linear algebra]], and play a prominent role in [[engineering]], [[physics]], [[chemistry]], [[computer science]], and [[economics]]. A [[Nonlinear system|system of non-linear equations]] can often be [[approximation|approximated]] by a linear system (see [[linearization]]), a helpful technique when making a [[mathematical model]] or [[computer simulation]] of a relatively complex system.
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| Very often, the coefficients of the equations are [[real number|real]] or [[complex number]]s and the solutions are searched in the same set of numbers, but the theory and the algorithms apply for coefficients and solutions in any [[field (mathematics)|field]]. For solutions in an [[integral domain]] like the [[ring (mathematics)|ring]] of the [[integer]]s, or in other [[algebraic structure]]s, other theories have been developed. See, for example, [[integer linear programming]] for integer solutions, [[Gröbner basis]] for [[polynomial]] coefficients and unknowns, or also [[tropical geometry]] for linear algebra in a more exotic structure.
| | '''MathML''' |
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| ==Elementary example==
| | <!--'''PNG''' (currently default in production) |
| The simplest kind of linear system involves two equations and two variables:
| | :<math forcemathmode="png">E=mc^2</math> |
| :<math>\begin{alignat}{5}
| |
| 2x &&\; + \;&& 3y &&\; = \;&& 6 & \\
| |
| 4x &&\; + \;&& 9y &&\; = \;&& 15&.
| |
| \end{alignat}</math>
| |
| One method for solving such a system is as follows. First, solve the top equation for <math>x</math> in terms of <math>y</math>:
| |
| :<math>x = 3 - \frac{3}{2}y.</math>
| |
| Now substitute this expression for ''x'' into the bottom equation:
| |
| :<math>4\left( 3 - \frac{3}{2}y \right) + 9y = 15.</math>
| |
| This results in a single equation involving only the variable <math>y</math>. Solving gives <math>y = 1</math>, and substituting this back into the equation for <math>x</math> yields <math>x = 3/2</math>. This method generalizes to systems with additional variables (see "elimination of variables" below, or the article on [[elementary algebra]].)
| |
|
| |
|
| ==General form==
| | '''source''' |
| A general system of ''m'' linear equations with ''n'' unknowns can be written as
| | :<math forcemathmode="source">E=mc^2</math> --> |
| :<math>\begin{alignat}{7} | |
| a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& b_1 \\
| |
| a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& b_2 \\
| |
| \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\
| |
| a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& b_m. \\
| |
| \end{alignat}</math>
| |
| Here <math>x_1, x_2,\ldots,x_n</math> are the unknowns, <math>a_{11},a_{12},\ldots,a_{mn}</math> are the coefficients of the system, and <math>b_1,b_2,\ldots,b_m</math> are the constant terms.
| |
|
| |
|
| Often the coefficients and unknowns are [[real number|real]] or [[complex number]]s, but [[integer]]s and [[rational number]]s are also seen, as are polynomials and elements of an abstract [[algebraic structure]].
| | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
|
| |
|
| ===Vector equation=== | | ==Demos== |
| One extremely helpful view is that each unknown is a weight for a [[column vector]] in a [[linear combination]].
| |
| :<math>
| |
| x_1 \begin{bmatrix}a_{11}\\a_{21}\\ \vdots \\a_{m1}\end{bmatrix} +
| |
| x_2 \begin{bmatrix}a_{12}\\a_{22}\\ \vdots \\a_{m2}\end{bmatrix} +
| |
| \cdots +
| |
| x_n \begin{bmatrix}a_{1n}\\a_{2n}\\ \vdots \\a_{mn}\end{bmatrix}
| |
| =
| |
| \begin{bmatrix}b_1\\b_2\\ \vdots \\b_m\end{bmatrix}
| |
| </math>
| |
| This allows all the language and theory of ''[[vector space]]s'' (or more generally, ''[[module (mathematics)|module]]s'') to be brought to bear. For example, the collection of all possible linear combinations of the vectors on the left-hand side is called their ''[[span (linear algebra)|span]]'', and the equations have a solution just when the right-hand vector is within that span. If every vector within that span has exactly one expression as a linear combination of the given left-hand vectors, then any solution is unique. In any event, the span has a ''[[basis (linear algebra)|basis]]'' of [[linearly independent]] vectors that do guarantee exactly one expression; and the number of vectors in that basis (its ''[[dimension (linear algebra)|dimension]]'') cannot be larger than ''m'' or ''n'', but it can be smaller. This is important because if we have ''m'' independent vectors a solution is guaranteed regardless of the right-hand side, and otherwise not guaranteed.
| |
|
| |
|
| ===Matrix equation===
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
| The vector equation is equivalent to a [[matrix (mathematics)|matrix]] equation of the form
| |
| :<math>A\bold{x}=\bold{b}</math> | |
| where ''A'' is an ''m''×''n'' matrix, '''x''' is a [[column vector]] with ''n'' entries, and '''b''' is a column vector with ''m'' entries.
| |
| : <math> | |
| A=
| |
| \begin{bmatrix}
| |
| a_{11} & a_{12} & \cdots & a_{1n} \\
| |
| a_{21} & a_{22} & \cdots & a_{2n} \\
| |
| \vdots & \vdots & \ddots & \vdots \\
| |
| a_{m1} & a_{m2} & \cdots & a_{mn}
| |
| \end{bmatrix},\quad
| |
| \bold{x}=
| |
| \begin{bmatrix}
| |
| x_1 \\
| |
| x_2 \\
| |
| \vdots \\
| |
| x_n
| |
| \end{bmatrix},\quad
| |
| \bold{b}=
| |
| \begin{bmatrix}
| |
| b_1 \\
| |
| b_2 \\
| |
| \vdots \\
| |
| b_m
| |
| \end{bmatrix}
| |
| </math>
| |
| The number of vectors in a basis for the span is now expressed as the ''[[rank (linear algebra)|rank]]'' of the matrix.
| |
|
| |
|
| ==Solution set==
| |
| [[Image:Intersecting Lines.svg|thumb|right|The solution set for the equations {{nowrap|''x'' − ''y'' {{=}} −1}} and {{nowrap|3''x'' + ''y'' {{=}} 9}} is the single point (2, 3).]]
| |
| A '''solution''' of a linear system is an assignment of values to the variables {{nowrap|''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x<sub>n</sub>''}} such that each of the equations is satisfied. The [[Set (mathematics)|set]] of all possible solutions is called the '''[[solution set]]'''.
| |
|
| |
|
| A linear system may behave in any one of three possible ways:
| | * accessibility: |
| # The system has ''infinitely many solutions''.
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| # The system has a single ''unique solution''.
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| # The system has ''no solution''.
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| ===Geometric interpretation=== | | ==Test pages == |
| For a system involving two variables (''x'' and ''y''), each linear equation determines a [[line (mathematics)|line]] on the ''xy''-[[Cartesian coordinate system|plane]]. Because a solution to a linear system must satisfy all of the equations, the solution set is the [[intersection (set theory)|intersection]] of these lines, and is hence either a line, a single point, or the [[empty set]].
| |
|
| |
|
| For three variables, each linear equation determines a [[plane (mathematics)|plane]] in [[three-dimensional space]], and the solution set is the intersection of these planes. Thus the solution set may be a plane, a line, a single point, or the empty set.
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| For ''n'' variables, each linear equation determines a [[hyperplane]] in [[n-dimensional space|''n''-dimensional space]]. The solution set is the intersection of these hyperplanes, which may be a [[flat (geometry)|flat]] of any dimension.
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| ===General behavior===
| | ==Bug reporting== |
| [[Image:IntersectingPlanes.png|thumb|right|The solution set for two equations in three variables is usually a line.]] | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| In general, the behavior of a linear system is determined by the relationship between the number of equations and the number of unknowns:
| |
| # Usually, a system with fewer equations than unknowns has infinitely many solutions or sometimes unique sparse solutions ([[Compressed sensing|Compressed Sensing]]). Such a system is also known as an [[underdetermined system]].
| |
| # Usually, a system with the same number of equations and unknowns has a single unique solution.
| |
| # Usually, a system with more equations than unknowns has no solution. Such a system is also known as an [[overdetermined system]].
| |
| In the first case, the [[dimension]] of the solution set is usually equal to {{nowrap|''n'' − ''m''}}, where ''n'' is the number of variables and ''m'' is the number of equations.
| |
| | |
| The following pictures illustrate this trichotomy in the case of two variables:
| |
| :{| border=0 cellpadding=5
| |
| |-
| |
| |width="150px" align="center"| [[Image:One Line.svg|120px]]
| |
| |width="150px" align="center"| [[Image:Two Lines.svg|120px]]
| |
| |width="150px" align="center"| [[Image:Three Lines.svg|120px]]
| |
| |-
| |
| |align="center"| One Equation
| |
| |align="center"| Two Equations
| |
| |align="center"| Three Equations
| |
| |}
| |
| The first system has infinitely many solutions, namely all of the points on the blue line. The second system has a single unique solution, namely the intersection of the two lines. The third system has no solutions, since the three lines share no common point.
| |
| | |
| Keep in mind that the pictures above show only the most common case. It is possible for a system of two equations and two unknowns to have no solution (if the two lines are parallel), or for a system of three equations and two unknowns to be solvable (if the three lines intersect at a single point). In general, a system of linear equations may behave differently than expected if the equations are '''[[linear independence|linearly dependent]]''', or if two or more of the equations are '''inconsistent'''.
| |
| | |
| ==Properties== | |
| | |
| ===Independence===
| |
| The equations of a linear system are '''independent''' if none of the equations can be derived algebraically from the others. When the equations are independent, each equation contains new information about the variables, and removing any of the equations increases the size of the solution set. For linear equations, logical independence is the same as [[linear independence]].
| |
| | |
| [[Image:Three Intersecting Lines.svg|thumb|right|The equations {{nowrap|''x'' − 2''y'' {{=}} −1}}, {{nowrap|3''x'' + 5''y'' {{=}} 8}}, and {{nowrap|4''x'' + 3''y'' {{=}} 7}} are not linearly independent.]]
| |
| For example, the equations
| |
| :<math>3x+2y=6\;\;\;\;\text{and}\;\;\;\;6x+4y=12</math>
| |
| are not independent — they are the same equation when scaled by a factor of two, and they would produce identical graphs. This is an example of equivalence in a system of linear equations.
| |
| | |
| For a more complicated example, the equations
| |
| :<math>\begin{alignat}{5}
| |
| x &&\; - \;&& 2y &&\; = \;&& -1 & \\
| |
| 3x &&\; + \;&& 5y &&\; = \;&& 8 & \\
| |
| 4x &&\; + \;&& 3y &&\; = \;&& 7 &
| |
| \end{alignat}</math>
| |
| are not independent, because the third equation is the sum of the other two. Indeed, any one of these equations can be derived from the other two, and any one of the equations can be removed without affecting the solution set. The graphs of these equations are three lines that intersect at a single point.
| |
| | |
| ===Consistency===
| |
| [[Image:Parallel Lines.svg|thumb|right|The equations {{nowrap|3''x'' + 2''y'' {{=}} 6}} and {{nowrap|3''x'' + 2''y'' {{=}} 12}} are inconsistent.]] | |
| A linear system is '''consistent''' if it has a solution, and '''inconsistent''' otherwise. When the system is inconsistent, it is possible to derive a [[contradiction]] from the equations, that may always be rewritten such as the statement {{nowrap|0 {{=}} 1}}.
| |
| | |
| For example, the equations
| |
| :<math>3x+2y=6\;\;\;\;\text{and}\;\;\;\;3x+2y=12</math>
| |
| are inconsistent. In fact, by subtracting the first equation from the second one and multiplying both sides of the result by 1/6, we get {{nowrap|0 {{=}} 1}}. The graphs of these equations on the ''xy''-plane are a pair of [[parallel (geometry)|parallel]] lines.
| |
| | |
| It is possible for three linear equations to be inconsistent, even though any two of them are consistent together. For example, the equations
| |
| :<math>\begin{alignat}{7}
| |
| x &&\; + \;&& y &&\; = \;&& 1 & \\
| |
| 2x &&\; + \;&& y &&\; = \;&& 1 & \\
| |
| 3x &&\; + \;&& 2y &&\; = \;&& 3 &
| |
| \end{alignat}</math>
| |
| are inconsistent. Adding the first two equations together gives {{nowrap|3''x'' + 2''y'' {{=}} 2}}, which can be subtracted from the third equation to yield {{nowrap|0 {{=}} 1}}. Note that any two of these equations have a common solution. The same phenomenon can occur for any number of equations.
| |
| | |
| In general, inconsistencies occur if the left-hand sides of the equations in a system are linearly dependent, and the constant terms do not satisfy the dependence relation. A system of equations whose left-hand sides are linearly independent is always consistent.
| |
| | |
| ===Equivalence===
| |
| Two linear systems using the same set of variables are '''equivalent''' if each of the equations in the second system can be derived algebraically from the equations in the first system, and vice-versa. Two systems are equivalent if either both are inconsistent or each equation of any of them is a linear combination of the equations of the other one. It follows that two linear systems are equivalent if and only if they have the same solution set.
| |
| | |
| ==Solving a linear system==
| |
| There are several [[algorithm]]s for [[equation solving|solving]] a system of linear equations.
| |
| | |
| ===Describing the solution===
| |
| When the solution set is finite, it is reduced to a single element. In this case, the unique solution is described by a sequence of equations whose left hand sides are the names of the unknowns and right hand sides are the corresponding values, for example <math>(x=3, \;y=-2,\; z=6)</math>. When an order on the unknowns has been fixed, for example the [[alphabetical order]] the solution may be described as a [[vector space|vector]] of values, like <math>(3, \,-2,\, 6)</math> for the previous example.
| |
| | |
| It can be difficult to describe a set with infinite solutions. Typically, some of the variables are designated as '''free''' (or '''independent''', or as '''parameters'''), meaning that they are allowed to take any value, while the remaining variables are '''dependent''' on the values of the free variables.
| |
| | |
| For example, consider the following system:
| |
| :<math>\begin{alignat}{7}
| |
| x &&\; + \;&& 3y &&\; - \;&& 2z &&\; = \;&& 5 & \\
| |
| 3x &&\; + \;&& 5y &&\; + \;&& 6z &&\; = \;&& 7 &
| |
| \end{alignat}</math>
| |
| The solution set to this system can be described by the following equations:
| |
| :<math>x=-7z-1\;\;\;\;\text{and}\;\;\;\;y=3z+2\text{.}</math>
| |
| Here ''z'' is the free variable, while ''x'' and ''y'' are dependent on ''z''. Any point in the solution set can be obtained by first choosing a value for ''z'', and then computing the corresponding values for ''x'' and ''y''.
| |
| | |
| Each free variable gives the solution space one [[Degrees of freedom (statistics)|degree of freedom]], the number of which is equal to the [[dimension]] of the solution set. For example, the solution set for the above equation is a line, since a point in the solution set can be chosen by specifying the value of the parameter ''z''. An infinite solution of higher order may describe a plane, or higher dimensional set.
| |
| | |
| Different choices for the free variables may lead to different descriptions of the same solution set. For example, the solution to the above equations can alternatively be described as follows:
| |
| :<math>y=-\frac{3}{7}x + \frac{11}{7}\;\;\;\;\text{and}\;\;\;\;z=-\frac{1}{7}x-\frac{1}{7}\text{.}</math>
| |
| Here ''x'' is the free variable, and ''y'' and ''z'' are dependent.
| |
| | |
| ===Elimination of variables===
| |
| The simplest method for solving a system of linear equations is to repeatedly eliminate variables. This method can be described as follows:
| |
| # In the first equation, solve for one of the variables in terms of the others.
| |
| # Plug this expression into the remaining equations. This yields a system of equations with one fewer equation and one fewer unknown.
| |
| # Continue until you have reduced the system to a single linear equation.
| |
| # Solve this equation, and then back-substitute until the entire solution is found.
| |
| | |
| For example, consider the following system:
| |
| :<math>\begin{alignat}{7}
| |
| x &&\; + \;&& 3y &&\; - \;&& 2z &&\; = \;&& 5 & \\
| |
| 3x &&\; + \;&& 5y &&\; + \;&& 6z &&\; = \;&& 7 & \\
| |
| 2x &&\; + \;&& 4y &&\; + \;&& 3z &&\; = \;&& 8 &
| |
| \end{alignat}</math>
| |
| Solving the first equation for ''x'' gives {{nowrap|''x'' {{=}} 5 + 2''z'' − 3''y''}}, and plugging this into the second and third equation yields
| |
| :<math>\begin{alignat}{5}
| |
| -4y &&\; + \;&& 12z &&\; = \;&& -8 & \\
| |
| -2y &&\; + \;&& 7z &&\; = \;&& -2 &
| |
| \end{alignat}</math>
| |
| Solving the first of these equations for ''y'' yields {{nowrap|''y'' {{=}} 2 + 3''z''}}, and plugging this into the second equation yields {{nowrap|''z'' {{=}} 2}}. We now have:
| |
| :<math>\begin{alignat}{7}
| |
| x &&\; = \;&& 5 &&\; + \;&& 2z &&\; - \;&& 3y & \\
| |
| y &&\; = \;&& 2 &&\; + \;&& 3z && && & \\
| |
| z &&\; = \;&& 2 && && && && &
| |
| \end{alignat}</math>
| |
| Substituting {{nowrap|''z'' {{=}} 2}} into the second equation gives {{nowrap|''y'' {{=}} 8}}, and substituting {{nowrap|''z'' {{=}} 2}} and {{nowrap|''y'' {{=}} 8}} into the first equation yields {{nowrap|''x'' {{=}} −15}}. Therefore, the solution set is the single point {{nowrap|(''x'', ''y'', ''z'') {{=}} (−15, 8, 2)}}.
| |
| | |
| ===Row reduction===
| |
| {{main|Gaussian elimination}}
| |
| In '''row reduction''', the linear system is represented as an [[augmented matrix]]:
| |
| :<math>\left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 3 & 5 & 6 & 7 \\
| |
| 2 & 4 & 3 & 8
| |
| \end{array}\right]\text{.}
| |
| </math>
| |
| This matrix is then modified using [[elementary row operations]] until it reaches [[reduced row echelon form]]. There are three types of elementary row operations:
| |
| :'''Type 1''': Swap the positions of two rows.
| |
| :'''Type 2''': Multiply a row by a nonzero [[scalar (mathematics)|scalar]].
| |
| :'''Type 3''': Add to one row a scalar multiple of another.
| |
| Because these operations are reversible, the augmented matrix produced always represents a linear system that is equivalent to the original.
| |
| | |
| There are several specific algorithms to row-reduce an augmented matrix, the simplest of which are [[Gaussian elimination]] and [[Gauss-Jordan elimination]]. The following computation shows Gauss-Jordan elimination applied to the matrix above:
| |
| :<math>\left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 3 & 5 & 6 & 7 \\
| |
| 2 & 4 & 3 & 8
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 0 & -4 & 12 & -8 \\
| |
| 2 & 4 & 3 & 8
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 0 & -4 & 12 & -8 \\
| |
| 0 & -2 & 7 & -2
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 0 & 1 & -3 & 2 \\
| |
| 0 & -2 & 7 & -2
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 0 & 1 & -3 & 2 \\
| |
| 0 & 0 & 1 & 2
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 3 & -2 & 5 \\
| |
| 0 & 1 & 0 & 8 \\
| |
| 0 & 0 & 1 & 2
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 3 & 0 & 9 \\
| |
| 0 & 1 & 0 & 8 \\
| |
| 0 & 0 & 1 & 2
| |
| \end{array}\right]</math><math>\sim
| |
| \left[\begin{array}{rrr|r}
| |
| 1 & 0 & 0 & -15 \\
| |
| 0 & 1 & 0 & 8 \\
| |
| 0 & 0 & 1 & 2
| |
| \end{array}\right].</math>
| |
| The last matrix is in reduced row echelon form, and represents the system {{nowrap|''x'' {{=}} −15}}, {{nowrap|''y'' {{=}} 8}}, {{nowrap|''z'' {{=}} 2}}. A comparison with the example in the previous section on the algebraic elimination of variables shows that these two methods are in fact the same; the difference lies in how the computations are written down.
| |
| | |
| ===Cramer's rule===
| |
| {{main|Cramer's rule}}
| |
| '''Cramer's rule''' is an explicit formula for the solution of a system of linear equations, with each variable given by a quotient of two [[determinant]]s. For example, the solution to the system
| |
| :<math>\begin{alignat}{7}
| |
| x &&\; + \;&& 3y &&\; - \;&& 2z &&\; = \;&& 5 & \\
| |
| 3x &&\; + \;&& 5y &&\; + \;&& 6z &&\; = \;&& 7 & \\
| |
| 2x &&\; + \;&& 4y &&\; + \;&& 3z &&\; = \;&& 8 &
| |
| \end{alignat}</math>
| |
| is given by
| |
| :<math>
| |
| x=\frac
| |
| {\,\left| \begin{matrix}5&3&-2\\7&5&6\\8&4&3\end{matrix} \right|\,}
| |
| {\,\left| \begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix} \right|\,}
| |
| ,\;\;\;\;y=\frac
| |
| {\,\left| \begin{matrix}1&5&-2\\3&7&6\\2&8&3\end{matrix} \right|\,}
| |
| {\,\left| \begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix} \right|\,}
| |
| ,\;\;\;\;z=\frac
| |
| {\,\left| \begin{matrix}1&3&5\\3&5&7\\2&4&8\end{matrix} \right|\,}
| |
| {\,\left| \begin{matrix}1&3&-2\\3&5&6\\2&4&3\end{matrix} \right|\,}.
| |
| </math>
| |
| For each variable, the denominator is the determinant of the matrix of coefficients, while the numerator is the determinant of a matrix in which one column has been replaced by the vector of constant terms.
| |
| | |
| Though Cramer's rule is important theoretically, it has little practical value for large matrices, since the computation of large determinants is somewhat cumbersome. (Indeed, large determinants are most easily computed using row reduction.)
| |
| Further, Cramer's rule has very poor numerical properties, making it unsuitable for solving even small systems reliably, unless the operations are performed in rational arithmetic with unbounded precision.
| |
| | |
| ===Other methods===
| |
| While systems of three or four equations can be readily solved by hand, computers are often used for larger systems. The standard algorithm for solving a system of linear equations is based on Gaussian elimination with some modifications. Firstly, it is essential to avoid division by small numbers, which may lead to inaccurate results. This can be done by reordering the equations if necessary, a process known as ''pivoting''. Secondly, the algorithm does not exactly do Gaussian elimination, but it computes the [[LU decomposition]] of the matrix ''A''. This is mostly an organizational tool, but it is much quicker if one has to solve several systems with the same matrix ''A'' but different vectors '''b'''.
| |
| | |
| If the matrix ''A'' has some special structure, this can be exploited to obtain faster or more accurate algorithms. For instance, systems with a [[symmetric matrix|symmetric]] [[positive-definite matrix|positive definite]] matrix can be solved twice as fast with the [[Cholesky decomposition]]. [[Levinson recursion]] is a fast method for [[Toeplitz matrix|Toeplitz matrices]]. Special methods exist also for matrices with many zero elements (so-called [[sparse matrix|sparse matrices]]), which appear often in applications.
| |
| | |
| A completely different approach is often taken for very large systems, which would otherwise take too much time or memory. The idea is to start with an initial approximation to the solution (which does not have to be accurate at all), and to change this approximation in several steps to bring it closer to the true solution. Once the approximation is sufficiently accurate, this is taken to be the solution to the system. This leads to the class of [[iterative method]]s.
| |
| | |
| ==Homogeneous systems==
| |
| {{see also|Homogeneous differential equation}}
| |
| A system of linear equations is '''homogeneous''' if all of the constant terms are zero:
| |
| :<math>\begin{alignat}{7}
| |
| a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& 0 \\
| |
| a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& 0 \\
| |
| \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \,\vdots \\
| |
| a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& 0. \\
| |
| \end{alignat}</math>
| |
| A homogeneous system is equivalent to a matrix equation of the form
| |
| :<math>A\textbf{x}=\textbf{0}</math>
| |
| where ''A'' is an {{nowrap|''m'' × ''n''}} matrix, '''x''' is a column vector with ''n'' entries, and '''0''' is the [[zero vector]] with ''m'' entries.
| |
| | |
| ===Solution set===
| |
| Every homogeneous system has at least one solution, known as the '''zero solution''' (or '''trivial solution'''), which is obtained by assigning the value of zero to each of the variables. If the system has a non-singular matrix ('''det'''('''A''') ≠ 0) then it is also the only solution. If the system has a [[singular matrix]] then there is a solution set with an infinite number of solutions. This solution set has the following additional properties:
| |
| # If '''u''' and '''v''' are two [[vector (mathematics)|vectors]] representing solutions to a homogeneous system, then the vector sum {{nowrap|'''u''' + '''v'''}} is also a solution to the system.
| |
| # If '''u''' is a vector representing a solution to a homogeneous system, and ''r'' is any [[scalar (mathematics)|scalar]], then ''r'''''u''' is also a solution to the system.
| |
| These are exactly the properties required for the solution set to be a [[Euclidean subspace|linear subspace]] of '''R'''<sup>''n''</sup>. In particular, the solution set to a homogeneous system is the same as the [[Kernel (matrix)|null space]] of the corresponding matrix ''A''.
| |
| | |
| ===Relation to nonhomogeneous systems===
| |
| There is a close relationship between the solutions to a linear system and the solutions to the corresponding homogeneous system:
| |
| :<math>A\textbf{x}=\textbf{b}\qquad \text{and}\qquad A\textbf{x}=\textbf{0}\text{.}</math>
| |
| Specifically, if '''p''' is any specific solution to the linear system {{nowrap|''A'''''x''' {{=}} '''b'''}}, then the entire solution set can be described as
| |
| :<math>\left\{ \textbf{p}+\textbf{v} : \textbf{v}\text{ is any solution to }A\textbf{x}=\textbf{0} \right\}.</math>
| |
| Geometrically, this says that the solution set for {{nowrap|''A'''''x''' {{=}} '''b'''}} is a [[translation (geometry)|translation]] of the solution set for {{nowrap|''A'''''x''' {{=}} '''0'''}}. Specifically, the [[flat (geometry)|flat]] for the first system can be obtained by translating the [[Euclidean subspace|linear subspace]] for the homogeneous system by the vector '''p'''.
| |
| | |
| This reasoning only applies if the system {{nowrap|''A'''''x''' {{=}} '''b'''}} has at least one solution. This occurs if and only if the vector '''b''' lies in the [[image (mathematics)|image]] of the [[linear transformation]] ''A''.
| |
| | |
| ==See also==
| |
| * [[LAPACK]] (the free standard package to solve linear equations numerically; available in Fortran, C, C++)
| |
| * [[Row reduction]]
| |
| * [[Simultaneous equations]]
| |
| * [[Arrangement of hyperplanes]]
| |
| * [[Linear least squares (mathematics)|Linear least squares]]
| |
| * [[Matrix decomposition]]
| |
| * [[Iterative refinement]]
| |
| | |
| ==Notes==
| |
| {{reflist}}
| |
| | |
| ==References==
| |
| {{see also|Linear algebra#Further reading}}
| |
| | |
| ===Textbooks===
| |
| * {{Citation
| |
| | last = Axler
| |
| | first = Sheldon Jay
| |
| | year = 1997
| |
| | title = Linear Algebra Done Right
| |
| | publisher = Springer-Verlag
| |
| | edition = 2nd
| |
| | isbn = 0-387-98259-0
| |
| }}
| |
| * {{Citation
| |
| | last = Lay
| |
| | first = David C.
| |
| | date = August 22, 2005
| |
| | title = Linear Algebra and Its Applications
| |
| | publisher = Addison Wesley
| |
| | edition = 3rd
| |
| | isbn = 978-0-321-28713-7
| |
| }}
| |
| * {{Citation
| |
| | last = Meyer
| |
| | first = Carl D.
| |
| | date = February 15, 2001
| |
| | title = Matrix Analysis and Applied Linear Algebra
| |
| | publisher = Society for Industrial and Applied Mathematics (SIAM)
| |
| | isbn = 978-0-89871-454-8
| |
| | url = http://www.matrixanalysis.com/DownloadChapters.html
| |
| }}
| |
| * {{Citation
| |
| | last = Poole
| |
| | first = David
| |
| | year = 2006
| |
| | title = Linear Algebra: A Modern Introduction
| |
| | publisher = Brooks/Cole
| |
| | edition = 2nd
| |
| | isbn = 0-534-99845-3
| |
| }}
| |
| * {{Citation
| |
| | last = Anton
| |
| | first = Howard
| |
| | year = 2005
| |
| | title = Elementary Linear Algebra (Applications Version)
| |
| | publisher = Wiley International
| |
| | edition = 9th
| |
| }}
| |
| * {{Citation
| |
| | last = Leon
| |
| | first = Steven J.
| |
| | year = 2006
| |
| | title = Linear Algebra With Applications
| |
| | publisher = Pearson Prentice Hall
| |
| | edition = 7th
| |
| }}
| |
| * {{Citation
| |
| | last = Strang
| |
| | first = Gilbert
| |
| | authorlink = Gilbert Strang
| |
| | year = 2005
| |
| | title = Linear Algebra and Its Applications
| |
| | publisher =
| |
| | edition =
| |
| }}
| |
| | |
| ==External links==
| |
| * [http://sole.ooz.ie/ WebApp descriptively solving systems of linear equations with a number of methods]
| |
| * [http://people.revoledu.com/kardi/tutorial/LinearAlgebra/SolvingSystemLinearEquations.html#SystemLinearEquations Solving system linear equations] online matrix calculator and tutorial.
| |
| * [http://www.solvingequations.net Online Equations Solver]
| |
| * Online [http://wims.unice.fr/wims/wims.cgi?module=tool/linear/linsolver.en linear solver]
| |
| * [http://www.stud.feec.vutbr.cz/~xvapen02/vypocty/linrov.php?language=english Online Calculator of System of linear equations]
| |
| {{Numerical linear algebra}}
| |
| | |
| [[Category:Equations]]
| |
| [[Category:Linear algebra]]
| |
| [[Category:Numerical linear algebra]]
| |
| | |
| [[ar:نظام معادلات خطية]]
| |
| [[an:Sistema d'equacions lineals]]
| |
| [[be:Сістэма лінейных алгебраічных ураўненняў]]
| |
| [[be-x-old:Сыстэма лінейных альгебраічных раўнаньняў]]
| |
| [[bg:Система линейни уравнения]]
| |
| [[bs:Sistem linearnih jednačina]]
| |
| [[ca:Sistema d'equacions lineals]]
| |
| [[cs:Soustava lineárních rovnic]]
| |
| [[de:Lineares Gleichungssystem]]
| |
| [[et:Lineaarvõrrandisüsteem]]
| |
| [[el:Σύστημα γραμμικών εξισώσεων]]
| |
| [[es:Sistema de ecuaciones lineales]]
| |
| [[eo:Sistemo de linearaj ekvacioj]]
| |
| [[eu:Ekuazio linealetako sistema]]
| |
| [[fa:دستگاه معادلات خطی]]
| |
| [[hif:System of linear equations]]
| |
| [[fr:Système d'équations linéaires]]
| |
| [[gl:Sistema de ecuacións lineais]]
| |
| [[ko:연립 일차 방정식]]
| |
| [[hr:Sustav linearnih jednadžbi]]
| |
| [[is:Línulegt jöfnuhneppi]]
| |
| [[it:Sistema di equazioni lineari]]
| |
| [[he:מערכת משוואות לינאריות]]
| |
| [[la:Systema aequationum linearium]]
| |
| [[hu:Lineáris egyenletrendszer]]
| |
| [[nl:Stelsel van lineaire vergelijkingen]]
| |
| [[ja:線型方程式系]]
| |
| [[no:Lineært ligningssystem]]
| |
| [[nn:Lineært likningssystem]]
| |
| [[oc:Sistèma d'equacions linearas]]
| |
| [[pnb:لینیر ایکوایشنز دا پربندھ]]
| |
| [[pl:Układ równań liniowych]]
| |
| [[pt:Sistema de equações lineares]]
| |
| [[ro:Sistem de ecuații liniare]]
| |
| [[ru:Система линейных алгебраических уравнений]]
| |
| [[simple:System of linear equations]]
| |
| [[sd:سِڌِر مساواتُن جو سرشتو]]
| |
| [[sl:Sistem linearnih enačb]]
| |
| [[sr:Систем линеарних једначина]]
| |
| [[sh:Sistem linearnih jednačina]]
| |
| [[fi:Lineaarinen yhtälöryhmä]]
| |
| [[sv:Linjärt ekvationssystem]]
| |
| [[ta:நேரியல் சமன்பாடுகளின் தொகுப்பு]]
| |
| [[tr:Doğrusal denklem dizgesi]]
| |
| [[uk:Система лінійних алгебраїчних рівнянь]]
| |
| [[ur:یکلخت لکیری مساوات کا نظام]]
| |
| [[vi:Hệ phương trình tuyến tính]]
| |
| [[war:Sistema han ekawsyones linyales]]
| |
| [[zh:线性方程组]]
| |
