2 數學傳播十九卷二期民 84 年 6 月 x 1 = [A 1,,A n ] x n = x 1 A x n A n = b (5) x 1 註 (A): 如果我們將向量視為矩 x n 陣的話, 則 (5) 式同時也告訴我們, 矩陣乘在右手邊其運算為行運算 ( 同理乘在左手邊則為

Size: px

Start display at page:

Download "2 數學傳播十九卷二期民 84 年 6 月 x 1 = [A 1,,A n ] x n = x 1 A x n A n = b (5) x 1 註 (A): 如果我們將向量視為矩 x n 陣的話, 則 (5) 式同時也告訴我們, 矩陣乘在右手邊其運算為行運算 ( 同理乘在左手邊則為"

淋浒时
5 years ago
Views:

1 線性代數的基本定理林琦焜前言 : 最近在 American Mathematical Monthly 閱讀到 Gilbert Strang 探討線性代數之文章, 讀後收穫良多, 尤其幾個圖形實在有教學上之價值在感動之餘想想何不動手, 以 Gilbert Strang 之文章為藍本, 同時把自己讀書與教學之心得將之整理後, 以與中文之讀者一起分享此文主要探討的是 Fredholm Altenative 定理, 要提醒的是雖然我們僅在有限的空間上討論, 但實際上都可推廣至無限維空間, 而這就是泛函分析 (functional analysis) 所研究的主題之一矩陣的本質 : 要瞭解線性代數, 最直接且最有動機莫若於從求聯立方程組的解開始其中 A x = b A : R n R m (1) x = (x1, x 2 x n ) T R n b = (b1, b 2 b m ) T R m 在此向量都是以行向量來表示其中 A 是一個 m n 矩陣 A = a 11 a 1n a 21 a 2n a m1 a mn a ij R, 1 i m, 1 j n (2) 首先我們將矩陣 A 視為向量 ( 實際上矩陣是向量的推廣 ) A = [A 1,,A n ] (3) a 1j A j = a 2j 1 j n (4) a mj 有了上述之結果, 我們可將 (1) 式的左邊表為向量的線性組合 : A x = a 11 a 1n x 1 a 21 a 2n a m1 a mn x n 1

2 2 數學傳播十九卷二期民 84 年 6 月 x 1 = [A 1,,A n ] x n = x 1 A x n A n = b (5) x 1 註 (A): 如果我們將向量視為矩 x n 陣的話, 則 (5) 式同時也告訴我們, 矩陣乘在右手邊其運算為行運算 ( 同理乘在左手邊則為列運算 ) 而其法則為 x 1 ( 第一行 ) + x 2 ( 第二行 ) + +x n ( 第 n 行 ) (6) 註 (B): 由 (5) 式我們也可略窺行空間 (column space) 的雛形, 由此角度而言, 求 A x = b 的解, 相當於求所有 A 1 A n 的線性組合正好等於 b, 即求 (x 1 x n ) R n 使得 x 1 A x n A n = b 註 (C): (5) 式可幫助我們明白矩陣的結合律, 一般在線性代數的課本是將矩陣視為線性變換 (linear transformation), 因此矩陣的結合律可視為是函數之合成的結合律, 但這種作法, 對學生而言, 幫助並不大在這裡我們希望藉由 (5) 及一些簡單的基本運算來証明矩陣的結合律 A(BC) = (AB)C 由 (5) 式知向量 A x 為矩陣 A 之行向量的線性組合, 利用這個概念, 我們可以對矩陣的乘法有另一個角度的體會, 給定任一矩陣 B = [B 1, B 2, B k ] B i 為矩陣 B 之第 i 行向量, 因此矩陣 A 與矩陣 B 之相乘可表為 AB = A[B 1, B 2, B k ] = [AB 1, AB 2,, AB k ] 即矩陣 AB 的第 i 行向量 (AB) i 為矩陣 A 乘矩陣 B 的第 i 行向量 AB i 由 (5) 式知 AB i 要有意義其先決條件為 B i 為一 n 維行向量, 即矩陣 B 為一 n k 矩陣 B = [B 1, B 2,, B k ] b 11 b 1k = b n1 b nk 同理, 矩陣 BC 要有意義為 C 為一 k l 矩陣 c 11 C = [C 1,, C l ] = c k1 b 1l c kl 我們現在考慮矩陣之結合律, 由 (5) 式知 A(BC i ) = A(c 1i B c ki B k ) = c 1i AB c ki AB k = [AB 1,, AB k ] = [AB 1,, AB k ]C i 再次利用 (5) 式可得矩陣之結合律 A(BC) = A(B[C 1,, C l ]) c 1i c ki

3 線性代數的基本定理 3 = A[BC 1,, BC l ] = [A(BC 1 ),, A(BC l )] = [(AB)C 1,, (AB)C l ] = (AB)[C 1,, C l ] = (AB)C 註 (D): (5) 式告訴我們的還不僅如此在中學階段就熟知 Cramer 公式, 亦可由此式再加點行列式的性質而得, 當然還是從解聯立方程組開始 A x = b 此時 A 為一 n n 矩陣向量, x, b 則視為 n 1 矩陣, 為著簡便用符號 [A i b ] 表示一 n n 矩陣, 其中矩陣 A = [A 1 A n ] 之第 i 行向量為向量 b 所取代, 即 [A i b ] = [A 1 A i 1, b, A i+1,, A n ] 但由 (5) 式並利用行運算基本上是矩陣乘在右手邊之原則得 [A 1 A i 1, A x, A i+1, A n ] = [A 1, A i 1, x 1 A x n A n, A i+1, A n ] = [A 1, A i 1, A i, A i+1 A n ] 1 0 x x x n 0 1 = A[I i x ] 因此聯立方程 A x = b 可改寫為 A[I i x ] = [A i b ] 兩邊同時取行列式得 (det A)(det[I i x ]) = det[a i b ] 由 Laplace 展開式或行列式的性質知 det[i i x ] = x i, 故 x i = det[a i b ] det A 這就是 Cramer 公式基本定理 : 習慣上, 我們將行空間 (column space) 記為 R(A), 明顯地 R(A) R m 談了行向量, 行空間自然要提它的孿生兄弟列向量 (row vecter), 列空間 (row space), 記為 R(A T ), 另要提的子空間如下 N(A) { x R n A x = 0} R n (7) N(A T ) { y R n A T y = 0} R m (8) 底下我們將注意力都集中在這四個子空間, 當然讀者可能會問為何要探討這些子空間, 實際上所有線性代數上的運算與應用皆可經由子空間的瞭解而來, 例如在中學階段所學利用加減消去法, 代入消去法來求聯立方程組的解, 就是無形中已使用到子空間的某些特性, 其中最重要的一個就是維數 (dimension) 的不變性維數在線性代數中扮演著極重要的角色定理 1: (i) dim R(A) = dim R(A T ) (ii) dim R(A) + dim N(A) = n

4 4 數學傳播十九卷二期民 84 年 6 月 (i) 式告訴我們行空間 (colum space) 與列空間 (row space) 的維數是一樣的, 如此的描敘還是抽象了一些, 最好的方式還是以例子來明瞭定理的意義其實學數學最好的方法即是從例子著手例 1: 經過化簡得 A = A }{{} 3 因此 dim R(A) = dim R(A T ) = 3 dim N(A) = 5 3 = 2 dim N(A T ) = 4 3 = 1 對於一般 m n 矩陣, 經過行運算 ( 或列運算 ) 後可容易判別上述的關係式例 2: A = [A 1 A n ] [B 1 B r, 0 0], {B 1 B r } 是線性獨立, 因此 dim R(A) = r, 由定理 1 知 dim N(A) = n r 線性代數另一個基本定理如下定理 2: N(A) R(A T ) 這定理告訴我們子空間的正交性 (orthogonality), 其意義與證明也可從聯立方程組的解來視出端倪 B 1 A x = x B m B 1 x = B m x = 0 取各分量得 B 1 x = = B n x = 0 0 x 與所有列向量 B i, (1 i m) 垂直因此 x ni=1 b i B i 即 x R(A T ), 所以 N(A) R(A T ) x B i (1 i m) x N(A) 同理, 取轉置 (transpose) 矩陣我們有定理 2 : N(A T ) R(A) 茲以一個圖形來說明上面二個定理

5 線性代數的基本定理 5 dim R(A T )=r 列空間 R n dim N(A) = n r R(A T ) x r O x n N(A) x = x r + x n A x r = b A x n = 0 A x = 0 N(A T ) R(A) b R m dim R(A) = r dim N(A T ) = m r 行空間這圖形說明了幾件事實 : (a) R n 上的向量 x 可分解為兩個互相垂直的向量 x = x r + x n, x r R(A T ), x n N(A) 或 R n = R(A T ) N(A) 實際上此分解是唯一的 (9) (b) A 將 R n 上的任一向量 x 帶到行空間 R(A), 而將核空間 (null space) 皆帶到 0 向量 (c) 若 b 落在行空間 R(A), 則聯立方程組 A x = b 是可解的換言之, 若 b 與所有 N(A T ) 的向量垂直 ( b N(A T )), 則聯立方程組 A x = b 是可解的而其解 x 可分解為二部份 x A x = x p + x h = A( x p + x h ) = A x p + A x h = b + 0 = b x p 為 (1) 式之特解 (particular solution) x h 為 (1) 式之均勻解 (homogeneous solution) 而 x p + x h 為一般解 (general solution), x p 稱為特解是因為 x p x h, x h N(A) (10) 另外順便一提的是所有均勻解所成的空間正好是核空間 (null space) N(A) = { x h R n A x h = 0} 註 : 上面 (c) 所談的在無窮維空間亦有相類似的結果, 其實這就是泛函分析 (functional analysis) 或積分方程 (integral equation ) 裡著名的 Fredholm Alternative 定理註 : 若將 A 視為一微分算子 (differential operator), 則 (c) 所言在微分方程也有相對應的結果讀者若有興趣可自行驗證事實上, 我們所提

6 6 數學傳播十九卷二期民 84 年 6 月的線性代數的基本定理是可直接推廣至無窮維空間如果值域為一維, 即 m = 1 A : R n R (11) 則 A 為一有界線性泛函 (bounded linear functional) 由 Riesz 表現定理告訴我們, A 可表為一內積之形式 Riesz 表現定理 : A 為一有界線性泛函從 R n 映到 R A : R n R 有界, 線性則存在唯一 y R n 使得 A( x ) = ( x, y ) x R n (12) 利用上述之結果, 再加上一點正交投影之概念可容易地證明且明白 Riesz 表現定理的幾何意義 : 定理證明 : ( 不失一般性可設 A 0 ) x R n 可表為 x = x r + x n, x r R(A T ), x n N(A) 而現在因為 A 為一線性泛函, m = 1 且 A 0, 因此由定理 1 知 dim R(A T ) = dim R(A) = 1 令 z R(A T ), z 0, 則 R(A T ) =< z >= {α z α R} 由正交投影知 P(x) = < x, z > z z 2 所以 A( x ) = A( x r ) = A(P( ( x ))) < x, z > = A z z 2 = < x, z > A( z ) z 2 = < x, A( z ) z 2 z > 令 y A( z ) z 2 z 即為所求註 1: 這個證明方法並沒有維數的限制, 對一般的內積空間 (inner produt space) 皆可 A( x ) = A( x r + x n ) = A( x r ) + A( 註 2: 因為用到投影的概念, x n ) = A( 因此在無形中, 我們已經將最短距 x r ) 離或變分學的概念注入這定理中而上式告訴我們 A 的值完全由在事實上這定理本身已具有變分原 R(A T ) 上的值所決定令 P 為一 R n 理 (variational principle) 的內涵在在 R(A T ) 上之正交投影, 則我們有偏微分方程 (PDE) 這定理是弱解 P( x ) = P( x r + x n ) = x r (weak solution) 存在的最好證明工具呢! 因此 A( x ) = A( x r ) = A(P( x )) 所以, 如果我們能決定 P( x ) 之長像, 則 A( x ) 之形像也跟著決定最小二乘方 :

7 線性代數的基本定理 7 關於 Fredholm Alternative 定理的另一個重要應用便是最小二乘方 (leastsquare) 由前面之理論知, 若 b 不屬於行空間 (column space) 則聯立方程組 ( 矩陣 A 並沒有限制一定是方陣 ) A x = b 無法求得其解但在現實情形與應用, 期待一個非奇異方陣是不實際的因此我們需要有某些方法以面對殘酷的現實我們的問題如下 : 試求一直線 : b = C + Dt 或一拋物線 b = C + Dt + Et 2 通過 (t 1, b 1 ) (t m, b m ) 這些點? 首先我們將問題表為聯立方程組, 即 C + Dt 1 = b 1 C + Dt m = b m C + Dt 1 + Et 2 1 = b 1 (13) 或 C + Dt m + Et 2 m = b m 乍見之下該聯立方程組為二個未知數 (C, D) ( 或 3 個未知數 (C, D, E) ) 卻要滿足 m 個方程式, 這顯然是要求過多上面之聯立方程組可表為 A x = b x = (C, D) t 或 x = (C, D, E) t (14) 而 A 則為一 m 2 或 m 3 矩陣, 因此 A x = b 要有解, 唯一可能的是這些點都落在同一直線上 ( 或拋物線上 ), 即 b 是落在矩陣 A 之行空間上這種向量 b 是限制過大, 所以我們問問題的方式需略作改變, 即求向量 x 使得 A x b 之長度為最短 (15) 或者是求向量 x 使得 η = (A x b ) (A x b ) = A x b 2 之值為最小 (16) 由於 A x 始終是行向量, 因此上面之問題相當於是求向量 b 至行空間之最短距離? (17) 而眾所周知, 求最短距離當然是與投影 (projection) 有關聯若 p 為向量 b 在行空間上之投影, 則向量 e = b p 為所求, 而且 e 與行空間垂直, 即 e Ker(A T ) A T e = A T ( b p ) = 0 (18) 令 p = Ax (19) 因此 (18) 等於告訴我們 A T Ax = A T b (20) (20) 式就是通常所說的正則方程式 (normal equation), 上面之結果可以圖來表示

8 8 數學傳播十九卷二期民 84 年 6 月列空間 (row space) x Ax = p p 行空間 (column space) 0 A x = b b = p + e R N q R N e 核空間 (null space) R q 正則方程式亦可由微分而來 ( 最短距離當然是與微分有關 ) η( x ) = η(x 1 x N ) (21) = (A x b ) (A x b ) = (A T A x 2A T b ) x + b b η 則 = 0 i = 1, N x i 得 A T A x = A T b 為了方便, 令 Ã = A T A b = A T b (22) 因此正則方程式可改寫為 Ãx = b (23) 該方程式有利之處在不管原矩陣 A 是否為方陣, Ã = A T A 一定是個對稱方陣, 故前面的 Fredholm- Alternative 定理現在就可派上用場, 即 (23) 要有解其充分必要條件為 b N( Ã T ) 不失一般性可設 { dim N( Ã) = dim N(ÃT ) = q dim R(Â) = N q (24) 因為 Ã 為對稱矩陣, 故存在正交矩陣 P, P P T = I, 使得 ( ) 0 0 P T ÃP = (25) 0 D = P T A T (AP) = (AP) T (AP) D 為一 (N q) (N q) 對角矩陣, 即 D = λ q λ N (26) 且 detd 0, 我們現在決定矩陣 P 可設 P = [ ϕ 1, ϕ q, ξ q+1,, ξ N ] (27)

9 ϕ i, 1 i q ξ j, q + 1 j N 為行向量, 其中 ( 可由 (24) 式看出來 ) 因此再一次由 (24) 可知 (AP) i (AP) j = (AP) T i (AP) j = 0 i j i = j q (AP) j (AP) j = (AP) T j (AP) j = λ j j > q (29) 而且 [ Ker(A T ) ] = [A ξ q+1,, A ξ N ] 現在定義 = [(AP) q+1,, (AP) N ] (30) z = P T x = (z1 z N ) T (31) 故由正則方程式 (28),(29) 知 ( ) 0 0 z (32) 0 D = P T ÃP z = P T A T APP T x = P T (A T A x ) = P T A T b = (AP) T b = (0,, 0, Aξ q+1,, Aξ N ) T b 線性代數的基本定理 9 = (0,, 0, (Aξ q+1 ) T b,, (AξN ) T b ) span{ ϕ 1 比較各座標知 ϕ q } = Ker(A) λ i z i = A ξ i b q + 1 i N 從 (24) 可得 z 1 z q 則為任意數 (33) AP =[(AP) 1,, (AP) q, (AP) q+1,, (AP) N ] =[A ϕ 1 A ϕ q, A ξ q+1,, A 故待求之 x 可表為 ξ N ] =[0, 0, A ξ q+1,, A q N ξ N ] (28) x = z i (A ξ ϕ i + i b ) ξ λ i (34) i i=1 直接檢驗可得 i=q+1 A T Ax = A T b 如果取 b R = q b ( b ϕ i ) ϕ i (35) j=1 則可得引理 : Ax = b R 下 : 綜合上面之討論, 我們整理如方程式 A x = b 有解之充分必要條件為定理 : (Fredholm Alternative) 方程組 A x = b 有解之充分必要條件為 b Ker(A T ), 而且其解可表為 q x = z i ϕ i + i=1 N i=q+1 (A ξ i b ) ξ λ i i b = 其中 z 1 z q 為任意常數如果 b R, 則存在唯一 w Ker(A T ) 使得 A w = b R 參考資料

10 10 數學傳播十九卷二期民 84 年 6 月 1 Gilbert Strang, The Fundamental Theorm of Linear Algebra American, Mathematical Monthly, 100 (1993), Gilbert Strang, Linear Algebra and Its Applications, 3rd ed, Harcourt Brace Jovanovich (1988) 3 Gilbert Strang, Introduction to Linear Algebra, Wellesley - Cambridge Press (1993) 本文作者任教於成功大學數學系

1-2 二元一次聯立方程式 21 例 1 代入法判斷二元一次聯立方程式的 { x3y5 2xy3 x1y2 x3y3 x2y1 xy 二元一次式 x y x+3y x-y x2y1 x2y1 { x3y5 2xy3 { 2x3y1 xy3 x2y1

1-2 二元一次聯立方程式 21 例 1 代入法判斷二元一次聯立方程式的 { x3y5 2xy3 x1y2 x3y3 x2y1 xy 二元一次式 x y x+3y x-y x2y1 x2y1 { x3y5 2xy3 { 2x3y1 xy3 x2y1 1 20 1-2 二元一次聯立方程式 1 二元一次聯立方程式 2 代入消去法 3 加減消去法主題 1 二元一次聯立方程式列二元一次聯立方程式 6 x y 3 1 700 3xy700 5 2 1200 5x2y1200 { 3xy700 5x2y1200 二元一次聯立方程式二元一次方程組二元一次聯立方程式的 3xy700 5x2y1200 xy x y 共同 x200y100 3xy700

2 數學傳播十九卷二期民 84 年 6 月 x 1 = [A 1,,A n ] x n = x 1 A x n A n = b (5) x 1 註 (A): 如果我們將向量 視為矩 x n 陣的話, 則 (5) 式同時也告訴我們, 矩陣乘在 右手邊其運算為行運算 ( 同理乘在左手邊則 為

2 數學傳播十九卷二期民 84 年 6 月 x 1 = [A 1,,A n ] x n = x 1 A x n A n = b (5) x 1 註 (A): 如果我們將向量視為矩 x n 陣的話, 則 (5) 式同時也告訴我們, 矩陣乘在右手邊其運算為行運算 ( 同理乘在左手邊則為