请输入您要查询的字词:

 

单词 LUDecomposition
释义

LU decomposition


Definition 1

Let A be an n×m matrix. An LU decompositionMathworldPlanetmath (sometimes also called an LU factorization) of A, if itexists, is an n×n unit lower triangular matrix L and ann×m matrix U, in (upper) echelon formMathworldPlanetmath, such that

A=LU

The LU factorization is closely related to the row reductionalgorithmMathworldPlanetmath. In a very real sense, the factorization is a record of thesteps taken in row reducing a matrix to echelon form. The matrixL “encodes” the sequence of row replacement operationsMathworldPlanetmath that rowreduce the given matrix A to echelon form U.

Proposition 2

Suppose that A=LU is an LU factorization, and let Lij denotethe entries of L. Then, the row reductionAρU is accomplished by thefollowing sequence ρ of 12n(n-1) row replacementoperations:

rowjrowj-Lj1row1,j=2,,n;
rowjrowj-Lj2row2,j=3,,n;
         
rowjrowj-Ljkrowk,j=k+1,,n,k=1,,n-1
         

Note: the first n-1 steps clear out column 1, the next n-2 stepsclear out column 2, etc.

Proposition 3

Not every matrix admits an LU factorization. Indeed, an LUfactorization exists if and only if A can be reduced to echelonwithout using row exchange operations. However, if an LUfactorization exists, then it is unique.

In the most general case, one has to employ row exchange operations.

Proposition 4

Let A be an n×m matrix. Then, there exists an n×npermutation matrixMathworldPlanetmath P (indeed, many such) such that the matrix PAadmits an LU factorization, i.e., there exist matrices P,L,Usuch that

PA=LU.

The key idea behind LU factorization is that one does not need toemploy row scalings to do row reduction until the second half (theback-substitution phase) of the algorithm. This has significantimplicationMathworldPlanetmath for numerical stability of the algorithm.

The LU decomposition of a given matrix A is useful for the solutionof the systems of linear equations of the form Ax=b. Indeed, itsuffices to first solve the linear system Ly=b, and second, to solvethe system Ux=y. This two-step procedure is easy to implement,because owing to the lower and upper-triangular nature of thematrices L and U, the required row operations are determined, moreor less, directly from the entries of L and U. Indeed, the firststep,

[Lb]ρ1[Iy]

a sequence of row operations ρ1, and the second step

[Uy]ρ2[Ex0]

a sequence of row operations ρ2, are exactly the same row operationsone has to perform to row reduce A directly to reduced echelon form E:

[Ab]ρ1[Uy]ρ2[Ex0].

Note: x0 is the particular solution of Ax=b that sits in therightmost colulmn of the augmented matrix at the termination of therow-reduction algorithm.

随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 0:10:43