数值计算第二章一元非线性方程的解法第一讲教学-ppt课件

1、1北北 京京 物物 资资 学学 院院第二章第二章 一元非线性方程的解法一元非线性方程的解法引例及问题综述1 . 2基本概念：,)(为一元连续函数设xf为线性方程；程是一次多项式时，称方当函数)2 . 2()(xf)2 . 2(0)( xf称方程为函数方程数时数、对数函数等超越函含有三角函数，指数函若)(xf称为超越方程次代数方程；为次多项式时，称方程是当函数nnxf)2 . 2()(统称为非线性方程次代数方程和超越方程)2( n0012211 axaxaxaxannnn001 axa0sin xexx0 xex02 xx2北北 京京 物物 资资 学学 院院第二章第二章 一元非线性方程的解法一元

2、非线性方程的解法3北北 京京 物物 资资 学学 院院)(0)(0)(,*的零点函数的根为方程，则称使得若存在一点xfxfxxfx )()()(*xgxxxfm 若0)(*不为其中xg重根的为方程则称mxfx0)(* )(重零点的函数mxf方程根的数值计算大致可分为三个步骤：方程根的数值计算大致可分为三个步骤：（1 1判定根的存在性判定根的存在性（2 2确定根的分布范围确定根的分布范围（3 3根的精确化根的精确化零点定理零点定理1.描图法描图法 2.搜索法搜索法), 2 , 1(0 iihxxi令上至少有一个实根则若, 0)()(11 iiiixxxfxf2.搜索法以步长搜索法以步长h进行）进行

3、）077.418 .381 .11)(1 . 223 xxxxf：例进行搜索取步长1 hx0123456f(x)-41.77-13.07-0.571.73-1.17-0.277.432.1 2.1 引例及问题综述引例及问题综述1.二分法二分法 2.迭代法等迭代法等1x2x3x4北北 京京 物物 资资 学学 院院再把区间逐次二等分包含根的区间基本思想：先确定方程,0)(baxf 2.2 2.2 二二 分分 法法理论依据：零点定理0 x)(xfab*x1b1b23a23,ba,11ba ,22ba ,33ba ,kkba )(ab 2kkkabx *xxk *limxxkk |*xxk )(21k

4、kab )(211abk 误差分析：0 即可只要 )(211abk abk 12即： ln)ln(2ln)1( abk12lnln)ln( abk2lnln)ln(ab k可取kkab k21 20bax 2111bax 2222bax kx数列52.2 2.2 二二 分分 法法二二分分法法的的计计算算步步骤骤3 . 2 . 2得到如下算法：中，分别存储在，将二分法中得到的借助计算机的存储特点xbaxbakkk,0 x)(xfab*xbba北北 京京 物物 资资 学学 院院6北北 京京 物物 资资 学学 院院2.2 2.2 二二 分分 法法：步骤1至少有一个根内则在，有若对于0)(),(, 0

5、)()( xfbabfafba：步骤2)(,2),(xfbaxba计算的中点取 ：步骤3xxxfxxf *0)(, 0)(后输出结果的根，停止计算，运行是则若xbxfxaxfaf 取有一个根内则在若.0)(),(, 0)()(xaxfxaxfaf 取有一个根内则在若.0)(),(, 0)()(：步骤42,|21abxab 结果退出计算，运行后输出若 2否则返回步骤7北北 京京 物物 资资 学学 院院2.2 2.2 二二 分分 法法：例1035812211372345 xxxxx用二分法求方程5102 , 1 为绝对误差上的根，设定停止条件在区间 无法求复根和重根。较慢，只能求实根单，缺点是收敛

6、速度比二分法的优点是比较简结果满足允许的误差结果满足允许的误差tol=1e-005.最终结果：最终结果： x1.3089218139658北北 京京 物物 资资 学学 院院2.2 2.2 二二 分分 法法：例2上的一个实根在用二分法求方程5 . 1 , 1 013 xx005. 05 . 1 , 1 为绝对误差上的根，设定停止条件在区间解：0875. 0)5 . 1(, 1)1( ff中有一个实根所以在5 . 1 , 1 计算过程见下表：1.31251.3751.3438+1.31251.34381.3281+1.31251.32811.32031.32051.32811.32423k0124

7、56kakbkx的符号)(kxf2kkkbax 其中3242. 16 x005. 0|6 xx的近似值可以作为 xx3242. 160 . 15 . 125. 1 25. 15 . 1375. 1 375. 125. 13125. 1)(手工计算9北北 京京 物物 资资 学学 院院2.3 2.3 简单迭代法简单迭代法用的方法迭代法是方程求解最常要求为止度直到满足预先给定的精反复校正这个初始值，然后用一个迭代公式，值，先给定一个粗糙的初始种逐次逼近的方法，首迭代法的基本思想是一0)( xf)(xx 称为一个初值给定0 x0)(0 xf?)(x 0 x01)(x 2x1)(x 2)(x x1 nn

8、nx得到一个数列*limxxnn 假设收敛如果数列nx两边取极限在)(1 nnxx )(limlim1 nnnnxx )lim(lim1 nnnnxx *x0)(* xf 3x 的解为0)(* xfx013 xx13 xx)(*x 10北北 京京 物物 资资 学学 院院2.3 2.3 简单迭代法简单迭代法有关定义：程重新整理成等价形式个方法，首先要把原方论的基础，为了应用这也是许多重要理的重要方法。这个方法简单迭代法是求解方程0)( xf)(xx )4 . 2(*0)(xxf的解方程 的不动点。称为)(x *x *x即)( )4 . 2(称;为不动点方程,相应地为迭代格式称), 3 , 2 ,

