第四章 解线性方程组的迭代法
/* Iterative Techniques for Solving Linear Systems */
求解 bxA
思路与解 f (x)=0 的不动点迭代相似 ……，将 等价bxA
改写为 形式，建立迭代 。
从初值 出发，得到序列 。
fxBx fxBx kk )()1(
)0(x? }{ )(kx?
计算精度可控，特别适用于求解系数为大型稀疏矩阵 /* sparse matrices */ 的方程组。
研究 内容：
如何建立迭代格式？收敛速度？
向量序列的收敛条件？ 误差估计？
§ 1 向量和矩阵范数 /* Norms of Vectors and Matrices */
—— 为了误差的度量
向量范数 /* vector norms */
定义 Rn空间的 向量范数 || · || 对任意 满足下列条件：
nRyx,
00||||;0||||)1( xxx （ 正定性 /* positive definite */ )
||||||||||)2( xx C对任意 (齐次性 /* homogeneous */ )
||||||||||||)3( yxyx （ 三角不等式 /* triangle inequality */ )
常用向量范数：
n
i
ixx
1
1 ||||||
n
i i
xx
1
2
2 ||||||
pn
i
p
ip xx
/1
1
||||||
||max||||
1 ini
xx
注：
||||||||l i m xx pp
§ 1 Norms of Vectors and Matrices – Vector Norms
定义 向量序列 收敛 于向量 是指对每一个 1? i? n 都有 。
}{ )(kx? *x?
*)(li m iki
k xx
可以理解为 0||*|| )(xx k
定义 若存在常数 C > 0 使得对任意 有,则称 范数 || · ||A 比范数 || · ||B 强 。
nRx BA xCx ||||||||
定义 若范数 || · ||A 比 || · ||B 强，同时 || · ||B 也比 || · ||A 强，即存在常数 C1,C2 > 0 使得,则称 || · ||A
和 || · ||B 等价 。
BAB xCxxC |||||||||||| 21
定理 Rn 上一切范数都等价。
可以理解为对任何向量范数都成立。 HW,p.62 #6,#7
§ 1 Norms of Vectors and Matrices – Matrix Norms
矩阵范数 /* matrix norms */
定义 Rm?n空间的 矩阵范数 || · || 对任意 满足：
nmRBA,
00||||;0||||)1( AAA （ 正定性 /* positive definite */ )
||||||||||)2( AA C对任意 (齐次性 /* homogeneous */ )
||||||||||||)3( BABA （ 三角不等式 /* triangle inequality */ )
(4)* || AB ||? || A || · || B || （ 相容 /* consistent */ 当 m = n 时 )
In general,if we have
|| AB || || A ||? · || B ||?,then
the 3 norms are said to be consistent.
Oh haven’t I had enough
of new concepts? What do I need
the consistency for?
When you have to analyze
the error bound of AB – imagine you doing it
without a consistent matrix norm…
§ 1 Norms of Vectors and Matrices – Matrix Norms
常用矩阵范数：
Frobenius 范数
n
i
n
j
ijF aA
1 1
2|||||| —向量 || · ||2的直接推广对方阵 以及 有nnRA nRx
22 |||||||||||| xAxA F
利用 Cauchy 不等式可证。 22 |||||||||| yxyx
算子 范数 /* operator norm */
由向量范数 || · ||p 导出关于矩阵 A? Rn?n 的 p 范数,
px
p
p
p xAx
xAA
px
||||m a x|||| ||||m a x||||
10 ||||
则
ppp
ppp
xAxA
BAAB
||||||||||||
||||||||||||
特别有,?
n
j
ijaA ni
1
||m a x||||
1
（ 行和范数 ）
n
i
ijaA nj
1
1 ||m a x|||| 1
（ 列和范数 ）
)(|||| m a x2 AAA T （ 谱范数 /* spectral norm */）
矩阵 ATA 的最大特征根 /* eigenvalue */
HW,p.62
#2,#4,#5
§ 1 Norms of Vectors and Matrices – Matrix Norms
注,?Frobenius 范数 不是 算子范数。
我们只关心有相容性的范数,算子范数 总是相容的。
即使 A中元素全为实数，其特征根和相应特征向量
/* eigenvector */ 仍可能是复数。将上述定义中绝对值换成 复数模 均成立。
若不然，则必存在某个向量范数
|| · ||v 使得 对任意 A 成立。
v
vF
x
xAA
x ||||
||||m a x||||
0?
Counterexample? 1
||||
||||m a x||||
0
v
vF
x
xIIn
x?
谱半径 /* spectral radius */
定义 矩阵 A的 谱半径 记为
(A) =,其中?i 为
A 的特征根。
||m a x1 ini
Re
Im
(A)
§ 1 Norms of Vectors and Matrices – Spectral Radius
定理 对任意算子范数 || · || 有 ||||)( AA
证明,由算子范数的相容性，得到 |||||||||||| xAxA
将任意一个特征根?所对应的特征向量 代入u?
|||||||||||| uAuA |||||||||| uu
定理 若 A对称，则有 )(||||
2 AA
证明,)()(|||| 2
m a xm a x2 AAAA T
A对称若?是 A 的一个特征根，则?2 必是 A2 的特征根。
又：对称矩阵的特征根为实数，即?2(A) 为非负实数，
故得证。
)()( 22m a x AA 对某个 A 的特征根?成立所以 2-范数亦称为谱范数 。
§ 1 Norms of Vectors and Matrices – Spectral Radius
定理 若矩阵 B 对某个算子范数满足 ||B|| < 1，则必有
① BI? 可逆； ②
||||1
11
BBI
证明,① 若不然，则 有非零解，即存在非零向量 使得
0)( xBI
0x? 00 xxB 1
||||
||||
0
0
x
xB 1|||| B?
② IBIBI 1))(( 11 )()( BIBBI
11 )()( BIBIBI?
||)(||||||1||)(|| 11 BIBBI
/* Iterative Techniques for Solving Linear Systems */
求解 bxA
思路与解 f (x)=0 的不动点迭代相似 ……，将 等价bxA
改写为 形式，建立迭代 。
从初值 出发，得到序列 。
fxBx fxBx kk )()1(
)0(x? }{ )(kx?
计算精度可控，特别适用于求解系数为大型稀疏矩阵 /* sparse matrices */ 的方程组。
研究 内容：
如何建立迭代格式？收敛速度？
向量序列的收敛条件？ 误差估计？
§ 1 向量和矩阵范数 /* Norms of Vectors and Matrices */
—— 为了误差的度量
向量范数 /* vector norms */
定义 Rn空间的 向量范数 || · || 对任意 满足下列条件：
nRyx,
00||||;0||||)1( xxx （ 正定性 /* positive definite */ )
||||||||||)2( xx C对任意 (齐次性 /* homogeneous */ )
||||||||||||)3( yxyx （ 三角不等式 /* triangle inequality */ )
常用向量范数：
n
i
ixx
1
1 ||||||
n
i i
xx
1
2
2 ||||||
pn
i
p
ip xx
/1
1
||||||
||max||||
1 ini
xx
注：
||||||||l i m xx pp
§ 1 Norms of Vectors and Matrices – Vector Norms
定义 向量序列 收敛 于向量 是指对每一个 1? i? n 都有 。
}{ )(kx? *x?
*)(li m iki
k xx
可以理解为 0||*|| )(xx k
定义 若存在常数 C > 0 使得对任意 有,则称 范数 || · ||A 比范数 || · ||B 强 。
nRx BA xCx ||||||||
定义 若范数 || · ||A 比 || · ||B 强，同时 || · ||B 也比 || · ||A 强，即存在常数 C1,C2 > 0 使得,则称 || · ||A
和 || · ||B 等价 。
BAB xCxxC |||||||||||| 21
定理 Rn 上一切范数都等价。
可以理解为对任何向量范数都成立。 HW,p.62 #6,#7
§ 1 Norms of Vectors and Matrices – Matrix Norms
矩阵范数 /* matrix norms */
定义 Rm?n空间的 矩阵范数 || · || 对任意 满足：
nmRBA,
00||||;0||||)1( AAA （ 正定性 /* positive definite */ )
||||||||||)2( AA C对任意 (齐次性 /* homogeneous */ )
||||||||||||)3( BABA （ 三角不等式 /* triangle inequality */ )
(4)* || AB ||? || A || · || B || （ 相容 /* consistent */ 当 m = n 时 )
In general,if we have
|| AB || || A ||? · || B ||?,then
the 3 norms are said to be consistent.
Oh haven’t I had enough
of new concepts? What do I need
the consistency for?
When you have to analyze
the error bound of AB – imagine you doing it
without a consistent matrix norm…
§ 1 Norms of Vectors and Matrices – Matrix Norms
常用矩阵范数：
Frobenius 范数
n
i
n
j
ijF aA
1 1
2|||||| —向量 || · ||2的直接推广对方阵 以及 有nnRA nRx
22 |||||||||||| xAxA F
利用 Cauchy 不等式可证。 22 |||||||||| yxyx
算子 范数 /* operator norm */
由向量范数 || · ||p 导出关于矩阵 A? Rn?n 的 p 范数,
px
p
p
p xAx
xAA
px
||||m a x|||| ||||m a x||||
10 ||||
则
ppp
ppp
xAxA
BAAB
||||||||||||
||||||||||||
特别有,?
n
j
ijaA ni
1
||m a x||||
1
（ 行和范数 ）
n
i
ijaA nj
1
1 ||m a x|||| 1
（ 列和范数 ）
)(|||| m a x2 AAA T （ 谱范数 /* spectral norm */）
矩阵 ATA 的最大特征根 /* eigenvalue */
HW,p.62
#2,#4,#5
§ 1 Norms of Vectors and Matrices – Matrix Norms
注,?Frobenius 范数 不是 算子范数。
我们只关心有相容性的范数,算子范数 总是相容的。
即使 A中元素全为实数，其特征根和相应特征向量
/* eigenvector */ 仍可能是复数。将上述定义中绝对值换成 复数模 均成立。
若不然，则必存在某个向量范数
|| · ||v 使得 对任意 A 成立。
v
vF
x
xAA
x ||||
||||m a x||||
0?
Counterexample? 1
||||
||||m a x||||
0
v
vF
x
xIIn
x?
谱半径 /* spectral radius */
定义 矩阵 A的 谱半径 记为
(A) =,其中?i 为
A 的特征根。
||m a x1 ini
Re
Im
(A)
§ 1 Norms of Vectors and Matrices – Spectral Radius
定理 对任意算子范数 || · || 有 ||||)( AA
证明,由算子范数的相容性，得到 |||||||||||| xAxA
将任意一个特征根?所对应的特征向量 代入u?
|||||||||||| uAuA |||||||||| uu
定理 若 A对称，则有 )(||||
2 AA
证明,)()(|||| 2
m a xm a x2 AAAA T
A对称若?是 A 的一个特征根，则?2 必是 A2 的特征根。
又：对称矩阵的特征根为实数，即?2(A) 为非负实数，
故得证。
)()( 22m a x AA 对某个 A 的特征根?成立所以 2-范数亦称为谱范数 。
§ 1 Norms of Vectors and Matrices – Spectral Radius
定理 若矩阵 B 对某个算子范数满足 ||B|| < 1，则必有
① BI? 可逆； ②
||||1
11
BBI
证明,① 若不然，则 有非零解，即存在非零向量 使得
0)( xBI
0x? 00 xxB 1
||||
||||
0
0
x
xB 1|||| B?
② IBIBI 1))(( 11 )()( BIBBI
11 )()( BIBIBI?
||)(||||||1||)(|| 11 BIBBI
