L.A. 2 - elimination

upper triangle

簡單來說就是要把system of linear equations變成一個upper triangle:

或是：

有時候可以重新排列一下equations的順序，方便elimination:

Pivots

原本的system中的每個equation的第一個element都是pivot，負責把下面rows同樣column位置的element消除掉。最後形成的upper triangle的對角線位置剛好就是這些pivots。

Singular: 無解的狀況

事實上這是一組平行線，當然無解（交點）了：

Singular: 無限多解

elimination到最後，發現其實變成n個式子但是有 > n 個 variables：

Singularity

上面兩種非唯一解稱為（singular)，意思是只有一個pivot可以做elimination，而有唯一解的system不會只有一個pivots。

3個unknowns equations的狀況

system:

1st pivot是第一row的 2x，用它來消去row 2的 4x和 row3的 -2x，新的row2和 row3形成：

再來row2的1y 是2nd pivot（可以看到這是一個recursive process)，用來消除row 3的 1y:

所以我們透過消除法把原本Ax=b 變成 Ux=c，這邊U = upper triangle:

這個Ax = b 轉變成 Ux = c的過程，稱為forward elimination，U中的對角線就是所謂的pivots，pivots經過elimination才會正確找出來。

upper triangle的好處是，其中一個變數立即有解，然後通過back substitute一一解出其他的變數。

Elimination matrix

Ax=b在做elimination的過程中，b事實上也是同步在做加減乘除。事實上這相當於vector b乘上某一個matrix E，或是說一個elimination matrix E 施作在 vector b上：

由於b中的每一個element都是E的row 和 b的dot product，所以有時候光看E的row大概就能知道b會被 E "施作“ 成什麼樣：

如果E是identity matrix I，則可以看到b的element與I的row dot product就是那個component自己，或直接說 I * b = b:

如果elimination matrix 是以下這個：

則我們可以知道對b3來說，它減去了b1 * (4)，這個elimination matrix成就了新的b3，在原本的forward elimination過程中，這E代表了要形成upper triangle過程中，透過pivot 1把row 3的第一個element消除成零的過程。

L.A. 1 - linear equations

linear combination

vector的寫法：

vector length的符號：

所以norm operator = length

unit vector:

把linear combination of vectors寫成矩陣A乘以vector x：

這個反過來解讀可以說是 A "acts on" x，把vector x內的component轉化成另一個vector x'，例如A可以是一個difference matrix:

國高中教的矩陣乘法其實只是為了方便運算，沒有linear combination的概念在內，採用dot product形式：

Invertible matrix

Ax = b，通常已知matrix A和vector x
如果反過來知道matrix A和b，如果能求出x，則說matrix A is invertible ，會有一個對應的A^(-1) matrix：

Linear Equations

某個system of linear equations:

linear意思是變數之間只有加法，不會有乘法出現。

可以看成兩條線交會：

或是把係數看成vectors，則解相當於這兩個vectors的linear combination:

linear equations 寫成matrix form，正確解讀就是所有係數vectors組成的matrix A，其linear combination = b。

LAFF筆記3 - 解出Ax = b via LU factorization

LU Factorization of A

一組equations可以寫成Ax = b，這是沒有問題的。

如果A是square matrix，則我們可以把A分解成兩個matrices，一個是unit lower triangular matrix L，一個是upper triangular matrix U，也都是square matrix，使得A = LU：

這個之前在MIT筆記中原來已經有了！

用wiki例子解釋好了，這個LAFF課程用了計算matrix的演算法來教，不是我要學的目的，因為我並沒有想要implement matrix computation library。

可以看到L1就是第一個elimination matrix，也就是把first pivot a11以下清空的matrix
L2則是把剩下的a22以下的清空的elimination matrix。
所以A經過兩次elimination matrix左乘後，變成一個完全Upper triangular matrix Ｕ，也就是高斯消去法的結過。

所以單純變成怎麼找出L1和L2的inverse的問題了。這邊要看MIT Linear Algebra 筆記。

LAFF的課其實真的不需要把matrix computation algorithm放到課中。@@

LAFF筆記2 - 高斯消去法

System of Equations表示法

以下三種都是同一組equations的表示：

高斯消去法

是一個系統性的解linear equations題目的方法，適合電腦程式化。
高斯消去法最終形式就是要把一個equations削減成upper triangular form。

