非线性代数方程组的数值解法36页PPT

y1 ( x2
y2 )(x2
y2 )
1 10
(3.25
x1
y1
4.5 x2
y2
)
0.45
x
y
1
(x) ( y) 1 1 (x) 2 ( y) 2 (x) 2 ( y) 0.75 x y
可见，函数 在上 D0是压缩的。因此，由定理6.8得知 结论成立。
以上讨论了迭代法在 D0的收敛性，下面讨论局部收敛性。
y2 )(x2
y2 )
3 10
(
x1
y1
x2
y2 ) 0.3 x y 1
第九页，共二十九页。
第六章非线性方程组的迭代解法
2 (x) 2 ( y)
1 10
x1
y1
x1 x22
y
2
y
2 2
1 10
x1
y1
x1
x
2 2
y1
x
2 2
y1
x
2 2
y1
y
2 2
从而
1 10
(1
x
2 2
)(
x1
y1 )
第十页，共二十九页。
第六章非线性方程组的迭代解法
定义6.4 设 x*为 的不动点，若存在 x*的一个领域 S ，D 对一切
x(0) S ， 由（6.4.3）式产生的序列 x(k) S
且 lim x(k) x* ，则称 x(k)具有局部收敛性。 k
定义6.5
设 x(k)收敛于 x，* 存在常数 p 2及常数c>0,使
10 1
0 10
x
(
0)
88
第十六页，共二十九页。
第六章非线性方程组的迭代解法

26
Newton下山法
原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之 间找一个更好的点 xk1，使得 f ( xk1) f ( xk ) 。
xk
xk+1
xk1 (1 )xk , [0, 1]
xk 1
[xk
)g( xn
)

n1

n

mng(xn ) mg( xn ) n g(
xn
)

n2 g( xn )
mg( xn ) n g( xn )

n1

2 n

g( xn )
mg( xn ) n g( xn )
若 xn 收敛，即
n 0 (n ),
没有具体的描述，而且若x0 的值没有取好，有可 能得不到收敛的结果。
以下定理，给出了 f x 满足一定的条件时，要使得牛顿
迭代法收敛，x0 应满足什么条件。
又 f ( ) 0
( ) 0 1,
牛顿迭代法局部收敛于
又 ( ) 0
即有：牛顿迭代法具有二阶（平方）收敛速度。
注. 定理要求 x0 充分接近 (局部收敛)，充分的程度
没有具体的描述，而且若x0 的值没有取好，有可 能得不到收敛的结果。
以下定理，给出了 f x 满足一定的条件时，要使得牛顿
迭代法收敛，x0 应满足什么条件。
定理 设 f x 在区间 a,b 上的二阶导数存在，且满足： ① f (a) f (b) 0; （保证 a, b中至少存在一个根）
若 xn 收敛，即 n 0 (n )
lim n1 lim[1

k
)
)
f2 ( X x1
)
X X (k)
(x2
x2
(
k
)
)
f2 ( X x2
)
X X (k)
(xn
xn
(
k
)
)
f2 ( X xn
)
X X (k)
f2(X (k))
(
x1
x1(k
)
)
fn ( X x1
)
X X (k)
(x2
x2
(
k
)
)
fn ( X x2
)
X X (k)
(xn
xn
(
k
)
)
fn ( X xn
i (x) 1
i 1, n
i j1 x j
2、 收敛准则 绝对收敛准则
X (k 1) X (k )
相对收敛准则
x (k 1) i
x(k) i
x(k) i
i=1,n
例1 用雅可比迭代求解问题1
T2 400 0.0075(300 T1)2 （1） T1 400 0.02(400 T2 )2 （2）
j 1
j i1
i i i
x1 x2
xn
两者一致!!
ai1 ai2 aii1 aii1 ain
aii aii
aii
aii
aii
对角占
ai1 ai2 aii1 aii1 ain
优
<1
即：
aii
aii ai1 ai2 aii1 aii1 ain
迭代的收敛条件普遍公式
n
max
)
X X (k)

