方程求根(计算方法).ppt

割线法不需要计算导数，需要两个初始点。牛顿法每次需要两个值f(xk),f’(xk)，割线法每次迭代只需计算一个函数值，因此实际上割线法的计算效率有时比牛顿法更高。牛顿法和割线法必须给出根附近的初始点。 小结 迭代收敛阶的概念 小结 【思考题】欲求f(x)=0的根，对于下面的每种情况，分别有哪些相应的方法数值方法可以使用？ (1)仅仅已知f(x)的求解方法。 (2)已知f(x)和f’(x)的求解方法。 设方程f(x)=0有近似根xk，将函数f(x)在xk处一阶泰勒展开 §2.4 牛顿法 于是方程线性化为 这个线性化方程的根为 按照迭代法，其迭代函数为 §2.4 牛顿法 牛顿法的收敛速度 牛顿法可以看成迭代公式 如果x*是f(x)=0的一个单根，则f(x*)=0， 于是由上节定理知牛顿法有二阶收敛速度。 §2.4 牛顿法 【注记】可以证明对于重根情形，牛顿法是1阶局部收敛。 迭代收敛判据有： §2.5 牛顿法下山法 ①第k次迭代xk充分接近于方程根x*，②|f(xk)|充分小，接近于零。这两个判据不等价，第一个能严格保证收敛，第二个并不能。虽然第一个判据很严格，但是实现起来有困难，因为x*未知，第二个判据尽管不严格，但易于实现。 后两个判据在实际中采用较多。 §2.5 牛顿法下山法 牛顿法算法 §2.4 牛顿法 以及最大迭代次数N。 已知函数f(x)及f’(x),给定x0, §2.4 牛顿法 §2.4 牛顿法 例2.7 用牛顿法求方程 在x=0.5附近的根。 §2.4 牛顿法 解：把方程写成 于是 取x0=0.5，得到 §2.4 牛顿法 k 0 1 2 3 xk 0.5 0.57102 0.56716 0.56714 用简单迭代法 得 k 0 1 2 3 … 18 xk 0.5 0.60653 0.54524 0.57970 … 0.56714 §2.4 牛顿法 例2.8 用牛顿法求Leonardo方程 的根,设x0=2，要求 解： §2.4 牛顿法 k 0 1 … 4 5 xk 2 1.6 … 1.368808109 1.368808108 故 【注】Leonardo在1225年研究了该方程，并得到x=1.368808107的结果，此时f(x)=-0.000000009，这在当时是非常重要的结果，但无人知道他是如何得到的。 例2.9 用牛顿法求 的近似值，精度 。 §2.4 牛顿法 解：化为求x2-115=0的正根，牛顿迭代公式为 取初值x0=10，经过4次迭代，得x*=10.723805 【思考题 】对于牛顿迭代公式，证明 §2.4 牛顿法 §2.5 牛顿下山法 第二章 方程求根 牛顿法的收敛性和初始迭代值有关，如果初始迭代值离方程根较近，则迭代收敛性可以保证；如果初始值距离方程根较远，则收敛过程可能发散。但是通常情况下很难给出一个离根较近的初始值，因为根无法预先知道。 §2.5 牛顿法下山法 我们发现这样一个事实：通常在根附近|f(x)|是单调下降的，即越接近根， |f(x)|越小，所以|f(xk)||f(xk+1)| 。于是我们把这个条件作为一个约束引入到迭代方程。满足这个约束条件的算法叫下山法。 §2.5 牛顿法下山法 具体作法：先得到牛顿法结果 把 与xk作加权平均得到： 叫下山因子, 时即为牛顿法。 §2.5 牛顿法下山法 可以通过选取 值使得|f(xk)||f(xk+1)|。通常先令 开始，若上式不成立则 减半，直到上式成立 如果 已经很小，上式仍不成立，则下山失败。 意味着新的 若不满足下山条件，则加大上一步结果的权重。 §2.5 牛顿法下山法 例2.10 用牛顿下山法求方程f(x)=x3-x-1=0在1.5附近的根，精确到7位有效数字，取x0=0.6。 §2.5 牛顿法下山法 解：应用牛顿下山公式 §2.5 牛顿法下山法 k xk f(xk) 0 1 0.6 -1.384000 1 1 17.899980 5716.4210 1/2 9.249990 781.20070 … … … 1/32 1.140624 -0.656644 2 1 1.366814 0.186641 … … … … 6 1 1.324718 0.000000 §2.6 割线法 第二章 方程求根 在牛顿法中， ，需要计算f(x)的导数f’(x)，有时不易求