当前位置：文档之家 › 2.2 迭代法的一般形式与收敛性定理

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

  • 格式：ppt
  • 大小：367.00 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

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 收敛 ，且有误差估计式
2.2 迭代法

2.2 迭代法


= ϕ ' (ξ )( x * − x * *) ≤ L x * − x * *
又， L < 1
⇒ x* = x * *
计算方法
② ∀x0 ∈ [a, b] 则 xk +1 − x *= ϕ ( xk ) − ϕ ( x*) = ϕ ' (ξ )( xk − x*)
≤ L xk − x * ≤ L2 xk −1 − x * x k +1 − x *
计算方法
二、收敛性分析
定理2.1 （全局收敛定理） 全局收敛定理） 定理
在区间[a,b]上可导 上可导 设ϕ ( x )在[a, b] 在区间
a （1）当a ≤ x ≤ b时， ≤ ϕ ( x ) ≤ b;
( 2) ∀x ∈ [a, b], | ϕ ' ( x ) |≤ L < 1 ( L为常数） 为常数）
ϕ ′( x ) ≤ L < 1
计算方法
则对于任意的初始值 x0 ∈ S ，由迭代公式 收敛于方程的根。 产生的数列 { xn } 收敛于方程的根。 （这时称迭代法在 α 的S邻域具有局部收敛性。） 邻域具有局部收敛性。）
x n +1 = ϕ ( x n )
Remark1：全局与局部收敛定理中的条件都是充分 Remark1： 条件，条件满足则迭代法收敛，不满足则不能判定， 条件，条件满足则迭代法收敛，不满足则不能判定， 此时可以用试算来判定迭代法的是收敛性。 此时可以用试算来判定迭代法的是收敛性。
p! p!
由迭代公式 xk +1 = ϕ ( xk ) 及 x * = ϕ ( x * ) 有 ϕ ( p ) (ξ ) * * p
′( x* ) = ϕ ′′( x* ) = L = ϕ ( p−1) ( x* ) = 0, ϕ ( p ) ( x* ) ≠ 0 ϕ 邻域是p阶收敛的。 则迭代过程在 x * 邻域是p阶收敛的。
数值分析第四章 解非线性方程的迭代法

数值分析第四章 解非线性方程的迭代法


即
(xk+1-α)2≈(xk-α)(xk+2-α) xk+12-2xk+1α+α2≈xkxk+2-(xk+xk+2)α+α2
解得
x k x k + 2 x k2+1 α≈ x k + 2 2 x k +1 + x k
( x k +1 x k ) 2 = xk x k + 2 2 x k +1 + x k
可见,|xk-xk-1|充分小可保证|xk-α|充分小, 而且对任 一ε>0,要使|xk-α|<ε, 只要 k > ln ε (1 L) ÷ ln L x1 x 0
证 记(x)=(x)-x,则(a)=(a)-a≥0, (b)=(b)b≤0, 由(x)的连续性,必存在α∈[a,b]使(α)=(α)-α=0, 即α=(α), 又′(x)=′(x)-1<0, 所以x=(x)的根唯一. |xk+1-xk|=|(xk)-(xk-1)| =|′(ξ)(xk-xk-1)|≤L|xk-xk-1| |xk+1-α|=|(xk)-(α)|=|′(ξ)(xk-α)|≤L|xk-α| |xk-α|=|(xk-xk+1)+(xk+1-α)| ≤|xk-xk+1|+|xk+1-α|≤L|xk-xk-1|+L|xk-α| 于是有:
k 0 1 2 3 4 5 xk 0.5 0.60653 0.54524 0.57970 0.56006 0.57117 |xk-xk-1| 0.10653 0.06129 0.03446 0.01964 0.01111 k 6 7 8 9 10 xk 0.56486 0.56844 0.56641 0.56756 0.56691 |xk-xk-1| 0.00631 0.00358 0.00203 0.00115 0.00065
迭代法和收敛性

迭代法和收敛性


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

迭代法的收敛性

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

