课程计算方法第2章方程求根

数值分析——第二章方程求根第2章方程求根解数值问题直接法逐次逼近法——规则：A1

A2…An…精确解其中Ai可以是数、向量、矩阵或其他两种形式：迭代法——利用递推公式搜索法——利用法则（如二分法）直接法——小型问题及特殊问题逐次逼近法——大型问题及非线性问题。2.1非线性方程的迭代法设非线性方程f(x)=0(2.1)若有

，使f(

)=0，则称

为方程(2.1)的根，或称

为函数f(x)的零点。注：(1)代数方程——5次以上不能用解析公式求根超越方程——求解更难(2)若f(x)=0在区间[a，b]上仅有一根，则称[a，b]为方程(2.1)的单根区间；若f(x)=0在区间[a，b]上有多个根，则称[a，b]为方程(2.1)的多根区间，统称为有根区间。2.1非线性方程的迭代法2.1.1根的搜索1.逐步搜索法为明确起见，不妨假定f(a)<0，f(b)>0。我们从有根区间[a，b]的左端x0=a出发，某个预定的步长h(譬如取h=(b–a)/N，N为正整数)一步一步地向右跨，每跨一步进行一次根的“搜索”，即检查节点xk=a+kh上的函数值f(xk)的符号，一旦发现节点xk与端点a的函数值异号，即f(xk)>0，则可以确定一个缩小了的有根区间[xk-1，xk]，其宽度等于预定的步长h.2.1非线性方程的迭代法2.1.1根的搜索1.逐步搜索法【例2-1】考察方程f(x)=x3–x–1=0.注意到f(0)<0，f(2)>0，知f(x)在区间(0，2)内至少有一个实根.

设从x=0出发，取h=0.5为步长向右进行根的搜索，列表记录各个节点上函数值的符号(表6-1)，我们发现区间[1.0，1.5]内必有一根.x00.51.01.5f(x)的符号---+2.1非线性方程的迭代法2.1.1根的搜索1.逐步搜索法在具体运用上述方法时，步长h的选择是个关键.很明显，只要步长h取得足够小，利用这种方法可以得到具有任意精度的近似根.不过当h缩小时，所要搜索的步数相应增多，从而使计算量增大。因此，如果精度要求比较高，单用这种逐步搜索方法是不合算的。下述二分法可以看作是逐步搜索方法的一种改进。2.1非线性方程的迭代法2.1.1根的搜索2.二分法考察有根区间[a，b]，取中点x0=(a+b)/2将它分为两半,然后进行根的搜索,即检查f(x0)与f(a)是否同号。如果确系同号，说明所求的根

在x0的右侧，这时令a1=x0，b1=b;否则

必在x0的左侧，这时令a1=a，b1=x0.不管出现哪一种情况，新的有根区间[a1，b1]的长度仅为[a，b]的一半.2.1非线性方程的迭代法2.1.1根的搜索2.二分法对压缩了的有根区间[a1，b1]又可施行同样的手续，即用中点x1=(a1+b1)/2将区间[a1，b1]再分为两半，然后通过根的搜索判定所求的根在x1的哪一侧，从而又确定一个新的有根区间[a2，b2]，其长度是[a1，b1]的一半。2.1非线性方程的迭代法2.1.1根的搜索2.二分法如此反复二分下去，即可得出一系列有根区间[a，b][a1，b1][a2，b2]…[ak，bk]…其中每个区间都是前一个区间的一半，因此[ak，bk]的长度bk–ak=(b–a)/2k+1当时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点

，该点显然就是所求的根.2.1非线性方程的迭代法2.1.1根的搜索2.二分法每次二分后，设取区间[ak，bk]的中点xk=(bk+ak)/2作为根的近似值，则在二分过程中可以获得一个近似根的序列x0，x1，x2，…，xk…该序列必以根为极根。由于|–xk|≤(bk–ak)/2=(b–a)/2k+1

