[ MIT Class ] Linear Algebra, Spring 2005 - Lec3

Source From Here 
Preface 
 

Matrix Multiplication 
這就是套公式, 對公式不熟的可以參考 Wiki - Matrix multiplication. 但在影片有提到幾個觀念值得在這邊提. 

Multiplication - Way 1 
如果以 "矩陣" x "只有一行的矩陣"的角度來看: 
 

以 GLA 的範例代碼來驗證會是: 

view plaincopy to clipboardprint?

1. // Multiplication W1  
2. // A(mxn) * B(nxp) = C(mxp)  
3. // C(c1) = A*(Column 1 of B) <--- a="" column="" combinatioin="" of="" span="">  
4. // C(c2) = A*(Column 2 of B)  
5. // ...  
6. Matrix A = LA.newMtx3(2, 3, [1,2,3,4,5,6])  
7. Matrix B = LA.newMtx3(3, 2, [1,0,0,2,1,0])  
8. Matrix C = A*B  
9. printf("%s\n", C)  
10. // First column of C ---> c1  
11. Matrix O = A.col2Mtx(0)*B.val(0, 0)+A.col2Mtx(1)*B.val(1, 0)+A.col2Mtx(2)*B.val(2, 0)  
12. assertEquals(O.c(0), C.c(0))  
13. // Second column of C ---> c2  
14. O = A.col2Mtx(0)*B.val(0, 1)+A.col2Mtx(1)*B.val(1, 1)+A.col2Mtx(2)*B.val(2, 1)  
15. assertEquals(O.c(0), C.c(1))  

Multiplication - Way 2 
如果以 "只有一列的矩陣" x "矩陣" 的角度來看: 
 

以 GLA 的範例代碼來驗證會是: 

view plaincopy to clipboardprint?

1. // Multiplication W2  
2. // A(mxn) * B(nxp) = C(mxp)  
3. // C(r1) = (Row 1 of A)*B  
4. // C(r2) = (Row 2 of A)*B  
5. // ...        
6. // First row of C ---> r1  
7. O = B.row2Mtx(0)*A.val(0, 0)+B.row2Mtx(1)*A.val(0, 1)+B.row2Mtx(2)*A.val(0, 2)  
8. assertEquals(O.r(0), C.r(0))  
9. // Second row of C ---> r2  
10. O = B.row2Mtx(0)*A.val(1, 0)+B.row2Mtx(1)*A.val(1, 1)+B.row2Mtx(2)*A.val(1, 2)  
11. assertEquals(O.r(0), C.r(1))  

Multiplication - Way 3 
(13:40) 接著考慮 Column of A x Row of B: 
 

Multiplication - Way 4 
如果把一個 Matrix 看成數個 Block 組成的角度來看: 
 


Inverse Matrix 
(24:00) 接著看 Invertible Matrix: 
 

這裡解釋 Invertible Matrix 所具備的特性以及何謂 Singular Matrix. 

Gauss-Jordan 
(34:30) 這裡開始解釋如何求 Matrix A 的反矩陣. 一個做法是使用 Gauss-Jordan Reduction. 
 

Supplement 
* Inverse of a matrix by Gauss-Jordan elimination

[ RubyAlg ] MIT Linear Algebra, Spring 2005 - Lec16 (Linear Regression)

Source From Here 
 

Recall 
 

P 矩陣用來將 b 投影到其 Column Space 上, 因此考慮一下極端案例: 

* b 就在 Column Space 上, 則 Pb = b
* b 與 Column Space 垂直, 則 Pb = 0

Projections 
 

因為 Pb=p, 其中 p + e = b. 也就是 e 分量是 b 投影到 Null Space of A^T 的部分. 因此我們可以知道: 

e = b - p = (b - Pb) = (I-P)b

Linear Regression 
 
(上面的 [1,2,3] 應該是 [1,2,2]) 

目前 b = [1,2,3] 並且在目前的 Column Space 並無解! (b1=1, b2=2, b3=3), 因此我們要找出近似解 p=[p1,p2,p3], 讓方程式可以找出線性方程式的解: 
 

接著要計算 A^T*A 與 A^T*b: 

view plaincopy to clipboardprint?

