《计算方法课件：第13次课代数方程求根》由会员分享，可在线阅读，更多相关《计算方法课件：第13次课代数方程求根（30页珍藏版）》请在金锄头文库上搜索。
1、1计算方法计算方法5 代数方程求根代数方程求根航空科学与工程学院航空科学与工程学院航空科学与工程学院航空科学与工程学院25.1 迭代法的基本概念迭代法的基本概念oo迭代法：迭代法：迭代法：迭代法： 从给定的一个或几个初始近似值从给定的一个或几个初始近似值从给定的一个或几个初始近似值从给定的一个或几个初始近似值( (初始值初始值初始值初始值) )x x0 0、x x1 1、x x2 2、x xr r出发，按某种方法产生的一个序列出发，按某种方法产生的一个序列出发，按某种方法产生的一个序列出发，按某种方法产生的一个序列x x0 0，x x1 1，x x2 2，x xr r， x xr+r+1 1，
2、x xk k ，称称称称为为迭代序列，使迭代序列，使迭代序列，使迭代序列，使得此序列得此序列得此序列得此序列收收收收敛敛于方程于方程于方程于方程f f( (x x)=0)=0的一个根的一个根的一个根的一个根p p。 当当当当k k足够大时，取足够大时，取足够大时，取足够大时，取x xk k作为作为作为作为p p的近似值。的近似值。的近似值。的近似值。代数方程求根代数方程求根代数方程求根代数方程求根3oo需要讨论的问题需要讨论的问题需要讨论的问题需要讨论的问题 迭代法的构造迭代法的构造迭代法的构造迭代法的构造( (迭代格式迭代格式迭代格式迭代格式) )； 迭代序列的收敛性和收敛速度；迭代序列的收
3、敛性和收敛速度；迭代序列的收敛性和收敛速度；迭代序列的收敛性和收敛速度； 误差估计。误差估计。误差估计。误差估计。代数方程求根代数方程求根代数方程求根代数方程求根4oo收敛速度收敛速度收敛速度收敛速度收敛阶数收敛阶数收敛阶数收敛阶数 令令令令 若存在实数若存在实数若存在实数若存在实数 和非零常数和非零常数和非零常数和非零常数C C，使得，使得，使得，使得 则称该迭代法为则称该迭代法为则称该迭代法为则称该迭代法为 阶收敛，或者说收敛阶数为阶收敛，或者说收敛阶数为阶收敛，或者说收敛阶数为阶收敛，或者说收敛阶数为 。 若若若若 =1=1线性收敛；线性收敛；线性收敛；线性收敛； 若若若若 11超线性收
4、敛；超线性收敛；超线性收敛；超线性收敛；代数方程求根代数方程求根代数方程求根代数方程求根55.3 不动点迭代不动点迭代oo将非线性方程将非线性方程将非线性方程将非线性方程f f( (x x)=0)=0化为等价方程化为等价方程化为等价方程化为等价方程 x x= =g g( (x x) )该方程的根称为函数该方程的根称为函数该方程的根称为函数该方程的根称为函数g g( (x x) )的不动点。的不动点。的不动点。的不动点。代数方程求根代数方程求根代数方程求根代数方程求根6oo 为了求为了求为了求为了求g g( (x x) )的不动点，选取一个初始近似的不动点，选取一个初始近似的不动点，选取一个初始
5、近似的不动点，选取一个初始近似值值值值x x0 0，令，令，令，令x xk k= =g g( (x xk k-1-1) )，k k=1, 2, =1, 2, 。以产生序列。以产生序列。以产生序列。以产生序列 x xk k ，这一类迭代法称为不动点迭代法，或，这一类迭代法称为不动点迭代法，或，这一类迭代法称为不动点迭代法，或，这一类迭代法称为不动点迭代法，或PicardPicard法。法。法。法。 g g( (x x) )称为迭代函数。称为迭代函数。称为迭代函数。称为迭代函数。oo若若若若g g( (x x) )连续，连续，连续，连续， ，则，则，则，则p p是是是是g g( (x x) )的一
6、个的一个的一个的一个不动点，不动点，不动点，不动点，p p为方程为方程为方程为方程f f( (x x)=0)=0的解。的解。的解。的解。代数方程求根代数方程求根代数方程求根代数方程求根7oo定理定理定理定理1 1 假设假设假设假设g g( (x x) )为定义在有限区间为定义在有限区间为定义在有限区间为定义在有限区间 a a，b b 上的一个实函数，满足下上的一个实函数，满足下上的一个实函数，满足下上的一个实函数，满足下列条件：列条件：列条件：列条件： (1)(1) (2) (2) LipschitzLipschitz条件，且条件，且条件，且条件，且LipschitzLipschitz常数常数
7、常数常数L L11，即存在正常数，即存在正常数，即存在正常数，即存在正常数L L11，使得，使得，使得，使得则对任意的初始值则对任意的初始值则对任意的初始值则对任意的初始值x x0 0 a a，b b ，由，由，由，由PicardPicard迭代产生的序列都收敛迭代产生的序列都收敛迭代产生的序列都收敛迭代产生的序列都收敛于于于于g g( (x x) )的唯一不动点的唯一不动点的唯一不动点的唯一不动点p p，并有误差估计式，并有误差估计式，并有误差估计式，并有误差估计式代数方程求根代数方程求根代数方程求根代数方程求根8oo推论推论推论推论 条件条件条件条件(2)(2)改为改为改为改为g g( (
8、x x) )的导数的导数的导数的导数g g( (x x) )在在在在 a a，b b 上上上上有界，且有界，且有界，且有界，且定理仍然成立。定理仍然成立。定理仍然成立。定理仍然成立。代数方程求根代数方程求根代数方程求根代数方程求根9oo定理定理定理定理2 2 在定理在定理在定理在定理1 1的假设条件下，再设的假设条件下，再设的假设条件下，再设的假设条件下，再设g g( (x x) )在区间在区间在区间在区间 a a，b b 上为上为上为上为mm( (22) )次连续可微，且在次连续可微，且在次连续可微，且在次连续可微，且在x x= =g g( (x x) )的根的根的根的根p p处处处处g g
9、j j( (p p)=0)=0，j j=1,=1, , mm-1-1，g gmm( (p p) 0) 0。则。则。则。则PicardPicard迭代为迭代为迭代为迭代为mm阶收敛。阶收敛。阶收敛。阶收敛。oo线性收敛线性收敛线性收敛线性收敛( (mm=1)=1)，平方收敛，平方收敛，平方收敛，平方收敛( (mm=2)=2)。代数方程求根代数方程求根代数方程求根代数方程求根10o证明：证明：证明：证明：e ek k+1+1= =x xk k+1+1- -p p= =g(g(x xk k)-g()-g(p p) )= =g(g(e ek k+ +p p)-g()-g(p p) )11oo定理定理定
10、理定理3 3 设设设设p p是方程是方程是方程是方程x x= =g g( (x x) )的一个根，的一个根，的一个根，的一个根，g g( (x x) )在在在在p p的某邻域内为的某邻域内为的某邻域内为的某邻域内为mm次连续可微，且次连续可微，且次连续可微，且次连续可微，且g gj j( (p p)=0)=0，j j=1,=1, , mm-1-1，g gmm( (p p) 0 () 0 (mm22) ) ，则当初始，则当初始，则当初始，则当初始值值值值x x0 0充分接近于充分接近于充分接近于充分接近于p p时，时，时，时，picardpicard序列序列序列序列 x xk k 收敛收敛收敛收
11、敛于于于于p p，且收敛阶数为，且收敛阶数为，且收敛阶数为，且收敛阶数为mm。代数方程求根代数方程求根代数方程求根代数方程求根12oo证明：证明：证明：证明： (1) (1) 由于由于由于由于g(g(p p)=0)=0，从而存在，从而存在，从而存在，从而存在p p的的的的r r邻域邻域邻域邻域 p-rp-r，p+rp+r ，满足满足满足满足| |g(g(x x)|=)|=L L11； (2) (2) 有界区间有界区间有界区间有界区间 | |g(g(x x)-g()-g(p p)|=|)|=|g(g(x x)- )-p p|x x- -p p|=|2)阶连续导数，阶连续导数，p是方程是方程f(x
12、)=0的单根，则当的单根，则当x0充分接近充分接近p时，时，Newton法收敛，且至少为二阶收敛。法收敛，且至少为二阶收敛。o证明？证明？20oo定理定理定理定理5 5： 设函数设函数设函数设函数f f( (x x) )在有限区间上存在二阶导数，且满足条件：在有限区间上存在二阶导数，且满足条件：在有限区间上存在二阶导数，且满足条件：在有限区间上存在二阶导数，且满足条件：(1) (1) f f( (a a) ) f f( (b b)0)0；(2) (2) f f( (x x) )00，x x a a，b b; ;(3) (3) ff( (x x) )在在在在 a a，b b 上不上不上不上不变变
13、号；号；号；号；(4)(4) NewtonNewton法法法法对对任意的初始任意的初始任意的初始任意的初始值值x x0 0 a a，b b ，都收，都收，都收，都收敛敛于方程于方程于方程于方程f f( (x x) )=0=0的唯一解的唯一解的唯一解的唯一解p p，且收，且收，且收，且收敛阶敛阶数数数数为为2. 2. 21oo开方公式开方公式开方公式开方公式 采用采用采用采用NewtonNewton法解二次方程，法解二次方程，法解二次方程，法解二次方程，的近似公式为的近似公式为的近似公式为的近似公式为 例例例例6 6。22ooNewtonNewton下山法下山法下山法下山法 x x0 0 1.5
14、1.50.60.6x x1 1 1.347831.3478317.917.9x x2 2 1.32521.3252 11.946811.9468x x3 31.324721.324727.985527.985525.356915.356913.6253.6252.505592.505591.820131.820131.461041.461041.339321.339321.324911.324911.324721.32472NewtonNewton法的收敛特性与法的收敛特性与法的收敛特性与法的收敛特性与x x0 0的选取有关的选取有关的选取有关的选取有关23ooNewtonNewton下山法下
15、山法下山法下山法 为了防止迭代发散，要求为了防止迭代发散，要求为了防止迭代发散，要求为了防止迭代发散，要求| |f f( (x xk k+1+1)|)|f f( (x xk k)| )|，满，满，满，满足这种要求的算法称为下山法。足这种要求的算法称为下山法。足这种要求的算法称为下山法。足这种要求的算法称为下山法。 NewtonNewton下山法下山法下山法下山法(0(0(0(01)1)1)1)称为下山因子，逐步探索得到。称为下山因子，逐步探索得到。称为下山因子，逐步探索得到。称为下山因子，逐步探索得到。24ooNewtonNewton下山法下山法下山法下山法 =1/32=1/23.87x x0
16、 0 0.60.6x x1 1 1.140621.32476x x2 2 1.147691.32476x x3 31.154421.160841.166971.172821.178411.182761.197921.202450.61.1406225oo二分法二分法二分法二分法+Newton+Newton法的比较法的比较法的比较法的比较11，22二分二分二分二分1 1次，次，次，次，x x0 0=1.5=1.5。 =1/32=1/23.87x x0 0 0.60.6x x1 1 1.140621.32476x x2 2 1.147691.32476x x3 31.154421.160841.1
17、66971.172821.178411.182761.197921.202450.61.1406226割线法割线法(弦截法弦截法)oo导数计算比较复杂，采用差商公式替换导数计算比较复杂，采用差商公式替换导数计算比较复杂，采用差商公式替换导数计算比较复杂，采用差商公式替换NewtonNewton公公公公式中的倒数，有：式中的倒数，有：式中的倒数，有：式中的倒数，有：oo图解图解图解图解27oo收敛速度收敛速度收敛速度收敛速度当当当当x x0 0充分接近充分接近充分接近充分接近p p，线性收敛。，线性收敛。，线性收敛。，线性收敛。28oo快速弦截法快速弦截法快速弦截法快速弦截法29oExercises 习题习题4中的第中的第17，20，22，23(3)不不做做)题。题。代数方程求根代数方程求根代数方程求根代数方程求根30谢谢！谢谢！
