常用数值分析方法§2线性方程组的数值解法.ppt

2 线性方程组的数值解法,2.1 概述 2.2 Gauus 消元法 2.3 主元素法 2.1 引入主元素法的必要性 2.2 列主元素法 2.3 全主元素法 2.4 Jacobi迭代法 2.5 Gauss-Seidel迭代法,2.1 概 述,在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法在工程计算中占有较重要的地位。,设n阶线性方程组：,其矩阵形式为：,Ax=b (2-2),其中：,求解Ax = b，曾经学过克莱姆(Cramer)法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们都知道，Cramer法则在理论上是绝对正确的，但当 n较大时， 在实际计算中却不能用。,如果线性方程组Ax = b的系数行列式不为零，即det(A) 0，则该方程组有唯一解。,线性方程组的数值解法,解线性方程组的数值方法大致分为两类：,请注意：由于在计算中某些数据实际上只能用有限位小数，即不可避免地存在着舍入误差的影响，因而即使是准确的直接解法，也只能求到近似解。 直接法在求解中小型线性方程组（100个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。,直接法：指假设计算过程中不产生舍入误差，经过有限步四则运算可求得方程组准确解的方法。,2. 迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。,线性方程组的 直接解法,2.2 Gauss消元法,Gauss消元法是最基本的一种方法，下例说明其基本思想:,例1,解线性方程组：,解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：,例1（续）,上述 Gauss 消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。,再消一次元得：,二次消元后将方程 化为倒三角形式，然后 进行回代容易解出： x3 = 3, x2 = 2, x1 = 1。,我们的目的，是要总结归纳出一般情况下的n阶线性方程组的消元公式和回代求解公式，从而得到求解n阶线性方程组的能顺利在计算机上实现的行之有效的算法。,Gauss消元法的基本步骤1（4阶）,为能更清楚地得到算法，下面以4阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的n阶线性方程组。,可以检查，分别以li1乘第一个方程加到第i个方程上可以完成第一次消元，得同解方程组：,变化以后的方程组系数及右边的常数项可总结出如下的计算公式：,Gauss消元法的基本步骤1（4阶）,Gauss消元法的基本步骤2（4阶）,以方程组中第i个方程减去第二个方程乘li2 (i = 3, 4)，完成第二次消元。,上标为3的系数 和右端项可由 下面公式计算：,Gauss消元法的基本步骤3（4阶）,第三步：消元：消x3（4阶方程组需进行3次消元） 将上述 A (3) X = b(3) 中最后一个方程中的x3消为零：,然后可回代求解：由于A(4)为上三角形，所以可按变量的逆序逐步回代求原方程组的解：,上述 消元、回代求解过程 很容易推广到一般的n阶线 性方程组。,经过上述消元步骤， 得到同解的上三角形方程组：A (4) x = b(4),Gauss消元法的消元过程1、2（n阶）,一般地，设 n阶方程组：,消元过程为：,Gauss消元法的消元过程3（n阶）,第k 步：设第k1步消元后得原方程组的同解方程组为：,第k步消元后同解方程组中上标为k+1的元素的计算公式见下屏：,照此消元下去，完成n1次 消元后，可将原方程组化成 同解的上三角形方程组如下：,Gauss消元法的消元过程3（n阶）,Gauss消元法的回代过程（n阶）,回代过程：逐步回代求得原方程组的解：,Gauss 消元法的优缺点：,缺点：但其计算过程中，要求akk(k)（称为主元素）均不为零，因而适用范围小，只适用于从1到n 1阶顺序主子式均不为零的矩阵A，计算实践还表明，Gauss消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。,优点：Gauss消元法简单易行。,2.3 主元素法,2.3.1 引入主元素的必要性 对线性方程组AX = b，若其系数行列式 det(A) 0，则该方程组有唯一 解，但是这一条件 不能保证所有主元素都不等于零，只要某一主元 素等于零，就不能用Gauss消元法求解该方程组， 即使所有主元素不等于零，但 某一主元素的绝对 值很小时，Gauss消元法也是不适用的。如下例：,例2,例2（续1）,解：为减小误差，计算过程中保留3位有效数字。 按Gauss消元法步骤：,第一次消元后得同解方程组：,第二次消元后得同解方程组：,回代得解，x3 = 2.02，x2 = 2.40，x1 = 5.80。 容易验证，方程组（3-8）的准确解为： x1 = 2.60， x2 = 1.00，x3 = 2.0。,显然两种结果相差很大。,若在解方程组前，先交换方程的次序， 如将（2-8）交换一行与二行改写成如下所示：,再用Gauss消元法，顺序消元后得同解方程组：,回代得解：x3 = 2.00，x2 = 1.00，x1 = 2.60 与准确解相同。,例2（续2）,例2两种解法的误差分析,在例2中，对(2-8)的方程进行顺序消元时， 主元a(1)11=0.50，a(2)22=0.100都比较小，以它们作 除数就增长了舍入误差,而导致计算结果不准确。,产生上述现象的原因在于舍入误差，当|a(k)kk| 很小时，进行第k次消元，要用|a(k)kk|作除数，这 样就可能增大舍入误差造成溢出停机，或者导致 错误的结果。,为了在计算过程中，抑制舍入误差的增长， 应尽量避免小主元的出现。如例2的第二种解法, 通过交换方程次序，选取绝对值大的元素作主元， 基于这种思想而导出主元素法。,2.3.2 列主元素法,为简便起见，对方程组（2-1），用其增 广矩阵（2-9）表示，并直接在增广矩阵上进行运算。,列主元素法的具体步骤如下：,列主元素法（续）,如此经过n1步，增广矩阵（2-9）被化成上三角形，然后由回代过程求解。 在上述过程中，主元是按列选取的，故称为列主元法。例2中的第二种解法就是按列主元法进行的。,2.3.3 全主元素法,经过nk次消元后，得到与方程组（2-1）同解的 上三角形方程组，再由回代过程求解。,主元素法举例,例3,计算过程保留三位小数。,此例的计算结果表明，全主元素法的精度优于列主元法，这是由于全主元法是在全体元素中选主元，故它对控制舍入误差十分有效。但是全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂,计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，且计算经验与理论分析均表明，它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好方法之一。,线性方程组的 间接解法,方程组的迭代解法概述,下面将讨论线性方程组的另一类解法迭代法，由于 迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别 适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏） 的线性方程组。 解线性方程组的迭代法的基本思想与解方程的迭代法相 似，首先将方程组Ax = b化为等价方程组x = Mx + g，其中M 为n阶方阵，b = (b1,b2,bn)T，g Rn，任取初始向量x(0) Rn， 代入迭代公式：,产生向量序列x(k)，若此序列收敛于x*，则有x* = Mx*+g，即x*为原方程组的解。因此，可根据精度要求选择一个合适的x(k)（k充分大时）作为近似解，这就是解线性方程组的迭代法，上式称为迭代格式，M称为迭代矩阵，若序列x(k)极限存在，称此迭代过程收敛，否则称为发散。,2.4 雅可比（Jacobi）迭代法,设有n阶线性方程组：,简记为：,其系数矩阵A非奇异，不妨设aii 0 (1,2,n)可将上式 改写为等价方程组：,或,雅可比（Jacobi）迭代法（续）,也可写作为：,可简记为：,由此可建立迭代格式：,Jacobi迭代法定义,选取初始向量x(0)代入（2-13）右端，可得x(1) = Bx(0) + g， 再将x (1)代入（2-13）右端，可得x(2) = Bx(1) + g，如此继续下去， 就产生一个向量序列x(k)，按（2-11）或（2-12）格式迭代求解 的方法称为雅可比（Jacobi）迭代法，又叫简单迭代法。 迭代式（2-13）中的M 称为迭代矩阵，它可直接由（2-11） 或（2-12）得到，也可用系数矩阵A来表示：,若将系数矩阵A分解为A = DLU，其中：,紧接下屏,Jacobi迭代法定义（续）,式（2-14）为简单迭代法的矩阵形式。,Jacobi迭代法举例,例4：用Jacobi迭代法求解线性方程组：,解：由第一个方程解x1，第二个方程解x2，第三个方程解x3得Joacbi迭代格式为：,继续迭代下去，迭代结果见表2-1：,取x(0) = (0,0,0)T代入迭代式 （2-15）或（2-16）得：,例4（续）,迭代9次，得近似解x(9) = (10.9994, 11.9994, 12.9992)T，此方程组的准确解为x =(11, 12, 13)T，从表2-1可以看出：随着迭代次数的增加，迭代结果越来越接近精确解。,2.5 高斯塞德尔(Gauss-Seidel)迭代法,Jacobi迭代法的优点是公式简单，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算x(k+1)时是用x(k)的全部分量代入求x (k+1)的全部分量。因此需同时保留两个近似解向量x(k)和x(k+1)。,高斯塞德尔(Gauss-Seidel)迭代法（续1）,Gauss-Seidel迭代法的迭代格式为：,高斯塞德尔(Gauss-Seidel)迭代