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

37第七节 迭代法及其收敛性

  • 格式：ppt
  • 大小：422.50 KB
  • 文档页数：11

下载文档原格式

  / 11

合集下载

几类特殊线性代数方程组的迭代解法及其收敛性分析的开题报告

几类特殊线性代数方程组的迭代解法及其收敛性分析的开题报告

几类特殊线性代数方程组的迭代解法及其收敛性分析的开题报告一、选题的背景和意义线性代数是数学中的一个重要分支，它在科学和工程中都有很广泛的应用。

线性方程组在生产和科学技术中的应用非常广泛，例如在物理、统计学、计算机科学、经济学、金融等领域中广泛使用。

然而，由于线性方程组通常是大规模的、复杂的，并且往往没有解析解，因此迭代方法是解决此类方程组的主要方法之一。

特殊的线性方程组是具有特殊结构的方程组，例如对角占优、对称正定、三对角等。

这些特殊的结构使得方程组的求解更具有可行性和稳定性，因此针对这些结构，设计相应的迭代方法具有理论和实际的重要性。

本文将研究这些特殊线性代数方程组的迭代解法及其收敛性分析，探究不同的迭代方法在不同的情况下的优缺点，并分析不同方法的收敛性，这对于理论和实践都具有重要意义。

二、研究内容和研究方法本文研究内容为各种特殊线性方程组的迭代解法及其收敛性分析，包括对角占优线性方程组、对称正定线性方程组、三对角线性方程组等。

本文将重点研究以下几种方法：1. Jacobi迭代法：Jacobi迭代法是一种基本的迭代方法，主要用于解对角占优线性方程组。

该方法的思路是将原方程组转化为x = Bx + g的形式，并进行迭代求解。

2. Gauss-Seidel迭代法：Gauss-Seidel迭代法是Jacobi迭代法的变种，也是基于x = Bx + g的思路，但是它可以利用已经求得的解来加快求解的速度。

3. SOR迭代法：SOR迭代法是在Jacobi和Gauss-Seidel迭代法的基础上发展而来的加速算法，该方法引入一个松弛因子来加速收敛。

4. CG迭代法：CG迭代法是一种用于求解对称正定线性方程组的迭代方法，它可以利用矩阵的对称性和正定性来加速求解。

5. TDMA迭代法：TDMA迭代法是一种用于求解三对角线性方程组的迭代方法，该方法利用三对角矩阵的特殊结构来简化矩阵运算，从而加速求解。

本文将运用数学分析、计算机仿真和实验比较等方法，对以上几种迭代方法的收敛性和求解速度进行深入研究。

迭代法的收敛性与稳定性 - 松弛迭代法、迭代法的收敛性与稳定性

迭代法的收敛性与稳定性 - 松弛迭代法、迭代法的收敛性与稳定性
Bk 0(零矩阵)(k )
定义 6.5 设有矩阵序列 Ak (aij(k ) ) Rnn 及 Ak (aij ) Rnn ，如果 n2 个数列极限存在
且有
lim
k
a (k) ij
aij
(i,
j
1,2,..., n)
则
Ak
称收敛于
A
记为 lim(k
)
。
定理 6.5
lim
k
Ak
A
lim
三 松弛法例题与程序
例 6.9 取 1.4, x(0) (1,1,1)T 用超松弛法解方程组
2x1 x2
1
x1 2x2 x3 0
x2 2x3 1.8
� � 解：由 xi(k1)
(1 )xik
aii
(bi
i 1 j 1
a x(k 1) ij j
n
aij
x
(k j
x j(k ) ) / aii xi(k )
j i
j i 1
i 1
n
(bi aij x j(k 1) aij x j(k ) ) / aii
ji
ji
(i 1,, n; k 0,1,).
� � i1
n
xi
b x(k 1) ij j
bij
x(k) j
gi
x(k) i
j 1
j i 1
a x(k1) ij j
aij x(jk ) ) / aii .
j 1
j i 1
(2) 再由 x(k) 与 ~xi(k 1) 加权平均定义 xi(k 1) ，即
x(k 1) i
(1 )xi(k)
x%i(k 1)

