解非线性方程组的数值方法

在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。第一节非线性方程求根的迭代法第二节非线性方程组的简单迭代法第三节非线性方程组的Newton型迭代法第四节无约束优化算法第八章非线性方程组的数值方法2/4/20231满足方程(1)的x值通常叫做方程的根或解，也叫函数f(x)=0的零点。非线性方程的一般形式f(x)=0(1)这里f(x)是单变量x的函数，它可以是代数多项式

f(x)=a0+a1x+……+anxn

(an≠0)也可以是超越函数，即不能表示为上述形式的函数。第一节非线性方程求根的迭代法2/4/20232

在用近似方法时，需要知道方程的根所在区间。若区间a,b含有方程f(x)=0的根，则称a,b为f(x)=0的有根区间；若区间a,b仅含方程f(x)=0的一个根，则称a,b为f(x)=0的一个隔根区间。求隔根区间有两种方法：一、非线性方程求根的基本问题包括：根的存在性、根的隔离和根的精确化

根的存在定理(零点定理)：

f(x)为[a,b]上的连续函数，若f(a)·f(b)<0，则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调递增或递减的，则f(x)=0仅有一个实根。2/4/20233例如，求方程3x-1-cosx=0的隔根区间。将方程等价变形为3x-1=cosx

，易见y=3x-1与y=cosx的图像只有一个交点位于[0.5，1]内。画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x)的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。(1)描图法2/4/20234(2)逐步搜索法运用零点定理可以得到如下逐步搜索法：先确定方程f(x)=0的所有实根所在的区间为[a,b],从x0=a出发,以步长

h=(b-a)/n

其中n是正整数，在[a,b]内取定节点：

xi=x0＋ih

(i=0,1,2，……，n)

计算f(xi)的值,依据函数值异号及实根的个数确定隔根区间,通过调整步长，总可找到所有隔根区间。2/4/20235例2.2

求方程x3-3.2x2+1.9x+0.8=0的隔根区间。解：设方程的根为α，ν=max{1，|-3.2|，|1.9|}μ=max{|-3.2|,|1.9|,|0.8|}=3.2故,即有根区间为(-4.2,-0.2)和(0.2,4.2)对于m次代数方程

f(x)=xm+am-1xm-1+…+a1x+a0=0其根的模的上下界有如下结论：(1)若μ=max{|am-1|,……,|a1|,|a0|}，则方程根的模小于μ+1(2)若ν=max{1，

|am-1|,……,|a1|},则方程根的模大于2/4/20236f=inline('x^3-3.2*x^2+1.9*x+0.8')

h=1;n=4/h;fori=0:nf(-4.2+i*h)endfori=0:nf(0.2+i*h)end2/4/20237h=0.8-1.377160000000e+002-81.95600000000002-43.34800000000001-18.81999999999999-5.300000000000000.284000000000001.060000000000000.50000000000000-0.316000000000001.684000000000009.5720000000000026.42000000000000h=1-1.377160000000e+002-70.81600000000002-29.51600000000001-7.816000000000000.284000000000001.060000000000000.200000000000000.140000000000006.8800000000000026.420000000000002/4/20238定义1

若有x*满足(x*)=0，则称x*为方程的根或函数f(x)的零点，特别地，如果函数f(x)可分解为f(x)=(x

x*)mg(x)且g(x*)0,则称x*是f(x)的m重零点或f(x)=0的m重根。当m=1时，称x*是f(x)的单根或单零点。

2/4/20239定理1

设函数f(x)∈Cm[a,b],则点p∈(a,b)是f(x)

的m重零点，当且仅当

f(p)=f’(p)=f’’(p)=…=f(m-1)(p)=0,但f(m)(p)≠0证明:(充分性)将f(x)在点p作m-1阶Taylor展开2/4/202310由假设证毕2/4/202311例给定方程：x-sinx=0,问x*=0是几重零点.解：设f(x)=x-sinx,则f(0)=0;f’(x)=1-cosx,f’(0)=0;f’’(x)=sinx,f’’(0)=0;f(3)(x)=cosx,f

(3)(0)=1;由定理1,x*=0是3重零点.2/4/202312

知α=φ(α)，即{xk}收敛于方程的根α

。二、简单迭代法

简单迭代法又称为不动点迭代法，基本思想是首先构造不动点方程x=φ(x)，即由方程f(x)=0变换为等价形式x=φ(x),式中φ(x)称为迭代函数。然后建立迭代格式：xk+1

=φ(xk)称为不动点迭代格式。当给定初值x0

