第六章 消元法.pptVIP

* * * * * * * * * * * * * * * * * * * * * 3、算法分析 基本思想 在消元过程的第k步，若第k列的第k至第n个元素与其所在行的绝对值的最大元素之比为最大者，就选取它作为主元。这种方法就是按比例列主元消去法。 6.1.4 Gauss按比例列主元消去法 基本算法： s1:选取各行最大元放到mr[n]; s2:消元: k=0 到 n-2 s21:计算ms=a[k][k]/mr[k] 若msa[i][k]/m[i], i=k+1,…,n-1; ms= a[i][k]/m[i], rn=i s22：交换mr[k] mr[rn];a[k][k] a[rn][k]; s23：循环消元i=k+1,…,n-1 s231 计算消去比例因子l=-a[i][k]/a[k][k]; s232 按列j=k,…,n循环计算 a[i][j]=a[i][j]+l*a[k][j]; s3:回代计算方程组的解。 6.1.5 Gauss-jordan消去法 [基本思想] 解线性方程组的Gauss-Jordan消去法实际上就是无回代过程的gauss消去法。 Gauss-Jordan消去法（按列主元）的计算公式。用增广矩阵计算，并设第k步选取的主元为列主元，则在消元过程中有： [算法] s1:输入a[n,n+1],i,j; s2: 循环消元 k=0 到 n-1 m=a[k][k]; s21:选主元 i=k 到 n-1 若 ma[i][k] m=a[i][k]; r=i; 交换行r与k s22: 循环i=0到n-1(消元） if(i!=k) m=a[i][k]/a[k][k]; for(j=k; j=n; j++) { a[i][j]=a[i][j]+m*a[k][j]; } s23: output the result eliminated s3:循环k=0;k=n-1; x[k]=a[k][n]/a[k][k]; 例：用按列选主元的高斯-若当消去法求矩阵A的逆矩阵，其中 线性方程组解对系数的敏感性 在计算过程中，由于计算机字长的有限性，不可避免地产生所谓的舍入误差。同时，由于所求问题的初始数据（例如线形方程组的系数矩阵和右端项系数）往往是带有一定误差的。因此计算结果总是不可避免地带有误差，或者说，如果初始数据有扰动，势必将带来具有一定误差的计算结果。对A x = b来说，由于观测或计算等原因，线形方程组两端的系数A和b都带有误差 ?A和?b，这样实际建立的方程组是近似方程组 (A+?A)(x+?x)=b+?b。对近似方程组求出的解是原问题的真解x加上误差 ?x,即 x+?x。而? x是由?A及?b引起的，它的大小将直接影响所求解的可靠性。 这种解依赖于方程组系数的误差 ?A及 ?b的问题，称为线性方程组解对系数的敏感性。 方程组的系数矩阵发生微小扰动，就有可能引起方程组性质上的变化，这是方程组本身的“条件问题”。 相对误差关系式： 设原线形方程组 Ax= b 和近似方程组 (A+?A)(x+?x)=b+?b 在: 1、?A=0,?b?0 2、?A?0,?b=0 一般情形 由这些关系式可看到，带有扰动的近似方程组中，扰动的大小直接影响着所求解的相对误差，故可作如下定义： 定义：设 A 非奇异，称||A-1||||A|| 为矩阵A的条件数，记为Cond (A)，即Cond (A)= ||A-1||||A||. Cond (A)可反映出方程组解对系数的敏感性。对此，可通过下面的例子加以理解。 方程组 此方程组的准确解为x1=0, x2=-1。现将其右端加以微小的扰动 使之变为： 经计算可得准确解为x1=2, x2=-3. 这两个方程组的解相差很大，说明方程组的解对常数项b的扰动很敏感。同时注意到||