非线性方程求根.ppt

非线性方程求根,汪 待 发 电话： 15801360553 信箱： 办公: 逸夫楼316房间,1,2,第一节 方程求根与二分法 第二节 迭代法及其收敛性 第三节 牛顿法 第四节 弦截法,主 要 内 容,第一节 方程求根与二分法,本章主要讨论单变量非线性方程 的求根或求f(x)零点问题，在这里 在科学与工程计算中有大量的方程求根问题，其中一类特殊的问题是多项式方程: 的求根问题。方程f(x)=0的根或者零点分为： 当n=1，n=2时方程的根较容易求解，n=3,4时虽有求积公式，但比较,第一节 方程求根与二分法,复杂，已不适合数值计算，更当n大于等于5时就不能用公式表示方程的根。因此，通常对 的多项式方程求根与一般连续函数方程一样都可以采用迭代法求根。所谓迭代法 -要求先给出根的一个近似，若 则根据连续函数的性质可知： 若（a,b）内至少有一个实根，此时称a,b为方程（1.1）的有根区间。,问题(1): 能否不用求根公式求解下列方程的根 1）lgx=3-x；2）x2-2x-1=0； 3）x3+3x-1=0.,第一节 方程求根与二分法,方法一：画图法 1）建立坐标系，画曲线f(x)； 2）观察曲线f(x)与x轴相交的交点； 3）将其中一个交点进行局部放大； 4）该交点的横坐标值就是方程的根 方法二：建立有根区间，再对区间进行搜索计算 例：求方程 的一个正的近似解 .（精确到0.1）,第一节 方程求根与二分法,问题（2）: 能否简述上述求方程近似解的过程?,第一节 方程求根与二分法,二分法 二分法（bisection method）：象上面这种求方程近似解的方法称为二分法，它是求一元方程近似解的常用方法。,第一节 方程求根与二分法,二分法算法描述： 若 反复执行步骤（2）及步骤（3），直到区间 即为所求的近似根。,（3）若,（1）若,（2）若,由,则,由,则,则,即为所求根否则，,长度小于容许误差，此时的区间中点,第一节 方程求根与二分法,这样不断将区间分半,得到一系列区间,但实际计算时只需满足：,时即可终止计算。,第一节 方程求根与二分法,例1 用二分法求 在(1,2)内的根 ，要求绝对误差不超过 解： 有根区间 中点 f(1)=-50 (1,2) f(1.5)0 (1,1.5) f(1.25)0 (1.25,1.375) f(1.313)0 (1.360,1.368),第一节 方程求根与二分法,若取近似根 则有 先验估计式 算法的优点：算法简单且总收敛。 算法的缺点：收敛慢.不易求重根.,第二节 迭代法,简单迭代法是一种简单而又直观的逐次逼近方法。 其基本思想是： 首先将方程f(x)=0化为等价的迭代形式的方程 若要求 于是称 为函数 的一个不动点 求f(x)=0的零点就等价于求 的不动点,第二节 迭代法,计算出序列 为迭代函数，如果对任意的初值 有 ， 则称迭代法收敛。这表明 就是方程（1.2）的不动点，也即是原方程f(x)=0的根 。 上述迭代法称为不动点迭代法 在此方法中，我们称 为迭代函数，迭代公式（1.3）成为迭代格式。 由此产生的序列 称为迭代序列。 由于迭代函数是一元函数，这种迭代方法属于单点迭代，又成为简单迭代, 几何意义见下图,第二节 迭代法,例2 用迭代法求方程 在区间1,2内的一个实数。 解：首先将方程等价改写为如下：,第二节 迭代法,于是可建立如下的迭代公式： 不妨取 =1.5为1,2上任一个点，于是我们可以得到迭代序列 实际计算时如果保留6 位有效数字，则由计算结果得 于是 可以认为近似解 计算结果见下表,第二节 迭代法,第二节 迭代法,对上述同一问题改写为另一种等价形式： 从而可建立迭代格式如下： 迭代初值仍取 继续迭代下去计算结果会越来越大，不可能趋于某个极限，这种不收敛的迭代过程称为发散。,第二节 迭代法,于是提出问题： 原方程 可以化为多种等价的 问什么条件下的 可以保证迭代过程收敛？ 以及怎样估计近似解的误差呢？ 定理2.1： 若迭代法中的迭代函数 满足下面两个条件 （1）对任意出近似值 ，迭代法 产生的迭代序列,第二节 迭代法,都收敛于方程 在区间a,b上的唯一实根 。 证明：首先证明不动点的存在性。 （a）先说明方程 在区间a,b上有根。 令 有连续函数中值定理知，存在 使得 （b）再证明唯一性 即说明方程 在区间a,b上有唯一根。设 都是方程 在区间a,b上的根，由条件（2）有,第二节 迭代法,所以只能有 即区间a,b内只能有唯一的实根。 定理2.2 设 Ca,b满足2.1的两个条件，则对任意 ，由 得到的迭代序列 收敛到 的不动点 ，并有误差估计式：,第二节 迭代法,证明： 设 是在a,b上的唯一不动点，由条件(1)，可知 也即 再由条件(2)可得 由于0<L<1，所以有 时， 故迭代序列 收敛到 ，从而结论(1)成立。 由不等式性质及 有以下估计式：,第二节 迭代法,类似于前面的推导过程，有： 所以结论成立,第二节 迭代法,上述误差估计式在原则上可以用来确定迭代次数，但由于含有信息 L ，不便于实际计算。故由 只要相邻两次计算结果的偏差 足够 小就可以保证近似值有足够的精度。,问题： 由定理2.1知道了不动点迭代收敛的条件，由定理2.2知道了解的误差估计式，那么收敛的速度又如何确定呢？,第二节 迭代法,定义： 设迭代过程 收敛于方程 的根 ， 如果迭代误差 ，当 时，有下式成立 则称该迭代过程是p阶收敛。 对于上述迭代过程，若另有 在所求根 的邻域连续，并且,第二节 迭代法,有下式成立： 也称迭代过程在 的邻近是p阶收敛的。,第三节 Newton 迭代法,Newton 迭代法,1.迭代公式建立 在 点Taylor展开 取前两项 令 解出 记为 ，则 上式称为Newton 迭代法,第三节 Newton 迭代法,2.Newton 迭代法的几何意义 过点 处的切线 与y=0求交点，解出 则,第三节 Newton 迭代法,Newton 迭代法收敛定理1 设 在a,b有根，且 在a,b （1） 连续，且分别不变号； （2）取初值 使 则 Newton 迭代法（3.1）产生的数列 收敛到根。 证：以 为例证明（其他情况类似） 将 在 处Taloyer展开,第三节 Newton 迭代法,说明数列 有下界 又 故 单调递减 收敛 。 设 例3 用Newton 迭代法求 解：设 取 ，则由（3.1）,第三节 Newton 迭代法,迭代收敛定理2 （1）设 收敛到 的根 。 若 则 线性收敛 （2）设定理1的条件成立 则Newton 迭代法求 单根的 （即 ）至少二阶收敛。 证：,第三节 Newton 迭代法,（2）由定理1的证明有： 所以，此时Newton 迭代法至少二阶收敛。 根据收敛速度的定义，这时牛顿法至少是二阶收敛，即牛顿法在单根附近至少是二阶收敛的，而在重根附近，牛顿法只有线性收敛速度.,第三节 Newton 迭代法,牛顿法优点： 收敛很快，算法简单，是常用的快速收敛法； 牛顿法缺点： (1)对重根收敛较慢 (2)对初值x0要求较严，要求x0相当接近真解x*。它常与其他方法联用，用其他方法确定初值x0 ，再用牛顿法提高精度。,第四节 弦截法,牛顿法的突出优点：收敛速度快 缺点：若计算 较困难，则用牛顿法不方便。 为避免计算 ，可用差商 近似代替 于是得弦截法的迭代格式： 上式有明显的几何意义： 设曲线 上横坐标为x0和xk的点分别为P0和Pk，则差商 表示弦 的斜率，弦 的方程为,第四节 弦截法,可见，前述迭代格式求得的xk+1实际上是 弦 与与x轴交点的横坐标（令y=0解出x 即可） 因而此法可形象地称为弦截法。 弦截法的收敛速度比牛顿法慢得多。为了 加快收敛速度，我们改用差商 来代替牛顿迭代格式中的 。于是得到 快速弦截法迭代格式：,第四节 弦截法,