37第七节 迭代法及其收敛性

37第七节 迭代法及其收敛性
x(k) x q x(k) x(k1) 1q
x(k) x qk x(1) x(0) 1q
证 因 (B)||B||=q<1, 所以迭代格式收敛, 且有 设 lim x (k) =x*，由 x(k+1) = Bx(k) + f ， 得 x* = Bx* + f ，则
数学学院 信息与计算科学系
又 || Bk|| ||B||k ，有 lim||Bk||=0 ， 故 lim B k =0，由1）知，迭代格式收敛。
数学学院 信息与计算科学系
三、迭代法的收敛速度
考察误差向量
e(k) =x(k) -x＊=Bk ·e(0)
设B有n个线性无关的特征向量及相应的特征值为
1 ,2 , ,n ,
1 , 2 , , n
数学学院 信息与计算科学系
2） 由1)知，迭代格式收敛 lim Bk=O ， 即lim||Bk||=0 ，从而存在 k ，使 || B k || <1，由谱半径 的性质有
[( B )]k = (B k ) ||B k ||<1，
故得
( B )<1，
因(B)=inf{||B||}且(B)<1，存在 >0及使 || B || ( B )+ <1，
取对数得 定义3 称
k s ln10
ln (B)
R(B) ln (B)
为迭代法 x(k+1) = Bx(k) + f 的收敛速度。 由此看出，当(B)<1愈小，速度R(B)就愈大，
所需要的迭代次数也就愈少。
数学学院 信息与计算科学系
定理 2 若 ||B||=q<1，则对任意x(0) 迭代格式 x(k+1) = Bx(k) + f 收敛 ，且有误差估计式

7.2 迭代法及其收敛性

7.2 迭代法及其收敛性

1 2 3 4 5 6 7 8 9 10 30 40 45
1.358484290 1.355301399 1.355302727 1.355301425 1.355301394
由上表数据可看出，若取迭代函数为(c )， (d )和 (e )三种情形，算法表现良好，均能较快得到方程 的近似根.
下面讨论用迭代的方法求 ( x )的不动点x * .取 方程(7.2.1)解的初始近似值x0 , 通过如下迭代
xk xk 1 , k 1,2,, 产生迭代序列 xk . (7.2.2)
如果序列 xk 收敛到x * ,即 lim xk x * ,因 ( x )
x k x * x k 1 x * L x k 1 x * L x k 2 x L x0 x .
* k *
2

7.2.3
由0 L 1可得 lim Lk 0,因此对上式取极限可得
k
lim xk x * lim Lk x0 x * 0
4 x 在[1,2] 的值域为[ 1.6, 2].此外
(7.2.1)
其中 ( x )为连续函数,其取法不唯一,例如可取
方程(7.2.1)的解称为函数 ( x )的不动点, 求方程 (7.2.1)的解的问题称为不动点问题.
因此, 对于方程f ( x ) 0,为求出它的一个实根, 常 常将其化为求解等价的不动点问题,因为不动点 问题的形式往往更易于分析求解.
但对于情形(a )，迭代序列发散;在情形(b)中， 出现负数开根号，从而迭代不能继续下去.
因此, 迭代函数 ( x )的选取将会对迭代过程的收 敛性产生很大的影响.事实上, 要使迭代法产生的序 列 xk 收敛,则迭代函数 ( x )应满足一定的条件.

数值计算方法 迭代法及其收敛性 - 迭代法及其收敛性

数值计算方法 迭代法及其收敛性 - 迭代法及其收敛性

