直接法算法设计中矩阵分解技巧的应用

直接法求解线性方程组 直接法的适用范围 直接法算法设计中矩阵分解技巧的应用 特殊线性方程的算法设计与分析 直接法所得“精确解”的精度分析

1. 直接法的适用范围 直接法：就是经过有限步算术运算，可求得方程 组精确解的方法(若计算过程中没有舍入误差), 如克莱姆法则就是一种直接法，直接法中具有代 表性的算法是高斯(Gauss)消去法。 直接法这个“直接”往往代表着解法思想简单， 直接了当。它往往能求各种方程，是一种通吃的 解法，像克莱姆法则、高斯(Gauss)消去法，它们 很强大，但也有缺点。这个缺点往往是致命的， 有些方程它能解，但人们往往不敢用它去解。

为什么呢？ 它们在计算高阶方程组计算量太大啦 所以直接法比较适吅解中低阶的矩阵 对于大型矩阵我们往往采取其它方法。如迭代法

在实际应用中选择算法往往从三个方面考虑： (1) 解的精度高； (2) 计算量小； (3)所需计算机内存小。 但这些条件相互间是矛盾而不能兼顾的，因此实 际计算时应根据问题的特点和要求及所用计算机 的性能来选择算法。一般说，系数矩阵为中、小 型满矩阵，用直接法较好；当系数矩阵为大型、 稀疏矩阵时，有效的解法是下节要讨论的迭代法。

2.直接法算法设计中矩阵分解技巧的应用 矩阵三角分解法 矩阵三角分解法是高斯消去法解线性方程的变形解法

矩阵三角分解原理 应用高斯消去法解n阶线性方程组Ax=b, 经过n步 消元之后, 得出一个等价的上三角型方程组A(n) x=b(n), 对上三角形方程组用逐步回代就可以求出 解来。上述过程可通过矩阵分解来实现。 将非奇异阵A分解成一个下三角阵L和一个上三角 阵U的乘积 A=LU称为对矩阵A的三角分解，又 称LU分解。

a11 a 21 A a31 a n1

a13 a1n a 22 a 23 a 2 n a32 a33 a3n LU a n 2 a n3 a nn a12

其中

1 m 21 1 , L m31 m32 1 mn1 mn 2 1

(1 (1 (1 a11) a12) a13) a1(1) n ( 2) ( 2) ( 2) a22 a23 a2n (3 U a33) a3(3) n (n ann)

方程组Ax=b的系数矩阵A经过顺序消元逐步 化为上三角型A(n),相当于用一系列初等变换左 乘A的结果。事实上，第1列消元将A(1)=A化 为A(2),若令： 1 m 21 L1 m31 mn1 0 1 0 0 0 0 0 0 1 0 0 0 1

ai(11) mi1 (1) , a11

(i 2,3, , n)

则根据距阵左乘有L1A(1)=A(2)

第2列消元将A(2)化为A(3),若令： 1 0 L2 0 0

0 1 m32 mn 2 0 0 1 0 0 0 2 ai(2 ) 0 mi 2 ( 2 ) , a 22 0 1

(i 3,4, , n)

经计算可知 L2A(2)=A(3),依此类推,一般有LkA(k)=A(k+1) 1 Lk 1 1 mk 1, k mnk 1 1

于是矩阵 A A(1) 经过消元化为上三角阵A (n ) Ln 1 Ln 2 L2 L1 A A ( n ) 的过程可表示为 上述矩阵 Lk (k 1,2, , n 1) 是一类初等矩阵, 它们都是单位下三角阵，且其逆矩阵也是单位 下三角阵,只需将 mik 改为 mik (i k 1, k 2, , n) , 就得到 L 1 。即 k 1 1 1 1

L 1 k

1 m k 1, k m nk

于是有A (L L L 1 1 1 2 1 n 1

)A

(n)

(L L L

1 1

1 2

1 n 1

)U LU

其中 1 m 21 1 , L m31 m32 1 mn1 mn 2 1 (1 (1 (1 a11) a12) a13) a1(1) n ( 2) ( 2) ( 2) a22 a23 a2n (3 U a33) a3(3) n (n ann)

L为由乘数构成的单位下三角阵，U为上三角阵，( 由此可见，在 akkk ) 0(k 1,2, , n 1) 的条件下

,高斯消去法实质上是将方程组的系数矩阵A分 解为两个三角矩阵的乘积A=LU。这种把非奇异矩 阵A分解成一个下三角矩阵L和一个上三角矩阵U 的乘积称为矩阵的三角分解，又称LU分解。( 显然，如果 akkk ) 0(k 1,2, , n 1),由行列式

的性质知，方程组系数矩阵A的前n-1个顺序主子

矩阵 Ak (k 1,2, , n 1) 非奇异，即顺序主子式不等于零，即

det(A1 ) a其中

(1) 11

0

(1 ( 2 ( det(Ai ) a11) a 22) aiii ) 0(i 2,3, , k )

a11 a1i (A的主子阵) A1 (a11 ), Ai a i1 a ii 反之,可用归纳法证明,如果A的顺序主子式(1 (2 ( det(Ai ) a11) a 22) aiii ) 0(i 1,2, , k )

则

a

(i ) ii

0(i 1,2, , k )

于是得到下述定理：

把A分解成一个单位上三角阵L和一个下三角阵U的乘积称为杜利特尔(Doolittle

)分解。其中

1 l 1 21 , L l n1 l n 2 1

u11 u12 u1n u u 22 2n U u nn

若把A分解成一个下三角阵L和一个单位上三角阵U的乘积称为克洛特分解Crout)

其中

l11 1 u12 u1n l l 1 u 2n 21 22 , U L 1 l n1 ln 2 l nn

用三角分解法解方程组

求解线性方程组Ax=b时,先对非奇异矩阵A进行 LU分解使A=LU,那么方程组就化

为 LU x=b L y=b U x=y 求解 y 求解 x

从而使问题转化为求解两个简单的的三角方程组

这就是求解线性方程组的三角分解法的基本思想。 下 面 只 介 绍 杜 利 特 尔 ( Doolittle ) 分 解 法 。 设 A=LU为