第3章 线方程组的直接解法.docVIP

第三章 线性方程组的数值方法 ? 在自然科学和工程技术中很多问题的解决常常归结为求解线性代数方程组. ? 当它的系数行列式不为零时，由克莱姆法则可以给出方程组的唯一解，但是这一理论上完 善的结果，在实际计算中可以说没有什么用处。因此如何建立在计算机上可以实现的有效而实用的解法，具有极其重要的意义。这些方法大致可分为两类：一类是直接法，就是经过有限步算术运算,可求得方程组精确解的方法(如果每步计算都是精确进行的话)；另一类是迭代法，就是用某种极限过程去逐步逼近其精确解的方法. 本章将阐述这两类算法中最基本的高斯消元法及其变形、矩阵分解法、雅可比迭代法、高斯 -塞德尔迭代法等. ? 第一节 高斯消元法 ? 一 回代过程  设系数矩阵为阶上三角矩阵的线性方程组 如果都不等于零，则由方程组(1)自下而上可以逐次求出为 按上述公式求方程组(1) 解的过程称为回代过程. 不难看出，解方程组(1)共需次加法和次乘法.这恰好是用一个阶三角方阵乘维向量所需的运算次数。当较大时,，同时加法运算速度远快于乘法的运算速度，所以，可用次乘法来近似表示回代过程的运算量. 二 消元过程 设有线性方程组 为了符号统一，记, 则原方程组改写成 如果，那么就可以保留其中第一个方程并利用它分别与其余方程消去第一个未知量.令 则以乘第一个方程加到第个方程中，就把方程组化为 其中 由方程组(3′)化为(5)的过程中，元素起着特殊的作用，特把元素称为主元素. 如果方程组(5)中, 则以为主元素，并利用类似的方法消去第个方程中的第二个未知量，即令 则以乘以第二个方程加到第个方程中,于是得到新的方程组 ? 其中 重复上述过程步后，我们得到原方程组等价的系数矩阵为三角形方阵的方程组 其中 把方程组(3)逐步化为方程组(10)的过程称为消元过程.最后，由回代过程可求得原方程组的解为 这种通过消元、再回代的求解方法称为高斯(Gauss)消元法(其特点是始终消去主对角线下方的元素). 注意到，上标仅仅用来识别一次消元前后系数矩阵的变化，而变为后,不再使用，所以在计算机存贮中只要用冲掉即可；另一方面，主元素所在列中主元素下面的各元素在消元过程中必然是零，而且在后面将要列出的回代过程中也不用它们，所以没有必要通过计算得到它们，从而在消元过程中就可从开始，这样做还可以节约计算时间. 例1 用高斯消元法求解方程组 解 用第一个方程消去后两个方程中的，得 再用第二个方程消去第三个方程中的，得 最后，经过回代求得方程组的解为 三 高斯消元法的条件与运算量 从消元过程可以看出，对于阶线性方程组，只要各步主元素不为零，即，经过步消元，就可以得到一个等价的系数矩阵为上三角形阵的方程组，然后再利用回代过程可求得原方程组的解.因此,有下面结论. 定理1 如果在消元过程中的主元素不为零，即(k=1,2,…,n),则可通过高斯消元法求出的解. 矩阵在什么条件下才能保证,下面的定理给出了这一条件. 引理 在高斯消元过程中系数矩阵的主元素不为零，即(k=1,2,…，n)的充要条件是矩阵的各阶顺序主子式不为零，即 证明 首先利用归纳法证明引理的充分性，显然 ，当时，引理的充分性是成立的，现假设引理对时也成立，求证引理对也成立，由归纳法假设有 , 于是可用高斯消元法将化为 且 由假设所以有. 反过来,由上式可知必要性是显然的. 定理2 如果阶矩阵的所有顺序主子式均不为零，即则可通过高斯消元法求出的解. 下面考虑求解(3)的高斯消元法的运算量.消元过程需要除法 次，而需要的乘法和加法的次数都是 加上回代过程的运算次数，共需乘、除法的次数为 加、减法的次数为 当较大时,,消元过程的运算量远大于回代过程，从而，高斯消元法中乘除法的次数与加减法的次数近似为. 第二节????? 高斯主元素消元法 一 问题的提出 由高斯消元法可知，在消元过程中如果出现的情况，这时消元法将无法进行；另一方面，即使主元素，但很小时，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，最后也使得计算结果很不可靠. 例1?????? 解方程组 (它的精确解为) 解法一 用高斯消元法求解(取5位有效数字)，用第一个方程消去第二个方程中的得 因而再回代，得 显然，这个解与精确解相差太远，不能作为方程组的近似解其原因是我们在消元过程中使用了小主元素，使得约化后的方程组中的元素量级大大增长，再经舍入使得计算中舍入误差扩散，因此经消元后得到的三角形方程组就不准确了.为了控制舍入误差，我们采用另一种消元过程. 解法二 为了避免绝