x*
lim
k
x
k
1
lim
k
(
xk
)
(lim k
xk
)
( x* )
故k充分大时，xk可作为方程根的近似值
按上述方法构造迭代格式来求解方程的方法称为简单迭代法或逐
次迭代法。
不动点迭代法： 将方程 f ( x) 0 改写为: x ( x).
1 若要求x*满足f ( x* ) 0,则x* ( x* );反之亦然，
重点
实多项式方程
f ( x) a0 x n a1 x n1 an1 x an (a0 0),
的求根问题.
（其中系数ai (i 0,1,, n)为实数）
若 方程f ( x*) 0, 则x*称为函数f ( x)的零点
1
若方程 f (x) (x x* )m g(x),
其 中m为 正 整 数 ， 且g( x* ) 0.
真真解解：：xx==1.13.234274272
典型例题
例3
用不同方法求方程x2 3 0的根x* 3.
(1) xk1 xk2 xk 3,(x) x2 x 3
(2)
xk 1
3 xk
,(x)
3, x
(3)
xk 1
xk
1 4
( xk2
3), ( x)
x
1 4
(x2
3)
(4)
xk 1
1 2
典型例题
(2)
xk1
3 xk
,(x)
3, x
( x* ) 1
(3)
xk 1
xk
1 4
(
x
2 k
3),( x)
x
1 (x2 4

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

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

迭代法和收敛性


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)

3.7 收敛与收敛阶- w


P x p 1
p
P
P
矩阵的谱半径
矩阵范数同矩阵特征值之间有密切的联系，设λ 是矩阵A相应于特征向量x的特征值，即 Ax＝λx,于 是利用向量-矩阵范数的相容性，得到
|λ| || x ||=||λx|| =|| Ax|| ≤ || A || ||x||
从而，对A的任何特征值λ均成立 |λ|≤|| A ||
x(k ) x* B x(k) x(k1) 1 B
x(k ) x* B k x(1) x(0) 1 B
现在讨论使误差减少初始误差的 倍所需的最
少迭代次数。
x(k) x* B k x(0) x*
若要求 x(k) x* x(0) x*
则 B k (B)k
复习
设向量x＝(x1，x2，…，xn)T，定义
向量1-范数： 向量2-范数： 向量无穷范数：
n
x 1 xi i 1
1
x
2
n i 1
x
2 i

2

x

max 1i n
xi
设 n 阶矩阵 A＝（aij），常用的矩阵范数有：
Hale Waihona Puke 矩阵1-范数：n A
1
max 1 j n
3.7迭代法及其收敛性
3.7.2 迭代法的收敛性
利用迭代公式构造序列x(k), 以求 得方程组
的近似解的算法称为解式的简单迭代法。
若迭代序列 x ( k ) 收敛，则称此迭代法是收敛的。
xk1 Bxk f , x* Bx* f
两式相减，知误差向量 xk x* 满足下列迭代关系：
k
Ak

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
*
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
从而 ||x(k+1) -x(k)|| =||(x(k+1) -x*)-(x(k) -x*)|| ||x(k) -x*||-||x(k+1) -x*|| ||x(k) -x*||-q||x(k) -x*||
=(1-q) ||x(k) -x*||
数学学院 信息与计算科学系
故得
1 q ( k 1) (k ) x x x x x ( k ) x ( k 1) 1 q 1 q k q q x ( k ) x x ( k ) x ( k 1) x (1) x(0) 1 q 1 q


