三角形方程组和三角分解

1、第一章 线性方程组的直接解法,直接法：是指在没有舍入误差的情况下经过有限次运算求得方程组的精确解； Gauss消去法是其中最基本的一种，适用于中小规模线性方程组(n1000)，系数稠密有没有任何特殊结构的线性方程组。 迭代法：从一个初始向量出发，按照一定的计算格式，采取逐次逼近的的方法，构造一个向量的无穷序列，其极限时方程组的精确解，有限次运算得不到精确解。,1.1 三角形方程组和三角分解 1.1.1 三角形方程组的解法,下三角形方程组的解法 考虑下三角形方程组 Ly = b (1.1.1) bRn已知, yRn 未知, LRnn已知非奇异的下三角阵,则(1.1.1)的分量形式为,这种解方程组

2、(1.1.1)的方法称为前代法。,实际计算时 bi 在算完 yi 之后就没用了, 故将得到的 yi 存放在 bi 所用的存储单元内，则上式变为,第i个式子的计算可先计算分子，算法为,for j=1:i-1 b(i)=b(i)-L(i, j) *b(j) end,故计算上述方程组, 可先按循环方式算出来分子, 再除以lii ，具体步骤如下,第一步: b(1)=b(1)/L(1,1) b(2)=b(2)-L(2,1)*b(1) b(3)=b(3)-L(3,1)*b(1) b(n)=b(n)-L(n,1)*b(1),第二步: b(2)=b(2)/L(2,2) b(3)=b(3)-L(3,2)*b(2

3、) b(4)=b(4)-L(4,2)*b(2) b(n)=b(n)-L(n,2)*b(2),递推直至第n-1步: b(n-1)=b(n-1)/L(n-1, n-1) b(n)=b(n)-L(n, n-1)*b(n-1),第n步: b(n)=b(n)/L(n, n),写成算法的形式：,for j=1:n-1 b(j)=b(j)/L(j, j) for i=j+1:n b(i)=b(i)-L(i, j) *b(j) end end b(n)=b(n)/L(n, n),b(j+1:n)=b(j+1:n)-b(j)*L(j+1:n, j),该算法运算量：,算法1.1.1(解下三角形方程组:前代法),上

4、三角形方程组的解法 考虑下三角形方程组 Ux = y (1.1.2) yRn已知, xRn 未知, URnn已知非奇异的上三角阵,该方程组可用回代法求解，即从方程组的最后一个方程出发，依次求出xn , xn-1 , , x1 , 计算公式为,类似算法1.1.1可得算法1.1.2(回代法). 运算量亦为n2.,一般的线性方程组的解法 考虑一般的线性方程组 Ax = b (1.1.3) ARnn, bRn已知, xRn 未知, 如果A能分解为 A = LU 即一个下三角阵L与一个上三角阵U的乘积, 那么方程组 (1.1.3)的解 x 可由以下两步得到 用前代法解 Ly = b 得 y； 用回代法解

5、 Ux = y 得 x；,问题关键：如何将A分解为下三角阵*上三角阵？,1.1.2 Gauss变换,Gauss变换的定义 称具有如下形式的初等下三角矩阵 Lk = IlkekT 为Gauss变换, 其中ek 是第k个单位坐标向量, 且,为Gauss向量，,即,Gauss变换的性质 设 xRn, xk0, 则存在Gauss变换 Lk 使得 Lk x = (x1 xk 0 0)T . 事实上，,只需取, i = k+1, , n, xk0.,写出此时lk = ？,Gauss变换的逆( IlkekT )1 = IlkekT. 事实上，,Lk A = ( IlkekT ) A = Alk (ekT A

6、).,事实上, rank(lk ekT A) = 1. 将Gauss变换作用于一 个矩阵相当于对该矩阵 进行秩1修正(外加一个 秩为1的修正, 例如 A+aeeT, e是单位向量, eeT就是秩为1的矩阵).,1.1.3 三角分解的计算,三角分解的定义 设ARnn, A的三角分解是指A = LU, 其中LRnn为下三角矩阵, URnn为上三角矩阵，,矩阵的三角分解也称为矩阵的LU分解.,使用Gauss变换实现矩阵的LU分解: 一个例子,例. 求 的LU分解.,解: (1),因为 , 所以,解: (2),因为 , 所以,使用Gauss变换实现矩阵的LU分解: 一般步骤,(1) 记A(0) = (

7、aij(0) ) = A = (aij) , 计算Gauss变换L1使得,00,(2) 对A(1), 计算Gauss变换L2使得,0 0,(3) 假定已求出L1, , Lk1, 使得,其中A11(k1)是k1阶上三角阵,若 , 则又可计算一个Gauss变换Lk使得Lk A(k1)中的第k列的最后nk个元素为0. 即,0 0,(4) 重复上述步骤 n-1 次, 得到A(n1)为 n 阶上三角阵, 即 Ln1L2 L1A = A(n1).,记L = (Ln1L2 L1)1 , U = A(n1) , 则得 A = LU .,(5) 下证: 上述L是单位下三角阵.,证明:,Gauss消去法 Dool

8、ittle分解,(6) 当Lk作用于A(k-1)后, A(k-1)的元素发生了什么变化？,(a) 前k行元素不变; (b) 第k列第k+1个元素开始往后变为0; (c) 其余元素: aij(k) = aij(k-1) likakj(k-1),其中 ，i, j = k+1: n.,(7) Lk和A(k)的元素怎样存储？,(a) A(k-1)中的第k+1行至第n行的元素在算出A(k)后不再有用, 故可用新算出的A(k)的元素冲掉A(k-1)中对应的元素.,(b) A(k)的第k列对角元以下的元素均为0, 无需存储, 故用这些位置存放lk中非零元.,以44阶矩阵为例，,(8) 算法1.1.3 (计算

9、三角分解: Gauss消去法) for k=1:n-1 A(k+1:n, k)=A(k+1:n, k)/A(k, k) A(k+1:n, k+1:n)=A(k+1:n, k+1:n) -A(k+1:n, k)A(k, k+1:n) end, , 前k行元素不变, 无需操作 第k列从第k+1个元素开始存放 lk+1 k 其余位置, 按公式算出新A(k)的元素, 冲掉A(k-1)对应位置的元素,运算量：,(9) 两个定理 定义: 称Gauss消去法过程中的akk(k-1)为主元. 算法1.1.3要求akk(k-1) (k = 1, 2, n-1) 均不为0. 矩阵A满足什么条件才能保证所有主元均不为0？ 定理1.1.1 主元aii(i-1) (i = 1, 2, k) 均不为0,A的i 阶顺序主子阵Ai (i =1, 2, k)都是非奇异的.,矩阵的三角分解(LU分解)存在的充分条件. 定理1.1.2 若ARnn的顺序主子阵AkRnn (k = 1, 2, n-1)均非奇异, 则存在唯