数值分析3-2课件

1牛顿法牛顿法的局部收敛性牛顿法的大范围收敛性简化牛顿法和牛顿下山法不用导数求根非线性方程组电子工程应用第三章非线性方程求根2牛顿法的几何意义：x0y=f(x)x1x2x*解方程f(x)=033.3.2牛顿法的局部收敛性(1)当x*是方程的单根时，可得二阶局部收敛4(2)当x*是方程的m重根时，可得3.3.2牛顿法的局部收敛性5一阶局部收敛3.3.2牛顿法的局部收敛性63.3.2牛顿法的局部收敛性牛顿法求重根只是线性收敛则若用此迭代格式求解，具有2阶收敛速度（但需要知道根的重数m）若取迭代函数为7牛顿法牛顿法的局部收敛性牛顿法的大范围收敛性简化牛顿法和牛顿下山法不用导数求根非线性方程组电子工程应用第三章非线性方程求根83.3.3牛顿法的大范围收敛性定理3.7

设f(x)在区间[a,b]

上存在二阶连续导数，且满足条件：1)f(a)f(b)<0;2)x∈[a,b]时，f’(x)≠0；

3)当x∈[a,b]时，保号；

则区间[a,b]

上存在唯一根。对任意初值x0∈[a,b]

，由牛顿迭代公式产生的序列{xk}二阶收敛.4)9条件1）保证方程在[a,b]

区间上存在根。条件2）保证方程在[a,b]

区间上存在唯一根。条件3）则保证曲线的凹凸性不变，即不存在拐点。3.3.3牛顿法的大范围收敛性增凸减凸增凹减凹条件4）保证了φ∈[a,b]1011证明：设第一种情形3.3.3牛顿法的大范围收敛性由于f(x)在区间[a,b]上单调增加，且由条件(4)知，f(x0)<0.

设过点(x0,f(x0))的切线为

切线在曲线上方123.3.3牛顿法的大范围收敛性依此类推，可得切线与x轴的交点x1，介于(x0,x*)之间。序列{xk}单调增加，且有上界x*。证毕！13例

给出用牛顿法求平方根√c(c

>0)的迭代公式，并分析算法的收敛性，计算√115。解：x2–c

=0令

f(x)=x2–c,则牛顿迭代法求解x2–c

=0的计算格式分析该迭代格式的收敛性。3.3.3牛顿法的大范围收敛性14条件1）f(0+)<0,f(+∞)>0,满足；条件2）x∈(0,+∞)

时，f’(x)>0,满足；条件3）x∈(0,+∞)

时，f’’(x)=2

>0,满足；条件4）计算√115，若取初值x0=12，迭代4次，可得结果。若取x0∈(√c,+∞)

，则满足3.3.3牛顿法的大范围收敛性实际上，只要x0>0，迭代法都收敛。15fi=inline('(x+115/x)/2');x0=12;er=1;k=0;whileer>0.5e-7;x=fi(x0)er=abs(x-x0);x0=x;k=k+1;endk=4,x=10.7238053.3.3牛顿法的大范围收敛性16牛顿迭代公式牛顿迭代格式的局部收敛性牛顿迭代格式的大范围收敛性简化牛顿法和牛顿下山法不用导数求根非线性方程组电子工程应用第三章非线性方程求根173.3.4

简化牛顿法和牛顿下山法牛顿法每迭代一次，要计算导数值，影响计算效率为避免计算重复计算导数值，可取其为一定值，如称为简化牛顿法简化牛顿法183.3.4

简化牛顿法和牛顿下山法x0y=f(x)x1x2x*迭代函数：推广的简化牛顿法：把f’(xk)取为任意的常数1/C(C≠0)，迭代函数193.3.4

简化牛顿法和牛顿下山法牛顿法的收敛性依赖于初值的选取。如果初值偏离所求的根x*较远，则牛顿法可能发散。为了防止迭代发散，对迭代过程附加一项要求，即：满足此要求的算法称为下山法将下山法与牛顿法结合起来使用（下山法保证函数值稳定下降，牛顿法加快收敛速度）牛顿下山法牛顿下山法202）与前一步的近似值xk适当加权平均其中，λ（0<λ<1）称为下山因子。3）则有试选常取，直到使条件满足，此时得迭代值xk+1

。然后令k=k+1，将λ恢复为1，返回步骤3），进行下一步循环。1）牛顿法计算结果作为中间结果：牛顿下山法的计算步骤：21牛顿迭代公式牛顿迭代格式的局部收敛性牛顿迭代格式的大范围收敛性简化牛顿法和牛顿下山法不用导数求根非线性方程组电子工程应用第三章非线性方程求根22为避免计算导数，可以用差商代替求导，就得到割线法（弦截法）。割线法也有一些变形，如试位法、Muller法、反二次插值。此外还有混合方法，如Brent法。3.4