迭代法的收敛性


即
det[I (D L)1U ] 0
从而 det(D L)1 det[(D L) U ] 0
所以
det[(D L) U ] 0
可得
因为
|aii| |aij | ji
i1
n
|||aii||| |aij ||| |aij |
j1
j i 1
i1
n
n
|| |aij| |aij| (||1) |aij|
(1)写出解该方程组旳Jacobi迭代旳迭代
阵，并讨论迭代收敛旳条件；
(2)写出解该方程组旳G-S迭代旳迭代阵， 并讨论迭代收敛旳条件。
17
补充例题
例：AX=b为二元线性方程组， 证明：解该方程组旳Jacobi迭代与G-S迭 代同步收敛或同步发散。
18
9
特殊方程组迭代法旳收敛性
4 1 1 问题：该矩阵具有怎样旳特点？
2 5 1 1
2
3
结论：该矩阵是严格对角占优阵
定义：假如矩阵A旳元素满足
jn
| aii | | aij | i 1,2,3,, n j 1 ji
则称A为严格对角占优矩阵。
10
特殊方程组迭代法旳收敛性
定理：若线性方程组AX=b旳系数矩阵A为 严格对角占优矩阵，则解该方程组旳Jacobi 迭代法和G-S迭代法均收敛。
2
一阶定常迭代法旳收敛性
则: (k 1) B (k ) B 2 (k 1) B k 1 (0)
注意 (0) x(0) x * 为非零常数向量
所以迭代法收敛旳充要条件
lim (k1) lim( x(k1) x*) 0
k
k
可转变为
lim Bk1 0
2.2 迭代法

2.2 迭代法

* lim | x xk | 0 要证结论(1)成立，即要证 k
首先用归纳假设证明如下不等式
| x* xk | Lk | x* x1 |
38
当k=1时 x x1 L x x0 ，已证成立。
k 1 x x L x x0 成立，可得 假设 k 1
不动点迭代的几何解释 y=f(x)=x y=g(x)
38
不动点判定定理
设g是一连续函数，且 { pn } 是由不动点迭代 n 0
生成的序列。若 lim pn p ，则p是g(x)的不动点
n
pn 1 p pn p ，则 lim 证：lim n n
g ( p ) g (lim pn ) lim g( pn ) lim pn1 p
1 1 x xk x k 1 x k ( x k ) ( x k 1 ) 1 L 1 L L Lk x k x k 1 x1 x0 1 L 1 L

L越小，收敛越快
38
不动点迭代的图形解释
一般来说从 f ( x ) 0 , 构造 ( x )不止一种，有的
38
由介值定理，存在 x [a , b] 使 f ( x ) 0


即
x ( x ).
②设方程 x ( x ) 还有一根 , 即 a (a ). 则由微分中值定理有
x ( x ) ( ) ( )( x ) L x
x4 2x 2 x 3 0 x 2 ( x)
x 4 1
x 3 ( x) x4 2x2 3
(其中第二式 x4 2 x 2 1=x 4 )
迭代解法全章

迭代解法全章


向量-矩阵范数旳相容性，得到
|λ| || x ||＝||λx|| =|| Ax|| ≤ || A || ||x||
从而，对A旳任何特征值λ均成立 |λ|≤|| A ||
（6.1）
设n阶矩阵A旳n个特征值为λ1,λ2，…λn。称
(
A)
max
1i n
i
为矩阵A旳谱半径，从（6.1）式得知，对矩阵A旳任何一
称(3)为求解(1)旳近似解旳迭代解法，称{x(k)}为(1)近
似解序列，称B为迭代矩阵。
假如 lim x (k ) x* 则有 k x*= Bx*+F
（4）
我们称迭代法(3)收敛，不然为发散。下面分析迭代格 式(3)收敛旳条件.
12/29/2023
19
x(k+1)= Bx(k)+F , k=0 ,1 , … , x*= Bx*+F
及向量
x*
( x1* ,
x2* ,,
x
* n
)T
假如
lim x(k) x* 0
k
则称向量序列 x(k) 收敛于向量 x* 。记作
lim x(k ) x* 或 x(k ) x*
k
向量序列 {x(k)} 收敛于向量 x*，当且仅当它旳每一 种分量序列收敛于x*旳相应分量，即
x(k)
x*
x(k) i
1
求解线性方程组旳数值解除了使用直接解法，迭代解 法也是经常采用旳一种措施，这种措施更有利于编程计 算，本章将简介这种措施。
§1 向量和矩阵旳范数
为了对线性方程组数值解旳精确程度，以及方程组 本身旳性态进行分析，需要对向量和矩阵旳“大小”引 进某种度量，范数就是一种度量尺度，向量和矩阵旳范 数在线性方程组数值措施旳研究中起着主要旳作用。
Ch2.2 一般迭代法

