数值计算方法(第3章)1课件

第3章线性方程组的数值解法1引言在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组。

线性代数方面的计算方法就是研究求解线性方程组的一些数值解法与研究计算矩阵的特征值及特征向量的数值方法。2引言关于线性方程组的数值解法一般有两类。直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）高斯消去法和矩阵分解法迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法直接法适合中小规模迭代法适于大型线性方程，存在收敛性及收敛速度等问题3什么是n元线性方程组简记AX=bN个未知量N个方程4矩阵形式AX=b5克莱姆法则在理论上有着重大意义，但在实际应用中存在很大的困难，在线性代数中，为解决这一困难给出了高斯消元法。63.1高斯消元法3.1.1高斯顺序消元法3.1.2高斯主元消元法73.1高斯消元法用消元法解方程组回忆手工解法8消元过程9上述过程如何用程序写出？10消去过程GaussElimination(A[1..n，1..n],b[1..n])//输入：系数矩阵A及常数项b//输出：方程组的增广矩阵等价的上三角矩阵fori=1tondo A[i][n+1]=b[i]fori=1ton-1doifA[i][i]=0then停机else forj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]11高斯消去法的计算量—消元过程

fori=1tondoA[i][n+1]=b[i]fori=1ton-1doifA[i][i]=0then停机elseforj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]若把内层循环看成1个单位的工作量三层循环的总工作量是多少？12思考回代过程如何编写？将解xi存放在bi中，即第n+1列记载解的值。13高斯消去法的计算量—回代过程同样依据循环次数考虑14上标表示即将做第1次消元15第一次消元16设第k-1次消元得A(k)x=b(k)其中17高斯顺序消去法则第k次消元:18最后19高斯顺序消去法也就是对于方程组AX=b系数矩阵做：20高斯顺序消去法

21高斯顺序消去法

22高斯顺序消去法条件

从最内层循环看出顺序消去法的条件是A[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]233.1.2高斯主元素消去法Gauss列主元消元法：从列的角度控制循环当k=1时，考察第一列找出绝对值最大的元素最大元素在第二行交换第二行和第k=1行的位置在此基础上按前面的高斯顺序消去法消掉第一个变量24当k=2时，考察第二列找出绝对值最大的元素(除第1行)最大元素在第三行交换第三行和第k=2行的位置在此基础上按前面的高斯顺序消去法消掉第二个变量2526betterGaussElimination(A[1..n，1..n],b[1..n])//输入：系数矩阵A及常数项b//输出：方程组的增广矩阵等价的上三角矩阵fori=1tondoA[i][n+1]=b[i]fori=1ton-1dopivotrow=iforj=i+1tondoif|A[j,i]|>|A[pivotrow,i]|pivotrow=jifA[pivotrow,i]=0then停机elsefork=iton+1doswap(A[i,k],A[pivotrow,k]) forj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]27练习282.全主元消去法当k=1时，在第k=1列到第n=4列，第k=1行到第n=4行范围内找出绝对值最大的元素最大元素在第4行，第4列交换第k=1行和第4行的位置，再交换第k=1列和第4列的位置用数组记录列的交换z(1)=4z(4)=129在此基础上按前面的高斯顺序消去法进行第一次消元30当k=2时，在第k=2列到第n=4列，第k=2行到第n=4行范围内找出绝对值最大的元素最大元素在第3行，第3列交换第k=2行和第3行的位置，再交换第k=2列和第3列的位置用数组记录列的交换z(2)=3z(3)=231在此基础上按前面的高斯顺序消去法进行第二次消元32当k=3时，在第3列到第4列，第3行到第4行范围内找出绝对值最大的元素最大元素在第3行，第3列交换第3行和第3行的位置，再交换第3列和第3列的位置3334练习353.高斯-约当消去法与一般消去法相比，高斯—约当消去法是一种无回代过程的算法36例子第k=1步，从当前第k=1列选择列主元,(注意从第k行开始)主元在第1行，不存在交换对于第k行：用主元除第k=1行的所有元素对于第i行(i<>k)：用-aik乘以第k行加到元素所在行i37第k=2步，从当前第k=2列选择列主元,(注意从第k行开始)主元在第3行，交换第3行和第k行对于第k行：用主元除第k=2行的所有元素对于第i行(i<>k)：用-aik乘以第k行加到元素所在行i38第k=3步，从当前第k=3列选择列主元,(注意从第k行开始)主元在第3行，无需交换对于第k行：用主元除第k=3行的所有元素对于第i行(i<>k)：用-aik乘以第k行加到元素所在行i则原方程的解是x=（3，-2，1）39Guass-Jordan消去法形式上比Guass消去法简单,求解无回代过程,但从工作量角度看前者大约需要O(),而后者需要量O(),比有回代的Guass消去法多O()工作量.40写在最后成功的基础在于好的学习习惯Thefoundationofsuccessliesingoodhabits41