不用导数求根牛顿法每迭代一次，要计算导数值，计算量较大，有时没法计算导数。233.4.1

割线法及其变形割线法（弦截法）差商代替求导割线法24设x*是方程f(x)=0的根,x0和x1是x*附近的两个点.y=f(x)过两点(x0,f(x0))和

(x1,f(x1))的割线与x轴的交点横坐标为x2x0x1x*x2几何意义：y=f(x)割线法（弦截法）25(k

=1,2,·······)·······定理3.8设f(x)在x*邻近二阶连续可微，且则存在

，当

时，由割线法产生的序列{xk}收敛于

x*，且收敛阶为

。这里p

是的正根。即：割线法超线性收敛，收敛性介于线性收敛和二次收敛之间。26例:

用割线法求方程在x0=0.4附近的实根，精确到4位有效数字。解：取x0=0.4，x1=0.6割线法（弦截法）27f=inline('x*(x+1)^2-1');x0=0.4;x1=0.6;er=1;k=0;whileer>0.00005x=x1-f(x1)*(x1-x0)/(f(x1)-f(x0))er=abs(x-x1);x0=x1;x1=x;k=k+1;endk=4,x=0.46557割线法（弦截法）k012345xk0.40.60.45745

0.46460

0.465580.46557试位法28在给定含有根的区间

[a,b]（假设f(a)f(b)<0），定义下一个点为因为点和在x轴的两侧，所以c点一定在[a,b]中根据

或者

选择

[a,c]或者

[c,b]作为新的有根区间试位法

给定区间

[a,b]，使f(a)*f(b)<0

fori=1,2,3,...

iff(c)=0stopendiff(a)*f(c)<0b=celsea=cendend29试位法算法试位法例:

用试位法在初始区间[-1,1]上求

的根

。30解：给定x0=-1,x1=1，计算新的点因为，所以新的区间是[x0,x2]=[-1,0.8]，完成了第一步。区间长度缩短的幅度远小于1/2。比二分法慢。Muller法用前面估计的3个点xi,xi+1,xi+2，画出通过它们的抛物线y=p(x)（抛物线的轴平行于y轴）31抛物线一般与x轴没有交点，或者有两个交点如果有两个交点，则距离xi+2最近的一个点被选作xi+3如果抛物线与x轴不相交，则方程有复数解，就需要确定复根反二次插值(InverseQuadraticInterpolation,IQI)用前面估计的3个点xi,xi+1,xi+2，画出通过它们的抛物线，抛物线具有x=p(y)的形式（轴线平行于x轴）32将y=0代入，整理得这条抛物线将与x轴相交于一个点，作为xi+3通过3个点(a,A),(b,B),(c,C)的二次多项式x=P(y)是其中反二次插值(InverseQuadraticInterpolation,IQI)给定3个初始估计，通过IQI方法，就可以计算出新的估计值x=P(0)，即：近似根用新的估计值去代替最早的一个估计值33IQI的另一种实现方式，是用新的估计值代替前面3个估计值中误差最大的那个。343.4.2

Brent法Brent方法是混合方法：把保证收敛的二分法与具有快速收敛特性的求根方法结合起来建立了一种保留各自最有用性质的新方法用于连续函数f，而且区间以a和b为界。

35算法：首先尝试用反二次插值法如果满足下面两条之一（1）后向误差改进了（2）包含根的区间至少缩短一半则用计算结果代替xi,ai,bi中的一个否则，尝试用割线法如果还是失败，则用二分法进行，来保证其区间长度至少减半3.4.2

Brent法36MATLAB的fzero()命令实现了一种Brent方法，它包含了一个预处理步。如果用户没有提供含有根的初始区间，则fzero就会自己找一个比较好的初始区间。3.4.2

Brent法如果用户提供了初始区间，则不需要预处理步。如分别输入：fzero(‘x^3+x-1’,1,optimset(‘Display’,‘iter’))（在1附近求根，并显示迭代方法）和fzero('x^3+x-1',[0,1],optimset('Display','iter'))（在[0,1]区间求根，并显示迭代方法）373839牛顿迭代公式牛顿迭代格式的局部收敛性牛顿迭代格式的大范围收敛性简化牛顿法和牛顿下山法不用导数求根非线性方程组电子工程应用第三章非线性方程求根403.5

非线性方程组当多个非线性方程构成方程组时，求解难度增加本节主要介绍求解非线性方程组的牛顿法及其变形3.5.1多变量牛顿法单变量牛顿法来源于泰勒展开式提供的线性近似对于非线性方程组，同样处理41定义向量值函数表示对向量值函数求偏导的Jacobi矩阵为3.5.1多变量牛顿法42在点x0附近，对向量值函数进行泰勒展开，其展开式为例如，在x0=(0,0)附近，的泰勒展开式为

