数值计算方法与算法

关于数值计算方法与算法

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

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

，使其收敛到某个极限向

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

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

第3页,共47页，2024年2月25日，星期天6.1

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

第4页,共47页，2024年2月25日，星期天若aii≠0,i=1,2,…,n,（6.1）可变为记则第5页,共47页，2024年2月25日，星期天写成矩阵形式或简记为对任意初始向量构造迭代格式：(6.2)是称为简单迭代或雅可比迭代。第6页,共47页，2024年2月25日，星期天

雅可比迭代矩阵

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

设矩阵序列则（证明见关治和陈景良编《数值计算方法》P410~412）定理6.1设迭代格式为由初始向量x(0)产生的向量序列{x(k)}收敛的充分必要条件是证明必要性（

）设则由（6.3）得第9页,共47页，2024年2月25日，星期天(6.3)-(6.4)得设第k次迭代的误差记为充分性（

）设ρ(M)<1,证{x(k)}收敛。如果ρ(M)<1，则I-M为非奇异矩阵。事实上，因为ρ(M)<1，λi<1，因此λ=1不是M的特征值，即第10页,共47页，2024年2月25日，星期天所以方程组(I-M)x=f有惟一解x*,满足(I-M)x*=f，即x*=Mx*+f。于是由引理6.1知，第11页,共47页，2024年2月25日，星期天例6.1

设系数矩阵为

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

第12页,共47页，2024年2月25日，星期天

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

则由迭代格式

确定的迭代序列{x(k)}收敛，且有误差估计式第13页,共47页，2024年2月25日，星期天证明又因为第14页,共47页，2024年2月25日，星期天分别把（c）和（d）代入（e）即得证（a）（b）。注：是收敛的充分条件，但不是必要条件。因为收敛，不能推出。例如第15页,共47页，2024年2月25日，星期天定义6.1

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

（对角优势定理）(3)

若A为严格对角占优矩阵，则A非奇异，且aii≠0,i=1,2,…,n.第16页,共47页，2024年2月25日，星期天证明

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

反证法假定det(A)=0

，则Ax=0有非零解，记为第17页,共47页，2024年2月25日，星期天

当方程组的系数矩阵为严格对角占优时，关于雅可比迭代我们有下面的定理。定理6.3当系数矩阵为严格对角占优时，雅可比迭代收敛。证明方法一：根据严格对角占优矩阵的定义。雅可比迭代矩阵：第18页,共47页，2024年2月25日，星期天方法二：反证法。

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

第19页,共47页，2024年2月25日，星期天第20页,共47页，2024年2月25日，星期天

雅可比迭代算法算法描述：1.输入系数矩阵A和常数项向量y；2.形成雅可比迭代矩阵B和向量g第21页,共47页，2024年2月25日，星期天3.赋初始值

第22页,共47页，2024年2月25日，星期天4.实现迭代5.输出方程组的解x2[i]，i=1,2,…,n.第23页,共47页，2024年2月25日，星期天6.2

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

的前n-1个分量求出为止，即可由（6.5）得到高斯-塞德尔迭代：算法第24页,共47页，2024年2月25日，星期天令B=L+U，其中则高斯-赛德尔迭代可写成矩阵形式或写成其中，为高斯-塞德尔迭代矩阵，第25页,共47页，2024年2月25日，星期天

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

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

证明类似于定理6.3的证明。反证法。第26页,共47页，2024年2月25日，星期天第27页,共47页，2024年2月25日，星期天第28页,共47页，2024年2月25日，星期天定理6.5当系数矩阵A为正定矩阵，高斯-塞德尔迭代收敛。证明第29页,共47页，2024年2月25日，星期天第30页,共47页，2024年2月25日，星期天例6.2

设系数矩阵为

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

第31页,共47页，2024年2月25日，星期天第32页,共47页，2024年2月25日，星期天

高斯-塞德尔迭代算法

根据(6.6)，可以写出高斯-塞德尔迭代的核心部分：记第33页,共47页，2024年2月25日，星期天第34页,共47页，2024年2月25日，星期天6.3

松弛迭代

高斯-塞德尔迭代为松弛迭代法是高斯-塞德尔迭代法的一种变化形式。令第35页,共47页，2024年2月25日，星期天其中，参数ω>0称为松弛因子。将(6.9)变形为(6.9)或(6.10)称为松弛迭代法。迭代矩阵为当0<ω<1时，称为低松弛迭代；当1<ω<2时，称为超松弛迭代；当ω=1时，即为高斯-塞德尔迭代。第36页,共47页，2024年2月25日，星期天

实际用计算机计算时，采用(6.9)的分量形式，即雅可比迭代、高斯-塞德尔迭代和松弛迭代均为单步线性迭代。第37页,共47页，2024年2月25日，星期天

松弛迭代的收敛性定理6.6松弛迭代收敛的必要条件是0<ω<2。即若松弛迭代收敛，则必有0<ω<2。证明松弛迭代矩阵其中，第38页,共47页，2024年2月25日，星期天

如果松弛迭代收敛，由定理6.1知，即Sω的所有特征值的绝对值均小于1。由特征方程的性质得由（1）和（2）两式得第39页,共47页，2024年2月25日，星期天定理6.7如果系数矩阵A为严格对角占优，当松弛因子

时，则松弛迭代收敛。

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

若A为对称正定矩阵时，则当时，松弛迭代收敛。第40页,共47页，2024年2月25日，星期天

松弛迭代算法

基本上与高斯-塞德尔迭代算法相同。第41页,共47页，2024年2月25日，星期天6.4

逆矩阵的计算1.用初等变换2.

用伴随矩阵3.用逆矩阵的定义：第42页,共47页，202