In mathematics, Gaussian elimination, also known as row reduction, is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for solving
systems of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in th ...
. It consists of a sequence of operations performed on the corresponding
matrix
Matrix most commonly refers to:
* ''The Matrix'' (franchise), an American media franchise
** ''The Matrix'', a 1999 science-fiction action film
** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
of coefficients. This method can also be used to compute the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
of a matrix, the
determinant
In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...
of a
square matrix
In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of order Any two square matrices of the same order can be added and multiplied.
Square matrices are often ...
, and the inverse of an
invertible matrix
In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that
:\mathbf = \mathbf = \mathbf_n \
where denotes the -by- identity matrix and the multiplicati ...
. The method is named after
Carl Friedrich Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
(1777–1855) although some special cases of the method—albeit presented without proof—were known to
Chinese mathematicians
Mathematics in China emerged independently by the 11th century BCE. The Chinese independently developed a real number system that includes significantly large and negative numbers, more than one numeral system ( base 2 and base 10), algebra, geomet ...
as early as circa 179 AD.
To perform row reduction on a matrix, one uses a sequence of
elementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multi ...
to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations:
* Swapping two rows,
* Multiplying a row by a nonzero number,
* Adding a multiple of one row to another row. (subtraction can be achieved by multiplying one row with -1 and adding the result to another row)
Using these operations, a matrix can always be transformed into an
upper triangular matrix
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
, and in fact one that is in
row echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian ...
. Once all of the leading coefficients (the leftmost nonzero entry in each row) are 1, and every column containing a leading coefficient has zeros elsewhere, the matrix is said to be in
reduced row echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian el ...
. This final form is unique; in other words, it is independent of the sequence of row operations used. For example, in the following sequence of row operations (where two elementary operations on different rows are done at the first and third steps), the third and fourth matrices are the ones in row echelon form, and the final matrix is the unique reduced row echelon form.
:
Using row operations to convert a matrix into reduced row echelon form is sometimes called Gauss–Jordan elimination. In this case, the term ''Gaussian elimination'' refers to the process until it has reached its upper triangular, or (unreduced) row echelon form. For computational reasons, when solving systems of linear equations, it is sometimes preferable to stop row operations before the matrix is completely reduced.
Definitions and example of algorithm
The process of row reduction makes use of
elementary row operations In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multi ...
, and can be divided into two parts. The first part (sometimes called forward elimination) reduces a given system to ''row echelon form'', from which one can tell whether there are no solutions, a unique solution, or infinitely many solutions. The second part (sometimes called
back substitution
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
) continues to use row operations until the solution is found; in other words, it puts the matrix into ''reduced'' row echelon form.
Another point of view, which turns out to be very useful to analyze the algorithm, is that row reduction produces a
matrix decomposition
In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of ...
of the original matrix. The elementary row operations may be viewed as the multiplication on the left of the original matrix by
elementary matrices. Alternatively, a sequence of elementary operations that reduces a single row may be viewed as multiplication by a
Frobenius matrix
A Frobenius matrix is a special kind of square matrix from numerical mathematics. A matrix is a Frobenius matrix if it has the following three properties:
* all entries on the main diagonal are ones
* the entries below the main diagonal of at most ...
. Then the first part of the algorithm computes an
LU decomposition
In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix decomposition). The product sometimes includes a pe ...
, while the second part writes the original matrix as the product of a uniquely determined invertible matrix and a uniquely determined reduced row echelon matrix.
Row operations
There are three types of elementary row operations which may be performed on the rows of a matrix:
# Swap the positions of two rows.
# Multiply a row by a non-zero
scalar
Scalar may refer to:
*Scalar (mathematics), an element of a field, which is used to define a vector space, usually the field of real numbers
* Scalar (physics), a physical quantity that can be described by a single element of a number field such ...
.
# Add to one row a scalar multiple of another.
If the matrix is associated to a system of linear equations, then these operations do not change the solution set. Therefore, if one's goal is to solve a system of linear equations, then using these row operations could make the problem easier.
Echelon form
For each row in a matrix, if the row does not consist of only zeros, then the leftmost nonzero entry is called the ''
leading coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
'' (or ''pivot'') of that row. So if two leading coefficients are in the same column, then a row operation of
type 3 could be used to make one of those coefficients zero. Then by using the row swapping operation, one can always order the rows so that for every non-zero row, the leading coefficient is to the right of the leading coefficient of the row above. If this is the case, then matrix is said to be in row echelon form. So the lower left part of the matrix contains only zeros, and all of the zero rows are below the non-zero rows. The word "echelon" is used here because one can roughly think of the rows being ranked by their size, with the largest being at the top and the smallest being at the bottom.
For example, the following matrix is in row echelon form, and its leading coefficients are shown in red:
:
It is in echelon form because the zero row is at the bottom, and the leading coefficient of the second row (in the third column), is to the right of the leading coefficient of the first row (in the second column).
A matrix is said to be in reduced row echelon form if furthermore all of the leading coefficients are equal to 1 (which can be achieved by using the elementary row operation of type 2), and in every column containing a leading coefficient, all of the other entries in that column are zero (which can be achieved by using elementary row operations of type 3).
Example of the algorithm
Suppose the goal is to find and describe the set of solutions to the following
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three ...
:
:
The table below is the row reduction process applied simultaneously to the system of equations and its associated
augmented matrix
In linear algebra, an augmented matrix is a matrix obtained by appending the columns of two given matrices, usually for the purpose of performing the same elementary row operations on each of the given matrices.
Given the matrices and , where
...
. In practice, one does not usually deal with the systems in terms of equations, but instead makes use of the augmented matrix, which is more suitable for computer manipulations. The row reduction procedure may be summarized as follows: eliminate from all equations below , and then eliminate from all equations below . This will put the system into
triangular form
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
. Then, using back-substitution, each unknown can be solved for.
:
The second column describes which row operations have just been performed. So for the first step, the is eliminated from by adding to . Next, is eliminated from by adding to . These row operations are labelled in the table as
:
Once is also eliminated from the third row, the result is a system of linear equations in triangular form, and so the first part of the algorithm is complete. From a computational point of view, it is faster to solve the variables in reverse order, a process known as back-substitution. One sees the solution is , , and . So there is a unique solution to the original system of equations.
Instead of stopping once the matrix is in echelon form, one could continue until the matrix is in ''reduced'' row echelon form, as it is done in the table. The process of row reducing until the matrix is reduced is sometimes referred to as Gauss–Jordan elimination, to distinguish it from stopping after reaching echelon form.
History
The method of Gaussian elimination appears – albeit without proof – in the Chinese mathematical text
Chapter Eight: ''Rectangular Arrays'' of ''
The Nine Chapters on the Mathematical Art
''The Nine Chapters on the Mathematical Art'' () is a Chinese mathematics book, composed by several generations of scholars from the 10th–2nd century BCE, its latest stage being from the 2nd century CE. This book is one of the earliest sur ...
''. Its use is illustrated in eighteen problems, with two to five equations. The first reference to the book by this title is dated to 179 AD, but parts of it were written as early as approximately 150 BC.
It was commented on by
Liu Hui
Liu Hui () was a Chinese mathematician who published a commentary in 263 CE on ''Jiu Zhang Suan Shu (The Nine Chapters on the Mathematical Art).'' He was a descendant of the Marquis of Zixiang of the Eastern Han dynasty and lived in the state o ...
in the 3rd century.
The method in Europe stems from the notes of
Isaac Newton
Sir Isaac Newton (25 December 1642 – 20 March 1726/27) was an English mathematician, physicist, astronomer, alchemist, theologian, and author (described in his time as a "natural philosopher"), widely recognised as one of the grea ...
. In 1670, he wrote that all the algebra books known to him lacked a lesson for solving simultaneous equations, which Newton then supplied. Cambridge University eventually published the notes as ''Arithmetica Universalis'' in 1707 long after Newton had left academic life. The notes were widely imitated, which made (what is now called) Gaussian elimination a standard lesson in algebra textbooks by the end of the 18th century.
Carl Friedrich Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
in 1810 devised a notation for symmetric elimination that was adopted in the 19th century by professional
hand computers to solve the normal equations of least-squares problems. The algorithm that is taught in high school was named for Gauss only in the 1950s as a result of confusion over the history of the subject.
Some authors use the term ''Gaussian elimination'' to refer only to the procedure until the matrix is in echelon form, and use the term Gauss–Jordan elimination to refer to the procedure which ends in reduced echelon form. The name is used because it is a variation of Gaussian elimination as described by
Wilhelm Jordan Wilhelm Jordan may refer to:
* Carl Friedrich Wilhelm Jordan (1819–1904), known as Wilhelm Jordan, German writer and politician
* Wilhelm Jordan (geodesist) (1842–1899), German scientist, noted for the Gauss–Jordan elimination algorithm
{{hn ...
in 1888. However, the method also appears in an article by Clasen published in the same year. Jordan and Clasen probably discovered Gauss–Jordan elimination independently.
Applications
Historically, the first application of the row reduction method is for solving
systems of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in th ...
. Here are some other important applications of the algorithm.
Computing determinants
To explain how Gaussian elimination allows the computation of the determinant of a square matrix, we have to recall how the elementary row operations change the determinant:
* Swapping two rows multiplies the determinant by −1
* Multiplying a row by a nonzero scalar multiplies the determinant by the same scalar
* Adding to one row a scalar multiple of another does not change the determinant.
If Gaussian elimination applied to a square matrix produces a row echelon matrix , let be the product of the scalars by which the determinant has been multiplied, using the above rules. Then the determinant of is the quotient by of the product of the elements of the diagonal of :
:
Computationally, for an matrix, this method needs only arithmetic operations, while using
Leibniz formula for determinants
In algebra, the Leibniz formula, named in honor of Gottfried Leibniz, expresses the determinant of a square matrix in terms of permutations of the matrix elements. If A is an n \times n matrix, where a_ is the entry in the i-th row and j-th column ...
requires operations (number of summands in the formula), and
recursive
Laplace expansion
In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an matrix as a weighted sum of minors, which are the determinants of some submatrices of . Spec ...
requires operations (number of sub-determinants to compute, if none is computed twice). Even on the fastest computers, these two methods are impractical or almost impracticable for above 20.
Finding the inverse of a matrix
A variant of Gaussian elimination called Gauss–Jordan elimination can be used for finding the inverse of a matrix, if it exists. If is an square matrix, then one can use row reduction to compute its
inverse matrix
In linear algebra, an -by- square matrix is called invertible (also nonsingular or nondegenerate), if there exists an -by- square matrix such that
:\mathbf = \mathbf = \mathbf_n \
where denotes the -by- identity matrix and the multiplicati ...
, if it exists. First, the
identity matrix
In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere.
Terminology and notation
The identity matrix is often denoted by I_n, or simply by I if the size is immaterial o ...
is augmented to the right of , forming an
block matrix
In mathematics, a block matrix or a partitioned matrix is a matrix that is '' interpreted'' as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original mat ...
. Now through application of elementary row operations, find the reduced echelon form of this matrix. The matrix is invertible if and only if the left block can be reduced to the identity matrix ; in this case the right block of the final matrix is . If the algorithm is unable to reduce the left block to , then is not invertible.
For example, consider the following matrix:
:
To find the inverse of this matrix, one takes the following matrix augmented by the identity and row-reduces it as a 3 × 6 matrix:
:
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is
:
One can think of each row operation as the left product by an
elementary matrix In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL''n''(F) when F is a field. Left multiplication (pre-multip ...
. Denoting by the product of these elementary matrices, we showed, on the left, that , and therefore, . On the right, we kept a record of , which we know is the inverse desired. This procedure for finding the inverse works for square matrices of any size.
Computing ranks and bases
The Gaussian elimination algorithm can be applied to any matrix . In this way, for example, some 6 × 9 matrices can be transformed to a matrix that has a row echelon form like
:
where the stars are arbitrary entries, and are nonzero entries. This echelon matrix contains a wealth of information about : the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
of is 5, since there are 5 nonzero rows in ; the
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
spanned by the columns of has a basis consisting of its columns 1, 3, 4, 7 and 9 (the columns with in ), and the stars show how the other columns of can be written as linear combinations of the basis columns. This is a consequence of the distributivity of the
dot product
In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an algebra ...
in the expression of a linear map
as a matrix.
All of this applies also to the reduced row echelon form, which is a particular row echelon format.
Computational efficiency
The number of arithmetic operations required to perform row reduction is one way of measuring the algorithm's computational efficiency. For example, to solve a system of equations for unknowns by performing row operations on the matrix until it is in echelon form, and then solving for each unknown in reverse order, requires divisions, multiplications, and subtractions, for a total of approximately operations. Thus it has
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
complexity of ; see
Big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
.
This arithmetic complexity is a good measure of the time needed for the whole computation when the time for each arithmetic operation is approximately constant. This is the case when the coefficients are represented by
floating-point number
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be r ...
s or when they belong to a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
. If the coefficients are
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s or
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s exactly represented, the intermediate entries can grow exponentially large, so the
bit complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
is exponential.
However, there is a variant of Gaussian elimination, called the
Bareiss algorithm In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm to calculate the determinant or the echelon form of a matrix with integer entries using only integer arithmetic; any divisions that are performed are guaranteed to be ...
, that avoids this exponential growth of the intermediate entries and, with the same arithmetic complexity of , has a bit complexity of .
This algorithm can be used on a computer for systems with thousands of equations and unknowns. However, the cost becomes prohibitive for systems with millions of equations. These large systems are generally solved using
iterative method
In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived fr ...
s. Specific methods exist for systems whose coefficients follow a regular pattern (see
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three ...
).
To put an matrix into reduced echelon form by row operations, one needs arithmetic operations, which is approximately 50% more computation steps.
One possible problem is
numerical instability
In the mathematics, mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the oth ...
, caused by the possibility of dividing by very small numbers. If, for example, the leading coefficient of one of the rows is very close to zero, then to row-reduce the matrix, one would need to divide by that number. This means that any error existed for the number that was close to zero would be amplified. Gaussian elimination is numerically stable for
diagonally dominant
In mathematics, a square matrix is said to be diagonally dominant if, for every row of the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the other (non-diagonal) entries in that row ...
or
positive-definite In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular:
* Positive-definite bilinear form
* Positive-definite fu ...
matrices. For general matrices, Gaussian elimination is usually considered to be stable, when using
partial pivoting
The pivot or pivot element is the element of a matrix, or an array, which is selected first by an algorithm (e.g. Gaussian elimination, simplex algorithm, etc.), to do certain calculations. In the case of matrix algorithms, a pivot entry is usuall ...
, even though there are examples of stable matrices for which it is unstable.
Generalizations
Gaussian elimination can be performed over any
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
, not just the real numbers.
Buchberger's algorithm
In the theory of multivariate polynomials, Buchberger's algorithm is a method for transforming a given set of polynomials into a Gröbner basis, which is another set of polynomials that have the same common zeros and are more convenient for extract ...
is a generalization of Gaussian elimination to
systems of polynomial equations. This generalization depends heavily on the notion of a
monomial order. The choice of an ordering on the variables is already implicit in Gaussian elimination, manifesting as the choice to work from left to right when selecting pivot positions.
Computing the rank of a tensor of order greater than 2 is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
.
Therefore, if , there cannot be a polynomial time analog of Gaussian elimination for higher-order
tensors
In mathematics, a tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such as vectors, scalars, and even other tensor ...
(matrices are
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
representations of order-2 tensors).
Pseudocode
As explained above, Gaussian elimination transforms a given matrix into a matrix in
row-echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian e ...
.
In the following
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
,
A, j
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
/code> denotes the entry of the matrix in row and column with the indices starting from 1. The transformation is performed ''in place'', meaning that the original matrix is lost for being eventually replaced by its row-echelon form.
h := 1 /* ''Initialization of the pivot row'' */
k := 1 /* ''Initialization of the pivot column'' */
while h ≤ m and k ≤ n
/* ''Find the k-th pivot:'' */
i_max := argmax (i = h ... m, abs(A , k)
if A _max, k= 0
/* ''No pivot in this column, pass to next column'' */
k := k + 1
else
swap rows(h, i_max)
/* ''Do for all rows below pivot:'' */
for i = h + 1 ... m:
f := A , k/ A , k /* ''Fill with zeros the lower part of pivot column:'' */
A , k:= 0
/* ''Do for all remaining elements in current row:'' */
for j = k + 1 ... n:
A, j
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
:= A, j
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
- A, j
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
* f
/* ''Increase pivot row and column'' */
h := h + 1
k := k + 1
This algorithm differs slightly from the one discussed earlier, by choosing a pivot with largest absolute value
In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
. Such a ''partial pivoting'' may be required if, at the pivot place, the entry of the matrix is zero. In any case, choosing the largest possible absolute value of the pivot improves the numerical stability
In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorit ...
of the algorithm, when floating point
In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be ...
is used for representing numbers.
Upon completion of this procedure the matrix will be in row echelon form
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian ...
and the corresponding system may be solved by back substitution
In mathematics, a triangular matrix is a special kind of square matrix. A square matrix is called if all the entries ''above'' the main diagonal are zero. Similarly, a square matrix is called if all the entries ''below'' the main diagonal are ...
.
See also
*Fangcheng (mathematics)
Fangcheng (sometimes written as fang-cheng or fang cheng) () is the title of the eighth chapter of the Chinese mathematical classic Jiuzhang suanshu (The Nine Chapters on the Mathematical Art) composed by several generations of scholars who flo ...
References
Works cited
* .
* .
* .
* .
* .
* .
*
*
* .
* .
*
* .
*
External links
Interactive didactic tool
{{Authority control
Numerical linear algebra
Articles with example pseudocode
Exchange algorithms