当前位置：文档之家 › 数值分析9迭代法收敛性证明资料

数值分析9迭代法收敛性证明资料

  • 格式：pptx
  • 大小：484.53 KB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

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

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

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

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

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

所以
lim(k) 0
k
第五页，共18页
5/18
矩阵B 的谱
设n阶方阵B 的n个特征值为:
则称集合 {1 ,2,,n}
为B 的谱. 记为 ch B
1 ,2,,n
特征值取模最大
矩阵B的谱半径 (B)m 1kna|xk|
注1: 当B是对称矩阵时, ||B||2 = (B)
注2: 对 Rn×n 中的范数|| ·||,有
除非BJ是非负矩阵时,两种迭代法有联系。
第十二页，共18页
12/18
误差估计定理
定理4.2 :设X*为方程组 AX=b 的解 若||B||<1,则对迭代格式 X(k+1) = B X(k) + f 有
(1) ||X(k)X *| | ||B||||X(k)X(k1)||
1||B||
(2) ||X(k)X*| | ||B|k | ||X(1)X(0)||
迭代矩阵: BIA
设矩阵A对称正定,则特征值 0,由于B是A的
多项式,故 B 的特征值为
1
(B)1 | |1 02/ 当不等式 02/||A|| 成立时
简单迭代法收敛.
第十八页，共18页
18/18
k
limBk 0
k
lkimik 0
(i = 1, 2,···, r)
| i | 1
m 1iar |xi |1
(i = 1, 2,···, r) 谱半径 (B) < 1
第八页，共18页
8/18
注1: AX = b X = BX + f ( I – B )X = f
X = ( I – B )-1 f
X(k+1) – X*= B(X(k) – X*)

迭代法的收敛性

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

迭代法和其收敛性

迭代法和其收敛性

(1) xk1 xk2 xk 3, g(x) x2 x 3,
g(x) 2x 1, g(x*) g( 3) 2 3 1 1.
3
3
(2)
xk 1
xk
,
g(x)
, x
g( x)
3 x2
,
g( x*)
1.
(3)
xk 1
xk
1 4
( xk2
3),
g(x)
x
1 4
(x2
3),
g(x) 1 1 x, g(x*) 1 3 0.134 1.
上g存(x在) [a, b]
因 a g，(x)下列b设
及 g(a) ，a定 g(b) b
义函数
f (x) g (x) x.
显然 f (x) C，[a且, b满] 足
f (a) g (a) a 0, f (b)
g(b) b，由0 连续函数性质可知存在
x使* (a, b)
f (x*) ， 0即
L xk1 x * Lk x0 x *.
因 0 L，故1 当 k时序列 收敛{到xk } .
x*
再证明估计式（2.5），由李普希兹条件有
xk1 xk g(xk ) g(xk1) L xk xk1 .
（2.6）
反复递推得
xk 1 xk Lk x1 x0 .
于是对任意正整数 p有
g在(x区) 间3x2 中
[1,2] g(x) 1
10.3 局部收敛性与收敛阶
上面给出了迭代序列 {在xk区} 间 上[旳a, b收]敛性， 一般称为全局收敛性. 定理旳条件有时不易检验，实际应 用时一般只在不动点 x *旳邻近考察其收敛性，即局部收 敛性.
定义7.2.1 设 有(x不) 动点 ，假x *如存在 旳某x个* 邻域 R : x x ，* 对任意 ，迭x0 代（R 2.2）产生旳序列 {xk }，R且收敛到 ，x则*称迭代法（2.2）局部收敛.

迭代法的收敛性

迭代法的收敛性

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

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

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

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

数值分析中的迭代法收敛性分析迭代法是数值分析领域中常用的一种数值计算方法，通过迭代逼近的方式求解数值问题。

在使用迭代法时，我们需要关注其收敛性，即迭代过程是否能够逼近问题的解。

本文将探讨数值分析中的迭代法收敛性分析方法。

一、迭代法的基本概念迭代法是一种通过逐次逼近的方式求解数值问题的方法。

在求解问题时，我们通过不断使用公式迭代计算，直到满足某个特定的条件为止。

迭代法在实际应用中广泛使用，例如求解方程组、求解最优化问题等。

