当前位置：文档之家 › 第七节 迭代法及其收敛性

第七节 迭代法及其收敛性

  • 格式：ppt
  • 大小：93.00 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

线性方程组迭代法收敛性分析

线性方程组迭代法收敛性分析
k
lim Ak 0 .
k
(2.27)
由定理 2.5 知，
( A k ) Ak ，
即
( A)
由(2.27) 和(2.28)可得
k
Ak .
(2.28)
lim ( A) 0
k k
再由矩阵谱半径的定义可知一定有 ( A) 1 . （必要性） 若 ( A) 1 ，则有定理 2.5 的推论可知至少存在一个 0 使得一种范数
若有
lim x ( k ) x* , 即 lim xi( k ) xi* ,
k k
则有 lim x ( k ) x*
k 2
0.
常见的向量范数有： ① 1-范数
x 1 xi ；
i 1
n
② ∞-范数
x

max xi ；
1 i n
③ 2-范数
x 2 ( x ) ；
lim x x* lim G k x x* 0 ，
k
0
k


k


再由向量范数的定义可知
lim x k x* 0 ，
k
即迭代过程收敛. （必要性） 若迭代公式(2.20)收敛，即满足
lim x x* 0
k k


由此推论可知当 ( A) 1 时，至少存在一种范数 A 1 .
定 理 2.6 设 A R nn ， 则 lim Ak 0 的 充 要 条 件 为 ( A) 1 . （ 其 中
k
Ak AA A）
k
证明： （充分性） 若 lim Ak 0 ，则由矩阵范数的定义可知

7.2 迭代法及其收敛性

7.2 迭代法及其收敛性

k4.1045
1/ 2
表 7.2.1 用不动点迭代法计算例7.2.1的结果
0 (a) 1.5 -0.625 6.447 -378.2 5.3697e7 -1.547e23 (b) 1.5 0.912871 2.454577 (c) (d) (e) 1.5 1.5 1.5 1.241638702 1.333333333 1.365079365 1.424290116 1.305205188 1.387624336 1.332682451 1.370291856 1.344991115 1.362217505 1.350582520 1.358732441 1.355350555 1.354767869 1.355301399 1.355384418 1.355301398 1.355288480 1.355303407 1.355301085 1.355301446 1.355301390
*
k
xk x L x0 x L max x0 a , b x0 ,
* k * k
从而 7.2.4 成立.
再由 7.2.3 , 对m k 1, 我们有
x m x k x m x m 1 x m 1 x m 2 x k 1 x k x m x m 1 x m 1 x m 2 x k 1 x k Lm 1 x1 x0 Lm 2 x1 x0 Lk x1 x0 Lk x1 x0 1 L L2 Lm k 1 .
(7.2.1)
其中 ( x )为连续函数,其取法不唯一,例如可取
方程(7.2.1)的解称为函数 ( x )的不动点, 求方程 (7.2.1)的解的问题称为不动点问题.

不动点迭代法及其收敛定理

不动点迭代法及其收敛定理
03
收敛速度取决于迭代函数在不动点附近的性质，如导数的大 小和符号等。
不动点迭代法的收敛定理
存在唯一不动点的定理
如果迭代函数在某个区间上单 调，那么该区间上存在唯一的
不动点。
收敛定理
对于任意初值$x_0$，迭代序 列$x_{n+1}=f(x_n)$会收敛到
不动点，当且仅当存在常数 $k$使得$|f'(x)| leq k < 1$在 包含不动点的某个区间上成立。
算法的改进和优化
改进现有不动点迭代法
研究现有方法的不足之处，并提出改进方案 ，以提高收敛速度和稳定性。
开发新的不动点迭代法
基于新的数学原理和方法，开发新的不动点迭代法 ，以解决现有方法无法解决的问题。
实现不动点迭代法的并行 化和分布式化
研究如何利用并行计算和分布式计算技术， 提高不动点迭代法的计算效率和可扩展性。
这种方法是将求解区域划分为粗细不 同的网格，并在每个网格上应用不动 点迭代法，以加速收敛。
改进迭代格式
修正不动点迭代法
通过引入修正项，改进不动点迭 代法的格式，以提高收敛速度和 稳定性。
广义极小残量法
这种方法是在不动点迭代法的基 础上，引入残量概念，并构造出 新的迭代格式，以提高求解非线 性方程组的精度和稳定性。
松弛法
粗细网格结合法
通过选择适当的迭代矩阵，可以加速 不动点迭代法的收敛速度。常用的加 速迭代法包括预条件迭代法和共轭梯 度法等。
松弛法是一种通过引入松弛因子来调整迭代矩 阵的方法，以加快收敛速度。常用的松弛法包 括SOR（Successive Over-Relaxation）方法 和SSOR（Symmetric Successive OverRelaxation）方法等。Part05不动点迭代法的未来研究方向

