当前位置：文档之家 › 数值分析第5次课

数值分析第5次课

  • 格式：pdf
  • 大小：897.50 KB
  • 文档页数：75
7
Jacobi迭代法的迭代矩阵为
0 2 2 1 B I D A 1 0 1 2 2 0 其特征方程为

2
| I B | 1 2 2
2 1 3 0

特征值 1 2 3 0, 谱半径 ( M ) 0 1 故Jacobi迭代法收敛.
9
其特征方程为
2 2 | I M | 0 2 3 ( 2)2 0 0 0 2
特征值 1 0, 2 3 2, 谱半径 ( M ) 2 1 故Gauss-Seidel迭代法发散.

10
一般来说, 计算矩阵的谱半径比较困难, 故用迭 代法收敛的充分必要条件来判断迭代法是否收敛往 往不太容易, 以下介绍用其他方法判别迭代法收敛 的充分条件.
|| x * x
(k )
1 || || x ( k 1) x ( k ) || (1 || M ||)
|| M || (k ) ( k 1 ) || x x || (1 || M ||)
21
停机准则
|| x
(k )
|| M || x* || || x ( k ) x ( k 1) || 1 || M ||
k 1 i 1 i 1 k 1 1 n n k 1 i i i
2 k 1 n k 1 t1u1 ( ) t2 u2 ( ) tnun 1 1 k 1 1 t1u1
故 1 xi(k1) xi(k ) x(k+1)为1的特征向量的近似向量(除一个因子外).
又
x
k
(k )
x* M x
k
k
k
lim M 0
k
(0)
x *
5
故对任意初始向量x(0), 均有
lim ( x ( k ) x*) lim M k ( x ( 0 ) x*) 0.
推论1
若迭代矩阵M满足||M||<1, 则下列迭代公
式对任意初始向量x(0)收敛
k 1 i n k i 1 i n i
k
( A)
k
1
定理 设A是任意n阶方阵, 由A的各次幂所组成的矩
阵序列
I , A, A 2 ,..., A k ,...
收敛于零矩阵, 即
k
lim A 0
k
的充分必要条件是
( A) 1
2
迭代法收敛的充分必要条件
定理 对任何初始向量 x(0)和右端项g, 由迭代公式 x(k+1) =Mx(k)+g (k=0, 1, 2, …)
特征值为 1 2 1 / 2, 3 1 故迭代矩阵的谱半径为 ( M ) 1 由迭代法收敛的充分必要条件知Jacobi迭代法发散.
18
误差估计
定理
设由迭代格式 x(k+1)=M x(k)+g, 若||M||<1,
则 {x(k)}收敛于 x*, 且有误差估计式
1 2 3 1 2 3 8 8 1 6 1 10 2 2 5 5 B A 6 12 3 1 6 12 3 1 3 2 3 9 3 9 3 2


