1、第二章 非线性方程的数值解法考察下列方程 f(x)=0f(x)可以是代数多项式，也可以是超越函数。求解精确解一般不可能，只能寻求数值解。,2.1 二分法 若函数f(x)在区间a,b上连续，且 f(a)f(b)0则方程 f(x)=0在区间a,b上至少有一个实数根。,二分过程：（假定有根区间仅一个实数根x*）如果 f(a)f(a+b)/2)0，则在区间f(a),f(a+b)/2 上有实数根。如果 f(a+b)/2)f(b)0，只要 便有此时xk为满足精度要求的近似解。,表2.1 x6=1.324 x* |x*-x6| 0.0039 0.005,例2.1 用二分法求方程f(x)=x3-x-1=0在区
2、间1,1.5内的一个实根，要求误差不超过0.005。,解：由公式（2.3）估计二分的次数于是，只要二分6次即可达到精度要求，二分过程见表2.1,2.2 Jacobi（简单）迭代法1、Jacobi迭代法的基本原理 考察方程 f(x)=0 x=(x) 在根x*的附近取一点x0作为x*的预测值，有 x1=(x0)重复上述步骤，有如下迭代公式 xk+1=(xk) (k=0,1,2,)其中(x)为迭代函数，x0,x1,xk,为迭代序列。,等价形式,如果迭代序列xk的极限存在，即 x*= xk则迭代过程收敛。如果迭代序列xk的极限不存在，迭代过程发散。,(a)迭代收敛,(b)迭代发散,例2.2 求方程f(
3、x)=x3-x-1=0在x=1.5附近的根x*的近似值。解：将方程f(x)=0改写为如下等价形式 x=(x+1)(1/3)迭代公式为 xk+1=(xk+1)(1/3) (k=0,1,2,)取x0=1.5，计算过程用6位有效数字表示，迭代结果见表2.2 表2.2,如果将原方程改写为如下等价形式 x=x3-1则有迭代公式 xk+1=(xk)3-1迭代初值x0=1.5，则有 x1=2.357,x2=12.39,迭代过程发散。,2、Jacobi迭代过程的收敛性定理2.1 如果迭代函数(x)满足如下条件（1）对任意x a,b，有 a (x) b（2）存在正数L1，使对任意x a,b，有 |(x)|L1则
4、迭代过程xk+1= (xk) 对任意x0 a,b均收敛于方程x=(x)的根x*，且有如下误差事后估计式,证：由微分中值定理 |x*-xk| =|(x*)-(xk-1)|=|()(x*-xk-1)| L|x*-xk-1|式中为x*与xk-1之间的一点。 据此反复递推 |x*-xk|L|x*-xk-1|L2|x*-xk-2|Lk|x*-x0| 显然，当k时，xkx*,迭代序列xk收敛于x*。为确保收敛，全体迭代值xk应在a,b上取值，为此对任意x a,b ，均有(x) a,b。 对任意正整数p，有|xk+p-xk|xk+p-xk+p-1|+|xk+p-1-xk+p-2|+ + |xk+1-xk|
5、=(Lp-1+Lp-2+ +1)|xk+1-xk|固定k并令p,有,定义2.1 称迭代过程在根x*的附近具有局部收敛性，指的是如果存在邻域:|x - x*|， 迭代过程xk+1=(xk)对任意初值x0 收敛。,由此可见，只要前后两次迭代值得差值足够小，就可使近似值xk+1达到任意精度。一般情形下，用 |xk+1 - xk|来控制迭代精度。,定理2.2 设(x)在方程x=(x)根的附近有连续的一阶导数，且 |(x)|1则迭代过程xk+1= (xk)具有局部收敛性。例2.3 求方程 x = e-x在x = 0.5附近的一个根，要求精度=10-5。解：通过搜索方法，得有根区间0.5,0.6，且有 (
6、x) =exp(-0.5)1迭代公式xk+1=e-xk对迭代初值x0=0.5收敛。,经18次迭代后，x18=0.56714，满足所规定的精度要求。2.3 Aitken加速迭代法 设xk是第k次迭代近似值，由迭代公式得第k+1次迭代值，记作 k+1，即 k+1=(xk)由微分中值定理，有 - k+1=,()( -xk)L ( -xk)记 k+1=( k+1)且有 - x k+1=,()( - k+1) L ( - k+1),于是 k+1 x k+1 xk k+1 整理后，有如下事后估计式 k+1 k+1 k+1 2 k+12 k+1+ 由此，得下列Aitken迭代加速公式,校正 k+1=(xk)
7、,再校正 k+1=( k+1),改进 xk+1= k+1 - k+1 k+1 2 k+12 k+1+ ,例2.4 用Aitken方法求解方程 f(x)=x3-x-1=0在x=1.5附近的根。解：以如下迭代公式 xk+1=(xk)3-1为基础，构造Aitken迭代加速公式 k+1=(xk)31 k+1=( k+1)3-1 xk+1 = k+1 - k+1 k+1 2 k+12 k+1+ 初值x0=1.5,经5次迭代，得x5=1.32472,例2.5 证明求方程 2 1=0在 1,2 上有一个实根，用二分法求这个根，要求 10 3 ，若要求 10 6 ，需二分区间 1,2 多少次？ 1.3253(
8、9),19例2.6 设方程123+2cos=0的迭代格式为 +1 =4+ 2 3 cos （1）证明对 0 ，均有 lim = ；（2）取 0 =4，求此迭代格式的近似值，精度为 = 10 3 ，列出各迭代值。 3.3475(3),2.4 Newton迭代法1、Newton迭代法的构造思路 设方程f(x)=0的根 ，xk为方程根的近似值 将函数f(x)在xk处做一阶Taylor展开 用 近似代替函数f(x) 于是 f(x)=0 求解 ，得,由此得Newton迭代格式 Newton迭代法的几何描述 y 切线法 xk+2 xk+1 xk x,例2.7 用Newton法求方程 x = e-x在x =
9、 0.5附近的一个根。解：将x = e-x改为x ex-1=0 令 f(x)= x ex-1 Newton迭代公式为 取x0= 0.5 ，利用上述迭代公式，得 x1= 0.57102 ，x2= 0.56716 ， x3= 0.56714,例2.8 用Newton法求 115 ，精度= 10 6 解：将此问题转化为下列二次方程 x 2 115=0 Newton迭代格式为 xk+1 = 1 2 (xk+ 115 xk ) 初值x0= 10 ，4次迭代得所要求的近似值 115 10.723805,2、Newton迭代法的收敛性定义2.2 设迭代序列 收敛于 ，误差为 = 如果有 +1 0 称迭代序列
10、是阶收敛的， 特别地 （1） =1，0 +1 下山条件具体方法为松弛法，记 +1 = , 取 +1 和 的加权平均作为迭代改进值 +1 ，即 +1 = 1 + +1 于是，得Newton下山法迭代公式 +1 = , 下山因子,下山因子的选取从=1开始，判断 +1 是否成立 成立，则用Newton迭代法进行迭代 不成立 ，则下山因子依次在下述集合 1 2 ， 1 4 ，, 1 2 , 中选取，直至满足 +1 。在例2.8中，仍取初值 0 =0.6，经过试探，找到= 1 32 ，得到第一步 1 =1.140625，比 0 更接近于根x*，从而保证迭代过程收敛。,4、有重根情形的Newton迭代法
11、设 为 =0的重根，即有 = ， ( )0， 2 Newton迭代法的迭代函数 = , ,()= 1 1 + 2, + 2 , 2 1+ , 2 , =1 1 0, 1此时，Newton迭代法收敛，但仅为线性收敛。方案一 将迭代函数 改造为 = , 且有, =0 于是下述迭代公式 +1 = , 至少具有是二阶收敛的。缺点：事先知道 的重数，一般不可能。,方案二 令 = , ，且 = 则 = 1 + , = + , 由此可见 是 =0的单根 =0的重根 =0的单根 取迭代函数 = , = , , 2 , ,从而构造迭代法 +1 = , , 2 , 例2.12 方程 4 4 2 +4=0的根 =
12、2 是二重根。 (1) +1 = 22 4 Newton迭代法 (2) +1 = 22 2 方案一 (3) +1 = 22 2+2 方案二,初值 0 =1.5方法（2）与（3）二阶方法，迭代第三步时精度到 10 9 ，方法（1）为线性收敛，要到达相同精度需迭代30次。,5、非线性方程组的Newton迭代法 设有非线性方程组 1 1 , 2 , =0 2 1 , 2 , =0 1 , 2 , =0 依次将上述个方程在点 处做一阶Taylor展开，得 1 , 2 , + ,记作 + , () () 这里 = 1 , 2 , 令 1 + 1 , () () =0 2 + 2 , () () =0 + , () () =0 由此得非线性方程组的Newton迭代公式,例2.13 用Newton迭代法求解下列方程组 1 1 , 2 = 1 210 1 + 2 2+8=0 2 1 , 2 = 1 2 2+ 1 10 2 +8=0 建立迭代公式。 例2.14 给定函数 ，设对一切，, 存在，而且0, 。证明对0 2 的任意常数，迭代法 +1 = 均收敛于方程 =0的根。,
