1、第七章 非线性方程求根1110 ()0 ()0,1:()sin0nnnnxfxffxnfxxa xaxa xae求 解 非 线 性 方 程是 非 线 性 函 数，例：代 数 方 程。例超 越 方 程 本章介绍一些求方程实根的近似值的有效方法，一般来说,使用这些方法求非线性方程的实根可以分两步进行.第一步是确定某根的所在区间a,b，或给出根的近似值x0.第二步是对方程的根进一步精确化,得到满足精度要求的近似根.(),()()0 ()0,()0f xa ba bf af bf af b设在上连续且有且仅有一个根又。则可用对分法：不妨设.,2 2 02 ,2 02 ,11111aababbbbaab
2、afbaxbaf反之，令，否则：若输出根若）,b,a),ba2211 1 2）的计算，并产生区间重复对.2 02 ),3baxbafiiii则得到根，若1.非线性方程实根的对分法(二分法)二分法的收敛性 11 ,nna ba ba b二分法产生一个有根区间：11,11 ()()22nnnnnnnbaa bbaba区间长度：，足够大时，取近似值当2 baxnnnn1 2nnbaxx误 差：计 算 简 便，容 易 估 计 误 差，但 收 敛 较 慢。a x*x0 b()f x a1 b1以上公式可用于估计对分次数k.分析以上过程不难知道，对分法的收敛速度与公比为1/2的等比级数相同.由于210=1
3、024，可知大约对分10次，近似根的精度可提高三位小数位.对分法的收敛速度较慢，它常用来试探实根的分布区间，或求根的近似值.例例1 1 求求x3-3x+1=0的实根分布情况，并求的实根分布情况，并求0,10,1中的实根近中的实根近似值，精确到三位小数似值，精确到三位小数.解解:从从-4,4-4,4区间以步长为区间以步长为1 1计算计算f f(x x)=)=x x3 3-3-3x x+1+1的函数值，列的函数值，列如下表如下表x-4-4-3-3-2-2-1-10 01 12 23 34 4f(x)-5151-1717-1-13 31 1-1-13 319195353表表7-17-1可见，在可见，
4、在(-2,-1)(-2,-1)区间、区间、(0,1)(0,1)区间、区间、(1,2)(1,2)区间各有一实根，区间各有一实根，下面求下面求(0,1)(0,1)区间上的实根区间上的实根,按二分法按二分法.可可得得 x 0.347167968,0.3474121090.347167968,0.347412109若取若取 =0.0.0005,0005,当当k=13=13时时,bk-ak=0.0002441410.0005,=0.0002441410.0005,此时过程结束此时过程结束,取取 xk=(0.347167968+0.347412109)/2=0.347290038=(0.347167968
5、+0.347412109)/2=0.347290038 0.3470.347可见，对分法的优点是对函数的要求低可见，对分法的优点是对函数的要求低(只要求只要求f(x)连续连续)，方法，方法简便、可靠，程序设计容易，事先估计计算次数容易，收敛速简便、可靠，程序设计容易，事先估计计算次数容易，收敛速度恒定；缺点是不能求出偶重根，收敛速度较慢度恒定；缺点是不能求出偶重根，收敛速度较慢.取适当的步长取适当的步长h=(b-a)/m 逐一检验小区间逐一检验小区间a+kh,a+(k+1)h,(k=0,1,2,m-1)的两端函数值是否异号，的两端函数值是否异号，若异号，则按以上二分法求出其中的根；若同号则不作
6、求根而若异号，则按以上二分法求出其中的根；若同号则不作求根而转入检查下一个区间，只要转入检查下一个区间，只要h选得较小，则可求出本区间内的选得较小，则可求出本区间内的所有奇重实根所有奇重实根(包括单实根包括单实根).h选得过大，可能漏掉某些根；选得过大，可能漏掉某些根；h选得过小，则计算量增大选得过小，则计算量增大.对分法的思想方法还可用于搜索一个较大区间对分法的思想方法还可用于搜索一个较大区间a,b内实根的分内实根的分布情况布情况(不包括偶重实根不包括偶重实根)，实际的作法是：，实际的作法是：2.迭代法及其收敛性 连续。且改写方程：)(0)(xxxfxxxnnn )(1，得到序列建立迭代格式
7、：1 (0 )(limlimlimnnnnnnnfxxxxx则 若收敛必收敛到）的根：*()()0limnnnxxxf xxx 若收敛，即，则：也称作不动点迭代法 P265 迭代过程的几何表示 ):)(xyxyxx交点即真根。()yxy xO x*x2 x1 x0 xy0P1Q1P2P*P2Q3*0331k ()10 1.5.1 1 1(0,1,2)k 0 1 2 7 8 x 1.51.35721 1.330861.324kkf xxxxxxxxxk 例：求方程 在附近的根解：（）将方程改写为由此建立迭代公式331k721.32472 2 11.k 0 1 2 x1.52.37512.39 k
8、kxxxx迭代收敛。（）若将方程改写为建立迭代公式 迭代不收敛。P266表7-2*1*.(),1,();(2)01,()()(),()(0,1,)nnxa bxa baxbLx ya bxyL xyxxa bxa bxxnx0定 理设 函 数在 区 间上 满 足 条 件（）对 任 意，都 有存 在 常 数使 得 对 一 切都 有则 方 程在内 有 唯 一 的 根且 对 任 何初 值 x迭 代 序 列均 收 敛 于，并 有*10 x1nnLxxxL 不动点的存在性与迭代法的收敛性 （P267 定理1，）连续，且满足 2(),()(),(),()()0,()()0,0,(),xa bxxxxa b
9、aaabbba bxxa b 证：由条件（）知在上连续。令则在上连续，且故存在，使得（）即（）,所以方程在内有根。*12*12121212 (),2()()xxa bxxxxxxL xxxx假设方程在内有两个根由条件（），有导出矛盾，唯一性得证。0*11*0*0*1111 ,()()01,limx,()()nnnnnnnnkkkkkkkxa bxxxxL xxxxLxxLxxa bxxkxxxxL xxLx 对 任 意由 迭 代 公 式 有依 此 类 推，得因 所 以即 对 任 意 初 值迭 代 序 列均 收敛 到 方 程 的 根。类 似 地，对 任 意 正 整 数,有0 x112112101
10、010121010*10,(1)1 1,1 npnnpnpnpnpnnnpnpnnpppnnnn pLpLxLxxxxxxxxxxxxxxLLLxxL LLLxxLxxx 于是，对任意正整数有令得*1*.(),1,();(2)01,()(),()(0,1,)xnnxa bxa baxbLxa bxLxxa bxa bxxnx0定理 设函数在区间上满足条件（）对任意，都有存在常数使得对一切都有则方程在内有唯一的根且对任何初值x迭代序列均收敛于，并有101nnLxxxL改变定理条件（）可得以下结论 ,()()()()()()()()()2x ya bx yxyxyxyxyL xyx 证：设为上任意
11、两点，由微分中值定理，在之间至少存在一点，使得即满足上一定理的条件（），故结论成立。*10 x1()(),nnLxxxLLxxa b误差估计式表明，常数 越小，简单迭代法收敛越快。因而构造迭代函数的原则是使在有根区间上有尽可能小的上界。11211211111111*,1 npnnpnpnpnpnnppnnnnnnnnnpLpLxxxxxxxxLxxxxLxxxxxx 对任意正整数 有）令得可通过检查来判断迭代过程应否终止。（21112 ()10 (1.5)0.250,(2)10 1.5,2 11()1.51.51()212111()3.162212 2.51(2)1()f xxxffxxxxx
12、xxxx 例：用简单迭代法求方程的根。解：因为有根区间。（）因且2222011 1.51()1221.5111 ()1.52.25 1.5,2,xxxx 因且根据定理，任取由这两种等价方程所构造的简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。局部收敛性 (P269)*01*()(,)()()1,()(0,1,2,).nnxxO xxxxxxxxxxnx 定 理：如 果 函 数在的 一 邻 域内 连 续 可 微，为 方 程的 根，且则 存 在 正 数使 得 对 任 意迭 代 序 列收 敛 于设有不动点，如存在的某个领域对任意的迭代产生的序列且收敛到，则称迭代法是局部收敛的)(x*x*x*
13、:xxRRx 0)(1kkxx*xkx定义定理3局部收敛 *x*1 ()(,)()1,1,()1(),()()()(),()nnxO xxLxxxxLxxxxxxL xxxxxxxx证：因在内 连 续，且故 存在 正 数使 得 对，有另 一 方 面，由又 有即。由 上 面 定 理 知，迭 代 序 列收 敛 于。实际用迭代法计算时，先用对分区间法求较好的初值，然后再进行迭代。1*1()()(0112kkkkkpkxxxxxexxkeCCepppp 定义：设迭代过程收敛于方程的根,如果迭代误差当时成立下列渐进关系式为常数）则称该迭代过程是 阶收敛的。为线性收敛，为超线性收敛，为平方收敛。迭代法收敛
14、速度定义(P271)()1*(1)*()*(),()()()()0;()0pkkppxxxxxxxxxp定理：对于迭代过程如果在所求根的邻近连续，并且则该迭代过程在点邻近是 阶收敛的。*1*()*()()*11()01,()()()()()()!()()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep证：由于故具有局部收敛性。将在根处展开，由条件有定理4:3.迭代收敛的加速方法*01021*1010*2121*1021*12 ()()()()()()()()()()(),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx设是 根的 某 个
15、 预 测 值，通 过 两 次 迭 代 校 正有 由 微 分 中 值 定 理，有假 定改 变 不 大，近 似 地 取 某 个 近 似 值则 由*2*0212*1012()2xxxxxxxxxxx此 种 加 速 需 用 两 次 迭 代 值 进 行 加 工。埃特金(Aitken)方法(P273)1112111111 ()()()2kkkkkkkkkkkxxxxxxxxxxx如 果 将 一 次 改 进 值 作 为 一 步，则 计 算 公 式 如 下：校 正再 校 正改 进可以证明0lim*1xxxxkkk表明kxkx即为斯蒂芬森(Steffensen)迭代法 (P273)的收敛速度比的收敛速度快,且为
16、2阶收敛的020000()0 02f x xTaylor()f(x)f()(x-)()!fxxfxxxx在真根附近点展开成级数：4.牛顿(Newton)法 非线性问题的最简单解法是线性近似.将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想)0(000011)()()f(xxxfxfxxx：作为近似根解出 ,2 ,1 ,0 ),()(Newton 1nfxfxxxnnnn法：依次产生迭代格式，称00 000 xx)(xf)f(x:f(x)取线性部分近似代替 Newton 法的几何解释 )x(f)x(fxxx)y01011 0(x：为第二个近似根轴交点与00
17、0000 ,()()()()()ff xyfxxxxfxxx当在取后（在真根附近），过作的切线，则切线方程：)(xfy 0 x1x2x*x故也称切线法 12*(),()0,()()()()()()()()()()(kkkkxxa bxfxxxfxfxxxfxfx fxxfxxfxfx迭代过程的收敛速度依赖于迭代函数的选取。如果当时则该迭代过程只可能是线性收敛。对牛顿公式其迭代函数为由于假定是的一个单根，即*)0,()0,()0,fxxx则由上式知由上述定理知，牛顿法在根的邻近至少是平方收敛的。410 10.()1,()(1)()()()1 10.5kxxxxxkkkkxef xxefxexf
18、xxexxxfxxxexxxx例：用牛顿法解方程解：牛顿法迭代函数为牛顿公式为可先用二分法或经验确定迭代初值，再按牛顿公式进行迭代。Newton法具有收敛快，稳定性好，精度高等优点，是求解非 线性方程的有效方法之一。但它每次迭代均需计算函数值与 导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。(见P277表7-5)牛顿法应用举例21 01 ().2kkkCxCCCxxx对于给定正数，应用牛顿法解二次方程即导出求开方值的计算程序02211221010202000 11 ()()22.,2.1 0,1.kkkkkkkkkkkkkkkkkxxCxCxCxCxxxCxCxCxC
19、xCxCxCxCxCqqxCCxCqxqkxC 现证此迭代公式对于初值都是收敛的。由迭代公式得记对任意总有，故当时，注 牛顿法每次计算)()(kkxfxf计算量较大1。简化牛顿法（平行弦法）0)(1CxCfxxkkk若1)(1)(xfCx即2)(0 xfC在根x*附近成立，则迭代为局部收敛。P2802。牛顿下山法 即在牛顿迭代法的基础上附加一个条件)()(1kkxfxf计算公式：)()(1kkkkxfxfxxkkkxxx)1(11)()(1kkkkxfxfxx即5.弦截法与抛物线法11111 (),(),(),()0(),(),(),(),()0()0 kkkkkkrkkkrrrkkf xf
20、xfxxxxf xf xf xf xpxpxf xxx基本思想：利用一些函数值来回避导数值的计算。设是的一组近似根，利用函数值构造插值多项式并适当选取的一个根作为的新的近似根，这就确定了一个迭代过程，记迭代函数为：1(,).12kkkrxxxrr当时为弦截法，当时为抛物线法。一、弦截法 （P283）111111111111 ,()0(),()()()0()0.()()()()()()().()()()kkkkkkkkkkkkkkkkkkkkkxxf xf xf xpxpxf xxf xf xpxf xxxxxf xxxxxf xf xf xxxf设是的近似根，利用构造一次插值多项式，并用的根作
21、为的新的近似根由此迭代公式可看作牛顿公式11()()()()kkkkkxf xf xfxxx中的导数用差商取代的结果。弦截法的几何表示x0Xx*x1 x2 x3Y f(x)0P0P2 P111011 ,.,kkkkkxxxxxxx弦截法在求时要用到前面两步的结果需两个初值，而牛顿切线法在计算时，只用到前一步的值。弦截法收敛性定理 （P285）*01111*():()0,()().()()151.618.2kkkkkkkf xxxxxfxxxf xxxxxf xf xpx定理：假设在根 的邻域内具有二阶连续导数，且对任意有又初值那么当邻域 充分小时，弦截法将按阶收敛到根11*11111*1111
22、1.11*1 ,()0(),()()()()()2()()()()()22 ()0()kkkkkkkkkkkkxxxfxpxxxffxpxxxxxffpxxxxxe expxpx 证：用数学归纳法证明迭代值全属于。首先证明当时必属于。设，是以为节点的插值多项式。由又由于是的根，故有*11111*11211()()()()()()()().kkkkkkkkpxpxpxxfxfxxxfexx 1112121112111101().2(),m ax(),.2 m in(),1,.,kkkkkkkxxkkkkkkfee efxxxxfxMfxMxxeMeeMxxx 对 上 两 个 式 子 联 立由 于
23、故 当时记选 取 邻 域充 分 小 以 保 证则 当与属 于时因由 数 学 归 纳 法 知kx一 切全 属 于23224111223*111112*1 ()0,()2()().2()1kkkkkkkkkkkkkkkkkeM eeMeeMeeeMMkekfee eeMeeffxMfxeM 由递推不等式故当时有收敛性得证。当 充分大时，由这里 令11.*,kzkkkdzzz则有差分方程111 11 111121211221212111*101.618,0.618;,111 ()kkkkkkkkkkkkkzcckzzzzzccc ckzcedddMMM 方程是一差分方程，考虑的特解，其特征方程 为故
24、差分方程的通解为（为任意常数）由于当 充分大时故 而1 1111*11*1*111 1 1.618.kkzckkkkkeddMMeeMeMMe，故有（）此说明弦截法收敛的阶 迭代法加速（埃特金方法）*01021*1010*2121*1021*12 ()()()()()()()()()()(),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx 设是根的某个预测值，通过两次迭代校正有 由微分中值定理，有假定改变不大，近似地取某个近似值则由*2*0212*1012()2xxxxxxxxxxx此种加速需用两次迭代值进行加工。用弦截法给出埃特金算法的几何解释()xx用弦截
25、法讨论形如得方程，给出埃特金算法的几何解释。yx()yx*P3P2P0P1P*x2x1x3x0 x332131301020213012*2013 ()2.,.Pxxxxxxxxxx xxxxxxxxxxx点的坐标满足由此解出此即为加速埃特金公式从图上可知 尽管迭代值比和更远偏离了但按上式定出的却明显地扭转了这种发散的趋势二、抛物线法 （P285）12221 ()0,(),(),.kkkkf xxxxpxpxx设已知方程的三个近似根以这三点为节点构造二次插值多项式并适当选取的一个零点作为新的近似根 这样确定的迭代过程称抛物线法 也称密勒法()f x2()P x*x1kxkx1kx2kx抛物线法计
26、算公式2112112112122 ()(),()+,()().,+,()()()()kkkkkkkkkkkkkkkkkkkkkkkkkpxfxf xxxxf xxxxxxxaf xxxbf xxf xxxxxcfxpxaxx插 值 多 项 式令 22*2112()4224,.2sgn()4kkkkkkkkkkkkkkkkkkkkkkkkkkkkkbxxcbba ccxxxabba cxxxxxxxxcbxxbba c在三 个 近 似 根 中 假 定更 接 近 根故 新 的 近似 根 应 在邻 近 即较 小 于 是 抛 物 线 计 算 公 式 为*012*,(),()01.84 fxxxxxxx
27、fxx可 以 证 明 如 果在 其 零 点邻 近 三 阶 连续 可 微 且 初 值充 分 接 近则 抛 物 线 法是 收 敛 的。特 别 地，若是 方 程的 单 根，收 敛 解 为。另 一 方 面，在 收 敛 性 的 证 明 中 虽 然 要 求 初始 值 充 分 接 近 根，但 实 际 计 算 表 明，抛 物 线法 对 初 值 要 求 并 不 苛 刻，在 初 值 不 太 好 的 情 况下 常 常 也 能 收 敛。缺 点 是 程 序 较 复 杂，并 在 计算 实 根 的 过 程 中，也 常 常 需 要 采 用 复 数 计 算，增 加()0fx了 工 作 量。因 此，抛 物 线 法 适 用 于 当
28、 初 值不 太 好 时 求 方 程的 复 根 的 情 况。三、代数方程的牛顿法0101100012012100 ()()0 ()()()()()()().();nnnnnnnnf xf xf xf xa xa xaxaxxf xf xxxp xp xb xbxbxbab如果是多项式，可针对多项式的特性，建立求解代数方程的有效解法。计算函数值的秦九韶法：多项式 以为除式，有令代入并与上式比较同次幂的系数得00010100;,11;,1;().().iiiiiinnnbaabx binbax binaf xbf xb 000000()2000000020 ():()()()()()()()2!()
29、()()()().!()()()()()()().()nnnfxf xfxf xf xxxfxxxfxxxf xxxp xnfxp xxxp xfxxxq xq xc xc用秦九韶算法求的台劳展开式：由此可知，导数又可看作用因式相除得出的余式。令其中 3132000101,;,11;().nnniiinxcxccbcbx cinfxc101110010011 ()0()()()();,1;().;,11;().nnnnkkkkkkiikikniikiknfxa xa xaxafxxxfxfxfxbabax binfxbcbcbx cinfxc代 数 方 程 的 牛 顿 法：对用 牛 顿 公 式
30、其 中 函 数 值与 导 数 值均 可 方 便 求 出：解非线性方程组的牛顿迭代法 P287考虑方程组0),(0),(111nnnxxfxxf或矩阵形式 F（X）=O其中),(1nxxX),(1nffFfi中至少一个是非线性函数时，称作非线性方程组注：非线性方程组可视作矩阵形式的单变量方程，所以前面介绍的牛顿法这里也可使用。假设已有方程的近似根),()()(1)(knkkxxx将fi(x)在x(k)处泰勒展开，且取线性部分)()()()()()(kkkxxxFxFxF令右端为零即得：)()()()()(kkkxFxxxF其中nnnnnnxfxfxfxfxfxfxfxfxfxF212221212111)(称为Jacobi矩阵。得迭代式,.2,1,0)()()(1)()()1(kxFxFxxkkkk