Ch2.2 一般迭代法


10 1.3247180
近似解 x9 x10 1.3247180 。 (8位有效)
思考：取 x x 3 1 构造迭代， 结果如何？
问题：如何构造迭代函数，可以保证迭代既
收敛，敛速还快？误差如何估计？
一个好的迭代法需要考虑：

迭代函数的构造； 收敛性、敛速； 误差估计。
迭代法的几何意义
(2) g ( x) x 3 1 , x [ 1 , 2 ] ， g ( x) 3x 2 1 ； 由Th 2 ， 该迭代发散。
2、局部收敛
Th3： 设方程x g ( x)有根x *， 且在x *的某个邻域U ( x * , )内
具有一阶连续导数 ， 则 (1) g ( x * ) 1 ， 局部收敛； (2) g ( x * ) 1， 发散。
y
yx
y g ( x)
o
x
*
x2
x1
x0
x
收敛的情形
y
yx
y g ( x)
o
x0 x 2 x 4
x
*
x3 x1
x
收敛的情形
ห้องสมุดไป่ตู้
y
y g ( x)
yx
x2
o
x1
x0 x *
x
发散的情形
迭代法的收敛条件
1、大范围收敛
Th1：（压缩映象原理）
若g ( x)在 [ a , b ] 上具有一阶连续导数 ， 且满足： 1、 x [ a , b] ， 有g ( x) [ a , b ]； 2 、 常数0 L 1 ， 对x ， y [ a , b ] ， 有 | g ( x) g ( y ) | L x y ；
迭代法

迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。

比较典型的迭代法如“二分法”和"牛顿迭代法”属于近似迭代法。

方法介绍迭代法是一类利用递推公式或循环算法通过构造序列来求问题近似解的方法。

例如，对非线性方程，利用递推关系式，从开始依次计算，来逼近方程的根的方法，若仅与有关，即，则称此迭代法为单步迭代法，一般称为多步迭代法；对于线性方程组，由关系从开始依次计算来过近方程的解的方法。

若对某一正整数，当时，与k 无关，称该迭代法为定常迭代法，否则称之为非定常迭代法。

称所构造的序列为迭代序列。

迭代法应用迭代法的主要研究课题是对所论问题构造收敛的迭代格式，分析它们的收敛速度及收敛范围。

迭代法的收敛性定理可分成下列三类：①局部收敛性定理：假设问题解存在，断定当初始近似与解充分接近时迭代法收敛；②半局部收敛性定理：在不假定解存在的情况下，根据迭代法在初始近似处满足的条件，断定迭代法收敛于问题的解；③大范围收敛性定理：在不假定初始近似与解充分接近的条件下，断定迭代法收敛于问题的解。

迭代法在线性和非线性方程组求解，最优化计算及特征值计算等问题中被广泛应用。

迭代法算法迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法（Iterative Method）。

一般可以做如下定义：对于给定的线性方程组（这里的x、B、f同为矩阵，任意线性方程组都可以变换成此形式），用公式（代表迭代k次得到的x，初始时k=0)逐步带入求近似解的方法称为迭代法（或称一阶定常迭代法）。

线性方程组的迭代法

线性方程组的迭代法


