非线性方程求根

非线性方程求根第1页，共57页，2023年，2月20日，星期二第二章非线性方程的求根方法引言方程求根的二分法迭代法及其收敛性Newton迭代法第2页，共57页，2023年，2月20日，星期二方程是在科学研究中不可缺少的工具；方程求解是科学计算中一个重要的研究对象；几百年前就已经找到了代数方程中二次至五次方程的求解公式；但是，对于更高次数的代数方程目前仍无有效的精确解法；对于无规律的非代数方程的求解也无精确解法；因此，研究非线性方程的数值解法成为必然。2.1 引言第3页，共57页，2023年，2月20日，星期二非线性方程的一般形式：f(x)=0代数方程：f(x)=a0+a1x+……+anxn

（an0）超越方程：f(x)中含三角函数、指数函数、或其他超越函数。用数值方法求解非线性方程的步骤：（1）找出隔根区间；（只含一个实根的区间称隔根区间）（2）近似根的精确化。从隔根区间内的一个或多个点出发，逐次逼近，寻求满足精度的根的近似值。2.1 引言第4页，共57页，2023年，2月20日，星期二2.2方程求根的二分法二分法的基本思想： 假定f(x)=0在[a,b]内有唯一单实根x*，考察有根区间[a,b]，取中点x0=(a+b)/2，若f(x0)=0，则x*=x0，否则，（1）若f(x0)f(a)>0，则x*在x0右侧，令a1=x0，b1=b;（2）若f(x0)f(a)<0，则x*在x0左侧，令a1=a，b1=x0。定理1（介值定理）设函数f(x)在区间[a,b]连续，且f(a)f(b)<0，则方程f(x)=0在区间[a,b]内至少有一个根。第5页，共57页，2023年，2月20日，星期二

以[a1,b1]为新的隔根区间，且其长度仅为[a,b]的一半，对[a1,b1]重复前过程，得新的隔根区间[a2,b2]，如此二分下去，得一系列隔根区间：

[a,b][a1,b1][a2,b2]…[ak,bk]……

其中每个区间长度都是前一区间的一半，故[ak,bk]的长度：当k趋于无穷时趋于0。即若二分过程无限继续下去，这些区间最后必收敛于一点x*，即方程的根。第6页，共57页，2023年，2月20日，星期二

性质：f(an)·f(bn)<0;bn–

an=(b–a)/2n2.2方程求根的二分法 每次二分后，取有根区间的中点xk=(ak+bk)/2作为根的近似值，则可得一近似根序列：x0,

x1,

x2,…该序列必以根x*为极限。始终收敛 实际计算中，若给定充分小的正数0和允许误差限1，当|f(xn)|<0或bn-an<1时，均可取x*xn。第7页，共57页，2023年，2月20日，星期二定理2

