当前位置：文档之家 › 迭代格式二迭代法的收敛性一

迭代格式二迭代法的收敛性一

  • 格式：ppt
  • 大小：540.50 KB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

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)的解的问题称为不动点问题.

迭代法的收敛性与误差估计

迭代法的收敛性与误差估计

迭代法的收敛性与误差估计一…的童滚.11/{安务刊迭代法的收敛性.与误差估计’\虞福星..Z冬}7.在许多工程技术问题中,常常会遇到求解一元非线性方程的问题.例如,代数方程一x—l一0或超越方程x+{x—l看上去形式很简单,但不易求出其准确根,只能求出方程达到一定精度的近似根.求解这类方程的方法很多,迭代法就是其中的一种.迭代法有许多优点:1.其算法的逻辑结构简单f2.收敛速度快I3.中间结果有扰动不会影响计算结论;4.计算误差容易控制.正因为如此,迭代法得到非常广泛的应用.一,迭代法的基本思想设有方程f(11=0首先,我们设法将式(1)代成下列等价形式x—g∽然后按式(2)构造迭代公式(1)(2)+l—g{-,k=o,1,2, (3)从给定的初始近似根x.出发,按迭代公式(3)可以得到一个敦列x.,x1,x2,...,x, (4)如果这个数列{}有极限,则称迭代公式(3)是收敛的,此时数列螅极限x=limx就是原方程(1)的根.二,迭代法的收敛性及误差估计具备怎样的条件,迭代公式(3)是收敛的,这就是我们要讨论的中心问题.对此,我们有定理:设方程x—g在(a,b)内有根x,若gt满足李普希茨条件,即对(a,b)内任意的x】和都有lg(x1)g(x2)l≤qlxl—x2l(5)q为某个正数,当q<1时,则方程在(a’b)内有唯一的根I且迭代公式(3)对任意初始近似值xo均收敛于根x;还有误差估计式一≤lXk--Xkil≤lXI--Xol(6)证明:先证唯一性由已知条件知,x’是方程x—g的根,即x一g66设i也是方程x=g(x)的根,则x=g于是1x一i1=1g)--g1由李普希茨条件,得1x一;1一Ig(-～g’;I≤q1x一il因为0<q<1,故必有x.=;,根的唯一性得证. 再证收敛性由李普希茨条件,得IXk+I--X.l=Ig’--g)l≤qI一x.I同样l一x’l≤qIXk一1一x.1,…,1x1--X.1≤qI～x’1于是有1+I—x’I≤?Ix.一x’1因为0<q<1,当k—o.时,一0,即有Ix…--X’j—O(k—oo)所以,limxx.k一收敛性得证.利用李普希茨条件,得l+1～f=fg’)--g(,一.I≤Ix,一一1I于是对任意正整数P,有l+p一1≤1Xk—p一+rII+1Xk+p一1--Xk+p一±1+…+1一1一I≤(q+qP 一+…+q)?j一l一lxr令P—oo,得一I≤一一l≤IX1--X0I三,选择迭代公式的原则如果方程(2)中的g’满足Ig’I]l≤M<IxE(a,b)则可取这里的M作为李普希茨(5)中的q,由式(6)可知,正数q越小,收敛速度越快.所以,选遗代公式要遵循使IgI在(a山)的最大值M为最小这个原则.由于把方程f㈨一0化成等价形式x;g的方法很多.例如,方程x一x一1—0可以化成以下四种形式(1)x一一167(2)x一+1㈣x=X--每=㈤x一一由此可得四个迭代公式x+?=x:一1(7);(8):(9)’(9)l一—)(,)式(1I)也可用牛顿切线法导出,可见牛顿切线法可视为谴代法的特殊情形.由于=苎【)所以.f(?f().因此,只要ll≤q<l,L”)J公式(II)就收敛68。

GaussSeidel迭代法

GaussSeidel迭代法

定理4 对 于 任 意 右 端 向 量 F 初 始 向量 X 0， Gauss Seidel 迭代法收敛的充分条件是
n
1
B max
1
j i1
bij
1;
n
2
B
max i
bij
j 1
1.
由此定理可知，条件(1）或(2）被满足时，则 Gauss Seidel 迭代法与 Jacobi 迭代法都收敛。
x (1) 1
b11
x (0) 1
b12
x (0) 2
L
b1n
x (0) n
f1
显然，迭代格式收敛的话，则 x11 比 x10 更接近于 X 的第一个分量 x1* 所以在计算x21时，我们不再像 Jacobi
迭代法那样以 x10 , x20 ,L xn0 代入(2.1)中第二式的右边 ， 而是把新算出的 x11 及 x20 , x30 ,L xn0 代入该式右边，得
例5 设方程组 AX b 的系数矩阵为
1 2 2
பைடு நூலகம்
A
1 2
1 2
1 1
试证明 Jacobi 迭代法收敛 ，而 Gauss Seidel 迭代法不收敛。
证明 显然， Jacobi 迭代法的迭代矩阵为
因为
0 2 2
B
2 2
0 2
01
2 2 I B 1 1 3
22
令 I B 0 ，则有
x2(k
1)
b21x1(k 1)
b22 x2(k)
b2n xn(k) f2 ,
xn
(
k
1)
bn1x1(k 1)
b x (k1) nn1 n1
bnn xn(k)

第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迭代收敛性：

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

37第七节 迭代法及其收敛性
从而 ||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) )
即有

