当前位置：文档之家 › 应用数值分析课件-6.3迭代法的收敛定理

应用数值分析课件-6.3迭代法的收敛定理

  • 格式：ppt
  • 大小：330.50 KB
  • 文档页数：2

下载文档原格式

  / 2

合集下载

第5节_迭代法的收敛性

第5节_迭代法的收敛性
x ≠0
Bx x
≥
Bx1 ቤተ መጻሕፍቲ ባይዱ1
= 1,与已知矛盾！
线性方程组迭代法收敛性
推论1：对任意初始向量x (0)和右端项g，若 M < 1, 由迭代式 x ( k +1) = Mx ( k ) + g产生的向量序列{ x ( k ) }收敛.
证明：矩阵范数性质3：ρ ( A) ≤ || A ||
迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向 量及右端项无关。 对同一方程组，由于不同的迭代法迭代矩阵不同，可能 出现有的方法收敛，有的方法发散的情形。
且至少有一个i值，使上式中不等号严格成立，则称A为弱 对角占优阵。若对所有i，上式不等号均严格成立，则称A 为严格角占优阵。
定义：如果矩阵A不能通过行的互换和相应的列互换成 A11 为形式 A = 0 A12 ,其中A11，A22为方阵，则称A为不可约。 A22
1 1 0 2 1 0 P = I13 例： A = 1 1 0 PT AP = 0 1 1 → 0 1 2 0 1 1
k →∞
证：设u为A特征值λ对应的特征向量， 则：Ak u = λ Ak -1u =...=λ k u 即：λ k为矩阵Ak的特征值。
ρ 所以：（Ak） [ ρ ( A)]k =
线性方程组迭代法收敛性
1- ρ ( A) > 0， 2 定理：设A为任意n阶方阵， 存在矩阵范数 ，使得 则对任意正数ε , 存在矩阵 1 + ρ ( A) A ≤ ρ ( A) + ε = <1 范数 ，使得： 2 证： 充分性：若ρ ( A) < 1 ，取ε = 则有： A = 0 lim
Gauss-Seidel迭代收敛性：

数值分析23迭代法的收敛性

数值分析23迭代法的收敛性
１，故应先求迭代矩阵。而
1 2 2
A 1 1
1
2 2 1
故A分解后的各矩阵分别为
1
D
1
1
0 0 0
L
1
0
0
2 2 0
0 2 2
U 0 0 1 0 0 0
Jacobi迭代法的迭代矩阵为
0 2
1 2 2
2 A 1 1
2 2 1
0 2 1
于是迭代矩阵为
0 2 2
M (D L)1U 0 2 3 0 0 2
其特征方程为
2 2 | I M | 0 2 3 ( 2)3 0
0 0 2
故 (B) 2 1,
所以Gauss-Seidel迭代法发散。
请思考: (1) 若 记 不 住 Jacobi 迭 代 法 和 GaussSeidel迭代法的矩阵表示，怎么写出迭 代矩阵？
Ax b ,
其中A
9 3
4 10
显然Aˊ是严格对角占优阵，因此对方程组
Ax b 用Jacobi法和Gauss-Seidel法均收敛。
例 3 ： 设 A=(aij) 是 二 阶 方 阵 ， 且 a11a22≠0. 试 证 求 解 方 程 组 Ax=b 的 Jacobi 法 与 Gauss-Seidel 法 同时收敛或发散。
注：定理表明，迭代法收敛与否只决定于迭代 矩阵的谱半径，与初始向量及方程组的右 端项无关。对同一方程组，由于不同的迭 代法迭代矩阵不同，因此可能出现有的方 法收敛，有的方法发散的情形。
举例：解方程组
x1 x1
2x2 2x3 x2 x3 2
1
2 x1 2 x2 x3 3
讨论Jacobi法与Gauss-Seidel法的收敛性。

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

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

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

数值分析23迭代法的收敛性

