数值分析李庆扬第五版第四章线性方程组的数值解法

第四章线性方程组的数值解法§4.1消元法§4.2直接分解法§4.3向量和矩阵的范数§4.4雅可比迭代§4.5高斯-赛德尔迭代§4.6松弛迭代直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!)（Gauss消去法及其变形、矩阵的三角分解法）迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）直接法比较适用于中小型方程组。对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。故能有效地解一些高阶方程组。线性方程组的数值解法AX=bnnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111（4.1）1．三角形方程组的解法---回代法（对角型方程组略）nnnnnnbxaxaxabxaxabxa221122221211111（4.2）nnnnnnnnbxabxaxabxaxaxa2222211212111（4.3）§4.1消元法2．顺序高斯消去法1,3322111,223232221211,11313212111nnnnnnnnnnnnnnaxaxaxaxaaxaxaxaxaaxaxaxaxa基本思想：通过消元将上述方程组化为三角形方程组进行求解。（1）消元过程其中第一步：若,0)1(11a用)1(11)1(11/aamii乘第一行加到第i行中，得到.00)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11nnnnnnnbbbxxxaaaaaaa),,3,2,(,)1(11)1()2(njiamaajiijij),,3,2(,)1(11)1()2(nibmbbiii第二步：若,0)2(22a用…….……第k步：若,0)(kkka用)()(/kkkkikikaam乘第k行加到第i行中，得到.00)1()1(1)()1(111)1()1(1)1(1)1(11)()(1)()1(1)1(11)1(1)1(11knkkkknkkknnknkknkkkkkknkkkkkknkkbbbbxxxxaaaaaaaaaaa其中),,1,(,)()()1(nkjiamaakkjikkijkij),,1(,)()()1(nkibmbbkkikkiki第n-1步：…….000)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa（2）回代过程若,0)(nnna则)()(nnnannbnx)1,,1(,)(1)()(nkkkkankjjxkkjabxkkk顺序高斯消去算法高斯消去法计算复杂度顺序Gauss消去法可执行的前提定理1给定线性方程组，如果n阶方阵的所有顺序主子式都不为零，即则按顺序Gauss消去法所形成的各主元素均不为零，从而Gauss消去法可顺利执行。AxbA()(1,2,)kkkakn注：当线性方程组的系数矩阵为对称正定或严格对角占优阵时，按Gauss消去法计算是稳定的。,0,0222112112111aaaaDaD01111kkkkkaaaaD顺序Gauss消去法计算过程中的akk(k)称为主元素，在第k步消元时要用它作除数,则可能会出现以下几种情况1、若出现akk(k)＝0，消元过程就不能进行下去。2、akk(k)≠0，消去过程能够进行，但若|akk(k)|过小，也会造成舍入误差积累很大导致计算解的精度下降。例4-1在四位十进制的限制下，试用顺序Gauss消去法求解如下方程组9812.4120032001.1291.58334.06781.0167.001.0012.0321321321xxxxxxxxx此方程组具有四位有效数字的精确解为x1＝17.46，x2＝－45.76，x3＝5.546解用顺序Gauss消去法求解，消元过程如下0.981200.41200320010.12910.58334.0000.16781.01670.00100.00120.0231017981044541467041.44010.8101000.006781.01670.00100.00120.05531065171011750041.44010.8101000.006781.01670.00100.00120.0经回代求解得x3＝5.546，x2＝100.0，x1＝－104.0和此方程组的精确解相比x3＝5.546，x2＝－45.76，x1＝17.46有较大的误差。对于此例，由于顺序Gauss消去法中的主元素绝对值非常小，使消元乘数绝对值非常大，计算过程中出现大数吃掉小数现象，产生较大的舍入误差，最终导致计算解x1＝－104.0和x2＝100.0已完全失真。为避免这种现象发生，可以对原方程组作等价变换，再利用顺序Gauss消去法求解。0.981200.41200320010.12910.58334.0000.16781.01670.00100.00120.06781.01670.00100.00120.010.12910.58334.0000.10.981200.412003200写出原方程组的增广矩阵：针对第一列找出绝对值最大的元素，进行等价变换：644.01670.0105500.0079.11909.54584.000.981200.41200320025329.00961.00079.11909.54584.000.981200.412003200求得方程的解为：x3＝5.546，x2＝－45.76，x1＝17.46精确解为：x3＝5.546，x2＝－45.76，x1＝17.46由此可见，第二种Gauss消去法的精度明显高于顺序Gauss消去法，我们称它为列主元Gauss消去法。列主元Gauss消去法与顺序Gauss消去法的不同之处在于：后者是按自然顺序取主元素进行消元前者在每步消元之前先选取主元素然后再进行消元3、列主元Gauss消去法计算步骤：1、输入矩阵阶数n，增广矩阵A(n,n+1);2、对于nk,,2,1(1)按列选主元：选取l使0maxikniklkaa(2)如果，交换A(n,n+1)的第k行与第l行元素kl(3)消元计算：nkiaamkkikik,,11,,1,,1,nkjnkiamaakjikijij3、回代计算1,,1,11,nnixaaxnijjijnii从§4.1中讨论可知，顺序Gauss消去法的消元过程是将增广矩阵[A，b]＝[A（1），b（1）]逐步化为矩阵[A（n），b（n）]。现在说明，在消元过程中，系数矩阵A＝A（1）是如何经矩阵运算化为上三角矩阵A（n）。即用矩阵运算的观点来看，消元的每一步计算等价于用一个单位下三角矩阵左乘前一步化得到的矩阵。)1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nnnnnnaaaaaaaaaA?§4.2直接分解法)1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(nnnnnnaaaaaaaaaA若，令，i＝2，3，…，n，0)1(11a)1(11)1(11/aalii得到下三角矩阵1001011131211nlllL施行第一步消元，我们得到(1)(2)(1)(2)11,LAALbb)2()2(2)2(2)2(22)1(1)1(12)1(11)1(1)2(00nnnnnaaaaaaaALA若，令，i＝2，3，…，n，则有0)2(22a)2(22)2(22/aalii10101012322nllL施行第二步消元，我们得到(2)(3)(2)(3)22,LAALbb)3()3(3)3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)2(2)3(00000nnnnnnaaaaaaaaaaaALA如此下去，施行第n－1步消元，得到)2()2(2)2(22)1(1)1(12)1(11)1(1)(nnnnnnnaaaaaaALA(n)由此可见，在顺序Gauss消去法的过程中，系数矩阵A＝A（1）经过一系列单位下三角矩阵的左乘运算化为上三角矩阵A（n），即)1(1)(nnnALA)2(21nnnALLALLLLnn1221这时)(111211nnALLLA11111nkkkkllL由111111nkkkkllL得)(111211,nnAULLLL令容易验证1111121323121111211nnnnnllllllLLLL则从顺序Gauss消去法的矩阵运算表示式可知，系数矩阵A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，即LUALLLAnn)(111211nnnnuuuuuu22211211其中)()2(2)2(22)1(1)1(12)1(11)(nnnnnnaaaaaaAU第一个方程组的系数矩阵为下三角矩阵，第二个方程组的系数矩阵为上三角矩阵，两个方程组都非常容易求解，具体求解结果如下：我们将A=LU称为矩阵A的三角分解,这时线性方程组为：bAXbLUX令YUX则有YUXbLYbLY对于nnnnnnbbbbyyyyllllll3213211213231211111由nkylbybykiikikk,,3,2,1111解得YUX对于nnnnnnyyyxxxuuuuuu212122211211由1,,2,1,/1nniuxuyxuyxiinijjijiinnnn求得bAX可以看出对于方程组：只要对系数矩阵作了三角