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

数值计算方法,第四章 计算函数零点和极值点的迭代法,本章讨论非线性方程（组）的求解问题,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)称为迭代序列(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)有可能：(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(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(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*|=|(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*|从而有又因|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*的某一邻域内局部收敛性,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 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*，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)是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)局部收敛。,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阶局部收敛。证明：由(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)=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 不动点迭代法及其收敛性,例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(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(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从而只要同时取迭代法至少具有三阶局部收敛性,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 不动点迭代法及其收敛性,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)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)+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)+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+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，ek=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,+)内的零点，取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=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 设在闭区域 上满足条件存在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记则压缩条件|(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+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)end,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)称为Newton迭代公式其迭代函数为(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 一元非线性方程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 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*)|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)采用Newton法即注：迭代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 多元非线性方程组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),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迭代公式，其迭代函数为 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.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.收敛性定理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(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(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 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|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)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法求非线性方程组在点(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)附近的根。解：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.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 多元非线性方程组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下山法例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)设多元函数