只要二分足够多次(即k充分大)，便有|–xk|<，这里为预定的精度.2.1非线性方程的迭代法2.1.1根的搜索2.二分法【例2-2】求方程f(x)=x3–x–1=0在区间[1.0，1.5]内的一个实根，要求准确到小数点后的第2位.

解：这里a=1.0，b=1.5，而f(a)<0，f(b)>0。取[a，b]的中点x0=1.25，将区间二等分，由于f(x0)<0，即f(x0)与f(a)同号，故所求的根必在x0右侧，这时应令a1=x0=1.25，b1=b=1.5，而得到新的有根区间[a1，b1].

如此反复二分下去。2.1非线性方程的迭代法2.1.1根的搜索2.二分法【例2-2】求方程f(x)=x3–x–1=0在区间[1.0，1.5]内的一个实根，要求准确到小数点后的第2位.

我们现在预估所要二分的次数，按误差估计(1.1)式，只要二分6次(k=6)，便能达到预定的精度|–x6|≤0.005.二分法的计算结果如表2-2.Kakbkxkf(xk)符号01.01.51.25-11.25l.375+21.3751.3125-31.3125l.3438+41.34381.3281+51.32811.3203-61.32031.3242-2.1非线性方程的迭代法2.1.1根的搜索2.二分法二分法是电子计算机上一种常用算法，下面列出计算步骤：步1准备计算f(x)在有根区间[a，b]端点处的值，f(a)，f(b).

步2二分计算f(x)在区间中点(a+b)/2处的值f((a+b)/2).2.1非线性方程的迭代法2.1.1根的搜索2.二分法二分法是电子计算机上一种常用算法，下面列出计算步骤：步3判断若f((a+b)/2)=0则(a+b)/2即是根，计算过程结束。否则检验：若f((a+b)/2)与f(a)异号，则根位于区间[a，(a+b)/2]内，这时以(a+b)/2代替b；若f((a+b)/2)与f(a)同号，则根位于区间[(a+b)/2，b]内，这时以(a+b)/2代替a.2.1非线性方程的迭代法2.1.1根的搜索2.二分法二分法是电子计算机上一种常用算法，下面列出计算步骤：反复执行步2和步3，直到区间[a，b]长度缩小到允许误差范围之内，此时区间中点(a+b)/2即可作为所求的根.

上述二分法的优点是算法简单，而且收敛性总能得到保证，但是不能用来求重根。2.1非线性方程的迭代法2.1.1根的搜索2.二分法

2.1非线性方程的迭代法2.1.2简单迭代法1.定义设方程x=

(x)(2.2)与(2.1)同解，即f(x)=0x=

(x)。任取初值x0，令x1=

(x0)，x2=

(x1)，…，一般地xk+1=

(xk)k=0，1，2，…(2.3)称(2.3)为迭代法(迭代过程、迭代格式)，

(x)称为迭代函数，xk称为第k步迭代值。若{xk}收敛，称迭代法收敛，否则称迭代法发散。2.1非线性方程的迭代法2.1.2简单迭代法1.定义设方程x=

(x)(2.2)与(2.1)同解，即f(x)=0x=

(x)。任取初值x0，令x1=

(x0)，x2=

(x1)，…，一般地xk+1=

(xk)k=0，1，2，…(2.3)

若xk

，则=

()，从而f()=0，即为方程(2.1)的根。2.1非线性方程的迭代法2.1.2简单迭代法【例2-3】求方程x3–x–1=0在x=1.5附近的根。解：方程化为等价方程，取初值x0=1.5，则

…取6位数字时x7与x8相同，即可认为x7是方程的根，x7=1.32472。2.1非线性方程的迭代法2.1.2简单迭代法【例2-3】求方程x3–x–1=0在x=1.5附近的根。解：方程化为等价方程，取初值x0=1.5，则

取6位数字时x7与x8相同，即可认为x7是方程的根，