二、迭代法的数学模型我们可以用以下数学模型描述迭代法的过程：设迭代公式为：x_(n+1) = g(x_n)，其中x_n表示第n次迭代的结果，g(x)为迭代函数。

三、迭代法的收敛性在使用迭代法时，我们希望迭代过程能够收敛到问题的解。

迭代法的收敛性分析是判断迭代过程是否能够收敛的关键。

1.线性收敛如果迭代法满足以下条件：1）对于任意的x_0，如果|x_n - x*| / |x_(n-1) - x*| ≤ C (0 < C < 1)，其中x*为问题的解，那么称迭代法是线性收敛的。

2）线性收敛的迭代法需要满足条件|x_1 - x*| / |x_0 - x*| ≤ C (0 < C <1)。

2.超线性收敛如果迭代法满足以下条件：对于任意的x_0，如果|x_n - x*| / |x_(n-1) - x*|^p ≤ C (0 < C < 1, p > 1)，那么称迭代法是超线性收敛的。

3.二次收敛如果迭代法满足以下条件：对于任意的x_0，如果|x_n - x*| / |x_(n-1) - x*|^2 ≤ C (0 < C < 1)，那么称迭代法是二次收敛的。

四、判断迭代法的收敛性在实际应用中，判断迭代法的收敛性是非常重要的。

下面介绍几种常用的判断方法。

1.收敛准则根据数列极限的定义，如果一个数列{x_n}满足：对于任意ε > 0，存在正整数N，当n > N时，有|x_n - x*| < ε，则称{x_n}收敛于x*。

迭代法的建立与收敛性

n
lim
n
| xn1 | | xn |
p
C
( C 0),
则称xn p阶收敛,相应的迭代法称为p阶方法. 特别, p=1时叫线性收敛,此时要求0<C<1; p=2时叫平方收敛;
p越大越好.(why?)
定理2.2.3 设(x)在的某邻域 内有充分多阶连续导 数，则迭代法xn+1 = (xn)为p阶收敛的充要条件是