数值分析23迭代法的收敛性
k
充分性: 若 ( A) 1, 取 1 ( A) 0
2
则存在一种矩阵范数||.||，使得
|| A || ( A) 1 ( A) 1
2 而 || Ak |||| A ||k 于是
lim || Ak || lim || A ||k 0
k
k
所以
lim Ak 0
k
二、迭代法的收敛条件
ln(
)
x(1) x(0)
x(1) x(0) k
ln B
下面对一些特殊的系数矩阵给出几个常用的判 断收敛的条件。
定义：若n阶方阵 A=(aij)满足
n
| aii | | aij |
(i 1,2,..., n)
j 1 ji
且至少有一个 i 值，使上式中不等号
严格成立，则称A为弱对角占优阵。
若对所有 i，不等号均严格成立，则 称A为严格对角占优阵。
例如：
10 1 2 矩阵 A 1 10 2 是严格对角占优阵
1 1 5
2 1 0 不是严格对角占优阵 矩阵 B 1 2 1
0 1 2
设有线性方程组Ax=b，下列结论成立：
1. 若A为严格对角占优阵，则Jacobi迭代法和 Gauss-Seidel迭代法均收敛。
例2：设方程组Ax=b的系数矩阵为
A
3 9
10 4
则 Jacobi 法 与 Gauss-Seidel 法 的 迭 代 矩 阵分别是
B
0 9/
4
10 / 3 0
M
0 0
10 / 3 15 / 2
其谱半径分别为
(B) 30 , (M ) 15
2
2
故这两种迭代法均不收敛。

第六章 迭代法-数值分析

