实验三求代数方程的近似根课件.ppt

1、1实验三实验三求代数方程的近似根求代数方程的近似根感谢你的观看2019年8月282l 解方程（代数方程）是最常见的数学问题之一，也是解方程（代数方程）是最常见的数学问题之一，也是众多应用领域中不可避免的问题之一众多应用领域中不可避免的问题之一l 目前还没有一般的解析方法来求解非线性方程，但如目前还没有一般的解析方法来求解非线性方程，但如果在任意给定的精度下，能够解出方程的近似解，则可果在任意给定的精度下，能够解出方程的近似解，则可以认为求解问题已基本解决，至少可以满足实际需要以认为求解问题已基本解决，至少可以满足实际需要l 本实验主要介绍一些有效的求解方程的数值方法：本实验主要介绍一些有效的求

2、解方程的数值方法：对对分法，不动点迭代法分法，不动点迭代法 和和 牛顿法牛顿法。同时要求大家学会如何。同时要求大家学会如何利用利用 Matlab 来求方程的近似解来求方程的近似解l 问题背景和实验目的问题背景和实验目的代数方程近似求解代数方程近似求解感谢你的观看2019年8月283相关概念相关概念()0f x l 若若 f(x)是一次多项式，称上面的方程为是一次多项式，称上面的方程为线性方程线性方程；否；否则称之为则称之为非线性方程非线性方程l 线性方程线性方程 与与 非线性方程非线性方程本实验主要讨论本实验主要讨论非线性方程非线性方程的数值求解的数值求解感谢你的观看2019年8月284内容提

3、要内容提要l 对分法对分法n 求解非线性方程的数值算法求解非线性方程的数值算法l 牛顿迭代法牛顿迭代法l 不动点迭代一般格式不动点迭代一般格式l 松弛加速迭代法松弛加速迭代法l Altken 加速迭代法加速迭代法l 不动点迭代法不动点迭代法感谢你的观看2019年8月285l 对分法对分法对分法对分法将将有根区间有根区间进行对分，判断出解在某个分段内，然后再对进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止该段对分，依次类推，直到满足给定的精度为止l 适用范围适用范围只能计算有根区间内的只能计算有根区间内的 单重实根单重实根 或或 奇数重实根奇数重实根l 数学原

4、理：数学原理：介值定理介值定理设设 f(x)在在 a,b 上连续，且上连续，且 f(a)f(b)0，则由介值定，则由介值定理可得，在理可得，在(a,b)内至少存在一点内至少存在一点 使得使得 f()=0l 基本思想基本思想感谢你的观看2019年8月286l 具体步骤具体步骤算法描述算法描述设设 f(x)在区间在区间 a,b 内连续，且内连续，且 f(a)f(b)0。对于给定的精度要求对于给定的精度要求 ，若有，若有|f(z)|，则则 z 就是我就是我们所需要的们所需要的 f(x)=0 在区间在区间 a,b 内的内的 近似根近似根例例：用对分法求用对分法求 x3-3x+1=0 在在 0,1 中的

5、解。中的解。(1)令令 x=(a+b)/2,计算计算 f(x)(2)若若|f(x)|，则停止计算，输出近似解，则停止计算，输出近似解 x(3)若若 f(a)f(x)0，则令，则令 b=x;否则令否则令 a=x(4)返回第一步返回第一步fuluA.m感谢你的观看2019年8月287l 收敛性分析收敛性分析对分法收敛性对分法收敛性=11111 11|*|()()()22 22kkkkkkxxbababa 设方程的根为设方程的根为 x*(ak,bk)，又又 ，所以，所以2kkkabx 0(k )对分法总是收敛的对分法总是收敛的l 对分法的收敛速度通常对分法的收敛速度通常较慢较慢l 对分法通常用来试探

6、实根的对分法通常用来试探实根的分布区间分布区间，或给出根的一，或给出根的一个较为个较为粗糙的近似粗糙的近似根据上面的算法，我们可以得到一个每次缩小一半的区间序列根据上面的算法，我们可以得到一个每次缩小一半的区间序列 ak,bk ，在在(ak,bk)中含有方程的根。中含有方程的根。感谢你的观看2019年8月288不动点迭代不动点迭代不动点迭代法不动点迭代法n 不动点迭代一般格式不动点迭代一般格式感谢你的观看2019年8月289不动点迭代法不动点迭代法l 构造构造 f(x)=0 的一个等价方程：的一个等价方程：()xx l 从某个近似根从某个近似根 x0 出发，计算出发，计算得到一个迭代序列得到一

7、个迭代序列 0kkx 1()kkxx k=0,1,2,.(x)的不动点的不动点f(x)=0 x=(x)等价变换等价变换f(x)的零点的零点l 不动点迭代基本思想不动点迭代基本思想感谢你的观看2019年8月2810若若 收敛，即收敛，即 ，假设，假设 (x)连续，则连续，则l 收敛性分析收敛性分析迭代法的收敛迭代法的收敛 1limlim()limkkkkkkxxx lim*kkxx*x(*)x kx*(*)xx (*)0f x 即即注：若得到的点列发散，则迭代法失效！注：若得到的点列发散，则迭代法失效！例例：用迭代法求用迭代法求 x3-3x+1=0 在在 0,1 中的解。中的解。fuluB.m感

