4计算函数零点和极值点的迭代法

《4计算函数零点和极值点的迭代法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章计算函数零点和极值点的迭代法本章讨论非线性方程（组）的求解问题4.1不动点迭代法及其收敛性1．不动点设非线性方程组f(x)=0(4.1-1)等价：x=F(x)(4.1-2)则有迭代格式：x(k+1)=F(x(k))，k=0，1，2，…若F连续，且迭代序列{x(k)}收敛到x*，则两边取极限得x*=F(x*)，即x*满足(4.1-2)，从而满足(4.1-1)，即x*为f零点。称x*为F(x)的不动点。注：(1)求零点求不动点(2)F(.)称为迭代函数，{x(k)}称为迭代序列(3)不同方法构造迭代函数，得不同的迭代序列

2、2．迭代法的基本问题(1)如何构造适当的迭代函数F(.)使迭代序列{x(k)}收敛(2)收敛的速度和误差(3)如何加速4.1.1解一元方程的迭代法1.根的隔离设一元方程f(x)=0，f连续，其实根可能有很多，需将各根隔离，即f在[a，b]内有且仅有一根。方法：设fÎC[a，b]，f(a)f(b)<0，且f在[a，b]上单调，则f在[a，b]内有且仅有一根。2.迭代序列的收敛性因为可以有多种迭代函数，所产生的迭代序列{x(k)}有可能：(1)收敛快(2)收敛慢(3)不收敛例1f(x)=x3–x–1=0，求f在x=1.5附近的

3、根，初值取x(0)=1.5。(p328)取——收敛取j(x)=x3–1——不收敛定理4.1-1(1)设j(x)ÎC[a，b]，且对于任意xÎ[a，b]有j(x)Î[a，b]，则j在[a，b]上必有不动点。(2)进一步，若j(x)ÎC1[a，b]，且存在L<1，使对于任意的xÎ[a，b]有

4、j'(x)

5、£L<1(4.1-4)则对于任意的x(0)Î[a，b]，x(k+1)=j(x(k))收敛于唯一不动点x*Î[a，b]。且有(4.1-5)证明：(1)若j(a)=a或j(b)=b，则结论显然成立现设a

6、y(x)=j(x)–x，则y(x)ÎC[a，b]，且y(a)=j(a)–a>0，y(b)=j(b)–b<0，故存在x*Î[a，b]，使y(x*)=0，即j(x*)–x*=0Þj(x*)=x*(2)设j(x)ÎC1[a，b]，且满足(4.1-4)，若有x1*，x2*Î[a，b]，x1*¹x2*，j(xi*)=xi*i=1，2由微分中值定理，

7、x1*–x2*

8、=

9、j(x1*)–j(x2*)

10、=

11、j'(ξ)

12、

13、x1*–x2*

14、£L

15、x1*–x2*

16、<

17、x1*–x2*

18、矛盾，所以不动点唯一。由

19、x(k)–x*

20、=

21、j(x(k-1)

22、)–j(x*)

23、£L

24、x(k-1)–x*

25、£…£Lk

26、x(0)–x*

27、及0

28、x(k)–x*

29、£L

30、x(k-1)–x*

31、得

32、x(k)–x*

33、£L

34、x(k-1)–x(k)+x(k)–x*

35、£L

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

37、+L

38、x(k)–x*

39、从而有又因

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

41、=

42、j(x(k-1))–j(x(k-2))

43、£L

44、x(k-1)–x(k-2)

45、£…£Lk-1

46、x(1)–x(0)

47、，代入上式的右边，即得注：(1)若L»1，则收敛很慢，须考虑加速问题(2)(4.1-5)中第一式为后验公

48、式—迭代停止准则第二式为先验公式—预测迭代次数(3)定理是以[a，b]中任一点作初值，迭代都收敛，称为全局收敛。（此要求较难满足，故考虑在）x*的某一邻域内—局部收敛性定理4.1-2设x*为j的不动点，j'在x*的某邻域内连续，且

49、j'(x*)

50、<1，则存在d>0，只要x(0)Î[x*–d，x*+d]，迭代法x(k+1)=j(x(k))收敛。证明：∵

51、j'(x*)

52、<1，及j'(x)在U(x*)内连续，存在d>0，使[x*–d，x*+d]ÌU(x*)，且"xÎ[x*–d，x*+d]有

53、j'(x)

54、£q<1Þ"xÎ[x*–

55、d，x*+d]，

56、j(x)–x*

57、=

58、j(x)–j(x*)

59、=

60、j'(ξ)

61、

62、x–x*

63、£q

64、x–x*

65、

66、j'(x(0))

67、明显小于1，则{x(k)}收敛于x*。例2求方程x=e–x在0.5附近的根。由于

68、j'(0.5)

69、=e–0.5»0.61明显小于1，故收敛3.收敛阶定义4.1-1设x(k)®x*，记ek=x(k)-x*若存在p³1，及c0，使则称{

70、x(k)}是p阶收敛的，或称收敛阶为p（p越高收敛越快）注：(1)p=1，01，称超线性收敛(3)p=2，称平方收敛因为

71、x(k+1)–x*

72、=

73、j(x(k))–j(x*)

74、=

75、j'(ξ)

76、

77、x(k)–x*

78、，其中ξ在x(k)和x*之间。则所以若j'(x*)¹0，则为线