数值分析课件第四章_线性方程组的迭代解法.ppt

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

1、第四章线性方程组的迭代解法向量和矩阵的范数Jacobi迭代法Gauss－Seidel迭代法迭代法的收敛性松弛迭代法（基于G-S的加速收敛方法）误差分析第四章线性方程组的迭代解法引言特点：该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法．4.1向量和矩阵的范数向量的范数矩阵的范数矩阵基础知识回顾向量的范数证明（2）:所以证明（1）:所以所以证明（3）:矩阵的范数矩阵特征值设A是n阶方阵，如果存在常数λ和n维非零列向量x使下式成立基础知识回顾则̀λ称为矩阵A的特征值，

2、x称为A对应于特征值λ的特征向量，上式还可写为。关于这个n维其次线性方程组有非零解的充分必要条件是2.矩阵求逆（初等行变换法）2.矩阵求逆（伴随矩阵法）其中A*为A的代数余子式每一项代数余子式的符号为-1^(i+j)迭代法的基本思想：例：求解方程组其精确解是x*=(3,2,1)T。现将原方程组改写为简写为x=B0x+f，其中任取初始值，如取x(0)=(0,0,0)T，代入x=B0x+f右边，若等式成立则求得方程组的解，否则，得新值x(1)=(x1(1),x2(1),x3(1))T=(2.5,3,3)T，再将x(1)代入，反复计算，得一

3、向量序列{x(k)}和一般的计算公式（迭代公式）：简写为x(k+1)=B0x(k)+fk=0,1,2,……x(10)=(3.000032,1.999838,0.999813)T迭代到第10次时有

4、

5、ε(10)

6、

7、∞=

8、

9、x(10)–x*

10、

11、=0.000187定义：（1）对于给定方程组x=Bx+f，用迭代公式x(k+1)=Bx(k)+f(k=0,1,2,……)逐步代入求近似解的方法称迭代法；（2）若k∞时limx(k)存在（记为x*），称此迭代法收敛，显然x*就是方程组的解，否则称迭代法发散；（3）B称为迭代矩阵。问题：如何建立迭代

12、格式？收敛速度？向量序列的收敛条件？误差估计？若A非奇异，且对角元不为零，将原方程组改写为4.2Jacobi迭代法4.3Gauss－Seidel迭代法4.4迭代法的收敛性设求解线性方程组的迭代格式为将上面两式相减,得而方程组的精确解为x*，则则取范数当即且越小，的速度就越快。定理：设x*为方程组Ax=b的解，若

13、

14、B

15、

16、<1,则对迭代格式x(k+1)=Bx(k)+f，有（1）（2）证由

17、

18、B

19、

20、<1,有所以

21、

22、x(k+1)–x*

23、

24、≤

25、

26、B

27、

28、

29、

30、x(k)–x*

31、

32、x(k+1)–x*=(Bx(k)+f)–(Bx*+f)=B(x(

33、k)–x*)

34、

35、x(k)–x*

36、

37、=

38、

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

40、

41、≤

42、

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

44、

45、+

46、

47、x(k+1)–x*

48、

49、≤

50、

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

52、

53、+

54、

55、B

56、

57、

58、

59、x*–x(k)

60、

61、=

62、

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

64、

65、+

66、

67、B

68、

69、

70、

71、x(k)–x*

72、

73、所以x(k+1)–x(k)=(Bx(k)–f)–(Bx(k-1)–f)=B(x(k)–x(k-1))

74、

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

76、

77、≤

78、

79、B

80、

81、

82、

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

84、

85、故可得误差估计式:注：（1）式说明，只要

86、

87、B

88、

89、不是很接近1，当x(k+1)和x

90、(k)很接近时，x(k)也越接近x*，故可用

91、

92、x(k+1)-x(k)

93、

94、中止迭代。（2）式说明，

95、

96、B

97、

98、越小，x(k)收敛越快，可作误差估计式。定理：迭代格式收敛的充要条件为迭代矩阵的谱半径(B)<1。证:对任何n阶矩阵B，都存在非奇异矩阵P，使B=P–1JP其中，J为B的Jordan标准型。其中,Ji为Jordan块其中λi是矩阵B的特征值，由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f收敛<=>谱半径(B)<1注：(B)≤

99、

100、B

101、

102、，且当B为对称阵时

103、，即AT=A，(B)=

104、

105、B

106、

107、2。例3.判别下列方程组用Jacobi法和Gauss-Seidel法求解是否收敛:解:(1)求Jacobi法的迭代矩阵所以即Jacobi迭代法收敛。(2)求Gauss-Seidel法的迭代矩阵：显然BJ的几种常用算子范数

108、

109、BJ

110、

111、>1，故用其特征值判断。所以Gauss-Seidel迭代法发散。注：本例说明Gauss-Seidel迭代法发散时而Jacobi迭代法却收敛，因此，不能说Gauss-Seidel迭代法比Jacobi迭代法更好。可得故定义设A=(aij)n×nRn×n，若(i=1,2,…,n

112、)，则称A为对角占优矩阵，若不等式严格成立，则称A为严格对角占优矩阵。迭代法收敛的其他结论：定理若Ax=b中A为严格对角占优矩阵，则Jacobi迭代和Gauss－Seidel迭代均收敛。证明：因为系数矩阵A严格对角占优，