数值分析解析9(迭代法收敛性证明)资料.ppt

《数值分析解析9(迭代法收敛性证明)资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、迭代法收敛性条件迭代误差估计定理《数值分析》9*总结:矩阵范数算子范数算子范数矩阵1范数,矩阵无穷范数,矩阵2范数例4设

2、

3、.

4、

5、为Rn×n上任意一种矩阵范数,则对任意的A∈Rn×n,有证明:例5设

6、

7、.

8、

9、为Rn×n上任意一种矩阵范数,则对AX=b(M–N)X=bMX=NX+b记(k)=X(k)–X*(k=0,1,2,···)则有(k+1)=B(k)(k=0,1,2,···)迭代格式:X(k+1)=BX(k)+f(B=M-1N,f=M-1b)X(k+1)–X*=B(X(k)–X*)设方程组的精确解为X*,则有X*=B

10、X*+f*

11、

12、(k+1)

13、

14、=

15、

16、B(k)

17、

18、≤

19、

20、B

21、

22、.

23、

24、(k)

25、

26、(k=0,1,2,···)*迭代法构造收敛条件中止准则引理1*参考:P.83引理2*引理3证:必要性,设迭代法产生的序列{X(k)}收敛,记X*是该序列的极限点,则X*=BX*+f。定理4.1对任意的f和任意的初始向量X(0)迭代法X(k+1)=BX(k)+f收敛的充分必要条件是由X(0)的任意性知*充分性*谱半径小于1是迭代收敛的充要条件,但它不易计算,所以在实际使用中通常并不好用。推论4.1若

27、

28、B

29、

30、<1,则对任意的f和任意的初始向量X(0)迭代

31、法X(k+1)=BX(k)+f收敛。*定理4.2设X*为方程组AX=b的解若

32、

33、B

34、

35、<1,则对迭代格式X(k+1)=BX(k)+f有(1)(2)证

36、

37、X(k+1)–X*

38、

39、=

40、

41、B(X(k)–X*)

42、

43、≤

44、

45、B

46、

47、

48、

49、X(k)–X*

50、

51、X(k+1)–X*=B(X(k)–X*)*

52、

53、X(k)–X*

54、

55、=

56、

57、(X(k)–X(k+1))+(X(k+1)–X*)

58、

59、≤

60、

61、X(k)–X(k+1)

62、

63、+

64、

65、X(k+1)–X*

66、

67、≤

68、

69、X(k)–X(k+1)

70、

71、+

72、

73、B

74、

75、

76、

77、X(k)–X*

78、

79、**迭代法构造收敛条件(局部vs全局)中止准则

80、统一的不动点框架定义4.1A=(aij)n×n,如果则称A为严格对角占优阵。*性质2A是严格对角占优矩阵,则D-L和D-U是严格对角占优矩阵。性质1A是严格对角占优矩阵,则。记A=D-L-U性质3A是严格对角占优矩阵,则当时则有和是严格对角占优矩阵。严格对角占优矩阵定理4.3若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Gauss-Seidel迭代收敛。证:由于矩阵A严格对角占优*所以故Jacobi迭代矩阵BJ=D-1(D–A)第i行绝对值求和故Jacobi迭代X(k+1)=BJX(k)+f收敛。*推论A是严格对角

81、占优矩阵,则A非奇异。Gauss-Seidel迭代矩阵为BGS=(D-L)-1U。由于A对角占优所以矩阵也是对角占优的,则矩阵一定非奇异,矛盾。注释:考虑反证法新证:定理4.4方程组Ax=b中,若A是实对称正定矩阵,则Gauss-Seidel迭法收敛。证明:由A=D–L–LTBGS=(D–L)-1LTA正定,故p=xTDx>0,记xTLTx=a,则有xTAx=xT(D–L–LT)x=p–a–a=p–2a>0设为BGS的任一特征值,x为其特征向量,则*所以迭代矩阵BGS的谱半径(BGS)<1,从而当A是实对称正定矩阵时,Gaus

82、s-Seidel迭代法收敛。*定理方程组Ax=b中,若A是实对称正定矩阵,则Jacobi迭法收敛？(反例)定理4.5设BJ元素均非负,则下列关系有且只有一个成立:参考文献:P.Stein,R.L.Rosenberg,Onthesolutionoflinearsimultaneousequationsbyiteration,J.LondonMath.Soc.**迭代法构造收敛条件(局部vs全局)中止准则统一的不动点框架直接法vs迭代法基于高斯消元法的直接方法提供了有限步内就可以得到解的方法。*寻求迭代方法的理由是什么呢？十阶百阶万阶百

83、万阶亿阶小不大较大大超大迭代法优势1:直接法运行一个完整LU分解才能得到解,迭代法从初始解开始每步对其加工改善使其更加精确。问题是在用户容忍的范围内需要多少步才能得到收敛性？*注释:运行一个完整LU分解花费O(n3)阶运算,一般地,迭代法每次迭代花费O(n2)阶运算,即每次迭代仅需要完整LU分解花费的一部分。迭代法优势2:求解稀疏方程组是使用迭代法的主要理由。*注释:系数矩阵稀疏度为n,则求解稀疏方程组迭代法每步迭代花费O(n)阶运算。求解特殊结构方程组(如Toeplitz)迭代法每步迭代花费O(nlogn)阶运算。Poisson方

84、程:令h=1/(n+1),xi=ih(i=0,1,···,n+1)记ui=u(xi),(i=0,1,···,n+1)迭代计算格式:差分格式:n=10000;e=ones(n,1);A=spdiags([e-2*ee],-1:1,n,n