欢迎来到天天文库
浏览记录
ID:14047238
大小:371.00 KB
页数:15页
时间:2018-07-25
《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,则结论显然成立现设a6、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、£L15、x1*–x2*16、<17、x1*–x2*18、矛盾,所以不动点唯一。由19、x(k)–x*20、=21、j(x(k-1)22、)–j(x*)23、£L24、x(k-1)–x*25、£…£Lk26、x(0)–x*27、及028、x(k)–x*29、£L30、x(k-1)–x*31、得32、x(k)–x*33、£L34、x(k-1)–x(k)+x(k)–x*35、£L36、x(k-1)–x(k)37、+L38、x(k)–x*39、从而有又因40、x(k)–x(k-1)41、=42、j(x(k-1))–j(x(k-2))43、£L44、x(k-1)–x(k-2)45、£…£Lk-146、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、£q64、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,则为线
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、及028、x(k)–x*29、£L30、x(k-1)–x*31、得32、x(k)–x*33、£L34、x(k-1)–x(k)+x(k)–x*35、£L36、x(k-1)–x(k)37、+L38、x(k)–x*39、从而有又因40、x(k)–x(k-1)41、=42、j(x(k-1))–j(x(k-2))43、£L44、x(k-1)–x(k-2)45、£…£Lk-146、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、£q64、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,则为线
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,则为线
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,则为线
此文档下载收益归作者所有