第3章解方程fx=0的迭代法

第3章解方程f(x)=0的迭代法3.1逐次迭代法3.2Newton法3.3割线法3.4二分法3.5根的分离和求全部单根概述非线性方程:高次代数方程，超越方程非线性方程的根：单根：f(x)=0但f’(x)≠0k重根:f(x)=…=f(k-1)(x)=0,但f(k)(x)≠0非线性方程求根的3个主要问题：(1)根的存在性:

有没有根?有几个根?(2)根的隔离:确定根的区间,使只有1个根(3)根的精确化:使根的近似值不断精确化，直到满足给定精度.3.1逐次迭代法3.1.1逐次迭代思想及迭代公式设f(x)在[a,b]上连续，且f(x)=0有唯一根x*。1、作同解变换：注：同解变换不是唯一的，可以有多种形式。2、对给定初值x0∈[a,b]，构造迭代公式：3.1逐次迭代法收敛性分析：当序列{xn}收敛于x*，且在x*处连续，就有：即n充分大时，xn就可作为x*的近似解.逐次迭代法的关键和难点：(1)哪一种同解变换能使{xn}收敛于x*?(2)初值x0取何值?(3)收敛速度如何?3.1逐次迭代法3逐次迭代法的收敛性3.1逐次迭代法3.1逐次迭代法推论的用途：用于寻找某一种同解变换收敛时的L系数。（通过不等式放大的方法）3.1逐次迭代法逐次迭代法的停止计算的条件3.1逐次迭代法3.1.3逐次迭代法的几何意义求方程f(x)=0的根问题

迭代求解直线y=x与曲线的交点从几何图形上：3.1逐次迭代法3.1逐次迭代法3.1逐次迭代法3.1.2收敛阶（收敛速度问题）3.1逐次迭代法收敛阶的判别方法3.1逐次迭代法3.1.4逐次迭代法的计算实例分析---求解步骤(1)确定有根区间(2)找有效的同解变形，并确定初值x0(3)作迭代计算3.1逐次迭代法3.1.4逐次迭代法的计算实例练习题:讨论下面方程根的情况补充题3.2Newton法3.2.1Newton法的迭代公式1.Newton法的基本思想(1)总体思想：不断用切线的根代替曲线的根，直到得到满意解。(2)主要思路：设x0是方程f(x)=0的一个近似解，过曲线y=f(x)上的点(x0,f(x0))作曲线的切线；取此切线与x轴交点的横坐标x1作为解的一个新近似值；依次继续，直到解的新近似值满足要求为止。3.2Newton法2.Newton法的迭代公式3.2Newton法3.2.2Newton法的几何意义3.2.3Newton法的收敛条件3.2Newton法3.2Newton法3.2.4Newton法的计算实例[例]Newton法的特点：Newton法是不动点迭代法，公式简单，使用方便，易于编程是2阶收敛的，收敛速度较快。每次迭代都要计算导数值，计算量大.补充：Newton法对重根的处理1.Newton法有m重根时的收敛阶补充：Newton法对重根的处理则Newton法在有m重根时，若不作任何改进，只能保证有1阶的收敛阶。2.有重根时的改进Newton法方法1：利用m构造新迭代公式此时能达到2阶收敛，但通常m很难预先知道。补充：Newton法对重根的处理方法2：构造新函数F(x)如果x*是f(x)的m重根，则x*也是F(x)的单根。从而对函数F(x)使用Newton迭代公式，也具有2阶收敛性。缺点：要求f(x)的二阶导数。3.3割线法(弦截法)割线法基本思想用割线的根代替曲线的根方法的关键：合适的初始点A(x0,y0)和B(x1,y1)割线法：双点割线法、单点割线法3.3.1单点割线法1.单点割线法的几何背景不断作割线:始终固定一个端点x0让另一个点xi（i=1,2,3,…）不断改变。3.3.1单点割线法2.过点x0和xn的割线方程3.3.1单点割线法3.单点割线法的迭代公式3.3.1单点割线法3.3.2单点割线法的收敛性3.3.1单点割线法3.3.3

单点割线法的计算实例[例1]3.3.4双点割线法1.双点割线法的迭代公式在Newton法的基础上，用差商代替导数，得双点割线法的迭代公式：初始点的选择：按单点割线法的定理1来确定x0,x1分别为区间[a,b]的哪个端点。3.3.1双点割线法2.双点割线法的收敛性收敛条件与单点割线法的定理1相同。收敛阶：3.3.1双点割线法3.双点割线法的计算实例[例1]3.4二分法3.4.1二分法的计算公式1.二分法的数学依据设函数f(x)在区间[a,b]是单调连续，若f(a)f(b)<0，则f(x)=0在[a,b]上只有一个根x*.2.二分法的基本思想不断对含有根的区间[a,b]作平分，判断x*属于哪个区间。3.4二分法3.二分法的计算步骤(尝试:画流程图?)3.4二分法4.二分法的误差分析5.当计算达到给定精度时，二分法的迭代次数N的估计3.4二分法3.4.2二分法的计算步骤3.4.3二分法的计算实例[例]注:二分法的特点(1)算法简单,方法稳定.(2)不能求偶次重根和复根.(3)收敛速度较慢,常用于求初始近似值.3.5根的分离和求全部单根设f(x)=0,x∈[a,b]有多个根，求全部根。算法步骤：(1)根的分离：对区间[a,b]，取适当步长h，将其分离为n个子区间，若f(xi-1)f(xi)<0，则为有根子区间；否则为无根子区间。(2)对有根