3线性方程组的迭代解法.ppt

《3线性方程组的迭代解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性方程组的迭代解法§1迭代法的一般形式设线性方程组Ax=b的系数矩阵A非奇异，从而有一组唯一的解。构造等价的方程组1建立迭代公式。任取一个初值x(0)，由迭代公式产生x近似解的一个向量序列{x(k)}，若则有即x*是Ax=b的解。注1迭代公式x(k+1)=Bx(k)+f的构造形式不同，就可得到不同的迭代法。2定义3.1若对任意的初值x（0），迭代公式x(k+1)=Bx(k)+f产生的向量序列{x（k）}均收敛，则称迭代公式是收敛的，否则称迭代公式是发散的。称B为迭代矩阵。注3由

2、迭代法产生的向量序列的收敛终止条件常为注2迭代法不需存储系数矩阵的零元素，特别适合求解零元素较多的稀疏矩阵。用直接解法求解时，一次消元就可能使系数阵丧失其稀疏性，不能充分利用其稀疏的特点。3例3.1用迭代法求解方程组4§2几种常用的迭代公式从三个方程中分别解出取初值x(0)=(0,0,0)T，得到迭代序列{x(k)}如下表k0123456789x102.50002.87503.13643.02403.00032.99382.99903.00023.0001x203.00002.36362.04551

3、.94781.98402.00002.00262.00061.9999x303.00001.00000.971600.920401.00101.00391.00310.999850.99988方程组的准确解为x=(3,2,1)T，从上表的计算结果可看出，向量序列{x（k）}收敛于方程组的准确解。5构造迭代格式为一般说来，对方程组6一、Jacobi方法（简单迭代法）并设从第i个方程解出xi，得等价的方程组构造迭代公式为这种迭代格式称为Jacobi迭代法，也称为简单迭代法。记7得Jacobi迭代法的矩阵

4、形式为其中8二、Gauss-Seidel迭代法在例1的Jacobi迭代法中，可以看出，在计算时，要利用，但此时的已经计算出来了。可以利用代替。一般地，计算(n≥i≥2)时，可使用代替(i>p≥1)，这样收敛会快一些，由此形成一种新的迭代法，称为Gauss-Seidel迭代法。例3.2用Seidel迭代法计算例1，并与例1的结果作比较。解迭代公式为9用它计算得到的序列{x(k)}列表如下表可见Gauss-Seidel迭代法比Jacobi迭代法收敛要快一些。Seidel迭代法的迭代公式如下10k01

5、23456x102.50002.97733.00982.99982.99993.0000x202.09092.02891.99681.99972.00012.0000x301.22731.00410.99591.00021.00011.0000Seidel迭代法的矩阵迭代形式为Seidel迭代法的矩阵形式迭代公式11注1Seidel迭代法在用计算机计算时，只需一组内存单元。注2在一定的条件下，Seidel迭代法比Jacobi迭代法收敛的速度快。算法（Gauss-Seidel迭代法）12三、逐次超松弛

6、法(SOR方法)13逐次超松弛法(SuccessiveOverRelaxationMethod)可看成是Gauss-Seidel方法的加速，Seidel迭代法是SOR方法的特例。将Seidel方法的迭代公式改写为记则为加快收敛，在增量前加一个因子，得称此公式为逐次超松弛法(SOR法)。当0<ω<1时，称为低松弛法。当ω=1时，就是Gauss-Seidel迭代法。当2>ω>1时，称为超松弛法。14故SOR方法的矩阵形式迭代公式为15SOR方法的矩阵形式为例3.3用Seidel迭代法和取ω=1.45的S

7、OR法求解方程组解取初值x(0)=(1,1,1)T，精度用Gauss-Seidel迭代法迭代有16达到同样的精度Gauss-Seidel迭代法需要迭代72步，而取ω=1.45的SOR法只需要迭代25步。由此可见选择适当的松弛因子，SOR方法收敛速度明显加快。所以SOR方法常用来求解大型的线性方程组。准确值x=(1,1,2)T取ω=1.45的SOR法迭代25步有§3迭代法的收敛条件设，引进误差向量有17定理3.1对任意初始向量x(0)和f，由产生的迭代序列{x(k)}收敛的充要条件是ρ(B)<1.证1

8、)必要性18基本定理设迭代格式收敛，则由基本定理和结论（2）可证。2)充分性定理3.1是充分必要条件，既能判别迭代法收敛性，也可以判别迭代法不收敛的情况。但由于ρ(B)的计算常常比解方程组本身更困难。基本定理和定理3.1可以看到，迭代法收敛与否与迭代矩阵B的性态有关，与初始向量x(0)和右端向量f无关。由于ρ(B)难于计算，而由结论1又有ρ(B)≤

9、

10、B

11、

12、，所以当

13、

14、B

15、

16、<1时，必有ρ(B)<1，于是得到19定理3.2若

17、

18、B

19、

20、<1，则由迭代格式x(k+1)=B