12
迭代法收敛的充分条件
产生的向量序列{x(k)}收敛的充分必要条件是
(M)<1
其中(M)是迭代矩阵M的谱半径. 迭代法的收敛性只与迭代矩阵的谱半径有关, 而 迭代矩阵是由A演变来的, 因此迭代法是否收敛只与 系数矩阵A以及演变的方式有关, 与常数项和初始向 量的选择无关.
3
迭代法收敛的充分必要条件
x ( k 1) Mx ( k ) g , 收敛 (0) x 任意
§3.3 迭代法的收敛条件
定义(谱半径)
(i=1,2,…,n), 则称
设n阶方阵A的特征值为i
( A ) max | i |
1 i n
为矩阵A的谱半径. Ak 的特征值为
k k 1 , k , , 2 n
故
( A ) max | | max | |
交换两个方程的次序，得原方程组的同解方程组
9 4 x1 b2 3 10 x2 b1
它是一个严格对角占优方程组，对此方程组 Jacobi迭代法和Gauss-Seidel迭代法均收敛.
15
例 方程组Ax=b的系数矩阵为
2 1 0 A 1 2 1 0 1 2
11
定义(严格对角占优阵) 称n 阶方阵 A (aij )n
是严格对角占优的，如果其主对角线元素的绝对值大 于同行其它元素绝对值之和：
若线性方程组的系数矩阵为严格对角占优阵，则称 这个线性方程组为严格对角占优方程组.
| aij | | aii | j 1 , j i
n
i 1,2,, n
8
Gauss-Seidel迭代法的迭代矩阵为 M ( D L)1 U
1 0 0 ( D L) 1 1 0 , 2 2 1
0 0 1 1 ( D L) 1 1 0 , 0 2 1
0 0 0 2 2 1 1 M ( D L ) U 1 1 0 0 0 1 0 2 1 0 0 0 0 2 2 0 2 3 , 0 0 2
A不是严格对角占优阵
17
Jacobi迭代法的迭代矩阵为
1/ 2 1/ 2 0 1 M I D A 1/ 2 0 1/ 2 1/ 2 1/ 2 0 其特征方程为 1/ 2 1/ 2 | I M | 1 / 2 1 / 2 ( 1)( 1 / 2)2 0 1/ 2 1/ 2
幂法: 求1及其相应的特征向量.
1通常称为主特征值.
27
幂法基本思想 给定初始非零向量x(0), 由矩阵A构造一向量序列
x (1) Ax ( 0 ) ( 2) (1) 2 (0) x Ax A x ( k 1 ) (k ) k 1 ( 0 ) x Ax A x
(k ) || x x* || , 只要 由此可知，为使
|| x
(k )
x
( k 1 )
1 || M || || || M ||
实际计算时，当||M||不太接近1时，可用
|| x
(k )
x
( k 1 )
||
作为停机准则, x(k)即为满足精度要求之近似解.
22
根据事先给定的精度, 可以估算出迭代的次数k
x ( k 1) Mx ( k ) g
6
例 解方程组
x1 2 x2 2 x3 1 x1 x2 x3 2 2 x 2 x x 3 1 2 3
讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性. 解 迭代法是否收敛等价于迭代矩阵的谱半径是否小 于1，故先求迭代矩阵
严格对角占优阵. 故Jacobi迭代法与Gauss-Sidel迭代法均收敛.
14
当所给的方程组不满足迭代法的收敛条件时, 适 当调整方程组中方程的次序, 有时可得到满足迭代法 收敛条件的同解方程组.
3 10 例 方程组Ax=b的系数矩阵为 A 9 4 非对角占优阵
由于x(0)为任意n维向量,
k
lim ( x ( k ) x*) 0, 必须 lim M k 0 即 ( M ) 1.
k
4
迭代法收敛的充分必要条件
x ( k 1) Mx ( k ) g , 收敛 (0) x 任意
( M ) 1.
证明 充分性. 若(M)<1, 则 =1不是M的特征值, 故 det( I M ) 0 方程 (I－M)x=g有唯一解, 记为x*, 即 x* Mx * g 且
在一定条件下, 当k充分大时: 相应的特征向量为:
x 1 x
x
( k 1 )
( k 1 ) i (k ) i
28
幂法的理论依据 对任意向量x(0),
(0) x ti ui , 设t1不为零. 有 i 1 n
x ( k 1) Ax ( k ) Ak 1 x ( 0 ) A ti ui t u
§1 幂法 幂法 用于计算矩阵按模最大的特征值及其相应的
特征向量, 特别适用于大型稀疏矩阵.
26
幂法 设A为n阶实矩阵, 其特征值为1, 2, …, n, 相应的特 征向量为u1, u2, …, un. 且满足条件
1
2
3 n
此时1一定是实数!
u1, u2, …, un线性无关.
|| x
(பைடு நூலகம் )
|| M || (1) (0) x* || || x x || 1 || M ||
k
ln k
(1 || M ||)
|| x x || ln || M ||
(1) (0)
23
上机作业
• 第89页第1题(1)(2).
24
第四章 特征值与特征向量的计算
幂法
25
非严格对角占优 但A为对称正定矩阵, Gauss-Seidel迭代法收敛. 要判别Jacobi迭代法是否收敛, 需要计算其迭代 矩阵的谱半径.
16
例 设有方程组Ax=b, 其中
1 1 2 1 2 A 1 2 1 1 2 1 2 1 2 1
讨论用两种迭代法求解的收敛性. 解 A是对称正定阵 故Gauss-Seidel迭代法收敛.

合集下载

数值分析(第四版)课后习题及答案

数值分析(第四版)课后习题及答案


0.30
0.39
0.45
0.53
yj
0.5000
0.5477
0.6245
0.6708
0.7280
试求三次样条插值 S (x) 并满足条件
i) S(0.25) 1.0000, S(0.53) 0.6868; ii) S(0.25) S(0.53) 0.
25. 若 f (x) C2 a,b, S (x) 是三次样条函数,证明
12. 在 1,1 上利用插值极小化求 1 f (x) tg 1x 的三次近似最佳逼近多项式.
13. 设 f (x) ex 在 1,1 上的插值极小化近似最佳逼近多项式为 Ln (x) ,若 f Ln 有界,
证明对任何 n 1,存在常数 n 、 n ,使
改用另一等价公式
ln(x x2 1) ln(x x2 1)
计算,求对数时误差有多大?
x1 1010 x2 1010 ; x1 x2 2.
14. 试用消元法解方程组
假定只用三位数计算,问结果是否可靠?
s 1 ab sin c,
0c
15. 已知三角形面积 2
n
x
k j

j1 f (xj )
0,0k n2; an1 ,k n1.
15. 证明 n 阶均差有下列性质:
i) 若 F (x) cf (x) ,则 F x0, x1,, xn cf x0, x1,, xn ;
ii) 若 F (x) f (x) g(x) ,则 F x0, x1,, xn f x0, x1,, xn g x0, x1,, xn .
5.
设 xk

