请输入您要查询的字词:

 

单词 RowReduction
释义

row reduction


Row reduction, also known as Gaussian elimination, is an algorithm for solving a system of linear equations

a11x1+a12x2++a1mxm=b1a21x1+a22x2++a2mxm=b2an1x1+an2x2++anmxm=bn

To describe row reduction, it is convenient to formulate a linearsystem as a single matrix-vector equation Ax=b, where

A=[a11a12a1ma21a22a2man1an2anm],b=[b1b2bn],x=[x1x2xm]

are, respectively, the n×m matrix of coefficients of thelinear system, the n-place column vectorMathworldPlanetmath of the scalars from theright-hand of the equations, and the m-place column vector ofunknowns.

The method consists of combining the coefficient matrix A with theright hand vector b to form the “augmented” n×(m+1) matrix

[Ab]=[a11a12a1mb1a21a22a2mb2an1an2anmbn]=[R1R2Rn,]

where each Ri is the m+1-place row vector corresponding to rowi of the augmented matrix.

A sequence of elementary row operations is then applied to this matrixso as to transform it to row echelon formMathworldPlanetmath. The elementary operations are:

  • row scaling: the multiplication a row by a nonzeroscalar;

    RicRi,c0;
  • row exchange: the exchanges of two rows;

    RiRj;
  • row replacement: the addition of a multiple of one row toanother row;

    RiRi+cRj,c0,ij.

Note that these operationsMathworldPlanetmath are “legal” because x is a solution ofthe transformed system if and only if it is a solution of the initial system.

If the number of equations equals the number of variables (m=n), andif the coefficient matrix A is non-singular (http://planetmath.org/singularPlanetmathPlanetmath), then the algorithm willterminate when the augmented matrix has the following form:

[a11a12a1nb10a22a2nb200annbn]

With these assumptionsPlanetmathPlanetmath, there exists a unique solution, which can beobtained from the above matrix by back substitution.

For the general case, the termination procedure is somewhat morecomplicated. First recall that a matrix is in echelon form if eachrow has more leading zeros than the rows above it. A pivot is theleading non-zero entry of some row. We then have

  • If there is a pivot in the last column, the system isinconsistent ; there will be no solutions.

  • If that is not the case, then the general solution will have ddegrees of freedom, where d is the number of columns from 1 tom that have no pivot. To be more precise, the general solutionwill have the form of one particular solution plus an arbitrary linearcombinationMathworldPlanetmath of d linearly independentMathworldPlanetmath n-vectors.

    In even more prosaic languagePlanetmathPlanetmath, the variables in the non-pivotcolumns are to be considered “free variablesMathworldPlanetmathPlanetmath” and should be“moved” to the right-hand side of the equation. The generalsolution is then obtained by arbitrarily choosing values of the freevariables, and then solving for the remaining “non-free” variablesthat reside in the pivot columns.

A variant of Gaussian elimination is Gauss-Jordan elimination. Inthis variation we reduce to echelon form, and then if the systemproves to be consistent, continue to apply the elementary rowoperations until the augmented matrix is in reduced echelonform. This means that not only does each pivot have all zeroesbelow it, but that each pivot also has all zeroes above it.

In essence, Gauss-Jordan elimination performs the back substitution;the values of the unknowns can be read off directly from the terminalaugmented matrix. Not surprisingly, Gauss-Jordan elimination isslower than Gaussian elimination. It is useful, however, for solvingsystems on paper.

Titlerow reduction
Canonical nameRowReduction
Date of creation2013-03-22 12:06:48
Last modified on2013-03-22 12:06:48
Ownerrmilson (146)
Last modified byrmilson (146)
Numerical id18
Authorrmilson (146)
Entry typeAlgorithm
Classificationmsc 15A06
SynonymGaussian elimination
SynonymGauss-Jordan elimination
Related topicRowEchelonForm
Related topicReducedRowEchelonForm
Related topicElementaryMatrix
Definespivot
Definesrow operation
Definesrow exchange
Definesrow replacement
Definesrow scaling
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 16:35:28