考研
線性代數
數學
線性代數這門學問最重要的就是在探討向量空間中線性轉換,定義向量空間最主要的2個運算為向量加法與純量乘法,再定義線性變換為一向量空間mapping到另一項向量空間的一個函數,記為,並保有以下2個線性運算的性質
考慮一歐式空間的線性變換,將歐式空間的標準基底做線性轉換可以推導得 因此可以得到結論 - 歐式空間的線性變換相當於做矩陣乘法,這個矩陣稱為代表矩陣,若是以基底做線性轉換,這個矩陣可稱為標準代表矩陣。
定義基底為線性獨立的向量集,記為且有"足夠多"的向量可以span成向量空間,記為,因此在這個向量空間中的每個向量都可以用這個基底所線性組合的係數合成,其中這個線性組合的係數稱之為座標 上述座標的form與歐式空間相似,因此有了上述基底與座標的觀念,就可以把一個有限維抽象的向量空間"透過基底"轉換為跟歐式空間相似的form。
需要記得是有限維數的空間,線性代數只探討有限維數的空間,至於無窮維的空間討論是泛函分析。
因此總結來說,考慮一個抽象的線性變換,透過給定抽象的向量空間一組基底與給定抽象的向量空間一組基底,就可以把這個兩個抽象的向量空間拉至歐式空間,而歐式空間的線性轉換等於矩陣乘法。
由於基底不具有唯一性,因此同一向量空間中不同基底之間轉換就需要乘上一個轉換的矩陣,這個矩陣就是要如何用新的基底選擇適當的線性組合合成出原基底的向量之中線性組合的係數。假設在標準基底下的代表矩陣難以計算,我們可以嘗試"繞遠路",先將標準基底轉換為"好算"的基底,這個"好算"的基底的代表矩陣十分好求,之後再將"好算"的基底轉換為標準基底即可。
特徵值/向量與對角化就是基於上述的觀念,首先把問題限制在定義域與對應域相同的線性轉換,想法是嘗試找一個"適當"的基底下使線性變換簡單,對單一向量來說這個簡單的線性就只是一個純量乘上自己,而對整個向量空間來說的代表矩陣就是對角化矩陣。
在求向量的線性變換時,我們有了不一樣的解題思路,嘗試把向量拆成各個特徵向量的線性組合
再來沿著各個特徵向量的方向去做移動,也就是乘上一個scalar
最後將這些運算完的向量一一相加就是,如下圖所示
另一個觀念是當求出來的特徵值是複數的話,經過對角化後對角線矩陣是複數,形式十分複雜,我們嘗試將其轉為Canical form,就可以發現實際上中是一個伸縮加上旋轉的矩陣。總結來說特徵值是實數就只是沿特徵向量方向做伸縮變換;特徵值是複數不只是沿特徵向量方向做伸縮變換,還會旋轉。
正定矩陣的先決條件為對稱矩陣,對所有非零的向量,滿足 其中稱之為矩陣的二項式(matrix of quadratic form)。觀察上式矩陣相乘最後的size,會是一個純量。
新增條件 | 矩陣分解 |
---|---|
高斯消去法時不需要列交換 | LU分解 |
可逆矩陣 | LDU分解 |
對稱矩陣 | LDLT分解 |
正定矩陣 | LLT分解 |
給定一不需要列交換的矩陣,透過"加法列運算的高斯消去法",一步步化簡為row echelon form,這個row echelon form就是上三角矩陣,而將之前經過"加法列運算的高斯消去法"的每一步都轉換為基本矩陣,記為
加上為可逆矩陣的條件,可以推得 其中對角線數字均不為0,因此進一步將拆解為對角線矩陣與對角線元素為1的上三角矩陣,記為 再加上為對稱矩陣的條件,可以推得 最後加上為正定矩陣的條件,可以推得 由於正定矩陣的條件,所以對角線矩陣每個對角線元素都會大於0,因此開根號後不會是虛數,矩陣就可以被進一步分解為 欲證明另一邊的,則將帶入正定矩陣的條件
正定矩陣其中一個等價條件為可被Cholesky分解,也就是對角線矩陣的元素皆大於0,因此
特徵值分解只適用可對角化的方陣,非對角化的方陣可以找其Jordan Form,但如果不是方陣的話就需要使用SVD(singular value decomposition)分解,SVD分解適用於任何矩陣。"仿造"前面對角化的觀念,當要求代表矩陣我們試圖"繞遠路",分別選擇兩組"好算"的基底為單位正交,使得在此基底下的線性轉換僅在對角線的前項數值有值。
因此SVD分解形式就可寫作為
嘗試改寫成以下形式
也就是說給定一歐式空間線性變換,其代表矩陣為
嘗試把向量空間的向量mapping至向量空間的向量,其中前項有值,而後面的向量則直接對應到0向量。
同理將取轉置得,其中歐式空間線性變換的代表矩陣,其中前項有值,而後面的向量則直接對應到0向量。
嘗試將轉置與相乘 欲求第一步就是求(或是),並做對角化,求出來的特徵值開根號就是的奇異值,記為
為半正定矩陣,故其特徵值必為實數且大於等於0,特徵值開根號所得的奇異值不會是虛數。
證明 - ,若,則
而的特徵值對應的特徵向量,做正規化,確保特徵向量是單位長度後,拉成一行行的行向量,形成 根據前面向量與向量之間線性轉換的關係式 求出向量,若向量的個數少於向量的個數,也就是代表矩陣是從高維歐式空間投影到低維歐式空間,根據此線性轉換的關係式求出來的會少求幾項。
我們可以嘗試選擇一組單位向量不平行於已知的,使用Gram-Schmidt orthogonalization求出單位正交基底 以三維空間的特殊case下就是做已知向量一與向量二的外積,記為,最後拉成一行行的行向量,形成正交矩陣 以上步驟就是把空間中的單位正交集合(set) 擴展到能代表空間的單位正交基底(basis) 的過程。
考慮一線性變換的代表矩陣 可將矩陣做SVD分解 在的右側乘上向量等於做行展式,其結果為這些線性獨立的向量的線性組合,因此的column space為 而null space定義為齊次聯立方程式中所有解,在此就是這些在定義域"對應到0向量"的向量,因此的null space為 同理,將矩陣的轉置,此線性變換的代表矩陣 可將矩陣做SVD分解 在的右側乘上向量等於做行展式,其結果為這些線性獨立的向量的線性組合,因此的column space,也就是的row space為 而null space定義為齊次聯立方程式中所有解,在此就是這些在定義域"對應到0向量"的向量,因此的null space,也就是的left null space為
觀察上式,要形成向量空間就是,就是將的row space與的null space兩空間的向量相加做線性組合(和空間)而成,而,因此為直和(direct sum)空間,其中與互為正交補空間(orthogonal complement space),同理的column space與的left null space 由ch2 秩數(rank)結論列向量獨立個數等於行向量獨立個數,因此 即可推得rank–nullity theorem 下圖為圖解法,其中垂直的符號代表兩向量子空間的交集為0向量。
在討論低秩近似法前,我們要找到如何代表兩矩陣"長得很像"的衡量標準?直覺來說就是找兩矩陣的"長度","長度"講為較專業的術語就是範數(norm),norm符合兩個性質,一是除了零矩陣的norm等於0,其他矩陣的norm必定大於0,二是符合三角不等式,norm在定義上百百種,這邊只討論2種norm
SVD分解中數值只由前項column vector,前的方陣決定,前項row vector所決定。因此若資料以SVD形式儲存,可進一步簡化為reduced SVD 由SVD計算步驟可知,欲求正交矩陣,是把單位正交集合(set)擴展到單位正交基底(basis),實際上擴展哪些基底不重要,也不具有唯一性,只是為了要讓的行向量單位正交而形成正交矩陣而已。
如此就可以定義SVD的前項外積展開式,取前將奇異值一一取出展開 其秩數,根據Eckart-Young Theorem,在同一秩數下,最接近原本矩陣的距離就是前項外積展開式,這就是低秩近似法(low-rank approximation)最佳化的問題。 因此在同一秩數下,最靠近的矩陣就是前項外積展開式。
最後就可計算相對誤差的最小值
考慮,若,也就是說有效方程式條,多於未知數個,屬於overdetermined problem,解不存在(或是只存在一組解),但問題總不能這樣就結束,因此我們"試圖"找到一個近似解的折衷方案 - 找能最小化的長度。
在空間下
只會落在的平面,也就是,如果沒落在這個平面上,記為,則解不存在。這時我們希望能在這個的平面上找到一個向量,使得的距離能短越好,記為,根據幾何的知識,要讓向量能垂直於的平面,因此
由於問題一開始假設是full column rank,即,根據性質,因此,屬於full rank,,因此矩陣可逆。最後推得
證明思路為先證明零核空間相同,再根據rank–nullity theorem證明。
定義一函數為取norm的平方,這是取距離平方是為了方便運算。 欲求極值,就是找critical point,對於一個多變數實函數而言,要使所有方向的一階偏導數等於0,也就是梯度等於0。 欲求梯度除了可以將將函數對每一項分量做偏微分,另一種較方便的解法是先求方向導數,再根據"方向導數為梯度與該方向的內積"這個關係式求得梯度。 觀察上式的form,欲求梯度,嘗試先求方向導數,並整理成一個向量跟單位方向向量的內積的form,這個向量就是梯度。 故critical point即為 同法一最後推得
考慮,若,也就是說有效方程式條,多於未知數個,屬於underdetermined problem,具有無限多組解,可將解拆為齊次解與特解。 其中齊次解為的子空間,屬於null space,以下圖空間為例,就是通過原點的平面,而特解就是將此平面做平移。欲求最佳的解,加上限制項 - 要讓解的距離最小。
要使的集合落在平面,要使的距離最小,就是讓向量跟平面垂直。
由於問題假設加上性質,因此矩陣是full rank,行列式值不等於0,存在可逆矩陣,因此進一步推導
定義一函數距離的平方,取距離平方是為了方便運算。 在限制條件之下,欲求,這種帶有限制條件的極值問題,就需要使用Lagrange multiplier,把Lagrange multiplier 想像是變數,因此將帶有限制項的單變數向量求極值問題,拓展為雙變數向量求極值問題。需要注意這裡Lagrange multiplier 是帶有條限制式的向量形式。 由上式可以看出Lagrange multiplier在幾何上的意義,假設在向量空間,發生極值的條件為的等位曲面與的等位曲面相切,兩個等位曲面相切,則代表兩個梯度向量會平行,彼此只會差上一個常數倍,這個常數就是Lagrange multiplier。
帶入數值計算 欲求梯度,同前面最小平方問題的技巧,先求方向導數,並整理成一個向量跟單位方向向量的內積的form,這個向量就是梯度。 解得梯度,因此聯立方程式為 將式(2)帶入式(1)得 由於問題假設加上性質,因此矩陣是full rank,行列式值不等於0,存在可逆矩陣,使得 將式(3)帶回式(2)得
考慮,若,想要找到向量使得,並且在這些無限多組解中找到能。
因此使用SVD這個好用的工具下去求解,將做SVD分解,再求 這時再將做基底轉換為,將做基底轉換為 因此轉換為 因此我們把的問題,轉換為,其中可以變動的是解,而解經過基底轉換後變成,因此只有可變動,根據上面推導的form,把最小化就是把項弄為0,選擇 再滿足最小平方問題後,再來滿足最小範數問題,欲,即為,因此後面項取0 總結為 最後變數變換(基底轉換)回原本的變數
給定秩數的矩陣,做奇異值分解為 則虛反矩陣(pseudoinverse)定義為
在求解線性方程式,其最小平方問題與最小範數問題的通解就是 而經過數學推導(省略),可以得出結論 - 最小平方問題、最小範數問題都是用虛反矩陣求解時的特例
給定矩陣