【资料】非线性方程数值解法详解汇编
- 格式：ppt
- 大小：1.03 MB
- 文档页数：29
下载文档原格式
合集下载
非线性方程组的求解(汇编)
非线性方程组的求解摘要：非线性方程组求解是数学教学中，数值分析课程的一个重要组成部分，作为一门学科，其研究对象是非线性方程组。
求解非线性方程组主要有两种方法：一种是传统的数学方法，如牛顿法、梯度法、共轭方向法、混沌法、BFGS 法、单纯形法等。
传统数值方法的优点是计算精度高，缺点是对初始迭代值具有敏感性，同时传统数值方法还会遇到计算函数的导数和矩阵求逆的问题，对于某些导数不存在或是导数难求的方程，传统数值方法具有一定局限性。
另一种方法是进化算法，如遗传算法、粒子群算法、人工鱼群算法、差分进化算法等。
进化算法的优点是对函数本身没有要求，不需求导，计算速度快，但是精度不高。
关键字：非线性方程组、牛顿法、BFGS 法、记忆梯度法、Memetic 算法1： 三种牛顿法：Newton 法、简化Newton 法、修改的Newton 法【1-3】求解非线性方程组的Newton 法是一个最基本而且十分重要的方法, 目前使用的很多有效的迭代法都是以Newton 法为基础, 或由它派生而来。
n 个变量n 个方程的非线性方程组, 其一般形式如下:⎪⎪⎩⎪⎪⎨⎧===0),...,(...0),...,(0),...,(21212211n n n n x x x f x x x f x x x f （1）式(1)中,),...,(21n i x x x f ( i=1, ⋯, n) 是定义在n 维Euclid 空间Rn 中开域 D 上 的实值函数。
若用向量记号，令：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n x x x ...X 21,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡====)(...)()(0),...,(...0),..,(0)...,()(2121212,211X f X f X f x x x f x x x f x x x f X F nn n n n则方程组（1）也可表示为：0)(=X F（2） 其中：X ∈R n ,F ∶R n →R 0, F(X) ∈R n , R n 为赋值空间。
5-非线性方程组的数值解法及最优化方法
然后通过各种下降法或优化算法求出模函数的极小值点，此 极小值点即为非线性方程组的一组解。
非线性方程组的数值解法
不动点迭代法：根据非线性方程求根的迭代法，将方程组改 写为如下等价方程组
xi i x1, x2,, xn , i 1,2,, n
构造迭代公式
xik 1 i x1k , x2k ,, xnk , i 1,2,, n
非线性方程组的数值解法
若对任意A Cmn 都有一个实数 A 与之对应，且满足：
（1）非负性：当 A O 时， A 0 ；当A O 时，A 0；
（2）齐次性：对任何 C ，A A ；
（3）三角不等式：对任意 A, B C nn ，都有A B A B ;
（4）相容性：对任意A, B C nn ，都有 AB A B ，
…
…
18
(0.2325670051,0.0564515197)
19
(0.2325670051,0.0564515197)
max
1 i 2
xik
xik
1
0.2250 0.0546679688 0.0138638640 0.0032704648 0.0008430541 0.0001985303 0.0000519694 0.0000122370 0.0000032485 0.0000007649
10-9
非线性方程组的数值解法
练习题：用牛顿迭代法求解方程组
取 X 0 1.6,1.2T
xx1122
x22 x22
4 1
结果：1.5811,1.2247
非线性方程组的数值解法
应用经过海底一次反射到达水听器阵的特征声线传播时间， 来反演海底参数。假设水中和沉积层声速都是恒定的，海底 沉积层上界面水平，下界面倾斜。特征声线由水中声源出发 折射进入沉积层，经过沉积层的下界面反射后，再折射进入 水中，由水中水听器阵接收。特征声线的传播时间为声线在 水中和沉积层中的传播时间之和。 三维坐标关系如图所示：
非线性方程组的数值解法
不动点迭代法：根据非线性方程求根的迭代法，将方程组改 写为如下等价方程组
xi i x1, x2,, xn , i 1,2,, n
构造迭代公式
xik 1 i x1k , x2k ,, xnk , i 1,2,, n
非线性方程组的数值解法
若对任意A Cmn 都有一个实数 A 与之对应，且满足：
（1）非负性：当 A O 时， A 0 ；当A O 时，A 0；
（2）齐次性：对任何 C ，A A ；
（3）三角不等式：对任意 A, B C nn ，都有A B A B ;
（4）相容性：对任意A, B C nn ，都有 AB A B ，
…
…
18
(0.2325670051,0.0564515197)
19
(0.2325670051,0.0564515197)
max
1 i 2
xik
xik
1
0.2250 0.0546679688 0.0138638640 0.0032704648 0.0008430541 0.0001985303 0.0000519694 0.0000122370 0.0000032485 0.0000007649
10-9
非线性方程组的数值解法
练习题：用牛顿迭代法求解方程组
取 X 0 1.6,1.2T
xx1122
x22 x22
4 1
结果：1.5811,1.2247
非线性方程组的数值解法
应用经过海底一次反射到达水听器阵的特征声线传播时间， 来反演海底参数。假设水中和沉积层声速都是恒定的，海底 沉积层上界面水平，下界面倾斜。特征声线由水中声源出发 折射进入沉积层，经过沉积层的下界面反射后，再折射进入 水中，由水中水听器阵接收。特征声线的传播时间为声线在 水中和沉积层中的传播时间之和。 三维坐标关系如图所示：
3-第三章 非线性方程的数值解法
到小数点后第三位小数，需要二分多少次？ 解：设 f ( x) x6 x 1，由于 f (1) f (2) 0, f ( x) 0(1 x 2)， 所以在区间 [1,2]内方程 f ( x) 0 有唯一实根。
ba 1 令 k 1 10 3 ，求得所需对分次数至少是10次。 2 2
x* xk ba k 1 2
时，停止计算。
§1 根的搜索与二分法
3 2 x 4 x 10 0 在 [1,2] 内的根的近似 例：用二分法求方程 1 2 值，要求绝对误差不超过 10 。 2 3 2 解： f ( x) x 4x 10 f ( x) 3x2 8x 0, x [1,2] 即 f ( x) 严格单调增加，又 f (1) f (2) 0 ，所以方程在[1,2]上有 唯一实根。 ba 1 2 令 2k 1 2 10 ，得到 k 6.64 ，取 k 7 ，即至少二分7次 。计算过程如下：
由 f ( x) 0 转化为 x ( x) 时，迭代函数 ( x) 不是唯一的， ( x) 不同，会产生不同的序列{xk } ，从而收敛情况也不 一样。
§2 迭代法及其迭代收敛的加速方法
几何意义： * x x ( x ) 求方程 的根 ，在几何上就是求直线 y x与曲线 y ( x) 交点 P* 的横坐标，如图所示。从图中可以看出， * ( x ) ( x ) x 当迭代函数 的导数 在根 处满足不同条件时，迭
特点：运算简单，方法可靠，对函数只要求在区间上连续 ；但收敛速度慢，不能用来求复数根及偶数重根。常用于为 其它求根方法提供较好的近似初始值。
§2 迭代法及其迭代收敛的加速方法
迭代法（逐次逼近）
数值分析第七章非线性方程的数值解法
数值分析第七章非线性方程的数值解法在数值分析中，非线性方程和非线性方程组的求解是非常重要的问题。
线性方程是指变量之间的关系是线性的，而非线性方程则指变量之间的关
系是非线性的。
非线性方程的数值解法是通过迭代的方式逼近方程的解。
非线性方程的求解可以分为两类：一元非线性方程和多元非线性方程组。
接下来，我们将对这两类方程的数值解法进行介绍。
对于一元非线性方程的数值解法，最常用的方法是二分法、牛顿法和
割线法。
二分法是一种直观易懂的方法，其基本思想是通过迭代将方程的解所
在的区间逐渐缩小，最终找到方程的解。
二分法的缺点是收敛速度较慢。
牛顿法是一种迭代法，其基本思想是通过选择适当的初始值，构造出
一个切线方程，然后将切线方程与x轴的交点作为新的近似解，并不断迭代，直到满足精度要求。
牛顿法的优点是收敛速度较快，但其缺点是初始
值的选择对结果影响很大，容易陷入局部极值。
割线法是对牛顿法的改进，其基本思想是通过选择两个初始值，构造
出一条割线，然后将割线与x轴的交点作为新的近似解，并不断迭代，直
到满足精度要求。
割线法的收敛速度介于二分法和牛顿法之间。
对于多元非线性方程组的数值解法，最常用的方法是牛顿法和拟牛顿法。
牛顿法的思想同样是通过构造切线方程来进行迭代，但在多元方程组中，切线方程变为雅可比矩阵。
牛顿法的优点是收敛速度快，但同样受初
始值的选择影响较大。
拟牛顿法是对牛顿法的改进，其基本思想是通过逼近Hessian矩阵来进行迭代，从而避免了计算雅可比矩阵的繁琐过程。
拟牛顿法的收敛性和稳定性较好，但算法复杂度相对较高。
数值分析非线性方程的数值解法
数值分析非线性方程的数值解法数值分析是一种应用数学方法来分析和解决数学问题的领域。
非线性方程是数值分析中一类重要的问题，其解法包括了迭代法、牛顿法、割线法等。
本文将详细介绍这些数值解法及其原理和应用。
一、迭代法迭代法是解非线性方程的一种常用数值方法。
该方法的基本思想是通过不断迭代逼近方程的根，直到达到所需精度或满足停止准则为止。
迭代法的求根过程如下：1.选择适当的初始值x0。
2. 利用迭代公式xn+1 = g(xn)，计算下一个近似根。
3.重复步骤2，直到满足停止准则为止。
常用的迭代法有简单迭代法、弦截法和牛顿法。
简单迭代法的迭代公式为xn+1 = f(xn)，其中f(x)为原方程的一个改写形式。
该方法的收敛性要求函数f(x)在解附近有收敛性且导数在一个区间内收敛。
弦截法的迭代公式为xn+1 = xn - f(xn) * (xn-xn-1) / (f(xn)-f(xn-1))。
该方法通过连接两个点上的函数值的割线来逼近方程的根。
牛顿法的迭代公式为xn+1 = xn - f(xn) / f'(xn)，其中f'(x)为f(x)的导数。
该方法通过用切线来逼近方程的根。
二、牛顿法牛顿法是解非线性方程的一种常用迭代法。
该方法通过使用方程的导数来逼近方程的根。
迭代过程如下：1.选择适当的初始值x0。
2. 利用迭代公式xn+1 = xn - f(xn) / f'(xn)，计算下一个近似根。
3.重复步骤2，直到满足停止准则为止。
牛顿法的收敛速度较快，但要求方程的导数存在且不为0。
三、割线法割线法是解非线性方程的另一种常用迭代法。
该方法通过连接两个点上的函数值的割线来逼近方程的根。
迭代过程如下：1.选择适当的初始值x0和x12. 计算下一个近似根xn+1 = xn - f(xn) * (xn-xn-1) / (f(xn)-f(xn-1))。
3.重复步骤2，直到满足停止准则为止。
割线法的收敛速度介于简单迭代法和牛顿法之间。
非线性方程(组)的数值解法
第三章 非线性方程(组)的数值解法一．取步长1h =，试用搜索法确立3()25f x x x =--含正根的区间，然后用二分法求这个正根，使误差小于310-。
【详解】因为是要寻找正根，因此，可选含根区间的左端点为0。
(0)5f =-，(1)5f =-，(2)1f =-，(3)16f =，因此，(2,3)中有一个正根。
这就确立了含根区间。
接下来，我们用二分法求这个正根，使误差小于310-，计算结果如下表 迭代次数k ak b k x0 2 3 2.5 1 2 2.5000 2.250 0 2 2 2.2500 2.125 0 3 2 2.1250 2.062 5 4 2.0625 2.1250 2.093 8 5 2.0938 2.1250 2.109 4 6 2.0938 2.1094 2.101 6 7 2.0938 2.1016 2.097 7 8 2.0938 2.0977 2.095 7 92.09382.09572.094 7二．对方程2()2sin 20f x x x =--=，用二分法求其在区间[]1.5,2内的根，要求误差小于0.01。
【详解】用二分法求解方程在[]1.5,2内的根，要求误差小于0.01，计算结果如下表： 迭代次数k ak b k x0 1.5 2 1.75 1 1.7500 2.0000 1.8750 2 1.8750 2.0000 1.9375 3 1.9375 2.0000 1.9688 4 1.9375 1.9688 1.9531 51.95311.96881.9609三．用不动点迭代法，建立适当的迭代格式，求方程3()10f x x x =--=在0 1.5x =附近的根，要求误差小于610-。
【详解】310x x --=，等价于x =。
这样，可以建立不动点迭代格式1k x +=当0x ≥时，总有23110(1)133x -'<=+≤<，因此，迭代格式对于任意初始值00x ≥总是收敛的。
非线性方程数值求解法总结
（一）非线性方程的迭代解法1.非线性方程的一般形式：f(x)=02.非线性方程的分类：⎩⎨⎧=为其他函数。
超越方程，次代数多项式；为代数方程，)()(0)(x f n x f x f 3.方程的根：若存在常数s 使f(s)=0，则称s 是方程(4.1)的根，又称s 是函数f(x)的零点。
4.重根：若f(x)能分解为)()()(x s x x f m ϕ-= 则称s 是方程(4.1)的m 重根和f(x)的m 重零点。
当m=1时，s 称为方程(4.1)的单根和f(x)的单零点。
5.结论：(1)零点存在定理：设函数f(x)在闭区间[a,b]上连续，且f(a)•f(b)<0，那么在开区间（a,b ）内至少有一点ξ，使f(ξ)=0.(2)根的唯一性判别：一阶导数不变号且不为零(3)n 次代数方程在复数域上恰有n 个根(4)高于4次的代数方程没有求根公式6.方法：(1)搜索根方法：①作图法：②逐步搜索法：确定方程根的范围的步骤：步骤1 取含f(x)=0根的区间[a,b]，即f(a)•f(b)<0；步骤2 从a 开始，按某个预定的步长h ，不断地向右跨一步进行一次搜索， 即检查kh a x k +=上的函数)(k x f 值的符号。
若0)()(1<•-k k x f x f ，则可以确定一个有根区间],[1k k x x -.步骤3 继续向右搜索，直到找出[a,b]上的全部有根区间],[1k k x x -（k=1,2,…,n).(2)二分法①基本思想：含根区间逐次分半缩小，得到一个区间长度以1/2的比例减小的含根区间序列 {}k I ,在给定根的误差界时，利用长度趋于零的特点，可得到在某个区间中满足要求的近似根。
②迭代终止的条件ε<)(k x fε2<-k k a b或者ε<-≤-2k k k a b s x(3)简单迭代法及其收敛性)(0)(x x x f ϕ=⇔=,2,1,0),(1==+k x x k k ϕ迭代法是一种逐次逼近法,用某个固定公式反复校正根的近似值,使之逐 步精确化,最后得到满足精度要求的解。
非线性方程数值解法详解课件
例如，对于求解非线性方程$f(x)=0$的 应用实例中需要注意选择合适的初始近
根，可以先选择一个初始近似解$x_0$， 似解和设置合适的精度要求，以确保算
然后按照弦截法的迭代过程逐步逼近方
法能够快速收敛到真实解。
程的真实解。
05 共轭梯度法
共轭梯度法的原理
它利用共轭方向的概念，通过迭代过程中不断更新搜 索方向，使得函数值逐渐减小，最终找到方程的解。
牛顿法的实现步骤
确定初始点x0，计算f(x0)和f'(x0)，如果f(x0)不等于0，则按照牛顿法的迭代公式 进行迭代，直到满足精度要求。
1. 选取初始点x0；2. 计算函数值f(x0)和导数值f'(x0)；3. 如果f(x0)不等于0，则 按照牛顿法的迭代公式x1=x0-f(x0)/f'(x0)进行迭代；4. 重复步骤2和3，直到满 足精度要求。
以求解非线性方程为例，通过选择合 适的迭代法和初值，可以有效地求解 非线性方程的近似解。
03 牛顿法
牛顿法的原理
01
基于函数f(x)的泰勒级数的前两项， 通过迭代的方式逼近方程f(x)=0 的解。
02
牛顿法的基本思想是通过泰勒级 数的近似，将非线性方程f(x)=0 转化为线性方程，然后利用线性 方程的解来逼近非线性方程的解。
当达到预设的迭代次数或满足一定的收敛 条件时，停止迭代，输出结果。
共轭梯度法的收敛性分析
共轭梯度法具有全局收敛性和局部收敛性，即只要初始点 选择得当，算法能够找到方程的解，且在局部范围内具有 快速收敛的特点。
收敛性分析主要涉及算法的迭代矩阵和函数的性质，如连 续性和可微性等。
共轭梯度法的应用实例
牛顿法的收敛性分析
在一定的条件下，牛顿法是收敛的， 且具有二阶收敛速度。
第4章 非线性方程数值解法
这是事前估计。选取n，预先估计迭代次数。
例题
例4.2.2 证明函数 (x) 3 x 1 在区间[1， 2]上满足迭代收敛条件。
证明：
1 ' 因为 ( x ) ( x 1) 3 0 3 2
x [1,2]
所以 ( x)是区间 a, b]上严格单调增函数。 [
例题
{xk } 。这种方法算为简单迭代法。
例题
例4.2.1 用迭代格式xk 1 1 (k 0,1, 2,) 2 ( xk 1)
求解方程f ( x) x ( x 1) 2 1 0在区间[0,1]的一个 实根.初始值x0 0.4, 精确至4位有效数字.
解：输入bdd
0.52
二分法
设 所求的根为 x ， 则 x [an , bn ] n 1,2......
即
an x bn
n
n 1,2......
lim(bn a n ) lim
n
1 2
n 1
(b a ) 0
取
lim an lim bn x
n n
例题
例1 设方程 f ( x) x3 x 1,[a, b] [1,1.5]
解：取h=0.1,扫描得：
f (1.3) 0.61 0 f (1.4) 0.344 0
方程的有根区间为 .3,1.4]. [1
又 f ' ( x) 3x 2 1 0, x [1.3,1.4] 即 f ( x) 0在 [1.3,1.4]有唯一根。
[a1 , b1 ] [a2 , b2 ]
非线性方程的数值解法
2. 2 二分法
二分法的误差估计
由于 x − x* ≤ 1 (b − a ) = b − a k k k k +1 k +1
2
只要有根区间[a 只要有根区间 k+1, bk+1]的长度小于预先给定的误 的长度小于预先给定的误 差ε，那么就可以取 作为所求根x*的第 次近似值。 作为所求根 的第k+1次近似值。其误差估计为 的第
计算机科学与工程系 21
2.3 迭代法
简单迭代法的原理 迭代法的收敛性 迭代加速法
计算机科学与工程系 22
2.3.1 简单迭代法原理
基本思想
将方程f 将方程 (x) = 0化为一个等价的方程 化为一个等价的方程 x = ϕ (x ) 从而构成序列
x k +1 = ϕ ( x k ) k = 0 , 1, 2 , L
计算机科学与工程系
9
2.1.2 根的隔离方法
画图法
f(x)
x0 =
a
x0 + h
x* b
计算机科学与工程系 10
2.1.2 根的隔离方法
逐步扫描法
设单值连续函数f(x)在有根区间 b]，从左端点 = 在有根区间[a, ，从左端点x 设单值连续函数 在有根区间 a出发，按某个预先选定的步长 一步一步地向右跨 出发， 出发 按某个预先选定的步长h一步一步地向右跨 每跨一步都检验每步起点x 和终点x 每跨一步都检验每步起点 0和终点 0 + h的函数值 的函数值 如果
1 x − xk ≤ k +1 (b − a) 2
*
计算机科学与工程系 16
1 xk = (ak + bk ) 2
输入 a, b, ε 定义f (x) 是
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
根的唯一性
设x=(x)在[a, b] 上有两根α1, α2， α1 α2 ， α1- α2=(α1)-(α2)L α1- α2 与 L<1矛盾.故α1= α2
序列的收敛性
xk+1-α=(xk)-(α)Lxk-α , xk+1-αLk+1x0-α
由0L<1有
lim
k
xk
误差估计
xk+1-xk=(xk)–(xk-1)Lxk-xk-1 xk+2-xk+1=(xk+1)–(xk)L2xk-xk-1
称该迭代法是全局收敛的。
迭代法的局部收敛性
定义2 设方程x=(x) 根α, 如果存在α 的某个邻域 : x-α，对任意初值
x0，迭代过程所产生的序列均收敛 于根α ，则称该迭代法是局部收敛的.
迭代过程的收敛速度
定义3 记 ek = α- xk ，若
则称迭代过程kli是m pee阶kk1p收 敛C 的0. 特别地，当p=1时，称为线性收敛；
非线性方程数值解法详解
求根步骤
（1）根的存在性. （2）根的隔离. （3）根的精确化.
非线性方程求根的数值方法
二分法 迭代法
单点迭代法(不动点迭代，Newton迭代法) 多点迭代法(弦截法）
迭代法的一般理论
迭代法是一种逐次逼近的方法，它的基 本思想是通过构造一个递推关系式 (迭代 格式) ，计算出根的近似值序列,并要求 该序列收敛于方程的根.
题中 (x)=4-2x，当时x(1,2)时,' (x)=-2xln2>2ln2>1 ,由
定理1.2不能用 xk1 42xk 来迭代求根.
把原方程改写为x=ln(4-x)/ln2, 此时(x)=ln(4-x)/ln2 , 则有 1°当x[1,2]时， (x)[1,ln3/ln2] [1,2]
2°x(1,2) ，有
单点迭代法
将方程f(x)=0改写成等价形式
x=(x)
(1)
建立迭代公式
xk+1=(xk)
(2)
在根的附近任取一点x0，可得一序列
xk
k0
.若
x
k
k
0
收敛，即
lim
k
xk
，且(x)连续，则对(2)两
端取极限有α =(α) ，从而α为方程(1)的根，
也称为(x)的不动点，这种求根算法称为不动点
(2)x1, x2[a, b] ，有
(x1)-(x2)L x1-x2 ， L<1 则对任意初值x0 [a, b], 迭代过程 xk+1=(xk)收敛于
x=(x)的惟一根 ，且有误差估计式
xk
L 1 L
xk xk 1
xk
Lk 1 L
x1 x0
证 根的存在性
由(2)知(x)连续. 令f(x)=x-(x), f(a)0, f(b)0, 从而 f(x)=0在[a, b] 上有根，即x=(x)在[a, b] 上有根.
x=(x)的惟一根.
不动点迭代法的局部收敛性及收敛阶
定理1.3 若(x)在方程x=(x)的根α的邻域内有
一阶连续的导数，且'(α) <1,则迭代过程xk+1=(xk) 具有局部收敛性 证 由连续函数性质，存在α的充分小邻域
: x-α, 使当x 时，有 ' (x)L<1
由微分中值定理有
(x)–α=(x)–(α)='()x-α<x-α 故(x)，由定理1.2知对任意初值x0 均收敛.
xk+p-xk+p-1Lpxk-xk-1
xk+p-xk xk+p-xk+p-1+xk+p-1-xk+p-2++ xk+1-xk
(Lp+Lp-1++L) xk-xk-1
=
LLp1 1L
xk xk1
令p，有
xk
L 1 L
xk xk 1
xk
Lk 1 L
x1 x0
定理1.2 设(x)在[a, b]上具有一阶导数，且 (1)当x[a, b]时, (x)[a, b] ； (1) x[a, b] ，有'(x)L<1 则对任意初值x0 [a, b], 迭代过程 xk+1=(xk)收敛于
近具有连续一阶导数，又F’ (x)=1+2cx，
解 F( 3)12 3c1 得 0 c 1
解 F( 3) 1 2 3c 1
得
1
3 c0
从而使迭代xk+1=F(xk) 具有局部收3敛性,则 c
令 F(3)12 得3c0；
c 1 23
1 3
，且c0.
令 F( 3)12得3c0,.
c 1 23
当p>1时，称为超线性收敛， 当p=2时，称为平方收敛. p越大，收敛越快.
效率指数
定义3 称
1
EI p
为效率指数. 其中p表示迭代的收敛阶，表示
每步迭代的计算量. EI越大，计算效率越高.
不动点迭代法
不动点迭代法的整体收敛性
定理1.1 设(x)满足
(1)当x[a, b]时，(x)[a, b] ；
迭代法（Picard迭代法）. (x) 称为迭代函数.
多点迭代法
建立迭代公式
xk+1=(xk-n+1, ,xk-2, xk-1, xk)
(3)
对于迭代法需要考虑一下几个主要问题 收敛性 收敛速度 计算效率
迭代法的局全收敛性
定义1 设为f(x)=0的根，如果x0[a, b]， 由迭代法产生的序列都收敛于根 ，则
定理1.4 若(x)在方程x=(x)的根α的邻域内有
充分阶连续的导数，则迭代过程xk+1=(xk)是p阶 收敛的充分且必要条件是
(j)(α)=0, j=1,2,,p-1
(p)(α)0
证 充分性
x k 1(x k)
()()(x k) (p 1 1 )!(p 1 )()(x k)p 1 p 1 !(p )()(x k)p
'(x)= 1 1 1 1 1 1
4xln2 42ln2 2ln2
由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区 间内的唯一根.
例 设F(x)=x+c(x2-3)，应如何选取c才
能使迭xk+1=F(xk)代具有局部收敛性？
方程x=F(x)的根为 13, 2 3，函数F(x)在根附
xk1p1!(p)(1)(xk )p
kli m xxkk1p
1 (p)()
p!
0
必要性 （略）
例 能不能用迭代法求解方程x=4-2x，如果不能
时，试将方程改写成能用迭代法求解的形式.
方程为x-4+2x =0.设f(x)= x-4+2x ，则f(1)<0，f(2)>0， f‘(x)= 1+2x ln2>0,故方程f(x)=0仅在区间(1, 2)内有唯一根.
设x=(x)在[a, b] 上有两根α1, α2， α1 α2 ， α1- α2=(α1)-(α2)L α1- α2 与 L<1矛盾.故α1= α2
序列的收敛性
xk+1-α=(xk)-(α)Lxk-α , xk+1-αLk+1x0-α
由0L<1有
lim
k
xk
误差估计
xk+1-xk=(xk)–(xk-1)Lxk-xk-1 xk+2-xk+1=(xk+1)–(xk)L2xk-xk-1
称该迭代法是全局收敛的。
迭代法的局部收敛性
定义2 设方程x=(x) 根α, 如果存在α 的某个邻域 : x-α，对任意初值
x0，迭代过程所产生的序列均收敛 于根α ，则称该迭代法是局部收敛的.
迭代过程的收敛速度
定义3 记 ek = α- xk ，若
则称迭代过程kli是m pee阶kk1p收 敛C 的0. 特别地，当p=1时，称为线性收敛；
非线性方程数值解法详解
求根步骤
（1）根的存在性. （2）根的隔离. （3）根的精确化.
非线性方程求根的数值方法
二分法 迭代法
单点迭代法(不动点迭代，Newton迭代法) 多点迭代法(弦截法）
迭代法的一般理论
迭代法是一种逐次逼近的方法，它的基 本思想是通过构造一个递推关系式 (迭代 格式) ，计算出根的近似值序列,并要求 该序列收敛于方程的根.
题中 (x)=4-2x，当时x(1,2)时,' (x)=-2xln2>2ln2>1 ,由
定理1.2不能用 xk1 42xk 来迭代求根.
把原方程改写为x=ln(4-x)/ln2, 此时(x)=ln(4-x)/ln2 , 则有 1°当x[1,2]时， (x)[1,ln3/ln2] [1,2]
2°x(1,2) ，有
单点迭代法
将方程f(x)=0改写成等价形式
x=(x)
(1)
建立迭代公式
xk+1=(xk)
(2)
在根的附近任取一点x0，可得一序列
xk
k0
.若
x
k
k
0
收敛，即
lim
k
xk
，且(x)连续，则对(2)两
端取极限有α =(α) ，从而α为方程(1)的根，
也称为(x)的不动点，这种求根算法称为不动点
(2)x1, x2[a, b] ，有
(x1)-(x2)L x1-x2 ， L<1 则对任意初值x0 [a, b], 迭代过程 xk+1=(xk)收敛于
x=(x)的惟一根 ，且有误差估计式
xk
L 1 L
xk xk 1
xk
Lk 1 L
x1 x0
证 根的存在性
由(2)知(x)连续. 令f(x)=x-(x), f(a)0, f(b)0, 从而 f(x)=0在[a, b] 上有根，即x=(x)在[a, b] 上有根.
x=(x)的惟一根.
不动点迭代法的局部收敛性及收敛阶
定理1.3 若(x)在方程x=(x)的根α的邻域内有
一阶连续的导数，且'(α) <1,则迭代过程xk+1=(xk) 具有局部收敛性 证 由连续函数性质，存在α的充分小邻域
: x-α, 使当x 时，有 ' (x)L<1
由微分中值定理有
(x)–α=(x)–(α)='()x-α<x-α 故(x)，由定理1.2知对任意初值x0 均收敛.
xk+p-xk+p-1Lpxk-xk-1
xk+p-xk xk+p-xk+p-1+xk+p-1-xk+p-2++ xk+1-xk
(Lp+Lp-1++L) xk-xk-1
=
LLp1 1L
xk xk1
令p，有
xk
L 1 L
xk xk 1
xk
Lk 1 L
x1 x0
定理1.2 设(x)在[a, b]上具有一阶导数，且 (1)当x[a, b]时, (x)[a, b] ； (1) x[a, b] ，有'(x)L<1 则对任意初值x0 [a, b], 迭代过程 xk+1=(xk)收敛于
近具有连续一阶导数，又F’ (x)=1+2cx，
解 F( 3)12 3c1 得 0 c 1
解 F( 3) 1 2 3c 1
得
1
3 c0
从而使迭代xk+1=F(xk) 具有局部收3敛性,则 c
令 F(3)12 得3c0；
c 1 23
1 3
，且c0.
令 F( 3)12得3c0,.
c 1 23
当p>1时，称为超线性收敛， 当p=2时，称为平方收敛. p越大，收敛越快.
效率指数
定义3 称
1
EI p
为效率指数. 其中p表示迭代的收敛阶，表示
每步迭代的计算量. EI越大，计算效率越高.
不动点迭代法
不动点迭代法的整体收敛性
定理1.1 设(x)满足
(1)当x[a, b]时，(x)[a, b] ；
迭代法（Picard迭代法）. (x) 称为迭代函数.
多点迭代法
建立迭代公式
xk+1=(xk-n+1, ,xk-2, xk-1, xk)
(3)
对于迭代法需要考虑一下几个主要问题 收敛性 收敛速度 计算效率
迭代法的局全收敛性
定义1 设为f(x)=0的根，如果x0[a, b]， 由迭代法产生的序列都收敛于根 ，则
定理1.4 若(x)在方程x=(x)的根α的邻域内有
充分阶连续的导数，则迭代过程xk+1=(xk)是p阶 收敛的充分且必要条件是
(j)(α)=0, j=1,2,,p-1
(p)(α)0
证 充分性
x k 1(x k)
()()(x k) (p 1 1 )!(p 1 )()(x k)p 1 p 1 !(p )()(x k)p
'(x)= 1 1 1 1 1 1
4xln2 42ln2 2ln2
由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区 间内的唯一根.
例 设F(x)=x+c(x2-3)，应如何选取c才
能使迭xk+1=F(xk)代具有局部收敛性？
方程x=F(x)的根为 13, 2 3，函数F(x)在根附
xk1p1!(p)(1)(xk )p
kli m xxkk1p
1 (p)()
p!
0
必要性 （略）
例 能不能用迭代法求解方程x=4-2x，如果不能
时，试将方程改写成能用迭代法求解的形式.
方程为x-4+2x =0.设f(x)= x-4+2x ，则f(1)<0，f(2)>0， f‘(x)= 1+2x ln2>0,故方程f(x)=0仅在区间(1, 2)内有唯一根.