← 全部笔记

数学分析

Newton迭代与收敛阶

文章目录

来源与整理范围 谢惠民等《数学分析习题课讲义》第2版上册第八章,印刷226–277页 / PDF243–294页,全52页已逐页核对。原编号在正文定位;证明重写、其他路线、条件比较及补充题由助手整理,不是逐字转录,不推断读者独立掌握。全31个原编号例题及凸性、经典不等式命题展开。补充原书留题证明及零分量处理,纠正Minkowski在p等于1时的等号条件;原书引用的Salamin–Brent背景与自行证明区分。 上册原书

1. 先证明收敛,再定义速度

原书以已趋于零的误差εn\varepsilon_n满足kεnα≤εn+1≤Kεnαk\varepsilon_n^\alpha\le\varepsilon_{n+1}\le K\varepsilon_n^\alpha定义α\alpha阶,k,K>0k,K>0;特别是εn+1/εnα→C∈(0,∞)\varepsilon_{n+1}/\varepsilon_n^\alpha\to C\in(0,\infty)。只有上界则称阶不低于α\alpha,不能称恰为此阶。

通常“线性收敛”还要求εn+1/εn→C<1\varepsilon_{n+1}/\varepsilon_n\to C<1。若比值趋于11,即便按原书较宽的阶数定义属于α=1\alpha=1,仍没有固定比例缩减,常称次线性;例如1/n1/n或L’Hospital法则与Taylor极限计算的正弦迭代。概念约定须先说清。

若εn+1≤Kεn2\varepsilon_{n+1}\le K\varepsilon_n^2且Kε0<1K\varepsilon_0<1,归纳得 εn≤K−1(Kε0)2n.\varepsilon_n\le K^{-1}(K\varepsilon_0)^{2^n}. 这说明足够小初始误差下的快速下降。KK不需要小于11;需要的是Kε0<1K\varepsilon_0<1。若最开始不满足,仍可能最终进入这样的局部阶段。

2. 例8.7.1:调和—几何组合的一阶收敛

设a0>b0>0a_0>b_0>0,递推an+1=2anbn/(an+bn)a_{n+1}=2a_nb_n/(a_n+b_n)、bn+1=an+1bnb_{n+1}=\sqrt{a_{n+1}b_n}。有bn<bn+1<an+1<anb_n<b_{n+1}<a_{n+1}<a_n,故上下序列各有极限。令δn=an−bn\delta_n=a_n-b_n,恒等式给 δn+1=an+1bn(an+1+bn+1)(an+bn)δn<12δn.\delta_{n+1}=\frac{a_{n+1}b_n}{(a_{n+1}+b_{n+1})(a_n+b_n)}\delta_n<\frac12\delta_n. 所以差趋于零,两极限为同一个A≥b0>0A\ge b_0>0。进一步系数趋于1/41/4,即δn+1∼δn/4\delta_{n+1}\sim\delta_n/4。

原书以区间宽度刻画算法速度。若要逐条序列的真实误差,也可证明an−A∼2δn/3a_n-A\sim2\delta_n/3、A−bn∼δn/3A-b_n\sim\delta_n/3: an−A=∑j=0∞(an+j−an+j+1),am−am+1=amam+bmδm.a_n-A=\sum_{j=0}^\infty(a_{n+j}-a_{n+j+1}),\qquad a_m-a_{m+1}=\frac{a_m}{a_m+b_m}\delta_m. 每个固定jj的项除以δn\delta_n趋于(1/2)(1/4)j(1/2)(1/4)^j;因δm+1<δm/2\delta_{m+1}<\delta_m/2,截去NN项后的尾和除以δn\delta_n有统一的几何小界。先取有限项极限再令N→∞N\to\infty,得到总和2/32/3。两误差比皆趋于1/41/4。

取a0=23,b0=3a_0=2\sqrt3,b_0=3时,原书把两序列解释为不断加倍边数的单位圆外接、内接正多边形半周长,极限为π\pi。几何辨认与以上代数收敛证明是不同部分;一般初值的AA不应随意标作π\pi。

3. 例8.7.2:算术—几何平均的二阶收敛

设a0>b0>0a_0>b_0>0,取an+1=(an+bn)/2a_{n+1}=(a_n+b_n)/2、bn+1=anbnb_{n+1}=\sqrt{a_nb_n}。同样保持bn<bn+1<an+1<anb_n<b_{n+1}<a_{n+1}<a_n,并且 δn+1=δn24(an+1+bn+1)<12δn.\delta_{n+1}=\frac{\delta_n^2}{4(a_{n+1}+b_{n+1})}<\frac12\delta_n. 共同极限A=AG(a0,b0)>0A=AG(a_0,b_0)>0存在,且δn+1/δn2→1/(8A)\delta_{n+1}/\delta_n^2\to1/(8A)。这次区间宽度二阶下降,与上一节相似的“均值组合”却有完全不同的速度。

若分析单独误差,an−an+1=δn/2a_n-a_{n+1}=\delta_n/2,而后续尾和为O(δn+1)=O(δn2)O(\delta_{n+1})=O(\delta_n^2),故an−A∼A−bn∼δn/2a_n-A\sim A-b_n\sim\delta_n/2,两者误差常数为1/(4A)1/(4A)。区间宽度常数与单序列误差常数并不相同。

