数值分析-第二章-学习小结

1第2章线性方程组的解法--------学习小结一、本章学习体会本章主要学习的是线性方程组的解法。而我们则主要学习了高斯消去法、直接三角分解法以及迭代法三种方法。这三种方法的优缺点以及适用范围各有不同。高斯消去法中，我们又学习了顺序高斯消去法以及列主元素高斯消去法。顺序高斯消去法可以得到方程组的精确解，但要求系数矩阵的主对角线元素不为零，而且该方法的数值稳定性没有保证。但列主元素高斯消去法因为方程顺序的调整，其有较好的数值稳定性。直接三角分解法中，我们主要学习了Doolitte分解法与Crout分解法。其思想主要是：令系数矩阵A=UL，其中L为下三角矩阵，U是上三角矩阵，为求AX=b的解，则引进Ly=b,Ux=y两个方程，以求X得解向量。这种方法计算量较小，但是条件苛刻，且不具有数值稳定性。迭代法（逐次逼近法）是从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限才是所求问题的精确解，只经过有限次运算得不到精确解。该方法要求迭代收敛，而且只经过有限次迭代，减少了运算次数，但是该方法无法得到方程组的精确解。二、本章知识梳理针对解线性方程组，求解线性方程组的方法可分为两大类：直接法和迭代法，直接法（精确法）：指在没有舍入误差的情况下经过有限次运算就能得到精确解。迭代法（逐次逼近法）：从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限才是所求问题的精确解，只经过有限次运算得不到精确解。我们以前用的是克莱姆法则，对于计算机来说，这种方法运算量比较大，因此我们学习了几种减少运算次数的方法，有高斯消去法、直接三角分解法，同时针对病态方程组，也提出了几种不同的解法。2.1Gauss消去法Gauss消去法由消元和回代两个过程组成，消元过程是指针对方程组的增广矩阵，做有限次初等行变化，使它系数矩阵变为上三角矩阵。2.1.1顺序Gauss消去法2消元过程：对于K=1,2,3…,n-1执行(1)如果𝑎𝑘𝑘(𝑘)=0,则算法失效，停止计算；否则转（2）(2)对于𝑖=𝑘+1,𝑘+2,…,𝑛计算𝑚𝑖𝑘=𝑎𝑖𝑗(𝑘)𝑎𝑘𝑘(𝑘)⁄𝑎𝑖𝑗(𝑘+1)=𝑎𝑖𝑗(𝑘)−𝑚𝑖𝑘𝑎𝑖𝑘(𝑘)(𝑗=𝑘+1,𝑘+2,…,𝑛)𝑏𝑖(𝑘+1)=𝑏𝑖(𝑘)−𝑚𝑖𝑘𝑏𝑘(𝑘)回代过程：𝑥𝑛=𝑏𝑛(𝑛)𝑎𝑛𝑛(𝑛)⁄𝑥𝑘=(𝑏𝑘(𝑘)−∑𝑎𝑘𝑗(𝑘)𝑥𝑗𝑛𝑗=𝑘+1)𝑎𝑘𝑘(𝑘)⁄(𝑘=𝑛−1,𝑛−2,…,1)综上：顺序Gauss消去法的数值稳定性是没有保证的。2.1.2列主元Gauss消去法1.消元过程对于K=1,2,3…,n-1执行（1）选行号𝑖𝑘，使得|𝑎𝑖𝑘(𝑘)|=𝑚𝑎𝑥𝑘≪𝑖≪𝑛|𝑎𝑖𝑘(𝑘)|（2）交换akj(k)与aik(k)(j=k,k+1,…,n)以及bk(k)与bik(k)所含的数值。（3）对于𝑖=𝑘+1,𝑘+2,…,𝑛计算𝑚𝑖𝑘=𝑎𝑖𝑗(𝑘)𝑎𝑘𝑘(𝑘)⁄𝑎𝑖𝑗(𝑘+1)=𝑎𝑖𝑗(𝑘)−𝑚𝑖𝑘𝑎𝑖𝑘(𝑘)(𝑗=𝑘+1,𝑘+2,…,𝑛)𝑏𝑖(𝑘+1)=𝑏𝑖(𝑘)−𝑚𝑖𝑘𝑏𝑘(𝑘)回代过程：𝑥𝑛=𝑏𝑛(𝑛)𝑎𝑛𝑛(𝑛)⁄𝑥𝑘=(𝑏𝑘(𝑘)−∑𝑎𝑘𝑗(𝑘)𝑥𝑗𝑛𝑗=𝑘+1)𝑎𝑘𝑘(𝑘)⁄(𝑘=𝑛−1,𝑛−2,…,1)经验证，列主元Gauss消元法有很好的数值稳定性。2.2直接三角分解法三角分解法的思想：系数矩阵A=UL，其中L为下三角矩阵，U是上三角矩阵，为求AX=b的解，则引进Ly=b,Ux=y两个方程，以求X得解向量。2.2.1Doolittle(杜利特尔)分解3L为单位下三角矩阵，U为上三角矩阵定理：矩阵A=[aij]n×n(n≫2)有唯一的能进行Doolittle(杜利特尔)分解的充分必要条件是：A的前n-1个顺序主子式不等于0（1）A的Doolitte分解的计算公式对于k=1,2,…,n计算𝑢𝑘𝑗=𝑎𝑘𝑗−∑𝑙𝑘𝑡𝑢𝑡𝑗𝑘−1𝑡=1(𝑗=𝑘,𝑘+1,…,𝑛)𝑙𝑖𝑘=(𝑎𝑖𝑘−∑𝑙𝑖𝑡𝑢𝑡𝑘𝑘−1𝑡=1)𝑢𝑘𝑘(𝑖=𝑘+1,𝑘+2,…,𝑛;𝑘𝑛)⁄解的计算公式：y1=b1𝑦𝑖=𝑏𝑖−∑𝑙𝑖𝑡𝑦𝑡𝑖−1𝑡=1(𝑖=2,3,…,𝑛)𝑥𝑛=𝑦𝑛𝑢𝑛𝑛⁄𝑥𝑖=(𝑦𝑖−∑𝑢𝑖𝑡𝑥𝑡𝑛𝑡=𝑖+1)𝑢𝑖𝑖(𝑖=𝑛−1,𝑛−2,…,1)⁄（2）选主元的Doolitte分解法：定理：若矩阵A∈Rn×n非奇异，则存在置换矩阵Q，使得QA可做Doolitte分解，QA=LU，其中L是单位下三角矩阵，U是上三角矩阵。只有矩阵A非奇异，则通过对A做适当的行变换就可以进行Doolitte分解，而不必要求A的前n-1个顺序主子式不为0.进行选主元的Doolitte分解法具体算法如下：1）做分解QA=LU对于K=1,2，…，n执行2）计算中间量𝑠𝑖=𝑎𝑖𝑘−∑𝑙𝑖𝑡𝑢𝑡𝑘(𝑖=𝑘,𝑘+1,…,𝑛)𝑘−1𝑡=1选行号ik,使得4|𝑠𝑖𝑘|=𝑚𝑎𝑥𝑘≤𝑖≤𝑛|𝑠𝑖|,令Mk=il若ik=k,则转下一步，否则交换𝑙𝑘𝑡与𝑙𝑖𝑘𝑡(t=1,2,…k-1)、𝑎𝑘𝑡与𝑎𝑖𝑘𝑡(t=k,k+1,…n)以及𝑠𝑖与𝑠𝑖𝑘所含的数值，转下一步计算𝑢kk=sk𝑢𝑘𝑗=𝑎𝑘𝑗−∑𝑙𝑘𝑡𝑢𝑡𝑗𝑘−1𝑡=1(𝑗=𝑘+1,…,𝑛;𝑘𝑛)𝑙𝑖𝑘=(𝑎𝑖𝑘−∑𝑙𝑖𝑡𝑢𝑡𝑘𝑘−1𝑡=1)𝑢𝑘𝑘(𝑖=𝑘+1,𝑘+2,…,𝑛;𝑘𝑛)⁄3）求Qb对于K=1,2，…，n-1执行t=Mk交换bk与bt所含的数值4）求解Ly=Qb和Ux=yy1=b1𝑦𝑖=𝑏𝑖−∑𝑙𝑖𝑡𝑦𝑡𝑖−1𝑡=1(𝑖=2,3,…,𝑛)𝑥𝑛=𝑦𝑛𝑢𝑛𝑛⁄𝑥𝑖=(𝑦𝑖−∑𝑢𝑖𝑡𝑥𝑡𝑛𝑡=𝑖+1)𝑢𝑖𝑖(𝑖=𝑛−1,𝑛−2,…,1)⁄2.2.2Crout(克劳特)分解L为下三角矩阵，U为单位上三角矩阵推论：矩阵A=[aij]n×n(n≫2)有唯一的能进行Crout(克劳特)分解分解的充分必要条件是：A的前n-1个顺序主子式不等于0A的Crout(克劳特)分解的计算公式对于k=1,2,…n计算𝑙𝑖𝑘=𝑎𝑖𝑘−∑𝑙𝑖𝑡𝑢𝑡𝑘𝑘−1𝑡=1(𝑖=𝑘,𝑘+1,…,𝑛)5𝑢𝑘𝑗=(𝑎𝑘𝑗−∑𝑙𝑘𝑡𝑢𝑡𝑗𝑘−1𝑡=1)𝑙𝑘𝑘(𝑗=𝑘+1,𝑘+2,…,𝑛;𝑘𝑛)⁄解的计算公式：𝑦1=𝑏1𝑙11⁄𝑦𝑖=(𝑏𝑖−∑𝑙𝑖𝑡𝑦𝑡𝑖−1𝑡=1)𝑙𝑖𝑖⁄(𝑖=2,3,…,𝑛)𝑥𝑛=𝑦𝑛𝑥𝑖=𝑦𝑖−∑𝑢𝑖𝑡𝑥𝑡𝑛𝑡=𝑖+1(𝑖=𝑛−1,𝑛−2,…,1)2.2.3三角分解法解带状线性方程组定理：（1）A=[aij]n×n是上半带宽为s，下半带宽为r的带状矩阵（2）A的前n-1个顺序主子式均不为零则A有唯一的Doolitte分解A=LU，其中L是下半带宽为r的单位下三角矩阵，U是上半带宽为s的上三角矩阵。（1）作分解A=LU对于k=1,2,…,n计算𝑢𝑘𝑗=𝑎𝑘𝑗−∑𝑙𝑘𝑡𝑢𝑡𝑗𝑘−1𝑡=max(1,𝑘−𝑟,𝑗−𝑠)(𝑗=𝑘.𝑘+1,…,min(𝑘+𝑠,𝑛))𝑢𝑖𝑘=(𝑎𝑖𝑘−∑𝑙𝑖𝑡𝑢𝑡𝑘𝑘−1𝑡=max(1,𝑖−𝑟,𝑘−𝑠))𝑙𝑘𝑘(𝑖=𝑘+1,𝑘+2,…,min(𝑘+𝑟,𝑛);𝑘𝑛)⁄（2）求解Ly=b,Ux=yy1=b1𝑦𝑖=𝑏𝑖−∑𝑙𝑖𝑡𝑦𝑡𝑖−1𝑡=max(1,𝑖−𝑟)(𝑖=2,3,…,𝑛)𝑥𝑛=𝑦𝑛𝑢𝑛𝑛⁄𝑥𝑖=(𝑦𝑖−∑𝑢𝑖𝑡𝑥𝑡min(𝑖+𝑠,𝑛)𝑡=𝑖+1)𝑢𝑖𝑖(𝑖=𝑛−1,𝑛−2,…,1)⁄62.3迭代法迭代法（逐次逼近法）：从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限才是所求问题的精确解，只经过有限次运算得不到精确解。2.3.1迭代法的一般形式及其收敛性（1）一般形式：,2,1,0,)()1(kdXGXkkG为迭代矩阵（2）向量顺序的收敛：（1）按坐标收敛；（2）按范数收敛。（3）矩阵序列的收敛（4）迭代公式的收敛性1.向量序列的收敛（极限）（1）定义：设向量,2,1,0,),,,()()(2)(1)(kxxxXTknkkk若nixxikik,,2,1,lim*)(（按坐标收敛），则称序列)(kX收敛于X*，记为*)(limXXkk.*)(limXXkk*)(limikikxx0lim*)(XXkk（2）向量序列收敛的充要条件*)(limXXkk0lim*)(XXkk（3）矩阵序列的极限,nmkCA],[)(kijkaA若,,,2,1,,,2,1,lim)(njmiaaijkijk则称][ijaA为矩阵序列}{kA的极限，记作：AAkklim2.3.2迭代收敛的条件（1）谱半径（2）迭代收敛的充要条件（3）迭代收敛的充分条件（4）迭代终止的条件2.3.3Jacobi迭代（1）分量形式7ininiiiiibxaxaxaxa2211)(1ijjijiiiixabaxnixabaxijkjijiiiki,,2,1),(1)()1(nixabaxijkjijiiiki,,2,1),(1)()1(（2）矩阵形式bDXADIXkk1)(1)1()(（3）Jacobi迭代矩阵)(11ULDADIGJA=D-（-L-U）2.3.4Gauss-Seidel迭代（异步迭代法）（1）分量形式nixaxabaxijnijkjijkjijiiiki,,2,1),(1111)()1()1(nixaxabaxijnijkjijkjijiiiki,,2,1),(1111)()1()1(（2）矩阵形式,2,1,0,)()1(kdGXXkkbLDUxDLxkk1)(1)1()()(（3）GS迭代矩阵UDLGG1)(A=(D+L)-(-U)UDLGG1)(2.3.5逐次超松弛迭代法（SOR迭代）（1）分量形式8)1()()1(111)()1()1(~)1()(1~kikikiijnijkjijkjijiiikixxxxaxabax（2）计算公式])11([111)()()1()1(iiiijnijkikjiiijkjiiijkiabxxaaxaax（3）矩阵形式bDUXDLXDXkkk1)(1)1(1)1(~)1()()1(~)1(kkkXXXbLDXUDLDXkk1)(1)1()1(])11[()1(bLDXUDLDXkk1)(1)1()1(])11[()1(（4）SOR迭代矩阵])11[()1(1UDLDGSω1,逐次超松弛迭代法ω1,逐次低松弛迭代法ω=1,GS迭代法UDLDA