当前位置：文档之家 › 数值分析第七章 非线性方程与方程组的数值解法0607

数值分析第七章 非线性方程与方程组的数值解法0607

  • 格式：ppt
  • 大小：1.41 MB
  • 文档页数：45

下载文档原格式

  / 45

合集下载

数值分析第七章非线性方程的数值解法

数值分析第七章非线性方程的数值解法

数值分析第七章非线性方程的数值解法在数值分析中，非线性方程和非线性方程组的求解是非常重要的问题。

线性方程是指变量之间的关系是线性的，而非线性方程则指变量之间的关
系是非线性的。

非线性方程的数值解法是通过迭代的方式逼近方程的解。

非线性方程的求解可以分为两类：一元非线性方程和多元非线性方程组。

接下来，我们将对这两类方程的数值解法进行介绍。

对于一元非线性方程的数值解法，最常用的方法是二分法、牛顿法和
割线法。

二分法是一种直观易懂的方法，其基本思想是通过迭代将方程的解所
在的区间逐渐缩小，最终找到方程的解。

二分法的缺点是收敛速度较慢。

牛顿法是一种迭代法，其基本思想是通过选择适当的初始值，构造出
一个切线方程，然后将切线方程与x轴的交点作为新的近似解，并不断迭代，直到满足精度要求。

牛顿法的优点是收敛速度较快，但其缺点是初始
值的选择对结果影响很大，容易陷入局部极值。

割线法是对牛顿法的改进，其基本思想是通过选择两个初始值，构造
出一条割线，然后将割线与x轴的交点作为新的近似解，并不断迭代，直
到满足精度要求。

割线法的收敛速度介于二分法和牛顿法之间。

对于多元非线性方程组的数值解法，最常用的方法是牛顿法和拟牛顿法。

牛顿法的思想同样是通过构造切线方程来进行迭代，但在多元方程组中，切线方程变为雅可比矩阵。

牛顿法的优点是收敛速度快，但同样受初
始值的选择影响较大。

拟牛顿法是对牛顿法的改进，其基本思想是通过逼近Hessian矩阵来进行迭代，从而避免了计算雅可比矩阵的繁琐过程。

拟牛顿法的收敛性和稳定性较好，但算法复杂度相对较高。

完整版数值分析第7章答案

完整版数值分析第7章答案

