第3章 非线性方程的数值解法 3.1 方程求根与二分法 3.2 迭代法及其收敛性 3.3 迭代收敛的加速方法 3.4 牛顿法 3.5 弦截法与抛物线法 3.1.1 引言 本章主要讨论单变量非线性方程 f(x)=0 (1.1) 的求根问题，这里xR, f(x)Ca, b. 在科学与工程 计算中有大量方程求根问题，其中一类特殊的问题是 多项式方程 其中系数ai(i=0,1,n)为实数. 3.1 方程求根与二分法 n=1,2时方程的根是大家熟悉的，n=3,4时虽有求 根公式但比较复杂，可在数学手册中查到，但已不适 合数值计算，而n5时就不能用公式表示方程的根.因 此，通常对n3的多项式方程求根与一般连续函数方 程(1.1)一样都可采用迭代法求根. 方程f(x)=0的根 x*，又称为函数f(x)的零点，它使得 f(x*)=0，若f(x)可分解为 f(x)=(x-x*)mg(x)， 其中m为正整数，且g(x*)0. 当m=1时，则称x*为单 根，若m1称x*为(1.1)的m重根，或x*为函数f(x)的m 重零点. 若x*是f(x)的m重零点，则 注： 3.1.2 二分法 如果 f(x) 在区间a, b上连续, f(a)f(b)0, 则在a, b 内有方程的根. （ Bisection Method ） 二分法原理 二分法的实施过程 取a, b的中点 将区间一分为二. 若 f (x0)=0, 则x0就是方程的根, 否则判别根 x*在 x0 的左侧还是右侧. 若f(a) f(x0)0, 则x*(a, x0), 令 a1= a, b1=x0; 若f(x0) f(b)0, 则x*(x0 , b), 令 a1=x0, b1=b. 不论出现哪种情况, (a1, b1)均为新的有根区间, 它 的长度只有原有根区间长度的一半, 达到了压缩有根 区间的目的. 如此反复进行, 即可的一系列有根区间套 由于每一区间都是前一区间的一半，因此区间an , bn的长度为 若每次二分时所取区间中点都不是根，则上述过程将 无限进行下去. 当 n 时，区间必将最终收缩为一 点x* ，显然 x* 就是所求的根. 若取区间an , bn的中点 作为x*的近似值，则有下述误差估计式误差估计式 只要 n 足够大, (即区间二分次数足够多)，误差就可 足够小. 二分法的误差估计 例1 用二分法求方程 f(x)=x3-x-1=0在(1, 1.5)的实根, 要求误差不超过0.005. 解 由题设条件，即： 则要 |x*-xn|0.005 由此解得 取 n=6, 按二分法计算过程见 下表, x6 = 1.3242 为所求之近似根. n an bn xn f(xn)说明 0 1 2 3 4 5 6 1.0 1.25 1.25 1.3125 1.3125 1.3125 1.3203 1.5 1.5 1.375 1.375 1.3438 1.3281 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 - + - + + - - (1) f(a)0 (2) 根据精 度要求， 取到小数 点后四位 即可. 二分法的优点是算法简单，且总是收敛的，缺点 是收敛的太慢，故一般不单独将其用于求根，只是用 其为根求得一个较好的近似值. 二分法的计算步骤: 步骤1 准备 计算函数f(x)在区间a, b端点处的值 f(a), f(b). 若f(a)f(a+b)/2)0, 则以(a+b)/2代替b ，否则以 (a+b)/2代替a. 步骤2 二分 计算函数f(x)在区间中点(a+b)/2处的 值f(a+b)/2). 步骤3 判断 若f(a+b)/2)=0，则(a+b)/2即是根， 计算过程结束，否则检验. 反复执行步骤2和步骤3，直到区间a, b长度小于 允许误差，此时中点(a+b)/2即为所求近似根. 3.2 迭代法及其收敛性 3.2.1 不动点迭代法 将方程 f(x)=0 改写为等价方程形式 x=(x). (2.1) 若要求 x* 满足 f(x*)=0，则 x*=(x*)；反之亦然，称 x* 为函数(x)的一个不动点不动点. 求 f(x) 的零点零点就等于求(x) 的不动点不动点，选择一个初始近似值 x0，将它代入(2.1)右 端，即可求得 x1=(x0). 可以如此反复迭代计算 xk+1=(xk) (k=0,1,2,). (2.2) (x)称为迭代函数. 如果对任何x0a, b，由(2.2)得 到的序列xk有极限 则称迭代方程(2.2)收敛. 且x*=(x*)为(x)的不动点， 故称(2.2)为不动点迭代法. 当(x)连续时，显然x*就是方程 x=(x)之根(不动点). 于是可以从数列xk中求得满足精度要求的近似根. 这种求根方法称为不动点迭代法, 称为迭代格式, (x)称为迭代函数, x0 称为迭代初值, 数列xk称为迭代序列. 如果迭代序列收敛, 则称迭代 格式收敛,否则称为发散. 分别按以上三种形式建立迭代公式，并取x0=1进行 迭代计算，结果如下： 解 对方程进行如下三种变形： 例2 用迭代法求方程x4+2x2-x-3=0 在区间1, 1.2内 的实根. 准确根 x * = 1.124123029, 可见迭代公式不同, 收敛情 况也不同. 第二种公式比第一种公式收敛快得多, 而 第三种公式不收敛. x y o y=(x) y=x 解x=(x) 求 y=x 与y=(x)的 交点的横坐标 x* x0 (x0 , x1) (x1 , x2) (x1 , x1) x1 x2 迭代法的几何意义 x y y = x x y y = x x y y = x x y y = x x*x* x*x* y=(x) y=(x) y=(x) y=(x) x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 注：迭代法的研究涉及四个问题： (1)迭代公式的选取； (2)迭代公式收敛性的判定； (3)在收敛情况下，如何比较收敛速度 ； (4)迭代停止的条件。 3.2.2 不动点的存在性与迭代法的收敛性 首先考察(x)在a, b上不动点的存在唯一性. 定理定理1 1 设(x)Ca, b满足以下两个条件： 1 对任意xa, b有a(x)b. 2 存在正数La及(b)0, f(b)=(b)-b0, 由连续函数性质可知存在 x*(a, b) 使 f(x*)=0，即 x*=(x*)，x*即为(x)的不动点. 再证不动点的唯一性唯一性. 设x1*, x2*a, b都是(x) 的不动点，则由(2.4)得 引出矛盾，故(x)的不动点只能是唯一的. 证毕证毕. . 定理定理2 2 设(x)Ca, b满足定理1中的两个条件 ，则对任意x0a, b，由(2.2)得到的迭代序列xk收 敛到不动点x*，并有误差估计式误差估计式 证明 设x*a, b是(x)在a, b上的唯一不动点, 由条件1，可知xka, b，再由(2.4)得 因01），并且 则该迭代过程在 x* 的邻近是 p 阶收敛的. 证明证明 由于(x*)=0，根据定理3立即可以断定迭 代过程xk+1=(xk)具有局部收敛性. 再将(xk)在根x*处做泰勒展开, 利用条件(2.8), 则有 注意到(xk)=xk+1，(x*)= x*，由上式得 因此对迭代误差，令k时有 这表明迭代过程xk+1=(xk)确实为 p 阶收敛. 证毕. 注：注：上述定理告诉我们，迭代过程的收敛速度依赖于 迭代函数(x)的选取. 如果xa, b但 (x)0 时，则 该迭代过程只可能是线性收敛. 的三阶方法. 假设 x0 充分靠近 x*, 求 提示： 设(x) =x(x2+3a)/(3x2+a)，则有(a)= 例例4 4 证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求 构造迭代公式 xk+1=(xk)，计算 的三阶方法，即 因此迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求 所以