解线性方程组的直接法和迭代法.docx

精品文档知识共享 精品文档知识共享 数值分析方法中方程求解的直接法和迭代法 第3章 解线性方程组的直接法 消元法 高斯消元法（加减消元）：首先将A化为上三角阵，再回代求解。 IHa?勺11冃2川 IH a? 勺11 冃2川 a1n a21 ■r ■r a22 111 * ■ * * a2n b2 a r 0n1 * ■ an2 HI I ann r bn丿 步骤如下： 0 a2? a2s III a22n 0 a3s IH a33) 第一步：第1行 虫?第行,,2，川，n aii a11 a11 ai2 III a1n a a21 ■r ■r a22 * III * a2n - b2 ■ ■ an1 an2 III ann ■ bn an a12 III am b x 0 * a22) ■ III ■ d2) b⑵ a2n b2 r i ■f 1° ■ aS ■f ■ III F 1 F f2) b⑵ En un 丿 _a（2） 第二步：第2行 容 ?第行,i =3,Hl,n 0 a22)川 a22) 0 a22)川 a22) b22) + r 0 an22 m al? b2) a1 1 a 1 2 a 13IH 0 a22) a 2(32 川 0 0 a33) IH a n 1 b 1 .2宦(2) an3(3b 3(3) 10 比3）川 ann( 3 bn 类似的做下去，我们有: _a(k) 第k步：第k行 备 ?第i行,i二k 1^1, n akk n—1步以后，我们可以得到变换后的矩阵为: TOC \o 1-5 \h \z 1 ai1 ai2 ai3 川 ain D 0 a22) a22)川 a22n bf 0 0 a33)川 a33) b33) + 4 1 - - 9 3 o o 川 ann)bn注意到，计算过程中akk)处在被除的位置，因此整个计算过程要保证它不为 0 所以，Gauss消元法的可行条件为：akk—0。 就是要求A的所有顺序主子式均不为0, 即 勺1川 det + 卜 * H0,i =1,…，n ?1 川 aii j 因此，有些有解的问题，不能用 Gauss消元求解。 另外，如果某个akk)很小的话，会引入大的误差 列主元消元法 在Gauss消元第k步之前，做如下的事情: 若max | akk)1=1 a即|交换k行和j行 S 1 3养 广4 3 5 4 3 5- T 2 1 3 J 6 2 J 6 2 f f f 4 3 5 4 3 5 4 3 0 1 J 0 2 1 3 0 2丄 T — T — 2 2 4 4 4 4 0 21 3 0 1 1 0 0 3 4 4」 I 2 2」 I 7」 5 3 其实就按行变换，不改变方程组的解，同时又有效地克服了 Gauss消元地缺陷 Gauss-Jordan 消元法 将在Gauss消元第k步，变为(遇上an=0的则需要换一行)： —a(k) 第k行 青?第i行,i =1,Hl,k-1,k 1^1,n akk 将该行上、下三角地部分都变为 0,即对角阵，同时主元系数也要消，这样就不 用回代了。 巾0川o 0 1 : : \ 0e川o b 二、直接分解法 Gauss消元法的第k步： (k) 第k行二Or ?第i行,i二k川，n akk 从矩阵理论来看，相当于左乘矩阵: 1I (k)1 1 I (k) 1 k -1k I (k) ? 1ik ^C-^k〕|l|,n o akk l(k) 1nk 因此，整个Gauss消元法相当于左乘了一个单位下三角阵。 『1 121 .(k) 1k 1k 山1 HI(k) 山1 HI (k) 1nk 所以有LA=U , L为单位下三角阵，U为上三角阵。 二 A = L」U ,,Lv = b 因此 Ax =b= LUx =b= Ux = y 我们可以通过2次反代过程求解方程组，分解的理论由Gauss消元得出，因此分 解能够进行的条件与Gauss消元一样。 Doolittle 分解 L为下三角，U为单位上三角 III am 5 ■p1 U12 III Um III t ■ a2n * — l21 4■ 1 ■ ■ U22 III ■r U2n t III * ann」 ? J n1 ■ In2 III h Unn」 ai1 a!2 a21 a22 ■f q ■* 1 fnl an 2 j = hl l|,n = ui j = ai j 比较第 比较第1行：aij二Uy 比较第 1 列：ai^ li1u11 i =2川 |, n =■ lii ai1 U11 比较第2行：a?j工匚山“ U2j 比较第2列： ai2 = 1 1U12 +l 2U 22 勺1 冃2 III a1n 『1 a21 卡 ■f a22 II 1