x7=1.32472。2.1非线性方程的迭代法2.1.2简单迭代法应当指出，迭代法的效果并不是总能令人满意的。譬如，方程化为另一种等价形式：x=x3–1，建立迭代公式xk+1=xk3–1。迭代初值仍取x0=1.5，则有x1=2.375，x2=12.39，x3=1904.…。继续迭代下去已经没有必要，因为结果显然会越来越大，不可能趋于某个极限。这种不收敛的迭代过程称作是发散的。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【定理2-1】假定迭代函数(x)满足下列两项条件：

1.对任意x∈[a，b]有a

(x)b；

2.存在正数L<1,使对任意x∈[a，b]有|'(x)|L<1.则迭代过程xk+1=

(xk)对于任意初值x0∈[a，b]均收敛于方程x=

(x)的根。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性证明：由微分中值定理xk+1–=

(xk)–

()='(

)(xk–)式中

是与xk之间某一点,当xk∈[a，b]时

∈[a，b]，因此利用条件可以断定|xk+1–|L|xk–|据此反复递推有|xk–|Lk|x0–|，故当k

时，迭代值xk将收敛到所求的根。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【定理2-1】假定迭代函数

(x)满足下列两项条件：

1.对任意x∈[a，b]有a

(x)b；

2.存在正数L<1,使对任意x∈[a，b]有|'(x)|L<1.则迭代过程xk+1=

(xk)对于任意初值x0∈[a，b]均收敛于方程x=

(x)的根。检验：,[，][1，2]，

,所以迭代法收敛2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性说明：(1)条件是充分的而非必要的.如方程x3–2x=0,

取，则，在[–1，1]上不满足|'(x)|<1，但实际上=0，取初值x0在0附近，迭代法有可能收敛。

(2)通常可先用定理判断，若不满足，则改变迭代公式使之满足，然后迭代。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性说明：(3)若|'(x)|1，则|xk+1–xk|=|

(xk)–

(xk–1)|=|'(

)||xk–xk-1||xk–xk-1|…|x1–x0|，故迭代法必发散。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性左图表示收敛的序列，右图表示发散的序列。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【推论】在定理条件下，有如下误差估计：

(2.4)(2.5)

证明:∵|xk+1–|=|

(xk)–

()|=|'(

)||xk–|L|xk–||xk+1–xk|=|

(xk)–

(xk–1)|=|'(

)||xk–xk–1|L|xk–xk–1|∴|xk–||xk–xk+1|+|xk+1–|L|xk–xk–1|+L|xk–|从而2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【推论】在定理条件下，有如下误差估计：

(2.4)(2.5)

证明:从而又因为|xk–xk–1|L|xk–1–xk–2|…Lk–1|x1–x0|所以 2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性

(2.4)(2.5)说明：(1)(2.4)用于控制迭代过程：(2.5)用于事先估计迭代次数：由求出k。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性说明：(2)定理是以[a，b]中任一点作初值，迭代都收敛，称为全局收敛。此要求较难满足，故考虑在的某一邻域内—局部收敛性【定理2-1'】若方程有根,|'()|<1，且

'在的某邻域U()内连续,则存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收敛。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【定理2-1'】若方程有根,|'()|<1，且

'在的某邻域U()内连续,则存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收敛。证明：∵|'()|<1，及

'(x)在U()内连续，存在

>0，使[–

，+

]U()，且x[–

，+

]有|'(x)|L<1.x[–

，+

]，|

(x)–|=|

(x)–

()|=|‘(

)||x–|L|x–|<

，即

(x)[–

，+

]1.对任意x∈[a，b]有a

(x)b；2.存在正数L<1,使对任意x∈[a，b]有|'(x)|L<1.则迭代过程xk+1=

(xk)对于任意初值x0∈[a，b]均收敛于方程x=

(x)的根。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【定理2-1'】若方程有根,|'()|<1，且

'在的某邻域U()内连续,则存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收敛。证明：x[–

，+

]有|'(x)|L<1.

x[–

，+

]，

(x)[–

，+

]由定理6-1知，任意x0[–

，+

]，迭代法xk+1=