1数值分析第七章第七章非线性方程求根一、重点内容提要（一）问题简介求单变量函数方程f(x)?0(7.1)f(x*)?0x*x*x*为也称为方程的根是指求(7.1).（实数或复数），使得称的根,m f(x)?(x?x*)g(x)f(x)f(x)函数的零点.若可以分解为g(x)g(x)?0x*x*为单称m=1满足时,是方程(7.1)的根.,则当其中m为正整数,g(x)x*x*是方程(7.1)的m称,充分光滑,为m重根.若重根,则有根;当m>1时(m?1)(m)f(x*)?f'(x*)?...?f(x*)?0,f(x*)?0f(x)f(a)f(b)?0,则方程(7.1)在(a,b)[a,b]若上连续且内至少有一个实根,称在[a,b]为方程(7.1)的有根区间.有根区间可通过函数作图法或逐次搜索法求得.(二)方程求根的几种常用方法1.二分法f(x)f(a)f(b)?0f(x)?0f(x)?0*x在上连续,再设内有根,则设.在(a,b)在[a,b]1x?(a?b)a?a,b?bf(x)f(x)?0000计算和.,若则(a,b)内仅有一个根.令20000a?xb?b[a,b])f(a)f(x?0x*?x;,则令,结束计算;若若得新的有根区间,10,11001a?ab?x0)?(f(a)fx,得新,则令的有根区间0110,0011b?a?(b?a)x?(a?b)[a,b][a,b]?[a,b]f(x)0101111再令计算,.,.同上法得221110101[a,b],如此反复进行出新的有根区间,可得一有根区间套22...?[a,b]?[a,b]?...?[a,b]001?n1?nnn2数值分析第七章11a?x*?b,n?0,1,2,...,b?a?(b?a)?...?(b?a)0n0?1nnn?1nn且. 221lim(b?a)?0,lim x?lim(a?b)?x* nnnnn故2????n??nn1x?(a?b)f(x)?0nnn的近似根,可作为,且有误差估计因此21(b?a)|x?x*|?n1?n(7.2)22.迭代法?(x?)x等价变形为将方程式(7.1) (7.3)??(x*)?)(xf(x*)?0x**xx*的一个不动点为函数.;反之亦然则.若要求称满足?(x)的不动点由式(7.3)产生的不动点迭代关系式(也求方程(7.1)的根等价于求称简单迭代法)为?(x),k?0,1,2...x?(7.4)k1?k?(x),k??x0,1,2...?(x)称为迭代函数.函数如果对任意,由式(7.4)产生的序列??x有极限kk??k则称不动点迭代法(7.4)收敛.kk?1x?x*lim?(x)?C[a,b]满足以下两个条件: 定理7.1(不动点存在性定理)设?(x)??b;x?[a,b]a有1.对任意??(y)|?|x?y|?,y[a,b]|(x)?x 2.存在正常数使对任意, ,都有(7.5)1?L?(x)[a,b]x*.则在上存在惟一的不动点?(x)?C[a,b]满足定理7.2(定理不动点迭代法的全局收敛性定理)设7.1中的两个??x]b,?x[a?(x)并条件,由,(7.4),的不动点式得到的迭代序列则对任意到.收敛k0有误差估计式3数值分析第七章L|x?*|?x||x?x1kkk?(7.6)L1?k L|x?x*|?|x?x|1?kkk L1?(7.7)和??'(xx))(xx**的某,为设在的不动点定理7.3(不动点迭代法的局部收敛性定理)?'(x)|?|1,则迭代法(7.4)局部收敛个邻域连续,且.?(xx?)x*,的根如果迭代误差收敛阶的概念设迭代过程(7.4)收敛于方程e?x?x*k??时成产下列渐近关系式当kk e k?1?C(常数C?0)e(7.8) k则称该迭代过程是p阶收敛的.特别地,p=1时称线性收敛,p>1时称超线性收敛,p=2时称平方收敛.(K)?(x)x*的邻近连续,并定理7.4(收敛阶定理在所求根)对于迭代过程(7.4),如果且(p?1)???(x*)?...?*)?'(x*)?0''(x(p)?(x*)?0(7.9)*x的邻近是收敛的,则该迭代过程在点并有e1)(p?1k?*)x?lim(p!ep??k (7.10)k斯蒂芬森(Steffensen)迭代法当不动点迭代法(7.4)只有线性收敛阶,甚至于不收敛时,可用斯蒂芬森迭代法进行加速.具体公式为??(y?)(x),zy?kkkk2)?x(y kk x?x?kk?1z?2y?x kkk k?0,1,2,...(7.11)4数值分析第七章此法也可写成如下不动点迭代式?(x),kx??0,1,2,...kk?12?)?x(x)(?(x)?x????(x)?2?(x(x))(7.12)?(x)x**x是为式(7.12)中则的不动点7.5(定理斯蒂芬森迭代收敛定理)设,?(x)???1*)''(x)?'(x(x)*x的不动点,存在,的不动点;设则,则斯蒂芬森迭代法是(7.11)是2阶收敛的.3.牛顿迭代法牛顿迭代法是一种特殊的不动点迭代法,其计算公式为f(x)k,x?k?0,1,2,...?x k?k1)xf'(其迭代函数为(7.13)k f(x)??(x)?x f'(x)f(x*)?0,f'(x*)?0,f''(x*)?0时牛顿迭代法的收敛速度当,容易证f''(x*)??0*)?''(x 0'(x*)?ff'(x*),由定理,明,7.4知,牛顿迭代法是平方收敛的,且ef''(x*)1?k?lim2*)f'(ex2??k(7.14)k f(x)?0(m?2)*x时,迭代函数的m重顿重根情形的牛迭代法当根是f(x)1??x)?(x?'(x*)?1??0?'(x*)|?1|)xf'(*x.所以牛顿迭代法求处的导数在,且m x*的重数m知道,重根只是线性收敛.若则迭代式f(x)k,k?0,1,2,...??xx?m kk?1)'(xf(7.15)k f(x)??x()f'(x)*x此时迭代式,的单重零点一定是函数,未知时m当.求重根二阶收敛5数值分析第七章?(x)f(x)f'(x)kkk?xx??x?kk?1k?)f''(x)x)]?f(x'(x)[f'(kkkk k?0,1,2,...(7.16)也是二阶收敛的.f(x)k,?k?0,1,2,...x?x k1k?)xf'(如下迭代法简化牛顿法0称为简化牛顿法或平行弦法.牛顿下山法为防止迭代不收敛,可采用牛顿下山法.具体方法见教材.4.弦截法f'(x)xxf(x)在,处的一阶差商来代替,将牛顿迭代法(7.13)中的即可得弦用kkk?1截法f(x)k(xx?x??x)1kk?1k?k f(x)?f(x)(7.17)??x*|:|x??*x内具有二阶连续导数,的邻域在其零点定理7.6假设且对任1kk?)(xfx,x??10f'(x)?0?x?,又初值,,意则当邻域充分小时,有弦截法(7.17)将按阶?1?5?p?1.6182???1?0?*x2的正根收敛到是方程..这里p5.抛物线法(x,f(x)),(x?f(x))两点的直线方程的根近似替弦截法可以理解为用过kk?1kk?1xxx0x)?(fx)?0f(用,过三若的根.已知个近似根,的2kk?1k?(x,f(x)),(x,f(x)),(x,f(x))f(x)?0的根,的抛物线方程的根近似代替2??k?k121k?kkk所得的迭代法称为抛物线法,也称密勒(Muller)法.f(x)f'(x*)?0*x,则抛物线法局部收敛当,在,的邻近有三阶连续导数且收敛阶p?1.839?1.84. 为数值分析第七章二、知识结构图三、常考题型及典型题精解3上有一个实根x*,并用二分法2]在[1,?1?例7-1 证明方程x0?x-6-3,需二分区间[1,2]10.若要求|x-x*|?求这个根,要求|x-x*|?10kk多少次?3在[1,2],则f(1)=-1<0,f(2)=5>0,故方程f(x)=0x?解设f(x)=x1?2在[1,2]时,f'(x)>0,即f(x)=0-1,所以当x?上有根x*.又因f'(x)=3x上有惟一实根x*.用二分法计算结果如表7-1所示.[1,2]7-1表k abxf(x)的符号kkkk+ 2 0 1 1.5- 1.5 1 1 1.25+ 2 1.25 1.51.3751.3125 3 1.251.375 -1.375 1.3438 1.3125 4 +1.312551.3282+1.1341.3125-861.32041.32041.32827-1.32431.32431.32821.3263+87数值分析第七章9 1.3243 1.3282 1.3253 +1.32631-3-3,可以作为x*的近??10此时x=1.3253满足|x-x*|?10?0.97799102似值.1-6?6,只需|x10-x*|?-x*|即可,解得k+1?19.932, 若要求|x?10?kkk+12即只需把[1,2]二分20次就能满足精度要求.x=1,(1)确定有根区间[a,b];(2)构造不动e例7-2 已知函数方程(x-2)点迭代公式使之对任意初始近似x?[a,b],迭代方法均收敛;(3)用所构0?3.|?10造的公式计算根的近似值,要求|x?x1k k?xx因此区间[2,3]0,e解 (1)令f(x)=(x-2)-1>-1,由于f(2)=-1<0,f(3)=e x x)=-1,f(,lim,lim f(x)=+?是方程f(x)=0的一个有根区间.又因f'(x)=(x-1)e???xx???1-1<0,当x>1时f(x)单增,x<1时f(x)单减,故f(x)=0在(-?,+?)内f'(1)=-e有且仅有一根x*,即x*?[2,3].x?xx?.由于当?将(x-2)e[2,3].则=1等价变形为x=2+ee(x)=2+,x(2)2??x??<1'(x)|=|-e?e[2,3]x?时2?|(x)?3,|x?[2,3]均收敛.??故不动点迭代法x=2+e x,k=0,1,2,...,对k0k+1x?进行迭代计算,结果如表7-2所示.e(3)取x=2.5,利用x=2+k k+10表7-28数值分析第七章此时x已满足误差要求,即x*?x?2.120094976.44例7?3考虑求解方程2cos x?3x?12?0的迭代公式2 x=4+cos x,k=0,1,2,...k k+13(1)试证:对任意初始近似x?R,该方法收敛;0-3;10-x|?(2)取x=4,求根的近似值x,要求|x k0k+1k+1(3)所给方法的收敛阶是多少?2?(x)=4+cos x,解 (1)由迭代公式知,迭代函数322?(x)的值域介于(4-)与(4+由于)之间,且(??,??).x?3322?'(x)|=|-sin x|??1|33?(x)在(??,??)内存在惟一的故根据定理7.1,7.2知,??收敛于x*.x?x?R,迭代公式得到的序列不动点x*,且对k0(2) 取x=4,迭代计算结果如表7-3所示.0表7-3x*?xx?3.347529903已满足误差要求，即此时55?'(x*)?0.136323129?0，故根据定理7 .4）由于（3知方法是线性收敛的，并e?1k?'(x?*)lim e??k。

第7章非线性方程组的数值解法

第7章非线性方程组的数值解法
( 1, 1 )
f 1 y f 2 2 y
2 y ( 1,1 ) 2
( 1,1 )
( y 3) ( 1, 1 )
( 1, 1 )
( x 1) ( 1 , 1 ) 2
( 1,1 )
f 1 f 2 2 2[ 2 * ( 3) ( 2 ) * ( 2 )] 4 f1 f2 g10 x ( 1,1) x ( 1,1) x f 1 f 2 g 2 2[ 2 * ( 3) 2 * ( 2 )] 20 20 y y f 1 y f 2 ( 1, 1 ) ( 1, 1 )
完
f ( x0 h, y0 k ) f ( x0 , y0 ) ( h k ) f ( x0 , y0 ) x y 1 2 ( h k ) f ( x 0 , y0 ) 2! x y 1 n ( h k ) f ( x 0 , y0 ) n! x y 1 n 1 ( h k ) f ( x0 h, y0 k ) ( n 1)! x y
2
2
令
0
得 f 1 f 1 ( g10 x g 20 y ) f 1 ( g10 ( g f 1 g f 1 ) 2 ( g 10 20 10 x y f 2 g 20 x f 2 g 20 x f 2 ) f2 y f 2 2 ) ( x y
1
f 1 ( x 0 , y0 ) f ( x , y ) 2 0 0
从n到n+1的迭代格式为：
f 1 ( x n , y n ) xn 1 x n x y y f 2 ( xn , yn ) n 1 n x

(完整版)第7章非线性方程与方程组的数值解法

(完整版)第7章非线性方程与方程组的数值解法
基本思想：逐步将区间分半，通过判别区间端点函数值的符号，
进一步搜索有根区间，将有根区间缩小到充分小，从而求
出满足给定精度的根 x的近似值。
[a1, b1] [a2 , b2 ] [a3, b3]
以 此 类 推
y
a3
a2
b2 2
x2
a1
oa
•••
x
y f (x) bx
a2
a1
b1 2
x1
5
x0
a
Else Set a=x;
Step 6 Set k=k+1; Compute x =(a+b)/2 ;Go To Step 3 ;
Step 7 Output the solution of equation: x; STOP.
7
数值分析
由二分法的过程可知：
第7章 非线性方程与方程组的数值解法
1、 a,b a1,b1 ak ,bk
数值分析
Numerical Analysis
李小林
重庆师范大学数学学院
数值分析
第七章
非线性方程与第7方章 程非线组性方的程与数方值程组解的数法值解法
/* Numerical Solutions of Nonlinear Equations and
Nonlinear Algebraic Systems*/
2
数值分析
第7章 非线性方程与方程组的数值解法
历史背景
n 代数方程的求根问题是一个古老的数学问题。理论上， 次 n 代数方程在复数域内一定有 个根(考虑重数)。早在16世纪就
找到了三次、四次方程的求根公式，但直到19世纪才证明大于 等于5次的一般代数方程式不能用代数公式求解，而对于超越 方程就复杂的多，如果有解，其解可能是一个或几个，也可能 是无穷多个。一般也不存在根的解析表达式。因此需要研究数

Ch7 非线性方程与方程组的数值解法(2)

Ch7 非线性方程与方程组的数值解法(2)
( g ( x) x) 2 ( x) x . g ( g ( x)) 2 g ( x) x
4 / 19
几何意义 Aitken 加速：
y y = g(x)
一般地有：
( x K 1 x K )2 ˆ xK xK xK 2 xK 1 xK 2
y=x
15 / 19
例 再求x 3 x 1 0在1.5附近的根x * .
解：依次用牛顿法 0 1.5，x0 0.6，简化牛顿法 0 0.6， x x 牛顿下山法 1，折半， 1 / 32，计算结果如下：
k 0 1 2 3 4 xk 1.5 1.34783 1.32520 1.32472 xk 0.6 17.9 发散 xk 0.6 1.140625 1.36181 1.32628 1.32472 f(xk) -1.384 -0.656643 0.1866 0.00667 0.0000086
x0 , x1 g ( x0 ), x 2 g ( x1 ), ˆ x 0 , x3 g ( x 2 ), ˆ x1 , x 4 g ( x3 ), ......
P(x1, x2) P(x0, x1)
ˆ x K 比x K 收敛得略快。
Steffensen 加速：
x x1 x* x2 x0
2 / 19

2 x1
2 x1x * x * x2 x0 x2 x * x0 x * x * ,
2 2
x1 x * x0 x * x2 x * x1 x *
2 2 2 x2 x0 x1 x2 x0 2 x0 x1 x0 x2 x0 x1 x* x0 x2 2 x1 x0 x2 2 x1 x0

数值分析第七章 非线性方程与方程组的数值解法0607)

数值分析第七章 非线性方程与方程组的数值解法0607)

一、二分法
3. 二分法的一个例题
例2 求x3 x 1 0在[1.0,1.5]内的一个实根，准确到
小数点后2位.
k ak
bk
xk
f(xk)符号
0 1.0
1.5
1.25
−
1 1.25
1.375
+
2
1.375 1.3125
−
3 1.3125
1.3438
+
4
1.3438 1.3281
+
5
1.3281 1.3203
续，并且
(x*) (x*) ( p1) (x*) 0， ( p) (x*) 0,
只要相邻两次 计算结果的偏
|
xk
x* |
Lk 1 L
|
x1
x0
|
.
(2.5)
差足够小即可
保证近似值xk 具有足够精度
|
xk
x* |
1 1 L
|
xk 1
xk
|
.
(2.6)
二、不动点迭代法
3. 存在性与收敛性
• 局部收敛性
- 定义1 设(x)有不动点x*，若对任意x0∈{ x*
的某个邻域R}，迭代公式(2.2)产生的序列 {xk}∈R，且收敛到x*，则称迭代法(2.2)局部 收敛.
2). 存在正数L<1，使对任意x,y∈[a, b]都有
| (x) ( y) | L | x y |;
则(x)在[a, b]上存在唯一的不动点x*.
二、不动点迭代法
3. 存在性与收敛性
• 全局收敛的充分条件
- 定理2 设(x) 满足定理1中两条件，则对任意
x0∈[a, b]，迭代法收敛，并有误差估计式

非线性方程和方程组的数值解法

非线性方程和方程组的数值解法

1. 使用二分法求3250x x --=在区间[2，3]上的根，要求误差不超过30.510-⨯.解：首先确定二分次数，根据误差估计式得，取k=10即可。

使用二分法计算10次，结果见下表2. 利用0)ln(=+x x 构造收敛的迭代格式，并求在0.5附近的根.解 首先考虑迭代格式1ln ,0,1,2,...k k x x k +=-=，相应的迭代函数()ln ,x x ϕ=-容易计算'1()x xϕ=-，在0.5附近有 ''()2,()21x x ϕϕ≈-≈>.迭代格式1ln ,0,1,2k k x x k +=-=不收敛，利用上题结论，函数()ln x x ϕ=-的反函数1()x x e ϕ--=，建立迭代格式1,0,1,2,...,k x k x e k -+==取初值00.5x =，计算结果见下表：最后*180.5671408x x≈=3.求方程310x x--=在]2,1[上的唯一正根，精度410-解考虑函数3()1, f x x x=--显然(1)10,(2)50f f=-<=>，故在[1,2]上方程有根存在；另外'2()312,[1,2],f x x x=-≥∈因此在[1,2]上方程有唯一的根。

建立迭代格式1nx+=迭代函数()xϕ=在[1,2]上满足23'131()(1)3x xϕ-=+<根据收敛性定理，迭代格式1nx+=[1,2]x∈均收敛。

例如，取初值x=1.5，并计算结果如下：方程31x x--=0在[]1,2上的精确解是* 1.324718x=4.利用简单加速方法，求方程xx e-=在x=0.5附近得一个根，精度510-。

解考虑'(),()0.6x xx e x e Lϕϕ--==-=≈-.利用简单加速方法()1111111n nnn nL Lx xx x xϕ+++--⎧=⎪⎨=-⎪⎩得()1111 1.60.6nxnnn nx ex x x-+++⎧=⎪⎨=+⎪⎩取初值00.5x =，计算结果列表如下：5. 利用Newton 法解方程x=cosx ，取初值0x =1.解 考虑()cos f x x x =-，建立Newton 迭代格式：()()01'1,,0,1,2.....n n n n x f x x x n f x +=⎧⎪⎨=-=⎪⎩方程x=cosx 的精确解是*x =0.739 085 133……。

数值分析 第七章 非线性方程(组)的数值解法.

数值分析 第七章 非线性方程(组)的数值解法.
x0
y
,这样就可得缩小有根区间 a1 , b1
y=f(x) y=f(x)
x* a a1 x1 a2 x* x0 b1 b2 b a x0 a1 x1 a2 b b1 b2
23/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
§7.2 二分区间法 ② 对压缩了的有根区间 a1 , b1 施行同样的手法, b 即取中点 x a 2 ,将区间 a1 , b1 再分为两半,然 后再确定有根区间 a 2 , b2 ,其长度是 a1 , b1 的 二分之一。
长h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0＋ih (i=0,1,2,…,n),从左至右检查f (xi)的符号,如发现xi与端点x0 的函数值异号,则得到一个缩小的有根子区间［xi-1,xi］。
y
0 A
a1 b1 a2 b2
B
x
20/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
§7.1 引言
数值解法的三个步骤 ① 判定根的存在性。即方程有没有根？如果有 根，有几个根？ ② 确定根的分布范围。即将每一个根用区间隔 离开来，这个过程实际上是获得方程各根的 初始近似值。（隔离根） ③ 根的精确化。将根的初始近似值按某种格式 逐步精确化，直到满足预先要求的精度为止。
10/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
3/87 郑州大学研究生2014-2015学年课程 数值分析 Numerical Analysis
§7.1 引言 当 f (x)不是x的线性函数时，称对应的函数方程
f (x)=0为非线性方程。

非线性方程组的数值解法

非线性方程组的数值解法

非线性方程组的数值解法
《非线性方程组的数值解法》是一个比较复杂的数学问题，它涉及到非线性方程组的求解。

非线性方程组的数值解法是指用数值方法来求解非线性方程组的近似解的方法。

非线性方程组的数值解法有很多种，其中最常用的有牛顿法、拟牛顿法、共轭梯度法等。

牛顿法是一种有效的非线性方程组求解方法，它的基本思想是通过迭代的方式，用近似的二次函数拟合原函数，求解近似解。

拟牛顿法是一种进一步改进的牛顿法，它通过迭代求解一系列近似解，从而求解非线性方程组。

共轭梯度法是一种求解非线性方程组的数值方法，它通过不断迭代，搜索最优解，从而求解非线性方程组。

非线性方程组的数值解法在工程中有着重要的应用，它可以用来求解复杂的非线性方程组，从而获得更准确的解。

因此，非线性方程组的数值解法是一个重要的数学工具，在工程中有着广泛的应用。

数值分析 李庆扬 第7章 非线性方程与方程组的数值解法

数值分析 李庆扬 第7章 非线性方程与方程组的数值解法
由定理2可得：迭代法是收敛的。 （2）当
x x3 1
时，在区间
1,2
有：
x 3 x 2 1
不满足定理的条件，无法保证迭代收敛。
a , b
上）
（2） 存在正常数 L 1 ，使对任意
x , y a , b 都有
x y L x y
（迭代函数的增量小于自变量的增量） 则
14
x 在 a , b
上存在唯一的不动点 x 。
2017年1月4日
*
《数值分析》 黄龙主讲
证明：先证不动点存在性。 若
x , y a , b 有
x y x y L x y , a , b
因此，可将上述定理 1 和定理 2 中的条件（2）改为：
x L 1
21
2017年1月4日
《数值分析》 黄龙主讲
例如：
（2） 存在正常数 L 1 ，使对任意
x y L x y
则对任意 由
x0 a , b ：
xk 1 xk 得到的迭代序列 xk
收敛到
x 的不动点 x*
，并有误差估计
k L x k x* x1 x0 1 L
17
2017年1月4日
*
最终取值： x
误差：取有根区间
ak , bk 的中点 （
ak bk xk 作为近似根，则： 2 b ak b a x* x k k k 1 2 2
特点：算法简单，可保证收敛，但收敛太慢。用于求近似解。
8
2017年1月4日
《数值分析》 黄龙主讲
P214例2 求方程 f x x 3 x 1 0 在区间 1.0 ,1.5 内的一个实根， 要求准确到小数点后的第二位。

数值分析教案_非线性方程的数值解法

数值分析教案_非线性方程的数值解法

定理 2（不动点迭代法的全局收敛性定理） 设 ( x) C[a, b] 满足定理 1 中的两个条 件，则对任意的 x0 [a, b] ，由（2.1）式生成的迭代序列 {xk } 收敛到 ( x) 在 [a, b] 上的不 动点，且有
| x* xk | | xk 1 xk | , 1 L
ak bk ） 。记第 n 次过程得到的隔根区间为 2
[an , bn ] ，则 [a0 , b0 ] [a1, b1 ] [a2 , b2 ] [an , bn ]
an x* bn ， n 0,1, 2,
bn an bn 1 an 1 2 b0 a0 2n
k
则称迭代方程（2.1）收敛。 2.2 不动点的存在性与迭代法的收敛性 定义 若存在常数 L ，使对任何 x1 , x2 [a, b] 有
| ( x1 ) ( x2 ) | L | x1 x2 |
则称 ( x) 在 [a, b] 上满足 Lipschitz（利普希茨）条件， L 称为 Lipschitz 常数。 显然， 若 ( x) 在 [a, b] 上满足 Lipschitz 条件， 则 ( x) 在 [a, b] 上连续。 若 ( x ) 在 [ a, b] 上一阶导数存在且有界，则 ( x) 在 [a, b] 上满足 Lipschitz 条件。 定理 1（不动点存在性定理） 设 ( x) C[a, b] 满足以下两个条件： （1）对任意 x [a, b] ，有 ( x) [a, b] ； （2） ( x) 在 [a, b] 上满足 Lipschitz 条件，且 Lipschitz 常数 L 1 ； 则 ( x) 在 [a, b] 上存在唯一的不动点。 证明：先证明不动点的存在性，记 g ( x) x ( x) ，由定理条件有 g (a) a (a) 0 及 g (b) b (b) 0 ，若有一等号成立，则 g (a) 0 或 g (b) 0 ，即 有不动点，否则必 有 g (a) g (b) 0 ，因 g ( x) C[a, b] ，则必有 x* [a, b] 使 g ( x* ) x* ( x* ) 0 ，x* 即为 的 不动点。

数值分析(本科)非线性方程求解

数值分析(本科)非线性方程求解
重数：设������为自然数，若成立 ������ ������ = ������ − ������∗
������ ������
������ ,
������ ������
且������ ������∗ ≠ ������
则称������∗ 是非线性方程������ ������ = ������的������重根，������ = ������时也称单根。
������������ 0.0000
0.5000 0.5000 0.6250 0.6875 0.6875
������������ 1.0000
1.0000 0.7500 0.7500 0.7500 0.7188
������(������������ ) -1.0000
-0.3445 -0.3445 -0.1239 -0.0041 -0.0041
三、二分法
几何解释
三、二分法
几何解释
三、二分法
几何解释
三、二分法
几何解释
三、二分法
考虑非线性方程������ ������ = ������，利用中值定理，可得到如下算法： 假设函数������ ������ 在 ������������ , ������������ 连续，且������(������������ )与������(������������ )异号， 则 ������������ , ������������ 为该方程的有根区间； 取区间 ������������ , ������������ 的中点������������ =
一、非线性方程的数值解法
问题：求解非线性方程 ������ ������ = ������ （*）
若������ ������∗ = ������,称������∗ 是������ ������ = ������的根或������的零点。

非线性方程数值解法

非线性方程数值解法
第三章
非线性方程的数值解法
根的概念
给定方程f(x)=0，如果有α使得f(α)=0， 则称α为f(x)=0的根或f(x)的零点. 设有正整数m使得f(x)=(x-α)mg(x) 且g(α)0 ，则当m2时，称α为f(x)=0的 m重根；当m=1时，称为f(x)=0的单根. 本章只讨论实根的求法.
例 研究求 a的Newton公式,证明：对一切 k 1,2,, xk a ， Newton公式产生的序列 {xk}是单调递减的，从而迭代过程收敛 .

其Newton公式为 证 因a>0，x0>0，故xk >0 (k=1,2,)
xk 1 1 a ( xk ) 2 xk 1 a 2 ( xk ) a a 2 xk
迭代法的局部收敛性

如果存在α的某个邻域: x-α，迭代过程 xk+1=(xk)对任意初值x0均收敛，则称迭代 过程xk+1=(xk)是局部收敛的.


定理3 设(x)在方程x=(x)的根α邻近有一阶连 续的导数. 若'(α) <1, 则迭代过程xk+1=(xk)具有局部收敛 性 若'(α) >1,则迭代过程xk+1=(xk)发散. 证 由于' (α) <1 ，存在充分小邻域: x-α,使 成立' (x)L<1．当x 时，由微分中值定理有 (x)–α=(x)–(α)=' ()x-α＜x-α 故(x)，由定理１知对任意初值x0 均收敛
级数
x0+(x1-x0) +(x2 –x1) ++(xk+1-xk)+收敛.即有
lim xk ，α[a, b] k 下面证α是原方程的根．由(x) 可导， 故(x)在[a, b]上连续，对等式xk+1=(xk)两边同时 取极限得α =(α)，即α是原方程的根．

计算方法第七章非线性方程与方程组的数值解法

计算方法第七章非线性方程与方程组的数值解法

y=x
y
y= ( x)
(x)
P*
x2
x1
x0 x* x
(x* ) 1
（c）
x3 x1 x* x0 x2 x
(x* ) 1
（d）
29
迭代法收敛的条件
对方程f(x)=0可以构造不同的迭代公式, 但 迭代公式
xk 1 ( xk ) (k 0,1,2,)
并非总是收敛。那么,当迭代函数 (x) 满足什 么条件时，相应的迭代公式才收敛呢？即使迭 代收敛时，我们也不可能迭代很多次，而是迭 代有限次后就停止，这就需要估计迭代值的误 差，以便适时终止迭代
根，有几个根？ ② 确定根的分布范围。即将每一个根用区间隔
离开来，这个过程实际上是获得方程各根的 初始近似值。 ③ 根的精确化。将根的初始近似值按某种方法 逐步精确化，直到满足预先要求的精度为止
4
二分法
二分法又称二分区间法,是求解方程(7.1)的近
似根的一种常用的简单方法。
设函数f(x)在闭区间[a,b]上连续,且f(a)f(b)<0,
第7章 非线性方程与方程组 的数值解法
§7.1 方程求根与二分法 §7.2 不动点迭代法及其收敛性 §7.3 迭代收敛的加速方法
§7.4 §7.5 §7.6
牛顿法 弦截法与抛物线法 求根问题的敏感性与多项式的零点
§7.7 非线性方程组的数值解法
1
§7.1 方程求根与二分法
在科学研究和工程设计中, 经常会遇到的一大类 问题是非线性方程
对值或 ak 与 bk 的差的绝对值是否小于ε来决
定二分区间的次数。
17
二分法算法实现
开始 输 入 a , b,ε
y xb
(a+b)/2 x f(a) f(x )<0 ?

数值分析课件第07章非线性方程求根

数值分析课件第07章非线性方程求根
由于它是基于切线方程而得到的，因而也叫切线法。
值分析
例题 用Newton法求方程
解
因为
在0.5附近的根。 ，故迭代格式为
取初值
，经迭代演算，得到前四次的近似根为
值分析
Newton法的应用 对于给定的正数C，应用Newton法解二次方程
因为 故得求
的近似值的迭代格式
例题 计算
解 凡是迭代算法，初值的选取都会影响到收敛速度。
数值分析课件第07章非线性 方程求根
值分析
第7章 非线性方程求根
§求根的基本问题及分析方法 §迭代法 §Newton法 §弦截法与抛物线法
值分析
7.1 求根的基本问题及分析方法
方程的求根大致包括3个基本问题： 根的存在性 方程有没有根？有的话，有几个？ 根的隔离 求出几个互不相交的区间，使每个区间中只有一个根。 根的精确化 在求出精度不高的近似根的基础上，逐步将根精确化， 直到满足预先要求的精度为止。
缩小，使根进一步精确化。
设
，且
，则可判定
。
不妨设
，且
。我们从左端开始，按预先选定的步长h
，一步一步地向右边走，每走一步检查一下终点的函数值是否取正号。
如果
，则表明根
。
如果精度不够，可将
看成 [a, b]再次进行搜索，并从左端点开始
向右搜索，直到满足精度为止。
在具体实施中，步长的选择是个关键，步长较小时精度高，但搜索次数
例对
求根的基本问题及分析方法
之根进行隔离。
解 显然，
，由
得驻点
。
因
故
分别
为 极大值和极小值。
从而
内各有一个实根。
由 y=f(x) 的草图可以直观地看到这点。

研究生课程《数值分析》-第七章非线性方程组求根

研究生课程《数值分析》-第七章非线性方程组求根
数值分析课件 第七章
非线性方程组求根
求解非线性代数数方程组 F(x) 0. 当 n 1 时就是单个方程.
f (x) 0
其中f (x)可以是代数方程。使 f (x) 0成立的 x值称为 方程的根，或称为 f (x) 的零点。
科学与工程计算中，如电路和电力系统计算、 非线性力学、非线性微（积分）方程、非线性规划 （优化）等领域中，问题的求解和模拟最终要解决
–
+
+
可以看出，在[1.0, 1.5]内必有一根。
• 用逐步搜索法进行实根隔离的关键是选取步长 h. • 要选择适当 h ，使之既能把根隔离开来，工作量又不 太大。 • 为获取指定精度要求的初值，可在以上隔离根的基础 上采用对分法继续缩小该含根子区间。
二分法可以看作是搜索法的一种改进。
开始
读a, h
二分法的基本思想是: 首先确定有根区间,将区间二等分, 通过判断 f(x) 的符号, 逐步将有根区间缩小, 直至有根区间 足够地小, 便可求出满足精度要求的近似根。
设 f(x) 在区间[a, b]上连续, f(a)·f(b)<0, 则在 [a, b]
1
内有方程的根.
取[a, b]的中点
x0
(a b), 2
f ( x) a0 x n a1 x n1 an1 x an (a0 0), (1.2)
其中系数 ai(i=0,1,,n) 为实数.
方程 f(x)=0 的根 x*，又称为函数 f(x) 的零点，即 f(x*)=0， 若 f(x)可分解为
f(x)=(x-x*)mg(x)，
其中 m 为正整数，且 g(x*)≠0. 若 m= 1时, 则称x*为单根； 若 m > 1 称 x*为(1.1)的m重根，或称 x* 为函数 f(x)的 m重 零点。若 x*是 f(x) 的m重零点，且 g(x)充分光滑，则
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

三、迭代收敛的加速方法
2.斯特芬森迭代法
• 加速方法
- 将埃特金加速技巧与不动点迭代结合
x0 y0 z0
x1
y1
z1
x2 y 2
z2

yk ( xk ), z k ( yk )
( y k xk ) 2 xk 1 xk z k 2 y k xk
四、牛顿法
1.牛顿法的基本算法
f ( xk ) m m
收敛速度？
xk 1 x 0 m 1 m 1 xk k 1 1, 线性收敛. m xk 0 m
四、牛顿法
2. 收敛性
•
f ( x) 牛顿法就是对 ( x) x f ( x) 的不动点迭代法
• 重根情形( f '(x*)=0 ,...,f (m-1)(x*)=0, f (m)(x*)≠0) - 修正牛顿法 :
原则上确定迭 代次数，但它 由于含有信息 L而不便于实 际应用.
(2.5)
(2.6)
| xk x* |
1 | xk 1 xk | . 1 L
二、不动点迭代法
3. 存在性与收敛性
• 全局收敛的充分条件
- 定理2 设(x) 满足定理1中两条件，则对任意 x0∈[a, b]，迭代法收敛，并有误差估计式
| ( x) ( y ) | L | x y |;
则(x)在[a, b]上存在唯一的不动点x*.
二、不动点迭代法
3. 存在性与收敛性
• 全局收敛的充分条件
- 定理2 设(x) 满足定理1中两条件，则对任意 x0∈[a, b]，迭代法收敛，并有误差估计式
Lk | xk x* | | x1 x0 | . 1 L
Tangent line : y f ( x0 ) f ( x0 )( x x0 )
• 牛顿迭代法的几何解释 y
x1 x0
f ( x0 ) f ( x0 )
x*
x
x0
f ( x1 ) x2 x1 f ( x1 )
x 2x 1
二、牛顿法应用举例
例7 用牛顿法求方程x e 解：牛顿迭代公式为
解：
3 (2) xk 1 xk 1,
0
1 2
1.5
1.35721 1.33086
3
4 5
1.32588
1.32494 1.32476
x0 1.5, x1 2.375, x2 12.39, .
6
7
1.32473
1.32472
二、不动点迭代法
2. 不动点迭代法
( x) 3 x 1
四、牛顿法
2. 收敛性
•
f ( x) 牛顿法就是对 ( x) x f ( x) 的不动点迭代法
• 单根情形( f '(x*)≠0 )
- 例 用牛顿法求f(x)=x2-a (a>0)的根的收敛性及 收敛速度. - 解 f '(√a)=2√a≠0，平方收敛
xk 1 a 2 1 . 2 收敛速度 k ( xk a ) 2 2 a 2 a lim
二、不动点迭代法
1.不动点
• 不动点
- 如果 x* ( x*) ，则称x*为 ( x) 的一个不动点
• 方程的根与不动点
- 方程 f ( x) 0总可以写成等价形式 x ( x) - x*为方程 f ( x) 0 的根等价于x*为 x ( x) 的不 动点
二、不动点迭代法
1.3203
1.3242
−
−
一、二分法
4. 二分法的优缺点
• 二分法的优点是算法简单，且总是收敛的，缺 点是收敛太慢
一、二分法
习题：
考虑方程 x 4 =x 3 +10 .
1) 求一个长度为1的区间 [a,b] ，使方程在其中有一 个解.
2) 以[a,b]开始，要算出10-10的之内的解需要多少步 二分法？用整数回答.
二、不动点迭代法
2. 不动点迭代法
( x) x 3 1
不动点迭代法收敛： 1. 不动点存在 2. 迭代序列收敛
二、不动点迭代法
3. 存在性与收敛性
• 定理1（不动点存在唯一性定理） 设(x)∈C[a, b]满足以下两个条件： 1). 对任意x∈[a, b]有a≤(x)≤b. 2). 存在正数L& 求x x 1 0在[1.0,1.5]内的一个实根，准确到 小数点后2位.
k 0 1 ak 1.0 1.25 bk 1.5 xk 1.25 1.375 f(xk)符号 − +
3
2
3 4 1.3125
1.375
1.3125
1.3438
−
+ +
1.3438
1.3281
5
6 1.3203
1.3281
①考察有根区间[a,b]，检查中点 c (a b) 2上的 函数值
②若f (c)=0，c为f (x)=0的根
否则若f (a)f (c)<0，有根在[a,c]区间中
否则若f (c)f (b)<0，有根在[c,b]区间中 ①对规模更小的有根区间，重复以上步骤，直到 区间长度小于ε
一、二分法
3. 二分法的一个例题
• 设 x*是方程 f (x)=0 的根, xk是x*的近似值.将 f (x)在 xk 附近展开, 有
f ( xk ) f ( xk )( x xk ) 0
牛顿迭代法 x0 初始估计; f ( xk ) xk 1 xk . f ( xk )
四、牛顿法
1.牛顿法的基本算法
3 3 （2）xk 1 ， ( x) 2 ， ( x*) 1; xk x 1 2 x 不同不动点迭代 3 ( x*) 1 （3）xk 1 xk ( xk 3)， ( x) 1 ， 0.134; 收敛速度不一样 4 2 2 1 3 1 3 （ 4）xk 1 ( xk )， ( x) (1 2 )， ( x*) 0. 2 xk 2 x
非线性方程的数值解法
二分法 不动点迭代法
牛顿法 求根问题的敏感性与多项式的零点
一、二分法
1. 二分法的理论基础
• 介值定理
- 设f 是区间[a,b]上的连续函数，满足f (a)f (b)<0 ，那么f在a与b之间有一个根，即存在一个数r （a<r<b），使f(r)=0.
一、二分法
一、二分法
2. 二分法的求解步骤
k xk 迭代法(1) 迭代法(2) 迭代法(3) 2 1.5 2 1.5 ‫׃‬ 2 1.75 1.73475 1.732631 ‫׃‬ 迭代法(4) 0 1 2 3 ‫׃‬ x0 x1 x2 x3 ‫׃‬ 2 3 9 87 ‫׃‬ 2 1.75 1.732143 1.732051 ‫׃‬
二、不动点迭代法
f ( xk ) xk 1 xk m 或 f ' ( xk )
( xk ) f ( x) xk 1 xk ， ( x) ， ' ( xk ) f ' ( x)
均局部平方收敛于x * .
四、牛顿法
习题：
▪ 1）求f(x)=sin x+x2cos x-x2-x的根x*=0的重数，并估 计牛顿法收敛到6位正确小数所需步数(设x0=1).
一、不动点迭代法
习题：
2 ( x ) x 2 x 2 的每一个不动点，并确定不动 ▪ 1）求
点迭代是否局部收敛于它.
三、迭代收敛的加速方法
1.埃特金加速收敛方法
• 加速方法
x0 x1 x1 x2 x2 x3 x3
xk 1 ( xk ) , k 0 ,1,
( xk 1 xk ) 2 xk 1 xk xk 2 2 xk 1 xk
四、牛顿法
2. 收敛性
•
f ( x) 牛顿法就是对 ( x) x f ( x) 的不动点迭代法
• 重根情形( f '(x*)=0 ,...,f (m-1)(x*)=0, f (m)(x*)≠0) - ( x*) 1 1 0, ' ( x*) 0
m
- 因此牛顿迭代法局部线性收敛，
第七章 非线性方程的数值解法
一些基本概念
▪ 非线性方程
3 2 • 如 f ( x) x 11.1x 38.8 x 41.77
▪ 方程的根
• 如果实数 x * 满足 f ( x*) 0 ，则称 x * 为方程的根
▪ m重根
m • 若 f ( x) 能分解为 f ( x) ( x x*) g ( x)，则称 x *为方 程的m重根
只要相邻两次 计算结果的偏 差足够小即可 保证近似值xk 具有足够精度
Lk | xk x* | | x1 x0 | . 1 L
| xk x* | 1 | xk 1 xk | . 1 L
(2.5)
(2.6)
二、不动点迭代法
3. 存在性与收敛性
• 局部收敛性
- 定义1 设(x)有不动点x*，若对任意x0∈{ x* 的某个邻域R}，迭代公式(2.2)产生的序列 {xk}∈R，且收敛到x*，则称迭代法(2.2)局部 收敛.
2. 不动点迭代法
• x0=初始估计 • xk 1 ( xk ) , k 0,1,
当步数趋于无穷时，数列xk可能收敛，也可能不收敛。 如果φ连续且xk收敛到x*，那么x*就是一个不动点。
二、不动点迭代法
2. 不动点迭代法
例3 求x3 x 1 0在1.5附近的根x * .
k xk
xk e xk xk 1 xk 1 xk