《Cht7非线性方程求根》由会员分享，可在线阅读，更多相关《Cht7非线性方程求根（84页珍藏版）》请在金锄头文库上搜索。
1、11 方程求根与二分法第7章 非线性方程求根一、引言非线性方程的分两类：2则可用搜索法求有根区间.x 1 0 1 2f(x)的符号 + +求根问题的三个方面：存在性，分布，精确化。31 方程求根的二分法 方程求根步骤 ：根的隔离确定根所在的区间a, b, 使在a, b内至少有方程 的一个根. 有根区间近似根的精确化已知根的一个近似值后, 构造某种算法, 将此近似值 精确化, 使其满足给定的精度要求.越小越好上一页 下一页 返回 4下面介绍方程求根的二分法在确立了有根区间a, b后, 需要逐步缩小有根区间.取a, b的中点x0=(a+b)/2,将区间一分为二.若 f(x0)=0,则x0 就是方程
2、的根,否则判别根 x* 在x0 的左 侧还是右侧.不论出现哪种情况, (a1, b1)均为新的有根区间, 它 的长度只有原有根区间长度的一半, 达到了压缩有根区 间的目的.上一页 下一页 返回 5重复以上过程, 继续进行二分, 可得一系列有根区间由于每个小区间都是有根区间, 所以这个点就是所 求方程的根.同时, 在每次二分时, 所求出的中点 形成一个无穷数列 这个数列必定收敛于 x*.上一页 下一页 返回 6abx0x1a1b2When to stop?x*b1上一页 下一页 返回 a27误差 分析：第1步产生的有误差第 k 步产生的 xk1 有误差对于给定的精度 ,可估计二分法所需的步数 k
3、 ： 算法简单; 对f (x) 要求不高(只要连续即可) ，收敛性总能得到保 证 无法求复数根及偶数重根（函数值的正负号相同）； 要计算很多次函数值，收敛慢二分法的误差估计式上一页 下一页 返回 8例1 用二分法求f (x)= x 3-x-1=0 在区间1, 1.5内的一个实根, 要求误差不超过0.005. 解： 由题可知x* (1, 1.5) ,要想解之得取 n6. 按二分法计算的过程见下表, x6 为所求之近似根 . 上一页 下一页 返回 9nanbnxnf (xn)备注 01.01.51.25- f(a0 )0 根据精度要求xn取 到小数点四位即可.11.251.51.375+ 21.2
4、51.3751.3125- 31.31251.3751.3438+ 41.31251.34381.3281+ 51.31251.32811.3203- 61.32031.32811.3242-上一页 下一页 返回 10逐步搜索法从区间a，b的左端点 a 出发, 按选定的步长 h 0 一步步向右搜索, 若：则区间a +j h, a +( j+1) h内必有根. 上一页 下一页 返回 于是可确定一个缩小了的有根区间a +j h, a +( j+1) h. 再对新的有根区间，取新的更小的预定步长，继续搜 索，直到有根区间的长度足够小。搜索过程也可从 b 开始, 这时应取步长 h 0；则牛顿迭代法产生
5、的序列 xk 收敛到f (x) 在 a, b 的唯一根。定理 有根根唯一产生的序列单调有界 ，保证收敛。保证f (x) 上凸或下 凸50 上一页 下一页 返回 与上一节例7相比，牛顿法的收敛速度快很多。 例9 51 上一页 下一页 返回 牛顿迭代法的流程图52注：注：牛顿迭代法的收敛性依赖于x0 的选取。x*x0x0x0上一页 下一页 返回 53 上一页 下一页 返回 1054二、牛顿法应用举例kxk 0 1 2 30.5 0.57102 0.56716 0.56714kxk 0 1 2 3 410 10.750000 10.723837 10.723805 10.72380555（4.5）这
6、种迭代公式对于任意初值 都是收敛的. 事实上，对（4.5）式施行配方手续，易知 以上两式相除得 据此反复递推有 （4.6）56记 整理（4.6）式，得 对任意 ，总有 ，故由上式推知，当 时 ，即迭代过程恒收敛. 57三、简化牛顿法与牛顿下山法图7-458（2） 牛顿下山法. 牛顿法收敛性依赖初值 的选取. 如果 偏离所求根较远，则牛顿法可能发散.例如，用牛顿法求方程 （4.8）在 附近的一个根 . 设取迭代初值 ，用牛顿法公式 （4.9）计算得 迭代3次得到的结果 有6位有效数字. 59但如果改用 作为迭代初值，则依牛顿法公式 （4.9）迭代一次得 这个结果反而比 更偏离了所求的根 . 为了
7、防止迭代发散，对迭代过程再附加一项要求，即 具有单调性： （4.10）满足这项要求的算法称下山法. 将牛顿法与下山法结合起来使用，即在下山法保证函 数值稳定下降的前提下，用牛顿法加快收敛速度. 将牛顿法的计算结果 60与前一步的近似值 适当加权平均作为新的改进值 （4.11）其中 称为下山因子，（4.11）即为 （4.12）(4.12)称为牛顿下山法. 选择下山因子时从 开始，逐次将 减半进行试 算，直到能使下降条件（4.10）成立为止. 若用此法解方程（4.8），当 时由（4.9）求得61，它不满足条件（4.10）.通过 逐次取半进行试算，当 时可求得. 此时有 ，而 显然 . 由 计算 时
8、 , 均能使条件（4.10） 成立. 计算结果如下 ： 即为 的近似. 一般情况只要能使条件（4.10）成立， 则可得到 ，从而使 收敛.62Q1: 若 ，牛顿迭代法是否仍收敛？设 x* 是 f 的 m 重零点, 则： 且 A1: 有局部收敛性，但仅为线性收敛.下面介绍计算重根的牛顿迭代法上一页 下一页 返回 63因此,求f(x)=0 之m重根x* 等价于求 (x)=0 的单根x* 。而对 (x)=0用牛顿迭代法求根则是平方收敛的,其迭代格式为 令 ，则 f 的重零点就是 的单零点。A2: 方法1：将求 f 的重零点转化为求另一函数的单零点。Q2: 如何加速求重根的收敛速度？上一页 下一页 返
9、回 64方法2：采用如下迭代格式可以证明它是求m重根 x*的具有平方收敛的迭代格式.如何确定根的重数 m ?则：上一页 下一页 返回 65例11 用牛顿迭代法求方程解：kxkk1/(1-k ) 00.9510.974427920.987058330.99348780.50902.036940.99673280.50472.019050.99835760.50072.002860.99919010.51252.0511上一页 下一页 返回 66 上一页 下一页 返回 67例12 用3种方法求解方程解：上一页 下一页 返回 都取x0=1.5，计算结果见下表：68方法（2）和方法（3）都是二阶方法，
10、x3都精确到了小数点后第9位，方法（1 ）即普通牛顿迭代法，解重根是一阶方法，要近30次迭代才能有相同的精度。xk方法（1）方法（2）方法（3） x01.51.51.5x11.458 333 3331.416 666 6671.411 764 706x21.436 607 1431.414 215 6861.414 211 438x31.425 497 6191.414 213 5621.414 213 562上一页 下一页 返回 69四、重根情形7071kxk(1)(2)(3) 0 1 2 3x0 x1 x2 x31.5 1.458333333 1.436607143 1.425497619
11、1.5 1.416666667 1.414215686 1.4142135621.5 1.411764706 1.414211438 1.414213562725 弦截法与抛物线法73图7-574弦截法与切线法（牛顿法）都是线性化方法，但两者 有本质的区别. 切线法在计算 时只用到前一步的值 ，而弦截法 （5.2），在求 时要用到前面两步的结果 ，因 此使用这种方法必须先给出两个开始值 .例10 用弦截法解方程 解 设取 作为 开始值，用弦截法求得的结果见表7-8， 比较例7牛顿法的计算结果可以看出， 弦截法的收敛速度也是相当快的. 实际上，弦截法具有超线性的收 敛性. 75767.5.2 抛
12、物线法 设已知方程 的三个近似根 ，以 这三点为节点构造二次插值多项式 ，并适当选取 的一个零点 作为新的近似根，这样确定的迭代过程称 抛物线法，亦称密勒（Mller）法. 在几何上，这种方法的基本思想是用抛物线 与 轴的交点 作为所求根 的近似位置（图7-6). 图7-677插值多项式 有两个零点： （5.3）式中 问题是该如何确定 ，假定在 三个近 似根中， 更接近所求的根 ，为了保证精度，选 （5.3） 中较接近 的一个值作为新的近似根 . 为此，只要取 根式前的符号与 的符号相同. 78例11 用抛物线法求解方程 解 设用表7-8的前三个值 作为开始值，计算得 故 代入（5.3）式求得
13、 79以上计算表明，抛物线法比弦截法收敛得更快. 在一定条件下可以证明，对于抛物线法，迭代误差有 下列渐近关系式 可见抛物线法也是超线性收敛的，其收敛的阶 , 收敛速度比弦截法更接近于牛顿法. 从（5.3）看到，即使 均为实数， 也 可以是复数，所以抛物线法适用于求多项式的实根和复根. 807.6 解非线性方程组的牛顿迭代法 考虑方程组 （6.1）其中 均为 的多元函数. 用向量记号记 , (6.1）就可写成 （6.2）当 ，且 中至少有一个是自变量81的非线性函数时，称方程组（6.1）为非线 性方程组. 非线性方程组求根问题是前面介绍的方程（即 ） 求根的直接推广，只要把前面介绍的单变量函数 看 成向量函数 则可将单变量方程求根方法推广到方程 组（6.2）. 若已给出方程（6.2）的一个近似根 ， 将函数 的分量 在 用多元函数泰 勒展开，并取其线性部分，则可表示为 令上式右端为零，得到线性方程组 （6.3）82其中 （6.4）称为 的雅可比(Jacobi)矩阵. 求解线性方程组（6.3），并记解为 ，则得 （6.5）这就是解非线性方程组（6.2）的牛顿迭代法. 83例12 求解方程组 给定初值 , 用牛顿法求解. 解 先求雅可比矩阵 由牛顿法（6.5）得 84作业: P290, 2,4.7作业: P291, 12,15.
