方程求根.ppt

第2章,方程求根,方程求根,非线性方程 的求解是工程上的常见问题. 1 二分法 2 简单迭代法 3 牛顿法,2.1二分法,求非线性方程,确定方程的有根区间 计算根的近似值,的根的方法,分为两步：,首先确定有限区间：依据零点定理。 设 ，且 ，则方程 在区间 上至少有一个根。如果 在 上恒正或恒负，则此根唯一。,等步长扫描法求有根区间,用计算机求有根区间：等步长扫描法。 设h0是给定的步长，取 ， 若 则扫描成功；否则令 ，继续上述方法，直到成 功。如果 则扫描失败。再将h 缩小， 继续以上步骤。,等步长扫描算法,算法：（求方程 的有根区间） (1) 输入 ； (2) ； (3) ，若 输出失败信息，停机。 (4)若 。输出 ，已算出方程的一个根，停机。,二分法,二分法的基本思想是把区间a，b二等分。 分点 计算函数值,二分法,如果 则求得实根 若 则取 否则取,二分法,对 重复上述做法得 且,二分法,设 所求的根为 ， 则 即 取 为 的近似解,二分法,求方程f(x)=0的根的二分法算法,求方程f(x)=0的全部实根的二分法算法,求方程f(x)=0的全部实根的二分法算法,二分法例题,用二分法求方程 在1，1.5内的一个实根，要求误差不超过0.005. 解：采用事前估计法由（2.2）估算出k=6,因此只需要二分六次就能获得满足精度要求的近似解.计算结果列表如下：,例题,例1 设方程 解：取h=0.1,扫描得： 又 即 在 有唯一根。,二分法例子,2.2迭代法-逐次逼近法,迭代法及收敛性 对于 有时可以写成 形式 如：,迭代法-逐次逼近法,逐次逼近法及收敛性,考察方程 。这种方程是隐式方程，因而不能直接求出它的根，但如果给出根的某个猜测值 ， 代入 中的右端得到 ，再以 为一个猜测值，代入 的右端得 反复迭代得,逐次逼近法,将 变为另一种等价形式 。 选取 的某一近似值 ，则按递推 关系 产生的迭代序列 。这种方法称为逐次逼近法。,迭代法-逐次逼近法,迭代法及收敛性,若 收敛，即 则得 是 的一个根,迭代法的几何意义,交点的横坐标,y=x,例题,例2. 试用迭代法求方程 在区间(1，2)内的实根。 解：由 建立迭代关系 k=10,1,2,3. 计算结果如下:,例题,精确到小数点后五位,例题,例3. 如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列,迭代法的收敛性,定理2.1（全局收敛定理） 设迭代函数 在闭区间 上满足 （1） （2） 满足Lipschitz条件 即 有 。,全局收敛定理,则 在 上存在 唯一解 ， 且对 ，由 产生 的序列 收敛于 。,全局收敛定理,证明：不失一般性,不妨设 否则 为方程的根。 首先证明根的存在性 令,全局收敛定理,则 ， 即 由条件2） 是 上的连续函数 是 上的连续函数。 故由零点定理 在 上至少有一根,全局收敛定理,再证根的唯一性 设有 均为方程的根 则 因为 0L1 ，所以只可能 ， 即根是唯一的。,全局收敛定理,最后证迭代序列的收敛性 与k无关，而0L1 即,全局收敛定理,误差估计 若 满足定理2.1条件，则 这是事后估计，也就是停机标准。L越小，收敛速度越快。 这是事前估计。选取k，预先估计迭代次数。,事后估计与事前估计,事后估计与事前估计,例题,例4. 证明函数 在区间1，2上满足迭代收敛条件。 证明：,例题,例题,例5.若取迭代函数 ， 不满足全局收敛定理，故不能肯定 是否收敛到方程的根。,局部收敛,局部收敛,简单迭代收敛情况的几何解释,2.3 收敛速度,迭代法收敛的阶 定义2.2 设序列 收敛到 ，若有实数 和非零常数C，使得 其中， ，则称该序列是p 阶收敛的，C 称为渐进误差常数。,迭代法收敛的阶,当p=1时，称为线性收敛； 当p1时，称为超线性收敛； 当p=2时，称为平方收敛或二次收敛。,2.3 Newton迭代法,设x * 是方程f (x ) = 0的根，又x0 为x * 附近的一个值 ，将f (x ) 在x0附近做泰勒展式 令 ，则,Newton迭代法,去掉 的二次项，有： 即 以x1代替x0重复以上的过程，继续下去得：,Newton迭代法,以此产生的序列Xn得到f(x)=0的近似 解，称为Newton法，又叫切线法。,Newton迭代法几何解释,几何意义,例题,例6 用Newton法求 的近似解。 解：由零点定理。,例题,例题,例7 用Newton法计算 。 解：,Newton迭代法算法框图,Newton迭代法算法,Newton迭代法收敛性,定理2.4 设函数 ，且满足 若初值 满足 时，由Newton法产生的序列收敛到 在a,b上的唯一根。,Newton迭代法收敛性,证明： 根的存在性 根的唯一性,Newton迭代法收敛性,收敛性,Newton迭代法收敛性,Newton迭代法收敛性,Newton迭代法收敛性,推论 在定理2.2 条件下， Newton迭代法具有平方收敛速度。,代数方程的Newton迭代法,代数方程的Newton迭代法推导 设n次代数方程 用Newton迭代法求有限区间的实根，则要计算 ，一般采用秦九韶算法。,代数方程的Newton迭代法,由Taylor展式,代数方程的Newton迭代法,代数方程的Newton迭代法,同理,代数方程的Newton迭代法,比较x的同次幂系数得： 故代数方程的Newton迭代公式,代数方程的Newton迭代法算法,2.4.3弦截法,Newton迭代法有一个较强的要求是 且存在。因此，用弦的斜率 近似的替代 。,弦截法,令y=0,解得弦与x轴的交点是坐标x2,弦截法,弦截法的几何解释,弦截法收敛定理,例题,例2.8 用快速弦截法求方程 在区间（1，2）内的实根。 解：取x0=1,x1=2,代入公式2.4.2计算结果,如表2.4.1所示。,弦截法收敛定理,求解方程f(x)=0的快速弦截法,