9、 1()(1 nxxnn ，否则称为发散。收敛，称迭代格式收敛若nx为迭代函数称)(x 性不同可使得迭代格式的收敛不同的)(x 附近的实根在用迭代法求方程例5 . 1013 . 23 xx可以将方程改写为：13 xx31 xxxx11 213 xxx)(xx 方法来完成的构造通常可以用多种迭代函数)(x 简单迭代法又称为不动点迭代简单迭代法又称为不动点迭代11北北 京京 物物 资资 学学 院院2.3 2.3 简单迭代法简单迭代法131 kkxx311 kkxxkkxx111 2131 kkkxxx k. x1=g1(x) x2=g2(x) x3=g3(x) x4=g4(x) 0 1.50000

10、0 1.500000e+000 1.500000 1.500000e+000 1 1.357209 2.375000e+000 1.290994 1.937500e+000 2 1.330861 1.239648e+001 1.332140 4.105347e+000 3 1.325884 1.904003e+003 1.323130 3.614817e+001 4 1.324939 6.902441e+009 1.325060 2.363480e+004 5 1.324760 3.288578e+029 1.324644 6.601240e+012 6 1.324726 3.556514e+

11、088 1.324734 1.438291e+038 7 1.324719 4.498562e+265 1.324715 1.487681e+114 8 1.324718 Inf 1.324719 Inf 9 1.324718 Inf 1.324718 Inf 10 1.324718 Inf 1.324718 Inf12北北 京京 物物 资资 学学 院院)(xx xy 简单迭代法的几何解释的交点问题与直线相当于求曲线xyxy )( 2.3 2.3 简单迭代法简单迭代法)(xy )(11 nnxy 1 nnyx, 3 , 2 , 1)(1 nxxnn， 0 x1x2x3xxyxy )(xy x

12、迭代公式收敛),(00yx),(11yx),(22yx),(01yx),(12yxyx )(xy 13北北 京京 物物 资资 学学 院院xyxy )(xy x0 x2.3 2.3 简单迭代法简单迭代法1x2x3x4x)(11 nnxy 1 nnyx, 3 , 2 , 1)(1 nxxnn， 迭代公式收敛),(00yx),(01yx),(11yx),(12yx14北北 京京 物物 资资 学学 院院0 xxyxy )(xgy x发散的几何解释2.3 2.3 简单迭代法简单迭代法)(11 nnxy 1 nnyx, 3 , 2 , 1)(1 nxxnn， 迭代公式发散1x2x),(00yx),(01y

13、x),(11yx),(12yx),(22yx15北北 京京 物物 资资 学学 院院0 xxyxy )(xgy x发散的几何解释2.3 2.3 简单迭代法简单迭代法)(11 nnxy 1 nnyx, 3 , 2 , 1)(1 nxxnn， 1x2x3x迭代公式发散16北北 京京 物物 资资 学学 院院条件下迭代格式收敛可能发散，那么在什么迭代格式可能收敛，也2.3.2 2.3.2 迭代公式的收敛性与误差估计迭代公式的收敛性与误差估计满足下列两个条件：设迭代函数定理)(1 . 2x ；时，有当,)(,)1(baxbax :,10)2(都有，使对任意存在常数bayxL )8 . 2(|1|1 kkk

14、xxLLxx| )()(|yxLyx xbax上存在惟一不动点在则,)( ,0bax 且对任意初始值 xxxxkkk都收敛于产生的数列由迭代公式)(1 并有误差估计式,条件李普希茨)(Lipschitz映内性：压缩性：)9 . 2(|1|01xxLLxxkk 证明：)()(xxxf 令；时，有当,)(,baxbax ,)(),(baba )()(aaaf )()(bbbf 0017北北 京京 物物 资资 学学 院院2.3.2 2.3.2 迭代公式的收敛性与误差估计迭代公式的收敛性与误差估计0)()( bfaf由零点原理知：)( xx 0)(使得存在一点 xfx xbax上有不动点在即,)( 下

15、证惟一性： 21xx ，假设存在两个不动点|21 xx则| )()(|21 xx |21 xxL|21 xx矛盾。上存在惟一不动点在故 xbax,)(: |1kkxx| )()(|1 kkxx | )()()()(|1 kkxxxx |)()(|kkxxxx |)()()( |kkxxxx | )()(|kkxxxx |kkxxLxx | )( | )1(kxxL |11|1kkkxxLxx )8 . 2(L 11| )()(|1 kkxx LL 1|1 kkxx18北北 京京 物物 资资 学学 院院2.3.2 2.3.2 迭代公式的收敛性与误差估计迭代公式的收敛性与误差估计 |1kkxx|

16、)()(|1 kkxx |1 kkxxL|212 kkxxL|01xxLk |101xxLLk )9 . 2(|11|1kkkxxLxx 中可以看出，从)9 . 2( |kxx要使即可。只要 |101xxLLk|)1(01xxLLk 即：来作为停机条件实际中，一般用 |1kkxx:,1)2(都有，使对任意存在正常数bayxL | )()(|yxLyx 条件李普希茨)(Lipschitz是很难验证的，事实上，条件)2(，并存在正常数上有连续的一阶导数，在若10),()()2( Lbax ,| )( |,Lxbax 有对19北北 京京 物物 资资 学学 院院满足下列两个条件：设迭代函数定理)(1

17、. 2x 2.3.2 2.3.2 迭代公式的收敛性与误差估计迭代公式的收敛性与误差估计,| )( |,10),()()2(,)(,)1(LxbaxLbaxbaxbax 有对，并存在正常数上有连续的一阶导数，在若；时，有当保证有不动点保证惟一性 xbax上存在惟一不动点在则,)( 证明：|21 xx则| )()(|21 xx 12( )|xxx|21 xx矛盾 21xx ，若存在两个不动点|21 xxL xbax上存在惟一不动点在故：,)( 必要条件以上定理的条件都不是收敛性上的收敛性，称为全局在区间以上迭代数列,baxn具有局部收敛性。则迭代格式，且邻域有连续的一阶导数的根在设定理)(,| )