2
7.1 方程求根与二分法
7.1.1 引言 单变量非线性方程的一般形式 （1.1） f ( x) 0 其中 x R , f ( x) C[a, b], [a, b] 也可以是无穷区间.
f(x)是高次多项式函数或超越函数 如果函数 f (x) 是多项式函数，即
f ( x ) a0 x n a1 x n1 an1 x an (a0 0),
xk
可得一个近似根的序列 x0 , x1 , x2 , xk ,,
2
9
且
x* xk (bk ak ) / 2 (b a) / 2k 1 , x * xk , k ln(b a ) ln 1
ln 2
（1.3）
(4) 要使
只要二分足够多次（即 k 充分大），便有
建立迭代公式 各步迭代的结果如下表
表7 3 k xk k xk
x1 2.375, x2 12.39.
xk 1 3 xk 1 (k 0,1,2,).
发散
如果仅取6位数字，
结果x7 与 x8 完全相同， 说明：①迭代函数不唯一，②迭代点列可能收敛，也可 0 1 .5 5 1.32476 能发散，迭代收敛与否不仅与迭代函数有关，还与初 1 1.35721 6 1.32473 x7 即为所求的根. 始点有关。
（1.2）
其中 a0 0, ai (i 0,1,, n) 为实数，则称方程(1.1)为 n 次代数方程.
超越函数 不能表示为多项式的函数
如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2 高次代数方程 超越方程
3
如果实数 x *满足 f ( x*) 0，则称 x * 是方程(1.1)的 根，或称 x *是 f (x)的零点. 若 f (x)可分解为 f ( x) ( x x*)m g ( x),

设 0为给定精 度要求，试确定分半次 数k 使
x* xk
ba 2k
由 于2k ， 两 边 取 对 数 ， 即 得
ba
k ln(b a) ln
ln 2
数值分析
18/47
§例1： 5.用2 二二分分法 求 法x3 4x2 10 0在[1,2]内 的 根 ，
要 求 绝 对 误 差 不 超 过1 102。 2
第七章 非线性方程的数值解法
数值分析
本章内容
§7.1 方程求根与二分法 §7.2 不动点迭代及其收敛性 §7.4 牛顿法 §7.5 弦截法
数值分析
2/47
本章要求
1. 掌握二分法基本原理，掌握二分法的算法 流程;
2. 掌握理解单点迭代的基本思想，掌握迭代 的收敛条件；
3. 掌握Newton迭代的建立及几何意义，了解 Newton迭代的收敛性；
27/47
§ 7.2 不动点迭代法及其收敛性
不动点迭代的几个重要问题： 1、迭代格式的构造； 2、初值的选取； 3、敛散性的判断；☆ 4、收敛速度的判断。
数值分析
28/47
§ 7.2 不动点迭代法及其收敛性
三.压缩映射原理（整体收敛性）
考虑方程x g( x), g( x) C[a, b], 若
则f (x)=0在[a, b]内必有一根。
二. 过程
将区间对分，判别f (x)的符号，逐步缩小有根区 间。
数值分析
14/47
§7.1.2 二分法
三. 方法
取xmid=0.5*(a+b)
若f(xmid) < (预先给定的精度)，则xmid即为根。
否则，若f (a)*f (xmid)<0，则取a1=a，b1=xmid 若f (a)*f (xmid)>0，则取a1=xmid，b1=b 此时有根区间缩小为[a1, b1]，区间长度为 b1-a1=0.5*(b-a)

例如，对于求解非线性方程$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 转化为线性方程，然后利用线性 方程的解来逼近非线性方程的解。
当达到预设的迭代次数或满足一定的收敛 条件时，停止迭代，输出结果。
共轭梯度法的收敛性分析
共轭梯度法具有全局收敛性和局部收敛性，即只要初始点 选择得当，算法能够找到方程的解，且在局部范围内具有 快速收敛的特点。
收敛性分析主要涉及算法的迭代矩阵和函数的性质，如连 续性和可微性等。
共轭梯度法的应用实例
牛顿法的收敛性分析
在一定的条件下，牛顿法是收敛的， 且具有二阶收敛速度。

