Programming Practice

LU-分割 (LU-decomposition) 問題就是將一個 n´n 的矩陣 A 分割成兩個 n´n 的三角矩陣 LU。其中 L 是一個下三角矩陣 (lower triangular matrix) 且其對角線 (diagonal) 的元素為 1,U 是一個上三角矩陣 (upper triangular matrix) 且其對角線的元素都不為 0。以下為 LU-分割的矩陣描述:

如果 A(k) 代表將 A 的前面 k 行和 k 列移除後的 (n-k)´(n-k) 矩陣,即

A(0) 開始到 A(n-1), LU-分割的演算法,即是每個 A(k) 執行下列三個步驟:

  1. 計算矩陣 U 的第 k 列元素:uk,j = ak,j, for k£j£n-1,

  2. 計算矩陣 L 的第 k 行元素:li,k = ai,k / ak,k, for k£i£n-1,

  3. 計算矩陣 A(k+1) 的元素:ai,j = ai,j - li,k ´ uk,j, for k<i, j£n-1.

寫一個 C 語言的程式以執行以下的步驟:

  1. 宣告 AA1、L、和 U 為 100´100 的二維陣列

  2. 輸入正整數 n 的值 (小於或等於 100);

  3. 使用副程式 rand() 隨機產生矩陣 A 元素的浮點數值 (假設 A 元素的值在 0 和 1 之間,並取小數點以下六位);同時,複製矩陣 A 的值到矩陣 A1;

  4. 輸出矩陣 A (至小數點以下四位);

  5. 計算 LU-分割的矩陣 L 和 矩陣 U 的值,以使得 A=LU

  6. 輸出矩陣 L(至小數點以下四位);

  7. 驗算 L U 的矩陣乘積是否等於 A1 (假設誤差值小於 0.0001)。

LU 分割寫成一個副程式 void LU_decompose(int n, float A[100][100], float L[100][100], float U[100][100]). 以下為程式執行範例:

Enter matrix size n: 8

Matrix A:
  0.4175   0.9645   0.3732   0.5116   0.1452   0.0945   0.5138   0.1312
  0.3235   0.9010   0.9087   0.8634   0.8326   0.6120   0.9682   0.0193
  0.8128   0.4834   0.8543   0.7756   0.5992   0.6586   0.2214   0.9546
  0.5157   0.3882   0.1194   0.0241   0.7749   0.5487   0.6325   0.1222
  0.5369   0.5116   0.5114   0.9309   0.0995   0.0082   0.6507   0.5696
  0.9939   0.9503   0.2220   0.4133   0.8510   0.6037   0.4215   0.3883
  0.6897   0.7085   0.6610   0.6358   0.7844   0.7723   0.6334   0.4508
  0.8098   0.3908   0.3777   0.4318   0.1415   0.7933   0.9431   0.6875

Matrix L:
  1.0000
  0.7749   1.0000
  1.9468  -9.0742   1.0000
  1.2352  -5.2270   0.5038   1.0000
  1.2860  -4.7426   0.5165  -2.1637   1.0000
  2.3806  -8.7584   0.8278   0.2102   0.5417   1.0000
  1.6520  -5.7585   0.6282   0.2302   0.1016   1.6936   1.0000
  1.9396  -9.6317   0.9776  -0.0526   0.0831   6.3578   4.8837   1.0000

Matrix U:
  0.4175   0.9645   0.3732   0.5116   0.1452   0.0945   0.5138   0.1312
           0.1537   0.6195   0.4670   0.7201   0.5388   0.5701  -0.0824
                    5.7494   4.0171   6.8508   5.3636   4.3942  -0.0482
                            -0.1908   0.9079   0.5459   0.7638  -0.4461
                                      1.7538   0.8526   2.0766  -0.9300
                                               0.0808  -0.7317  -0.0080
                                                        1.1592   0.0008
                                                                -0.2124


The LU-decomposition program is correct.