迭代法的收敛性ppt课件.ppt

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

1、第三节迭代法的收敛性迭代矩阵B满足什么条件时，由迭代法产生的向量序列{x(k)}收敛到x*.引进误差向量可得误差向量的递推公式则研究迭代法收敛性问题就是要研究迭代矩阵B满足什么条件时，有.8.3.1迭代法的收敛性定义设有矩阵序列Ak=(aij(k))∈Rn×n及A=(aij)∈Rn×n，如果n2个数列极限存在且有则{Ak}称收敛于A，记为lim(k→∞).例设有矩阵序列{Ak},其中Ak=Bk,而且设

2、λ

3、<1，考查矩阵序列极限.解显然,当

4、λ

5、<1时,则有矩阵序列极限概念可以用矩阵算子范数来描述.定理1其中

6、

7、·

8、

9、为矩阵的任意一种算子范数.定理2定理3设B=(bij)∈

10、Rn×n，则limBk=0(k→∞)(零矩阵)的充分必要条件是矩阵B的谱半径(B)<1.证明由矩阵B的若当标准形,存在非奇异矩阵P使其中若当(Jordan)块且　　　　，显然有其中显然有,Et,0=I,Et,k=0(当k≥t)，(Et,1)k=Et,k.由于Ji=λI+Et,1，因此下面考查Jik的情况.引进记号其中定理4(迭代法基本定理)设有方程组x=Bx+f.及一阶定常迭代法x(k+1)=Bx(k)+f.对任意选择初始向量x(0)，迭代法收敛的充要条件是矩阵B的谱半径(B)<1.证明充分性.设(B)<1，则(I-B)可逆，(I-B)x=f有唯一解，记为x*，则x*

11、=Bx*+f.误差向量由设(B)<1，应用定理3，有　　.于是对任意x(0)有，即.其中x(k+1)=Bx(k)+f.显然，极限x*是方程组的解，且对任意x(0)有必要性.设对任何x(0)有由定理2知再由定理3，即得(B)<1.定理4是一阶定常迭代法的基本理论.定理3和定理4的结论和起来即为(1)迭代法x(k+1)=Bx(k)+f收敛limBk=O；(2)迭代法x(k+1)=Bx(k)+f收敛(B)<1.推论设Ax=b，其中A=D-L-U为非奇异矩阵且D非奇异矩阵，则有(1)Jacobi迭代法收敛(J)<1,其中J=D-1(L+U).(2)G-S迭代法收敛

12、(G)<1,其中G=(D-L)-1U.(3)SOR迭代法收敛(Lω)<1,其中Lω=(D-ωL)-1[(1-ω)D+ωU].例：考察用Jacobi方法解系数矩阵为A的方程组的收敛性.解迭代矩阵J为得迭代矩阵J的特征方程为解得即(J)<1.所以用Jacobi方法解方程组是收敛的.例考察用迭代法解方程组的收敛性.其中解方程组的迭代矩阵B的特征方程为矩阵B的特征值为　　　　即(B)>1.这说明用迭代法解此方程组不收敛.迭代法的基本定理在理论上是重要的，根据谱半径的性质(B)≤

13、

14、B

15、

16、，下面利用矩阵B的范数建立判别迭代法收敛的充分条件.定理5(迭代法收敛的充分条件)设有

17、方程组x=Bx+f，B=(bij)∈Rn×n，及一阶定常迭代法x(k+1)=Bx(k)+f.如果有B的某种算子范数

18、

19、B

20、

21、=q<1，则(1)迭代法收敛，即对任取x(0)有证明(1)由基本定理4结论(1)是显然的.(2)显然有关系式x*-x(k+1)=B(x*-x(k))及x(k+1)–x(k)=B(x(k)–x(k-1)).于是有(a)

22、

23、x(k+1)–x(k)

24、

25、≤q

26、

27、x(k)–x(k-1)

28、

29、;(b)

30、

31、x*-x(k+1)

32、

33、≤q

34、

35、x*-x(k)

36、

37、.反复利用(b)即得(2).(3)考查

38、

39、x(k+1)–x(k)

40、

41、=

42、

43、x*–x(k)–(x*–x(k+1))

44、

45、

46、≥

47、

48、x*–x(k)

49、

50、–

51、

52、x*–x(k+1)

53、

54、≥(1–q)

55、

56、x*–x(k)

57、

58、,即得(4)利用(3)的结果反复利用(a)，则得到(4).即注意，上述定理只给出迭代法收敛的充分性，即使条件

59、

60、B

61、

62、<1对任何常用范数均不成立，迭代序列仍可能收敛.例迭代法x(k+1)=Bx(k)+f，其中显然

63、

64、B

65、

66、=1.1,

67、

68、B

69、

70、1=1.2,

71、

72、B

73、

74、2=1.043,

75、

76、B

77、

78、F=(1.54)1/2,但由于(B)=0.9<1，故由此迭代法产生的迭代序列{x(k)}是收敛的.8.3.2关于解某些特殊方程组迭代法的收敛性在科学及工程计算中，要求解方程组Ax=b，其矩阵A常常具有

79、某些特性.例如，A具有对角占优性质或A为不可约阵，或A是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性.定义(对角占优阵)设A=(aij)n×n.(1)如果A的元素满足称A为严格(按行)对角占优阵.(2)如果A的元素满足且上式至少有一个不等式成立，称A为弱(按行)对角占优阵.定义(可约与不可约矩阵)设A=(aij)n×n(n≥2)，如果存在置换阵P使其中A11为r阶方阵，A22为n-r阶方阵(1≤r≤n)，则称A为可约矩阵.否则，如果不存在这样置换阵P使上式成立，则称A为不可约矩阵.A为可约矩阵意即A可经过若