GSL 系列 6 — 線性代數 1 — 背景知識 1

文章目錄

• • 0 寫在前面
  • 1 LU 分解
  • • 1.1 相關符号
    • 1.2 LU 分解
    • 1.3 應用
    • 1.4 相關函數說明
  • 2 QR 分解
  • • 2.1 相關符号
    • 2.2 QR 分解
    • 2.3 應用
    • 2.4 QR 分解實施方式
    • 2.5 特殊矩陣的 QR 分解
    • 2.6 帶列轉置的 QR 分解
    • 2.7 相關函數說明
  • 3 LQ 分解
  • • 3.1 相關符号
    • 3.2 LQ 分解
    • 3.3 應用
    • 3.4 相關函數

0 寫在前面

本篇旨在對線性代數相關的背景知識做一些簡要結論性說明，這樣做的目的是為了更清楚的了解

GSL

線性代數部分的函數是在做什麼，是以并不會進行推導性說明。

同時，本篇還對每個線性代數知識點提供一個說明對應

GSL

相關函數的連結頁面，是以本篇還有對

GSL

線性代數部分的相關函數進行導航的功能。

由于本人知識水準有限，不免出錯，敬請指出，萬分感謝。

1 LU 分解

1.1 相關符号

置換矩陣： P P P

上三角 (梯形) 矩陣： U U U

下三角 (梯形) 矩陣： L L L

1.2 LU 分解

對于一般矩陣 A ( M × N ) A(M\times N) A(M×N)，有如下分解：

P A = L U PA=LU PA=LU

其中： P : M × M ;        L : M × min ⁡ ( M , N )        U : min ⁡ ( M , N ) × M P:M\times M;\;\;\;L:M\times \min(M,N)\;\;\;U: \min(M,N)\times M P:M×M;L:M×min(M,N)U:min(M,N)×M;

M ≥ N M\ge N M≥N 時， L L L 是下機關三角（梯形）矩陣

1.3 應用

1. 求解線性方程組 A x = b Ax=b Ax=b
2. 求逆 A − 1 A^{-1} A−1
3. 求行列式 det ⁡ ( A ) \det(A) det(A)

1.4 相關函數說明

參見：GSL 系列 6 — 線性代數 2 — LU 分解

2 QR 分解

2.1 相關符号

Q Q Q：正交矩陣

R R R：上三角（梯形）矩陣

H H H：Householder 矩陣

v v v：Householder 向量

τ \tau τ：Householder 系數

2.2 QR 分解

矩陣 A A A ( M × N M\times N M×N) 可以分解為如下形式：

A = Q R A=QR A=QR

其中： Q : M × M          R : M × N Q:M\times M\;\;\;\;R:M\times N Q:M×MR:M×N

2.3 應用

一般可以用來求超定方程 ( M > N M>N M>N) 的最小二乘解

2.4 QR 分解實施方式

這裡說明兩種，也是 GSL 當中實作的兩種。

1. Householder 變化法

   Householder 矩陣是一個正交矩陣，其作用在向量上是一個鏡像變換，也就是說通過鏡像變換可以将向量映射到坐标軸上，即将向量大部分元素置 0。可以通過多個 Householder 矩陣将矩陣 A A A 變為上三角（梯形）矩陣

   注意：對于此種方法在 GSL 中， Q Q Q 矩陣并不是直接存儲的，而是通過 Householder 公式轉換的方式進行存儲，公式如下：

   Q = H k ⋯ H 2 H 1 Q=H_k\cdots H_2H_1 Q=Hk​⋯H2​H1​ H i = I − τ i v i v i T H_i=I-\tau_iv_iv_i^T Hi​=I−τi​vi​viT​ v i = ( 0 , 0 , ⋯   , 1 , a i + 1 , a i + 2 , ⋯   ) v_i=(0,0,\cdots,1,a_{i+1},a_{i+2},\cdots) vi​=(0,0,⋯,1,ai+1​,ai+2​,⋯)

   是以，在此種方式中， GSL 對 Q Q Q 矩陣儲存如下兩個部分：

   • 一個 τ \tau τ 向量， ( τ 1 , τ 2 , ⋯   , τ k ) (\tau_1,\tau_2,\cdots,\tau_k) (τ1​,τ2​,⋯,τk​)
   • 每個 v i v_i vi​ 向量，并且隻儲存後面的 a a a 部分

2. 遞歸法（DGEQRF）

   參考文獻：Applying recursion to serial and parallel QR factorization leads to better performance

   注意： 同樣在此種方法中， Q Q Q 也不是直接儲存的，按照如下公式進行轉換儲存：

   Q = 1 − V T V T Q=1-VTV^T Q=1−VTVT

   其儲存也分為如下兩個部分：

   • 儲存 V V V， V V V 的列向量就是 v i v_i vi​，儲存方式如同 Householder 變化法
   • 儲存矩陣 T T T，矩陣 T T T 的對角向量就是 τ \tau τ

2.5 特殊矩陣的 QR 分解

( S A ) = Q R \left(\begin{array}{l}S \\ A\end{array}\right)=Q R (SA​)=QR

S S S 為 上三角矩陣，次元 N × N N\times N N×N； A A A 為稠密矩陣，次元 M × N M\times N M×N ，此時的 Q Q Q 公式如下：

Q = I − V T V T Q=I-VTV^T Q=I−VTVT V = ( I Y ) V=\left(\begin{array}{l}I \\ Y\end{array}\right) V=(IY​)

此時，其儲存分為三部分：

1. T T T 儲存
2. Y Y Y 儲存， Y Y Y 也是稠密矩陣，次元和 A A A 一樣
3. R R R 儲存

2.6 帶列轉置的 QR 分解

A P = Q R AP=QR AP=QR A = Q R P T A=QRP^T A=QRPT

2.7 相關函數說明

參見：GSL 系列 6 — 線性代數 3 — QR 分解

3 LQ 分解

3.1 相關符号

L L L: 下三角（梯形）矩陣

3.2 LQ 分解

A = L Q A=LQ A=LQ

其中： L : M × N          Q : N × N L:M\times N\;\;\;\;Q:N\times N L:M×NQ:N×N

3.3 應用

LQ 分解一般可以用來求亞定方程 ( M ≤ N M\le N M≤N) 的最小範數解

3.4 相關函數

參見：GSL 系列 6 — 線性代數 4 — LQ 分解