2000年10月16日
2-5
第6页/共93页
收敛
Newton-Raphson 法需要一个收敛的度量以决定何时结束迭代。给 定外部载荷（Fa），内部载荷（ Fnr ）（由单元应力产生并作用于 节点），在一个体中，外部载荷必须与内力相平衡。
Fa - Fnr = 0
收敛是平衡的度量。
2000年10月16日
样将易于绘制载荷－位移曲线。
2000年10月16日
2-18
第19页/共93页
自动时间步
• 子步中的载荷增量大小 (F) 由时间 步的大小t决定。
• 时间步大小可由用户设定或由 ANSYS自动预测与控制。
载荷
F2 F
• 自动时间步 算法可在载荷步内为所有
子步预测与控制时间步长的大小（载 荷增量）。
F1
CRITERION= 2.113
DISP CONVERGENCE VALUE = 0.1024E-01 CRITERION= 0.9406
<<< CONVERGED
EQUIL ITER 3 COMPLETED. NEW TRIANG MATRIX. MAX DOF INC= 0.3165E-02
FORCE CONVERGENCE VALUE = 2.179
CRITERION= 2.108
<<< CONVERGED
>>> SOLUTION CONVERGED AFTER EQUILIBRIUM ITERATION 4
*** LOAD STEP
1 SUBSTEP 15 COMPLETED. CUM ITER =
31
*** TIME = 59.1250

非线性方程组数值 解法课件
目 录
• 非线性方程组概述 • 迭代法求解非线性方程组 • 牛顿法求解非线性方程组 • 拟牛顿法求解非线性方程组 • 非线性方程组数值解法的应用
01
非线性方程组概述
非线性方程组的定义与分类
定义
非线性方程组是由多个非线性方 程组成的数学模型，描述了多个 变量之间的关系。
在工程问题中的应用
航空航天工程
土木工程
非线性方程组数值解法用于设计和优 化飞行器、卫星和火箭的结构和性能。
在建筑设计、桥梁和高层建筑的结构 分析中，非线性方程组数值解法用于 模拟结构的承载能力和稳定性。
机械工程
在机械设计中，非线性方程组数值解 法用于分析复杂机械系统的动力学特 性和稳定性。
在金融问题中的应用
拟牛顿法的收敛性分析主要基于Hessian 矩阵的条件数和近似矩阵的误差界。在适 当的条件下，拟牛顿法能够保证全局收敛 性和局部超线性收敛性。
拟牛顿法的实现
总结词
拟牛顿法的具体实现可以通过不同的算法实 现，如DFP算法和BFGS算法等。
详细描述
DFP算法（Davidon-Fletcher-Powell）和 BFGS算法（Broyden-Fletcher-GoldfarbShanno）是两种常见的拟牛顿算法。它们 的主要区别在于近似矩阵的更新方式。DFP 算法采用三对角化方法更新近似矩阵，而 BFGS算法采用迭代更新的方式。在实际应 用中，BFGS算法通常比DFP算法更受欢迎， 因为它在大多数情况下都能提供更好的收敛 效果。
05
非线性方程组数值解法的 应用
在物理问题中的应用
量子力学方程
非线性方程组数值解法在 量子力学中用于描述微观 粒子的行为和相互作用。

06
应用举例与算法实现
应用举例
经济学
非线性方程组在经济学中广泛应用于描述市场均衡、消费者行为等问题。例如，求解供需平衡价格时，可以通过构建 非线性方程组来表示供给和需求函数，进而求解市场均衡价格。
工程学
在机械、电子等工程领域，非线性方程组常用于描述系统的动态行为。例如，在控制系统中，通过建立非线性状态方 程来描述系统的状态变化，可以求解系统的稳定性、响应特性等问题。
拟牛顿法是对牛顿法的改进，通过近 似计算雅可比矩阵或其逆矩阵来减少 计算量。常见的拟牛顿法有BFGS方 法、DFP方法等。程序设计时，需要 实现拟牛顿法的迭代过程，包括选择 合适的拟牛顿公式、更新近似矩阵等 步骤。
信赖域方法
信赖域方法是一种全局收敛的非线性 方程组求解算法，其基本思想是在每 次迭代中构造一个信赖域，然后在该 区域内寻找使目标函数充分下降的试 探步。程序设计时，需要实现信赖域 方法的迭代过程，包括构造信赖域、 求解子问题、更新信赖域半径等步骤 。
04
解析解法分离变量法源自01 适用于可将方程中的变量分离为两个或多个独立 函数的情况。
02 通过将方程两边同时积分，得到各变量的通解。 03 需要注意积分常数的确定，以及解的合理性验证。
行波法
01
适用于可化为行波形式的非线性方程。
02
通过引入行波变换，将原方程化为关于行波参数的常微分方 程。
03
步骤
1. 选定适当的坐标轴，将方程的变量表 示为坐标轴上的点。
等倾线法
定义：等倾线法是一种通过绘 制等倾线（即斜率相等的线） ，从而找出方程解的方法。
步骤
1. 将方程转化为斜率形式， 即 y' = f(x, y)。
3. 通过观察等倾线的交点、 切线等性质，可以判断方程 的解的存在性、唯一性等。

