Linear system of equations

In linear algebra, a linear system of equations ( LGS for short ) is a set of linear equations with one or more unknowns that should all be satisfied at the same time.

A corresponding system for three unknowns looks, for example, as follows: ${\displaystyle x_{1},\ x_{2},\ x_{3}}$

${\displaystyle {\begin{matrix}3x_{1}&+&2x_{2}&-&x_{3}&=&1\\2x_{1}&-&2x_{2}&+&4x_{3}&=&-2\\-x_{1}&+&{1 \over 2}x_{2}&-&x_{3}&=&0\end{matrix}}}$

For all three equations are fulfilled, it is a solution of the system. In contrast to the solution of a single equation (consisting of a single number), a solution must consist of an n-tuple , in this case a number triple. This is also known as the solution vector . ${\displaystyle x_{1}=1,\ x_{2}=-2,\ x_{3}=-2}$

In general, a linear system of equations with equations and unknowns can always be expressed in the following form: ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle {\begin{matrix}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 &\\a_{m1}x_{1}+a_{m2}x_{2}\,+&\cdots &+\,a_{mn}x_{n}&=&b_{m}\\\end{matrix}}}$

Systems of linear equations are called homogeneous if all are equal to 0 , otherwise inhomogeneous. Homogeneous systems of equations always have at least the so-called trivial solution, in which all variables are equal to 0. In the case of inhomogeneous systems of equations, on the other hand, the case may arise that no solution exists at all. ${\displaystyle b_{i}}$

example

The graphs of the question that intersect at point A (46; 16).

Linear systems of equations often arise as models of practical tasks. A typical example from school mathematics is as follows:

“A father and a son are 62 years old together. Six years ago the father was four times as old as the son then. How old is everyone? "

It can also be described by the following system of linear equations:

${\displaystyle {\begin{matrix}I.&v+s&=&62\\{\mathit {II.}}&v-6&=&4\cdot (s-6)\end{matrix}}}$

The variable here represents the age of the father and the variable that of the son. In a first step, the system of equations is usually brought into a standard form in which there are only terms with variables on the left and the pure numbers on the right. In this example, the second equation is multiplied out and rearranged. ${\displaystyle v}$ ${\displaystyle s}$

${\displaystyle {\begin{matrix}I.&v&+&s&=&62\\{\mathit {II}}.&v&-&4s&=&-18\end{matrix}}}$

To solve this system of equations, a variety of solution methods ( see Solving Methods ) can be used. The addition method is used here as an example . To first eliminate the variable , the first equation is subtracted from the second. ${\displaystyle v}$

${\displaystyle {\begin{aligned}v-4s-(v+s)&=-18-62\\-5s&=-80\\\end{aligned}}}$

The resulting equation is solved for the variable by dividing both sides by . That gives the age of the son, who is 16 years old. This value for is put back into the first equation. ${\displaystyle s}$ ${\displaystyle -5}$ ${\displaystyle s}$ ${\displaystyle s}$

${\displaystyle v+16=62}$

Solving the equation for the variable can calculate the age of the father, who is 46 years old. ${\displaystyle v}$

Matrix shape

For the treatment of linear systems of equations it is useful to combine all coefficients into a matrix of the so-called coefficient matrix : ${\displaystyle a_{ij}}$ ${\displaystyle A,}$

${\displaystyle A={\begin{pmatrix}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{pmatrix}}}$

Furthermore, all unknowns and the right-hand side of the system of equations can be combined to form single-column matrices (these are column vectors ):

${\displaystyle x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}};\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{pmatrix}}}$

This means that a linear system of equations using matrix-vector multiplication is short

${\displaystyle A\cdot x=b.}$

Both the coefficients , the unknowns and those come from the same body . In particular, ${\displaystyle a_{ij}}$ ${\displaystyle x_{j}}$ ${\displaystyle b_{i}}$ ${\displaystyle K}$

${\displaystyle A\in K^{{m}\times {n}},}$ ${\displaystyle b\in K^{m}}$ and ${\displaystyle x\in K^{n}.}$

It is not necessary to specify the unknowns to define a linear system of equations. It is sufficient to specify the extended coefficient matrix that results when a column with the right side of the system of equations is added to the coefficient matrix: ${\displaystyle A}$ ${\displaystyle b}$