后,由迭代格式xk+1=φ(xk)可求得数列{xk}。如果{xk}收敛于α，且φ(x)在α连续，则α就是不动点方程的根。因为：2/4/202313迭代法的几何意义记y1=x,y2=φ(x),它们交点的横坐标α即为方程的根2/4/202314xyy=xx*y=φ(x)x0p0x1p1xyy=xx*y=φ(x)x0p0x1p1xyy=xx*y=φ(x)x0p0x1p1xyy=xx*y=φ(x)x0p0x1p12/4/202315对于迭代法需要讨论的基本问题是，迭代函数的构造，迭代序列的收敛性和收敛速度以及误差估计。问题：φ(x)的形式不唯一，如：2/4/202316取初始值，计算结果如下：

0.3

0.3

-0.0047

0.3617

-1.0108

0.3732

0.3753

0.37572/4/202317用蛛网图观察不动点迭代zlxp1132/4/202318若从任何可取的初值出发都能保证收敛，则称它为大范围收敛。如若为了保证收敛性必须选取初值充分接近于所要求的根，则称它为局部收敛。通常局部收敛方法比大范围收敛方法收敛得快。因此，一个合理的算法是先用一种大范围收敛方法求得接近于根的近似值（如对分法），再以其作为新的初值使用局部收敛法（如迭代法）。这里讨论迭代法的收敛性时，均指的是局部收敛性。2/4/202319考虑方程x=φ(x),φ(x)C[a,b],若(I)当x[a,b]时，φ(x)[a,b]；(II)对x[a,b],有

|φ’(x)|L<1成立。则任取x0[a,b]，由xk+1=φ

(xk)得到的序列收敛于φ(x)

在[a,b]上的唯一不动点。并且有误差估计式：(k=1,2,…)且存在极限定理2（收敛定理）2/4/202320证明：①φ(x)

在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间而2/4/202321③当k

时，

xk收敛到x*？④2/4/202322⑤⑥注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性：若在x*的某领域B={x||xx*|}有φC1[a,b]且|φ’(x*)|<1，则由x0B开始的迭代收敛。即调整初值可得到收敛的结果。2/4/202323迭代法收敛阶则称数列为阶收敛，也称相应的迭代法为阶方法。当且时，称数列为线性收敛.当时，称数列平方收敛（或二阶收敛）.当时，称数列为超线性收敛。定义设数列收敛于,令误差,如果存在某个实数及正常数，使2/4/202324显然，越大，数列收敛的越快。所以，迭代法的收敛阶是对迭代法收敛速度的一种度量。2/4/202325定理3（迭代法的局部收敛定理）设α是方程x=φ(x)的根，如果(1)迭代函数φ(x)在α的邻域可导；(2)在α的某个邻域S={x:|x-α|≤δ},对于任意的xS有则对于任意的初值x0S

，迭代公式xn+1=φ(xn)

产生的数列{xn}，收敛于方程的根α

。2/4/202326定理3’（迭代法的局部收敛定理）设α是方程x=φ(x)的根，如果(1)迭代函数φ(x)在α的邻域一阶导数连续；则存在α的某个邻域S={x:|x-α|≤δ}

及正数L<1,使对于任意的xS有取任意的初值x0S

，迭代公式xn+1=φ(xn)

产生的数列{xn}，收敛于方程的根α

。2/4/202327控制误差ε的方法：(1)先计算满足误差要求的迭代次数n，再迭代。由可得(2)事后误差估计法。由于因而可用|xn-xn-1|≤ε来控制迭代过程。2/4/202328例

用迭代法求x3-x2-1=0在隔根区间[1.4,1.5]内的根，要求准确到小数点后第4位.解：(1)由方程的等价形式构造迭代公式由2/4/202329知φ(x)在（1.4,1.5)可导，且故迭代法收敛。2/4/202330functiony=diedai(fname,x0,e,N)%用途:迭代法求解非线性方程f(x)=0y=x0;x0=y+2*e;k=0;whileabs(x0-y)>e&k<Nk=k+1;x0=y;y=fname(x0);

disp(y)endifk==N

disp('warning')end

f=inline('(x^2+1)^(1/3)');y=diedai(f,1.5,10^(-4),500);2/4/202331三、牛顿迭代法任取初始值，上过点的切线方程为：与轴交于点过点的切线方程为与轴交于点如此下去得牛顿迭代公式:用切线代替曲线，用线性函数的零点作为