x0
清华第五版数值分析第5章课件

清华第五版数值分析第5章课件


第一步：选 ai ,1 max ai 1 ,交换第1行和第i1行，
1 i n
然后进行消元，得
( a111 ) [ A( 2 ) , b ( 2 ) ]
( 1 a121 ) a1( n ) ( (2 a222 ) a2 n )

( an 2 ) 2


(2 ann )
三
高斯列主元消去法
基本思想：在每轮消元之前，选列主元素 （绝对值最大的元素）
设方程组 AX b的增广矩阵为 a11 a (1) (1) 21 [ A , b ] [ A , b] an1 具体步骤为：
1
b1 a22 a2 n b2 an 2 ann bn a12 a1 n
如此至多经过n-1步,就得到与之同解的上三角形方 程组的增广矩阵,再用回代过程即可得方程组的解.
例：用Gauss列主元消去法解方程组 2 4 6 x1 3 4 9 2 x 5 2 1 1 3 x3 4
(1)
1 2 n
a (1) 0 0
a (1) a (1)
12 1n
(2 ( a22 ) a22 ) n



( (2 an22) ann)
b(1) ( 2) b2 ( 2) bn
1
则
a 令m i 1 , i 2,3,...,n a
n
a (1) 0 0
11
a (1) a (1)
12
(2 ( a22 ) a22 ) n



( (2 an22) ann)
数值分析课程第五版课后习题答案

数值分析课程第五版课后习题答案

N +1 N
=
1 = 1.7863 × 10 − 2 。 55.982
8、当 N 充分大时，怎样求 ∫ [解]因为 ∫
N +1 N
1 dx ？ 1+ x2
1 dx = arctan( N + 1) − arctan N ，当 N 充分大时为两个相近数相 1+ x2
减，设 α = arctan( N + 1) ， β = arctan N ，则 N + 1 = tan α ， N = tan β ，从而 tan(α − β ) = 因此 ∫
5、计算球体积要使相对误差限为 1%，问度量半径 R 允许的相对误差是多少？ 4 ε * ( π (R* )3 ) 4 3 [解]由 1% = ε r* ( π ( R * ) 3 ) = 可知， 4 3 * 3 π (R ) 3 ′ 4 4 4 ε * ( π ( R * ) 3 ) = 1% × π ( R * ) 3 = π ( R * ) 3 ε * ( R * ) = 4π ( R * ) 2 × ε * ( R * ) ， 3 3 3
ε * ( y n ) = 10ε * ( y n −1 ) = 10 n ε * ( y 0 ) ，
1 1 从而 ε * ( y10 ) = 1010 ε * ( y 0 ) = 1010 × × 10 − 2 = × 10 8 ，因此计算过程不稳定。 2 2 12、计算 f = ( 2 − 1) 6 ，取 2 ≈ 1.4 ，利用下列公式计算，哪一个得到的结果最 好？ 1 ( 2 + 1)
* r
x= x
*
ε ( x * ) = n( x * ) n −1 2% x * = 2n% ⋅ x * ，
数值分析第五版第5章学习资料

数值分析第五版第5章学习资料

6
n
即 de(A t) aijAij (i1,2,,n), j1
其中 A ij 为 a ij 的代数余子式，Aij(1)ijMij, M ij 为元素 a ij 的余子式.
行列式性质：
( ad ) ( A e ) d t B ( A e )d ( t B )A e , ,B t R n n .
有非零解，故系数行列式 deIt (A)0，记
a11 a12 p()det(I A) a21 a22
a1n a2n
（1.3）
an1 an2 ann n c1n1cn1cn 0.
p()称为矩阵 A的特征多项式，方程(1.3)称为矩阵 A的特
征方程.
9
因为 n次代数方程 p() 在复数域中有 n个根
其中用 ri 表示矩阵的第 i行. 由此看出，用消去法解方程组的基本思想是用逐次消
去未知数的方法把原方程组 Axb化为与其等价的三角 形方程组，而求解三角形方程组可用回代的方法.
上述过程就是用行的初等变换将原方程组系数矩阵化 为简单形式(上三角矩阵)，从而将求解原方程组(2.1)的 问题转化为求解简单方程组的问题.
n
n
trA aii i.
i1
i1
（1.4） （1.5）
称 trA为 A的迹.
A的特征值 和特征向量 x还有一下性质：
(1) AT 与 A有相同的特征值 及特征向量 .
(2)若 A非奇异，则 A1 的特征值为 1，特征向量为 x.
(3)相似矩阵 BS1AS有相同的特征多项式.
11
例1 求 A的特征值及谱半径
4x2x3 5,
2x3 6.
显然，方程组(2.6)是容易求解的，解为
x (1,2,3)T.