实验三求代数方程的近似根(解)

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

2、不动点迭代法不动点迭代法 和和 牛顿法牛顿法。同时要求大家学会如何。同时要求大家学会如何利用利用Matlab 来求方程的近似解来求方程的近似解q 问题背景和实验目的问题背景和实验目的代数方程近似求解代数方程近似求解3相关概念相关概念( )0f x l 如果如果 f(x) 是一次多项式，称上面的方程为是一次多项式，称上面的方程为线性方线性方程程；否则称之为；否则称之为非线性方程非线性方程q 线性方程线性方程 与与 非线性方程非线性方程本实验主要讨论本实验主要讨论非线性方程非线性方程的数值求解的数值求解4主要内容主要内容n 对分法对分法q 本实验讨论的数值算法本实验讨论的数值算法n 牛顿迭代法牛顿

3、迭代法l 不动点迭代一般形式不动点迭代一般形式l 松弛加速迭代法松弛加速迭代法l Altken 加速迭代法加速迭代法n 不动点迭代法不动点迭代法5q 基本思想基本思想对分法对分法将有根区间进行对分，判断出解在某个分段内，然后将有根区间进行对分，判断出解在某个分段内，然后再对该段对分，依次类推，直到满足给定的精度为止再对该段对分，依次类推，直到满足给定的精度为止q 适用范围适用范围求有根区间内的求有根区间内的 单重实根单重实根 或或 奇重实根奇重实根q 数学原理：数学原理：介值定理介值定理设设 f(x) 在在 a, b 上连续，且上连续，且 f(a) f(b)0，则由介值定，则由介值定理可得，在

4、理可得，在 (a, b) 内至少存在一点内至少存在一点 使得使得 f( )=06q 具体步骤具体步骤对分法对分法设设 f(x) 在区间在区间 a,b 内连续，且内连续，且 f(a)f(b)0。对于给定的精度要求对于给定的精度要求 ，若有，若有 |f(z)| ，则则 z 就是我就是我们所需要的们所需要的 f(x)=0 在区间在区间 a,b 内的内的 近似根近似根例例：用对分法求：用对分法求 x3 - 3x + 1 = 0 在在 0, 1 中的解。（中的解。（fuluA.m） (1) 令令 x = (a+b)/2, 计算计算 f(x) (2) 若若 |f(x)| ，则停止计算，输出近似解，则停止计

5、算，输出近似解 x(3) 若若 f(a) f(x) 0，则令，则令 b = x; 否则令否则令 a = x(4) 返回第一步返回第一步7q 收敛性分析收敛性分析对分法收敛性对分法收敛性=11111 11|*|()()()22 22kkkkkkxxbababa 设方程的根为设方程的根为 x* (ak , bk ) ，又，又 ，所以，所以2kkkabx 0(k )对分法总是收敛的对分法总是收敛的l 对分法的收敛速度通常对分法的收敛速度通常较慢较慢l 对分法通常用来试探实根的对分法通常用来试探实根的分布区间分布区间，或给出根的一，或给出根的一个较为个较为粗糙的近似粗糙的近似根据上面的算法，我们可以得

6、到一个每次缩小一半的根据上面的算法，我们可以得到一个每次缩小一半的区间序列区间序列 ak , bk ，在，在 (ak , bk ) 中含有方程的根。中含有方程的根。8主要内容主要内容n 对分法对分法q 本实验讨论的数值算法本实验讨论的数值算法n 牛顿迭代法牛顿迭代法l 不动点迭代一般形式不动点迭代一般形式l 松弛加速迭代法松弛加速迭代法l Altken 加速迭代法加速迭代法n 不动点迭代法不动点迭代法9不动点迭代法不动点迭代法q 基本思想基本思想u 构造构造 f (x) = 0 的一个等价方程：的一个等价方程： ( )xx u 从某个近似根从某个近似根 x0 出发，计算出发，计算得到一个迭代序

7、列得到一个迭代序列 0kkx 1()kkxx k = 0, 1, 2, . . (x) 的不动点的不动点f (x) = 0 x = (x)等价变换等价变换f (x) 的零点的零点10u 若若 收敛，即收敛，即 ，假设，假设 (x) 连续，则连续，则q 收敛性分析收敛性分析迭代法的收敛性迭代法的收敛性 1limlim ()limkkkkkkxxx lim*kkxx *x( *)x kx*( *)xx ( *)0f x 即即注：若得到的点列发散，则迭代法失效！注：若得到的点列发散，则迭代法失效！11q 定义：定义：迭代法收敛性判断迭代法收敛性判断q 定理定理 2：如果定理如果定理 1 的条件成立，

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

9、0|* |1kkqxxxxq q 定理定理 3：已知方程已知方程 x = (x)，且且(1) 对对 x a, b，有有 (x) a, b；(2) 对对 x a, b，有有| (x)| q 1；q 越小越小，迭代收敛，迭代收敛越快越快 (x*) 越小越小，迭代收敛，迭代收敛越快越快则对则对 x0 a, b ，由由迭代迭代 xk+1 = (xk) 得到的点列都得到的点列都收敛，且收敛，且13迭代法收敛性判断迭代法收敛性判断q 以上所给出的收敛性定理中的条件的验证都比较以上所给出的收敛性定理中的条件的验证都比较困难，在实际应用中，我们常用下面不严格的判别困难，在实际应用中，我们常用下面不严格的判别方