数值分析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法的收敛性。

数值分析3.1.二分法、迭代法及收敛性


上述令p→∞, 及limxk+p=x* (p→∞)即得(2.6)式. 证毕. 注：误差估计式(2.5)原则上确定迭代次数，但它由 于含有信息 L 而不便于实际应用. 而误差估计式(2.6) 是实用的，只要相邻两次计算结果的偏差足够小即 可保证近似值 xk 具有足够精度.
注： 对定理1和定理2中的条件2º 可以改为导数，即 在使用时如果(x)∈C[a, b]且对任意x∈[a, b]有
显然f(x)∈C[a, b],且满足f(a)=(a)-a>0, f(b)=(b)-b<0, 由连续函数性质可知存在 x*∈(a, b) 使 f(x*)=0，即 x*=(x*)，x*即为(x)的不动点. 再证不动点的唯一性. 设x1*, x2*∈[a, b]都是(x) 的不动点，则由(2.4)得
可以如此反复迭代计算
xk+1=(xk) 到的序列{xk}有极限 (k=0,1,2,). (2.2)
(x)称为迭代函数. 如果对任何x0∈[a, b]，由(2.2)得
lim xk x .
k
则称迭代方程(2.2)收敛. 且x*=(x*)为(x)的不动点， 故称(2.2)为不动点迭代法.
例1 用二分法求方程 f(x)=x3-x-1=0在(1, 1.5)的实根, 要求误差不超过0.005.
解 由题设条件，即：
|x*-xn|≤0.005 则要
1 2
n 1
(b a)
1 2
n 1
(1.5 1)
1 2
n 2
0.005
2 由此解得 n 1 5.6,取 n=6, 按二分法计算过程见 lg 2
L2 xk 1 xk 2 Lk x1 x0 .
于是对任意正整数 p 有

迭代法和收敛性


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)

类矩阵两种迭代法的收敛性比较

类矩阵两种迭代法的收敛性比较引言：在科学计算中，线性方程组的求解是很普遍的问题。

尤其是在大型科学计算中，线性方程组的求解是最重要的任务之一。

线性方程组的求解有很多种方法，例如高斯消元法、LU分解法、迭代法等等，其中迭代法是一种高效的方法。

迭代法的思想是从一个初值解开始，逐步改进解的准确度，直到满足误差要求。

在本文中，我们将讨论两种类矩阵迭代法的收敛性比较，即雅可比迭代法和高斯-赛德尔迭代法。

1.雅可比迭代法（Jacobi Iterative Method）：雅可比迭代法是最简单的迭代法之一。

它是基于线性方程组的矩阵形式 Ax=b，将 A 分解成 A=D-L-U（D为A的对角线元素，L为A的下三角矩阵，U为A的上三角矩阵），其中 D 为对角线元素，L为严格下三角矩阵，U 为严格上三角矩阵。

则有如下迭代关系式： x^{(k+1)}=D^{-1}(L+U)x^{(k)}+D^{-1}b (1)其中，x^{(k)} 为 k 次迭代后的解，x^{(0)} 为初始解。

雅可比迭代法的迭代矩阵为M = D^{-1}(L+U)。

以下是雅可比迭代法的收敛性分析：定理1：若矩阵 A 为对称正定矩阵，则雅可比迭代法收敛。

证明：由于 A 为对称正定矩阵，所以存在唯一的解。

假设迭代后得到的解为 x^{(k)}，则我们可以用误差向量 e^{(k)} = x-x^{(k)} 表示剩余项，则有 Ax^{(k)}-b = e^{(k)}。

对 (1) 式两边同时乘以 A^-1，得：x^{(k+1)}=x^{(k)}-A^{-1}e^{(k)}。

(2)将 (2) 式代入 Ax^{(k)}-b = e^{(k)} 中，得：Ax^{(k+1)}-b = Ae^{(k)}.(3)由于 A 为对称正定矩阵，则存在 A=Q\\Lambda Q^{-1}，其中Q 为正交矩阵，\\Lambda 为对角矩阵。