${\displaystyle \left({\begin{array}{c|c}A&b\end{array}}\right)=\left({\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right)}$

Solvability

A vector is a solution of the linear system of equations if holds. Whether and how many solutions a system of equations has is different. In the case of linear systems of equations over an infinite body , three cases can arise: ${\displaystyle x}$ ${\displaystyle A\cdot x=b}$ ${\displaystyle K}$

• The system of linear equations has no solution; that is, the solution set is the empty set.
• The system of linear equations has exactly one solution, i. That is, the solution set contains exactly one element.
• The system of linear equations has an infinite number of solutions. In this case, the solution set contains an infinite number of n-tuples that satisfy all equations of the system.

Over a finite field, the number of solutions is a power of the power of . ${\displaystyle K}$

Solvability criteria

A linear system of equations is solvable if the rank of the coefficient matrix is equal to the rank of the augmented coefficient matrix is ( set of Kronecker Capelli ). If the rank of the coefficient matrix is ​​equal to the rank of the extended coefficient matrix and also equal to the number of unknowns, the system of equations has exactly one solution. ${\displaystyle A}$ ${\displaystyle (A\mid b)}$

In the case of a quadratic system of equations, i.e. in the case (see below), the determinant provides information about the solvability. The system of equations can be solved uniquely if and only if the value of the determinant of the coefficient matrix is ​​not equal to zero. However, if the value is zero, the solvability depends on the values ​​of the secondary determinants. In each of these, one column of the coefficient matrix is ​​replaced by the column on the right-hand side (the vector  ). Only if all secondary determinants have the value zero can the system have an infinite number of solutions, otherwise the system of equations is unsolvable. ${\displaystyle m=n}$ ${\displaystyle b}$

In particular, systems of equations with more equations than unknowns, so-called overdetermined systems of equations , often have no solution. For example, the following system of equations has no solution because both equations cannot be satisfied: ${\displaystyle x_{1}}$

${\displaystyle {\begin{matrix}3x_{1}&=&2\\4x_{1}&=&2\end{matrix}}}$

Approximate solutions of overdetermined systems of equations are then mostly defined and determined using the adjustment calculation .

That a linear system of equations has an infinite number of solutions can only happen if there are fewer linearly independent equations than unknowns and the underlying body contains an infinite number of elements. For example, the following system of equations (consisting of only one equation) has an infinite number of solutions, namely all vectors with ${\displaystyle K}$ ${\displaystyle x_{2}=1-x_{1}:}$

${\displaystyle x_{1}+x_{2}=1}$

Solution set

The solution set of a linear system of equations consists of all vectors for which is fulfilled: ${\displaystyle x,}$ ${\displaystyle Ax=b}$

${\displaystyle L=\left\{x\mid Ax=b\right\}}$

If there is a homogeneous linear system of equations, its solution set forms a subspace of. Thus, the superposition property applies , according to which for one or more solutions their linear combinations (with any ) solutions of the system of equations also apply . The solution set is therefore also called the solution space and is identical to the core of the matrix. Describes the rank of the matrix,  then according to the rank theorem the dimension of the solution space is equal to the defect of the matrix  ${\displaystyle L}$ ${\displaystyle K^{n}.}$ ${\displaystyle x_{i}\in K^{n}}$ ${\displaystyle \textstyle \sum \alpha _{i}\,x_{i}}$ ${\displaystyle \alpha _{i}\in K}$  ${\displaystyle A.}$ ${\displaystyle r}$ ${\displaystyle A,}$ ${\displaystyle d=n-r}$ ${\displaystyle A.}$

If the solution set of an inhomogeneous system of linear equations is not empty, then it is an affine subspace of It then has the form where is the solution space of the associated homogeneous system of equations and any solution of the inhomogeneous system of equations. An inhomogeneous system of equations can therefore be solved uniquely if the zero vector is the only solution (“trivial solution”) of the homogeneous system of equations. In particular, either or with applies ${\displaystyle K^{n}.}$ ${\displaystyle v+U,}$ ${\displaystyle U}$ ${\displaystyle v}$ ${\displaystyle L=\emptyset }$ ${\displaystyle \operatorname {dim} (L)=n-r}$ ${\displaystyle r=\operatorname {Rang} (A).}$

The solution set of a linear system of equations does not change if one of the three elementary line transformations is carried out:

1. Swap two lines
2. Multiply a row by a number other than zero
3. Add a row (or a multiple of a row) to another row

The set of solutions of a quadratic linear system of equations does not change even if the system of equations is multiplied by a regular matrix .

Determination via the extended coefficient matrix

The form of the solution set can basically be determined with the help of the extended coefficient matrix, in which it is brought into step form with the help of elementary line transformations (see Gauss method ):

${\displaystyle \left({\begin{array}{cccccc|c}a_{11}&a_{12}&\cdots &a_{1k}&\cdots &a_{1n}&b_{1}\\0&a_{22}&\cdots &a_{2k}&\cdots &a_{2n}&b_{2}\\\vdots &\ddots &\ddots &\vdots &\ddots &\vdots &\vdots \\0&\cdots &0&a_{kk}&\cdots &a_{kn}&b_{k}\\\vdots &\ddots &\vdots &0&\cdots &0&\vdots \\0&\cdots &0&0&\cdots &0&b_{m}\\\end{array}}\right)}$

In order to always get exactly this form, you sometimes have to swap columns. Swap columns change the order of the variables, which you have to consider at the end. It is also assumed here that the coefficients are not zero. ${\displaystyle a_{jj},j=1,\dotsc ,k}$

The number of solutions can then be read from the: ${\displaystyle b_{i}}$

• If at least one of the is not equal to zero, there is no solution. ${\displaystyle b_{k+1},\dotsc ,b_{m}}$
• If all are zero (or ), then: ${\displaystyle b_{k+1},\dotsc ,b_{m}}$ ${\displaystyle k=m}$
  • If , then the system of equations can be solved uniquely. ${\displaystyle k=n}$
  • Is there are infinite solutions. The solution space has the dimension . ${\displaystyle k<n}$ ${\displaystyle n-k}$

With further elementary line transformations (see Gauss-Jordan method ) the matrix can be given the following form:

${\displaystyle \left({\begin{array}{ccccccc|c}1&0&\cdots &0&a_{1,k+1}&\cdots &a_{1n}&b_{1}\\0&1&\ddots &0&a_{2,k+1}&\cdots &a_{2n}&b_{2}\\\vdots &\ddots &\ddots &\vdots &\vdots &\ddots &\vdots &\vdots \\0&\cdots &0&1&a_{k,k+1}&\cdots &a_{kn}&b_{k}\\\vdots &\ddots &\vdots &0&\cdots &\cdots &0&\vdots \\0&\cdots &0&0&\cdots &\cdots &0&b_{m}\\\end{array}}\right)}$

If there is a solution at all ( ), the following applies to the solution set : ${\displaystyle b_{k+1},\dotsc ,b_{m}=0}$ ${\displaystyle \mathbb {L} }$

${\displaystyle \mathbb {L} =\left\{{\begin{array}{c|c}\left({\begin{array}{c}b_{1}\\\vdots \\b_{k}\\0\\\vdots \\0\\\end{array}}\right)+\left({\begin{array}{cccc}-a_{1,k+1}&-a_{1,k+2}&\cdots &-a_{1n}\\\vdots &\ddots &\ddots &\vdots \\-a_{k,k+1}&-a_{k,k+2}&\cdots &-a_{kn}\\1&0&\cdots &0\\0&1&\ddots &\vdots \\\vdots &\ddots &\ddots &0\\0&\cdots &\cdots &1\\\end{array}}\right)\cdot {\begin{pmatrix}s_{k+1}\\s_{k+2}\\\vdots \\s_{n}\end{pmatrix}}&{\begin{pmatrix}s_{k+1}\\s_{k+2}\\\vdots \\s_{n}\end{pmatrix}}\in K^{n-k}\end{array}}\right\}}$

Here is the vector of the free variables. ${\displaystyle s={\begin{pmatrix}s_{k+1}\\s_{k+2}\\\vdots \\s_{n}\end{pmatrix}}}$

Forms of systems of equations

Systems of linear equations can exist in forms in which they can be easily solved. In many cases, any system of equations is brought into a suitable form using an algorithm in order to subsequently find a solution.

Square

We speak of a quadratic system of equations if the number of unknowns is equal to the number of equations. A system of equations of this form can be solved uniquely if the rows or columns are linearly independent (solution methods are discussed below).

Step shape, stair shape

In the step form (also line step form, line normal form, step form, graduated form, stair form, stair step form or stair normal form) the number of unknowns is reduced by at least one in each line, which then no longer occurs in the following lines. Using the Gaussian elimination method, any system of equations can be converted into this form.

Example (the coefficients of omitted elements are ): ${\displaystyle 0}$

${\displaystyle {\begin{matrix}6x_{1}&+&3x_{2}&+&4x_{3}&=&1\\&&&-&5x_{3}&=&10\end{matrix}}}$

Linear systems of equations in step form can be solved by inserting them backwards (back substitution). Starting with the last line, the unknown is calculated and the result obtained is inserted in the line above to calculate the next unknown.

Solution to the above example:

1. Resolve the second line after ${\displaystyle x_{3}:}$

   ${\displaystyle x_{3}={\frac {10}{-5}}=-2}$

2. Inserting in the first line: ${\displaystyle x_{3}}$

   ${\displaystyle 6x_{1}+3x_{2}+4\cdot (-2)=1}$

3. Resolve the first line after ${\displaystyle x_{2}:}$

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

4. With all vectors of the form are solutions of the system of equations. ${\displaystyle x_{1}=t}$ ${\displaystyle {\begin{pmatrix}t\\-2t+3\\-2\end{pmatrix}}}$

Triangular shape

The triangular shape is a special case of the step shape, in which each line has exactly one less unknown than the previous one. This means that all the coefficients of the main diagonal are different from . The triangular shape arises when the Gaussian elimination method is used if the system of equations has exactly one solution. ${\displaystyle a_{ii}}$ ${\displaystyle 0}$

Example (the coefficients of omitted elements are ): ${\displaystyle 0}$

${\displaystyle {\begin{matrix}6x_{1}&+&3x_{2}&+&4x_{3}&=&1\\&&8x_{2}&+&5x_{3}&=&-1\\&&&-&2x_{3}&=&6\end{matrix}}}$

Like linear systems of equations in step form, those in triangular form can also be solved by inserting them backwards.

Reduced step shape

The reduced step form (also standardized line step form) is a special case of the step form. The first unknowns of each line appear only once and have the coefficient The reduced step form of a linear system of equations is unambiguous: there is exactly one reduced step form for every linear system of equations. Using the Gauss-Jordan algorithm , any linear system of equations can be brought into this form. ${\displaystyle 1.}$

Example (the coefficients of omitted elements are ): ${\displaystyle 0}$

${\displaystyle {\begin{matrix}x_{1}&&&&&+&4x_{4}&=&-1\\&&x_{2}&&&-&5x_{4}&=&-9\\&&&&x_{3}&-&7x_{4}&=&10\end{matrix}}}$

The solution of the linear system of equations can now be read off directly: If set and the system of equations is solved recursively, all vectors of the form result as solutions. ${\displaystyle x_{4}=t}$ ${\displaystyle (-4t-1,5t-9,7t+10,t)^{T}}$

Other forms

In practice, the special cases of thinly populated matrices (very large matrices with relatively few non-zero elements) and ribbon matrices (also large matrices whose non-vanishing elements are concentrated around the main diagonal), which can be treated with specially adapted solution methods (see below), are relevant .

Solution method

The methods for solving systems of linear equations are divided into iterative and direct methods. Examples of direct methods are the substitution method , the equation method and the addition method for simple systems of equations as well as the Gaussian elimination method based on the addition method, which brings a system of equations into step form. A variant of the Gaussian method is the Cholesky decomposition , which only works for symmetric , positively definite matrices . The QR decomposition , which is more stable , takes twice as much effort as the Gauss method . The Cramer's rule used determinants to generate formulas for the solution of a quadratic linear system when it has a unique solution. However, it is not suitable for numerical calculation due to the high computational effort.

Iterative methods are, for example, the Gauß-Seidel and Jacobi methods belonging to the class of splitting methods . These do not converge for every matrix and are very slow for many practical problems. More modern methods are, for example, preconditioned Krylow subspace methods , which are particularly fast for large sparse matrices , as well as multi-grid methods for solving systems that come from the discretization of certain partial differential equations .

Applications (e.g. geodesy ) often take measurements of different types and, to reduce the impact of measurement errors , more measurements are taken than unknowns need to be determined. Each measurement provides an equation to determine the unknown. If these equations are not all linear, the system of equations is linearized using known approximations of the unknowns . Then instead of the actual unknowns, their small deviations from the approximate values ​​must be determined. Usually, when there are more equations than unknowns, the equations contradict each other so there is no strict solution. As a way out, a solution is then usually determined by means of an adjustment using the least squares method , which typically does not exactly satisfy any equation, but provides an optimal approximation of the “true” measured variables based on reasonable assumptions about the measurement errors.

The currently best known asymptotic upper bound of arithmetic operations for solving any linear system of equations is provided by a practically inapplicable algorithm by Don Coppersmith and Shmuel Winograd from 1990, which solves a system in O (n ^2,376 ) . It is clear that at least O (n ² ) operations are necessary; not, however, whether this lower bound can also be reached. ${\displaystyle n\times n}$

Almost singular linear systems of equations can be solved passably in a numerical way by singular value decomposition .

literature

• G. Frobenius : On the theory of linear equations. In: Journal for pure and applied mathematics (= Crelle's Journal.) Vol. 129, 1905 ISSN  0075-4102 , pp. 175-180, digitized.
• Andreas Meister: Numerics of linear systems of equations. An introduction to modern procedures. 2nd, revised edition. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7 .
• Falko Lorenz: Linear Algebra. Volume 1, 4th edition. Spektrum Akademischer Verlag, Heidelberg et al. 2003, ISBN 3-8274-1406-7 .
• Gerd Fischer : Linear Algebra. 15th, improved edition. Vieweg, Wiesbaden 2005, ISBN 3-8348-0031-7 .

Web links

• PDF collection on gecco.info. Detailed description of various possible solutions for linear systems of equations (simple, without matrices).
• Arndt Brünner Scripts. Online calculator for solving systems of linear equations.
• Online solver for systems of linear equations (English, but supports parameters).
• Introduction to the three solution methods (video) for pupils and students.

Individual evidence

1. ^ Gene H. Golub , Charles F. Van Loan: Matrix Computations. 3rd edition, reprint. Johns Hopkins University Press, Baltimore MD et al. 1996, ISBN 0-8018-5414-8 .