原书列举Salamin–Brent圆周率算法作为背景应用;它的π\pi表达还需均值与相关积分的理论,不能单由“AGM二阶收敛”推出来。本笔记证明当前均值迭代的收敛与阶,不把原书引用的数值表当成自行执行的计算。

4. Newton从切线或局部线性化得到

在xnx_n处切线与xx轴交点为 xn+1=xn−f(xn)f′(xn).x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. 也可在f(ξ)=0f(\xi)=0的Taylor式中暂时忽略二阶余项,解出对根ξ\xi的线性近似。推导只给候选算法,还没有保证分母非零、迭代留在定义域或确实收敛。

命题8.7.1:一组全区间充分条件 设f∈C2[a,b]f\in C^2[a,b],f(a)<0<f(b)f(a)<0<f(b)、f′>0f'>0、f′′>0f''>0在整个区间成立。以x0=bx_0=b为初值,Newton迭代保持ξ<xn+1<xn≤b\xi<x_{n+1}<x_n\le b,收敛到唯一根ξ∈(a,b)\xi\in(a,b),且恰为二阶。

证明:先锁住位置。 介值及严格单调给唯一根。若xn>ξx_n>\xi,在xnx_n展开f(ξ)f(\xi),得 0=f(xn)+f′(xn)(ξ−xn)+12f′′(θn)(ξ−xn)2.0=f(x_n)+f'(x_n)(\xi-x_n)+\frac12f''(\theta_n)(\xi-x_n)^2. 正二阶项使切线在根处为负,因此ξ<xn+1\xi<x_{n+1};f(xn)>0f(x_n)>0又给xn+1<xnx_{n+1}<x_n。归纳保证每步留在区间,分母处处正。单调有界得极限η\eta;因f,f′f,f'连续且f′(η)>0f'(\eta)>0,在递推中取极限得f(η)=0f(\eta)=0,所以η=ξ\eta=\xi。

再算误差阶。 上式整理为 en+1=f′′(θn)2f′(xn)en2,en=xn−ξ>0.e_{n+1}=\frac{f''(\theta_n)}{2f'(x_n)}e_n^2,\qquad e_n=x_n-\xi>0. 所有中值点趋于ξ\xi,故en+1/en2→f′′(ξ)/(2f′(ξ))>0e_{n+1}/e_n^2\to f''(\xi)/(2f'(\xi))>0。这给恰为二阶,若最高系数为零只能先说至少二阶,需要继续找首项。

5. 前验与后验误差怎样获得

记m=min⁡f′>0m=\min f'>0、M=max⁡f′′>0M=\max f''>0,则en+1≤(M/(2m))en2e_{n+1}\le(M/(2m))e_n^2。若(M/(2m))e0<1(M/(2m))e_0<1,上述双指数上界可预估步数。区间足够短(b−a)<2m/M(b-a)<2m/M是一种可用的初始充分条件,不是Newton收敛的必要条件。

后验界来自∣f(xn)∣≥men|f(x_n)|\ge m e_n及在xn−1x_{n-1}处的Taylor展开:一次项被Newton递推消去,故 en≤∣f(xn)∣m≤M2m∣xn−xn−1∣2.e_n\le\frac{|f(x_n)|}{m}\le\frac M{2m}|x_n-x_{n-1}|^2. 这允许用已经算出的两次迭代差来保证当前误差;简单观察相邻值“很接近”而没有导数界,不具有同样的保证。

6. 例8.7.3–4:平方根和二阶常数

例8.7.4。 对A>0A>0取f(x)=x2−Af(x)=x^2-A,Newton得到xn+1=(xn+A/xn)/2x_{n+1}=(x_n+A/x_n)/2。任意x0>0x_0>0都使x1≥Ax_1\ge\sqrt A,此后除已到根外严格下降到根;恒等式 xn+1−A=(xn−A)22xnx_{n+1}-\sqrt A=\frac{(x_n-\sqrt A)^2}{2x_n} 给误差常数1/(2A)1/(2\sqrt A)。正数初值的重要性在于分母和取值域,不能删去。

例8.7.3。 A=2,x1=1A=2,x_1=1时,接下来为x2=3/2x_2=3/2、x3=17/12x_3=17/12、x4=577/408x_4=577/408。已有x42−2=1/4082x_4^2-2=1/408^2,因此 0<x4−2=14082(x4+2)<12.8⋅4082.0<x_4-\sqrt2=\frac1{408^2(x_4+\sqrt2)}<\frac1{2.8\cdot408^2}. 这里2>1.4\sqrt2>1.4且x4>2x_4>\sqrt2,上界小于2.2×10−62.2\times10^{-6}。这些有理等式和严格误差界可手算核验;原书随后用软件列更多有效位数,本笔记没有冒称复现那一整张软件计算表。

7. 为什么唯一根仍不足以保证Newton成功

多重根f(x)=(x−ξ)rf(x)=(x-\xi)^r,r>1r>1,迭代误差满足en+1=(1−1/r)ene_{n+1}=(1-1/r)e_n,只有一阶;根处f′=0f'=0使常见二阶结论的假设失效。

另一反例f(x)=x3−2x+2f(x)=x^3-2x+2只有一个实根,但初值00给0↦1↦00\mapsto1\mapsto0的周期,不收敛。两个驻点处函数值都正,故唯一根在负半轴;周期点分母并非零。可见根数、初值位置和切线构造的保持性必须分开研究。