计算方法-4方程求根的迭代法.ppt

寻找第五章方程根的数值解法，1二分法2迭代法3切线法(牛顿法)4弦切割法5加速度迭代法方程；1二分法，我们已经习惯了解一阶方程、一阶二次方程和一些特殊类型的高阶代数方程或非线性方程的方法。这些方法都是代数解法，古老的根是方程的正确根。但是，在很多实际问题上出现的方程，例如代数方程x3-x-1=0或超越方程，是简单的形状，但找到正确的根并不容易。为此，方程只能找到一定精度的近似根。一圆非线性方程式可以是f (x)=0 (5-1)、方程式(5-1)，包括实数、腹肌或腹肌。本章主要讨论实际根的数值计算。方程式布线的数值计算大致可以三个步骤确定布线的存在，即： (1)。(2)确定根的分布范围，每个根被隔离为区间。(3)根的精确，即根的初始近似值，以某种方式逐渐精确，直到满足前提条件的精度。将F(x)设定为区段定义的连续函数，方程式(5-1)具有实际布线。方程(5-1)的根通常分布范围更复杂，但将函数f(x)的域划分为仅包含一个实际根的多个地块并不难。例如，考虑图5.1中所示的x2-2x-1=0方程式，此方程式的负实际根在-1和0之间，而另一个正实际根在2和3之间。图5.1，这样，始终可以假定方程(5-1) (a，b)中有单根x*。如果F (a) f (b)小于0，则根据连续函数的中间值定理，可以在(a，b)中使用点x0作为方程的初始近似根。例如，方程式f(x)=x3-x-1=0表示f (1) 0和f(x)在宗地(1，1.5)中单调连续，因此(1，1建议使用端点或地块的点值作为管线的初始近似值。如果函数f(x)在间距a，b中单调，并且f (a) f (b)小于0，则方程式(5-1)在间距(a，b)中只有一个实际根x。下面介绍根段(a，b)内二分法的基本思想。如果F(a)和f(x0)，f (a) f (x0)为0，则根x(a，x0)，a1=a，b1=x0，否则a1=.(ak，bk)，其中a0=a，b0=b显然是，(5)，根x的近似值，取每两分钟后根间距(ak，bk)的中点，然后取近似根序列x0，x1，x2，xk、此序列是根x为极限(5-3)，对于预指定精度，如果存在，则结果xk是方程式(5-1)满足预指定精度的近似根。也就是说，通过形式(5-2)和(5-3)，误差估计为(5-3)，二分法具有简单易操作的优点。计算步骤是框图，如图5.3所示。一，一。计算步骤输入具有根部分的端点a、b和预定精度；(a b)/2x；如果f (a) f (x)小于0，则为XB，steering；否则，xa，转向。B- a 的情况下，输出方程满足精度的根x，结束。否则转向。方块图范例1寻找方程式f(x)=x3-x-1=0在间隙(1，1.5)内的布线。必须以4个小数点计算，直到10-2。其中a=1，b=1.5宗地(1，1.5)的中点，图5.3，f (1.25)小于0，因此a1=1.25，b1=1.5为新根宗地(1.25，1.5)余度，表5-1，2迭代法的基本思想是，首先以等价形式替换方程(5-1)，以等价形式构造相应的迭代公式，迭代方法是数值计算中的重要连续逼近方法。例如，寻找方程式x3-x-1=0，并寻找x=1.5附近的根(由6位有效数字计算)。首先，可以用等价形式复盖原始方程，用初始近似根x0=1.5赋值(5-5)的右端，x1和x0的差值很大。相反，如果使用x1作为近似根参数(5-5)的右端，则对于表5-2，对于正则表达式(5-1)，首先将其转换为以下等效形式x=g (x) (5-7)，然后按(5-7)给出迭代公式的初始按一下重复公式(5-8)时，x0、x1、x2、xk，如果此序列xk有限制，迭代公式(5-8)将收敛。此系列的极限是原始方程式(5-1)的根。迭代法的基本思想很简单，但效果并不总是令人满意的。在上例中，通过表达式创建的x=x3-1 (5-9)迭代公式xk1=x3k-1，k=0，1，2，如果初始值x0=1.5仍然存在，则迭代结果为x1=2.375，目标x2=12.3976，清理方程式x=g(x)在(a，b)中有根x，g(x)在Lipschitz(因为所有正整数p都有(5-11)，x是方程式x=g(x)的根，x=g(x)也是方程式的根(5-11)，所以由于Lipschitz条件为q 1，所以存在自下而上矛盾()迭代公式xk1=g (xk)，k=0，1，2，lipschz条件，(5-12)，由5-12使用，(5-13) q 1，k，qk0，即初始值x0迭代公式的收敛。利用李普西茨条件，迭代方法的几何意义：将方程(5-1)的求根的问题转化为数列xn的极限，实际上是将求根问题转化为求流，图5.4，迭代过程(5-7)当Q1从p1(x1，x2)(平行于y轴的直线相交曲线y=g(x)中连接时，点列P0 (x0，x1)、P1 (x1，x2)、p2 (x2，x3)、在这种情况下，迭代方法参照图5.4(a)收敛。否则，迭代方法将发散。请参见图5.4(b)。2点： 确认g(x)是否符合这个条件通常是困难的，如果g(x)很小，就用足够的条件代替。其中q 1是非常重要的条件，否则无法保证迭代收敛。对于收敛迭代过程，误差估计(5-11)显示了迭代值的偏差| xk-xk-1 |相当小可保证迭代误差| x-xk |足够小。因此，为了控制迭代过程的结束，在特定计算中常用的条件| xk-1 | (5-15)。迭代方法的突出优点是算法的逻辑结构简单，计算时中间结果扰动时不影响计算结果。此计算为： (1)，决定方程式f(x)=0的对应格式x=g(x)，并且g(x)必须满足lipschts条件(或| g | 880q 1)，以收敛迭代过程使用公式Xk1=g (xk)、k=0、1、2等选择初始值x0。3 | xk 1-xk | 时停止计算，x-xk 1。范例2寻找x=0.5附近的x=e-x方程式。如果按5位小数计算，则计算精度必须为=10-3。f(x)=x-e-x-x-x由于f (0.5) 0 (0.5)，因此x=0.5 (5，0.6)，x=0.5最后，在将方程式(5-1)设为等价物(5-7)时，提供g(x)的说明，最常用的形式可以写成x=x (x) f (x) (5-16)。其中 (x)是任意正函数或负函数。因此，g (x)=x (x) f (x) (5-17)根据表达式(5-17)选择(x)，以使迭代公式(5-8)满足收敛条件。特别是使用(5-18)时，由表达式(5-16)构造的迭代公式是下面介绍的切线迭代公式。使用(5-19)可以得到代码截断迭代公式。，3切线方法(牛顿方法)5734-图5.6中，曲线y=f(x)和x轴的交点x是方程(5-1)的根，这是求解方程(5-1)的重要迭代方法。图5.6，与x轴的交点为xk 1，点xk 1满足切线方程。也就是说，可以得到切线迭代公式(或Newton迭代公式)，(5-20)，切线方法是非线性方程的线性化方法。给出了： 初始近似根x0和精度。计算 x1-x0 | ，转向；否则，x1厘米x0，转向。输出以满足精度的根x1结束。切线方法的计算方块图如图5.7所示。图5.7，范例3使用切线方法寻找方程式xex-1=0的根(计算为5位小数)。如果取-x0=0.5，则重复结果如表5-4所示。表5-4，切线迭代公式(5-20)是(5-1)的等效表达式，因此，如果表达式(5-21)的单个根，则在点附近收敛切线方法，收敛速度更快。4弦截断法根据切线迭代公式收敛条件(5-21)，迭代简单收敛，但有时需要计算导出f(x)，因此很麻烦。本节介绍的代码截断法避免了切线方法的不足。点xk 1满足该弦的方程式，将弦切割重复公式(5-23)、图5.8、表5-5、范例4使用弦切割方程式xex-1=0，将x0=0.5、x1=0.6解析为初始近似根。因此，f(x)=x-e-x=0使用公式(5-23)得出弦剪切迭代公式，如表5-5所示。与切线方法的计算相比，可以看出弦方法的收敛速度也比较快。Xk 1由已知方程(5-1)的近似根Xk，即5加速迭代方法(5-8)得到。现在，xk 1是切换值，(5-24)，(5-25)，x是方程式(5-1)的实际根，也就是由表示式(5-24)和(5-26)清理(对于x=0.5附近的g =-e-XG (0.5)=-e-0.5-0.6，与表5-6、图5.9、示例2相比，加速度迭代公式在同一示例中的精度=10-这个加速过程的