f(x)的零点的近似值。2/4/202332（收敛的充分条件）设f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整个[a,b]上f”不变号且f’(x)0；(3)选取x0

[a,b]使得f(x0)f”(x0)>0；则Newton’sMethod产生的序列{xk}收敛到f(x)在[a,b]的唯一根。根唯一产生的序列单调有界，保证收敛。定理42/4/202333yx0bax0yx0bax0yx0bax0yx0Bax02/4/202334例

用迭代法求在隔根区间[1.4,1.5]内的根，要求准确到小数点后第4位。（1）牛顿迭代公式为（2）当时有，因,故取,牛顿迭代法收敛。2/4/202335functiony=newton(fname,dfname,x0,e,N)y=x0;x0=y+2*e;k=0;whileabs(x0-y)>e&k<Nk=k+1;x0=y;y=x0-fname(x0)/dfname(x0);

disp(y)endifk==N

disp('warning')end2/4/202336

f=inline('x^3-x^2-1');

df=inline('3*x^2-2*x');y=newton(f,df,1.5,0.5*10^(-4),500)2/4/202337（局部收敛性）设f

C2[a,b]，若x*

为f(x)在[a,b]上的根，且f’(x*)0，则存在x*的邻域使得任取初值，Newton’sMethod产生的序列{xk}收敛到x*，且满足定理5证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：2/4/202338只要f’(x*)0，则令可得结论。注：在单根附近收敛快，是平方收敛的．由Taylor展开：2/4/202339

对于迭代过程，如果在所求根的邻近连续，并且(*)

则该迭代过程在点邻近是P阶收敛的。定理6证明：由于。据上定理，立即可以断定迭代过程具有局部收敛性。再将在根处展开，利用条件(*)，则有注意到，由上式得2/4/202340因此对迭代误差有:。这表明迭代过程确实为P阶收敛，证毕。2/4/2023412/4/2023422/4/2023432/4/2023442/4/2023451、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。牛顿迭代法的优缺点2、缺点：选定的初值要接近方程的解，否则有可能得不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。2/4/202346牛顿法主要有两个缺点：局部收敛，计算量大。2/4/202347割线法的几何意义用割线代替曲线，用线性函数的零点作为

f(x)的零点的近似值。收敛阶为P=1.6182/4/202348（Horner算法）四、高次代数方程求根的嵌套算法2/4/2023492/4/202350五、迭代法和离散动力系统

对于一个给定的迭代法，它产生的序列除了收敛于一个固定点外，还可能有十分复杂的行为。研究当时渐近行为成为离散动力系统这门学科分支所关注的内容。它的理论、方法和结果不但对科学计算有重大意义，近年来它也为其他领域的科学家深感兴趣，它所引出的混沌、分形等术语已广泛出现在各类文献中。2/4/202351考虑二次函数的迭代，即一维离散动力系统其中是一个可变的参数，观察不同的r值对迭代点列的影响。1.取r=[00.30.60.91.21.51.82.12.42.73.03.33.63.9],观察迭代序列的极限。2/4/202352（1）当r

分别等于0,0.3,0.6,0.9,1.2,1.5,1.8,2.1,2.4时，每个r所对应的后50个迭代值均重合为一点，这说明对这些值极限存在。（2）当r

分别等于3.0,3.3时，迭代值对应两个点，这说明极限不存在。（3）当r

分别等于3.6,3.9时，出来更多的点。zlx12/4/2023532.用蛛网图观察三种不同类型的迭代r=2.7r=3.2r=3.90.2,0.5120,0.7995,0.5129,0.7995,0.5130,0.7995,0.5130,…构成一个二循环zlx22/4/2023543.加密r的值，得到Feigenbaum图。

我们看到，随着r的增加，图中从开始的一条曲线（不动点）分裂为两条曲线（2周期循环）,4条曲线（4周期循环）,8条曲线（8周期循环）,…,这种现象叫倍周期现象。zlx002/4/202355第二节非线性方程组的简单迭代法

一、引言2/4/202356非线性方程组解的复杂性2/4/202357clear,clfx1=-2:.2:2;y2=-2:.2:2;y1=f1(x1);x2=f2(y2);plot(x1,y1,'r:',x2,y2,'b')xlabel('x'),ylabel('y')(3)a=0(4)a=-1(1)a=1(2)a=1/42/4/202358几类典型非线性问题2/4/2023592/4/202360例：半线性椭圆型边值问题解:(1)剖分求解域.YN+1N:210012….NN+1X2/4/202361(2)对微分算子进行离散.2/4/202362在每个点(xi