数值计算方法(第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(A1.n，1.n,b1.n)/输输入：系数矩入：系数矩阵阵A及常数及常数项项 b /输输出：方程出：方程组组的增广矩的增广矩阵阵等价的上三角矩等价的上三角矩阵阵 for i=1 to n do Ain+1=bi for i=1 to n-1 do if Aii=0 then 停机停机 else for j=i+1 to n do for k=i to n+1 do Ajk=Ajk Aik*Aji/Aii11高斯消去法的计算量高斯消去法的计算量消元过程消元过程 for i=1 to n do Ain+1=bi for i=1 to n-1 do if Aii=0 then 停机停机 else for j=i+1 to n do for k=i to n+1 do Ajk=Ajk Aik*Aji/Aii若把内层循环看成若把内层循环看成若把内层循环看成若把内层循环看成1 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高斯顺序消去法条件高斯顺序消去法条件 从最内层循环看出顺序消去法的条件是从最内层循环看出顺序消去法的条件是 Ajk=Ajk Aik*Aji/Aii233.1.2 高斯主元素消去法高斯主元素消去法Gauss列主元消元法：从列的角度控制循环列主元消元法：从列的角度控制循环当当k=1时，考察第一列找出绝对值最大的元素时，考察第一列找出绝对值最大的元素最大元素在第二行最大元素在第二行交换第二行和第交换第二行和第k=1行的位置行的位置在此基础上按前面在此基础上按前面的高斯顺序消去法的高斯顺序消去法消掉第一个变量消掉第一个变量24当当k=2时，考察第二列找出绝对值最大的元素时，考察第二列找出绝对值最大的元素(除第除第1行行)最大元素在第三行最大元素在第三行交换第三行和第交换第三行和第k=2行的位置行的位置在此基础上按前面在此基础上按前面的高斯顺序消去法的高斯顺序消去法消掉第二个变量消掉第二个变量2526betterGaussElimination(A1.n，1.n,b1.n)/输输入：系数矩入：系数矩阵阵A及常数及常数项项 b /输输出：方程出：方程组组的增广矩的增广矩阵阵等价的上三角矩等价的上三角矩阵阵 for i=1 to n do Ain+1=bi for i=1 to n-1 do pivotrow=i for j=i+1 to n do if|Aj,i|Apivotrow,i|pivotrow=j if Apivotrow,i=0 then 停机停机 else for k=i to n+1 do swap(Ai,k,Apivotrow,k)for j=i+1 to n do for k=i to n+1 do Ajk=Ajk Aik*Aji/Aii27练习练习282.全主元消去法全主元消去法当当k=1时，时，在第在第k=1列到第列到第n=4列，第列，第k=1行到第行到第n=4行范围内行范围内找出绝对值最大的元素找出绝对值最大的元素最大元素在第最大元素在第4行，第行，第4列列交换第交换第k=1行和第行和第4行的位置，再交换第行的位置，再交换第k=1列和第列和第4列的位置列的位置用数组记录列的交换用数组记录列的交换z(1)=4 z(4)=129在此基础上按前面在此基础上按前面的高斯顺序消去法的高斯顺序消去法进行第一次消元进行第一次消元30当当k=2时，时，在第在第k=2列到第列到第n=4列，第列，第k=2行到第行到第n=4行范围内行范围内找出绝对值最大的元素找出绝对值最大的元素最大元素在第最大元素在第3行，第行，第3列列交换第交换第k=2行和第行和第3行的位置，再交换第行的位置，再交换第k=2列和第列和第3列的位置列的位置用数组记录列的交换用数组记录列的交换z(2)=3 z(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行行(ik)：用：用-aik乘以第乘以第k行加到元素所在行行加到元素所在行i37第第k=2步，从当前第步，从当前第k=2列选择列主元列选择列主元,(注注意从第意从第k行开始行开始)主元在第主元在第3行，行，交换第交换第3行和第行和第k行行对于第对于第k行：行：用用主元除第主元除第k=2行行的所有元素的所有元素对于第对于第i行行(ik)：用用-aik乘乘以第以第k行加到元素所在行行加到元素所在行i38第第k=3步，从当前第步，从当前第k=3列选择列列选择列主元主元,(注意从第注意从第k行开始行开始)主元在第主元在第3行，行，无需交换无需交换对于第对于第k行：行：用主元除第用主元除第k=3行的行的所有元素所有元素对于第对于第i行行(ik)：用用-aik乘乘以第以第k行加到元素所在行行加到元素所在行i则原方程的解是则原方程的解是x=（3，-2，1）39Guass-Jordan消去法形式上比消去法形式上比Guass消消去法简单去法简单,求解无回代过程求解无回代过程,但从工作量角但从工作量角度看前者大约需要度看前者大约需要O(),而后者需要而后者需要量量 O(),比有回代的比有回代的Guass消去法多消去法多O()工作量工作量.40写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits41 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日