web.mit.edu/18.06
繪制矩陣:blog.csdn.net/weixin_34130269/article/details/88010192
一.矩陣與方程組
1.方程組的幾何解釋
(1)行圖像(Row picture):1個行圖像展示1個方程
2x-y=0 ⇒ x = 1
-x+2y=3 y = 2
(2)列圖像(Column picture):方程組對∀b是否有解,等價于列的所有線性組合是否能覆寫整個Rn(在未知數個數=方程數時,n等于二者)
- 如果某些列是其他列的線性組合,并非始終有解,列的所有線性組合隻能覆寫Rless_than_n
x [2,-1] + y [-1,2] = [0,3] ⇒ x = 1,y = 2
(3)矩陣形式(Matrix form)
- Ax就是A的各列的線性組合
[[2 -1],[-1 2]] [x,y] = [0,3]
A x = b
2.高斯-約爾當消元法(Gauss-Jordan Elimination)解方程組:計算機求解方程組的方法
1.選擇主元
2.消元--成功/失敗-->行階梯型((Row-echelon Form)
3.回代(Back-Substitution)
4.消元-->行最簡型
#成功:
[[1 2 1],[3 8 1],[0 4 1]] ~ [[1 2 1],[0 2 -2],[0 4 1]] ~ [[1 2 1],[0 2 -2],[0 0 5]]
A U
#失敗:
#行交換可以解決主元的暫時失效
[[1 2 1],[3 6 1],[0 4 1]] ~ [[1 2 1],[0 0 -2],[0 4 1]] ~ [[1 2 1],[0 4 1],[0 0 -2]]
#永久失效
[[1 2 1],[3 8 1],[0 4 -4]] ~ [[1 2 1],[0 2 -2],[0 4 -4]] ~ [[1 2 1],[0 2 -2],[0 0 0]]
#回代:
[[1 2 1],[0 2 -2],[0 0 5]] = [2,12,2]
U b
#增廣(Augmented)矩陣:[A b] (系數矩陣右側加上結果列向量)
[[1 2 1 2],[3 8 1 12],[0 4 1 2]] ~ [[1 2 1 2],[0 2 -2 6],[0 0 5 -10]]
#即:
x + 2y + z = 2 x = 2
2y - 2z = 6 ⇒ y = 1
5z = -10 z = -2
#轉換為行最簡型
[[1 2 1],[0 2 -2],[0 0 5]] ~ [[1 0 3],[0 2 -5],[0 0 5]] ~ [[1 0 3],[0 2 0],[0 0 5]] ~ [[1 0 3],[0 1 0],[0 0 1]] ~ [[1 0 0],[0 1 0],[0 0 1]]
3.消元矩陣(E)
[[1 0 0],[-3 1 0],[0 0 1]] * [[1 2 1],[3 8 1],[0 4 1]] = [[1 2 1],[0 2 -2],[0 4 1]]
E21 A
[[1 0 0],[0 1 0],[0 -2 1]] * [[1 2 1],[0 2 -2],[0 4 1]] = [[1 2 1],[0 2 -2],[0 0 5]]
E32 U
[[1 0 0],[0 1 0],[0 -2 1]] * [[1 0 0],[-3 1 0],[0 0 1]] * [[1 2 1],[3 8 1],[0 4 1]] = [[1 2 1],[0 2 -2],[0 0 5]]
E32 E12 A U
E~32 * E~21 * A = U
E * A =U (E = E~32 * E~21)
#如果E21,E32均可逆
#穿脫原則:先進行的變換在逆變換中後進行
#機關矩陣(I/E):對角線上為1,其餘均為0
A = E21^(-1) * E32^(-1) * U
A= E^(-1) * U
二.矩陣(Matrix)
1.矩陣的運算
(1)線性運算:
#加/減法:
A~mn ± B~mn = C~mn
c~ij = a~ij ± b~ij
#數乘:用标量(Scalar)乘矩陣
B~mn = k * A~mn
b~mn = k * a~mn
- 線性運算的8條規則:任何滿足這8條規則的存在都可被視為向量
u,v,w為向量;a,b為數
1.u + (v + w) = (u + v) + w (加法結合律)
2.v + w = w + v (加法交換律)
3.There is a vector 0 such that 0 + v = v for all v
4.For every v there is a -v so that -v + v = 0
5.a * (b * v) = (a * b) * v (乘法結合律)
6.1 * v = v
7.a * (v + w) = a * v + a * w (乘法配置設定律)
8.(a + b) * v = a* v + b * v (乘法配置設定律)
(2)矩陣乘法:用矩陣/向量(Vector)乘矩陣
#正常方法((對應)行 * (對應)列):
[[...]...[c~m1...c~mp]...[...]] * [[...b~1n...]...[...b~pn...]] = [[...]...[...c~mn...]...[...]]
A~kp B~pq C~kq
c~mn= row m of A * column n of B = ∑(c~mi * b~in) (i = 1,2...p)
#列方法:
#C的任何1列都是A中各列的某個線性組合
column i of C = ∑(A * column i of B) (i = 1,2...p)
#行方法:
#C的任何1行都是B中各行的某個線性組合
row i of C = ∑(row i of A * B) (i = 1,2...p)
#(對應)列 * (對應)行:
C = ∑(column i of A * row i of B) (i = 1,2...p)
#分塊:
[[A11...A1q]...[Ap1...Apq]] * [[B11...Bt]...[Bq1...Bqt]] = [[C11...C1t]...[Cp1...Cpt]]
A分為p * q塊 B分為q * t塊 C分為p * t塊
Cij = block_row i of A * block_column j of B = ∑(Aip * Bpj) (p = 1,2...q)
A~mn·B~np=C~mp:結果矩陣的行數等于左側矩陣的行數,列數等于右側矩陣的列數;左側矩陣的列數需等于右側矩陣的行數才可乘
A~1n·B~np=C~1p:行向量*矩陣=行向量;矩陣各行的線性組合
A~mn·B~n1=C~m1:列向量*矩陣=列向量;矩陣各列的線性組合
(3)逆(Inverse)矩陣/非奇異(Non-singular)矩陣(相當于除法;A^(-1)):
- 要求A是方陣
#如果A可逆:
A~n^(-1) * A~n = A~n * A~n^(-1) = I~n
左可逆 右可逆
[[1 0 0],[0 1 0],[0 0 1]] = [[1 0 0],[3 1 0],[0 0 1]] * [[1 0 0],[-3 1 0],[0 0 1]] = [[1 0 0],[-3 1 0],[0 0 1]] * [[1 0 0],[3 1 0],[0 0 1]]
I A^(-1) A
#如A,B均可逆:
(A * B)^(-1) = B^(-1) * A^(-1)
A * B * (B^(-1) * A^(-1)) = A * B * B^(-1) * A^(-1) = A * A^(-1) = I
(A^T)^(-1) = (A^(-1))^T
A^T * (A^(-1))^T = (A^(-1) * A)^T = I^T =I
#利用高斯-約爾當消元法求A^(-1):
[A E] ~ [E A^(-1)]
A^(-1) * [A E] = [A^(-1) * A A^(-1) * E] = [E A^(-1)]
- A可逆的等價說法:
·A(左/右)可逆
·A非奇異(Non-Singular)
·det A ≠ 0
·A中各行/列線性無關
·Ax = 0的解隻有零向量
假設A可逆,且Ax=0的解包括非零向量
Ax = 0
A^(-1)Ax = 0
x = 0
與假設沖突
·A行等價于I
·det A ≠ 0
·A滿秩
·A^(-1)或A^T或A^k或A*可逆
·A~n的行/列階梯型有n個非0行/列
·A的行/列最簡型為I
·A的标準型為I
·A可表示為有限個初等矩陣的積
2.矩陣的LU分解
- 上三角(Upper Triangular)矩陣(U):隻有對角線上即其上方有非0元素
- 下三角(Lower Triangular)矩陣(L):隻有對角線上即其下方有非0元素
- 對角(Diagonal)矩陣(D):對角線上為非0元素,取餘均為0
#如果A在消元時不需要互換行
E * A = U ⇒ A = L * U = L * D * U'
[[1 0],[-4 1]] * [[2 1],[8 7]] = [[2 1],[0 3]] ⇒ [[2 1],[8 7]] = [[1 0],[4 1]] * [[2 1],[0 3]] = [[1 0],[4 1]] * [[2 0],[0 3]] * [[1 1/2],[0 1]]
E21 A U L D L'
#如果A在消元時需要互換行
P * A = L * U
#如果消元過程中沒有換行,消元乘數(即E中元素)可以直接取絕對值,然後寫到L相應位置
E = [[1 0],[-4 1]],L = [[1 0],[4 1]]
#消元次數(步驟數Cost):
#記1次乘+1次加為1個步驟(對1行的1次消元使步驟數+n(等于列數))
#對A~n ⇒ U~n
C = ∑(i * (i - 1)) (i = 2...n) ≈ Σ(i^2) ≈ ∫(0,n)(i^2)di = (n^3)/3 ∝ n^3
#對b~n1 ⇒ b'~n1 (跟随A進行消元)
C = Σ(i) (i = 1...n-1) = n * (n - 1) / 2 ≈ (n^2) / 2 ∝ n^2
3.轉置(Transposed)矩陣(A^T):
a~ij = (a^T)~ji
A* A^T在A的各行線性無關時可逆,此時(A * A^T)^T = A * A^T
A^T * A * x = 0 ⇒ x^T * A^T *A * x = 0 ⇒
(A * x)^T * (A * x) = 0 ⇒
A * x = 0 =A各列線性無關 =>
x = 0 =矩陣可逆,零空間為{0} =>
A^T * A可逆
N(A^T * A) = N(A)
rank A^T * A = rank A
4.特殊矩陣
(1)方陣(Square Matrix):
#行數 = 列數,記為A~n,可稱為n階方陣
(2)對稱(Symmetric)矩陣:
- 要求為方陣
- 該概念适用于實矩陣,對于複矩陣,有類似的概念"埃爾米特矩陣"
S^T = S OR s~ij = s~ji
#任何矩陣乘其轉置都得到對稱矩陣:
R^T * R = S
(R^T * R)^T = R^T * R^(TT) = R^T * R
#反對稱(Anti-Symmetric)矩陣:AS^T = -AS OR as~ij = - as~ji
#主對角線上的元素全部為0
- 機關(Identity)矩陣(I/E):
I~ii = 1 AND I~mn = 0
#對角線上元素均為1,其餘元素均為0
(3)零矩陣(O):
o~ij = 0
#所有元素均為0
(4)置換(Permutation)矩陣( P):
#P~n是行經過重新排列的I~n
#對n階而言,有n!個
#Pi * Pj ∈ Set P;Pi^(-1) = P^T ∈ Set P
#(P~n構成1個對矩陣乘法和逆封閉的群)
#以3階為例:
[[1 0 0],[0 1 0],[0 0 1]],[[0 1 0],[1 0 0],[0 0 1]],[[0 0 1],[0 1 0],[1 0 0]],
[[1 0 0],[0 0 1],[0 1 0]],[[0 1 0],[0 0 1],[1 0 0]],[[0 0 1],[1 0 0],[0 1 0]]
#行置換矩陣:
#乘在原矩陣左側
[[0 1],[1 0]] * [[a b],[c d]] = [[c d],[a b]]
#列置換矩陣
#乘在原矩陣右側
[[a b],[c d]] * [[0 1],[1 0]] = [[b a],[d c]]
(5)r = 1的矩陣:
r = 1的矩陣可以寫成列向量與行向量之積
A = [[1 4 5],[2 8 10]] = [1 2]^T * [1 4 5]
1個r = x的矩陣可以被分解為x個r = 1的矩陣
r = 1的矩陣可以視為基
max{rank A,rank B} ≤ rank (A + B) ≤ rank A + rank B
(6)旋轉(Rotation)矩陣(Q):
乘以一個向量時改變向量的方向但不改變大小并保持手性不變的矩陣
#執行個體:
Q = [0 -1,1 0]#使向量逆時針旋轉90°
7.正矩陣(Positive Matrix):
對矩陣A,若∀a~ij>0,則稱A為正矩陣,記為A>0
5.矩陣的迹(Trace):
即矩陣所有特征值的和,記為tr(A)
#即Tr(A) = Σ(λi) (i = 1...n),記為tr(A)
#性質:
矩陣的迹等于矩陣對角線上所有元素的和,即Tr(A) = Σ(a~ii) (i = 1...n)
三.向量空間(Vector Space)
1.向量空間
(1)R^n:所有n維實向量(Real Vector)構成的空間
R^1:1條過原點的直線
R^2:1個過原點的平面
R^3:1個過原點的3維空間
(2)向量空間對加法和數乘是封閉的(closed)(向量空間中任意2個向量的線性組合仍在該向量空間中)
- 必定包含0向量(vec a - vec a = 0)
2.子空間(Sub-space):1個嵌在向量空間中(是另1個向量空間的一部分)的向量空間
- A * x = b在b ≠ 零向量時的解均不構成子空間:
解中不包含0向量
解的集合是R^n平移到不過原點的位置
(1)Rm(m ≤ n)是Rn的子空間
R^2的子空間:
整個R^2
L:任何過(0,0)的直線(R^1)
Z:0向量(R^0)
(2)4個重要子空間:
1.列空間(Column Space;C(A)):矩陣各列的所有線性組合
C(A) in R^m;dim C(A) = r
#Ax = b不總是有解(C(A)無法填充整個R^m):僅當b ∈ C(A)時有解
#Ax = 0總是有解(0向量永遠在C(A)中)
#1組基是所有主列
#執行個體:
A~32 = [[1 3],[2 3],[4 1]]
C(A):(10/3)x - (11/3)y + z = 0 OR x * [1 2 4]^T + y * [3 3 1]^T
a R^2 in R^3
A~43 = [[1 1 2],[2 1 3],[3 1 4],[4 1 5]]#第3列與前2列線性相關
C(A) = x * [1 2 3 4]^T + y * [1 1 1 1]^T
a R^2 in R^4
2.行空間(Row Space;C(A^T)):矩陣各行的所有線性組合,即轉置矩陣的列空間
C(A^T) in R^n;dim C(A^T) = r
#1組基是R的前r行
#行變換不改變行空間
3.零空間(Null Space;N(A)):Ax = 0的解構成的空間
N(A) in R^n;dim N(A) = n - r
#性質:設A為矩陣,v,w為向量,k為常數
A * v = 0 AND A * w = 0 ⇒ A * (v + w) = 0 ⇒ v + w ∈ N(A)
A * (k * v) = 0 ⇒ k * A * v = 0
#1組基是所有自由列
#執行個體:
A~43 = [[1 1 2],[2 1 3],[3 1 4],[4 1 5]]
N(A) = [c,c,-c] (c為∀常數)
a R^1 in R^3
#求解零空間過程見 四.1
4.左零空間(Left-Null Space;N(A^T)):轉置矩陣的零空間
N(A^T) in R^m;dim N(A^T) = m - r
#為何稱為左零空間(非正式):
A^T * y = 0~n1 ⇒ (A^T * y)^T = 0^T ⇒ y^T * A = 0~1n
#N(A^T)的1組基是E(E = R * A^(-1))的後m - r行
E * [A~mn I~m] = [R~mn E~m]
R的後m - r行為零向量,即E的後m - r行乘A得到零向量
(3)4個重要子空間的關系:
#次元:
dim C(A^T) + dim N(A) = n
dim C(A) + dim N(A^T) = m
#嵌入:
C(A),N(A^T) in R^m
C(A^T),N(A) in R^n
#基本變換與行/列空間:
行變換不改變行空間,但會改變列空間;列變換相反
#正交:
C(A)與N(A^T)是R^n中的正交補(Orthogonal Complements)
#即C(A)包括且隻包括R^n中所有與N(A^T)正交的向量
證明同理
C(A^T)與N(A)是R^n中的正交補
1.A * x = 0 ⇒ [row 1,row 2...row n] * x = 0 ⇒ [row i] * x = 0 (i = 1...n) ⇒ x與C(A^T)的1組基正交 ⇒ C(A^T) ⊥ N(A)
2.dim C(A^T) + dim N(A) = n
(4)性質:
Sub-space1 ∪ Sub-space2 is not Sub-space (除非1是2的子集)
Sub-space1 ∩ Sub-space2 is Sub-space2
(5)零和向量空間
向量空間中所有向量次元相同,每個向量的各分量和為0
S = [[xi1 xi2 ... xin]^T ...] (xi1 + xi2... + xin = 0) (i = 1,2...m)
(xi1 + ... + xin) + (xj1 + ... + xjn) = 0
k * (xi1 + ... + xin) = 0
dim S = n - 1
S = N([1 1 ... 1])
[1 ... 1] * [[x11 x12 ... x1n]^T ... [xi1 ... xin]] = [x11 + x12 + ... + x1n ... xi1 + xi2 + ... + xin] = 0
3.秩(Rank;r):
矩陣主元(Pivot)的個數
消元得到行階梯型矩陣(R)後,主元所在的列為主列(Pivot Column),其餘列為自由列(Free Column)
自由變量的個數即為n - r
對A~mn,r ≤ min{m,n}
4.基(Basis):
向量空間的一組基:一組向量,這些向量線性無關且能生成這個向量空間
#不多(線性無關)不少(可以生成這個向量空間)
#對R^n,其∀1組基構成的的矩陣需要可逆
#∀1個向量空間都有無窮多組基
#1個給定向量空間的每組基向量的個數都相等
#列空間的1組基是其所有主列
5.維數(Dimension):
向量空間S的1組基中向量的個數,記作dim S
#dim C(A) = r (主向量的個數)
#dim N(A) = n - r (自由向量的個數)
*6.一些特别的向量空間
(1)矩陣構成的向量空間
#将矩陣看作向量
#矩陣加法/數乘的運算律與向量相同
#所有矩陣構成的向量空間的一些子空間:
#所有m * n的矩陣M:dim M = m * n (R^n ⇒ R^(m * n) )
#n階方陣 = S + U:dim (S + U) = n^2
#所有上/下三角矩陣U/L:dim U~n = (n^2 + n) / 2
#所有對稱矩陣S:dim S~n = dim U~n
#對角矩陣D = U ∩ S:dim D~n = n
#3階方陣向量空間M的子空間
#3階U/L:dim U = 3 * 3 = 9
[[1 0 0],[0 0 0 ],[0 0 0]]...[[0 0 0],[0 0 0],[0 0 1]]
#3階S:dim S = 6
[[1 0 0],[0 0 0],[0 0 0]]...[[0 0 0],[0 0 0],[0 0 1]],[[0 1 0],[1 0 0],[0 0 0]]...[[0 0 0],[0 0 1],[0 1 0]]
#3階U/L ∩ 3階S = 3階D:dim D = 3
[[1 0 0],[0 0 0],[0 0 0]]...[[0 0 0],[0 0 0],[0 0 1]]
#M = S + U:dim(S + U) = 9
#dim (S ∩ U) + dim (S + U) = dim S + dim U
(2)線性微分方程的通解:
#示例:
y''(x) + y(x) = 0
1組基:sin(x),cos(x)
向量空間:y = C1 * sin(x) + C2 * cos(x)
dim (Solution Space) = 2
四.方程組可解性(Solvability)及求解方法
- 當b ∈ C(A),有解
- 特别地,當b為0向量,始終有解
1.A * x = 0 (齊次方程組)
[[1 2 2 2],[2 4 6 8],[3 6 8 10]]
#解出零空間(A * x = 0 ⇒ U * x = 0 ⇒ R * x = 0)
#消元得到行階梯型(消元不改變零空間)
A = [[1 2 2 2],[2 4 6 8],[3 6 8 10]] ⇒ [[1 2 2 2],[0 0 2 4],[0 0 2 4]] ⇒ [[1 2 2 2],[0 0 2 4],[0 0 0 0]] = U1
#找出n - r個線性無關的特解(數量等于自由變量數)
#通常在1個特解中,1個自由變量取1,其餘自由變量取0(即用自由變量表示主變量)
r1 = [-2 1 0 0]^T,r2 = [2 0 -2 1]
#這r個特解的線性組合為零空間
N(A) = x2 * r1 + x4 * r2 = x2 * [-2 1 0 0]^T + x4 * [2 0 -2 1]^T
#消元得到行最簡型
[[1 2 2 2],[0 0 2 4],[0 0 0 0]] ⇒ [[1 2 0 -2],[0 0 1 2],[0 0 0 0]]
#回代相當于利用列變換将矩陣變成标準型(Reduced Row-echelon Form;R)
#R的形式為[[I~rr F~r(n-r)],[O~(n-r)r O~(n-r)(n-r)]]
#F是自由變量構成的矩陣
[[1 2 0 -2],[0 0 1 2],[0 0 0 0]] ⇒ [[1 0 2 -2],[0 1 0 2],[0 0 0 0]]
R
#利用零空間矩陣(Nullspace Matrix)1次找出所有解R * N = O
#N為所有解構成的矩陣,即N = [x1 x2...xn]
R * N = O ⇒ N = [-F,I] ⇒ R * x = 0 ⇒ [[I F],[O O]] * [x~pivot,x~free] = O ⇒ x~pivot = - F * x~free
[[1 0 2 -2],[0 1 0 2],[0 0 0 0]] ⇒ N = [[2 -2,0 -2],[1 0,0 1]] ⇒ x
#(注意此時變量順序已發生改變)
#當N(A) = R^0.隻有零解;當N(A) ≠ R^0,有非零解
當m < n:一定有非零解
2.A * x = b (非齊次方程組)
- 如果A各行的線性組合(系數不均為0)可以得到0向量,b各行的相同線性組合也需要為0
- 解的幾何表示:N(A)平移到過x~p的位置
#當方程有解:
#将所有自由變量設為0
x2 = 0,x4 = 0
#在自由變量均為0的情況下解出A * x = b的1個特解x~p
x1 + 2x3 = 1 ⇒ x1 = - 2
2x3 = 3 x3 = 3 / 2
x~p = [-2 0 3/2 0]^T
#求出A的零空間
N(A) = x2 * [-2 1 0 0]^T + x4 * [2 0 -2 1]^T
#将N(A)與x~p相加得到所有解
A * x~p = b
A * x~n = 0
A * (x~p + x~n) = A * x~p + A * x~n = b + 0 = b
x = N(A) + b = x2 * [-2 1 0 0]^T + x4 * [2 0 -2 1]^T + [-2 0 3/2 0]^T
A~mn,rank A = r
#如果列滿秩(Full Column Rank):r = n < m
N(A) = {0} AND R = [I,O]
x = x~p(唯一解;Unique Solution)或無解(0解/1解)
#如果行滿秩(Full Row Rank):r = m < n
有n - m = n -r個自由變量 AND R = [I F] (實際上主變量與自由變量交插出現)
x = x~p或c * x1 + d * x2 + x~p(1/∞解)
#如果滿秩(Full Rank):r = m =n
N(A) = {0} AND R = I
x = x~p(1解)
#如果不滿秩:r < min{m,n}
R = [[I F],[O O]]
x = c * x1 + d * x2 + x~p或無解(0/∞解)
3.解的結構
(1)A * x = 0:
x = c * x1 + d * x2
#x1,x2為方程的兩個特解;c,d為∀實數
(2)A * x = b:
x = N(A) + x~p = c * x1 + d * x2 + x~p
#x~p為A * x = b的1個特解
五.線性相關性(Linear Independence)
1.定義:
對向量x1...xn,如果不存在c1...cn(c1^2 + ... + cn^2≠0)使c1 * x1 + ... + cn * xn = 0,則稱x1...xn線性無關;反之稱為線性相關
#如果1組向量中包含零向量,這組向量一定線性相關
c1 * 0 + 0 * x2 + ... + 0 * xn = 0
#如果向量數超過其維數,這組向量一定線性相關
A * x = 0在m < n時一定有非零解
2.矩陣的列的線性無關性:
#與A * x =0的解
A * x = 0如果無非零解(A的零空間隻包括零向量),A的各列線性無關
A * x = 0隻存在零解 ⇒ [α1 α2...αn] * [x1 x2...xn]^T = 0隻存在零解 ⇒ α1 * x1 + α2 * x2 + ... + αn * xn = 0隻存在零解
#與零空間
#當r = n時A的各列線性無關(無自由變量)
#當r < n時A的各列線性相關
#互相垂直的各列一定線性無關
3.向量組生成(Span)向量空間:
這個向量空間由這個向量組所有向量的全部線性組合組成
#矩陣的列生成列空間
六.正交(Orthogonality)和投影
1.正交(Orthogonal)向量/子空間:
#正交向量:
x與y正交 <==> x ⊥ y <==> x · y^T = 0 <==> |x|^2 + |y|^2 = |x + y|^2
向量x的長度 = x · x^T
|x|^2 + |y|^2 = |x + y|^2 ⇒ x · x^T + y · y^T = (x + y) · (x + y)^T ⇒ 0 = x · y^T + y · x^T ⇒ x · y^T = 0
零向量與任何向量正交
#正交子空間
子空間S與子空間T正交 <==> S中的∀向量與T中的∀向量正交
如果S和T在非0向量處相交,S一定不和T正交
C(A) ⊥ N(A^T),C(A^T) ⊥ N(A)
2.子空間投影(Projection)
(1)子空間投影:
#對2維向量
#a,b為行向量,将b投影到a上
#p,a,b關系:
p ⊥ e ⇒ a * (b - x * a)^T = 0 ⇒
x * a * a^T = a * b ⇒
x = (a * b) / (a * a^T) ⇒
p = x * a^T ⇒
p = [(a * b) / (a * a^T)] * a^T
#投影矩陣P:
p = P * b ⇒
P = (a^T * a) / (a * a^T)
#性質:
C(P) = 1條過a,平行于向量a的直線
rank P = 1
P^T = P
P^T = ((a^T * a) / (a * a^T) )^T = (a^T * a)^T / (a * a^T) = P
P^2 = P
#對n維向量空間
#b,a1,a2...an為列向量,A以a1,a2...an為基,将b投影到C(A)上
p = A * x' (為列向量)
e = b - p ⊥ C(A) ⇒
e ⊥ a1 ... an ⇒
e ⊥ C(A)
[a1^T...]^T * (b - A * x') = [0 ... 0]^T即A^T * (b - A * x') = 0 ⇒
A^T * A * x' = A^T * b ⇒
x' = A^T * (A^T * A)^(-1) * b ⇒
p = A * (A^T * A)^(-1) * A^T * b ⇒
P = A * (A^T * A)^(-1) * A^T
#如果A是方陣:P = I,C(A) = R^n,b在C(A)中,P * b = b
#如果b ⊥ C(A):b in N(A^T),P * b = 0
#性質:P^T = P,P^2 = P
投影到與C(A)垂直的空間上,投影矩陣為P' = I - P,P'性質同P
p + e = b
e = (I - P) * b
(2)應用:在A~mn * x = b (m > n)無解時"求解"該方程
即解出最接近的解
利用(A^T)~nm * A~mn = S~n,S一定可逆
求解A^T * A * x' = A^T * b#一定可解
3.最小二乘法(Least Squares):線性回歸分析(Linear Regression)
資料點b1(t1,y1),b2(t2,y2)...bn(tn,yn);拟合曲線y = D * t + C
求曲線,要求:D * ti + C = yi (i = 1 ... n)
即:[[1 t1],[1 t2]...[1 ti]] * [C D]^T = [y1 y2 ... yn]^T (無解)
最優解使|A * x - b|^2 = e^2 = e1^2 + ... + en^2最小
即:Σ(D * ti - C - yi)^2 (i = 1 ... n)最小
求解x' = [C' D']^T和p
A^T * A * x' = A^T * b,p = A * x'
執行個體:
資料點(1,1),(2,2),(3,2) ⇒ 方程組:C + D = 1,C + 2D =2,C + 3D =2
[[1 1 1],[1 2 3]] * [[1 1 1],[1 2 3],[1 2 2]]^T = [[3 6 5],[6 14 11]]
A^T [A b]
新方程組:3C + 6D = 5,6C + 14D = 11(正規方程組;Normal Equations)
最優直線:y = t / 2 + 2 / 3
易受離群值(Outlier)影響:如果有遠離大多數點的點,偏差将極大
4.标準正交向量組(Orthonormal Vectors):
(1)概念:
q1,q2...qn均為列向量
由互相垂直的機關向量構成的向量組
qi^T * qj = 0 (i ≠ j) OR 1 (i = j) (即|qi| = 1 (i = 1 ... n) AND qi ⊥ qj)
#執行個體:[1 0 0]&[0 1 0]&[0 0 1],[cosθ,sinθ]&[-sinθ,cosθ]
标準正交向量:a ⊥ b且|a| = |b| = 1
标準正交基(Orthonormal Basis):标準正交向量組作為基
(2)正交矩陣(Orthogonal Matrix;Q):
#有标準正交列的矩陣(Matrix with Orthonormal Columns):
Q = [q1 q2 ... qn]
Q^T * Q = [q1^T,q2^T,...qn^T] * [q1 q2...qn] = I
投影矩陣P = Q * (Q^T * Q)^(-1) * Q^T = Q * Q^T
#執行個體:Q = [1 -2,2 -1,2 2] / 3
#當Q為方陣,稱為正交矩陣(Orthogonal Matrix)
#習慣上不稱為标準正交矩陣(Orthonormal Matrix)
此時Q可逆,Q^(-1) = Q^T
投影矩陣P = Q * Q^T = I
#執行個體:
置換矩陣,Q = [cosθ -sinθ,sinθ cosθ],Q = [1 1,1 -1] / (2)^(1/2)
#正規方程:
Q^T * Q * x' = Q^T * b ⇒ x' = Q^T * b ⇒ x'i = qi^T * b
#阿德瑪矩陣(Adhemar Matrix):僅由1,-1構成的正交矩陣
#已知在n = 2,4,16,64...時存在,在哪些次元下成立的規律未知
#執行個體:
Q = [1 1 1 1,1 -1 1 -1,1 1 -1 -1,1 -1 -1 1] / 2
(3)格拉姆-施密特正交化(Graham-Schmidt Calculation):由線性無關向量構造标準正交向量
#步驟:
線性無關向量a1,a2 ... an ⇒
正交向量組a1',a2' ... an' ⇒
标準正交向量組q1 = a1' / |a1'|,q2 = a2' / |a2'| ... qn = an' / |an'|
#缺點:經常出現根号
#當n = 2:
a,b為線性無關的列向量
a' = a
b' = b - p = b - [(a'^T * b) / (a'^T * a')] * a'
q1 = a' / |a'|
q2 = b' / |b'|
#當n = 3:
a,b,c為線性無關的列向量
a' = a
b' = b - [(a'^T * b) / (a'^T * a')] * a'
c' = c - [(a'^T * c) / (a'^T * a')] * a' - [(b'^T * c) / (b'^T * b')] * b'
減去a方向上的分量 減去b方向上的分量
q1 = a' / |a'|
q2 = b' / |b'|
q3 = c' / |c'|
#當n ≥ 4:同理
#執行個體:
a = [1,1,1],b = [1,0,2],c = []
a' = a = [1,1,1]
b' = b - [(a^T * b) / (a^T * a)] * a = [1,0,2] - (3 / 3) * [1,1,1] = [0,-1,1]
Q = [q1 q2] = [a' / |a'| b' / |b'|] = [[1 / 3,1 / 3,1 / 3] [0,-1 / sqrt(2),1 / sqrt(2)]]
#總結:
ai' = ai - Σ{[(aj^T * ai) / (aj^T * aj)] * aj} (i = 1,2...n;j ＜ i)
qi = ai' / |ai'|
(4)矩陣的QR分解
A = Q * R
#A的列向量線性無關;Q的列向量是由A的列向量構造的标準正交向量組
#故C(A) = C(Q)
#a1,a2...q1,q2...均為列向量
A = [a1 a2],Q = [q1 q2] ⇒
R = [a1^T * q1,a2^T * q1;a1^T * q2,a2^T * q2] = [a1^T * q1,a2^T * q1;0,a2^T * q2]
#由于qi ⊥ qj (j < i),故R為上三角矩陣
#矩陣Q的性質:Q^(-1) = Q^T ⇐ Q * Q^T = E
BTW.線性代數與圖論(Graphs)
(1)圖(Graphs):邊(Edge)和節點(Node)的集合,邊連接配接節點
(2)1個包含n個節點,m條邊的圖可以用1個m * n的矩陣表示
(3)研究人際關系(人為節點,關系為邊),網際網路
距離:從1個節點到另1個節點最少需要經過多少條邊
六度分離理論(Six Degrees of Separation)—小世界圖
(4)電路分析:
關聯矩陣(Incidence Matrix):
A = [[-1 1 0 0],[0 -1 1 0],[-1 0 1 0],[-1 0 0 1],[0 0 -1 1]]#-1指電流從此流出,1指電流流入這裡
dim C(A) = dim C(A^T) = 3
非0元素共2m個
回路(Loop):起點和終點相同的路徑,如邊1,2,3構成1個回路
1個回路的邊所在的各行線性相關
樹(Tree):無回路的圖,如邊1,2,4
如果存在n個節點,樹中最多有n - 1條邊,故r = n - 1
A * x = [x2 - x1 x3 - x2 x3 - x1 x4 - x1 x4 - x3]^T
xi (i = 1 ... 4)代表對應結點的電勢(Potential) = A * x = e (電勢) =>
xi - xj代表對應邊上的電勢差(Potential Difference) = y = ρ * e (電導率;歐姆定律) =>
N(A) = C * [1 1 1 1]^T#所有結點的電勢由1個常數決定,進而決定電勢差然後是電流
Node4接地,電勢為0 ==> 求出其他結點電勢
任意3個結點電勢線性無關,第4個接地
dim N(A) = 1,r A = 3 (互相無關的邊數),dim N(A^T) = 2 (互相無關的回路數量)
A^T * y = [- y1 - y3 - y4 y1 - y2 y2 + y3 - y5 y4 + y5]
yi (i = 1 ... 5)代表對應邊上的電流(Current) = A^T * y = f (外部輸入電流) =>
A^T * y = 0(基爾霍夫電流定律KCL)
(任何結點的電流在電荷不積累,無電源時流入=流出)
N(A^T) = a * [1 1 -1 0] + b * [0 0 1 -1 1]
基本方程:A^T * ρ * A * x = f
dim N(A^T) = m - r = m - (n - 1)
loops = edges - nodes + 1
nodes - edges + loops = 1 (歐拉公式)