1 20 D 1b
1 8
24 1.2 12 1.5 1 15 30 2
x1( k 1) 0 0.1 0.15 x1( k ) 1.2 ( k 2) x ( k ) 1.5 0 0.125 2 x2 0.125 ( ( x3k 1) 0.133 3 0.2 0 x3k ) 2.0
将方程组AX=b的系数A分解成 A=D+L+U 其中D=diag(a11,a22,,ann) ，L和U分别是A的 对角线下方元素和上方元素组成的严格下三角 阵与严格上三角阵. 即

0 0 a2 1 0 A a n1 an 2

0 a1 1 0 0 0 a1 2 0 0 a2 2 0 0 0 0 0 0 an n 0 0

k 1 r k 1 0 0 (k )

所以Gauss-Seidel迭代 法收敛.
定理 超松弛法收敛的必要条件为 0<<2

证 设其迭代矩阵G的特征值为1,2,, n , 由于迭代收敛,故有 max i 1 1 i n 从而 det G 12 n (max i ) n 1
a
j 1 j i
n
ij
aii
n
(i 1,2, , n )
aij aii 1
故
GJ

max
1i n j 1 j i
从而Jacobi迭代收敛

* * * * 设方程组的精确解为 X ( x1 , x2 , xn )

迭代法的收敛性


谱半径分别是 ρ ( B ) =
30 15 , ρ ( M ) = 。均不收敛。 2 2
若交换方程的次序，得 Ax = b的同解方程组 Ax=b,
' '
3 − 10 9 −4 ' A= → A = 3 −10 9 −4 A '为严格对角占优阵，因而对方程组 A ' x = b '用 Jacobi与 Gauss − Seidel 迭代求解均收敛。
k →∞
x* = Mx* + g 由迭代公式有 x ( k ) − x* = Mx ( k −1) + g − Mx* − g = M ( x ( k −1) − x* ) = M 2 ( x ( k − 2) − x* ) = M k ( x (0) − x* ) 于是有 lim M k ( x (0) − x* ) = lim( x ( k ) − x* ) = 0
其特征方程
λ
1 λI − B = 2 1 2
1 2
λ
1 2 1 3 1 3 = λ − λ + 2 4 4
1 λ 2 1 2 = ( λ − ) ( λ + 1) = 0 2
1 , λ 3 = − 1, 因 而 ρ ( B ) = 1 得λ1 = λ 2 = 2 ⇒ J a c o b i迭 代 法 不 收 敛 。
移项得 代入得
(I − M ) x (k ) − x*
−1
1 ≤ 1− M
k
M ≤ 1− M
x (1 ) − x ( 0 ) 。
由误差估计式 x
(k )
−x
*
≤
M
k
1− M
x (1) − x ( 0 )

数值分析中的迭代方法与收敛性分析

数值分析中的迭代方法与收敛性分析迭代方法是数值分析中一种重要的算法，用于求解数值问题。

迭代方法基于一个初始猜测解，并通过不断迭代逼近真实解。

本文将介绍迭代方法的基本原理以及如何进行收敛性分析。

一、迭代方法的原理迭代方法的基本原理是通过不断更新猜测解来逼近真实解。

假设我们要求解一个方程f(x)=0，其中f(x)表示一个函数。

我们可以通过选择一个初始猜测解x0，然后使用迭代公式x_{k+1}=g(x_k)来生成下一个近似解x_{k+1}，其中g(x_k)是一个迭代函数。

通过不断迭代，我们希望逐渐接近真实解。

二、常见的迭代方法在数值分析中，有许多常见的迭代方法被广泛应用于求解不同类型的数值问题。

以下是几种常见的迭代方法：1. 不动点迭代法不动点迭代法通过将方程f(x)=0转化为等价的x=g(x)的形式来求解。

其中g(x)是一个迭代函数，可以通过不断迭代x_{k+1}=g(x_k)逼近真实解。

不动点迭代法的收敛性通常需要满足收敛性条件，如Lipschitz条件或收缩映射条件。

