计算机数学基础下第5编 数值分析

计算机数学基础(下)第5编数值分析,第10章线性方程组的数值解法,本章主要内容：,高斯消去法列主元消去法雅可比迭代法高斯赛德尔迭代法迭代法的收敛性重点：高斯消去法、雅可比迭代法难点：迭代法收敛的判定,n元线性方程组的有关概念由n个未知量，n道所有的未知量都是一次的方程组成的方程组称为n元线性方程组。习惯上我们用xj表示这些未知量，用aij表示它们的系数，用bj表示方程等号右边的常数。因此，n元线性方程组的一般形式为：,n元线性方程组可以写成矩阵的形式AXB其中：A称为系数矩阵，是nn矩阵,X称为未知量矩阵，b称为常数矩阵，它们都是n1的列矩阵或称为n维列向量。当|A|0时，方程组的解唯一存在。,线性方程组的增广矩阵由系数矩阵和常数矩阵并列构成的矩阵称为线性方程组的增广矩阵，记作A|bA|b,10.1高斯消去法,10.1.1高斯顺序消去法的基本思想高斯消去法的基本思想是对线性方程组的增广矩阵进行行初等变换，使增广矩阵中的系数矩阵变为上三角矩阵，从而解出最后一个未知数xn的值，然后在依次回代，求出其余的未知数的值。如果消元是按方程组的自然顺序进行的就称为高斯顺序消去法。,例1.解线性方程组解：将方程组写成矩阵的形式AXb其中：A|b,它相当于方程组：解得x35，回代到第2式可解得x24，再已将求出的x3，x2的值回代到第1式可解得x1-1方程组的解为(-1,4,5)T,10.1.2高斯顺序消去法公式记初始方程组AXb为A(0)Xb(0)第一次消元后的方程组记为A(1)Xb(1)消元公式是：消元后的增广矩阵是：,第二次消元的公式是怎样的呢？,第二次消元后的方程组记为A(2)Xb(2)第二次消元公式是：由此可得，,第k次消元后的方程组记为A(k)Xb(k),公式是：消元进行到第n1次时结束，,可求出xn，然后回代。得到公式：,小结：高斯顺序消去法解线性方程组的步骤：消元对k1到n1，若进行消元第k次消元公式前面已经给出。若回代，方程组的解为,定理1线性方程组AXb能用高斯消去法求解的充分必要条件是A的各阶顺序主子式不为0。例2.用高斯消去法求解线性方程组解：写出增广矩阵A|bA(0)|b(0),第1次消元：各元素分别加到第2、3行上，得到A()|b()第2次消元：A(2)|b(2),此时，系数矩阵部分已化为上三角矩阵，因为于是可以回代，得到：所以，原方程组的解为,2001年7月试卷计算题11用高斯消去法求解线性方程组解：A|b,10.1.3列主元消去法在高斯消去法中我们把分别称为第1步、第2步、第k步的主元，如果这些主元中的某一个主元0，当它做除数时就会使舍入误差增大，导致解的严重失真。,为了提高算法的稳定性，应选取绝对值尽可能大的元素作为主元，这种消去法称为列主元消去法。例3.用列主元消去法解线性方程组解：A|b,在第1列中选取绝对值最大的元素-18作为主元，把第1行与第2行互换后再作第1次消元A(0)|b(0)消元后再选取第2列主元A(1)|b(1),再选取第2列主元，把第2行与第3行互换A(1)|b(1)再消元得A(2)|b(2)回代得,2002年1月试卷填空题8用列主元消去法解线性方程组在作第1次消元之前，应选择主元。,4,2002年1月试卷填空题8用列主元消去法解线性方程组作第1次消元之后的第个方程是。解：A|b,如果矩阵满足即主对角线上每一元素的绝对值均大于同行(列)其它元素绝对值之和，这样的矩阵称为严格对角占优矩阵。如果矩阵满足，各阶顺序主子式的值均为正数，这样的矩阵称为正定矩阵。正定矩阵和严格对角占优矩阵在消元过程中主元必是，因此不必选主元，可以用顺序消元法解，而且一定满足前面所说的定理1的条件，用顺序消元法解一定可以进行到底。作业：P.23带的练习题,10.3解线性方程组的迭代法,10.3.1引言设线性方程组AXb其中：若将线性方程组变形为等价的方程组XBXf建立迭代公式X(k+1)BX(k)f，就可以从给定的初始向量X(0)出发，按上面的迭代公式得到解向量X(k),这种解法称为线性方程组的迭代解法。,能否用迭代法求出线性方程组的解，关键在于向量序列X(k)是否收敛。设：如果，当时X(k)的每一个元素都收敛。即，则称向量序列X(k)收敛，向量序列X(k)的极限向量为,若向量序列X(k)收敛，设其极限向量为对迭代公式两边取极限：得，即因此，为方程组的解，此时称迭代法收敛。用迭代法解线性方程组需要解决两个问题：如何建立迭代公式，迭代收敛的条件是什么？,10.3.2雅可比迭代法将线性方程组AXb改写成：得相应的迭代公式(雅可比迭代公式)：,例2求解线性方程组解：把方程组变形为：其雅可比迭代公式为：,取迭代初始值利用雅可比迭代公式计算，迭代过程如表，可见，随着迭代次数k的增加，迭代值越来越接近原方程的精确解：一般地说，我们可以在预先给定的精度下停止迭代，把最后一次的迭代值作为原方程组的近似解。例如在此例中，如果精确到小数点后面5位小数，第13次迭代值与第12次迭代值相同，我们就可以用第13次迭代值作为方程组的解。,2002年1月试卷计算题11用雅可比迭代法解线性方程组从初始向量(0,0,0)T开始，计算出第3次迭代结果，并要求写出迭代公式，计算过程中保留4位小数。解：迭代公式为：计算过程如表，解为：,雅可比迭代的矩阵表示：线性方程组可以用矩阵表示为：其中,2001年7月试卷选择题2用雅可比迭代法求解线性方程组构造迭代公式，则雅可比迭代矩阵B0,雅可比迭代公式的矩阵形式为：若记,矩阵的分解为：其中：了解矩阵的分解可以帮助我们记忆下面所要学的高斯赛德尔迭代矩阵。,10.3.3高斯赛德尔迭代法高斯赛德尔迭代公式为：高斯赛德尔迭代公式的矩阵形式为：其中：,例3用高斯赛德尔迭代法解线性方程组解：高斯赛德尔迭代公式为：取迭代初始值利用高斯赛德尔迭代公式计算，迭代过程如表，一般说来，高斯赛德尔迭代法比雅可比迭代法收敛快。,2002年1月试卷填空题7用高斯赛德尔迭代法解线性方程组的迭代格式中，。,10.3.5迭代法的收敛性定理4(迭代基本定理)若线性方程组XBXf对于任意初始向量X(0)及任意f，对应此线性方程组的迭代公式X(k+1)BX(k)f(k=0,1,2,)，收敛的充分必要条件是其中是迭代矩阵B的特征根，当为复数时表示的模。,例5设线性方程组AXb，矩阵证明雅可比迭代法发散，而高斯赛德尔迭代法收敛。证明：矩阵A的雅可比迭代矩阵为：,特征方程为：矩阵A的高斯赛德尔迭代矩阵为：,而,的特征方程为解得特征根为：由定理4可知，高斯赛德尔迭代收敛。,定理5(迭代法收敛的充分条件)设线性方程组XBXf，若矩阵B中的元素则对于任意初始向量X(0)及任意f，解此线性方程组的迭代公式X(k+1)BX(k)f(k=0,1,2,)，收敛。该定理是充分条件，因此满足此条件的迭代一定收敛，不满足此条件不一定不收敛。所以，如题目要求证明某迭代法必收敛时可以用此方法证明，但如果题目要求判别某迭代法是否收敛或证明某迭代法发散，一般应采用定理4证明。,例6设线性方程组AXb，矩阵证明雅可比迭代法和高斯赛德尔迭代法都收敛。证明：矩阵A的雅可比迭代矩阵为：由定理5，雅可比迭代收敛。,矩阵A的高斯赛德尔迭代矩阵为：由定理5，高斯赛德尔迭代收敛。,作业P.6四、证明题设解线性方程组试证明用雅可比迭代法求解收敛，而用高斯赛德尔迭代法求解发散。证明：,B0的特征方程为：矩阵A的高斯赛德尔迭代矩阵为：,G的特征方程为：,2002年1月试卷选择题2设线性方程组XBXf，n阶矩阵B的特征根为，对任意初始向量X(0)及任意f，对应此线性方程组的迭代格式X(k+1)B