第三章线性方程组的数值解法

第三章线性代数方程组的数值解法3.1引言3.2解线性方程组的消去法3.3解线性方程组的矩阵分解法3.4解线性方程组的迭代法3.1引言给定一个线性方程组)13(bAxnnnnnnnnnnijbbbbxxxxaaaaaaaaaaA2121212222111211,,)(这里求解向量x。第一类是直接法。即按求精确解的方法运算求解。第二类是迭代法。其思想是首先把线性方程组(3-1)等价变换为如下形式的方程组：数值解法主要有两大类：)23(fxMxnnnnnnnnnijffffmmmmmmmmmmM21212222111211)(，其中然后构造迭代格式)33(1fxMxkk这称为一阶定常迭代格式，M称为迭代矩阵。3.2解线性方程组的消去法3.2.1高斯消去法与高斯若当消去法例1第一步：先将方程（1）中未知数的系数2除（1）的两边，得到下列方程组：1x6224524212321313213211xxxxxxxxI620245242123211归一620245241312622452413231321321xxxxxxxx解：1、消元过程矩阵的观点再将第二个方程减去第一个方程的4倍，第三个方程减去第一个方程的2倍。52421232132323212xxxxxxxI第二步：将方程中第二个方程的两边除以的系数45214121232132323211xxxxxxxII2I2x511021402123211”消元“51104241102123211”归一“294321412123213323212xxxxxxII将第三个方程减去第二个方程：第三步：为了一致起见，将第三个方程中的系数变为1，621412123213323211xxxxxxIII3x61002141102123211”归一“2943004241102123211”消元“2、回代过程：321-6-19xxx)13(bAx下面我们来讨论一般的解n阶方程组的高斯消去法，且就矩阵的形式来介绍这种新的过程：)0(24)0(4)0(42)0(41)0(13)0(3)0(32)0(31)0(12)0(2)0(22)0(21)0(11)0(1)0(12)0(110)0()0(1,)0()0(,,nnnnnnnnniiiijijaaaaaaaaaaaaaaaabAabbaa）（则增广矩阵为：记）（一、高斯消去法高斯消去法：（1）消元过程：对k=1,2,…,n依次计算)43()1,,1;,,2,1()1;,2,1(/)()1()1()()1()1()(nkjnkkiaaaankkjaaakjkkkikjikjikkkkjkkjk(2)回代过程：)53()1,,1,(1)()(1)(1nnkxaaxaxnkjjkjkknkknnnn例3.1试用高斯消去法求解线性方程组542832852432121321xxxxxxxx375.25.1045.220225.15.01542180328524消元归一bA消元过程为解0100225.110225.15.010625.400225.110225.15.01”归一“”归一““消元”即把原方程组等价约化为0225.1225.15.0332321xxxxxx据之回代解得120123xxx为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为单位矩阵I，从而得到解，即xIbA行初等变换这一无回代的消去法称为高斯-若当（Jordan）消去法二、高斯-若当（Jordan）消去法解归一消元641202524312.1321xxx解方程组例没有回代过程),(),(xIbA511021402123211620245241312),(bA归一消元归一消元29430021411043811015110214110212321161001010900161002141104381101619321xxx例2试用高斯-若当消去法求解例3.1的线性方程组。因为0100201010010625.400225.1101875.101375.25.1045.220225.15.01542180328524bATx021,解所以解高斯-若当（Jordan）消去法一般公式：)1,,1;,,1,1,,1()1;,2,1(/)()1()1()()1()1()(nkjnkkiaaaankkjaaakjkkkikjikjikkkkjkkjk高斯约当消去法是一个具有消去过程而无回代过程的算法。以上两种消去法都是沿系数矩阵的主对角线元素进行的，即第k次消元是用经过前k-1次消元之后的系数阵位于（k,k)位置的元素作除数，这时的(k,k)位置上的元素可能为0或非常小，这就可能引起过程中断或溢出停机。3.2.2消去法的可行性和计算工作量定理3.1如果的各阶顺序主子式均不为零，即有),3,2(0,01111111nkaaaaDaDkkkkk即消去法可行。推论若系数矩阵严格对角占优，即有),2,1(1niaanjijijii),,3,2(/,1)1(1)0(11nkDDaDakkkkk则消去法可行，且定理3.2求解n阶线性方程组(3-1)的高斯消去法的乘除工作量约为，加减工作量约为；而高斯-若当消去法的乘除工作量约为，加减工作量约为。3/3n3/3n2/3n2/3n注意：高斯-若当消去法求解矩阵方程和求矩阵的逆矩阵例3.3试用高斯-若当消去法求解如下矩阵方程3332312322211312117761061532,232143012,xxxxxxxxxXBABAX01210011001021100108.26.58.20016.08.04.01022.14.12.0012442205.25.1215.205.25.1105.017762321061143532012BA012110211X所以解：)~()(BIBABAX)()(1AIIAIAX其中X是矩阵3.2.3选主元素的消去法主元素的选取通常采用两种方法：一种是全主元消去法；另一种是列主元消去法。下面以例介绍选主元的算法思想例3.4试用选主元消去法解线性方程组12510034510412321xxx（1）用全主元高斯消去法回代解出：1~,3~,0~123xxx还原得：1~,0~,3~133221xxxxxx解0100375.01012.00103.100375.01012.00162.0201234012.00112430622.00102.011243010214501512034551010412)2()2()1()1(bAbAbA记为记为1,0,3321xxx故得解为（2）用全主元高斯-若当消去法110000103001112.00003.103075.01112.00602.0212034112.0012034602.025510120341041212034551010412)2()2()2()1(bAbA记为记为归一、消元主元主元主元归一、消元归一、消元（3）用列主元高斯消去法回代解得3,0,1123xxx110055103075.015.65.60055103075.01445.0055103075.0110412551012034120345510104123.3解线性方程组的矩阵分解法一、非对称矩阵的三角分解法矩阵分解法的基本思想是：nnnnllllllL21222111nnnnuuuuuuU22211211可逆下三角矩阵可逆上三角矩阵)0(AbAx对于给定的线性方程组LUA（1）分解——解两个三角形方程组。(2)UxyAxbLUxbLyb定理3.3分解。—为单位上三角为下三角，分解。—为上三角为单位下三角，CroutULDoolittleUL.2的对角元则唯一。或分解不唯一，但规定了UL.1注意角阵）分别为可逆的下，上三则的各阶顺序主子式若ULLUAnkDAk,(),,,2,1(0矩阵的Crout分解的计算公式nnnnnnaaaaaaaaa212222111211nnnnllllll212221111112112nnuuu001]00[1111jjjiiiiiijuulllajiululjilulikijiikjikjkijkjik1111010k规定),,1;1,,2,1(/)(),,2,1;,,2,1(1111nijnilulauijniulalikiikjikijijjkkjikijij(3-12)Crout分解的计算公式Crout分解的计算公式的记忆方法44434241343332312423222114131211aaaaaaaaaaaaaaaa4443424141343332313124232221211414131312121111)()()()()()()(aaalaaaalaaaalauauauala4443424141343332313124232221211413121111)