舉例過程如下：

三個空格依序是2 , 3, 1.6，最後得到一個upper triangular system，最後透過back substitution先解決X2 -> X1 -> X0，這就是upper triangular system的好處。

所以我們得出解答的vector:

Matrix form elimination

當然我們也可以寫成matrix form，然後把答案的vector寫入最右邊的appended column，類似以下：

Gauss Transform

這是一個elimination matrix ，乘上我們要解決的equations形成的matrix:

row picture乘法：matrix在左邊的時候，左邊matrix row 1 為右邊matrix 每個row的linear combination係數，之後放入等號右邊的第一個row:

所以等號右邊的一個row =
1 * [ 2 4 -2 ] + 0 * [4 -2 6] + 0 * [6 -4 2] = [ 2 4 -2]

左邊這個matrix 代表了第一步的gaussian elimination，並非全部：

所以我們可以把所有Gaussian Elimination的係數寫成一個matrix，變成一個transformation稱為Gauss transform。

LAFF筆記1 - Matrix and Linear Transformation

Standard basis vector (unit basis vector)

n-dimension vector如果只有index = j的element是1（index從0開始），其他都是零，那稱為一個unit basis vector ej:

Linear Combination of vectors

定義就是兩個vectors乘上scalars相加：

可以generalize成n個：

Inner Product (Dot Product)

這邊主要紀錄符號，因為很容易忘記v^T * v =  dot(v,v)。

Transpose 對加法的分配律

linear combination對加減法是有分配性的。

Linear Transformation定義

我們care about linear transformation function f，是因為他在許多application中比較好解！甚至我們會把non-linear problem用linear function來approximate，也是因為要比較簡單去解答。

Linear Combination & Linear Transformation

首先，任意一個vector x 都是unit basis vectors的linear combination:

所以對x apply某個linear transformation function L，由於linear transformation的性質，可以寫成：

這提供了一個速算法！我們不需要知道L真正的定義事實什麼，如果我們可以知道L(ej)的結果是什麼的話，L(x)就可以算出來了。

Matrix的意義

matrix只是表現一個linear transformation function L的數學表示法。每個column of A代表了unit basis vector是如何被L transformed的結果：

Matrix * vector的意義

乘上，既然matrix A的意義是所有unit basis vector被L transformed過的結果組合，則A乘上某一個vector x的意義為：

為什麼？因為兩者會得出一樣的結果，所以matrix A * vector x的意義就是對vector x做了某個linear transformation L的結果。

用matrix定義linear transformation

如果一個vector function可以用matrix A表示，則此function是一個linear transformation:

可以用這個性質來檢驗一個function是否為linear transformation。

Linear Algebra筆記12 - 解Ax=0的演算法 範例

再來練習一次演算法

假設有以下matrix A，求nullspace of A。

首先我們預期column1 column2會是pivot variables，因為independent，而column3因為是column1 + column2，所以會是一個free variable

(1) 先做row reduction for pivot (1,1)，結果如下：

(2) 再來做row reduction for pivot (2,2)，不過這是一個零啊！
可以跟row3 exchange:

然後做pivot(2,2) row reduction，完成了echelon form:

所以rank = 2，因為有兩個pivot columns。n-r = 3-2 = 1 free column。


(3) 對一個可能的x = (x1 x2 x3)，由于column3是free variable，所以我們可以任意assign值給x3，方便我們帶入解x1 x2，假設我們令x3 = 1:

則把x3帶入U所代表的system，我們得到一組特殊解：

事實上任意倍數cx都是解，所以在這條R^3空間中的通過原點的直線cx是一個subspace。那是不是Ax=0的整個nullspace呢？

答案是。因為不論x3取什麼值，x永遠會是c * (-1 -1 1)的線上。



(4) reduced row echelon form R

藉由把row2 * - 1加到row 1，我們把pivot(2,2)的上方數字清成0，並且移掉row2的2倍數，得到了R:

R的組成就是Identity matrix I和 Free matrix F的組成在上方，下方都是0。


(5) 得到nullspace matrix N

之前的nullspace cx可以發現就是c * (-F I)，所以以後只要得到RREF，就能組成nullspace of A。

結論

如果不做(3)，直接做到(4) (5)，也都可以找到nullspace，所以RREF提供一個較為系統性（不用任意給free variable值來back substitution)的演算方法來找出N(A)。