code

2017年1月17日 星期二

Linear Algebra筆記10 - 解Ax=0的演算法 (non reduced row echelon form)

Solve x for Ax=0

假設有以下的matrix A (3 equations, 4 unknowns):


要解Ax=b(求出x),我們要利用row reduction。
不過這邊不需要把0寫入成augmented matrix,因為將永遠是0向量。

注意高斯消去法顯而易見並不會改變nullspace(意即所有解的set形成的subspace),這正是消去法的作用。不過高斯消去法會改變column space,詳見後述。

再來要注意column2是column1的倍數,且row3 = row1 + row2


Elimination Process

經過第一個pivot(1,1)消去column 1所有非pivot位置的數目:


結果發現(2,2)和(3,2)都變成零了,這表示column2 和 column1有倍數關係才會變成這樣的結果。

不過這邊有一點奇怪,這不是一個square matrix,所以這算是第一次課堂上用non-square matrix來做高斯消去法,所以我們無法最後得到一個upper triangular matrix,只能說近似一個upper triangular matrix。

最後一步消去用pivot (2,3):



這其實有個專有名詞,稱為echelon form,形成某種階梯形沿著零的項目:



至此,我們已經把Ax=0 化簡成 Ux= 0,而不改變null space!

注意row 3為零row向量,代表其為上方pivot所在的row的linear combination,所以是一個non-independent row。

Rank of Algorithm

這個elimination過程中使用到的pivot數目就是所謂的rank! 在此例中為2。




Pivot variables and free variables

現在來到此演算法的一個關鍵步驟。
所有包含pivot的column稱為pivot variable,反之則稱為free variable,意味著可以assign任何x solution給free columns當linear combination形成null space的係數(i.e. 解),所以在此例中, column2 column4為free columns:



所以某特定解x = (x1 x2 x3 x4),其中x2 和 x4可以是任意數,例如(x1 1 x3 0)
有了任意設定的x2 x4,我們可以解此Ux=0,藉由back substitution帶入x2=1 和 x4=0:



我們可以得到一組特定解:


所以我們可以確定nullspace至少有包含這條線:任意實數c* vector x。
但這肯定不是整個nullspace,為什麼?因為我們可以任選x2=a, x4=b。

假設我們選x2 = 0, x4=1,可以得出另一個解:




Rank, Pivot Variables, Free Variables的關係

我們已經可以確定rank = pivot variables的數量了,因為這就是rank的定義。
知道了rank,我們也可以知道free variables的數量 = n - rank,如果A為 mxn matrix

事實上rank代表了真正independent equation的數量,在此例中為2,因為第三個equation是row1 + row2,不是independent的。



Generate Nullspace

有了兩個特定解的向量:



我們能產生整個nullspace嗎?

可以,事實上這兩者的linear combination就是:


不過x是一個4-d vector,換句話說nullspace要是 R^4 的subspace。

沒有留言:

張貼留言