第四章 解线性方程组的迭代法
/* 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
i x x
1
1 | | || ||
? ?
?
?
n
i i
x x
1
2
2 | | || ||
? p n
i
p
i p x x
/ 1
1
| | || || ? ?
?
?
| | max || ||
1 i n i
x x
? ? ?
? ? 注,
??? ? ||||||||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
i x x
1
1 | | || ||
? ?
?
?
n
i i
x x
1
2
2 | | || ||
? p n
i
p
i p x x
/ 1
1
| | || || ? ?
?
?
| | max || ||
1 i n i
x x
? ? ?
? ? 注,
??? ? ||||||||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