求解方程 f (x) 0 的数值解法大致可以分为三步骤：
（1）根的存在性，方程是否有根？如果有，有几个 对于多项式方程，n次方程有n个根。
（2）根的隔离，把区间分为较小的子区间，每个子区 间或者有一个根，或者没有根。这样可以将有根 区间内的任一点都可看成根的一个近似值
（3）根的精确化，对某个近似值设法逐步精确化，使 其满足一定的精确要求
一系列有根区间序列：
a, b a1, b1 a2 , b2 ... ak , bk ...
a,b a1,b1 a2,b2 ... ak ,bk ...
上述每个区间都是前一个区间的一半,因此 ak , bk
的长度：
1 bk ak 2 (bk 1 ak 1 ) ...
任取一个初值 x0 , 代入式 x ( x) 的右端, 得到：
x1 ( x0)
再将 x1 代入式 x ( x) 的右端, 得到 x2 ( x1 )
依此类推, 得到一个数列：
x3 (x2 ) , .......
其一般表示为：
xk1 ( xk ) (k 0,1,2,) (2.6)
式(2.6)称为求解非线性方程的简单迭代法。
这里ε为给定精度,由于 x* a k , bk ,则：
bk
ak 2
ba bk 1 ak 1 2k 1Fra bibliotekx* xk
bk ak 2
ba 2k1
当给定精度ε＞0后,要想 x* xk 成立,只
要取k满足
1 2k 1
(b
a)
即可，亦即当:
k lg(b a) lg 1
lg 2
第二章 非线性方程的数值解法
2.1 二分法 2.2 非线性方程求解的迭代法 2.3 非线性方程求解的matlab函数

xn
(yn xn )2 zn 2yn xn
Steffensen迭代格式
也能够改写成
xn1 (xn )
其中迭代函数
(n 0,1,......)
(x) x [(x) x]2 ((x)) 2(x) x
Steffensen迭代法收敛旳充要条件
定理2.2.3 设函数(x) C1， [x* , x* ], 为足够小的正数，且(x*) 1，则
不满足压缩映像原理，故不能肯定 xn1 (xn ) n 0,1,.... 收敛到方程旳根。
简朴迭代收敛情况旳几何解释
2.2.2 Steffensen加速收敛法
迭代法收敛旳阶
设序列
收敛到 { x，n}0若有实数x*
零常p 数 1C，使得 lim
n
en1 enp
C
和非
其中，en xn x*，则称该序列是p 阶收敛旳， C 称为渐进误差常数。
故{xn }0 收敛到x*。
敛速是线性旳
因为lim n
en1 en
lim
n
(
xn ) xn
(
x*
x*
)
(x*)
0
所以{xn }0
x*
线性收敛到 。
Steffensen迭代格式
由线性收敛知
lim en2 lim en1 C 0
e e n
n
n1
n
当n充分大时有
en2 en1 en1 en
x (a,b)
压缩映像原理
再证根旳唯一性
设有 x1 , x2 [a, b]均为方程旳根
则
|
x1
x2
|| (x1 )
(
x
2
)

