Điều này dẫn đến một thuật toán phân hủy LU tổng quát cho một Quốc hội × NA nonsingular ma trận như mô tả trong khung bên dưới. Những thói quen MATLAB "lu_dcmp ()" thực hiện thuật toán để tìm thấy không chỉ các ma trận L / trên hình tam giác và U, nhưng cũng là ma trận P hoán vị. | 94 SYSTEM OF LINEAR EQUATIONS a11 a12 a13 step 1 a21 a22 a23 a31 a32 a33 11 an Z21 a21 11 Z31 a31 11 12 a12 1 __ a22 a22 - Z21 12 1 a32 a32 - Z31 12 13 a13 1 a23 a23 - Z21 13 1 a33 a33 - Z31 13 11 12 13 step 2 Z21 1 22 a22 1 23 a23 l31 l32 a3 12 22 2 1 l a33 a33 - l32 23 This leads to an LU decomposition algorithm generalized for an NA X NA nonsingular matrix as described in the following box. The MATLAB routine lu_dcmp implements this algorithm to find not only the lower upper triangular matrix L and U but also the permutation matrix P. We run it for a 3 X 3 matrix to get L U and P and then reconstruct the matrix P-LU A from L U and P to ascertain whether the result is right. function L U P lu_dcmp A This gives LU decomposition of A with the permutation matrix P denoting the row switch exchange during factorization NA size A 1 AP A eye NA augment with the permutation matrix. for k 1 NA - 1 Partial Pivoting at AP k k akx kx max abs AP k NA k if akx eps error Singular matrix and No LU decomposition1 end mx k kx-1 if kx 1 Row change if necessary tmp_row AP k AP k AP mx AP mx tmp_row end LU decomposition for m k 1 NA AP m k AP m k AP k k Eq. AP m k 1 NA AP m k 1 NA -AP m k AP k k 1 NA Eq. end end P AP 1 NA NA 1 NA NA Permutation matrix for m 1 NA for n 1 NA if m n L m m 1. U m m AP m m elseif m n L m n AP m n U m n 0. else L m n 0. U m n AP m n end end end if nargout 0 disp L U P Awith L U P end You can check if P L U A DECOMPOSITION FACTORIZATION 95 cf The number of floating-point multiplications required in this routine lu_dcmp is NA-1 NA-1 NA - k NA - k 1 NA NA 1 - 2NA 1 k k2 k 1 k 1 NA - 1 NA NA 1 - 1 2NA 1 NA - 1 NA 1 NA - 1 NA 2NA - 1 2 6 1 NA - 1 NA NA 1 1 NA3 with NA the size of matrix A 0. Initialize A 0 A or equivalently a n amn for m n 1 NA. 1. Let k 1. 2. If a . 1 0 do an appropriate row switching operation so that Ojyt-1 0. When it is not possible then declare the case of singularity and stop. 3. a n a n 1 ukn for n k