2. 牛顿迭代法牛顿迭代法通过利用函数的导数信息来加速收敛速度。

迭代公式为x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}，其中f'(x_k)表示函数f(x_k)的导数。

牛顿迭代法的收敛性通常需要满足局部收敛性条件，如满足Lipschitz条件和拟凸性条件。

3. 雅可比迭代法雅可比迭代法用于求解线性方程组Ax=b，其中A是系数矩阵，b是常数向量。

迭代公式为x_{k+1}=D^{-1}(b-(L+U)x_k)，其中D、L和U分别是矩阵A的对角线、下三角和上三角部分。

雅可比迭代法的收敛性要求系数矩阵A满足严格对角占优条件。

三、迭代方法的收敛性分析在使用迭代方法求解数值问题时，我们需要进行收敛性分析，以确定迭代方法是否能够逼近真实解。

常用的迭代收敛性分析方法包括：1. 收敛域分析收敛域分析用于确定迭代方法的收敛域，即迭代过程中能够保证收敛的初始猜测解的范围。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

复变函数迭代法的收敛性和稳定性分析

复变函数迭代法的收敛性和稳定性分析复变函数迭代法是数值计算中常用的求解复变函数的数值方法。

在使用复变函数迭代法求解问题时，我们首先将复平面划分为若干个矩形或圆形区域，然后使用迭代公式进行迭代计算，直到达到预定的精度要求或满足一些停止准则为止。

本文将对复变函数迭代法的收敛性和稳定性进行详细的分析。

一、收敛性的分析在复平面上，定义一个函数f(z)，其输入是复数z，输出也是复数。

对于给定的初始值z0，我们通过迭代公式z(n+1)=f(z(n))来进行迭代计算，直到满足一些停止准则为止。

那么我们需要分析迭代过程是否能收敛到问题的解。

下面是收敛性的分析过程。

1.收敛性定理在复平面上，如果函数f(z)是全局收敛的，即对于任意的初始值z0，迭代过程都会收敛到问题的解，那么我们称函数f(z)是全局收敛的。

收敛性定理指出，如果函数f(z)在一些区域R上解析，并且在该区域上的导数，f'(z)，的模不大于1，即，f'(z)，<=1，那么函数f(z)是局部收敛的。

2.收敛半径在复平面上，我们可以通过计算函数f(z)在一些点的导数值，f'(z)，的模来判断收敛性。

当，f'(z)，<1时，该点是函数f(z)的收敛点；当，f'(z)，>1时，该点是函数f(z)的发散点。

收敛半径可以定义为函数f(z)收敛的最大半径，即，z，<R时，函数f(z)是收敛的。

3.收敛域和发散域根据函数f(z)在复平面上的性质，我们可以将复平面分为收敛域和发散域两部分。

收敛域是指函数f(z)在该区域内收敛的点的集合，发散域是指函数f(z)在该区域内发散的点的集合。

二、稳定性的分析稳定性是指在计算过程中的误差是否会扩散和放大。

在复变函数迭代法中，稳定性是一个重要的性质，对于保证计算结果的准确性和可靠性起到关键作用。

下面是稳定性的分析过程。

1.条件数和误差扩散在复变函数迭代法中，函数f(z)的条件数用来衡量函数的敏感性。

迭代法的收敛定理