Step 4 If |x| < TOL , STOP; Output the solution x.
Step 5 If x*f(a)<0 , Set b=x; Else Set a=x;
Step 6 Set k=k+1; Compute x=f((a+b)/2);Go To Step 3 ;
Step 7 Output the solution of equation: x; STOP.
思
xk+1 = g(xk), … 若
xk
k0
收敛，即存在 x* 使得
路 lk im xk x*，且 g 连续，则由 lk i m x k 1lk 可 i 知m gxx *k=
g(x* )，即x* 是 g 的不动点，也就是f 的根。
几何意义
y
p1 p0
y=x y=g(x)
x3 1.365230014 x 11 1 .3 6 5 1 3 7 8 2 1 x 4 1.365230013
x 29 1 .3 6 5 2 3 0 0 1 3
法4
x 1 1 .3 4 8 4 0 x 2 1 .3 6 7 3 8 x 3 1 .3 6 4 9 6 x 4 1 .3 6 5 2 6 x 4 1 .3 7 5 1 7 x 5 1 .3 6 5 2 2 5
⑥ lki m xxxxkk1 g(x) ?
L 越 小 收敛越快
lix m * x k 1 lig m (ξ k)x (* x k) g (x *) k x * x k k x * x k
注：条件 ( II ) 可改为 在[a, b] 满足Lipschitz条件, 定理结论仍然成立(定理2.3’)。

解： 将方程化成等价形式
x 1 1 ex 5 10
此时，迭代函数 g ( x ) 1 1 e x。由于 f ( x ) e x 10 x 2 , 于是有 5 10
f (0 ) 1 0 , f (1) e 8 0
所以函数 f ( x )在区间 [0 ,1]内至少有一个根。
又由于 g ' ( x ) 1 e x ,当 x [0 ,1]时有： 10
表明，要使
，只x*要xn 1
1 1Lxn1xn
1.
因此，当取 (1时L，)由1 就能保证 x* xn 1.
xn1xn
2021/4/10
25
2021/4/10
26
***1***
2021/4/10
27
2021/4/10
***2***
28
2.2.5 迭代法的收敛阶
对非线性方程 f(x)=0 求解，我们可选取不同的迭代函数。 即使由这些迭代函数产生的迭代序列都收敛，它们也会有 快慢之分。如何反映迭代序列收敛的快慢呢？这就要引进 迭代法收敛阶的概念。
x*xn 11Lxn1xn.
（2.6) （证明见P25略）
2021/4/10
23
证：将满足方程的解的 相减，由所给条件并用
等式 x * g ( x * )与迭代格式 x n 1 g ( x n ) 微分中值定理可得
x * x n 1 g ( x * ) g ( x n ) g ' ( ) x * x n ， U ( x * , )。
2021/4/10
11
2021/4/10
12
五. 二分法的优缺点 1.二分法简单有效，它所对求方程根的函f 数 (x),
仅要求在有根区间上续连。

弦截法
弦截法是一种改进的迭代方法 ，通过将非线性方程转化为线 性方程来求解根。
弦截法的迭代公式为 $x_{n+1}=x_nfrac{f(x_n)}{f(x_n)-f(x_{n-1})}$ ，其中$f(x)$为非线性方程。
弦截法的优点是无需计算函数 的导数，但收敛速度较慢，且 需要选择合适的迭代初值。
04
迭代法的优点是简单易 行，但收敛速度较慢， 且需要选择合适的迭代 初值。
牛顿法
牛顿法是一种基于泰勒级数的迭代方 法，通过线性化非线性方程来求解根 。
牛顿法的收敛速度较快，但需要计算 函数的导数，且在接近根时可能会产 生震荡。
牛顿法的迭代公式为$x_{n+1}=x_nfrac{f(x_n)}{f'(x_n)}$，其中$f(x)$为 非线性方程。
步长与收敛性的关系
深入研究步长与算法收敛性的关系，以找到最佳的步长调整策略。
THANKS FOR WATCHING
感谢您的观看
这类方程在某些区间上具 有不同的非线性性质，例 如 $|x| = y$。
非线性方程的特性
不存在通用解法
与线性方程不同，非线性 方程没有统一的解法，需 要根据具体方程的特点选 择合适的解法。
解的复杂性
非线性方程的解通常比线 性方程复杂，可能存在多 个解或不存在解，也可能 存在混沌解。
对初值和参数敏感
线性方程
如果一个方程中未知数的最高次 幂为一次，并且没有未知数的幂 ，那么这个方程就是线性方程。
非线性方程的分类
01
02
03
代数非线性方程
这类方程中包含未知数的 幂，例如 $x^2 + y^3 = 1$。
超越非线性方程