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。
沒有留言:
張貼留言