（二分法收敛定理）设x*为方程f(x)=0在[a,b]内的唯一根，且f(x)满足f(a)f(b)<0，则由二分法产生的第n个区间[an,bn]的中点xn满足不等式2.2方程求根的二分法证明：第8页，共57页，2023年，2月20日，星期二对于预先给定的精度只需要即：或者：这时的xk就是满足精度要求的近似值便有:第9页，共57页，2023年，2月20日，星期二例2.1用二分法求方程在区间[1,1.5］内的一个实根，要求误差不超过0.005。解因为即只要二分6次，便能达到所要求的精度。所以f(x)在区间[1,1.5]上单调增加，且f(1)f(1.5)<0,故根唯一且满足介值定理的条件，故可直接求得：第10页，共57页，2023年，2月20日，星期二计算结果kakbkxkf(xk)01.01.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-第11页，共57页，2023年，2月20日，星期二第12页，共57页，2023年，2月20日，星期二计算过程简单，收敛性可保证；对函数的性质要求低，只要连续即可。收敛速度慢；不能求复根和重根；调用一次求解一个[a,b]间的多个根无法求得。二分法求解非线性方程的优缺点：第13页，共57页，2023年，2月20日，星期二不动点迭代法不动点的存在性与迭代法的收敛性迭代收敛的加速方法2.3迭代法及其收敛性第14页，共57页，2023年，2月20日，星期二迭代法的基本思想：迭代法是一种逐次逼近的方法，用某个固定公式反复校正根的近似值，使之逐步精确化，最后得到满足精度要求的结果。例：求方程x3-x-1=0在x=1.5附近的一个根。解：将所给方程改写成假设初值x0=1.5是其根，代入得x1≠x0，再将x1代入得x2≠x1，再将x2代入得第15页，共57页，2023年，2月20日，星期二如此下去，这种逐步校正的过程称为迭代过程。这里用的公式称为迭代公式，即k=0,1,2,……迭代结果见下表：

k

xk

k

xk012341.51.357211.330861.325881.3249456781.324761.324731.324721.32472仅取六位数字，x7与x8相同，即认为x8是方程的根。x*≈x8=1.32472第16页，共57页，2023年，2月20日，星期二2.3.1不动点迭代法将连续函数方程f(x)＝0改写为等价形式：x=(x)其中(x)也是连续函数，称为迭代函数。不动点：若x*满足f(x*)=0，则x*=(x*)；反之，若x*=(x*)，则f(x*)=0，称x*为(x)的一个不动点。不动点迭代：(k=0,1,……)若对任意x0[a,b]，由上述迭代得序列{xk}，有极限则称迭代过程收敛，且x*=(x*)为(x)的不动点。第17页，共57页，2023年，2月20日，星期二但迭代法并不总令人满意，如将前述方程x3-x-1=0改写为另一等价形式：建迭代公式：仍取初值x0=1.5，则有x1=2.375，x2=12.396，x3=1904,结果越来越大。此时称迭代过程发散。x2

x1

x0y=x几何意义：第18页，共57页，2023年，2月20日，星期二收敛发散第19页，共57页，2023年，2月20日，星期二定理3（不动点的存在性和唯一性）

设(x)C[a,b]且满足以下两个条件：（1）对于任意x[a,b]，有a≤(x)≤b；（2）若(x)在[a,b]一阶连续，且存在常数0<L<1，使得对任意x[a,b]，成立

|’(x)|≤L

则(x)在[a,b]上存在唯一的不动点x*。2.3.2不动点的存在性与迭代法的收敛性第20页，共57页，2023年，2月20日，星期二不动点的存在性证明：证：若或显然(x)在[a,b]有不动点a或b；否则，设则有（因a≤(x)≤b）记则有故存在x*使得即x*即为不动点。第21页，共57页，2023年，2月20日，星期二不动点存在的唯一性证明：设有x1*≠x2*,使得则由拉格朗日中值定理有：其中，ξ介于x1*和x2*之间。由定理条件可得矛盾！故

x1*=x2*，不动点唯一。第22页，共57页，2023年，2月20日，星期二定理4（全局收敛性）设(x)C

[a,b]且满足以下两个条件：则对任意x0[a,b]，由xn+1=(xn)得到的迭代序列{xn}收敛到(x)的不动点x*，并有误差估计：（2）若(x)在[a,b]一阶连续，且存在常数0<L<1，使得对任意x[a,b]，成立 |’(x)|≤L（1）对于任意x[a,b]，有a≤(x)≤b；第23页，共57页，2023年，2月20日，星期二(0<L<1)故迭代格式收敛。所以证明：第24页，共57页，2023年，2月20日，星期二反复递推，可得误差估计式:上述式子的意义在于:只要前后两次近似值的差值足够小，就可以近似值xn+1达到任意的精度。第25页，共57页，2023年，2月20日，星期二定义设(x)有不动点x*，若存在x*的某邻域R：|x-x*|≤，对任意x0R，迭代过程xk+1=(xk)产生的序列{xk

}R且收敛到x*，则称不动点迭代法xk+1=(xk)局部收敛。 定理4给出的收敛性称全局收敛性，实际上其条件在较大的有根区间上是很难保证的，应用时通常只在不动点x*邻近考察其收敛性，称局部收敛性。第26页，共57页，2023年，2月20日，星期二证明：根据连续函数性质，因’(x)连续，存在x*的某邻域R：|x-x*|≤，对任意x

R，|’(x)|≤L<1(闭区间上的连续函数能取到最大值和最小值），且

|(x)-x*|=|(x)-(x*)|=|’(ξ)||x-x*|

≤L|x-x*|≤|x-x*|≤

即对任意x

R，总有(x)

R。由全局收敛性定义知，迭代过程xk+1=(xk

)对于任意初值x0R均收敛。定理5（局部收敛性）设x*为(x)的不动点，’(x)在x*的某邻域连续，且|’(x*)|<1，则不动点迭代法xk+1=(xk

)局部收敛。第27页，共57页，2023年，2月20日，星期二例用不同方法求的根。解：格式（1）格式（2）格式（3）格式（4）第28页，共57页，2023年，2月20日，星期二取x0=2，对上述四种方法，计算三步所得结果如下：k xk

(1)(2) (3) (4)0 x0

22 2 2x1

3 1.5 1.75 1.75x29 2 1.73475 1.732143x3

87 1.5 1.732361 1.732051第29页，共57页，2023年，2月20日，星期二收敛阶定义：设迭代过程xk+1=(xk)收敛于方程x=(x

)的根x*，若迭代误差ek=xk–x*

当k时成立下列渐近关系式：（c为常数，且c0）则称迭代过程是r阶收敛的。特别地，r=1时称线性收敛；

r=2时称平方收敛；

r>1时称超线性收敛。且r

越大，收敛越快。第30页，共57页，2023年，2月20日，星期二定理：设x*为x=(x

)的不动点，若(x

)满足：（1）(x

)在x*附近有连续的p阶导数(p>1)；（2）则迭代过程xn+1=(xn)在点x*邻近是p阶收敛的。得所以故迭代过程xn+1=(xn

)

p阶收敛。证：由Taylor公式第31页，共57页，2023年，2月20日，星期二Newton迭代法及其收敛性简化Newton迭代法（平行弦法）弦截法Newton下山法重根情形2.4Newton迭代法第32页，共57页，2023年，2月20日，星期二设方程f(x)=0有第k次近似根xk（f’(xk)0），将f(x)在xk展开： （在x和xk之间）2.4.1Newton迭代法及其收敛性基本思想：将非线性方程逐步归结为某种线性方程求解。可设第33页，共57页，2023年，2月20日，星期二记该线性方程的根为第k+1次近似xk+1，则 故f(x)=0可近似表示为即为Newton法迭代格式。（k=0,1,……）第34页，共57页，2023年，2月20日，星期二Newton迭代法的几何意义：（亦称切线法）xyx*xk+1xkPky=f(x)显然y=f(x)在点（xk,f(xk)）处的切线方程为：它与x轴交点的横坐标即为上述第k+1次近似:第35页，共57页，2023年，2月20日，星期二Newton迭代法的收敛性：迭代函数：定理：假设f(x)在x*的某邻域内具有连续的二阶导数，且设f(x*)=0，f’(x*)0，则对充分靠近x*的初始值x0，Newton迭代法产生的序列{xn}至少平方收敛于x*。设f(x*)=0，f’(x*)0，则’(x*)=0，故Newton迭代法在x*附近至少平方收敛。第36页，共57页，2023年，2月20日，星期二解：f’(x)=ex+xex，故newton迭代公式为k

xk

0 0.51 0.571022 0.567163 0.56714迭代3次即可达到4位有效数字的近似解0.56714。若用迭代公式则达到同有效数字需18次。例：用newton迭代法解方程xex-1=0。即取迭代初值x0=0.5，结果如下：第37页，共57页，2023年，2月20日，星期二Newton迭代法的缺陷：1.被零除错误2.程序死循环y=arctanx方程:f(x)=x3–3x+2=0在重根x*=1附近，f’(x)近似为零。对f(x)=arctanx存在x0，Newton迭代法陷入死循环。第38页，共57页，2023年，2月20日，星期二若|’(x)|=|1-cf’(x)|<1，即取0<cf’(x)<2在x*附近成立，则收敛。若取c=1/f’(x0)，则称简化Newton法。2.4.2简化Newton法（平行弦法）迭代公式：（c0,k=0,1,……）迭代函数：第39页，共57页，2023年，2月20日，星期二在Newton迭代格式中，用差商近似导数，2.4.3弦截法（割线法）称弦截法。得第40页，共57页，2023年，2月20日，星期二弦截法的几何意义：xyx*xk+1xk-1Pk-1y=f(x)xkPk弦线PkPk-1的方程：当y＝0时，第41页，共57页，2023年，2月20日，星期二例用简化的Newton迭代法和弦截法计算方程x3-3x+1=0的根。解：设f(x)=x3-3x+1，则f`(x)=3x2-3由简化的Newton法，得由弦截法，得第42页，共57页，2023年，2月20日，星期二x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553简化Newton法弦截法要达到8位有效数字，简化Newton法迭代11次，弦截法迭代5次，Newton迭代法迭代4次。第43页，共57页，2023年，2月20日，星期二无论前面哪种迭代法：（Newton迭代法、简化Newton法、弦截法）Newton迭代法x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收敛均与初值的位置有关。如x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.9631e-010x5=0收敛发散第44页，共57页，2023年，2月20日，星期二为防止Newton法发散，可增加一个条件：|f(xk+1)|<|f(xk)|，满足该条件的算法称下山法。可用下山法保证收敛，Newton法加快速度。2.4.4Newton下山法称Newton下山法。（0<1,—下山因子）记即第45页，共57页，2023年，2月20日，星期二从=1开始，逐次减半计算。的顺序，直到使下降条件|f(xk+1)|<|f(xk)|成立为止。的选取：即按第46页，共57页，2023年，2月20日，星期二例：求解方程要求达到精度|xn-xn-1|≤10-5，取x0=-0.99。解：先用Newton迭代法：f`(x)=x2-1x2=21.69118 x3=15.15689x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607

x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205需迭代13次才达到精度要求第47页，共57页，2023年，2月20日，星期二用Newton下山法，结果如下：k=0x0=-0.99f(x0)=0.666567k=1x1=32.505829f(x)=11416.4

=0.5x1=15.757915f(x)=1288.5

=0.25x1=7.383958f(x)=126.8

=0.125x1=3.196979f(x)=7.69

=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1

=0.5x2=2.60928f(x)=3.31

=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000k

下山因子

xk

f(xk)第48页，共57页，2023年，2月20日，星期二设f(x)=(x-x*)m

g(x),m

2，m为整数，g(x*)0,则x*为方程f(x)=0的m重根。此时有

f(x*)=f`(x*)=……=f(m-1)(x*)=0,f(m)(x*)02.4.5重根情形《方法一》只要f`(xk

)0，仍可用Newton法计算，此时为线性收敛。《方法二》若取则`(x*)=0，用迭代法求m重根，则具2阶收敛，但