(xk)收敛。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【定理2-1'】若方程有根,|'()|<1，且

'在的某邻域U()内连续,则存在

>0,只要x0[–

，+

]，迭代法xk+1=

(xk)收敛。说明：只要x0充分接近，且|'(x0)|明显小于1，则{xk}收敛于

。2.1非线性方程的迭代法2.1.2简单迭代法2.收敛性【例2-4】求方程x=e–x在x=0.5附近的一个根，要求精度

<10–3。分析：记f(x)=x–e–x，则f(0.5)<0，f(1)>0，即根∈[0.5，1]，要验证定理6-1的条件很麻烦，只须验证定理6-1'的条件，或|'(x)|<1于[0.5，1]上。解：因为

(x)=e–x，

'(x)=–e–x，|

'(x)|=e–x<1于[0.5，1]上。(当然有|

'()|<1)。所以取x0=0.5，迭代法必收敛。计算结果如表kxkkxk00.570.56843810.60653180.56640920.54523990.5675630.579703100.56690740.560065110.56727750.571172120.56706760.564863130.5671862.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶一种迭代格式要具有实用意义，不但需要肯定是收敛的，还要求它收敛得比较快，就是说要有一定的收敛速度，否则未必有实际意义。那么，何谓收敛速度呢？下面就来介绍这个概念.2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶【定义2-1】设由某方法确定的序列{xk}收敛于方程的根，如果存在正实数p，使得

(C为非零常数)则称序列{xk}收敛于的收敛速度是p阶的，或称该方法具有p阶敛速。2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶【定义6-1】设由某方法确定的序列{xk}收敛于方程的根，如果存在正实数p，使得

(C为非零常数)当p=1时，称该方法为线性(一次)收敛；当p>1时，称方法为超线性收敛。特别当p=2时，称方法为平方(二次)收敛；2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶【定义6-1】设由某方法确定的序列{xk}收敛于方程的根，如果存在正实数p，使得

(C为非零常数)由定义易见，一个方法的收敛速度实际就是绝对误差的收缩率，敛速的阶p越大，绝对误差缩减得越快，也就是该方法收敛得越快。2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶在定理2-2中，若

'(x)连续，且

'()0，则迭代格式xk+1=

(xk)必为线性收敛。因为由如果

'()=0，则收敛速度就不止是线性的了。进一步有2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶【定理2-2】设方程方程x=

(x)，正整数p2，若

(p)在根的某邻域内连续，且满足

(6.6)则{xk}p阶局部收敛。证明：∵

'()=0(<1)，∴xk局部收敛。设

(x)在处展开为2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶

(2.6)则{xk}p阶局部收敛。证明：由(2.6)知，所以即{xk}p阶局部收敛。2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶

【例2-5】设fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三阶局部收敛的。解：由定理2-2知，应有

'()=

"()=0，因为

'(x)=1–r1'(x)f(x)–r1(x)f'(x)–r2'(x)f2(x)–2r2(x)f(x)f'(x)而f()=0，f

'()≠0（单重零点）,令

'()=0有1–r1'()f

'()=0.取,则有

'()=02.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶

【例2-5】设fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三阶局部收敛的。解：此时有

'(x)=–r1'(x)f(x)–r2'(x)f

2(x)–2r2(x)f(x)f'(x)

"(x)=–r1"(x)f(x)–r1'(x)f'(x)–r2"(x)f

2(x)–4r2'(x)f(x)f'(x)–2r2(x)[f'(x)]2–2r2'(x)f(x)f

"(x)其中

2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶

【例2-5】设fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三阶局部收敛的。解：

"(x)=–r1"(x)f(x)–r1'(x)f'(x)–r2"(x)f

2(x)–4r2'(x)f

(x)f

'(x)–2r2(x)[f

'(x)]2–2r2'(x)f

(x)f

"(x)令

"(

)=0，有即取

，则有

"(

)=0。2.1非线性方程的迭代法2.1.2简单迭代法3.收敛阶

