《计算函数零点和极值点的迭代法.ppt》由会员分享,可在线阅读,更多相关《计算函数零点和极值点的迭代法.ppt(157页珍藏版)》请在三一办公上搜索。
1、数值计算方法,第四章 计算函数零点和极值点的迭代法,本章讨论非线性方程(组)的求解问题,1不动点设非线性方程组 f(x)=0(4.1-1),4.1 不动点迭代法及其收敛性,非线性方程组 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)的不动点。,4.1 不动点迭代法及其收敛性,x(k+1)=(x(k),k=0,1,2,注:(1)求零点求不动点(2)(.)称为迭代函数,x(k)称为迭
2、代序列(3)不同方法构造迭代函数,得不同的迭代序列,4.1 不动点迭代法及其收敛性,2迭代法的基本问题(1)如何构造适当的迭代函数(.)使迭代序列x(k)收敛(2)收敛的速度和误差(3)如何加速,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法1.根的隔离设一元方程f(x)=0,f 连续,其实根可能有很多,需将各根隔离,即f在某区间a,b内有且仅有一根。方法:设f Ca,b,f(a)f(b)0,且f在a,b上单调,则f在a,b内有且仅有一根。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法2.迭代序列的收敛性因为可以有多种迭代函数,所产生的迭代序列x(k)有可能:
3、(1)收敛快(2)收敛慢(3)不收敛,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法例1 f(x)=x3 x 1=0,求f在x=1.5附近的根,初值取x(0)=1.5。(p328)取 收敛k=1,x0=1.5x1=(1+x0)(1/3)while abs(x1-x0)0.00001 k=k+1,x0=x1;x1=(1+x0)(1/3)end,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法例1 f(x)=x3 x 1=0,求f在x=1.5附近的根,初值取x(0)=1.5。(p328)取(x)=x3 1 不收敛k=1,x0=1.5x1=x03-1while abs(
4、x1-x0)0.00001 x1=x03-1end,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-1(1)设(x)Ca,b,且对于任意x a,b有(x)a,b,则在a,b上必有不动点。(2)进一步,若(x)C1a,b,且存在L1,使对于任意的x a,b有|(x)|L 1(4.1-4)则对于任意的x(0)a,b,x(k+1)=(x(k)收敛于唯一不动点x*a,b。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-1(2)进一步,若(x)C1a,b,且存在L1,使对于任意的x a,b有|(x)|L 1(4.1-4)则对于任意的x(0)a,b,x
5、(k+1)=(x(k)收敛于唯一不动点x*a,b。且有(4.1-5),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-1(1)设(x)Ca,b,且对于任意x a,b有(x)a,b,则在a,b上必有不动点。证明:(1)若(a)=a或(b)=b,则结论显然成立现设a 0,(b)=(b)b 0,故存在x*a,b,使(x*)=0,即(x*)x*=0(x*)=x*,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法证明:(2)设(x)C1a,b,且满足(4.1-4),若有x1*,x2*a,b,x1*x2*,(xi*)=xi*i=1,2由微分中值定理|x1*x2*|=
6、|(x1*)(x2*)|=|()|x1*x2*|L|x1*x2*|x1*x2*|矛盾,所以不动点唯一。,4.1 不动点迭代法及其收敛性,|(x)|L 1,4.1.1 解一元方程的迭代法证明:(2)设(x)C1a,b,且满足(4.1-4),由|x(k)x*|=|(x(k-1)(x*)|L|x(k-1)x*|L k|x(0)x*|及0 L 1知即x(k)收敛于x*。,4.1 不动点迭代法及其收敛性,|(x)|L 1,4.1.1 解一元方程的迭代法证明:(2)由|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*
7、|从而有又因|x(k)x(k-1)|=|(x(k-1)(x(k-2)|L|x(k-1)x(k-2)|L k-1|x(1)x(0)|,代入上式的右边,即得,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法(4.1-5)注:(1)若L 1,则收敛很慢,须考虑加速问题(2)(4.1-5)中第一式为后验公式迭代停止准则;第二式为先验公式预测迭代次数(3)定理是以a,b中任一点作初值,迭代都收敛,称为全局收敛。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法(4.1-5)注:(3)定理是以a,b中任一点作初值,迭代都收敛,称为全局收敛。(此要求较难满足,故考虑在)x*的某一
8、邻域内局部收敛性,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-2 设x*为的不动点,在x*的某邻域内连续,且|(x*)|0,只要x(0)x*,x*+,就有迭代法 x(k+1)=(x(k)收敛。证明:|(x*)|0,使x*,x*+U(x*),且 x x*,x*+有|(x)|q 1,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-2 设x*为的不动点,在x*的某邻域内连续,且|(x*)|0,只要x(0)x*,x*+,就有迭代法 x(k+1)=(x(k)收敛。证明:存在 0,使x*,x*+U(x*),且 x x*,x*+有|(x)|q 1 x
9、x*,x*+,|(x)x*|=|(x)(x*)|=|()|x x*|q|x x*|,,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-2 设x*为的不动点,在x*的某邻域内连续,且|(x*)|0,只要x(0)x*,x*+,就有迭代法 x(k+1)=(x(k)收敛。证明:存在 0,使 x x*,x*+,|(x)x*|,即(x)x*,x*+,由定理4.1-1知,任意x(0)x*,x*+,迭代法x(k+1)=(x(k)收敛。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法定理4.1-2 设x*为的不动点,在x*的某邻域内连续,且|(x*)|0,只要x(0)x
10、*,x*+,就有迭代法 x(k+1)=(x(k)收敛。注:只要x(0)充分接近x*,且|(x(0)|明显小于1,则x(k)收敛于x*。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法例2 求方程x=ex在0.5附近的根。由于|(0.5)|=e0.5 0.61明显小于1,故收敛解:Matlab代码如下k=1,x0=0.5x1=exp(-x0)while abs(x1-x0)0.00001 x1=exp(-x0)end,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法3.收敛阶定义4.1-1 设x(k)x*,记ek=x(k)-x*若存在p 1,及c 0,使则称x(k)
11、是p阶收敛的,或称收敛阶为p(p越高收敛越快)注:(1)p=1,0 1,称超线性收敛(3)p=2,称平方收敛,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法3.收敛阶因为|x(k+1)x*|=|(x(k)(x*)|=|()|x(k)x*|,其中在x(k)和x*之间。则所以若(x*)0,则为线性收敛想得到更高阶的收敛性,须(x*)=0,通常可考虑泰勒展式。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法3.收敛阶定理4.1-3 设x*为的不动点,正整数p 2,若(p)在x*的某邻域内连续,且满足(4.1.6)则x(k)p阶局部收敛。证明:(x*)=0(1),x(k
12、)局部收敛。,4.1 不动点迭代法及其收敛性,定理4.1-3 设x*为的不动点,正整数p 2,若(p)在x*的某邻域内连续,且满足(4.1.6)则x(k)p阶局部收敛。证明:(x*)=0(1),x(k)局部收敛。设(x)在x*处展开为,4.1 不动点迭代法及其收敛性,定理4.1-3 设x*为的不动点,正整数p 2,若(p)在x*的某邻域内连续,且满足(4.1.6)则x(k)p阶局部收敛。证明:设(x)在x*处展开为由(4.1-6)知,,4.1 不动点迭代法及其收敛性,定理4.1-3 设x*为的不动点,正整数p 2,若(p)在x*的某邻域内连续,且满足(4.1.6)则x(k)p阶局部收敛。证明:
13、由(4.1-6)知所以即x(k)p阶局部收敛。,4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数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)f 2(x)-2r2(x)f(x)f(x)而f(x*)=0,f(x*)0(单重零点),令(x*)=0有1 r1(x*)f(x*)=0,4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x
14、)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:令(x*)=0有1 r1(x*)f(x*)=0,4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:令(x*)=0,有1 r1(x*)f(x*)=0即取,则有(x*)=0,此时有(x)=-r1(x)f(x)-r2(x)f 2(x)-2r2(x)f(x)f(x),4.1 不动点迭代
15、法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:即取,则有(x*)=0,此时有(x)=-r1(x)f(x)-r2(x)f 2(x)-2r2(x)f(x)f(x)(x)=-r1(x)f(x)-r1(x)f(x)-r2(x)f 2(x)-4r2(x)f(x)f(x)-2r2(x)f(x)2-2r2(x)f(x)f(x),4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2
16、(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:(x)=-r1(x)f(x)-r1(x)f(x)-r2(x)f 2(x)-4r2(x)f(x)f(x)-2r2(x)f(x)2-2r2(x)f(x)f(x),4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:(x)=-r1(x)f(x)-r1(x)f(x)-r2(x)f 2(x)-4r2(x)f(x)f(x)-2r2(
17、x)f(x)2-2r2(x)f(x)f(x)其中令(x*)=0,有,4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:令(x*)=0,有,4.1 不动点迭代法及其收敛性,例3 设f C2a,b,x*为f的单重零点,(x)=x r1(x)f(x)r2(x)f 2(x)。试确定未知函数r1(x)、r2(x),使迭代法x(k+1)=(x(k)至少是三阶局部收敛的。解:令“(x*)=0,有即取,则有(x*)=0从而只要同时取迭代
18、法至少具有三阶局部收敛性,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速幂法中曾有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),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速 1在x(k)和x*之间 2在x(k+1)和x*之间因为x(k)x*,所以当k充分大时,(1)(2),4.1 不动点迭代法及其收敛性,
19、4.1.1 解一元方程的迭代法4.加速 1在x(k)和x*之间 2在x(k+1)和x*之间因为x(k)x*,所以当k充分大时,(1)(2)即(4.1-7),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速即(4.1-7),4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速即(4.1-7)记则 比x(k)收敛得快。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:由 知ek+1=(+k)ek,其中k0 x(k+1)x(k)=x(k+1)
20、x*(x(k)x*)=ek+1 ek=(1)+kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:x(k+1)x(k)=(1)+kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:x(k+1)x(k)=(1)+kek又 x(k+2)2x(k+1)+x(k)=(x(k+2)x(k+1)(x(k+1)x(k)=(1)+k+1ek+1(1)+kek=(1)
21、+k+1(+k)ek(1)+kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:x(k+1)x(k)=(1)+kek又 x(k+2)2x(k+1)+x(k)=(1)+k+1(+k)ek(1)+kek,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:x(k+1)x(k)=(1)+kek又 x(k+2)2x(k+1)+x(k)=(1)+k+1(+k)ek(1
22、)+kek=(1)2+kek,4.1 不动点迭代法及其收敛性,k=k+1+(2)k+k+1k0,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:又因为,4.1 不动点迭代法及其收敛性,x(k+1)x(k)=(1)+kekx(k+2)2x(k+1)+x(k)=(1)2+kek,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:又因为所以,4.1 不动点迭代法及其收敛性,x(k+1)x(k)=(1)+kekx(k+2)2x(k
23、+1)+x(k)=(1)2+kek,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则证明:所以,4.1 不动点迭代法及其收敛性,x(k+1)x(k)=(1)+kekx(k+2)2x(k+1)+x(k)=(1)2+kek,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,ek=x(k)x*0,0|1(线性收敛)则注:(1)(4.1-7)称为Aitken加速,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速定理4.1-4 设x(k)线性收敛于x*,且k0,e
24、k=x(k)x*0,0|1(线性收敛)则注:(2)k=1,2,称为史蒂文生迭代法。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速例4 用迭代法和Steffensen迭代法求函数f(x)=x lnx 2在区间(2,+)内的零点,取x(0)=3解:将f(x)=0化为等价的方程x=lnx+2=(x),由于(x)=1/x在2,+)上满足|(x)|1/2 1,且2(x)+,所以迭代法x(k+1)=ln x(k)+2收敛。,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速例4 用迭代法和Steffensen迭代法求函数f(x)=x lnx 2在区间(2,+)
25、内的零点,取x(0)=3解:Steffensen迭代法的计算公式为:取初值x(0)=3作迭代,结果见p336,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速例4 用迭代法和Steffensen迭代法求函数f(x)=x lnx 2在区间(2,+)内的零点,取x(0)=3解:迭代法x(k+1)=ln x(k)+2:x0=3k=1x1=log(x0)+2while(abs(x1-x0)0.0000001)x0=x1;k=k+1 x1=log(x0)+2end,4.1 不动点迭代法及其收敛性,4.1.1 解一元方程的迭代法4.加速解:Steffensen迭代法:x0=3k=1y
26、=log(x0)+2z=log(y)+2x1=z-(z-y)2/(z-2*y+x0)while(abs(x1-x0)0.0000001)x0=x1;k=k+1 y=log(x0)+2 z=log(y)+2 x1=z-(z-y)2/(z-2*y+x0)end,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法设非线性方程组 f(x)=0(4.1-1)考虑等价形式 x=(x)(4.1-2)迭代公式 x(k+1)=(x(k)k=0,1,2,(4.1-3)其收敛性有下述压缩映射(不动点)原理,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法定理4.1-5 设在闭区域
27、上满足条件存在q,0q1,使x,y,有|(x)(y)|q|xy|且x(x)。则(1)存在唯一不动点x*,且 x(0),迭代向量列收敛于x*。(2)证明与定理2.4-3及定理4.1-1相似,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法定理4.1-5 设在闭区域 上满足条件存在q,0q1,使x,y,有|(x)(y)|q|xy|且x(x)。则(1)存在唯一不动点x*,且 x(0),迭代向量列收敛于x*。(2)注:(1)保证序列,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法注:(2)若i(x)在 上可微,(x)=(1(x),2(x),n(x)T记则压缩条件|
28、(x)(y)|q|xy|可用下式替代其中D(x)是(x)在点x处的Jacobi矩阵,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法例5 用不动点迭代法求非线性方程在闭域 内的根。解:(1)取x(0)=(1,-1.5)T,按迭代公式:k=0,1,2,产生的序列收敛(见p339),4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法解:(1)取x(0)=(1,-1.5)T,按迭代公式:k=0,1,2,产生的序列收敛(见p339)k=1,x0=1,-1.5x1=log(1-x0(2),-sqrt(4-x0(1)2)while abs(x1-x0)0.0001 k=k
29、+1,x0=x1;x1=log(1-x0(2),-sqrt(4-x0(1)2)end,4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法例5 用不动点迭代法求非线性方程在闭域 内的根。解:(2)按迭代公式:k=0,1,2,产生的序列未必收敛(见p340),4.1 不动点迭代法及其收敛性,4.1.2 解非线性方程组的迭代法解:(2)按迭代公式:k=0,1,2,产生的序列未必收敛(见p340)k=1,x0=1,-1.5x1=sqrt(4-x0(2)2),1-exp(x0(1)while abs(x1-x0)0.0001 x1=sqrt(4-x0(2)2),1-exp(x0(1)en
30、d,4.1 不动点迭代法及其收敛性,4.2.1 一元非线性方程f(x)=01.牛顿迭代方法线性化:设f(x)在点x(k)处可微,则展开式用线性部分近似表示f(x)f(x(k)+f(x(k)(x x(k)即考虑方程 f(x(k)+f(x(k)(x x(k)=0,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程1.牛顿迭代方法即考虑方程 f(x(k)+f(x(k)(x x(k)=0,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程1.牛顿迭代方法即考虑方程 f(x(k)+f(x(k)(x x(k)=0若f(x(k)0,则有令:k=0,1,2,(4.2-4)称为Newto
31、n迭代公式其迭代函数为(4.2-5),4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(1)若x*是f(x)的单重根:f(x*)=0,f(x*)0因为而一般不为0,所以,Newton法是局部二阶收敛的 由定理4.1-3,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性例1 用Newton法求非线性方程f(x)=xex 1=0在(0,1)内的根,取x(0)=0.5。解:因为f(x)=(1+x)ex,故其Newton迭代公式为 k=0,1,2,从x(0)=0.5出发,计算结果见p342表4.2-1。,4.2 Newton迭代法及其变形,4.2.1 一
32、元非线性方程2.收敛性例1 用Newton法求非线性方程f(x)=xex 1=0在(0,1)内的根,取x(0)=0.5。解:因为f(x)=(1+x)ex,故其Newton迭代公式为 k=0,1,2,k=0,x0=0.5x1=x0-(x0*exp(x0)-1)/(1+x0)*exp(x0)while abs(x1-x0)0.00001 x1=x0-(x0*exp(x0)-1)/(1+x0)*exp(x0)end,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(2)若x*是f(x)的重根,即有 f(x)=(x x*)mg(x),其中g(x*)0,m 2因为f(x)=m(x
33、 x*)m-1g(x)+(x x*)mg(x)记x=x*+h,则,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(2)若x*是f(x)的重根,即有 f(x)=(x x*)mg(x),其中g(x*)0,m 2,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(2)若x*是f(x)的重根,即有 f(x)=(x x*)mg(x),其中g(x*)0,m 2,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(2)若x*是f(x)的重根,即有 f(x)=(x x*)mg(x),其中g(x*)0,m 2当m 2时,(x*)0,且|(x
34、*)|1所以Newton迭代法一阶收敛。,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(3)(2)的改进中若取易知有(x*)=0所以,若事先知道x*的重数,则可改迭代公式为(4.2-6)此时,迭代序列x(k)是二阶收敛的。,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程2.收敛性(3)或令则x*是u的单重零点,应用Newton法于u(x),有(4.2-7)迭代序列也是二阶收敛的,4.2 Newton迭代法及其变形,f(x)=(x x*)mg(x),其中g(x*)0,m 2,4.2.1 一元非线性方程例2 是方程x4 4x2+4=0的二重根(1)采用N
35、ewton法即注:迭代15次,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程例2 是方程x4 4x2+4=0的二重根(2)采用(4.2-6)k=0,x0=1.5x1=x0-(x02-2)/(2*x0)while abs(x1-x0)0.00001 x1=x0-(x02-2)/(2*x0)end迭代5次,4.2 Newton迭代法及其变形,4.2.1 一元非线性方程例2 是方程x4 4x2+4=0的二重根(3)采用(4.2-7)即迭代5次,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组 f(x)=0(4.1-1),4.2 Newton迭代法及其变形,4.2.2
36、多元非线性方程组f(x)=0(4.1-1)1.Newton迭代公式线性化 设f(x)=f1(x),f2(x),fn(x)T在点x(k)处可微,将fi(x)在点x(k)处展开用线性函数近似表示,即有(i=1,2,n),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式用线性函数近似表示,即有(i=1,2,n)其矩阵形式:f(x(k)+Df(x(k)(x x(k)=0(4.2-1),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式(i=1,2,n)其矩阵形式:f(x(k)+Df(x(k)(x x(k)=0(4.2-1),
37、4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式(i=1,2,n)其矩阵形式:f(x(k)+Df(x(k)(x x(k)=0(4.2-1)其中是f(x)在点x(k)处的Jacobi矩阵,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式矩阵形式:f(x(k)+Df(x(k)(x x(k)=0(4.2-1)若Df(x(k)可逆,则由(4.2-1)解出 x=x(k)Df(x(k)-1f(x(k)令 x(k+1)=x(k)Df(x(k)-1f(x(k)(4.2-2)称(4.2-2)为解方程组(4.2-1)的Newton迭代
38、公式,其迭代函数为 x Df(x)-1f(x),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式令 x(k+1)=x(k)Df(x(k)-1f(x(k)(4.2-2)称(4.2-2)为解方程组(4.2-1)的Newton迭代公式,其迭代函数为 x Df(x)-1f(x),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式令 x(k+1)=x(k)Df(x(k)-1f(x(k)(4.2-2)称(4.2-2)为解方程组(4.2-1)的Newton迭代公式,其迭代函数为 x Df(x)-1f(x)注:由于求逆较难,考虑(4
39、.2-2)的变形:Df(x(k)(x(k+1)x(k)=f(x(k)即解方程组:Df(x(k)x(k)=f(x(k)求得x(k)=x(k+1)x(k),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组1.Newton迭代公式 x(k+1)=x(k)Df(x(k)-1f(x(k)(4.2-2)注:由于求逆较难,考虑(4.2-2)的变形:Df(x(k)(x(k+1)x(k)=f(x(k)即解方程组:Df(x(k)x(k)=f(x(k)求得x(k)=x(k+1)x(k),即得迭代公式:k=0,1,2,(4.2-3),4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组2.
40、收敛性定理4.2-1 设x*是f(x)的零点,f(x)在x*的某一领域N内二次连续可微,且Df(x*)可逆,则存在闭球S=x|x x*|N,由S内任一点x(0)出发,按公式(4.2-2)产生的序列x(k)被包含在S内(x(0)Sx(k)S),且有|x(k+1)x*|C|x(k)x*|2,其中C与k无关。,4.2 Newton迭代法及其变形,x(k+1)=x(k)Df(x(k)-1f(x(k),4.2.2 多元非线性方程组2.收敛性证明:因为Df(x)在x*处连续,且Df(x*)可逆,故存在 0,使在S=x|x x*|N上Df(x)可逆,且f(x)二次连续可微于S。又因为f(x*)=0,所以若x
41、(k)S,就有x(k+1)x*=x(k)x*Df(x(k)-1f(x(k)f(x*)=Df(x(k)-1f(x*)f(x(k)+Df(x(k)(x(k)x*),4.2 Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有x(k+1)x*=Df(x(k)-1f(x*)f(x(k)+Df(x(k)(x(k)x*),4.2 Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有x(k+1)x*=Df(x(k)-1f(x*)f(x(k)+Df(x
42、(k)(x(k)x*)|x(k+1)x*|Df(x(k)-1|f(x*)f(x(k)+Df(x(k)(x(k)x*)|Df(x(k)-1|max|D2f(x*-t(x(k)-x*)|:0 t 1|x(k)-x*|2(其中f(x(k)=f(x*)+Df(x(k)(x(k)-x*)+D2f(x*-t(x(k)-x*)(x(k)-x*)2,4.2 Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有x(k+1)x*|Df(x(k)-1|max|D2f(x*-t(x(k)-x*)|:0 t 1|x(k)-x*|2,4.2
43、Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有|x(k+1)x*|Df(x(k)-1|max|D2f(x*-t(x(k)-x*)|:0 t 1|x(k)-x*|2因为f 在S上二次连续可微,所以max|D2f(x*t(x(k)x*)|:0 t 1MDf(x(k)-1在S上连续,所以|Df(x(k)-1|D这里M、D与k无关。,4.2 Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有|x(k+1)x*|Df(x(k)-1|max
44、|D2f(x*-t(x(k)-x*)|:0 t 1|x(k)-x*|2max|D2f(x*t(x(k)x*)|:0 t 1M|Df(x(k)-1|D,4.2 Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有|x(k+1)x*|Df(x(k)-1|max|D2f(x*-t(x(k)-x*)|:0 t 1|x(k)-x*|2max|D2f(x*t(x(k)x*)|:0 t 1M|Df(x(k)-1|D|x(k+1)x*|DM|x(k)x*|2=C|x(k)x*|2.,4.2 Newton迭代法及其变形,|x(k+1
45、)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有|x(k+1)x*|DM|x(k)x*|2=C|x(k)x*|2.,4.2 Newton迭代法及其变形,|x(k+1)x*|C|x(k)x*|2,4.2.2 多元非线性方程组2.收敛性证明:若x(k)S,就有|x(k+1)x*|DM|x(k)x*|2=C|x(k)x*|2.只要C 1,就有|x(1)x*|C|x(0)x*|2 C2 x(1)S 再由归纳法可证:x(k)S(k)由知,Newton法是局部二阶收敛的。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组例3 用Newton法求非
46、线性方程组在点(1.5,1)附近的根。解:由迭代公式有,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组例3 用Newton法求非线性方程组在点(1.5,1)附近的根。解:由迭代公式有从x(0)=(1.5,1)T出发,计算结果见p345表4.2-3。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组例3 用Newton法求非线性方程组在点(1.5,1)附近的根。解:由迭代公式有从x(0)=(1.5,1)T出发,计算结果见p345表4.2-3。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组例3 用Newton法求非线性方程组在点(1.5,1)附
47、近的根。解:Matlab代码:k=0,x0=1.5;1f=x0(1)+2*x0(2)-3;2*x0(1)2+x0(2)2-5;df=1,2;4*x0(1),2*x0(2);dx=-inv(df)*fx1=x0+dxwhile norm(x1-x0)0.00001 dx=-inv(df)*f x1=x0+dxend,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组注:虽然Newton法收敛较快,但(1)要求x(0)充分靠近x*才能保证其收敛性(2)每一次迭代须解方程组Df(x(k)x(k)=f(x(k)当Df(x(k)不可逆时无法继续,4.2 Newton迭代法及其变形,4.2.
48、2 多元非线性方程组3.改进Newton下山法为改善对初始值的要求,在迭代公式中引入松弛因子k:x(k+1)=x(k)kDf(x(k)-1f(x(k)或 Df(x(k)x(k)=k f(x(k)其中k的选取满足:|f(x(k+1)|f(x(k)|(4.2-10)即|f(x(k)|严格单减,且x(k)收敛于f 的零点。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组3.改进Newton下山法其中k的选取满足:|f(x(k+1)|f(x(k)|(4.2-10)即|f(x(k)|严格单减,且x(k)收敛于f 的零点。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组
49、3.改进Newton下山法k的选取满足:|f(x(k+1)|f(x(k)|(4.2-10)即|f(x(k)|严格单减,且x(k)收敛于f 的零点。方法(1)依次令进行“试探”,直到(4.2-10)满足,再进行下一次迭代,若选不到k,则Newton下山法失败,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组3.改进Newton下山法方法(2)求的最小值点*令 x(k+1)=x(k)*Df(x(k)-1f(x(k)这样迫使序列|f(x(k)|严格单调下降,从而从某个x(k)开始进入x*的附近。,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组3.改进Newton下山
50、法例4 求解非线性方程组初值取x(0)=0.5,1T(1)用Newton法:,4.2 Newton迭代法及其变形,4.2.2 多元非线性方程组3.改进Newton下山法例4 求解非线性方程组初值取x(0)=0.5,1T(2)用Newton下山法:,4.2 Newton迭代法及其变形,问题:求函数F(x)的最小值,即确定x*Rn 使注:(1)该问题为最优化理论中无约束化问题(2)上述最小值点记为,4.3 无约束优化问题的下降迭代法,4.3.0 预备知识(1)设多元函数F(.)具二阶连续偏导数,记 F的梯度g为多元向量值函数,4.3 无约束优化问题的下降迭代法,4.3.0 预备知识(1)设多元函数