§ 3 矩阵的 LU分解
矩阵的 LU分解
对称矩阵的平方根法
改进的平方根法
解三对角方程组的追赶法二、平方根法工 程 实 际 计 算 中,线 性 方 程 组 的 系 数 矩 阵 常 常具 有 对 称 正 定 性,即 其 各 阶 顺 序 主 子 式 及 全 部 特 征值 均 大 于 零 。 矩 阵 的 这 一 特 性 使 它 的 三 角 分 解 也 有更 简 单 的 形 式,从 而 导 出 一 些 特 殊 的 解 法,如 平 方根 法 与 改 进 的 平 方 根 法 。
,
A
L
T
A LL
L
定 理,设 是 对 称 正 定 矩 阵,则 存 在 唯 一的 非 奇 异 下 三 角 阵 使 得且 的 对 角 元 素 皆 为 正 。
证明 1； 证明 2。
定理证明（ 1）
11
22
1
11
11 12 1
112
11 11
1,
1,
2
1
2
1
(,,
,
1
),
nn
n
nn
nn
n
n nn n
u
u
u
A
uu
A
LLU
D di ag u u P D U
u u u
u
U
u
u
U
P
u
uu
证,因 对 称 正 定,其 各 阶 顺 序 主 子 式 均 大 于 零,故 有其 中 为 单 位 下 三 角 矩 阵,为 上 三 角 阵 。
令 则 为 单 位 上 三 角 阵 。
T
TT
TT
A L U L D P A P D L
A P D
D
P
P
PLLU
故由 分 唯 一 性解 的定理证明（ 2）
1 1 1 1
11
0,/ 0 ( 2,3,,)
(,,
,
(
( ),
)
)
ii i i
T
n
T
n
T
T
TT T
u D u D D i n
D di ag
DDP
u u D D D
A
A
L DP
P DP P P LD PLD
证 明,由 于 是 对 称 正 定 的 其 顺 序 主 子式 均 大 于 零 。 故令则其 中 为 非 奇 异 下 三 角 阵 且 对 角 元 素 皆
（ 存 在 性 ）
为 正 数 。
1 1 1 1 1 1
1
1
1
1
,
(
( ) (
,
) ( )
(
)
)
T T T T T T
TT
TT
TT
L G L LL G
GL
A LL G G
L G L G
L G G G L
L
GL
G
G
L G I
,假 定 存 在 非 奇 异 下 三 角 阵 其 对 角 元素 皆 为 正 数,且 使 得 于 是 有因 为 上 三 角 阵,为 下 三 角 阵,故 由 上 式 得即 与 假唯 一 性设 矛 盾 。
平方根 (Cholesky分解法）法
11 11 12 1
21 22 22 2
12
11
2
2
1
00
0
0
00
0 ( 1
( ) ( 1,
,2,,),0
( ),
,,
(
2 ),
n
nT
n n nn nn
ii j
j
jj jj jk
k
ij ij i
k
kj
l l l l
l l l l
A L L
l l l l
l i n l
l a l j n
l a l
jk
l
由其 中 由 矩 阵 乘 法 及 当 时得
1
1
) / ( 1,,) ;
j
k jj
k
l i j n
0
1 1 1 2 2 2
1
( 2,3,,) ( 3,)
0
,i
k
il l i n l l i n
这 里 规 定 。 计 算 顺 序 是 按 列 进 行,即
。
1
1
1
( ) / ( 1
,2,,),
( ) / (,
,;
1,,1 )
2,
.
T
i
i i ik k ii
k
n
i i k i k ii
k
T
i
A
Ly b y L
A x L L x
x y x
b
y b l y l i n
x y l x l i n n
当 矩 阵 完 成 平 方 根 分 解 后,求 解即 求 解 两 个 三 角 形 方 程 组
(1) 求 （ ）,求
＝,
3
,
/6
n
A
G a u ss
A
Ln
b L A
y x b
由 于 的 对 称 性,平 方 根 法 的 乘 除 运 算 量为 数 量 级,约 是 消 去 法 的 一 半 。 上机 计 算 时,所 需 存 储 单 元 也 少,只 要 存 储 的下 三 角 部 分 和 右 端 项,计 算 中 存 放 在 的 存储 单 元,存 储 在 的 存 储 单 元 。
但 这 种 方 法 在 求 时 需 作 次 开 方 运 算,这样 又 增 加 了 计 算 量 。 为 了 避 免 开 方,可 使 用 改进 的 平 方 根 方 法 。
改进平方根法
1
21 2
12
21 1
2
1
1
1
1
1
(,1)
1
,
0
jj jk
T
n n n
n
n
l
d
ld
A L DL
l l d
ll
l
l j k
其 中 由 比 较 法 得
1
2
1
1
1
1
1
1
1;
( ) / ( 1,,),;
( ) / ( 1,,)
,
1,2,,
1,2,
.
,,
i
i ii ik k
k
i
ji ji jk k ik i
k
i
i ii ik ik
k
i
ji ji ik jk i
ik k k
k
i
d a l d
l a l d l d j i n
d a t l
l a t l d j i
in
in
n
t l d
对 于上 式 虽 避 免 了 开 方 运 算,但 增 加 了 相 乘 因 子,引 进 变 量对 于 有
11
1
1
1
/;
/ ( 1,,2,1 );
( 2,,),
,
.
T
T
n
T
i
i i ik k
k
nn
n
i i i k i k
k
T
i
LL
yb
yb
L DL
L DL
x y d
x y d l x i n
A
L y b DL
l
xy
y i n
对 称 正 定 矩 阵 按 分 解 和 按 分 解计 算 量 差 不 多,但 分 解 不 需 要 开 方 计 算 。
求 解 计 算 公 式三、追赶法
A x d?
在 数 值 计 算 中,如 三 次 样 条 插 值 或 用 差 分 方 法解 常 微 分 方 程 边 值 问 题,常 常 会 遇 到 求 解 以 下 形 式的 方 程 组此 系 数 矩 阵 的 非 零 元 素 集 中 分 布 在 主 对 角 线 及 其 相 邻两 次 对 角 线 上,称 为 三 对 角 矩 阵 。 方 程 组 称 为 三 对 角方 程 组 。
11
2 2 2
1
2
1 1 1
1
2
11
ii i i
nnn
n
i
n
n
n
n n
d
d
d
d
bc
a b c
ab
d
c
a b c
a
x
b
x
x
x
x
11
22
1
2
3
1
1
1
0
0( 2,3,,1 )
0
1
1
( 1,,
2)
1
,1
n
n
i i i i i
n
n
n
i
uc
lu
bc
b a c a c i n
ba
c
A L U l
c
l
i
u
n
c
定 理,设 三 对 角 方 程 组 系 数 矩 阵 满 足 下 列 条 件,
则 它 可 分 解 为其 中 为 已 给 出 的,且 分 解 是 唯 一 的,
定理证明（ 1）
11
1
1
1
1
1
1
,,
/ ( 2
0
( 2,3,,)
,3,
( 1 2,)
),
,
i i i
ii
i i i
i i i i
i
i
i
bu
a l u
ui
ub
l a u i
im
b c l u
m
l
m
A
u b c
将 上 式 右 端 按 乘 法 规 则 展 开 并 与 进 行 比 较 得如 果 则 由 式 得，,上 可定理证明（ 2）
11
()
1 1 1
111
11
/ ( 2,3
1
,,)
k k k k k
kk
k
k k k
nnn
nn
uc
uc
A a b c
a b c
a
k
u b c a u k
Ga us s
n
b
按 消 去 法 步 骤 易 得,经 次 消 元 后,三 对角 方 程 的 系 数 矩 阵 变 为其 中 。
定理证明（ 3）
1 1 2 2 2
1 2 1 2 1 2 1 2 1 212
2 2 2
1
11
1 2 1 2 1 2 1 2 1
1
2
2
2)
1
(
1
0.
0
0 ( 1
,,
,2,
,
)
i
A
b c b a c
b b c a b b c a b cca
u
ub
b b b a b c c
A
LU
a b c
u
u i n
bc
u b b b
由 于 满 足 定 理 所 给 条 件,显 然 有又 因 为 于 是从 而 有
。
故 且 矩 阵 仍 满 足 定 理 条 件 。 依 此 类 推 可 得 出因 此 由 上 面 公 式 唯 一 定 了 和确 。
追赶法的计算公式
1
1
1
1
1
1
1
1
/ ( 2,3,,)
( 2,3,,)
/
( ) / ( 1,2,,1 )
,
i i i
i i i
k k k k
n n n
k k k k
i
k
A L U
yd
y d l y k n
x y u
ub
l a u i m
Ux
x y c x u
u b c
y
d
k n n
l
Ly
分 解 公 式,
解 得,
再 解 得
,,
,,
,
G a u s s追 赶 法 的 基 本 思 想 与 消 去 法 及 三 角 分 解 法相 同 只 是 由 于 系 数 中 出 现 了 大 量 的 零 可 使 计 算 公 式简 化 减 少 了 计 算 量 。 可 证 当 系 数 矩 阵 为 严 格 对 角 占优 时 此 方 法 具 有 良 好 的 数 值 稳 定 性 。
矩阵的 LU分解
) (
T
T
PL
TTTTA L U L D P P D P DP D D P PL D P L
唯 一 性平方根法改进的平方根法
11 11
22
12
11
2
1
22
11
2 1 2 2
12
2
11
2
2
1
( ) ( 1,2,,),
( ) / (
00
0
nn
n
nn
nn
nn
j
j j j j j k
k
i j i j i k j k j j
nn
u u u
u
U
u
l
u
u
D
u
u
u
D
u
l a l j n
l a l l l i
ll
L
l l l
L
为 单 位 下 三 角 矩 阵
＝
，
，
＝
，
1
1
1,,);
j
k
jn
§ 4.向量和矩阵的范数及方程组的性态
向量范数
矩阵的范数
方程组的性态及矩阵条件数一、向量范数
,
:
,
,,
1,; ( )
2,( )
3,
0,
0
,
0
n
n
xx
R
x y x
xx
x
y
x
,x
x
y
R
x设 对 任 意 向 量 按 一 定 的 规 则 有 一 实数 与 之 对 应 记 为 若 满 足定 义对 任 意为 任 意正实且 当 且 定仅数 齐 次当
( )
x x
三 角 不 等 式则 称 为 向 量 的 范 数向量范数向量范数
1
2
22
12
2
i
1
()n
n
i
x xx x
1i1
1
n
n
i
x x x x
1i 1m a x {,,} m a x { }n inx x x x
1/
1
,
pn
p
ip
i
xx
,
1 1,
,( 1 )
-
,
2
,
ii
n
yR x i n
x,y
可 验 证 上 面 范 数 均 满 足 范 数 定 义 的 条 件 。
以 为 例显 然 满 足 条 件 ;
2 由 于范 数为 向 量,而 其 分 量为 实 数,故 有
1
11
1
ma
ma
max
x m a x
x
i i i i
i n i n
i in
i i
n
yy
y
x
x y x
x
x + y
( 1,2,3 ) Tx例,计 算 向 量 的 各 种 范 数 。
'
'
,
,0
n
mM
n
mx
x
x M x
R如 果 中 两 个 范 数 和,存 在 实 数,
使 得 对 任 意 维 向 量 都 有
,
则 称 这 两 个 范 数 是 的 。 对 两 个 等 价 范 数 而 言,
同 一 向 量 相 同等 价序 列 有 的 极 限 。
21 3,146,.xx x解,
12?－ 范 数,－ 范 数 和 － 范 数 是不 难 证 明,等 价 的 。
2 － 范－ 范 数 和 数 等 价 。
如 不 作 说 明,今 后 是 指 任 意 一 种 向 量 范 数 。
1m a x,ji inx x x设 则
1m a x iinxx例,
2 2 2
12 2n xx x x
n n
2
2
x
xx
n?
jxx
2 2 2
12 2,nx x x x
二、矩阵的范数
AA
n A,对 任 意 阶 方 阵,按 一 定 的 规 则 由 一实 数 与 之 对 应,记 为 。
义若定满 足
1,0,0 0 ;
2.,
3.,
4
(
)
)
)
(
(
A A A
A A
A B A B,A B n
AB A B
且 当 且 仅 当为 任 意 实 数对 任 意 两 个 阶 方正阵定三 角 不齐 次
（ 相等 式
,容 性 条 件 ）
AA为 矩 阵则 称 的 范 数 。
1
m a x
()
m a x
,1
x ma
n
x
ij
xx
A n R
Ax
A
x
Aa
Ax xx
A
x x x
Ax
A Ax
x
n x n
定 理,设 为 阶 方 阵,是 中 的 向 量 范 数,则是 一 种 矩 阵 范 数,
且 称 其 为 由 向 量 范 数 。
证,设 为 任 意 阶 方 阵,为 任 意 维 非 零 向 量 。
因 为 为 范 数 是 的 单 位 向 量,故诱 导 出 的 矩 阵 范 数
1
11
1
1 0,0,m a x 0.
0 0
0,
2 m a x m a x
m a x,
3,
x
xx
x
A A A A x
A A x A x
A
A A x A x
A x A
n A B
AB
，显然 若 则反之，若
，
对任意两个 阶方阵 和,
11
1 1 1
m a x ( ) m a x
m a x ( ) m a x m a x
,
xx
x x x
A B x A x B x
A x B x A x B x
AB
11
11
4
,
m a x ( ) m a x ( )
m a x m a x
5
xx
xx
nx
Ax
A Ax A x
x
AB AB x A Bx
A Bx A B x
AB
n x Ax A x
，对任意 维非零向量,
有 即故有
，对任意 维向量,都有 。
这一性质称为矩阵范数与向量范数的相容性。
可由三种常用的向量范数诱导出矩阵范数。
矩阵范数例
2
2 1121
,m a x
()
T
x
ij
A A x A A
Aa n
其 中 是 的 。最 大 特 征 值又 称 为 谱 范 数 。 设 为 阶 方 阵 。
与前述三种向量范数相容的三种矩阵范数：
1
11 11
1
,m a x x
1
ma
n
ij
x j n
i
A A x a
为最 大矩 阵 的列 向 量 的 的 称 矩 阵 的值 为－ 范 数 列 范 数 。
11
1
,m a x
1
m a x
n
ij
x i n
j
A A x a
行最 大为 矩 阵 的向 量 的 － 范 数 的 称 矩 阵 的为值 行 范 数 。
2
12
34
,
n
R
AA
如 果 将 矩 阵 范 数 看 作 空 间 上 的 向 量 范 数,
则 由 向 量 范 数 的 等 价 性 可 得 矩 阵 范 数 的 等 价 性 。
例,计 算 的 各 种 范 数 。
12 6,7,5,4 6,A A A解,
/
AA
A A A A A A
矩 阵 的 误 差 可 用 矩 阵 范 数 表 示,设 是 的 近似 矩 阵,分 别 称 为 的 关 于 范数 的 绝 对 误 差 与
、
相 对 误 差 。
矩阵 A的谱半径
1
( 1,2,,)
( ) m
,
ax
nn
i
i
in
A
A R i n
A
定 义,设 的 特 征 值 为 称为 的 谱 半 径 。
,( A ) AA A定 理,为 的 任 意 矩 阵 范 数,
(,
)
A
()
AxxxAxx
xAxAAA?
三,方程组的性态与矩阵条件数
矩阵的条件数
右端项 b的扰动对解的影响
系数矩阵 A的扰动对解的影响
条件数的 定义 和 性质
,病态”方程的经验判断
误差分析
1、矩阵的条件数一 个 实 际 问 题 化 为 数 学 问 题,初 始 数 据 往 往 会 有误 差,即 有 扰 动,从 而 使 计 算 结 果 产 生 误 差 。
1 2 1
1 2 1
1 2 2
1 2 2
22
.
1,0 0 0
21
.
1,0 0 0 0 1 2
0 1 2 0
,0 0 0 0
11
x x x
x x x
xx
x x x
x
例,方 程 组而 方 程 组
5
,1012
1
2
比 较 这 两 个 方 程 组 可 以 看 出,他 们 只 是 右 端 项 有 微 小 的差 别,最 大 相 对 误 差 为 但 它 们 的 解 却 大 不 相 同,解 分量 的 相 对 误 差 至 少 为 。
Ab
A x b
A
A
,如 果 矩 阵 或 常 数 项 的 变 化,引起 方 程 组 解 的 变 化,则 称 此 方 程 组 为
,矩 阵 称 为,病 态,矩 阵 （ 相对 于 方 程 组 而 言 ） 。
否 则 称 方 程 组 为,良 态,方 程 组,称 为
,良 态,矩 阵 。
矩 阵 的,病 态
,病
” 性微 小质 是态,
矩 阵方 程本 身定组大义巨的 特 性 。
为了定量刻画方程组的“病态”程度，下面对方程组 Ax＝ b就系数矩阵的扰动或右端项有扰动的两种情况进行讨论。
右端项 b的扰动对解的影响
1
11
11
,
)
(
Ax b A x b x A b
A b A A bx
b b x x
A x x b b
A
xA
bxb
xb
x
A
A
b A b
A
设 有 扰 动,相 应 解 的 扰 动 记 为 即由两 边 取 范 数又 因 为
，
1
,,
AA?
此 式 表 明 当 右 端 项 有 扰 动 时 解 的 相 对 误 差 不 超 过右 端 项 的 相 对 误 差 的 倍 。
系数矩阵 A的扰动对解的影响
1
1
1
1
1
1
1
,
,
( ) ( )
()
( ) 0
1
1
1
()
A
x
A A x x b A x A x
x
A
AA
AAxA
Ax A
x
A A A
A
AA
A
x A A x x A A x x
A
如 果 右 端 项 无 扰 动,系 数 矩 阵 有 扰 动,相 应 的 解的 扰 动 仍 记 为 则如 果 充 分 小,使 得 则 由 上 式 得
1
1
A
AA
A?
上 式 表 明,当 系 数 矩 阵 有 扰 动 时,解 的 扰 动 仍 与有 关 。 越 大,解 的 扰 动一 般 地,也 越 大 。
条件数的定义
-1,
,
AA综 上 分 析 可 知 量 实 际 上 刻 划 了 解 对 原 始 数 据 变化 的 灵 敏 程 度 即 刻 划 了 方 程 组 的,病 态,程 度 。
1( ) ( 1,
2
v vvA c o n d A A A v
A
,设 为 非 奇 异 阵,称 数定 义或 ） 为 矩 阵 的 条 件 数 。
-1
1 m a x
22
m in
2
1
2
1
( 1 )
()
( 2 ) A,(
()
(
(
)
),
)
T
T
n
n
AA
AA
AA
AA
A c o n
c o n d
c o n A
A
A
A
d
d
；
的 谱 条 件 数当 为 对 称 矩 阵 时,
其 中,为 的 绝 对 值 最 大 和 绝 对 值 最 小 的 特 征 值 。
常用的条件数，有条件数的性质
11
2
2
1,
2
3
( ) 1
( ) 1.
( ) ( )
( ) 1
(
0
)
v
v
v
vv
vv
c ond A
c ond A A A A A I
c ond c A c ond A
c ond A
c on
A
A
A
c
d RA c
AR
on
非 奇 异 矩 阵非 奇 异
＝
,对 任 何,都 有由 定 义
,设 为 （ 常 数 ）,则
,如 果 为 矩 阵,则矩 阵 且正 交非 奇 异 正 交；
如 果 为 矩 阵,为 矩 阵,则
22
.( ) ( )d AR c ond A?
3
11
1
2
11
1
2 3 1
1 1 1
1 2 1
n
n
H n
H ilb e
n
t
n
H
n
r
例,矩 阵计 算 的 条 件 数 。
1
3 3
9 36 30
36 192 180
30 180 1
11
1
23
1
80
11
234
11
,
1
3 4 5
HH
解,
nHn一 般 矩 阵 当 越 大 时,病 态 越 严 重 。
1
3
6
6
3
3
33
11
()
( ) 2,9
408
( 1 ) ( ),
.748
1 0,
6
c o n d H H H
H c o n d H
c o n d H
计 算 条 件 数同 样 可 计 算
11
22
33
1 1 11
1
2 3 6
1
1 1 1 13
2 1
2 3 4 12
1
47111
603 4 5
xx
xx
xx
（ ） 考 虑
11
22
33
33
3
1,0 0 0,5 0 0 0,3 3 3 1,8 3
0,5 0 0 0,3 3 3 0,2 5 0 1,0 8
0,3 3 3 0,2 5 0 0,2 0 0 0,7 8 3
( ) ( ),
( 1,0 8 9 5,0,4 8 8 0,1,4 9 1 )
T
Hb
xx
xx
xx
H H x x b b
xx
设 及 有 微 小 误 差 （ 取 位 有 效 数 字 ） 有简 记 为其 解 为
3 3
3
3
( 1,0 8 9 5,0,4 8 8 0,1,4 9 1 ),( 1,1,1 )
( 0,0 8 9 5,0,5 1 2 0,0,4 9 1 0 )
0,1 8 1 0 0,0 2 %
0,5 1 2 0
0,1 8 2 % 5 1,2 %
1
5 0
TT
T
x x x
x
H
H
bx
bx
Hb
由 于
，
这 表 明 与 相 对 误 差 不 超 过 0.2%,而 引 起解 的 相 对 误 差 超 过 ％,
“病态”方程的经验判断计 算 条 件 数 需 要 求 矩 阵 的 逆,因 而 比 较 困 难 。 根据 数 值 经 验,在 下 列 情 况 下,方 程 组 常 是,病 态,的 。
1（ ） 在 用 主 元 素 法 时 出 现 小 主 元 ；
2 A
A
（ ） 如 果 的 最 大 特 征 值 和 最 小 特 征 值 之 比 （ 按 绝 对 值 ）
是 大 的,则 是,病 态,的 。
3（ ） 系 数 矩 阵 中 有 行 （ 或 列 ） 近 似 线 性 相 关,或 系 数 行列 式 的 值 近 似 于 零 。
,
d e t ( ) 0,( ) ( ) 1,n
AI
A c o n d A c o n d I
但 这 不 是 绝 对 的,如 当 为 很 小 的 数 时,有但 方 程 组 状 态 良 好 。
4 A
A
（ ） 系 数 矩 阵 元 素 间 数 量 级 相 差 很 大,并 且 无 一 定 规 则可 能,病 态,。
1;
.
( ),)
,
,
(
A
P
P A Q y P b
y Q x
c
xb
P
o n d P A Q c
Q
o n d A
Q
用 选 主 元 素 的 消 去 法 不 能 解 决 病 态 问 题,对 病态 方 程 组 可 采 用 高 精 度 的 算 术 运 算 或 采 用 预 处 理方 法 。 即 将 求 解 转 化 为 一 等 价 方 程 组非 奇 异对选角择 使一 阵 或 者般 选 择矩 阵为 三 角 矩 阵 。
2、误差分析 *
**
*
A x b x
x r b A x
rx
r
在 求 得 方 程 组 的 一 个 近 似 解 后,检 验 精 度 的 一 个简 单 方 法 是 将 代 入 方 程 组 求 得 。
如 果 很 小,就 认 为 解 比 较 准 确 。 但 在,病 态,严 重 的方 程 组,也 有 即 使 残 差 量 很 小,近 似 解 与 准 确 解 的 差 仍很残 量 （ 余 量 ）
大 的 情 形 。
1 2 1
1 2 1
*
1
5
2
1,1
22
1,0 0 0 0 1 2 0
( 2,0 ) ( 1,1 ) ( 1,
( 2,2 ) ( 2,2,0 0 0 0 1 ) ( 0,1 0
)
1 )
T
T T T
TT
x x x
x x x
x
r
x
xx
上 例 中,方 程 组若 以 作 为 它 的 近 似 解,其 残 量很 小,但 解 的 误 差却 不 小 。
* 1 * 1
*
1
(
)
x
b A x A
x
x
x
x x A b A x A r A r
证,因 为所 以
1Ar
b
A
1 (),
rrA A c o n d A
bb
由 上 式 可 看 出,当 方 程 组,病 态,严 重 时,条 件 数 很大,即 使 残 量 很 小,解 的 相 对 误 差 仍 可 能 很 大 。
*
*
*
-
(,)
xx r
c o n d A
x
x x A x b
rx
b
,设 和 分 别 是 方 程 组 的 准 确 解 和 近 似 解,
为 的 残 量,则定 理
矩阵的 LU分解
对称矩阵的平方根法
改进的平方根法
解三对角方程组的追赶法二、平方根法工 程 实 际 计 算 中,线 性 方 程 组 的 系 数 矩 阵 常 常具 有 对 称 正 定 性,即 其 各 阶 顺 序 主 子 式 及 全 部 特 征值 均 大 于 零 。 矩 阵 的 这 一 特 性 使 它 的 三 角 分 解 也 有更 简 单 的 形 式,从 而 导 出 一 些 特 殊 的 解 法,如 平 方根 法 与 改 进 的 平 方 根 法 。
,
A
L
T
A LL
L
定 理,设 是 对 称 正 定 矩 阵,则 存 在 唯 一的 非 奇 异 下 三 角 阵 使 得且 的 对 角 元 素 皆 为 正 。
证明 1； 证明 2。
定理证明（ 1）
11
22
1
11
11 12 1
112
11 11
1,
1,
2
1
2
1
(,,
,
1
),
nn
n
nn
nn
n
n nn n
u
u
u
A
uu
A
LLU
D di ag u u P D U
u u u
u
U
u
u
U
P
u
uu
证,因 对 称 正 定,其 各 阶 顺 序 主 子 式 均 大 于 零,故 有其 中 为 单 位 下 三 角 矩 阵,为 上 三 角 阵 。
令 则 为 单 位 上 三 角 阵 。
T
TT
TT
A L U L D P A P D L
A P D
D
P
P
PLLU
故由 分 唯 一 性解 的定理证明（ 2）
1 1 1 1
11
0,/ 0 ( 2,3,,)
(,,
,
(
( ),
)
)
ii i i
T
n
T
n
T
T
TT T
u D u D D i n
D di ag
DDP
u u D D D
A
A
L DP
P DP P P LD PLD
证 明,由 于 是 对 称 正 定 的 其 顺 序 主 子式 均 大 于 零 。 故令则其 中 为 非 奇 异 下 三 角 阵 且 对 角 元 素 皆
（ 存 在 性 ）
为 正 数 。
1 1 1 1 1 1
1
1
1
1
,
(
( ) (
,
) ( )
(
)
)
T T T T T T
TT
TT
TT
L G L LL G
GL
A LL G G
L G L G
L G G G L
L
GL
G
G
L G I
,假 定 存 在 非 奇 异 下 三 角 阵 其 对 角 元素 皆 为 正 数,且 使 得 于 是 有因 为 上 三 角 阵,为 下 三 角 阵,故 由 上 式 得即 与 假唯 一 性设 矛 盾 。
平方根 (Cholesky分解法）法
11 11 12 1
21 22 22 2
12
11
2
2
1
00
0
0
00
0 ( 1
( ) ( 1,
,2,,),0
( ),
,,
(
2 ),
n
nT
n n nn nn
ii j
j
jj jj jk
k
ij ij i
k
kj
l l l l
l l l l
A L L
l l l l
l i n l
l a l j n
l a l
jk
l
由其 中 由 矩 阵 乘 法 及 当 时得
1
1
) / ( 1,,) ;
j
k jj
k
l i j n
0
1 1 1 2 2 2
1
( 2,3,,) ( 3,)
0
,i
k
il l i n l l i n
这 里 规 定 。 计 算 顺 序 是 按 列 进 行,即
。
1
1
1
( ) / ( 1
,2,,),
( ) / (,
,;
1,,1 )
2,
.
T
i
i i ik k ii
k
n
i i k i k ii
k
T
i
A
Ly b y L
A x L L x
x y x
b
y b l y l i n
x y l x l i n n
当 矩 阵 完 成 平 方 根 分 解 后,求 解即 求 解 两 个 三 角 形 方 程 组
(1) 求 （ ）,求
＝,
3
,
/6
n
A
G a u ss
A
Ln
b L A
y x b
由 于 的 对 称 性,平 方 根 法 的 乘 除 运 算 量为 数 量 级,约 是 消 去 法 的 一 半 。 上机 计 算 时,所 需 存 储 单 元 也 少,只 要 存 储 的下 三 角 部 分 和 右 端 项,计 算 中 存 放 在 的 存储 单 元,存 储 在 的 存 储 单 元 。
但 这 种 方 法 在 求 时 需 作 次 开 方 运 算,这样 又 增 加 了 计 算 量 。 为 了 避 免 开 方,可 使 用 改进 的 平 方 根 方 法 。
改进平方根法
1
21 2
12
21 1
2
1
1
1
1
1
(,1)
1
,
0
jj jk
T
n n n
n
n
l
d
ld
A L DL
l l d
ll
l
l j k
其 中 由 比 较 法 得
1
2
1
1
1
1
1
1
1;
( ) / ( 1,,),;
( ) / ( 1,,)
,
1,2,,
1,2,
.
,,
i
i ii ik k
k
i
ji ji jk k ik i
k
i
i ii ik ik
k
i
ji ji ik jk i
ik k k
k
i
d a l d
l a l d l d j i n
d a t l
l a t l d j i
in
in
n
t l d
对 于上 式 虽 避 免 了 开 方 运 算,但 增 加 了 相 乘 因 子,引 进 变 量对 于 有
11
1
1
1
/;
/ ( 1,,2,1 );
( 2,,),
,
.
T
T
n
T
i
i i ik k
k
nn
n
i i i k i k
k
T
i
LL
yb
yb
L DL
L DL
x y d
x y d l x i n
A
L y b DL
l
xy
y i n
对 称 正 定 矩 阵 按 分 解 和 按 分 解计 算 量 差 不 多,但 分 解 不 需 要 开 方 计 算 。
求 解 计 算 公 式三、追赶法
A x d?
在 数 值 计 算 中,如 三 次 样 条 插 值 或 用 差 分 方 法解 常 微 分 方 程 边 值 问 题,常 常 会 遇 到 求 解 以 下 形 式的 方 程 组此 系 数 矩 阵 的 非 零 元 素 集 中 分 布 在 主 对 角 线 及 其 相 邻两 次 对 角 线 上,称 为 三 对 角 矩 阵 。 方 程 组 称 为 三 对 角方 程 组 。
11
2 2 2
1
2
1 1 1
1
2
11
ii i i
nnn
n
i
n
n
n
n n
d
d
d
d
bc
a b c
ab
d
c
a b c
a
x
b
x
x
x
x
11
22
1
2
3
1
1
1
0
0( 2,3,,1 )
0
1
1
( 1,,
2)
1
,1
n
n
i i i i i
n
n
n
i
uc
lu
bc
b a c a c i n
ba
c
A L U l
c
l
i
u
n
c
定 理,设 三 对 角 方 程 组 系 数 矩 阵 满 足 下 列 条 件,
则 它 可 分 解 为其 中 为 已 给 出 的,且 分 解 是 唯 一 的,
定理证明（ 1）
11
1
1
1
1
1
1
,,
/ ( 2
0
( 2,3,,)
,3,
( 1 2,)
),
,
i i i
ii
i i i
i i i i
i
i
i
bu
a l u
ui
ub
l a u i
im
b c l u
m
l
m
A
u b c
将 上 式 右 端 按 乘 法 规 则 展 开 并 与 进 行 比 较 得如 果 则 由 式 得，,上 可定理证明（ 2）
11
()
1 1 1
111
11
/ ( 2,3
1
,,)
k k k k k
kk
k
k k k
nnn
nn
uc
uc
A a b c
a b c
a
k
u b c a u k
Ga us s
n
b
按 消 去 法 步 骤 易 得,经 次 消 元 后,三 对角 方 程 的 系 数 矩 阵 变 为其 中 。
定理证明（ 3）
1 1 2 2 2
1 2 1 2 1 2 1 2 1 212
2 2 2
1
11
1 2 1 2 1 2 1 2 1
1
2
2
2)
1
(
1
0.
0
0 ( 1
,,
,2,
,
)
i
A
b c b a c
b b c a b b c a b cca
u
ub
b b b a b c c
A
LU
a b c
u
u i n
bc
u b b b
由 于 满 足 定 理 所 给 条 件,显 然 有又 因 为 于 是从 而 有
。
故 且 矩 阵 仍 满 足 定 理 条 件 。 依 此 类 推 可 得 出因 此 由 上 面 公 式 唯 一 定 了 和确 。
追赶法的计算公式
1
1
1
1
1
1
1
1
/ ( 2,3,,)
( 2,3,,)
/
( ) / ( 1,2,,1 )
,
i i i
i i i
k k k k
n n n
k k k k
i
k
A L U
yd
y d l y k n
x y u
ub
l a u i m
Ux
x y c x u
u b c
y
d
k n n
l
Ly
分 解 公 式,
解 得,
再 解 得
,,
,,
,
G a u s s追 赶 法 的 基 本 思 想 与 消 去 法 及 三 角 分 解 法相 同 只 是 由 于 系 数 中 出 现 了 大 量 的 零 可 使 计 算 公 式简 化 减 少 了 计 算 量 。 可 证 当 系 数 矩 阵 为 严 格 对 角 占优 时 此 方 法 具 有 良 好 的 数 值 稳 定 性 。
矩阵的 LU分解
) (
T
T
PL
TTTTA L U L D P P D P DP D D P PL D P L
唯 一 性平方根法改进的平方根法
11 11
22
12
11
2
1
22
11
2 1 2 2
12
2
11
2
2
1
( ) ( 1,2,,),
( ) / (
00
0
nn
n
nn
nn
nn
j
j j j j j k
k
i j i j i k j k j j
nn
u u u
u
U
u
l
u
u
D
u
u
u
D
u
l a l j n
l a l l l i
ll
L
l l l
L
为 单 位 下 三 角 矩 阵
＝
，
，
＝
，
1
1
1,,);
j
k
jn
§ 4.向量和矩阵的范数及方程组的性态
向量范数
矩阵的范数
方程组的性态及矩阵条件数一、向量范数
,
:
,
,,
1,; ( )
2,( )
3,
0,
0
,
0
n
n
xx
R
x y x
xx
x
y
x
,x
x
y
R
x设 对 任 意 向 量 按 一 定 的 规 则 有 一 实数 与 之 对 应 记 为 若 满 足定 义对 任 意为 任 意正实且 当 且 定仅数 齐 次当
( )
x x
三 角 不 等 式则 称 为 向 量 的 范 数向量范数向量范数
1
2
22
12
2
i
1
()n
n
i
x xx x
1i1
1
n
n
i
x x x x
1i 1m a x {,,} m a x { }n inx x x x
1/
1
,
pn
p
ip
i
xx
,
1 1,
,( 1 )
-
,
2
,
ii
n
yR x i n
x,y
可 验 证 上 面 范 数 均 满 足 范 数 定 义 的 条 件 。
以 为 例显 然 满 足 条 件 ;
2 由 于范 数为 向 量,而 其 分 量为 实 数,故 有
1
11
1
ma
ma
max
x m a x
x
i i i i
i n i n
i in
i i
n
yy
y
x
x y x
x
x + y
( 1,2,3 ) Tx例,计 算 向 量 的 各 种 范 数 。
'
'
,
,0
n
mM
n
mx
x
x M x
R如 果 中 两 个 范 数 和,存 在 实 数,
使 得 对 任 意 维 向 量 都 有
,
则 称 这 两 个 范 数 是 的 。 对 两 个 等 价 范 数 而 言,
同 一 向 量 相 同等 价序 列 有 的 极 限 。
21 3,146,.xx x解,
12?－ 范 数,－ 范 数 和 － 范 数 是不 难 证 明,等 价 的 。
2 － 范－ 范 数 和 数 等 价 。
如 不 作 说 明,今 后 是 指 任 意 一 种 向 量 范 数 。
1m a x,ji inx x x设 则
1m a x iinxx例,
2 2 2
12 2n xx x x
n n
2
2
x
xx
n?
jxx
2 2 2
12 2,nx x x x
二、矩阵的范数
AA
n A,对 任 意 阶 方 阵,按 一 定 的 规 则 由 一实 数 与 之 对 应,记 为 。
义若定满 足
1,0,0 0 ;
2.,
3.,
4
(
)
)
)
(
(
A A A
A A
A B A B,A B n
AB A B
且 当 且 仅 当为 任 意 实 数对 任 意 两 个 阶 方正阵定三 角 不齐 次
（ 相等 式
,容 性 条 件 ）
AA为 矩 阵则 称 的 范 数 。
1
m a x
()
m a x
,1
x ma
n
x
ij
xx
A n R
Ax
A
x
Aa
Ax xx
A
x x x
Ax
A Ax
x
n x n
定 理,设 为 阶 方 阵,是 中 的 向 量 范 数,则是 一 种 矩 阵 范 数,
且 称 其 为 由 向 量 范 数 。
证,设 为 任 意 阶 方 阵,为 任 意 维 非 零 向 量 。
因 为 为 范 数 是 的 单 位 向 量,故诱 导 出 的 矩 阵 范 数
1
11
1
1 0,0,m a x 0.
0 0
0,
2 m a x m a x
m a x,
3,
x
xx
x
A A A A x
A A x A x
A
A A x A x
A x A
n A B
AB
，显然 若 则反之，若
，
对任意两个 阶方阵 和,
11
1 1 1
m a x ( ) m a x
m a x ( ) m a x m a x
,
xx
x x x
A B x A x B x
A x B x A x B x
AB
11
11
4
,
m a x ( ) m a x ( )
m a x m a x
5
xx
xx
nx
Ax
A Ax A x
x
AB AB x A Bx
A Bx A B x
AB
n x Ax A x
，对任意 维非零向量,
有 即故有
，对任意 维向量,都有 。
这一性质称为矩阵范数与向量范数的相容性。
可由三种常用的向量范数诱导出矩阵范数。
矩阵范数例
2
2 1121
,m a x
()
T
x
ij
A A x A A
Aa n
其 中 是 的 。最 大 特 征 值又 称 为 谱 范 数 。 设 为 阶 方 阵 。
与前述三种向量范数相容的三种矩阵范数：
1
11 11
1
,m a x x
1
ma
n
ij
x j n
i
A A x a
为最 大矩 阵 的列 向 量 的 的 称 矩 阵 的值 为－ 范 数 列 范 数 。
11
1
,m a x
1
m a x
n
ij
x i n
j
A A x a
行最 大为 矩 阵 的向 量 的 － 范 数 的 称 矩 阵 的为值 行 范 数 。
2
12
34
,
n
R
AA
如 果 将 矩 阵 范 数 看 作 空 间 上 的 向 量 范 数,
则 由 向 量 范 数 的 等 价 性 可 得 矩 阵 范 数 的 等 价 性 。
例,计 算 的 各 种 范 数 。
12 6,7,5,4 6,A A A解,
/
AA
A A A A A A
矩 阵 的 误 差 可 用 矩 阵 范 数 表 示,设 是 的 近似 矩 阵,分 别 称 为 的 关 于 范数 的 绝 对 误 差 与
、
相 对 误 差 。
矩阵 A的谱半径
1
( 1,2,,)
( ) m
,
ax
nn
i
i
in
A
A R i n
A
定 义,设 的 特 征 值 为 称为 的 谱 半 径 。
,( A ) AA A定 理,为 的 任 意 矩 阵 范 数,
(,
)
A
()
AxxxAxx
xAxAAA?
三,方程组的性态与矩阵条件数
矩阵的条件数
右端项 b的扰动对解的影响
系数矩阵 A的扰动对解的影响
条件数的 定义 和 性质
,病态”方程的经验判断
误差分析
1、矩阵的条件数一 个 实 际 问 题 化 为 数 学 问 题,初 始 数 据 往 往 会 有误 差,即 有 扰 动,从 而 使 计 算 结 果 产 生 误 差 。
1 2 1
1 2 1
1 2 2
1 2 2
22
.
1,0 0 0
21
.
1,0 0 0 0 1 2
0 1 2 0
,0 0 0 0
11
x x x
x x x
xx
x x x
x
例,方 程 组而 方 程 组
5
,1012
1
2
比 较 这 两 个 方 程 组 可 以 看 出,他 们 只 是 右 端 项 有 微 小 的差 别,最 大 相 对 误 差 为 但 它 们 的 解 却 大 不 相 同,解 分量 的 相 对 误 差 至 少 为 。
Ab
A x b
A
A
,如 果 矩 阵 或 常 数 项 的 变 化,引起 方 程 组 解 的 变 化,则 称 此 方 程 组 为
,矩 阵 称 为,病 态,矩 阵 （ 相对 于 方 程 组 而 言 ） 。
否 则 称 方 程 组 为,良 态,方 程 组,称 为
,良 态,矩 阵 。
矩 阵 的,病 态
,病
” 性微 小质 是态,
矩 阵方 程本 身定组大义巨的 特 性 。
为了定量刻画方程组的“病态”程度，下面对方程组 Ax＝ b就系数矩阵的扰动或右端项有扰动的两种情况进行讨论。
右端项 b的扰动对解的影响
1
11
11
,
)
(
Ax b A x b x A b
A b A A bx
b b x x
A x x b b
A
xA
bxb
xb
x
A
A
b A b
A
设 有 扰 动,相 应 解 的 扰 动 记 为 即由两 边 取 范 数又 因 为
，
1
,,
AA?
此 式 表 明 当 右 端 项 有 扰 动 时 解 的 相 对 误 差 不 超 过右 端 项 的 相 对 误 差 的 倍 。
系数矩阵 A的扰动对解的影响
1
1
1
1
1
1
1
,
,
( ) ( )
()
( ) 0
1
1
1
()
A
x
A A x x b A x A x
x
A
AA
AAxA
Ax A
x
A A A
A
AA
A
x A A x x A A x x
A
如 果 右 端 项 无 扰 动,系 数 矩 阵 有 扰 动,相 应 的 解的 扰 动 仍 记 为 则如 果 充 分 小,使 得 则 由 上 式 得
1
1
A
AA
A?
上 式 表 明,当 系 数 矩 阵 有 扰 动 时,解 的 扰 动 仍 与有 关 。 越 大,解 的 扰 动一 般 地,也 越 大 。
条件数的定义
-1,
,
AA综 上 分 析 可 知 量 实 际 上 刻 划 了 解 对 原 始 数 据 变化 的 灵 敏 程 度 即 刻 划 了 方 程 组 的,病 态,程 度 。
1( ) ( 1,
2
v vvA c o n d A A A v
A
,设 为 非 奇 异 阵,称 数定 义或 ） 为 矩 阵 的 条 件 数 。
-1
1 m a x
22
m in
2
1
2
1
( 1 )
()
( 2 ) A,(
()
(
(
)
),
)
T
T
n
n
AA
AA
AA
AA
A c o n
c o n d
c o n A
A
A
A
d
d
；
的 谱 条 件 数当 为 对 称 矩 阵 时,
其 中,为 的 绝 对 值 最 大 和 绝 对 值 最 小 的 特 征 值 。
常用的条件数，有条件数的性质
11
2
2
1,
2
3
( ) 1
( ) 1.
( ) ( )
( ) 1
(
0
)
v
v
v
vv
vv
c ond A
c ond A A A A A I
c ond c A c ond A
c ond A
c on
A
A
A
c
d RA c
AR
on
非 奇 异 矩 阵非 奇 异
＝
,对 任 何,都 有由 定 义
,设 为 （ 常 数 ）,则
,如 果 为 矩 阵,则矩 阵 且正 交非 奇 异 正 交；
如 果 为 矩 阵,为 矩 阵,则
22
.( ) ( )d AR c ond A?
3
11
1
2
11
1
2 3 1
1 1 1
1 2 1
n
n
H n
H ilb e
n
t
n
H
n
r
例,矩 阵计 算 的 条 件 数 。
1
3 3
9 36 30
36 192 180
30 180 1
11
1
23
1
80
11
234
11
,
1
3 4 5
HH
解,
nHn一 般 矩 阵 当 越 大 时,病 态 越 严 重 。
1
3
6
6
3
3
33
11
()
( ) 2,9
408
( 1 ) ( ),
.748
1 0,
6
c o n d H H H
H c o n d H
c o n d H
计 算 条 件 数同 样 可 计 算
11
22
33
1 1 11
1
2 3 6
1
1 1 1 13
2 1
2 3 4 12
1
47111
603 4 5
xx
xx
xx
（ ） 考 虑
11
22
33
33
3
1,0 0 0,5 0 0 0,3 3 3 1,8 3
0,5 0 0 0,3 3 3 0,2 5 0 1,0 8
0,3 3 3 0,2 5 0 0,2 0 0 0,7 8 3
( ) ( ),
( 1,0 8 9 5,0,4 8 8 0,1,4 9 1 )
T
Hb
xx
xx
xx
H H x x b b
xx
设 及 有 微 小 误 差 （ 取 位 有 效 数 字 ） 有简 记 为其 解 为
3 3
3
3
( 1,0 8 9 5,0,4 8 8 0,1,4 9 1 ),( 1,1,1 )
( 0,0 8 9 5,0,5 1 2 0,0,4 9 1 0 )
0,1 8 1 0 0,0 2 %
0,5 1 2 0
0,1 8 2 % 5 1,2 %
1
5 0
TT
T
x x x
x
H
H
bx
bx
Hb
由 于
，
这 表 明 与 相 对 误 差 不 超 过 0.2%,而 引 起解 的 相 对 误 差 超 过 ％,
“病态”方程的经验判断计 算 条 件 数 需 要 求 矩 阵 的 逆,因 而 比 较 困 难 。 根据 数 值 经 验,在 下 列 情 况 下,方 程 组 常 是,病 态,的 。
1（ ） 在 用 主 元 素 法 时 出 现 小 主 元 ；
2 A
A
（ ） 如 果 的 最 大 特 征 值 和 最 小 特 征 值 之 比 （ 按 绝 对 值 ）
是 大 的,则 是,病 态,的 。
3（ ） 系 数 矩 阵 中 有 行 （ 或 列 ） 近 似 线 性 相 关,或 系 数 行列 式 的 值 近 似 于 零 。
,
d e t ( ) 0,( ) ( ) 1,n
AI
A c o n d A c o n d I
但 这 不 是 绝 对 的,如 当 为 很 小 的 数 时,有但 方 程 组 状 态 良 好 。
4 A
A
（ ） 系 数 矩 阵 元 素 间 数 量 级 相 差 很 大,并 且 无 一 定 规 则可 能,病 态,。
1;
.
( ),)
,
,
(
A
P
P A Q y P b
y Q x
c
xb
P
o n d P A Q c
Q
o n d A
Q
用 选 主 元 素 的 消 去 法 不 能 解 决 病 态 问 题,对 病态 方 程 组 可 采 用 高 精 度 的 算 术 运 算 或 采 用 预 处 理方 法 。 即 将 求 解 转 化 为 一 等 价 方 程 组非 奇 异对选角择 使一 阵 或 者般 选 择矩 阵为 三 角 矩 阵 。
2、误差分析 *
**
*
A x b x
x r b A x
rx
r
在 求 得 方 程 组 的 一 个 近 似 解 后,检 验 精 度 的 一 个简 单 方 法 是 将 代 入 方 程 组 求 得 。
如 果 很 小,就 认 为 解 比 较 准 确 。 但 在,病 态,严 重 的方 程 组,也 有 即 使 残 差 量 很 小,近 似 解 与 准 确 解 的 差 仍很残 量 （ 余 量 ）
大 的 情 形 。
1 2 1
1 2 1
*
1
5
2
1,1
22
1,0 0 0 0 1 2 0
( 2,0 ) ( 1,1 ) ( 1,
( 2,2 ) ( 2,2,0 0 0 0 1 ) ( 0,1 0
)
1 )
T
T T T
TT
x x x
x x x
x
r
x
xx
上 例 中,方 程 组若 以 作 为 它 的 近 似 解,其 残 量很 小,但 解 的 误 差却 不 小 。
* 1 * 1
*
1
(
)
x
b A x A
x
x
x
x x A b A x A r A r
证,因 为所 以
1Ar
b
A
1 (),
rrA A c o n d A
bb
由 上 式 可 看 出,当 方 程 组,病 态,严 重 时,条 件 数 很大,即 使 残 量 很 小,解 的 相 对 误 差 仍 可 能 很 大 。
*
*
*
-
(,)
xx r
c o n d A
x
x x A x b
rx
b
,设 和 分 别 是 方 程 组 的 准 确 解 和 近 似 解,
为 的 残 量,则定 理