10、法：方法：当有根区间当有根区间 a, b 较小，且对某一较小，且对某一 x0 a, b ，| (x0)| 明显小于明显小于 1 时，则我们就认为迭代收敛时，则我们就认为迭代收敛例例：用不动点迭代法求：用不动点迭代法求 x3 - 3x + 1 = 0 在在 0, 1 中的解。中的解。 （fuluB.m） 14迭代法的加速迭代法的加速1 1 ()()kkkkkxwxwx u 设迭代设迭代 xk+1 = (xk) ，第，第 k 步和第步和第 k+1 步得到的近似步得到的近似根分别为根分别为 xk 和和 (xk) ，令，令其中其中 wk 称为加权系数或权重。得新迭代称为加权系数或权重。得新迭代 xk+

11、1 = (xk) 1( )()( )xw xwxu 加权系数加权系数 wk 的确定：令的确定：令 (x)=0 得得11( )wx 11()kkwx 15松弛迭代法松弛迭代法q 松弛法迭代公式：松弛法迭代公式：1 1 ()()kkkkkxwxwx l 松弛法具有较好的加速效果松弛法具有较好的加速效果 l 甚至甚至有些不收敛的迭代，加速后也能收敛有些不收敛的迭代，加速后也能收敛 1, 1()()1kkkwxx u 缺点：缺点：每次迭代需计算导数每次迭代需计算导数例例：用松弛迭代法求：用松弛迭代法求 x3 - 3x + 1 = 0 在在 0, 1 中的解。中的解。 （fuluD.m） 16Altke

12、n 迭代法迭代法q Altken迭代法迭代法用用 差商差商 近似近似 微商微商211*( *)()( )( *)xxxxxx u 设设 x* 是方程的根，则由中值定理可得是方程的根，则由中值定理可得10211010()()( )xxxxxxxx 212110*( *)xxxxxxxx 2212210()*2xxxxxxx 17Altken 迭代法迭代法q Altken迭代公式迭代公式2212210()*2xxxxxxx (1)(2)(1)(),()kkkkxxxx(2)(1)2(2)1(2)(1)()2kkkkkkkxxxxxxx k = 0, 1, 2, . . Altken 法同样具有较好

13、的加速效果法同样具有较好的加速效果例例：用：用Altken迭代法求迭代法求 x3 - 3x + 1 = 0 在在 0, 1 中的解。中的解。 （fuluE.m） 18主要内容主要内容n 对分法对分法q 本实验讨论的数值算法本实验讨论的数值算法n 牛顿迭代法牛顿迭代法l 不动点迭代一般形式不动点迭代一般形式l 松弛迭代法松弛迭代法l Altken 迭代法迭代法n 不动点迭代法不动点迭代法19牛顿牛顿迭代法迭代法000()()()f xfxxx令：令：( )0P x 000()()f xxxfx0()0)fx q 基本思想：基本思想：用线性方程来用线性方程来近似近似非线性方程，即采用非线性方程，即

14、采用线性化线性化方法方法20000( )( )()()()()2!ff xf xfxxxxx u 设非线性方程设非线性方程 f (x)=0 , f (x) 在在 x0 处的处的 Taylor 展开为展开为( )P x20牛顿牛顿法迭代公式法迭代公式q 牛顿迭代公式牛顿迭代公式000()()f xxxfx1()()kkkkf xxxfx k = 0, 1, 2, . . q 牛顿牛顿法的收敛速度法的收敛速度( )( )( )f xxxfx 令令2( )( )( )( )f x fxxfx 牛顿法至少二阶局部收敛牛顿法至少二阶局部收敛当当 f (x*) 0 时时 (x*)=0 (x) 即为牛顿法的

15、迭代函数即为牛顿法的迭代函数例例：用牛顿法求：用牛顿法求 x3 - 3x + 1 = 0 的解。的解。(fuluF.m) 21牛顿牛顿法迭代公式法迭代公式q 牛顿牛顿的的优点优点q 牛顿牛顿法是目前求解非线性方程法是目前求解非线性方程 (组组) 的主要方法的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。代点充分靠近精确解时。q 牛顿牛顿的缺点的缺点l 对重根收敛速度较慢（线性收敛）对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解对初值的选取很敏感，要求初值相当接近真解在实际计算中，可以先用其它方法获得

16、真解的一个粗在实际计算中，可以先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。糙近似，然后再用牛顿法求解。22Matlab 解方程函数解方程函数roots(p)：多项式的多项式的所有零点所有零点，p 是多项式系数向量。是多项式系数向量。fzero(f,x0)：求求 f=0 在在 x0 附近的根，附近的根，f 可以使用可以使用 inline、字符串字符串、或、或 ，但不能是方程或符号表达式！，但不能是方程或符号表达式！solve(f,v)：求方程关于指定自变量的解，求方程关于指定自变量的解，f 可以是可以是用用字符串表示的方程字符串表示的方程、符号表达式符号表达式或或符号方程符号方程；l solve 也可解方程组也可解方程组(包含非线性包含非线性)；l 得不到解析解时，给出数值解。得不到解析解时，给出数值解。linsolve(A,b)：解线性方程组。解线性方程组。 23上机作业与要求上机作业与要求u 教材第教材第 87 页：页：第第 4 题题