線性代數 中,收斂矩陣 是在求冪過程中收斂到零矩陣 的矩陣。
背景
矩陣 T 的冪隨次數增加而變小時(即T 的所有項都趨近於0),T 收斂到零矩陣。可逆矩陣 A 的正則分裂 會產生收斂矩陣T 。A 的半收斂分裂會產生半收斂矩陣T 。將T 用於一般的迭代法 ,則對任意初向量都是收斂的;半收斂的T 則要初向量滿足特定條件才收斂。
定義
n 階方陣T 若滿足
∀
i
=
1
,
2
,
…
,
n
,
j
=
1
,
2
,
…
,
n
,
lim
k
→
∞
(
T
k
)
i
j
=
0
,
{\displaystyle \forall i=1,\ 2,\ \dots ,\ n,\ j=1,\ 2,\ \dots ,\ n,\ \lim _{k\to \infty }(\mathbf {T} ^{k})_{ij}=0,}
1
則稱T 是是收斂矩陣 。[ 1] [ 2] [ 3]
例子
令
T
=
(
1
4
1
2
0
1
4
)
.
{\displaystyle {\begin{aligned}&\mathbf {T} ={\begin{pmatrix}{\frac {1}{4}}&{\frac {1}{2}}\\[4pt]0&{\frac {1}{4}}\end{pmatrix}}.\end{aligned}}}
T 的冪是
T
2
=
(
1
16
1
4
0
1
16
)
,
T
3
=
(
1
64
3
32
0
1
64
)
,
T
4
=
(
1
256
1
32
0
1
256
)
,
T
5
=
(
1
1024
5
512
0
1
1024
)
,
{\displaystyle {\begin{aligned}&\mathbf {T} ^{2}={\begin{pmatrix}{\frac {1}{16}}&{\frac {1}{4}}\\[4pt]0&{\frac {1}{16}}\end{pmatrix}},\quad \mathbf {T} ^{3}={\begin{pmatrix}{\frac {1}{64}}&{\frac {3}{32}}\\[4pt]0&{\frac {1}{64}}\end{pmatrix}},\quad \mathbf {T} ^{4}={\begin{pmatrix}{\frac {1}{256}}&{\frac {1}{32}}\\[4pt]0&{\frac {1}{256}}\end{pmatrix}},\quad \mathbf {T} ^{5}={\begin{pmatrix}{\frac {1}{1024}}&{\frac {5}{512}}\\[4pt]0&{\frac {1}{1024}}\end{pmatrix}},\end{aligned}}}
T
6
=
(
1
4096
3
1024
0
1
4096
)
,
{\displaystyle {\begin{aligned}\mathbf {T} ^{6}={\begin{pmatrix}{\frac {1}{4096}}&{\frac {3}{1024}}\\[4pt]0&{\frac {1}{4096}}\end{pmatrix}},\end{aligned}}}
綜之,
T
k
=
(
(
1
4
)
k
k
2
2
k
−
1
0
(
1
4
)
k
)
.
{\displaystyle {\begin{aligned}\mathbf {T} ^{k}={\begin{pmatrix}({\frac {1}{4}})^{k}&{\frac {k}{2^{2k-1}}}\\[4pt]0&({\frac {1}{4}})^{k}\end{pmatrix}}.\end{aligned}}}
由於
lim
k
→
∞
(
1
4
)
k
=
0
{\displaystyle \lim _{k\to \infty }\left({\frac {1}{4}}\right)^{k}=0}
lim
k
→
∞
k
2
2
k
−
1
=
0
,
{\displaystyle \lim _{k\to \infty }{\frac {k}{2^{2k-1}}}=0,}
T 是收斂矩陣。注意其譜半徑
ρ
(
T
)
=
1
4
{\displaystyle \rho (\mathbf {T} )={\frac {1}{4}}}
,因為
1
4
{\displaystyle {\frac {1}{4}}}
是T 唯一的特徵值 。
特徵
設T 是n 階方陣,則下列表述等價於T 的收斂矩陣:
對某自然範數,
lim
k
→
∞
‖
T
k
‖
=
0
{\displaystyle \lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0}
對所有自然範數,
lim
k
→
∞
‖
T
k
‖
=
0
{\displaystyle \lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0}
ρ
(
T
)
<
1
{\displaystyle \rho (\mathbf {T} )<1}
∀
x
,
lim
k
→
∞
T
k
x
=
0
{\displaystyle \forall \mathbb {x} ,\ \lim _{k\to \infty }\mathbf {T} ^{k}\mathbf {x} =\mathbf {0} }
[ 4] [ 5] [ 6] [ 7]
迭代法
一般的迭代法 包含將線性方程組
A
x
=
b
{\displaystyle \mathbf {Ax} =\mathbf {b} }
2
轉為等價方程組
x
=
T
x
+
c
{\displaystyle \mathbf {x} =\mathbf {Tx} +\mathbf {c} }
3
的過程。選定初向量
x
(
0
)
{\displaystyle \mathbf {x} ^{(0)}}
,近似解向量序列的生成由
∀
k
≥
0
,
x
(
k
+
1
)
=
T
x
(
k
)
+
c
{\displaystyle \forall k\geq 0,\ \mathbf {x} ^{(k+1)}=\mathbf {Tx} ^{(k)}+\mathbf {c} }
4
[ 8] [ 9]
對任意初向量
x
(
0
)
∈
R
n
{\displaystyle \mathbf {x} ^{(0)}\in \mathbb {R} ^{n}}
,序列
{
x
(
k
)
}
k
=
0
∞
{\displaystyle \lbrace \mathbf {x} ^{\left(k\right)}\rbrace _{k=0}^{\infty }}
由(4 )定義,
∀
k
≥
0
,
c
≠
0
{\displaystyle \forall k\geq 0,\ \mathbf {c} \neq 0}
,若且唯若
ρ
(
T
)
<
1
{\displaystyle \rho (\mathbf {T} )<1}
收斂於(3 )的唯一解,即T 是收斂矩陣。[ 10] [ 11]
正則分裂
矩陣分裂 是用多個矩陣的和或差表示矩陣。對(2 )所示的線性方程組,若A 可逆,則A 就可分裂為
A
=
B
−
C
{\displaystyle \mathbf {A} =\mathbf {B} -\mathbf {C} }
5
於是(2 )可重寫為(4 )。若且唯若
B
−
1
≥
0
,
C
≥
0
{\displaystyle \mathbf {B} ^{-1}\geq \mathbf {0} ,\ \mathbf {C} \geq \mathbf {0} }
時,(5 )式是A的正則分裂 ;即
B
−
1
,
C
{\displaystyle \mathbf {B} ^{-1},\ \mathbf {C} }
只有非負元素。若分裂(5 )是A 的正則分裂、且
A
−
1
≥
0
{\displaystyle \mathbf {A} ^{-1}\geq \mathbf {0} }
,則
ρ
(
T
)
<
1
{\displaystyle \rho (\mathbf {T} )<1}
,T 是收斂矩陣,迭代法(4 )收斂。[ 12] [ 13]
半收斂矩陣
n 階方陣T ,若極限
lim
k
→
∞
T
k
{\displaystyle \lim _{k\to \infty }\mathbf {T} ^{k}}
6
存在,則稱之為半收斂矩陣 。[ 14] 若A 可能奇異,而(2 )齊次,即b 在A 的範圍內,則若且唯若T 是半收斂矩陣時,對任何初向量
x
(
0
)
∈
R
n
{\displaystyle \mathbf {x} ^{(0)}\in \mathbb {R} ^{n}}
,(4 )定義的序列收斂到(2 )的解。這時,分裂(5 )稱作A 的半收斂分裂 。[ 15]
另見
註釋
^ Burden & Faires (1993 , p. 404)
^ Isaacson & Keller (1994 , p. 14)
^ Varga (1962 , p. 13)
^ Burden & Faires (1993 , p. 404)
^ Isaacson & Keller (1994 , pp. 14,63)
^ Varga (1960 , p. 122)
^ Varga (1962 , p. 13)
^ Burden & Faires (1993 , p. 406)
^ Varga (1962 , p. 61)
^ Burden & Faires (1993 , p. 412)
^ Isaacson & Keller (1994 , pp. 62–63)
^ Varga (1960 , pp. 122–123)
^ Varga (1962 , p. 89)
^ Meyer & Plemmons (1977 , p. 699)
^ Meyer & Plemmons (1977 , p. 700)
參考文獻
Burden, Richard L.; Faires, J. Douglas, Numerical Analysis 5th, Boston: Prindle, Weber and Schmidt , 1993, ISBN 0-534-93219-3 .
Isaacson, Eugene; Keller, Herbert Bishop, Analysis of Numerical Methods, New York: Dover , 1994, ISBN 0-486-68029-0 .
Carl D. Meyer, Jr.; R. J. Plemmons. Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems. SIAM Journal on Numerical Analysis . Sep 1977, 14 (4): 699–705. doi:10.1137/0714047 .
Varga, Richard S. Factorization and Normalized Iterative Methods. Langer, Rudolph E. (編). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press . 1960: 121–142. LCCN 60-60003 .
Varga, Richard S., Matrix Iterative Analysis, New Jersey: Prentice–Hall , 1962, LCCN 62-21277 .