8、谢你的观看2019年8月2811迭代法收敛性判断迭代法收敛性判断定理定理 1：如果定理如果定理 1 的条件成立，则有如下估计的条件成立，则有如下估计10|*|1kkqxxxxq 11|*|1kkkxxxxq 定义：定义：如果存在如果存在 x*的的某个某个 邻域邻域 =(x*-,x*+),使得对使得对 x0 开始的迭代开始的迭代 xk+1=(xk)都收敛都收敛,则称该迭代法在则称该迭代法在 x*附近附近局部收敛局部收敛。定理定理 1：设设 x*=(x*)，(x)在在 x*的的某个某个 邻域邻域 内连续，内连续，且对且对 x 都有都有|(x)|q 1,则对则对 x0 ，由由迭代迭代 xk+1=(x

9、k)得到的点列收敛。得到的点列收敛。感谢你的观看2019年8月2812定理定理 3：已知方程已知方程 x=(x)，且且 (1)对对 x a,b，有有 (x)a,b；(2)对对 x a,b，有有|(x)|q 1；则对则对 x0 a,b，迭代迭代 xk+1=(xk)得到的点列都收敛，且得到的点列都收敛，且迭代法收敛性判断迭代法收敛性判断10|*|1kkqxxxxq q 越小越小，迭代收敛，迭代收敛越快越快(x*)越小越小，迭代收敛，迭代收敛越快越快感谢你的观看2019年8月2813迭代法的加速迭代法的加速迭代法的加速迭代法的加速n 松弛加速松弛加速 n Altken 加速加速 感谢你的观看2019

10、年8月2814松弛迭代法松弛迭代法1 1()()kkkkkxwxwx l 设迭代设迭代 xk+1=(xk)，第，第 k 步和第步和第 k+1 步得到的近似步得到的近似根分别为根分别为 xk 和和 (xk)，令，令其中其中 wk 称为加权系数或权重。得新迭代称为加权系数或权重。得新迭代 xk+1=(xk)1()()()xw xwxl 加权系数加权系数 wk 的确定：令的确定：令 (x)=0 得得11()wx 11()kkwx 感谢你的观看2019年8月2815松弛迭代法松弛迭代法l 松弛法迭代公式松弛法迭代公式 1 1()()kkkkkxwxwx l 松弛法具有较好的加速效果松弛法具有较好的加速

11、效果 l 甚至甚至有些不收敛的迭代，加速后也能收敛有些不收敛的迭代，加速后也能收敛 1,1()()1kkkwxx l 缺点：缺点：每次迭代需计算导数每次迭代需计算导数例例：用松弛迭代法求用松弛迭代法求 x3-3x+1=0 在在 0,1 中的解。中的解。其中其中k=0,1,2,.fuluD.m感谢你的观看2019年8月2816Altken 迭代法迭代法l Altken 加速加速用用 差商差商 近似近似 微商微商211*(*)()()(*)xxxxxx l 设设 x*是方程的根，则由中值定理可得是方程的根，则由中值定理可得10211010()()()xxxxxxxx 212110*(*)xxxxx

12、xxx 2212210()*2xxxxxxx 感谢你的观看2019年8月2817Altken 迭代法迭代法2212210()*2xxxxxxx (1)(2)(1)(),()kkkkxxxx(2)(1)2(2)1(2)(1)()2kkkkkkkxxxxxxx k=0,1,2,.l Altken 算法中不需要计算导数算法中不需要计算导数l Altken 算法同样具有较好的加速效果算法同样具有较好的加速效果例例：用用 Altken 迭代法求迭代法求 x3-3x+1=0 在在 0,1 中的解。中的解。fuluE.m感谢你的观看2019年8月2818牛顿迭代牛顿迭代牛顿迭代法牛顿迭代法感谢你的观看201

13、9年8月2819牛顿牛顿迭代法迭代法000()()()f xfxxx令：令：()0P x 000()()f xxxfx0()0)fx l 牛顿法基本思想牛顿法基本思想 用用线性方程线性方程来来近似非线性方程近似非线性方程，即采用，即采用线性化方法线性化方法20000()()()()()()2!ff xf xfxxxxx l 设非线性方程设非线性方程 f(x)=0,f(x)在在 x0 处的处的 Taylor 展开为展开为()P x感谢你的观看2019年8月2820牛顿牛顿法迭代公式法迭代公式l 牛顿迭代公式牛顿迭代公式000()()f xxxfx1()()kkkkf xxxfx k=0,1,2,

14、.l 牛顿牛顿法的收敛速度法的收敛速度()()()f xxxfx 令令2()()()()f x fxxfx 牛顿法至少二阶局部收敛牛顿法至少二阶局部收敛当当 f(x*)0 时时 (x*)=0(x)即为牛顿法的迭代函数即为牛顿法的迭代函数例例：用牛顿法求用牛顿法求 x3-3x+1=0 在在 0,1 中的解。中的解。fuluF.m感谢你的观看2019年8月2821牛顿牛顿法迭代公式法迭代公式l 牛顿牛顿法的优点法的优点l 牛顿牛顿法是目前求解非线性方程法是目前求解非线性方程(组组)的主要方法的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠

15、近精确解时。充分靠近精确解时。l 牛顿牛顿法的缺点法的缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解在实际计算中，可以先用其它方法获得真解的一个粗在实际计算中，可以先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。糙近似，然后再用牛顿法求解。感谢你的观看2019年8月2822Matlab 解方程函数解方程函数见讲义：见讲义：Matlab 多项式运算与代数方程求解多项式运算与代数方程求解感谢你的观看2019年8月2823上机作业与要求上机作业与要求l 教材第教材第 87 页：页：第第 4 题题q 上机上机作业作业要求写实验报告要求写实验报告q 上机要求上机要求l 见课程主页见课程主页l 将所编写的程序分别命名为将所编写的程序分别命名为 hw341.m,hw342.m,hw343.m,hw344.m,hw345.ml 参考课程主页上的附录程序参考课程主页上的附录程序感谢你的观看2019年8月2824感谢你的观看2019年8月28