一、基本收敛定理
The Fundamental convergence theorem
Theorem :for any initial value x (0) R n, the fundamental iterative method defined
by x(k+1)=Bx(k)+f (k=0,1,2,…) converges to the unique solution of x=Bx+f if only if
1.25 x1 3.69 x2 12.37 x3 0.58 10.01x1 9.05 x2 0.12 x3 1.43 1.22 x 4.33x 2.67 x 3.22 1 2 3
无法直接判断Jacobi 迭代法和G-S迭代法的收敛性，但如果 将方程组的次序修改为
对角占优矩阵
diagonally dominant matrix
如果线性方程组AX=b的系数矩阵A具有某种特殊性质 （如对称正定、对角占优等），则可从A本身直接得出某些 迭代法收敛性结论。 定义3.1 如果矩阵A满足条件
aii aij
j i
(i 1,2,
, n)
(2)
则称A是严格对角占优阵(strictly diagonally dominant matrix)； 如果矩阵A满足条件 aii aij (i 1,2, , n) (3)
在偏微分方程数值解中，有限差分往往导出对角占优的 线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵， 因此这两个判断定理是很实用的。 对于给定的线性方程组，借助于定理3.3和定理3.4可 以直接判断Jacobi 迭代法和G-S迭代法的收敛性。 但同时应当注意，迭代法收敛与否与方程组中方程排列 顺序有关，如线性方程组

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

数值计算中的迭代法与收敛性分析数值计算是现代科学技术中不可或缺的一部分，主要解决数学问题的计算和应用问题的模拟。

其中，在数学问题的计算中，经常需要使用迭代法。

本文将从迭代法的基本概念、应用、收敛的定义和分类、收敛性分析以及优化中的迭代法等几个方面论述迭代法与收敛性分析。

一、迭代法的基本概念和应用迭代法是指通过对一个初值的反复迭代求解来逼近某个方程的解或某个函数的极值的方法。

通常来说，迭代法都需要给出迭代序列的计算公式，将初值代入迭代公式计算，得到下一项的迭代结果，不断迭代，直到达到预定的迭代次数或满足收敛精度要求为止。

在数值计算中，迭代法的应用十分广泛，例如求解非线性代数方程、求解常微分方程初值问题、解方程组、求解最优化问题等。

二、收敛的定义和分类在迭代方法求解问题时，我们需要考虑其迭代序列的收敛性问题。

收敛是指迭代序列随着迭代次数的增加，逐渐逼近欲求解的精确解。

在数值计算中，可以用迭代序列中后面几项的误差与该序列最后一项的关系来描述收敛情况。

如果迭代序列中的误差随着迭代次数的增加而逐渐趋于零，那么该迭代序列就是收敛的；反之，如果误差在某个阶段始终无法收敛，那么该迭代序列就是发散的。

按照算法的不同，迭代可以分为简单迭代和牛顿迭代等多种迭代方法。

而根据问题的不同性质，迭代的收敛性可以分为线性收敛和非线性收敛两种情况。

在常见的迭代算法中，如牛顿迭代等，通常都需要对迭代的收敛性进行分析，并根据问题特点选择适当的算法。

三、收敛性分析收敛性分析是数值计算中非常重要的一部分，其主要目的就是分析迭代序列的收敛性，找到迭代公式使其遵循收敛性的要求。

对于某些特定的迭代算法，分析收敛的方法也不相同。

下面我们以简单迭代法和牛顿迭代法两种常见的迭代算法为例，简单分析一下如何对其进行收敛性分析。

（1）简单迭代法的收敛性分析对于简单迭代法，其基本的思路就是对于方程f(x)=0，在x_0处展开泰勒公式，得到x_(k+1)和x_k間的关系式，根据其收敛的条件来选择迭代公式。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

设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
*
Hx
k
f
0 x 引理2.1：迭代法对任何初始近似 均收敛的
等价变换
迭代矩 阵
x(k+1)=Hx(k) +f
H 并不是 唯一的, 因此迭代 格式也不 是唯一的!
e. g. A I A I x I A x b
A D A D x I D 1 A x D 1b x D 1 (b Ax ) a ii 0 A L D U x D 1 L U x D 1b aii 0
H
p k
q 1 x R n , lim x x and
0 k k p
x x*
q k k 1 x x 1 q qk 1 0 x x 1 q
p
p
后验估计 Posterior error – estimated 先验估计 Prior error— estimated
0 a12 0 U
a1n a2 n 0
k
0.1 0.5 f , 其中 H ， 0.8 0.1
讨论该迭代法的收敛性。
例2 设 x
k 1
Hx
k
0.9 0 f , 其中 H ， 0.3 0.8
讨论该迭代法的收敛性。
2.2.3 迭代法的收敛速度
定理2.5 当 H 1 时，由迭代法式所定义的 序列 {x( k ) } 满足如下估计式：
x
(k )
x
*
H 1 H
k
x( k ) x( k 1)
x
(k )
H x x (1) x (0) 1 H
*
现在讨论使误差减少初始误差的 倍所需的最 少迭代次数
x
(k )
x H x (0) x *
*
k
(k ) * (0) * x x x x 若要求
kk 1 ， ， k
lim k lim
k k k
k