第七节 迭代法及其收敛性

第七节 迭代法及其收敛性

证 1）设 lim x (k) =x*， 则 x* = Bx* + f ,
上页 下页 返回
第三章 第七节
x (k+1) -x*= B( x (k) -x*)， x (k) -x*= B k( x (0) -x*) ， 故 lim x (k) =x* lim B k =O；
2） 存在 k ，使 || B k || <1，
[( B )]k = (B k ) ||B k ||<1，
故
( B )<1，
因 ( B )=inf {|| B || }，存在 >0 使
|| B || ( B )+ <1， 又 || B k || ||B ||k ，
故
lim B k =0。
上页 下页 返回
三 迭代法的收敛速度
第三章 第七节
定理 2 若 ||B ||<1，则迭代格式
|| x(k) x || 1 || x(k1) x(k) || || B || || x|
|| x(k) x || || B || || x(k) x(k1) || || B ||k || x(1) x(0) ||
1 || B ||
其中 B N 1P ; f N 1b
上页 下页 返回
第三章 第七节
据此，我们便可以建立迭代公式 xk1 Bx f k 0,1,2
我们称此迭代公式中的B 为迭代矩阵
二 迭代法的收敛性
定理1
1） 迭代格式 x(k+1) = Bx(k) + f 收敛 lim B k =O；
2） 迭代格式 x(k+1) = Bx(k) + f 收敛 ( B )<1。
x(k+1) = Bx(k) + f 收敛 ，且

迭代法和收敛性

迭代法和收敛性

x1(k x2(k
1) 1)
0.2x2(k) 0.1x3(k) 0.3
0.2x1(k )
0.1x3(k) 1.5 , k
0,1, 2,
x3(k
1)
0.2x1(k )
0.4x2(k )
2
迭代计算
x(0) 0 [0, 0, 0]T
x(1) 1
0.3
x(1) 2
1.5
x1(k x2(k
其中系数矩阵非奇异，且主对角元aii≠0，(i
=1,2,…,n)，由第i 个方程解出xi，有
x1
1 a11
(b1
a12 x2
a13 x3
x2
1 a22
(b2
a21x1
a23x3
xn
1 ann
(bn
an1x1
an2 x2
a1n xn ) a2n xn )
ann1xn1)
建立迭代格式
aij
x
( j
k
)
)
j i 1
加速
x ( k 1) i
( k 1)
xi
(1 ) xi(k )
i 1, 2, , n
或合起来写成迭代加速的形式
x (k 1) i
aii
(bi
i 1
a x (k 1) ij j j 1
n
aij
x
(k j
)
)
(1
)
xi( k
)
j i1
参数 称为松弛因子， 1 时迭代格式就是高斯-
x (k1) i
1 aii
(bi
n
aij x j(k ) ),
j1
(i 1,2,, n)

7、解非线性方程的迭代法

7、解非线性方程的迭代法

(1.1)
2. 超越方程, 如 : x e x 0.
如果f ( x)可以分解为 f ( x) ( x x*)m g ( x), 其中0 | g ( x*) | , m为正整数. 则称x * 为f ( x)的m重零点.
此时 f ( x*) f ( x*) f ( m 1) ( x*) 0, f ( m) ( x*) 0.
k 0 1 2 3 4 5 6 7 xk 1.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472
3 (2) xk 1 xk 1, x0 1.5, x1 2.375, x2 12.39, .
二、不动点的存在性与迭代法的收敛性
二、斯蒂芬森迭代法
把不动点迭代与埃特金加速技巧结合，得到斯蒂芬森 ( Steffensen)迭代法 yk ( xk ), zk ( yk ),
( yk xk ) 2 xk 1 xk zk 2 yk xk
改写为另一种不动.4)
k 0 1 2 3 ‫׃‬ xk x0 x1 x2 x3 ‫׃‬ 迭代法(1) 2 3 9 87 ‫׃‬ 迭代法(2) 2 1.5 2 1.5 ‫׃‬ 迭代法(3) 2 1.75 1.73475 1.732631 ‫׃‬ 迭代法(4) 2 1.75 1.732143 1.732051 ‫׃‬
定义2 设迭代过程xk 1 ( xk )收敛于x*,误差ek xk x*, 若 lim
例6 求方程3x 2 e x 0在[3,4]中的解.
解： 取对数得x 2 ln x ln 3 g ( x)， 构造迭代法 xk 1 2 ln xk ln3 2 2 ( x) , max ( x) 1, 当x [3,4], ( x) [3,4], x 3 x 4 3 由定理2迭代收敛. x0 3.5, x16 3.73307 .

