数值分析 典型例题与习题2

ρ ( A) ≤|| A ||
Ex4.若矩阵A是n阶对称矩阵, 则有 ρ ( A) =|| A ||2 阶对称矩阵,
的任一特征值, 对称, 证：设λ 是A的任一特征值,由于 对称,故λ2 是矩阵 的任一特征值 由于A对称 ATA的特征值,即 的特征值, 的特征值
λ ( AT A) = λ ( A 2 ) = [λ ( A)]2
《数值分析》典型例题 II
三、四章内容提要
典型例题分析 部分习题解答 补充练习题
一、解线性方程组直接法
顺序消元法、列主元法、 顺序消元法、列主元法、追赶法 矩阵的直接分解、对称矩阵 矩阵的直接分解、 的LU分解 分解 二、向量和矩阵的范数 向量范数、算子范数、三种 向量范数、算子范数、 矩阵范数、 矩阵范数、矩阵的条件数 三、解线性方程组迭代法 Jacobi迭代、Seidel迭代、SOR迭代、迭代收敛性、 迭代、 迭代、 迭代、 迭代 迭代 迭代 迭代收敛性、 初等变分原理、最速下降法、共轭梯度法* 初等变分原理、最速下降法、共轭梯度法
|| x || − || y || ≤|| x − y ||
7/16
Ax = b, 将矩阵分裂 A = D – U – L 将矩阵分裂:
Jacobi 迭代法的迭代矩阵
特征多项式与特征方程: 特征多项式与特征方程
BJ = D-1(U+L)
| λI – D-1(U+L)| = |D-1|·|λD – (U+L) | | λD – (U+L) | = 0 Gauss-Seidel迭代法的矩阵 BG-S= (D – L)-1U 迭代法的矩阵: 迭代法的矩阵
14/16
练习7 写出n维向量序列 维向量序列{X 收敛于向量X 的定义； 练习 . 写出 维向量序列 (k)} 收敛于向量 * 的定义；
设 证明
lim X ( k ) = X * ,而 B 是 n 阶方阵 而 k →∞
lim BX
k →∞
(k )
= BX
*
练习8 为对称正定阵,且有 练习8.有方程组Ax = b,其中A为对称正定阵 且有 ,
特征多项式与特征方程: 特征多项式与特征方程
|λI – (D – L)-1U| = |(D – L )-1|·|λ(D– L ) – U | |λ(D– L ) – U | = 0
8/16
Ex6. 若A是严格主对角占优矩阵，求证解方程组 是严格主对角占优矩阵， 是严格主对角占优矩阵 AX=b的高斯-赛德尔迭代法收敛。 的高斯的高斯 赛德尔迭代法收敛。 证：高斯-赛德尔迭代矩阵为(D – L )-1U,该矩阵的特 高斯-赛德尔迭代矩阵为 , 征方程为
n n n j =1 j≠k j =1 j≠k j =1 j≠k
| a kk | ⋅ | uk |=| ∑ a kj u j |≤ ∑ | a kj u j | ≤ ∑ | a kj | ⋅ | uk |
两边约去 |uk|，得 ，
| a kk |≤ ∑ | a kj |
j =1 j≠k
n
这与主对角占优矛盾, 这与主对角占优矛盾 故det(A) ≠0。 。
的范数有关系: 径与A的范数有关系:ρ(A) ≤ || A || 任一特征值,x 证:设 λ 是矩阵 任一特征值 是对应的特征向量 则 设 是矩阵A任一特征值 是对应的特征向量,则
Ax = λx || λx ||=|| Ax ||≤|| A || ⋅ || x || | λ | ⋅ || x ||≤|| A || ⋅ || x || | λ |≤|| A ||
2 1 2 5 − 2 − 2 3 1 1 − 2 x1 4 x 7 3 − 2 2 = 3 5 x3 − 1 2 3 x4 0
13/16
练习5: 练习 求矩阵的 2-范数,
用反证法。 则齐次方程组Ax=0有非 证: 用反证法。设det(A) = 0, 则齐次方程组 有非 零解 u =[u1, u2, ···, un ]T. 设
|| u ||∞ =| uk | 考虑 =0的第 个等式 考虑Au 的第 的第k个等式 a k 1 u1 + ⋯ + a kk uk + ⋯ + a kn un = 0
1 || X k − A ||≤ || X k +1 − X k || 1− q
−1
16/16
4/16
Ex2.设A对称且a11≠ 0,高斯消元法一步后 约化为 高斯消元法一步后,A约化为
T a11 α 1 0 A2 证明 A2 也是对称矩阵。 T a11 α 1 A= 证明:设 证明 设 α 1 A1
1 α1 m1 = a11
1 F1 = − m1 I n −1
9/16
| λa ii |=| λ | × | a ii |>| λ | ∑ | a ij | = ∑ | λ | × | a ij | ≥ ∑ | λa ij | +
j =1 j≠i j =1 j≠i j =1
n
n
i −1
j = i +1
∑| a
n
ij
|
也是严格主对角占优矩阵。 故C(λ)也是严格主对角占优矩阵。由于严格主对角占 也是严格主对角占优矩阵 优矩阵的行列式不为零， 优矩阵的行列式不为零，故λ不是特征方程
迭代公式
X
( k +1)
=X
(k )
+ ω (b − AX
(k )
)
讨论使迭代序列收敛的ω 的取值范围.
15/16
练习9: 练习 设A是n阶可逆矩阵,有A的一个近似逆B,令 R=I –AB如果 || R ||≤ q <1 ，试证明 (1) A–1 = B ( I + R + R2 + …… )； ； (2)任意给定n阶矩阵X0,由迭代格式 Xk+1 = Xk R + B ( k = 0，1，2，…… ) ， ， ， 产生的矩阵序列{ Xk }收敛到矩阵A-1； (3)对矩阵序列{ Xk }，有误差估计式 ，
6/16
由2-范数计算公式 范数计算公式
|| A || 2 = λ max ( A T A) = max[λ j ( A)]2 = max | λ j ( A) |= ρ ( A)
1≤ j ≤ m 1≤ j ≤ n
Ex5.对任意 ，y∈Rn，利用向量范数的三角形不 对任意x， ∈
等式证明： 等式证明：
C(λ) = |λ(D– L ) – U | = 0
的根。所以当A是严格主对角占优矩阵时,(D – L )-1U 是严格主对角占优矩阵时, 的根。所以当 是严格主对角占优矩阵时 的特征值必然满足： 的特征值必然满足：|λ | < 1，从而高斯-赛德尔迭代矩 ，从而高斯阵谱半径小于1 迭代法收敛。 阵谱半径小于1，迭代法收敛。
||Hale Waihona Puke Baidux
(k )
|| B || || x(k ) − x(k−1) || − x* ||≤ 1− || B ||
定理4.3 若 Ax = b 的系数矩阵 A 是严格对角占优矩 阵,则Jacobi迭代和Seidel迭代均收敛
3/16
Ex1.如果A是严格主对角占优矩阵 则 det(A) ≠0. 如果 是严格主对角占优矩阵,
|λ(D– L ) – U | = 0
a 12 ⋯
行列式对应的矩阵为
λa 11 λa 21 C (λ ) = ⋮ λ a n1
λa 22
⋮
λa n 2
a1n ⋯ a 2n ⋱ ⋮ ⋯ λa nn
矩阵的主对角占优性质， 当|λ | > 1时，利用 矩阵的主对角占优性质，得 时 利用A矩阵的主对角占优性质
1 A → F1 A = − m1
T a11 α 1 a11 = I n −1 α 1 A1 0
T A1 − m1α 1
T α1
1 T A2 = A1 − αα a11
所以,
A2 = A2T
5/16
Ex3.对任何一种矩阵的算子范数,证明矩阵 的谱半 对任何一种矩阵的算子范数,证明矩阵A的谱半
以及2-范数意义的条件数
1 1 1 − 1 1 − 1 Q= − 1 − 1 1 1 −1 −1
1 1 1 1
练习6. 练习 设 A =( aij )n×n为实对称正定矩阵, x∈R n, ∈ × b ∈R n,如果 u 使二次函数 1 f ( x ) = ( Ax , x ) − (b, x ) 2 取极小值 , 证明 u 是线性方程组 Ax = b 的解。
|| x || − || y || ≤|| x − y ||
证: || x || = || (x – y )+ y || ≤|| x – y || + || y || || x || – || y || ≤|| x – y || 同理, 同理 || y || – || x || ≤|| y – x || =|| x – y || || x || – || y ||≥ – || x – y || – || x – y || ≤ || x || – || y || ≤|| x – y ||
Ex8 设 A∈R n×n 为对称正定矩阵 定义 为对称正定矩阵,定义 ∈ || x ||A = x T Ax
上的一种向量范数。 证明 || x ||A 是 R n 上的一种向量范数。
12/16
练习1. 分析求解三对角方程组追赶法的计算工作量。 练习 分析求解三对角方程组追赶法的计算工作量。 练习2. 练习 . 设A=(aij)n×n 为可逆下三角矩阵，证明 × A-1 仍为下三角矩阵。 仍为下三角矩阵。 练习3. 练习 . 设 A=(aij)n×n为可逆上三角矩阵，证 × 为可逆上三角矩阵， 仍为上三角矩阵。 明 A-1 仍为上三角矩阵。 练习4 练习 . 用列主元法解方程组
10/16
Ex7.设A是一个可逆矩阵，矩阵序列满足 设 是一个可逆矩阵 是一个可逆矩阵， Xk+1=Xk(2I – A Xk )，（ =0，1，2，……） ，（k ， ， ， ，（ ） 证明:当 证明 当 ρ ( I − AX 0 ) < 1 时
lim X k = A −1
k →∞
证明： 证明：由Xk+1=Xk(2I – A Xk )，得 ， I – AXk+1 = I – A Xk(2I – A Xk )= (I – A Xk )2 于是 I – AXk =(I – A Xk -1)2 × =(I – A Xk -2)2×2 = ··········
= ( I − AX 0 )
2k
11/16
X k = A [ I − ( I − AX 0 ) ]
2k
−1
ρ ( I − AX 0 ) < 1
−1
lim ( I − AX 0 )
k →∞
2k
2k
=0
lim X k = lim A [ I − ( I − AX 0 ) ] = A −1
k →∞ k →∞
2/16
=
=
消元法使用的条件 定理3.1 约化主元ak+1,k+1(k) ≠ 0 (k=0,1,···,n-1)的 矩阵A的各阶顺序主子式不为零 的各阶顺序主子式不为零. 充分必要条件是 矩阵 的各阶顺序主子式不为零 定理4.2 :设x*为方程组 Ax=b 的解 若||B||<1,则对迭代格式 x(k+1) = B x(k) + f 有