【例2-5】设fC2[a,b],

(x)=x–r1(x)f(x)–r2(x)f2(x)

为f的单重零点。试确定未知函数r1(x)、r2(x)，使迭代法xk+1=

(xk)至少是三阶局部收敛的。解：从而只要同时取和迭代法至少具有三阶局部收敛性。2.1非线性方程的迭代法2.1.3Newton迭代法及其变形1.Newton迭代法取

(x)=x+k(x)f(x),(k(x)0).则x=

(x)与f(x)=0同解.由

'(x)=1+k'(x)f(x)+k(x)f'(x).令

'()=0k()f'()=–1.若f'()0,则有即迭代法：称为牛顿迭代法。如何构造

(x)使迭代法收敛？令x=x+f(x)？不妥!2.1非线性方程的迭代法2.1.3Newton迭代法及其变形1.Newton迭代法几何意义：给定非线性方程f(x)=0的解

的近似值xn用过点Pn(xn,f(xn))的切线：y=f(xn)+(x-xn)f'(xn)近似表示曲线y=f(x)并将该切线与x轴的交点的横坐标xn+1作为

的新的近似值。2.1非线性方程的迭代法2.1.3Newton迭代法及其变形【例2-6】用牛顿法计算方程x3–x–1=0在x=1.5附近的根.解：f(x)=x3–x–1，f'(x)=3x2–1在x=1.5附近不为零.

k=0，1，2，…从x(0)=1.5出发，迭代3次即有6位有效数字.2.1非线性方程的迭代法2.1.3Newton迭代法及其变形【例2-7】用Newton法求非线性方程f(x)=xex–1=0在(0，1)内的根，取x(0)=0.5。解：因为f

'(x)=(1+x)ex，故其Newton迭代公式为k=0，1，2，…从x(0)=0.5出发，计算结果2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(1)若是f(x)的单重根：f()=0，f'()≠0因为一般不为0所以，在f'()0,f"(x)连续的条件下，牛顿迭代法至少是平方收敛的.<'()=0>.2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(2)若是f(x)的重根，即有f(x)=(x–)mg(x)其中g()≠0，m2因为f'(x)=m(x–)m-1g(x)+(x–)mg'(x)，记x=+h，则

2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(2)若是f(x)的重根，即有f(x)=(x–)mg(x)其中g()≠0，m2，记x=+h，则

2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(2)若是f(x)的重根，即有f(x)=(x–)mg(x)当m2时，

'(

)≠0，由|

'(

)|<1，知Newton迭代法一阶收敛。2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(3)若是f(x)的重根，即有f(x)=(x–)mg(x)(2)的改进：

取

，易知有

'(

)=0，所以，若事先知道的重数，则可改迭代公式为此时，迭代序列{xk}是二阶收敛的。2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(3)若是f(x)的重根，即有f(x)=(x–)mg(x)或令则是u(x)的单重零点。2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性(3)若是f(x)的重根，即有f(x)=(x–)mg(x)或令，则是u(x)的单重零点。应用Newton法于u(x)，有此时，迭代序列也是二阶收敛的

2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性【例2-8】是方程x4–4x2+4=0的二重根(1)采用Newdon法即

2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性【例6-8】是方程x4–4x2+4=0的二重根(2)采用(3.15)2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性【例2-8】是方程x4–4x2+4=0的二重根(3)采用，即2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性【例2-8】是方程x4–4x2+4=0的二重根分别采用2.1非线性方程的迭代法2.1.3Newton迭代法及其变形2.收敛性【例2-9】计算的近似值分析：是方程x3–7=0的根Newton迭代公式：2.1非线性方程的迭代法2.1.3Newton迭代法及其变形3.弦截法牛顿迭代计算导数f'(x)不方便，代入(2.10)中有2.1非线性方程的迭代法2.1.3Newton迭代法及其变形3.弦截法牛顿迭代计算导数f'(x)不方便，即

(2.11)称(2.11)为弦截法.2.1非线性