n方程组直接解法.

2020年1月11日星期六2/88第3章线性方程组解法本章主要内容Gauss消元法直接三角分解法误差分析迭代法2020年1月11日星期六3/88§3.1Gauss消元法高斯消元法是一个古老的直接法，由它改进得到的选主元的消元法，是目前计算机上常用于求低阶稠密矩阵方程组的有效方法，其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题。2020年1月11日星期六4/88(一)引言为便于以下讨论,把涉及到的有关名词及问题的引出暂介绍如下:含n个未知量的线性方程组a11x1+a12x2+…+a1nxn=b1┆┆┆(1)an1x1+an2x2+…+annxn=bn其中，系数a11,…,a1n，a21,…,a2n，…，an1,…,ann是给定的常数；b1,…,bn也是给定的常数，通常称为常数项，或称为方程组的右端。方程组(1)也常用矩阵的形式表示，写为Ax=b(2)§3.1Gauss消元法2020年1月11日星期六5/88其中,A是由系数按次序排列构成的一个n阶矩阵,称为方程组的系数矩阵,x和b都是n维向量,称b为方程组的右端向量。使方程组(1)中每一个方程都成立的一组实数x1*,x2*,…,xn*称为式(1)的解,把它记为向量的形式，称为解向量。nnnnnnnnxxxxbbbbaaaaaaaaaA2121212222111211我们总是希望方程组有解，且有唯一解。由线性代数的克莱姆(cramer)规则可知，如果方程组(1)的系数矩阵A的行列式(一般记为D=|A|)不等于零，那么这个方程组有唯一解。§3.1Gauss消元法2020年1月11日星期六6/88克莱姆规则在理论上尽管是完善的，但在实际计算中却没有什么实用价值。本章我们将重点讨论求解线形方程组的一种有效的数值方法。解线性方程组的数值方法很多，但归纳起来可分为两类：①精确解法(或直接解法),是指它只包含有限次四则运算，且每一步运算过程都不发生舍入误差的假设下，计算的结果就是原方程组的精确解。但实际中不可能没有舍入误差，因而精确解法的解并不见得精确，可能仍是近似值。②迭代法，是指把方程组的解看作是某种极限过程(逐次逼近)的极限，而在实现这一极限过程的每一步的结果，是把前一步的结果施行相同的演算步骤得到的。同样地，我们不可能把极限过程进行到底，而是将迭代过程进行了有限次，使其结果达到一定的§3.1Gauss消元法2020年1月11日星期六7/88精度要求。因而，用实际计算办法解方程组，算出的解x一般不是它的精确解x*。把ε＝x*－x叫做近似解x的误差(向量),ε的“大小”是衡量近似解好坏的一个标准。但x*一般不可知,因此只好设法估计ε的界。用A作用于定义式，有r=Aε=Ax*－Ax=b－Ax而这是容易计算的，通常称之为残向量。并用它的大小作为衡量近似解的另一个标准。不过单凭r的大小或ε的大小都不足以判断近似解的好坏。比如r确实很小，可A–1很大，则ε=A–1r可能很大。反之亦然.此外，怎样衡量向量ε、r及矩阵A、A–1的大小呢？这需要范数的有关知识(后面再讲)。§3.1Gauss消元法2020年1月11日星期六8/88如何评价解法的好坏，主要有三个标准：①精度高；②计算量小；③存储单元少。但这些要求往往是矛盾的。值得注意的是，要考虑方程组Ax=b或方阵A的特性。主要有：①是否稀疏；②是否为带状；③是否为对称且正定。此外还涉及对角占优和不可约等重要概念。(二)求解线形方程组的消元法消(元)去法是求解线形方程组Ax=b(2)和满秩矩阵的逆阵A-1的一种直接方法。尽管它比较古老，但它具有演算步骤、推算公式都系统化的特点(对其中选主元消去法，还可以证明是稳定的)。因此，它至今仍然是求解方程组的一种有效的方法。§3.1Gauss消元法2020年1月11日星期六9/881.三角形方程组的解法三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一，实际上消元法就是通过简化一般线性方程组为三角形方程组后再求解的。上三角方程组的一般形式是：nnnniinnnnnnnnnnnbxaniabxaxabxaxabxaxaxa),......,2,1(0....................................................................................................111112222211212111其中§3.1Gauss消元法2020年1月11日星期六10/88nikiikikiinnnnaxabxabx1/)(,/nikiiikikinnnnxaxabnniForxab1/)(1.21,,2,1.2/.1为求解上面的上三角方程组，从最后一个方程开始，先解出，然后按方程从后向前顺序，用已求出的值，从方程中依次解出。这样就完成了上三角方程组的求解过程。这个过程的计算公式为：nnnnabx/kx121,....,,xxxnn§3.1Gauss消元法2020年1月11日星期六11/8822221211111bxaxabxa下三角方程组的一般形式为：111111),,3,2(/)(/ikiikikiiniaxabxabxniaii,,2,1,0其中下三角方程组可以参照上三角方程组的解法求解，求解顺序为从第一个方程开始，按从上到下的顺序，依次解出，计算公式如下：nxxx,,,21nnnnnnbxaxaxa2211如上解三角方程组的方法称为回代法。§3.1Gauss消元法2020年1月11日星期六12/8894232221321211xxxxxx组用回代法求解线性方程例次加法与乘法。（个除法与需求解一个三角形方程组所以，解为解ninnninxxxxxx1232132121)1(21)1)1,1,1(),,(14/)12139(11/)12(12/2:§3.1Gauss消元法2020年1月11日星期六13/882.Gauss消元法(一)高斯消去法的求解过程,可大致分为两个阶段:首先,把原方程组化为上三角形方程组,称之为“消去”过程;然后,用逆次序逐一求出三角方程组(原方程组的等价方程组)的解,并称之为“回代”过程.下面分别写出“消去”和“回代”两个过程的计算步骤.消去过程:第一步:设a110,取做(消去第i个方程组的x1)第i个方程－li1第一个方程i=2,3,…,n则第i个方程变为1111/aalii)1()1(2)1(21)1(1ininiibxaxaxa§3.1Gauss消元法2020年1月11日星期六14/88因为可得第一步消元后的方程组为)1()1(2)1(2)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnbxaxabxaxabxaxaxai,j=2,3,…,niijijiiiijijijibbaablbbalaa)0()0()0(11)0()1()0(11)0()1(,,,i,j=2,3,…,n01111111111)1(1aaaaalaaiiiii§3.1Gauss消元法2020年1月11日星期六15/88若将消元公式用矩阵描述，相当于用一个矩阵L1左乘A和b，即L1A=A(1),L1b=b(1)。其中10001011131211nlllL§3.1Gauss消元法2020年1月11日星期六16/88第二步:设,取做(消去第i个方程组的x2,i=3,4,…,n)第i个方程－li2第二个方程i=3,4,…,n类似可得第二步消元后的方程组为0)1(22a)1(22)1(22aalii)2()2(3)2(3)2(3)2(33)2(33)1(2)1(22)1(22)0(1)0(12)0(121)0(11nnnnnnnnnnnbxaxabxaxabxaxabxaxaxanjiblbbalaaiiijijiji,...,4,3,,)1(22)1()2()1(22)1()2(§3.1Gauss消元法2020年1月11日星期六17/88第k步:设,取做(消去第i个方程组的xk,i=k+1,k+2,…,n)第i个方程－lik第k个方程i=k+1,k+2,…n类似可得第k步消元后的方程组为0)1(kkka)1()1(kkkkikikaal)()(1)(1)(1)(11)(11)1(2)1(22)1(22)0(1)0(12)0(121)0(11knnknnkkknkknknkkkkknnnnbxaxabxaxabxaxabxaxaxankkjiblbbalaakkikkikikjkikkjikji,...,2,1,,)1()1()()1()1()(§3.1Gauss消元法2020年1月11日星期六18/88同样，将第k步消元公式用矩阵描述，相当于用一个矩阵Lk左乘A(k-1)和b(k-1)，即LkA(k-1)=A(k),Lkb(k-1)=b(k)。其中1111,,1knkkkllL§3.1Gauss消元法2020年1月11日星期六19/88继续下去到第n-1步消元,可将线性方程组化为如下上三角方程组:次消元后的系数，表示第的上标和其中kkbabxabxaxabxaxaxakikjinnnnnnnnnn)()()1()1()1(2)1(22)1(2211212111nkkjiblbbalaaaalnkkkikkikikjkikkjikjikkkkkiik,...,2,1,/1,,3,2,1)1()1()()1()1()()1()1(对计算公式为§3.1Gauss消元法2020年1月11日星期六20/88此时，A(n-1)为上三角矩阵，记作U。用矩阵乘法表示这n-1步消元过程，即于是令则有A=LU其中L为下三角矩阵。这说明，Gauss消元法过程可将矩阵A分解为一个单位下三角矩阵L与一个上三角矩阵U的乘积。)1(1221)1(1221nnnnnnbbLLLLAALLLL)1(11121211nnnALLLLA)1(11121211,nnnAULLLLL§3.1Gauss消元法2020年1月11日星期六21/881111121323121nnnnllllllL§3.1Gauss消元法nnnnnuuuuuuuuuuU3332232211312112020年1月11日星期六22/88EndxaxabnnkForxabbbabnkkjaaaaaaankkiForstopthenaIfnkForxxxnjibanGaussGaussnjkkkjkjknnnikikiijkjikijikkkikkkniij4/)(1.31,,2,13/23.2.1),,2,1(2.2.1/1.2.1,,2,12.101.11,,2,11,,,),,2,1,(,,,121输出“不能消元”，步骤输出输入的解。消元法来求线性方程组本算法用说明消元法算法：§3.1Gauss消元法2020年1