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

数值计算方法第四章计算函数零点和极值点的迭代法本章讨论非线性方程（组）的求解问题2/801．不动点设非线性方程组f(x)=0(4.1-1)0),...,,(0),...,,(0),...,,(21212211nnnnxxxfxxxfxxxf4.1不动点迭代法及其收敛性3/801．不动点设非线性方程组f(x)=0(4.1-1)等价：x=(x)(4.1-2)则有迭代格式：x(k+1)=(x(k))，k=0，1，2，…若连续，且迭代序列{x(k)}收敛到x*，则两边取极限得x*=(x*)，即x*满足(4.1-2)，从而满足(4.1-1)，即x*为f的零点。称x*为(x)的不动点。0),...,,(0),...,,(0),...,,(21212211nnnnxxxfxxxfxxxf4/80注：(1)求零点求不动点(2)(.)称为迭代函数，{x(k)}称为迭代序列(3)不同方法构造迭代函数，得不同的迭代序列5/802．迭代法的基本问题(1)如何构造适当的迭代函数(.)使迭代序列{x(k)}收敛(2)收敛的速度和误差(3)如何加速6/804.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]内有且仅有一根。7/802.迭代序列的收敛性因为可以有多种迭代函数，所产生的迭代序列{x(k)}有可能：(1)收敛快(2)收敛慢(3)不收敛8/80例1f(x)=x3–x–1=0，求f在x=1.5附近的根，初值取x(0)=1.5。(p328)取——收敛k=1,x0=1.5x1=(1+x0)^(1/3)whileabs(x1-x0)0.00001k=k+1,x0=x1;x1=(1+x0)^(1/3)end取(x)=x3–1——不收敛k=1,x0=1.5x1=x0^3-1whileabs(x1-x0)0.00001&&k5k=k+1,x0=x1;x1=x0^3-1end31)(xx9/80定理4.1-1(1)设(x)C[a，b]，且对于任意x[a，b]有(x)[a，b]，则在[a，b]上必有不动点。(2)进一步，若(x)C1[a，b]，且存在L1，使对于任意的x[a，b]有|'(x)|L1(4.1-4)则对于任意的x(0)[a，b]，x(k+1)=(x(k))收敛于唯一不动点x*[a，b]。且有(4.1-5))0()1(*)()1()(*)(11xxLLxxxxLLxxkkkkk10/80证明：(1)若(a)=a或(b)=b，则结论显然成立现设a(a)，(b)b，令(x)=(x)–x，则(x)C[a，b]，且(a)=(a)–a0，(b)=(b)–b0，故存在x*[a，b]，使(x*)=0，即(x*)–x*=0(x*)=x*(2)设(x)C1[a，b]，且满足(4.1-4)，若有x1*，x2*[a，b]，x1*x2*，(xi*)=xi*i=1，2由微分中值定理，|x1*–x2*|=|(x1*)–(x2*)|=|'(ξ)||x1*–x2*|L|x1*–x2*||x1*–x2*|矛盾，所以不动点唯一。11/80由|x(k)–x*|=|(x(k-1))–(x*)|L|x(k-1)–x*|…Lk|x(0)–x*|及0L1知即x(k)收敛于x*。并且由|x(k)–x*|L|x(k-1)–x*|得|x(k)–x*|L|x(k-1)–x(k)+x(k)–x*|L|x(k-1)–x(k)|+L|x(k)–x*|从而有0||lim*)(xxkk)1()(*)(1kkkxxLLxx12/80又因|x(k)–x(k-1)|=|(x(k-1))–(x(k-2))|L|x(k-1)–x(k-2)|…Lk-1|x(1)–x(0)|，代入上式的右边，即得注：(1)若L1，则收敛很慢，须考虑加速问题(2)(4.1-5)中第一式为后验公式—迭代停止准则第二式为先验公式—预测迭代次数(3)定理是以[a，b]中任一点作初值，迭代都收敛，称为全局收敛。（此要求较难满足，故考虑在）x*的某一邻域内—局部收敛性)0()1(*)(1xxLLxxkk13/80定理4.1-2设x*为的不动点，'在x*的某邻域内连续，且|'(x*)|1，则存在0，只要x(0)[x*–，x*+]，就有迭代法x(k+1)=(x(k))收敛。证明：∵|'(x*)|1，及'(x)在U(x*)内连续，存在0，使[x*–，x*+]U(x*)，且x[x*–，x*+]有|'(x)|q1x[x*–，x*+]，|(x)–x*|=|(x)–(x*)|=|'(ξ)||x–x*|q|x–x*|，即(x)[x*–，x*+]，由定理4.1-1知，任意x(0)[x*–，x*+]，迭代法x(k+1)=(x(k))收敛。注：只要x(0)充分接近x*，且|'(x(0))|明显小于1，则{x(k)}收敛于x*。14/80例2求方程x=e–x在0.5附近的根。由于|'(0.5)|=e–0.50.61明显小于1，故收敛解：Matlab代码如下k=1,x0=0.5x1=exp(-x0)whileabs(x1-x0)0.00001&&k25k=k+1,x0=x1;x1=exp(-x0)end15/803.收敛阶定义4.1-1设x(k)x*，记ek=x(k)-x*若存在p1，及c≠0，使则称{x(k)}是p阶收敛的，或称收敛阶为p（p越高收敛越快）注：(1)p=1，0c1，称为线性收敛；(2)p1，称超线性收敛(3)p=2，称平方收敛ceepkkk||||lim116/80因为|x(k+1)–x*|=|(x(k))–(x*)|=|'(ξ)||x(k)–x*|，其中ξ在x(k)和x*之间。则所以若'(x*)0，则为线性收敛想得到更高阶的收敛性，须'(x*)=0，通常可考虑泰勒展式。|)('|||||lim*1xeekkk17/80定理4.1-3设x*为的不动点，正整数p2，若(p)在x*的某邻域内连续，且满足(4.1.6)则{x(k)}p阶局部收敛。证明：∵'(x*)=0(1)，∴x(k)局部收敛。设(x)在x*处展开为0)(1,...,2,1,0)(*)(*)(xpkxpkpkppkpkkkxxpxxpxxxxxxxxx)(!)()()!1()(...)(!2)())((')()(*)()(1*)(*)1(2*)(**)(**)(18/80由(4.1-6)知，所以即{x(k)}p阶局部收敛。pkpkkxxpxxxx)(!)()()(*)()(*)(*)1(0!)(!)()(*)()(*)(*)1(pxpxxxxpppkk19/80例3设fC2[a，b]，(x)=x–r1(x)f(x)–r2(x)f2(x)，x*为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法x(k+1)=(x(k))至少是三阶局部收敛的。解：由定理4.1-3知，应有'(x*)=(x*)=0，因为'(x)=1-r1'(x)f(x)-r1(x)f'(x)-r2'(x)f2(x)-2r2(x)f(x)f'(x)而f(x*)=0，f'(x*)≠0（单重零点），令'(x*)=0，有1–r1(x*)f’(x*)=0，即取，则有'(x*)=0，此时有'(x)=-r1'(x)f(x)-r2'(x)f2(x)-2r2(x)f(x)f'(x)(x)=-r1(x)f(x)-r1'(x)f'(x)-r2(x)f2(x)-4r2'(x)f(x)f'(x)-2r2(x)[f'(x)]2-2r2'(x)f(x)f(x))('1)(1xfxr20/80(x)=-r1(x)f(x)-r1'(x)f'(x)-r2(x)f2(x)-4r2'(x)f(x)f'(x)-2r2(x)[f'(x)]2-2r2'(x)f(x)f(x)其中令(x*)=0，有即取则有(x*)=0，从而只要同时取迭代法至少具有三阶局部收敛性。21)]('[)()('xfxfxr0)](')[(2)(')(2**2**xfxrxfxf32)]('[2)()(xfxfxr32)]('[2)()(xfxfxr)('1)(1xfxr21/804.加速幂法中曾有Aitken加速，这里使用相同的思想若x(k)x*，由中值定理，x(k+1)–x*=(x(k))–(x*)='(ξ1)(x(k)–x*)ξ1在x(k)和x*之间x(k+2)–x*=(x(k+1))–(x*)='(ξ2)(x(k+1)–x*)ξ2在x(k+1)和x*之间因为x(k)x*，所以当k充分大时，'(ξ1)'(ξ2))('1*)(*)1(xxxxkk)('2*)1(*)2(xxxxkk22/80即(4.1-7)记则{}比{x(k)}收敛得快。*)(*)1(*)1(*)2(xxxxxxxxkkkk)()1()2(2)1()2()2(*2)(kkkkkkxxxxxxx)()1()2(2)1()2()2()2(2)(ˆkkkkkkkxxxxxxx)(ˆkx23/80定理4.1-4设{x(k)}线性收敛于x*，且k0，ek=x(k)–x*≠00||1(线性收敛)则证明：因为所以ek+1=(+εk)ek，其中εk0x(k+1)–x(k)=x(k+1)–x*–(x(k)–x*)=ek+1–ek=[(–1)+εk]ekkkkee1lim0ˆlim*)(*)(xxxxkkkkkkee1lim24/80又x(k+2)–2x(k+1)+x(k)=(x(k+2)–x(k+1))–(x(k+1)–x(k))=[(–1)+εk+1]ek+1–[(–1)+εk]ek=[(–1)+εk+1](+εk)ek–[(–1)+εk]ek=[(–1)2+k]ek.其中k=εk+1+(–2)εk+εk+1εk0所以)()1()2(2)()1()()()1()2(2)1()()2()()1()2(2)1()2()2()2(2)(2)(2)(ˆkkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxx])1[(])1[(])1[(])1[(2)(ˆ22222)()1()2(2)()1(*)(*)2(kkkkkkkkkkkkkkkkeeeeexxxxxxxx25/80注：(1)(4.1-7)称为Aitken加速(2)k=1，2，…称为史蒂文生迭代法。0)])1[(])1[(1(limˆlim21*)2(*)2(kkkkkkkkeexxxx)()()(2)()()()1()()()()(2)()()(kkkkkkkkkkkxyzyzzxyzxy)()1()2(2)1()2()2()2(2)(ˆkkkkkkkxxxxxxx26/80例4用迭代法和Steffensen迭代法求函数f(x)=x–lnx–2在区间(2，+)内的零点，取x(0)=3.解：将f(x)=0化为等价的方程x=lnx+2=(x)，由于'(x)=1/x在[2