数值计算方法与算法

关于数值计算方法与算法第一页，共四十七页，2022年，8月28日

求解线性方程组Ax=y，可用直接法。当A为稀疏矩阵时，直接法将破坏矩阵A的稀疏性。

我们可以对线性方程组进行等价变换，构造出等价方程组x=Mx+g,由此构造迭代关系式例如，分解A=N-P，则第二页，共四十七页，2022年，8月28日迭代法：构造一个向量序列{x(k)}

，使其收敛到某个极限向

量x*，即则x*就是线性方程组的解。常用迭代方法：

雅可比迭代，高斯-赛德尔迭代，松弛迭代等。

第三页，共四十七页，2022年，8月28日6.1

雅可比迭代6.1.1雅可比迭代格式迭代格式线性方程组Ax=y，即

第四页，共四十七页，2022年，8月28日若aii≠0,i=1,2,…,n,（6.1）可变为记则第五页，共四十七页，2022年，8月28日写成矩阵形式或简记为对任意初始向量构造迭代格式：(6.2)是称为简单迭代或雅可比迭代。第六页，共四十七页，2022年，8月28日

雅可比迭代矩阵

记所以称为雅可比迭代矩阵，是常数项向量。第七页，共四十七页，2022年，8月28日如果通过(6.2)构造的迭代序列{x(k)}收敛，即则x*为Ax=y的解，即Ax*=y。事实上，对(6.2)取极限得第八页，共四十七页，2022年，8月28日迭代格式的收敛性引理6.1(线性代数定理)

设矩阵序列则（证明见关治和陈景良编《数值计算方法》P410~412）定理6.1设迭代格式为由初始向量x(0)产生的向量序列{x(k)}收敛的充分必要条件是证明必要性（）设则由（6.3）得第九页，共四十七页，2022年，8月28日(6.3)-(6.4)得设第k次迭代的误差记为充分性（）设ρ(M)<1,证{x(k)}收敛。如果ρ(M)<1，则I-M为非奇异矩阵。事实上，因为ρ(M)<1，λi<1，因此λ=1不是M的特征值，即第十页，共四十七页，2022年，8月28日所以方程组(I-M)x=f有惟一解x*,满足(I-M)x*=f，即x*=Mx*+f。于是由引理6.1知，第十一页，共四十七页，2022年，8月28日例6.1

设系数矩阵为

判定雅可比迭代格式的收敛性。解雅可比迭代矩阵为特征方程为

第十二页，共四十七页，2022年，8月28日

实际计算中，M的特征值难于计算，因此也难于判断。由于可用作为判断收敛的条件。定理6.2若

则由迭代格式

确定的迭代序列{x(k)}收敛，且有误差估计式第十三页，共四十七页，2022年，8月28日证明又因为第十四页，共四十七页，2022年，8月28日分别把（c）和（d）代入（e）即得证（a）（b）。注：是收敛的充分条件，但不是必要条件。因为收敛，不能推出。例如第十五页，共四十七页，2022年，8月28日定义6.1

如果A的元素满足并且至少有一个不等式严格成立，则称A为行对角占优矩阵；如果A的元素满足则称A为严格行对角占优矩阵。同样可以定义列对角占优矩阵和严格列对角占优矩阵。引理6.2

（对角优势定理）(3)

若A为严格对角占优矩阵，则A非奇异，且aii≠0,i=1,2,…,n.第十六页，共四十七页，2022年，8月28日证明

由线性代数知识知，det(A)≠0Ax=0只有零解。

反证法假定det(A)=0

，则Ax=0有非零解，记为第十七页，共四十七页，2022年，8月28日

当方程组的系数矩阵为严格对角占优时，关于雅可比迭代我们有下面的定理。定理6.3当系数矩阵为严格对角占优时，雅可比迭代收敛。证明方法一：根据严格对角占优矩阵的定义。雅可比迭代矩阵：第十八页，共四十七页，2022年，8月28日方法二：反证法。

