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

《第三章解线性方程组的直接方法.ppt》由会员分享，可在线阅读，更多相关《第三章解线性方程组的直接方法.ppt（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值计算方法第三章 解线性方程组的直接方法Direct Method for Solving Linear Systems其中其中简记作简记作求解求解解线性方程组的两类方法：解线性方程组的两类方法：迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)高斯消元法：高斯消元法：思思路路首先将首先将A化为上三角阵化为上三角阵 /*upper-triangular matrix*/，再回代求解再回代求解 /*backward substitution*/。=一、Gauss 消去法计算过程相当

2、于第i个方程-第一个方程数新的第i方程同解！第一方程不动！其中其中 上述消元过程除第一个方程不变以外,第2第 n 个方程全消去了变量 1，而系数 和常数项全得到新值：系数矩阵与常数项：记记Step 1：设设 ，计算因子，计算因子将增广矩阵将增广矩阵/*augmented matrix*/第第 i 行行 mi1 第第1 1行行，得到得到其中其中Step k：设设 ，计算因子，计算因子且计算且计算共进行共进行？步步n 1回代过程算法消去第一列的 n-1 个系数要计算n*(n-1）个乘法。Gauss消去法乘法计算量需要修改前述算法，研究原矩阵需要修改前述算法，研究原矩阵A A在什么条件下才能保在什么

3、条件下才能保证高斯消去的进行。证高斯消去的进行。What if?No unique solution exists.What if?Then we must find the smallest integer k i with ,and interchange the k-th row with the i-th row.What if we cant find such k?No unique solution exists.定理定理6 若若A的所有的所有顺序主子式顺序主子式/*determinant of leading principal submatrices*/均不为均不为0，则高斯

4、消元无需换行即可，则高斯消元无需换行即可进行到底，得到唯一解。进行到底，得到唯一解。注注注注：事实上，只要事实上，只要 A 非奇异，即非奇异，即 A 1 存在，则可通过逐次存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯消元及行交换，将方程组化为三角形方程组，求出唯一解。一解。高斯主元素消去法高斯主元素消去法例例1.1.用用GaussGauss消去法解线性方程组消去法解线性方程组(用用3 3位十位十进制浮点数计算）进制浮点数计算）解解:本方程组的精度较高的解为本方程组的精度较高的解为用用Gauss消去法求解消去法求解(用用3位十进制浮点数计算位十进制浮点数计算)9999回代后得

5、到回代后得到与精确解相比与精确解相比,该结果相当糟糕该结果相当糟糕究其原因究其原因,在求行乘数时用了很小的数在求行乘数时用了很小的数0.0001作除数作除数主元主元如果在求解时将如果在求解时将1,2行交换行交换,即即0.9999回代后得到回代后得到这是一个相当不错的结果这是一个相当不错的结果每一步消去过程相当于左乘初等变换矩阵LkGauss消去法的矩阵表示i+1行 i+1行LU形式Hey hasnt GE given me enough headache?Why do I have to know its matrix form?!When you have to solve the syst

6、em 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.定理定理 若若A的所有顺序主子式的所有顺序主子式/*determinant of leading principal submatrices*/均不为均不为0，则，则 A 的的 LU 分解唯一（其中分解唯一（其中 L 为为单位单位下三角阵）。下三角阵）。证明：证明：由由1中定理可知，中定

7、理可知，LU 分解存在。下面证明唯一性。分解存在。下面证明唯一性。若不唯一，则可设若不唯一，则可设 A=L1U1=L2U2，推出推出Upper-triangularLower-triangularWith diagonal entries 1注注注注：L 为一般下三角阵而为一般下三角阵而 U 为为单位单位上三角阵的分解称为上三角阵的分解称为Crout 分解分解。实际上只要考虑实际上只要考虑 A*的的 LU 分解，即分解，即 ，则，则 即是即是 A 的的 Crout 分解。分解。直接计算直接计算 A A 的的 LU LU 分解分解(例例)一般计算公式 计算量与 Gauss 消去法同.LU 分解求

8、解线性方程组 平方根法平方根法 /*Choleskis Method*/：对称对称/*symmetric*/正定正定/*positive definite*/矩阵的分解法矩阵的分解法一个矩阵一个矩阵 A=(aij)n n 称为称为对称阵对称阵，如果，如果 aij=aji。一个矩阵一个矩阵 A 称为称为正定阵正定阵，如果，如果 对任意非零向对任意非零向量量 都成立都成立。因此Diagonal:对角为非奇异下三角阵为非奇异上三角阵-(2)-(3)因此所以综合以上分析,则有-(4)-(5)定理11.(Cholesky分解)且该分解式唯一这种关于对称正定矩阵的分解称为Cholesky分解-(6)-(7

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

10、 positive definite n n 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,n 1,do steps 4 and 5Step 4 Set ;Step 5 For j=i+1,n,set ;Step 6 Set ;Step 7 Output(l

11、ij 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:追追即解即解 ：

12、Step 3:赶赶即解即解 ：与与G.E.类似，一旦类似，一旦 i=0 则算法中断，故并非任何则算法中断，故并非任何三对角阵都可以用此方法分解。三对角阵都可以用此方法分解。定理定理 若若 A 为为对角占优对角占优/*diagonally dominant*/的三对角阵，的三对角阵，且满足且满足 ，则追赶法可解以，则追赶法可解以 A 为系为系数矩阵的方程组。数矩阵的方程组。Hey,what does diagonally dominant mean?It means that the diagonal entries of the matrix are very LARGE.Well,how l

13、arge is LARGE?They satisfy the following inequality:注注注注：如果如果 A 是是严格严格对角占优阵，则不要求三对角线上的对角占优阵，则不要求三对角线上的所有元素非零。所有元素非零。根据不等式根据不等式 可知：分解过程中，矩阵元素不会过分增大，算法可知：分解过程中，矩阵元素不会过分增大，算法保证稳定。保证稳定。运算量为运算量为 O(6n)。5.5.向量和矩阵的范数向量和矩阵的范数一、向量范数显然显然二、矩阵的范数二、矩阵的范数矩阵范数例矩阵范数例 与前述三种向量范数相容的三种矩阵范数：与前述三种向量范数相容的三种矩阵范数：求矩阵求矩阵A A的各

14、种常用范数的各种常用范数解解:由于特征方程为容易计算计算较复杂对矩阵元素的变化比较敏感使用最广泛性质较好矩阵A的谱半径ReIm (A)定理1.与假设矛盾与假设矛盾定理1.5.6 5.6 误差分析误差分析右端项右端项b b的扰动对解的影响的扰动对解的影响相对误差放大因子相对误差放大因子系数矩阵系数矩阵A A的扰动对解的影响的扰动对解的影响条件数的定义条件数的定义条件数的性质条件数的性质精确解精确解为为例例计算计算cond(A)2。A 1=解：解：考察考察 A 的特征根的特征根39206 1 测试病态程度：测试病态程度：给一个扰动给一个扰动，其相对误差为，其相对误差为此时此时精确解精确解为为2.0

15、102 200%例：例：Hilbert 阵阵cond(H2)=27cond(H3)748cond(H6)=2.9 106cond(Hn)as n 注：注：一般判断矩阵是否病态，并不计算一般判断矩阵是否病态，并不计算A 1，而由经验而由经验得出。得出。行列式很大或很小（如某些行、列近似相关）；行列式很大或很小（如某些行、列近似相关）；元素间相差大数量级，且无规则；元素间相差大数量级，且无规则；主元消去过程中出现小主元；主元消去过程中出现小主元；特征值相差大数量级。特征值相差大数量级。近似解的误差估计及改善：近似解的误差估计及改善：设设 的近似解为的近似解为，则一般有，则一般有cond(A)误差上

16、限误差上限 改善方法：改善方法：Step 1:近似解近似解Step 2:Step 3:Step 4:若若 可被精确解出，则有可被精确解出，则有 就是精确解了。就是精确解了。经验表明经验表明：若：若 A 不是非常病态（例如：不是非常病态（例如：），则如），则如此迭代可达到机器精度；但若此迭代可达到机器精度；但若 A 病态，则此算法也不能改病态，则此算法也不能改进。进。二、误差分析 改善方法：改善方法：Step 1:近似解近似解Step 2:Step 3:Step 4:若若 可被精确解出，则有可被精确解出，则有 就是精确解了。就是精确解了。经验表明经验表明：若：若 A 不是非常病态（例如：不是非常病态（例如：），则如），则如此迭代可达到机器精度；但若此迭代可达到机器精度；但若 A 病态，则此算法也不能改病态，则此算法也不能改进。进。