2.2 迭代法的一般形式与收敛性定理


设aii0 (i=1,2,,n)，并将A写成三部分
0 a11 a 21 0 a 22 A a n 1 ,1 a n 1 , 2 0 a nn a n 2 a n , n 1 a n1 0 a12 a1,n1 a1n 0 a 2 , n 1 a 2 n 0 a n 1, n 0 D LU. 0
则
k
B ( H )
k
两边取对数得: k ln ( H ) ln k
ln ln ( H )
定义:
ln ( H )
为迭代法(2.2.3)的渐近收敛速 度。
解线性方程组的迭代法
线性方程组
a11 x1 a12 x2 a x a x 21 1 22 2 an1 x1 an 2 x2 a1n xn b1 a2 n xn b2 ann xn bn
复习：矩阵的谱半径 设λ是矩阵A相应于特征向量x的特征值，即 Ax＝λx 向量-矩阵范数的相容性，得到 |λ| || x ||=||λx|| =|| Ax|| ≤ || A || ||x|| 从而，对A的任何特征值λ均成立 |λ|≤|| A || （ 3）
设n阶矩阵A的n个特征值为λ1,λ2，…λn，称 ( A) max i
x ( k 1) x* H ( x ( k ) x* )
由此递推：x ( k 1) x* H k 1 ( x ( 0) x* ), k 0,1,2,
x 是线性方程组Ax=b的解
x* Hx* g
x
k 1
*

迭代法的收敛性