数学学院 信息与计算科学系
二、迭代法的收敛性
定义2 如果
lim A
k
k
(k )
A O
则称矩阵序列｛A(k)｝依范数收敛于A，记
lim A( k ) A
由范数的等价性可以推出，矩阵序列｛A(k)｝ 依某种范数收敛，则依任何一种范数它都收敛，故 下面不强调是在那种范数意义下收敛。
x
k 1
Bx( k ) f
k 0,1,2
其中B称为迭代矩阵。
数学学院 信息与计算科学系
若序列｛x(k)｝收敛，即
lim x ( k ) x
k
显然有
x Bx f
此极限 x＊就是方程组 Ax=b 的解。 定义1 如果序列｛x(k)｝的极限存在(记 x＊)， 则称迭代法收敛，x＊就是方程组 Ax=b 的解，否则 称此迭代法发散。
数学学院 信息与计算科学系
x(k+1) -x*= B( x(k) -x* ) , x(k+1) –x(k)= B( x(k) –x(k-1) )
即有
x ( k 1) x B x ( k ) x q x ( k ) x
x ( k 1) x ( k ) B x ( k ) x ( k 1) q x ( k ) x ( k 1)
j 1 j 1 k j
n
可以看出，当(B)<1愈小时， jk 0(k ) 愈 快，即 e ( k ) 0 愈快，故可用(B)来刻画迭代法收 敛速度的快慢。
数学学院 信息与计算科学系
现在来确定迭代次数k，使
s ( B ) 10 k
取对数得 定义3 称
(k )
有了误差估计式，在实际计算时，对于预先给 定的精度 ，若有
x ( k 1) x ( k )
则就可以认为x(k+1)是方程组满足精度的近似解. 此 外，还可以用第二个式子来事先确定需要迭代的次 数以保证 ||e(k)||<。
Ax b 为方程组Ax=b 的解，即
k
lim x k x
数学学院 信息与计算科学系
把矩阵A 分解成矩阵N 和P 之差，即 A=N-P 其中N为非奇异矩阵，于是，方程组 Ax=b 便可以表 示成 Nx=Px+b 即有 1 1 x N Px N b Bx f 1 1 其中 B N P; f N b 据此，我们便可以建立迭代公式
q x x ( k ) x ( k 1) 1 q

x(k+1) = Bx(k) + f 收敛，且有误差估计式
x( k )
k q x x (1) x (0) 1 q
证 因 (B)||B||=q<1, 所以迭代格式收敛, 且有 设 lim x (k) =x*，由 x(k+1) = Bx(k) + f ， 得 x* = Bx* + f ，则
数学学院 信息与计算科学系
三、迭代法的收敛速度
考察误差向量 e(k) =x(k) -x＊=Bk ·e(0) 设B有n个线性无关的特征向量及相应2 ,, n
k n
由 得
e (0) a j j
e
(k )
B e
j 1 k (0)
aj B j aj j
数学学院 信息与计算科学系
2） 由1)知，迭代格式收敛 lim Bk=O ， 即lim||Bk||=0 ，从而存在 k ，使 || B k || <1，由谱半 径的性质有 故得 [( B )]k = (B k ) ||B k ||<1， ( B )<1，
因(B)=inf{||B||}且(B)<1，存在 >0及使 || B || ( B )+ <1， 又 || Bk|| ||B||k ，有 lim||Bk||=0 ， 故 lim B k =0，由1）知，迭代格式收敛。
数学学院 信息与计算科学系
定理1
1） 迭代格式 x(k+1) = Bx(k) + f 收敛 lim Bk=O； 2） 迭代格式 x(k+1) = Bx(k) + f 收敛 ( B )<1。 1） 设 lim x(k) =x*， 则 x* = Bx* + f ,
证
x(k+1) -x*= B( x(k) -x*)， x(k) -x*= Bk( x(0) -x*) ， 故 lim x (k) =x* lim Bk=O；
s ln10 k ln ( B )
R( B) ln ( B)
为迭代法 x(k+1) = Bx(k) + f 的收敛速度。 由此看出，当(B)<1愈小，速度R(B)就愈大， 所需要的迭代次数也就愈少。
数学学院 信息与计算科学系
定理 2
x
(k )
若 ||B||=q<1，则对任意x(0) 迭代格式
数学学院 信息与计算科学系 第七节 迭代法及其收敛性
一、迭代法的一般格式
前面介绍了解线性方程组 Ax=b 的一些直接方法， 下面介绍解方程组的另一类方法—迭代法。 所谓迭代法就是对任意给定初始近似 x 0 , 按某种 规则逐次生成序列 x 0 , x 1 , x 2 x k , 使极限