18、( |)()(2 . 21kkxxLxxxxx xx 接近0Lx | )( |0 20北北 京京 物物 资资 学学 院院2.3.4 2.3.4 收敛速度与迭代公式的加速收敛速度与迭代公式的加速概念题，引入“收敛阶”的为了评价收敛速度的问|,kknxxexx 记的数列对于收敛到定义：Cp和如果存在常数0 Ceepkkk 1lim使得阶收敛的则称迭代格式是 p;1时，为线性收敛 p;2时，为平方收敛 p)6 . 2(0)(, 0)()()()()()(3 . 2)()1(*)(1 xxxxxxxxxpppkk 但并且邻域连续，在所求根，如果对于迭代格式定理阶收敛的的邻域是则迭代格式在的px 证：0

19、)( x 知：由定理2 . 2局部收敛迭代格式)(1kkxx 处泰勒展开在 xxk)( )(kx 0)()(!)(kkkkxxkx 时，超线性收敛1 p21北北 京京 物物 资资 学学 院院2.3.4 2.3.4 收敛速度与迭代公式的加速收敛速度与迭代公式的加速处泰勒展开在 xxk)( )(kx )(x )( xxxk 2)(! 2)( xxxk 1)1()()!1()( pkpxxpx 3)(! 3)( xxxk pkkpxxp)(!)()( 0)(, 0)()()()()()1( xxxxxpp 但 )(kx )( x pkkpxxp)(!)()( 1kx xpkkpxxp)(!)()(

20、!)()()(1pxxxxkppkk !)()1()()()1(1pxxxxkpppkk !)()1()()()1(1peekpppkk 即：之间与介于 xxkk !)(lim)1()(lim)()1(1peekpnppkkn !)()1()()1(pxpp 0 得证。)(1kkxx 22北北 京京 物物 资资 学学 院院2.3.4 2.3.4 收敛速度与迭代公式的加速收敛速度与迭代公式的加速迭代公式的加速收敛比较慢时，当迭代格式)(1kkxx )(x 引入新的迭代函数 )()(xx )( xx 如果)()()( xxkxx 那么)( x x的不动点也为)(xx )(1nnxx 可以构造迭代格

21、式LLk 1可以取)(1)(1nnnnxxLLxx 迭代格式变为：nnnxLLxLx 1)(111 也可写成：)(1nnxx 迭代)(1111nnnnxxLLxx 改进加速迭代所以称为加权迭代法)(0 xL 一般)(xxk )1)()()( xkxx 0 )(1()(kkxxk )(1()( xxk )(1()(00 xxk 23北北 京京 物物 资资 学学 院院)(0)(1xxxf 改写成等价的迭代形式：把给定的方程步骤), 3 , 2 , 1()(21 kxxxkkk计算出：由迭代公式步骤 2,)(|31否则返回为解，则结束给定的精度：若步骤xxxkk 2.3 2.3 简单迭代法计算步骤简

22、单迭代法计算步骤迭代法的计算步骤迭代法的计算步骤)(0)(1xxxf 改写成等价的迭代形式：把给定的方程步骤), 3 , 2 , 1(1)(1121 kxxLLxLxknnn计算出：由迭代公式步骤 2,)(|31否则返回为解，则结束给定的精度：若步骤xxxkk 加权迭代法的计算步骤加权迭代法的计算步骤)(0 xL 其中24北北 京京 物物 资资 学学 院院2.3 2.3 简单迭代法例题简单迭代法例题附近的实根在用迭代法求方程例5 . 1013 . 23 xx可以将方程改写为：31 xxxx11 解：311 nnxxkkxx111 构造迭代格式：5 . 10 x3011 xx315 . 1 1.3572 3121 xx311.3572 1.3309 3231 xx311.3309 1.3259 3341 xx311.3259 1.3249 3451 xx311