第五章解线性方程组的直接方法.ppt

1、数值分析,第五章 解线性方程组的直接方法,Direct Method for Solving Linear Systems,其中,简记作,求解,解线性方程组的两类方法：,迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）,直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!),Gauss 消去法, 高斯消元法：,一、Gauss 消去法计算过程,相当于第i个方程-第一个方程数新的第i方程同解！第一方程不动！,其中,上述消元过程除第一个方程不变以外, 第2第 n 个方程全消去了变量 1，而系数 和常数项全得到新值：,系数矩阵与常数项：,

2、消元,记,其中,Step k：设 ，计算因子 且计算,共进行 ？ 步,n 1,回代过程算法,No unique solution exists.,What if we cant find such k ?,No unique solution exists.,定理6,若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。,注：事实上，只要 A 非奇异，即 A1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。,消去第一列的 n-1 个系数要计算n*(

3、n-1） 个乘法。,Gauss消去法乘法计算量,高斯主元素消去法,例1.,用Gauss消去法解线性方程组(用3位十进制浮点数计算）,解:,本方程组的精度较高的解为,用Gauss消去法求解(用3位十进制浮点数计算),9999,回代后得到,与精确解相比,该结果相当糟糕,究其原因,在求行乘数时用了很小的数0.0001作除数,主元,如果在求解时将1,2行交换,即,0.9999,回代后得到,这是一个相当不错的结果, 高斯-若当消去法 /* Gauss-Jordan Method */,与 Gaussian Elimination 的主要区别：, 每步不计算 mik ，而是先将当前主元 akk(k) 变为

4、 1;, 把 akk(k) 所在列的上、下元素全消为0;,Hey! Isnt it better than Gaussian Elimination?,What makes you say so?,Obviously we no longer need the backward substitution!,Youd better wait till we go through the next section to draw your conclusion,高斯若当消去法,每一步消去过程相当于左乘初等变换矩阵Lk,Gauss消去法的矩阵表示,LU形式,Hey hasnt GE given me

5、 enough headache? Why do I have to know its matrix form?!,When you have to solve the system for different with a fixed A.,Could you be more specific, please?,Factorize A first, then for every you only have to solve two simple triangular systems and .,证明：由1中定理可知，LU 分解存在。下面证明唯一性。,若不唯一，则可设 A = L1U1 = L

6、2U2 ，推出,Upper-triangular,Lower-triangular With diagonal entries 1,注： L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Crout 分解。,直接计算 A 的 LU 分解(例),一般计算公式,计算量与 Gauss 消去法同.,LU 分解求解线性方程组, 平方根法 /* Choleskis Method */： 对称 /* symmetric */ 正定 /* positive definite */ 矩阵的分解法,回顾：对称正定阵的几个重要性质,

7、A1 亦对称正定，且 aii 0,若不然，则,对任意 , 存在 , 使得 , 即 。, A 的顺序主子阵 /* leading principal submatrices */ Ak 亦对 称正定,对称性显然。对任意 有 , 其中 。, A 的特征值 /* eigen value */ i 0,设对应特征值 的非零特征向量 为 ，则 。, A 的全部顺序主子式 det ( Ak ) 0,因为,因此,Diagonal:对角,为非奇异下三角阵,为非奇异上三角阵,-(2),-(3),因此,所以,综合以上分析,则有,-(4),-(5),定理11. (Cholesky分解),且该分解式唯一,这种关于对称

8、正定矩阵的分解称为Cholesky分解,-(6),-(7),-(8),对称正定线性方程组的解法,线性方程组,-(10),-(11),则线性方程组(10)可化为两个三角形方程组,-(12),-(13),-(14),-(15),对称正定方程 组的平方根法,例1.,用平方根法解对称正定方程组,解:,即,所以原方程组的解为,本例中出现了大量的根式运算,原因为,考虑改变分解方式,请求解例1.,平方根法的数值稳定性,用平方根法求解对称正定方程组时不需选取主元,由,可知,因此,平方根法是数值稳定的,事实上,对称正定方程组也可以用顺序Gauss消去法求解,而不必加入选主元步骤,Algorithm: Chole

9、skis Method To factor the symmetric positive definite nn matrix A into LLT, where L is lower triangular. Input: the dimension n; entries aij for 1 i, j n of A. Output: the entries lij for 1 j i and 1 i n of L. Step 1 Set ; Step 2 For j = 2, , n, set ; Step 3 For i = 2, , n1, do steps 4 and 5 Step 4

10、Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ; Step 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP.,因为A 对称，所以只需存半个 A，即 其中,运算量为 O(n3/6)， 比普通LU 分解少一半，但有 n 次开方。用A = LDLT 分解，可省开方时间。, 追赶法解三对角方程组 /* Crout Reduction for Tridiagonal Linear System */,Step 1: 对 A 作Crout 分解,直接比较等式两边的元素，可得到计算公式（p.194）。,Step 2: 追即解 ：,Step 3: 赶即解 ：,与G.E.类似，一旦 i = 0 则算法中断，故并非任何 三对角阵都可以用此方法分解。,Hey, what does diagonally dominant mean?,It means that the diagonal entries of the mat