数值分析07线性代数方程组的直接法

《数值分析07线性代数方程组的直接法》由会员分享，可在线阅读，更多相关《数值分析07线性代数方程组的直接法（62页珍藏版）》请在文档大全上搜索。

1、第七章第七章( Direct Method for Solving Linear Systems)nnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（3.1） 线性方程组数值解法的分类线性方程组数值解法的分类 直接法直接法（适用于中等规模的（适用于中等规模的n n阶线性方程组）阶线性方程组） GaussGauss消去法及其变形消去法及其变形 矩阵的三角分解法矩阵的三角分解法 迭代法迭代法（适用于高阶线性方程组）（适用于高阶线性方程组） JacobiJacobi

2、迭代法迭代法 Gauss-SeidelGauss-Seidel迭代法迭代法 逐次超松弛法逐次超松弛法 共轭斜量法共轭斜量法(Gaussian Elimination)1 1三角形方程组的解法三角形方程组的解法-回代法回代法nnnnnnbxaxaxabxaxabxa221122221211111 （3.2）nnnnnnnnbxabxaxabxaxaxa2222211212111（3.3） 2 2顺序高斯消去法顺序高斯消去法思思路路首先将首先将A化为上三角阵化为上三角阵 ( upper-triangular matrix )，此过程称为此过程称为消去过程消去过程，再求解如，再求解如下形状的方程组，

3、此过程称为下形状的方程组，此过程称为回代求解回代求解 ( backward substitution )。=nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111将增广矩阵将增广矩阵的的第第 i 行行 + li1 第第1 1行行，得到：，得到：,)(记)1()1(nnijaAA(1 )(1 )(1 )()1Tbbbbn消元过程：消元过程：第一步第一步：设设 ，计算因子，计算因子0)1(11a)1(11)1(11aalii)1(1)1(1)1(12)1(11.baaan) 2(A) 2 (b其中其中) 1(11) 1()2() 1(11) 1()2

4、(, 3 , 2, ,blbbnjialaaiiijiijij0)( kkka第第k步：步：设设 ，计算因子，计算因子( )( )/(1,., )kkikikkklaaikn 将增广矩阵将增广矩阵的的第第 i 行行 + lik 第第k k行行，得到：，得到：(1)()()(1)()()( ,1, .,)kkkijijikkjkkkiiikkaal abbl bijkn其中其中(1)(1)(1)(1)(1)111111,11( )( )( )( ),1(1)(1)(1)11,11,1(1)(1)( ),100000kknkkkkkkkk kknkkkkkkkknkkkkn knnnnbxaaaa

5、xaaabxaabaaxb )()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii回代过程：回代过程：共进行共进行 n 1步，得步，得到到 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa 运算量运算量 （Amount of Computation）（1 1）用克莱姆用克莱姆（CramerCramer）法则求解法则求解n n阶线性方程组阶线性方程组 每个行列式由每个行列式由n!n!项相加，而每项包含了项相加，而每项包含了n n个因子个因子相乘，乘法运算次数为相乘，乘法运算次数为(

6、 (n-1)n !n-1)n !次次. .,1, 2,.,iiDxinD仅考虑乘仅考虑乘( (除除) )法运算法运算, ,计算解向量包括计算计算解向量包括计算n+1n+1个行列式和个行列式和n n次除法运算次除法运算, ,乘乘( (除除) )法运算次法运算次数数N=(n+1)(n-1)n!+n. .当当n=8时时,N200，0000（2） 高斯消去法高斯消去法:第第1 1个消去步个消去步， 计算计算l li1i1(i=2,3(i=2,3，n)n)， 有有n-1n-1次次除法运算除法运算. . 使使a aijij(1)(1)变为变为 a aijij(2)(2) 以及使以及使b bi i(1)(1

7、)变为变为b bi i(2)(2)有有n(n-1)n(n-1)次乘法运算次乘法运算. . 第第k k个消去步个消去步，有，有n-kn-k次除法运算、次除法运算、( (n-k+1)(n-k)n-k+1)(n-k)次次乘法运算乘法运算. .乘法运算总次数为：乘法运算总次数为： 除法运算总次数为除法运算总次数为: : (n-1)+ (n-1)+1=n(n-1)/2+1=n(n-1)/2311 (13nk k k)(n)n回代过程的计算回代过程的计算除法运算次数为除法运算次数为n次次. 乘法运算的总次数为乘法运算的总次数为 n+(n-1)+1=n(n-1)/2次次 Gauss Gauss消去法消去法

8、除法运算次数为除法运算次数为: :n(n-1)/2+n=n(n+1)/2n(n-1)/2+n=n(n+1)/2， 乘法运算次数为乘法运算次数为: : n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6 n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6， 通常也说通常也说GaussGauss消去法的运算次数与消去法的运算次数与n n3 3同阶，记为同阶，记为O(nO(n3 3) )(30,9890)n 为顺序顺序GaussGauss消去法可执行的前提消去法可执行的前提定理定理 1 1 给定线性方程组给定线性方程组 ，如果，如果n n阶方阵阶方阵

9、的所有顺序主子式都不为零，即的所有顺序主子式都不为零，即 则按顺序则按顺序GaussGauss消去法所形成的各主元素消去法所形成的各主元素 均不为零，从而均不为零，从而Gauss 消去法可顺利执行。消去法可顺利执行。AxbA( )(1,2, )kkkakn注：注：当线性方程组的系数矩阵为对称正定或严格对角当线性方程组的系数矩阵为对称正定或严格对角占优阵时，按占优阵时，按GaussGauss消去法计算是稳定的。消去法计算是稳定的。, 0, 0222112112111aaaaDaD01111kkkkkaaaaDIllustration3、列主元（、列主元（ Column pivot element

10、 ）Gauss消去法：消去法：1、输入矩阵阶数输入矩阵阶数n，增广矩阵增广矩阵 A(n,n+1);2、对于对于nk, 2 , 1(1) 按列选主元：选取按列选主元：选取 l 使使 0maxikniklkaa(2) 如果如果 ，交换，交换 A(n,n+1) 的第的第k行与第行与第l 行元素行元素kl (3) 消元计算消元计算 ：nkiaalkkikik,1 .1,1,1, lnkjnkiaaakjikijij3、回代计算回代计算1 ,1, ，/）（,1nniaxabxiinijjijii4 4无回代过程的主元消去法无回代过程的主元消去法算法：算法：第一步：选主元，在第一列中选绝对值最大的元素，设

11、第第一步：选主元，在第一列中选绝对值最大的元素，设第k行为主元行，行为主元行， 将主元行换至第一行，将第一个方程中将主元行换至第一行，将第一个方程中x1的系数变为的系数变为1，并从，并从 其余其余个方程中消去个方程中消去x1。第二步：在第二列后第二步：在第二列后n 1个元素中选主元，将第二个方程中个元素中选主元，将第二个方程中x2的的 系数变为系数变为1，并从其它，并从其它个方程中消去个方程中消去x2。第第k步：在第步：在第k列后列后n k个元素中选主元，换行，将第个元素中选主元，换行，将第k个方程个方程xk的系数的系数 变为变为1，从其它，从其它个方程中消去变量个方程中消去变量xk，nkki