k
lim
k
1 k
k 1
0.
x 是线性方程组Ax=b的解
x* Hx* g
x
k 1
*
Hx
k
f
0 引理2.1：迭代法对任何初始近似 x 均收敛的 充分必要条件是 H k 0 k
k
2.2.2 迭代法的收敛性
定义 利用迭代公式构造序列 x ( k ) , 以求 得方程组 的近似解的算法称为解式的简单迭代法。 若迭代序列 x ( k ) 收敛，则称此迭代法是收敛的。
x
k 1
Hx
k
f,
x Hx f
* *
k * x x 两式相减，知误差向量 满足下列迭代关系：
充分必要条件是
H k 0k
k H 引理2.2： 0 k 的充要条件是 ( H ) 1
定理2.4：迭代法对任何初始近似均收敛的充分 必要条件是迭代矩阵H的谱半径
( H ) 1
(k ) 定义 设矩阵序列A k (a ij ) R nn , A (a ij ) R nn，若 (k ) lim a a ij ij k
1 i n
为矩阵A的谱半径。
2.2 迭代法的一般形式 与收敛性定理
2.2.1 迭代法的一般形式
已知线性代数方程组
Ax b
首先将方程组改写成等价的形式
x Hx g
从而建立迭代式：
称
x
xபைடு நூலகம்
k 1
为迭代序列，并称H为迭代矩阵。
Hx g k 0,1,2
H k 0 k 的充要条件是 ( H ) 1 引理2.2：
定理2.4：迭代法对任何初始近似均收敛的充分 必要条件是迭代矩阵H的谱半径 ( H ) 1
推论：若 H 1 ( 允许为任何一种相容的矩阵范 数) ，则迭代法收敛。
例1 设 x
k 1
Hx
迭代法思想： 第一步 第二步
将Ax b转化为等价方程组： x Hx f 设x * 为精确解，x* Hx * f
构造迭代格式，任取初 始向量x ( 0 ) , 按逐次代
H 与k无关，称为 入方法构造 { x(k ) } 一阶定常迭代法
x
( k 1 )
Hx
(k )
f
收敛？发散？
( i , j 1,2, , n)
k
则称{ A k }收敛于A，记为lim A k A .
例 设矩阵序列 1 2 2 A 0 , A 0 且 | | 1，考查其极限 .
k 2 k ， , A 2 0
若 lim x ( k ) x*,则称迭代法收敛，且 x * 为方程的解。
k
否则此迭代法发散。
判断收敛的方法：
(k ) (k ) 若 lim || x x * || ＝ lim || || 0, 则此迭代法收敛。 k k
( k 1 )＝x ( k 1 ) x* Hx ( k ) f Hx * f H ( x ( k ) x*) H ( k ) H k 1 ( 0 ) 即有 ( k ) 0, H k 0
即
A=D-L-U
a11 a 21 A a n1 0 a L 21 a n1
a12 a22 an 2
a1n a2 n ann 0
a11 D
a22
ann
0 an 2
计算中判断迭代终止条件的方法：
|| x ( k 1) x ( k ) || , x* x ( k 1)
如何判断迭代法是收敛 的？？
收敛条件
1. lim x k x* lim H k 0
k k
2.
lim H k 0 H 1
x
3.
a11 a12 a a 21 22 an1 an 2
a1n x1 b1 x b a2 n 2 2 ann xn bn
Ax=b
怎样设计迭代格 式? Ax=b x=Hx+f