1. require "alg/math/LinearAlgebra"  
2.   
3. LA = LinearAlgebra  
4.   
5. A = LA.newMtx3(3,2,[1,1,1,2,1,3])  
6. b = LA.newMtx3(3,1,[1,2,2])  
7. printf("A:\n%s\n", A)  
8. printf("A^T:\n%s\n",A.t)  
9. printf("b:\n%s\n", b)  
10. printf("\n")  
11.   
12. A2 = A.t*A  
13. b2 = A.t*b  
14. printf("A^T*A:\n%s\n", A2)  
15. printf("A^T*b:\n%s\n", b2)  

執行結果為: 
 

因此這時的方程式變成: 

3C' + 6D' = 5
6C' + 14D' = 11

(此時的解 C', D' 與原先方程式的解 C, D 是不同的!) 

下面使用代碼求出 C', D': 

view plaincopy to clipboardprint?

1. x2 = A2.inv*b2  
2. printf("[C',D']:\n%s\n", x2)  

執行結果: 

[C',D']:
0.6666666666666679 (C'=2/3)
0.5 (D'=1/2)

而得到的解為 C' = 2/3, D' = 1/2: 
 

接下來要使用剛剛解的方程式 y=2/3+1/2t 來看看近似的點與原先的點的誤差 (e1, e2, e3): 
 
(上面的 e1, e2, e3 還需乘與一個負號) 

接著回來原先的 b = p + e 等式: 
 

而有些特性可以知道如下: 

* p 與 e 垂直: 很直覺, 因為 p 是在 Column Space, e 是在 Null Space of A^T 上, 這兩個分量注定垂直. (p*e=0)
* e 與 Column Space 垂直: 這也是定義的觀點, 也就是說 e*[1,1,1] 與 e*[1,2,3] 皆會得到 zero!

Supplement 
- If A has independent column vector(s), then A^T*A is invertable (Prove) 
Suppose A^T*A*x=0, then x must be zero vector if A^T*A is invertable. Let's play a trick here. Consider: 

x^T*A^T*A*x = (A*x)^T * (A*x)=0

So we can infer that A*x = 0, then we know that A has independent column which force x to be zero only!

[ RubyAlg ] MIT Linear Algebra, Spring 2005 - Lec15 (Projection)

Source From Here


Projection

如上圖, 考慮 向量 b 在 向量 a 上面的投影為 p (p = xa, 向量 p 為 a 向量的常數倍); 而 p 向量加上 e 向量等於 b. 因為 e 向量與 b 向量垂直, 因此:

a^T * e = a^T * (b - xa) = 0

展開後並移項可以得到:

x*a^T*a=a^T*b

因此我們可以得到 b 向量在 a 向量上投影的常數 x (p = xa):


因此向量 p 便可以推得為 a 向量上的常數倍:


接著考慮下面簡單範例:


接著便可以利用剛剛得到的公式來使用代碼得到 p 向量:

view plaincopy to clipboardprint?

1. require "alg/math/LinearAlgebra"  
2.   
3. LA = LinearAlgebra  
4.   
5. b = Vector.new([1,1])  
6. a = Vector.new([2,0])  
7. printf("b:%s\n", b)  
8. printf("a:%s\n", a)  
9. p = a*(a.inner(b).to_f/a.inner(a))  
10. printf("p=:%s\n", p)  

執行結果如直覺為 p=[1,0] (其實就是 p 向量在 x 上面的分量):

b:[1, 1]
a:[2, 0]
p=:[1.0, 0]

接著思考是否有個投影 vector, 公式 或是 matrix P, 讓向量 b 可以透過它得到某個向量的投影量:


Why Projection? (20:00)
當 Ax = b 沒有解時, 我們能做的便是求近似解! 因此原先方程式會改成 Ax = p (p 為 b 在 column space of A 上的投影), 此時方程式會有解:


因為我們修改了方程式, 因此新方程式的 x 也就不是原先方程式的 x, 因此我們給它帶個帽子:


接下來會有一長串推論, 主要是想知道帶帽子的 x 與 p 向量的特徵:


整理 P 矩陣特性如下:

P^T = P
P^2 = P

Least Squares Fitting by A Line
接下來的主題延續問題當 Ax=b 沒有解, 那近似解該怎麼求? 考慮我們有三個點: (1,1), (2,2), (3,2). 如果想找到一條直線能夠穿過這三個點基本上是不可能, 因此只能求 "最接近" 這三個點的一條直線: b = C + Dt


方程式長相如下, 基本上可以很直覺地看出無解:


因此下一章節便要來介紹如何求近似解.