第六章 迭代法-数值分析
1 j n
由极限存在准则得 即
k
lim xi( k ) xi =0
k
(i 1, 2, , n)
, n)
lim xi( k ) xi
(i 1, 2,
定义：设{ A( k ) }为n阶方阵序列，A为n阶方阵，如果 lim A( k ) A 0
k
其中 为矩阵范数，则称序列{ A( k ) }收敛于矩阵A，记为 lim A( k ) A


g
n
其中bij
aij aii
, (i j , i, j 1, 2,
, n), g i
bi (i 1, 2, aii
, n).
迭代公式x ( k 1) Bx ( k ) g (k 0,1, 2, )用方程组表示为
(k ) (k ) (k ) ( k 1) b13 x 3 b1n x n g x b 1 12 x 2 1 (k ) (k ) (k ) ( k 1) b 23 x 3 b 2 n x n g x2 b 21 x 1 2 ( k 1) (k ) (k ) (k ) b n1 x1 b n 2 x 2 b n,n 1 x n 1 g x n n 因此，在Jacobi迭代法的计算过程中，需同时保留两个
k k
即x是方程组Ax b的解。
引入误差向量
k
(k ) (k ) lim x x lim 0 所以 等价于 k

( k 1)
x
( k 1)
x
由
x ( k 1) Mx ( k ) g
x Mx g
则可得

( k 1)

第六章6.3迭代法的收敛性

第六章6.3迭代法的收敛性

一阶定常迭代法的收敛性
det 1 det( I B J) 2 2

2
2 3 1 0
所以
( B max(| |) 0 1 0 J)
即Jaobi迭代法收敛。
8
一阶定常迭代法的收敛性
(2) 求Gauss-Seidel法的迭代矩阵
j 1 j i 1 j i 1
14
i 1
n
n
如果 | | 1 ,则有
| | | a | | | | a | | a | ii ij ij
j 1 j i 1 i 1 n
则 [(DL )U] 为严格对角占优矩阵
从而 det[ ( D L ) U ] 0
16
补充例题
例：方程组
x1 x2 b1 x1 2x2 b2
(1)写出解该方程组的Jacobi迭代的迭代
阵，并讨论迭代收敛的条件；
(2)写出解该方程组的G-S迭代的迭代阵，
并讨论迭代收敛的条件。
17
补充例题
例：AX=b为二阶线性方程组， 证明：解该方程组的Jacobi迭代与G-S迭 代同时收敛或同时发散。
的充要条件为： (B ) 1
5
一阶定常迭代法的收敛性
例：判别下列方程组用Jacobi迭代法和G-S 法求解是否收敛。
1 2 2 x1 1 1 1 1 x2 1 2 2 1 x 1 3
6
一阶定常迭代法的收敛性
由于 B 的形式不易确定 , G
13
B 的特征值 满足 det( I B ) 0 G G
即

迭代法的收敛性

迭代法的收敛性
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,由迭代

《迭代法及其收敛性》课件

《迭代法及其收敛性》课件
猜测一个初始解，作 为迭代的起点。
2 建立迭代公式
根据问题的特性和已 知条件，建立迭代公 式。
3 判断迭代是否收敛
判断迭代得到的解是 否足够接近真实解， 停止迭代。
迭代法的例子
牛顿迭代法
用于求解方程的数值方 法，通过不断迭代逼近 方程的根。
埃特金迭代法
用于求解线性方程组的 数值方法迭代法
用于求解线性方程组的 数值方法，通过不断迭 代逼近方程组的解。
迭代法的收敛性
收敛性是指迭代得到的解越来越接近真实解，而收敛速度是指迭代得到的解 的收敛速度有快有慢。
收敛速度的度量方法
1 零点误差
迭代得到的解与真实 解之间的差距。
2 牛顿数列
迭代得到的解之间的 差值的变化规律。
3 收敛阶
《迭代法及其收敛性》 PPT课件
迭代法及其收敛性
迭代法是一种求解数值问题的方法，通过反复迭代得到更精确的解。这个PPT 课件将讲解迭代法的定义、步骤、例子以及收敛性的度量方法。
什么是迭代法？
迭代法是一种求解某些数值问题的方法，从一个猜测的解开始，通过反复迭 代得到更精确的解。
迭代法的步骤
1 猜测初始解
迭代得到的解的收敛 速度的量化指标。
如何判断迭代是否收敛？
1 绝对误差减小
迭代得到的解的绝对 误差逐渐减小。
2 相对误差减小
迭代得到的解的相对 误差逐渐减小。
3 后验估计准则
通过计算后验估计准 则判断迭代的结果是 否满足要求。
总结
1 迭代法是一种常用的数值求解方法 2 收敛性和收敛速度是迭代法的重要评价指标 3 判断迭代收敛的方法有多种，需要根据问题具体情况选择

《迭代法的收敛定理》课件

《迭代法的收敛定理》课件
《迭代法的收敛定理》 PPT课件
探索迭代法的基本概念、原理和应用，了解其令人着迷的收敛性质和常见的 收敛定理，并深入分析和实践应用。
迭代法的基本概念
通过逐步逼近的方式解决学问题。了解如何选取初始值和迭代函数，掌握迭代过程和迭代序列的特点。
迭代法的原理和应用
深入理解迭代法的工作原理，及其在数值计算和优化问题中的广泛应用。探 索迭代算法的灵活性和效率。
收敛定理的证明方法
介绍证明收敛定理的常见方法，如数学归纳法、反证法和递推关系法。演示具体应用并讨论证明的合理性。
例题分析和实践应用
通过实际例题的分析和解决，加深对迭代法和收敛定理的理解。展示迭代法 在实践中的应用和效果。
迭代法的收敛性质
研究迭代法的收敛性质，包括局部收敛、全局收敛和收敛速度。掌握如何评估和优化迭代算法的收敛性。
收敛定理的定义
介绍收敛定理的概念和定义。了解不同类型的收敛定理，如不动点定理、收敛性判别定理等。
常见的收敛定理
详细说明常见的收敛定理，如Banach不动点定理、Newton-Raphson法的收敛 性等。展示定理的应用和实例。

迭代的收敛判据

迭代的收敛判据

迭代的收敛判据
正文：
迭代的收敛判据
在数学中，迭代法是一种解方程的方法，其基本思想就是将原问题转
化为形式相同但某些参数具有不同数值的几个问题。

每个问题的解都
由前一个问题的解按某种递推式得到。

通过不断递推，问题的解趋于
一个固定值的过程就称为迭代过程。

而迭代的收敛性判定则是判断迭
代过程是否能收敛到期望解的关键。

根据迭代法理论，一个迭代过程是否收敛，是与迭代函数的奇异性有
关的。

如果该函数在某个区间上单增且有上界，或单减且有下界，则
收敛性得以保证。

而如果迭代函数不具备这些性质，就需要通过其他
方式进行收敛性判定。

一种较为通用的收敛判据是柯西收敛准则。

柯西收敛准则是指一个数
列收敛当且仅当它满足柯西收敛条件，即对于任意的正数ϵ，存在正整
数N，使得当n，m≥N时，|an−am|<ϵ成立。

直观来说，就是数列的每
一项和相邻两项之间的差距越来越小，最终达到一个稳定的值。

此外，迭代收敛性还与待求解方程的性质相关。

以求解一元方程f(x)=0为例，其迭代公式为xn+1=g(xn)。

若f(x)在某个区间上单峰且具有单调性，那么迭代一定收敛，且收敛速度越快。

若不具备单峰性和单调性，
则需要将其转化为具有这些性质的方程组，才能通过迭代法求解。

总之，迭代法是一种非常有效的解方程的方法，也是数学中的重要理论之一。

在应用迭代法时，一定要注意选择合适的迭代公式和收敛判据，才能保证迭代过程的收敛性和计算精度。

数值分析二分法迭代法及收敛性优秀课件

数值分析二分法迭代法及收敛性优秀课件
定义1 设(x)有不动点x*，如果存在 x* 的某个邻
域U: |x-x*|≤δ，对任意x0∈U，迭代公式(2.2)产生 的序列{xk}∈U，且收敛到 x*，则称迭代法(2.2)局部 收敛.
定理3 设x*为(x)的不动点，( x)在x*的某个邻 域连续，且 ( x ) 1，则迭代法(2.2)局部收敛.
其中系数ai(i=0,1,,n)为实数.
n=1,2时方程的根是大家熟悉的，n=3,4时虽有求 根公式但比较复杂，可在数学手册中查到，但已不适 合数值计算，而n≥5时就不能用公式表示方程的根.因 此，通常对n≥3的多项式方程求根与一般连续函数方 程(1.1)一样都可采用迭代法求根.
注：
方程f(x)=0的根 x*，又称为函数f(x)的零点，它使得 f(x*)=0，若f(x)可分解为
若f(a) ·f(x0)<0, 则x*∈(a, x0), 令 a1= a, b1=x0;
若f(x0) ·f(b)<0, 则x*∈(x0 , b), 令 a1=x0, b1=b.
不论出现哪种情况, (a1, b1)均为新的有根区间, 它 的长度只有原有根区间长度的一半, 达到了压缩有根 区间的目的.
如此反复进行, 即可的一系列有根区间套
x*
y
y=(x) p0
x x1
y=x
p1
x x0 x* x1
注：迭代法的研究涉及四个问题：
(1)迭代公式的选取； (2)迭代公式收敛性的判定； (3)在收敛情况下，如何比较收敛速度； (4)迭代停止的条件。
3.2.2 不动点的存在性与迭代法的收敛性
首先考察(x)在[a, b]上不动点的存在唯一性.
lim
k
xk
x.
当(x)连续时，显然x*就是方程 x=(x)之根(不动点).

迭代法的收敛定理

迭代法的收敛定理
返回节
二、Jacobi 迭代法和Gauss-Seidel迭 代法的收敛条件
Some convergence theorem of Jacobi and Guass-Seidel method for linear system With special matrix A 引子 对角占优矩阵 实例 相关定理 定理3.3的证明
定理3.4
若A为对称正定阵，则G-S迭代法收敛。
Theorem 3.4 If A is symmetry and positive definitive matrix, then for any choices of x0, Guass-Seidel methods converge to the unique solution 0f Ax=b
2.解线性方程组AX b的Jacobi Seidel 迭代法 收敛的充分条件是 Sufficient conditions BJ 1 1
(BG ) 1
;
其中

BJ D
1
BG

。
1
L U ,
BG D L U

在一般情况下，计算矩阵的范数比计算谱半径省事， 所以通常是利用定理3.2进行判断。 但定理3.2只是充分条件，所以即使判断失效， 迭代法仍可能收敛，这时就应该使用定理3.1判断。
Application to Jacobi and Guass-Seidel method: 将定理3.1和3.2用于Jacobi迭代法及Seidel迭代 法，则有
1. 解线性方程组AX b的Jacobi Seidel 迭代法 收敛的充要条件是 Necessary and sufficient conditions ( BJ ) 1

数值计算中的迭代方法与收敛性

数值计算中的迭代方法与收敛性

数值计算中的迭代方法与收敛性迭代方法在数值计算中起着重要的作用，它通过逐步逼近解决了很多复杂的数学问题。

本文将探讨数值计算中的迭代方法以及它们的收敛性。

一、迭代方法的基本原理迭代方法是通过不断重复逼近的过程来求解问题的一种数值计算方法。

其基本原理是从一个初始值开始，通过迭代公式不断逼近目标值，直至满足预设的收敛条件。

通常情况下，迭代方法可以应用于求解方程、优化问题等。

二、常见的迭代方法1. 不动点迭代法不动点迭代法是迭代方法中最常见的一种。

其基本思想是将原问题转化为寻找一个函数的不动点，即函数自身在某点上的取值等于该点本身。

通过选择适当的迭代函数，不动点迭代法可以有效地求解方程或优化问题。

2. 牛顿迭代法牛顿迭代法是一种高效的求解方程的方法。

其核心思想是利用函数的局部线性近似来逼近方程的解。

通过迭代公式不断逼近方程的根，牛顿迭代法可以在较短的时间内获得较高的精度。

3. 雅可比迭代法雅可比迭代法是一种用于线性方程组求解的迭代方法。

它通过将方程组表示为矩阵乘法的形式，将解向量的每个分量都表示为先前迭代解的线性组合。

通过不断迭代更新解向量的各个分量，雅可比迭代法可以逐步逼近方程组的解。

三、迭代方法的收敛性分析迭代方法的收敛性是判断该方法是否能够求解准确解的重要指标。

常用的收敛性分析方法有局部收敛性和全局收敛性。

1. 局部收敛性局部收敛性是指在迭代过程中，当初始值选择在某个特定的范围内时，迭代方法能够收敛到准确解。

局部收敛性通常通过迭代函数的导数来分析，若导数满足一定条件，则可以判断方法具有局部收敛性。

2. 全局收敛性全局收敛性是指迭代方法对于任意初始值都能够收敛到准确解。

全局收敛性是迭代方法的理想性质，但在实际应用中很难满足。

对于某些迭代方法，可以通过收敛域的定义和分析来判断其全局收敛性。

四、迭代方法的应用与改进迭代方法在数值计算中有着广泛的应用，涉及到方程求解、优化、插值等领域。

尽管迭代方法具有很多优点，但也存在一些问题，如收敛速度慢、迭代公式复杂等。

数值分析6-3 §3 迭代法的收敛性

数值分析6-3 §3 迭代法的收敛性

下面的定理对建立迭代法的收敛条件十分重要.
定理：设A为n阶方阵，则
lim Ak 0
k
的充要条件为 ( A) 1
证明：必要性。若 lim Ak 0
k
则 lim || Ak || 0
而
k
0 (
Ak
)
[( A)]k
||
Ak
||
于是由极限存在准则，有
பைடு நூலகம்
lim[( A)]k 0 故 ( A) 1
谱半径为
( Ak
)
max{|
1in
ki
|}
[( A)]k
定理：设A为任意n阶方阵，||.||为任意由向量
范数诱导出的矩阵的范数，则
( A) || A ||
证明：对A的任一特征值λi 及相应的特征向量 ui，都有
| i | || ui || || iui |||| Aui || || A || || ui ||
定义：如果矩阵A不能通过行的互换和相应列 的互换成为形式
A11 A12
0
A22
其中A11，A22为方阵，则称A为不可约.
例如：判断下列矩阵是否可约？
1 1 0
2 1 0
矩阵 A 1 1 0 是可约的。 0 1 1
0 1 2
0 1 1
交换第1与3行(列)
1 2 2
矩阵 A 1 1
1
注：定理表明，迭代法收敛与否只决定于迭代 矩阵的谱半径，与初始向量及方程组的右 端项无关。对同一方程组，由于不同的迭 代法迭代矩阵不同，因此可能出现有的方 法收敛，有的方法发散的情形。
举例：解方程组
x1 x1
2x2 2x3 x2 x3 2
1

迭代解法(全章)讲解ppt课件

迭代解法(全章)讲解ppt课件

10/18/2023
第六章 线性方程组的迭代解法
21
§3 常用的三种迭代解法
一、 Jacobi迭代法
对于线性方程组 Ax=b
(1)
设 det(A)≠ 0 ，aii ≠ 0,i=0,1,2,…,n ，按照如下方式对A
进行分裂：
A=L+D+U
(2)
10/18/2023
第六章 线性方程组的迭代解法
22
则由 Ax=b 得到 (L+D+U) x=b >D x=-(L+U)x+b
或 向量序列 {x(k)} 收敛于向量 x* ，当且仅当它的每一 个分量序列收敛于x* 的对应分量，即
10/18/2023
第六章 线性方程组的迭代解法
7
二、矩阵的范数
矩阵范数是反映矩阵“大小”的一种度量，具体定义如下。 定义6.3 设||·||是以n阶矩阵为变量的实值函数，且满足 条件：
(1) || A ||≥0，且|| A ||＝0时，当且仅当A＝0
矩阵1-范数：
列和
矩阵2-范数：
矩阵∞-范数：
行和
以上三种范数都满足矩阵范数的条件，通常将这三种 矩阵范数统一表示为||A ||p，P＝1 ，2 ，∞。
10/18/2023
第六章 线性方程组的迭代解法
9
例6.2 设矩阵
求矩阵A的范数||A ||p，P＝1 ，2 ，∞ 。 解 根据定义
由于 则它的特征方程为:
25
对于 n 元线性方程组 其一般式为：
从中解出：
得Jacobi迭代格式
通过|| x(k+1)-x(k)||<ε 控制迭代次数。
10/18/2023

迭代法的收敛条件

迭代法的收敛条件

(3 24)
(M ) 1
(k )
［证明］ 设存在n 维向量 x* 使得 则
x
*
lim x
满足
p9
k
x

*
x Mx g
7

解线性方程组的迭代法
由迭代公式(3-24),有
( k 1) g Mx g M ( x( k 1) x ) x ( k ) x Mx M 2 ( x( k 2) x ) M k ( x ( 0 ) x )
例３也说明了
0 2 确实只是松弛法
的情形.
收敛的必要条件，而非充要条件，因为Gauss-Seidel 迭代即为
1
定理3.6虽然给出了判别迭代法收敛的充要条件， 但实际使用是很不方便 。因为求逆矩阵和特征值的 难度并不亚于用直接方法求解线性方程组。推论１与 推论２使用起来方便得多， 但它们分别给出收敛的 充分条件与必要条件，许多情形下，不能起作用.
det( M)
( D L) 1 (1 ) D U
1
1 ( D L) a11a22 ann
(1 ) D U (1 )n a11a22 ann
n ( 1 ) 1 所以 于是有 det( M )
0 2
11
解线性方程组的迭代法
22
10 1 2 例: 考虑 Ax b, 其中 A 1 10 2 1 1 5
解线性方程组的迭代法
A为严格对角占优阵，故Jacobi迭代法与Gauss-Seidel
迭代均收敛.
又如例２中，系数矩阵
2 1 0 A 1 2 1 0 1 2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
([保障措施] 高速计算机能胜任那些程序简单、 重复量大的迭代计算，况且还有许多加速收敛 的办法做保障。)
返回节
OK! Let’s have a break!
定理
2
一、基本收敛定理
由 可推知
可见
X(k+1)=BX(k)+f 及 X *=B X *+f
εk+1 = X (k+1) - X *= B（X (k) - X *）
= ·············
= B k+1（X(0) -X *）
=
B
k+1
ε 0
X(k) X* B k 0
(k∞ )
利用矩阵的Jordan标准形，可以证明(前一章中的结论)
无法直接判断Jacobi 迭代法和G-S迭代法的收敛性，但如果将
方程组的次序修改为
11.02.20x11x1
9.05x2 4.33x2
0.12x3 2.67x3
1.43 3.22
1.25x1 3.69x2 12.37x3 0.58
由于系数矩阵A是严格对角占优阵，因此用Jacobi 迭代
反复利用 || X (k+1) - X*||=||BX (k)- BX*||=||B(X (k)- X*)|| ≤‖B‖.‖X (k)- X*‖,
可以得到
||X (k)- X*||≤‖B‖k ·‖X(0)- X*‖，
可见X (0)越接近X*，序列{ X (k)}收敛越快，收敛速度 与初值X (0)的选取有关。
对于给定的线性方程组，借助于定理6.3和定理6.4可以 直接判断Jacobi 迭代法和G-S迭代法的收敛性。
但同时应当注意，迭代法收敛与否与方程组中方程排列 顺序有关，如线性方程组
11.205.0x11 x1
3.69x2 9.05x2
12.37x3 0.58 0.12x3 1.43
1.22x1 4.33x2 2.67x3 3.22
第六章 线性方程组迭代解法
§ 6.3 迭代法的收敛定理
基本数学问题描述
迭代法的收敛性，是指方程组
AX b
从任意初始向量X(0)出发，由迭代算法
X (k1) BX (k ) f
算出向量序列
X (1) , X (2) , , X (k) , X (k1) ,
随着k的增加而趋向于解向量X *。
记各次误差向量
例如 设有线性方程组 X=BX+f，其中
0.9 0.0
B
0.3 0.8
1 f
2
考察迭代法 X (k+1)=B X(k)+f 的收敛性。
解：
由于 B 1.2, B 1.02, B 1.1, B 1.54 均大于
1
2
F
1，故定理3.2在此无法判断；
但因为
λ 1
=0.9,
λ2=0.8,即ρ(B)
而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。
迭代法程序简单，对于许多问题，收敛较快。 因而，有时能够解决一些高阶问题。 但应注意， 对于某些问题，迭代法可能发散或收敛很慢， 以致失去使用价值。这种情况下，仍以采用直 接法为宜。
只要断定系数矩阵满足收敛条件，尽管多次迭 代计算工作量大一些，却能达到预定精度。
BJ
max
aij
a 1in 1 jn, ji ii
由严格对角占优定义（定义6.1 ），得 BJ ∞<1,所以, Jacobi 迭代法收敛。
下面证明G-S迭代法的收敛性。对于严格对角占优阵A， 其对角元素 aii ≠ 0 ， i=1,2,,n（定义6.1 ），故
n
det( D L) aii 0 i 1
=0.9<1,由定理3.1知
本题迭代法收敛。
返回节
二、Jacobi 迭代法和Gauss-Seidel 迭代法的收敛速度
引子 对角占优矩阵 实例 相关定理 定理3.3的证明
返回节
引子
虽然利用定理6.1和定理6.2可以判定Jacobi 迭代 法和G-S迭代法的收敛性，但其中只有定理6.2对 Jacobi 迭代法使用比较方便，此外，对于大型方程 组，要求出G-S迭代矩阵BG和ρ(BG)以及Jacobi 迭代 矩阵BJ和ρ(BJ)都不是容易的事。
这里介绍一些判定收敛的充分条件，它们是利 用原方程组系数矩阵A和迭代矩阵B的特殊性质建立 的，很实用，用起来也很方便。这些判定定理也都 是以定理3.1和定理3.2为基础的。
对角占优矩阵
如果线性方程组AX=b的系数矩阵A具有某种特殊性质 （如对称正定、对角占优等），则可从A本身直接得出某 些迭代法收敛性结论。
注：
1. 定理6.1为判断迭代法的收敛性提供 了强有力的手段： 注意是充分必要条件！
2. 定理6.1的条件往往不易验证： 矩阵的谱半径不易求出！
3. 利用谱半径的有界性可以给出另外一 个条件较弱的结果： 即定理6.2
定理3.2 迭代法收敛的充分条件 如果 B 1，则对任意
初始向量 X0，迭代法 Xk1 BX k f
定义6.1 如果矩阵A满足条件
aii aij
ji
则称A是严格对角占优阵；
(i 1,2,L ,n)பைடு நூலகம்(2)
如果矩阵A满足条件
aii aij (i 1, 2,L , n) (3)
ji
且其中至少有一个不等式严格成立，则称A是弱对角占优阵。
实例
例如 其中
8 3 2 A 4 11 1
2 1 4
严格对角占优性质，有
n
i 1
n
aii
aij aij aij , i 1, 2,L , n
j1, ji
j 1
ji 1
这说明矩阵
a11 a11 L
(D
L)
U
a21
a22
L
L
O
a11
a11
an1
an2
L
ann
是严格对角占优阵，所以它是非奇异的，即
det((D-L)-U) 0与特征值满足det((D-L)-U) =0 矛盾。
0 X X (0) 1 X X (1)
k X X (k)
显然，迭代法的收敛性与误差向量序列
0,1, ,k ,
随着k的增加而趋向于零向量是等价的。
由于精确解X *自然满足
X BX f
因此有
X X (k1) B X X (k)
或
k1 B k
再递推出
k Bk0
所以矩阵（D-L）为可逆下三角矩阵，其逆也是下三角矩阵， G-S迭代法的迭代矩阵是 BG =(D - L)-1U。
考虑BG的特征值λ，其特征方程为
det(I-BG) = det(I-(D-L)-1U)
= det(D-L)-1det((D-L)-U)=０
=>det((D-L)-U)=0
我们通过A的严格对角占优性质去证明det((D-L)-U)=0 的根有性质 | |<1。用反证法：假设| |≥1，且由于A的
另一方面，由于ρ(B) ≤‖B‖<1，‖B‖越小， 说明ρ(B) 越小，序列{ X (k)}收敛越快。
收敛速度的概念
下面我们给出收敛速度的概念： 定义6.1 R(B)= -lnρ(B)，称为迭代法的渐进 收敛速度。
将定理6.1和6.2用于Jacobi迭代法及Seidel迭代法， 则有
1. 解线性方程组AX b的JacobiSeidel迭代法
法和G-S迭代法求解该方程组均收敛。
定理6.3的证明
证 首先证明Jacobi 迭代的收敛性。由
0
BJ D 1 (L U ) aaa22n121
a12 a11 0
an2
a1n a11
a2n a22
,
0
b1
a11
b2
fJ
ab2n2
ann
ann
ann
易求
Bk 0 B 1
其中, B叫做B的谱半径。
若B的特征值为1，L n ,则
(B)
B
max
1in
i
定理3.1 迭代法收敛的充要条件 设有线性
方程组
X BX f，
则对于任意的初始向量 X (0)，迭代法
X (k1) BX k f
收敛的充分必要条件是
B 1 。
定理3.1表明，线性方程组迭代法收敛与否 与 X (0)和 f 的取值无关，而只与迭代矩阵 B 的 性质有关。
必收敛，且有
X * X (k) B X (k) X (k1) (1) 1 B
矩阵A的谱半径不超过矩阵的任何一种算子范数!
进一步，我们可以推知：
X (k) X * B k X (1) X (0) 1 B
式(1)说明，当||B||<1 且不接近1并且相邻两次 迭代向量X(k+1) 与 X (k)很接近时，则X(k)与精确解X * 很接近。因此，在实际计算中，用|| X (k+1) - X (k) ||≤ε作为迭代终止条件是合理的。
收敛的充要条件是
(BJ ) 1
(BG ) 1 ;
2.解线性方程组AX b的JacobiSeidel迭代法
收敛的充分条件是
BJ 1
BG 1 。
其中 BJ D1L U , BG D L1U
在一般情况下，计算矩阵的范数比计算谱半径省事， 所以通常是利用定理6.2进行判断。
但定理6.2只是充分条件，所以即使判断失效， 迭代法仍可能收敛，这时就应该使用定理6.1判断。
故
<1 即ρ(BG) <1，
G-S迭代法收敛。
定理得证。
返回章
注意的问题
（1）Jacobi迭代法和Gauss-Seidel迭代法的 迭代矩阵不同：