因为A为严格对角占优矩阵，由引理6.2知，aii≠0.

第十九页，共四十七页，2022年，8月28日第二十页，共四十七页，2022年，8月28日

雅可比迭代算法算法描述：1.输入系数矩阵A和常数项向量y；2.形成雅可比迭代矩阵B和向量g第二十一页，共四十七页，2022年，8月28日3.赋初始值

第二十二页，共四十七页，2022年，8月28日4.实现迭代5.输出方程组的解x2[i]，i=1,2,…,n.第二十三页，共四十七页，2022年，8月28日6.2

高斯-塞德尔(Gauss-Seidel)迭代高斯-塞德尔迭代的计算在雅可比迭代(6.4)的迭代过程中，可用新求出的x(k+1)的分量来代替x(k)的分量参与计算，直到用x(k+1)的前n-1分量代替x(k)

的前n-1个分量求出为止，即可由（6.5）得到高斯-塞德尔迭代：算法第二十四页，共四十七页，2022年，8月28日令B=L+U，其中则高斯-赛德尔迭代可写成矩阵形式或写成其中，为高斯-塞德尔迭代矩阵，第二十五页，共四十七页，2022年，8月28日

高斯-塞德尔迭代的收敛性

由定理6.1知，高斯-塞德尔迭代收敛的充分必要条件为也可以利用条件来判断高斯-塞德尔迭代收敛。定理6.4当系数矩阵为严格对角占优时，高斯-塞德尔迭代收敛。

证明类似于定理6.3的证明。反证法。第二十六页，共四十七页，2022年，8月28日第二十七页，共四十七页，2022年，8月28日第二十八页，共四十七页，2022年，8月28日定理6.5当系数矩阵A为正定矩阵，高斯-塞德尔迭代收敛。证明第二十九页，共四十七页，2022年，8月28日第三十页，共四十七页，2022年，8月28日例6.2

设系数矩阵为

判定高斯-塞德尔迭代格式的收敛性。解高斯-塞德尔迭代矩阵为其中，

第三十一页，共四十七页，2022年，8月28日第三十二页，共四十七页，2022年，8月28日

高斯-塞德尔迭代算法

根据(6.6)，可以写出高斯-塞德尔迭代的核心部分：记第三十三页，共四十七页，2022年，8月28日第三十四页，共四十七页，2022年，8月28日6.3

松弛迭代

高斯-塞德尔迭代为松弛迭代法是高斯-塞德尔迭代法的一种变化形式。令第三十五页，共四十七页，2022年，8月28日其中，参数ω>0称为松弛因子。将(6.9)变形为(6.9)或(6.10)称为松弛迭代法。迭代矩阵为当0<ω<1时，称为低松弛迭代；当1<ω<2时，称为超松弛迭代；当ω=1时，即为高斯-塞德尔迭代。第三十六页，共四十七页，2022年，8月28日

实际用计算机计算时，采用(6.9)的分量形式，即雅可比迭代、高斯-塞德尔迭代和松弛迭代均为单步线性迭代。第三十七页，共四十七页，2022年，8月28日

松弛迭代的收敛性定理6.6松弛迭代收敛的必要条件是0<ω<2。即若松弛迭代收敛，则必有0<ω<2。证明松弛迭代矩阵其中，第三十八页，共四十七页，2022年，8月28日

如果松弛迭代收敛，由定理6.1知，即Sω的所有特征值的绝对值均小于1。由特征方程的性质得由（1）和（2）两式得第三十九页，共四十七页，2022年，8月28日定理6.7如果系数矩阵A为严格对角占优，当松弛因子

时，则松弛迭代收敛。

证明类似于定理6.4。定理6.8

若A为对称正定矩阵时，则当时，松弛迭代收敛。第四十页，共四十七页，2022年，8月28日

松弛迭代算法

基本上与高斯-塞德尔迭代算法相同。第四十一页，共四十七页，2022年，8月28日6.4

逆矩阵的计算1