k
x* Mx* g 由迭代公式有 M (x
k k
x ( k ) x* Mx ( k 1) g Mx* g
( k 1)
x ) M (x
* 2 * k
( k 2) (k )
x ) M (x
* k
(0)
x )
*
于是有 lim M ( x
1 1 例：Ax b, A 2 1 2
1 2 1 1 讨论用三种迭代法求解的收敛性。 2 1 1 2 解：因A为对称且其各阶主子式皆大于零，故A为对称正定矩 1 2 阵。由判别条件3，Gauss-Seidel迭代法与松弛法(0 2) 均收敛。A不是弱对角占优阵，故不能用条件1判断。 0 1 -1 Jacobi迭代法的迭代矩阵为B I - D A 2 1 2 1 2 0 1 2 1 2 1 2 0

1,
1,由推论1无法判别收敛性。
对一些特殊的系数矩阵可给出几个常用的判 别收敛条件
设有线性方程组Ax b, 下列结论成立（收敛充分条件） 1.若A为严格对角占优阵或不可约弱对角占优阵，则 Jacobi迭代法和Gauss-Seidel迭代法均收敛。 2.若A为严格对角占优阵， 0 1, 则松弛法收敛。 3.若A为对称正定阵，则松弛法收敛的充要条件为 0 2。 10 1 2 2 1 0 B 1 2 1 上两例中： A 1 10 2 1 1 5 0 1 2 A为严格对角占优阵，故Jacobi与Gauss-Seidel迭 代均收敛。B为非严格对角占优阵，但为对称正定 阵， =1.4故松弛法收敛。
推论1 对任意初始向量x 和右端项g，若 M 1,由迭代

牛顿迭代法收敛定理

关于牛顿迭代法的课程设计实验指导非线性方程（或方程组）问题可以描述为求 x 使得f (x ) = 0。

在求解非线性方程的方法中，牛顿迭代法是求非线性方程（非线性方程组）数值解的一种重要的方法。

牛顿是微积分创立者之一，微积分理论本质上是立足于对世界的这种认识：很多物理规律在微观上是线性的。

近几百年来，这种局部线性化方法取得了辉煌成功，大到行星轨道计算，小到机械部件设计。

牛顿迭代法正是将局部线性化的方法用于求解方程。

一、牛顿迭代法及其收敛速度牛顿迭代法又称为牛顿-拉夫逊方法（Newton-Raphson method ），是一种在实数域和复数域上通过迭代计算求出非线性方程的数值解方法。

方法的基本思路是利用一个根的猜测值x 0做初始近似值，使用函数f (x )在x 0处的泰勒级数展式的前两项做为函数f (x )的近似表达式。

由于该表达式是一个线性函数，通过线性表达式替代方程中的求得近似解x 1。

即将方程f (x ) = 0在x 0处局部线性化计算出近似解x 1，重复这一过程，将方程f (x ) = 0在x 1处局部线性化计算出x 2，求得近似解x 2，……。

详细叙述如下：假设方程的解x *在x 0附近（x 0是方程解x *的近似），函数f (x )在点x 0处的局部线化表达式为)()()()(000x f x x x f x f '-+≈由此得一次方程 0)()()(000='-+x f x x x f求解，得 )()(0001x f x f x x '-= 如图1所示，x 1比x 0更接近于x *。

该方法的几何意义是：用曲线上某点（x 0，y 0）的切线代替曲线，以该切线与x 轴的交点（x 1，0）作为曲线与x 轴的交点（x *，0）的近似（所以牛顿迭代法又称为切线法）。

设x n 是方程解x *的近似，迭代格式)()(1n n n n x f x f x x '-=+ ( n = 0，1，2，……) 就是著名的牛顿迭代公式，通过迭代计算实现逐次逼近方程的解。

线性方程组的迭代解法及收敛分析

2.8098
1.9583
0.8468
0.2974
9
1.0975
2.0954
2.8217
1.9788
0.8847
0.2533
10
1.0850
2.0738
2.8671
1.9735
0.8969
0.2041
11
1.0673
2.0645
2.8802
1.9843
0.9200
0.1723
12
1.0577
2.0509
2.9077
1.9828
0.9303
0.1400
13
1.0463
2.0437
2.9191
1.9887
0.9448
0.1174
14
1.0392
2.0350
2.9363
1.9886
0.9527
0.0959
15
1.0318
2.0297
2.9451
1.9920
0.9620
0.0801
16
1.0267
2.0241
Keywords：MATLAB,Mathematical model,Iterative method,ConvergenceSystem of linear equations
1
在实际生活中，存在着大量求解线性方程组的问题。这些方程组具有数据量大，系数矩阵稀疏，在一定精度保证下，只需要求解近似解等特点。线性方程组的迭代解法特别适合于这类方程组的求解，它具有程序设计简单，需要计算机的贮存单元少等特点，但也有收敛性与收敛速度问题。因此，研究线性方程组的迭代解法及收敛分析对于解决实际问题具有非常重要的作用。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
上页 下页 返回
第三章 第七节
x(k+1) -x*= B( x(k) -x* ) , x(k+1) –x(k)= B( x(k) –x(k-1) )
从而
||x(k+1) -x(k)|| =||( x(k+1) -x*)-( x(k) -x*)||
|| x(k) -x* ||-|| x(k+1) -x*|| 故
[( B )]k = (B k ) ||B k ||<1，
B )=inf {|| B || }，存在 >0 使
|| B || ( B )+ <1， 又 || B k || ||B ||k ，
故
lim B k =0。
上页 下页 返回
三 迭代法的收敛速度
第三章 第七节
定理 2 若 ||B ||<1，则迭代格式
|| x(k) x || 1 || x(k1) x(k) || || B || || x(k) x(k1) ||
1 || B ||
1 || B ||
|| x(k) x || || B || || x(k) x(k1) || || B ||k || x(1) x(0) ||
1 || B ||
1 || B ||
上页 下页 返回
其中 B N 1P ; f N 1b
上页 下页 返回
第三章 第七节
据此，我们便可以建立迭代公式 xk1 Bx f k 0,1,2
我们称此迭代公式中的B 为迭代矩阵
二 迭代法的收敛性
定理1
1） 迭代格式 x(k+1) = Bx(k) + f 收敛 lim B k =O；
2） 迭代格式 x(k+1) = Bx(k) + f 收敛 ( B )<1。
x(k+1) = Bx(k) + f 收敛 ，且
|| x(k) x || || B || || x(k) x(k1) || 1 || B ||
|| x(k) x || || B ||k || x(1) x(0) || 1 || B ||
证 因 ( B ) || B||< 1，所以迭代收敛。
设 lim x (k) =x*，由 x(k+1) = Bx(k) + f ， 得 x* = Bx* + f ，则
第三章 第七节
第七节 迭代法及其收敛性
一 迭代法的一般格式
所谓迭代法就是对任意给定初始近似 x0 , 按某种 规则逐次生成序列 x0, x1, x2 xk ,
使极限
lim xk x
k
为方程组Ax=b 的解，即 Ax b
矩阵A 分解成矩阵N 和P 之差 A=N-P 其中N为非
奇异矩阵，于是方程组 Ax=b 便可以表示成 Nx=Px+b 即 x N 1Px N 1b Bx f
证 1）设 lim x (k) =x*， 则 x* = Bx* + f ,
上页 下页 返回
第三章 第七节
x (k+1) -x*= B( x (k) -x*)， x (k) -x*= B k( x (0) -x*) ， 故 lim x (k) =x* lim B k =O；
2） 存在 k ，使 || B k || <1，