因此，我们可以将 (3) 式转化为：\\| x^{(k+1)}-x \\|_{A} =\\| Q^{-1}A^{-1}Qe^{(k)}\\|_{\\Lambda} \\leq \\rho (Q^{-1}A^{-1}Q)\\|e^{(k)}\\|_{A}。

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)。

a22
0 a 21 L an1
0
an,n1
0
0 a12 0 U 0
显然，A D L U .
二
SOR 迭代法的收敛性
由 3.5 式有
DX
k 1
1 DX k b LX

k 1
记
1 B D L [1 D U ] 1 F D L b
3.6
则有
X
k 1
B X F
k
3.7
其中，称 B 为 SOR 迭代矩阵。
由定理1及定理2直接得知： （1） SOR 迭代法收敛的充要条件是 B 1 。 （2） SOR 迭代法收敛的充分条件是 B 1 。
ai ,i 1 xi 1 ai ,i 1 xi 1 ain xn )
ai ,i 1 xi 1 ain xn )
ain xn
aii xi aii xi (bi ai1 x1 ai 2 x2 aii xi ai ,i 1 xi 1
SOR 迭代法收敛与否或收敛快慢都与松弛因
子 有关 。 关于 的范围，有如下定理。
定理6
SOR 迭代法收敛的必要条件是松弛
因子 应满足条件 0 2 。
因 SOR 法收敛，故 B 1 。记 B 的 特征值 为 1,2 , n 。因为n阶矩阵的n个 特征值之积等于其行列式之值，即 证明
( k 1) j

j i 1
a x
ij
n
(k ) j

即有
xi
k 1
(1 ) x
(k ) i

bi aij x aii j 1
i 1, 2,

i 1
( k 1) j

j i 1
a x
ij
n
(k ) j
,
3.4
,n
第三节 SOR 迭代法
一、 SOR 迭代格式 二
SOR 迭代法的收敛性
一、 SOR 迭代格式
SOR 是 Succesive
Over R e laxation
( 逐次超松弛 )
的缩写。SOR 迭代法是解大型稀疏矩阵方程组的有效 方法之一。它可以看作是
Gauss Seidel 迭 代 法 的加
速， Gauss Seidel 迭代法是 SOR 迭代的一种特殊形式。
(bi aij x
j 1
i 1
( k 1) j
aij x (jk ) ),
j i
n
i 1, 2,
,n
则 3.1 式可写为
xi( k 1) xi( k ) 1 (k ) ri aii
3.2
由此可以看出， Gauss Seidel 迭代法的第 k 1 步 ，相当于在第 k 步的基础上每一个分量增加
SOR迭代法常以这种形式进行计算。 格式（3.4）的矩阵形式为
X ( k 1) (1 ) X D 1 b LX UX ( k ) ,
k k


3.5
其中
a11 D 0 0 , ann a1n an1,n 0
k 1) ai ,i 1, xi( aii xi( k ) 1源自(k ) ain xn
x
(k ) i
i 1 n 1 ( k 1) (k ) bi aij x j aij x j aii j 1 j i
3.1
若记
ri
(k )
xi xi 1 (bi ai1 x1 ai 2 x2 aii aii xi ai ,i 1 xi 1
其 Gauss Seidel 迭 代 格 式 可写为 (aii 0) ：
xi( k 1) xi( k )
1 bi ai1 x1( k 1) aii
1 (k ) 一个修正量 a ri 。现在，为了获得更快的收敛 ii
效果，在修正项的前面乘以一个参数 ，便得到
逐次超松弛迭代格式

aii
x
( k 1) i
x
(k ) i

ri( k ) , i 1,2,
,n
3.3
称 为松弛因子，称 0 1 的 迭 代 过 程 3.3 为低松弛方法，对于一些方程组，用Gauss Seidel 迭代 法得不到收敛解或不收敛，但用低松弛方法却是收敛 的 。称 1 的迭代过程 3.3 为超 松 弛 方法, 此法 可以加速 Gauss Seidel 迭 代 方 法 的收敛。 1 的迭 代过程 3.3 就是 Gauss Seidel 迭代公式。 由迭代格式（3.3）
xi
k 1
x
(k ) i
有
xi
k 1
i 1 n 1 ( k 1) (k ) bi aij x j aij x j aii j 1 j i
x
(k ) i
xi
k
bi aij x aii j 1

i 1
将方程组 AX b 写成
ai1 x1 ai 2 x2 ai ,i 1 xi 1 aii xi (i 1, 2, ain xn bi , , n)
则有
aii xi bi ai1 x1 ai 2 x2 ai ,i 1 xi 1
UX
k

即
DX
k 1
LX
k 1
1 DX UX b
k k
于是有
( D L) X X
k 1 k 1
[1 D U ] X b
k k
( D L) 1[1 D U ] X ( D L) 1 b