3.5.1多变量牛顿法43牛顿法是忽略高阶无穷小O(h2)的一个线性近似假设x*为根，x0为假设的初始解，则为避免进行矩阵求逆s故：多变量牛顿法的迭代步骤如下Jacobi矩阵讲义第三章p18,(3-5-2)符号有误s是向量，可利用解线性方程组的方法，求解s44例：取初始估计为(1,2)，用牛顿法求解方程组解：Jacobi矩阵为初始点为x0=(1,2)T,求解方程，即可以采用消去法，或迭代法求解，得到s=(0,-1)T45第二步需要计算新的Jacobi矩阵，为求解解为s=(-1/8,-3/8)T。故第二步迭代产生步骤uv01.000000000000002.0000000000000011.000000000000001.0000000000000020.875000000000000.6250000000000030.829036348267120.5643491124260440.826040108170650.5636197735028450.826031357732410.5636241621316360.826031357654190.5636241621612670.827031357654190.56362416216126463.5.1多变量牛顿法可见，经过7次迭代，解已经精确到小数点后14位，收敛速度极快。此外，观察方程组可以发现，方程组具有对称性，若(u,v)是一个解，则(-u,-v)也是一个解。例：

用牛顿法求出以下方程组的解：47解：Jacobi矩阵为求解矩阵方程利用初始点x0=(1,0)T，有解为s=(-1,16)T。故第一步迭代产生483.5.1多变量牛顿法继续求解，经过15次迭代，可以得到一个精确到小数点后6位的近似解为(0.865939,0.462168)。若选择初值为(-1,0)，经过30次迭代，可以得到精确到小数点后6位的近似解为(0.886809,-0.294007)；而若选择初值为(2,2)，经过6次迭代可以得到准确解(1,1)。注：本方程组有3个根493.5.2Broyden方法若能计算出Jacobi矩阵，则牛顿法是求解非线性方程组的一种好方法若不能，可以有多种牛顿法的变形。其中Broyden方法是一种选择

Broyden方法，不必计算Jacobi矩阵用一个矩阵来近似Jacobi矩阵，并将它代入牛顿法的迭代公式中，用于迭代计算根的近似值（类似于求非线性方程的简化牛顿法）5051牛顿迭代公式牛顿迭代格式的局部收敛性牛顿迭代格式的大范围收敛性简化牛顿法和牛顿下山法不用导数求根非线性方程组电子工程应用第三章非线性方程求根523.6电子工程应用（

工业高温炉）电子工程师会涉及到半导体器件制作，如太阳能电池和集成电路。这类生产过程会涉及到采用工业高温炉来处理材料。通过加热元件将炉内加热，但热量也会通过炉壁传到外面使得炉温降低。变量x表示炉内的温度，通常假设炉内温度均匀；T表示炉外面周围空气的温度。单位都用°K来表示。炉温的变化率可以建立为如下的模型533.6电子工程应用（

工业高温炉）其中是正常数，与炉子的热容量有关。表示由于对流引起的热损耗表示由于辐射引起的热损耗表示加热元件上的电流，假设电流保持为常数要得到稳定的温度，就要求542.5电子工程应用（

工业高温炉）假设加热元件电流为

，周围温度是

，炉子的其它参数为即：求以下方程的根553.6电子工程应用（

工业高温炉）56m=50;eps=1.e-6;T=293.15;u=21.0;alpha=50.0;beta=2.0e-7;gamma=800.0;xmin=1000;xmax=1200;a=-beta;b=-alpha;c=gamma*u^2+alpha*T+beta*T^4;f=inline('a*x^4+b*x+c','a','b','c','x');f1=inline('4*a*x^3+b','a','b','x');x0=xmin;x1=(xmax+xmin)/2;ii=0;whileabs(x1-x0)>eps&ii<m;x0=x1;x1=x0-f(a,b,c,x0)/f1(a,b,x0);ii=ii+1;endx=x13.6电子工程应用（

工业高温炉）ii=4,x=1.1185e+003牛顿法求解程序57zd电介质ε0εr接地板III3.6电子工程应用（TM表面波截止波数）求沿+z方向传播的表面波的截止波数二维接地介质板波导的几何结构。厚度为d、相对介电常数为εr的介质假定在y和z方向是无限延伸的。假设波沿着在+z方向传播并具有传播因子，而在y方向无变化（）。x583.6电子工程应用（TM表面波截止波数）纵向场分量法若传输线或波导区域无源，则频域Maxwell方程：传输线或波导均匀，具有的传播因子

593.6电子工程应用（TM表面波截止波数）利用Ez和Hz，由以上六个方程可得四个横向场分量其中，截止波数。

是填充在波导区域中的材料的波数

603.6电子工程应用（TM表面波截止波数）Ez可以由亥姆霍兹方程求出

因为，简化为二维波方程这里613.6电子工程应用（TM表面波截止波数）xzd电介质ε