x n 1 ) L x n x n 1 . （2.2.3）
由 (2.2.2) 和 (2.2.3) 式 得 xn L 1－ L x n x n 1 L
n
1－ L
x1 x 0 .
注1：L越小，收敛越快。 由定理结论(3)或(2.2.2)，只要前后两次迭代值的差值足 够小，就可使近似值 x n 1 达到任意的精度。在实际计算 中，一般用 | x n 1 x n | 来控制迭代过程结束。 注2：定理条件非必要条件，可将[a, b]缩小，定义局部收敛性： 定义2.2.1 若存在 的某 邻域 B = { x | | x | } , 使由 x0B 开始的迭代都收敛, 则称迭代法具有局部收敛性。 定理2.2.2 设(x)在的某邻域内具有连续的一阶导数， 且 | '() | < 1， 则迭代法xn+1 = (xn)具有局部收敛性。
§2.2 迭代法
一. 迭代法的建立与收敛性
1. 建 立 : 把 f ( x ) 0 改 写 成 x ( x )， ( f ， 连 续 ）
所以, 为f的根的充要条件是为的不动点。
取 定 初 值 x0 xn1 ( xn ) ( n 0, 1, 2, ...)

迭代法的收敛性


谱半径分别是 ρ ( 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 )
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1 || B ||
证 X(k+1)–X* =B(X(k) – X* )
|| X(k+1) – X* || = ||B(X(k) – X*) || ≤ ||B|| || X(k) – X* ||
05:57
11/34
||X(k) – X* ||= || (X(k) – X(k+1) ) + (X(k+1) –X* ) || ≤ ||X(k) – X(k+1)|| + ||X(k+1) –X*|| ≤ ||X(k) – X(k+1)|| +||B|| ||X(k) –X*||
05:57
4/34
➢迭代法构造
f (x) 0 x (x)
➢收敛条件
f ( x) Ax b x M 1Nx M 1b, 其中A M N
x*为 ( x)的不动点, ( x)
在x*的某邻域N (x* )连续
且| ( x* )| 1, 则迭代法
对任意x(0) N (x* )收敛
➢中止准则
引理2 若(B) 1,则I B是非奇异的。
思路 : (I B)(I B B2 Bk ) I Bk1,
故(I B)-1 = B j。 j0
引理3 若 B 1,则对于矩阵算子范数满足
(I B)1 1 1 B
思路 : (I B)(I B)1 I (I B)1 B(I B)1 I
(I B)1 I B(I B)1 I B (I B)1
05:57
7/34
定理4.1 对任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收敛的充分必要条件是序列{X(k)}收敛, 记 X*是该序列的极限点, 则X* =B X*+f。
|| X (k) X * || 1 || X (k1) X (k ) ||
1 || B ||
|| X (k) X * || || B || || X (k) X (k1) ||
1 || B ||
05:57
12/34
统一的不动点框架
➢迭代法构造
x (x)
➢收敛条件(局部vs全局)
x M 1Nx M 1b, 其中A M N
《数值分析》 9
迭代法收敛性条件 迭代误差估计定理
05:57
1/34
总结:
矩阵范数 算子范数
算子范数 矩阵1范数, 矩阵无穷范数, 矩阵2范数
2/34
例4 设||.||为Rn×n 上任意一种矩阵范数, 则对 任意的A ∈ Rn×n , 有( A) A 。
证明: 设( A) max | i |, x 0是模最大特 征值对应特征向量满足Ax x。
X* = B X* + f X(k+1) – X*= B(X(k) – X*)
记 (k) = X(k) – X* ( k = 0, 1, 2, ··· ) 则有 (k+1) = B (k) ( k = 0, 1, 2, ···) ||(k+1) ||= ||B(k) || ≤ ||B||.||(k) || ( k = 0, 1, 2, ···)
则xxT 不是零矩阵。 对于任意矩阵范数 . ,由范数定义有
( A) xxT xxT AxxT A xxT
例5 设||.||为Rn×n 上任意一种矩阵范数, 则对
有1 I ,特别的 . 为算子范数则 I =1。
3/34
A X = b (M–N )X = b M X = N X + b 迭代格式: X(k+1) = B X(k) + f ( B = M-1N, f=M-1b ) 设方程组的精确解为 X*,则有
思路 : (B) B 1
05:57
10/34
定理4.2 设X*为方程组 AX=b 的解若||B||<1,则 对迭代格式 X(k+1) = B X(k) + f 有
(1) || X (k ) X * ||
1
|| X ( k 1) X ( k ) ||
1 || B ||
(2) || X (k) X* || || B ||k || X (1) X (0) ||
| x(k ) x* | L | x(k ) x(k1) | 1 L
05:57
5/34
引理1 矩阵B Rnn ,则lim Bk 0的充分必要条件 k
是 ( B)
1, 其中 ( B)= max 1 k n
|
k
|
为矩阵B的
谱半径,1,2 , n是矩阵B的特征值。
参考: P. 83
05:57
6/34
(B) 1 lim Bk 0 k (I B)-1 = B j。 j0
lim X (k) (I B)1 f 说明迭代法产生的序列收敛。
k
05:57
9/34
谱半径小于1是迭代收敛的充要条件,但它不 易计算,所以在实际使用中通常并不好用。
由性质( A) A ,我们有如下推论 :
推论4.1 若||B||<1,则对任意的f和任意的初始向量 X(0)迭代法 X(k+1) =B X(k) +f 收敛。
x*为( x)的不动点,( x)
在x*的某邻域N (x* )连续
且 | ( x* ) | 1, 则迭代法
对任意x(0) N (x* )收敛
➢中止准则
| x(k ) x* | L | x(k ) x(k1) | 1 L
05:57
对任意的f 和任意的初始 向量X(0)迭代法收敛的充
分必要条件是(B) 1和
X (k1) X *
B( X (k) X * ) B2 ( X (k1) X * ) Bk1( X (0) X * )
由X(0) 的任意性知
B* =lim Bk O (B) 1。
k
05:57
8/34
充分性 k
X (k1) BX (k) f B(BX (k1) f ) f Bk1 X (0) B j f j0 则(I B)(I B B2 Bk ) I Bk1,
充分条件是||B|| 1
|| X (k) X * || || B || || X (k) X (k1) || 1 || B ||
13/34
严格对角占优矩阵
n
定义4.1 A=(aij)n×n, 如果| aii | | aij | 则称A为
严格对角占优阵。
j 1 ji
性质1 A 是严格对角占优矩阵, 则 | aii | 0 。