Tag Archives: 仿射投影

Kaczmarz 算法

本文的閱讀等級:中級 Kaczmarz 算法是線性方程 的一種迭代解法,1937年由波蘭數學家科區馬茲 (Stefan Kaczmarz) 所提出[1]。1970年,戈登 ( Richard Gordon)、本德爾 (Robert Bender) 和赫爾曼 (Gabor Herman) 三人重新發現此法,稱之為代數重建技術 (algebraic reconstruction technique),主要應用於電腦斷層掃描的影像重建[2]。我們以包含兩個未知數和兩個方程式的線性方程組 說明 Kaczmarz 算法的基本原理。考慮 , 其中係數 和常數 是實數。當係數矩陣可逆時,線性方程的解為下列兩個超平面 (此例為 平面的二直線) 的交點: 見下圖,給定任一初始點 ,連續交互正交投影至超平面 和 可得一向量序列 ,。當 ,,此即 的解。 Advertisements

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , | 3 Comments

Lagrange 乘數法

本文的閱讀等級:中級 約束最佳化 (constrained optimization) 是指在一個或多個束縛條件下,尋找一個多變數函數的極值 (極大值或極小值)。舉例來說,我們希望得到 的極小值,但前提是 與 必須滿足束縛條件 。最直截了當的作法是解出束縛條件,如此 可表示為 的函數,譬如 。將上式代入 可得單變數函數 ,求導並設為零即得極值的必要條件 。這個方法的主要缺點在於束縛條件未必存在代數解,也就是說 無法寫成 的函數。此外,當變數的數量增多或有多個束縛條件時,縱使能夠得到代數解,無約束目標函數的表達式也可能相當複雜。與上述作法比較,拉格朗日乘數法 (method of Lagrange multipliers) 或稱未定乘數法 (undetermined multipliers) 不須解出束縛條件,因而保留了變數之間的對稱性。由於兼具簡單與典雅兩個優點,Lagrange 乘數法是目前最常被使用的一種求解約束最佳化方法:令 Lagrangian 函數為 , 其中 稱為 Lagrange 乘數。計算 對所有變數的偏導數並設為零: , 這個方程組即為最佳解的必要條件。本文採用較富直覺的幾何觀點解說 Lagrange 乘數法的基本原理,預備知識包括正交補餘和正交投影 (見“正交補餘與投影定理”)。

Posted in 特別主題 | Tagged , , , , , | 8 Comments

仿射投影

本文的閱讀等級:中級 令 為一個有限維內積空間。考慮 的平移變換 , 其中 是一個非零向量。平移變換 並非線性變換,而是一個仿射變換 (見“仿射變換”)。設 為 的一個子空間, 自原點平移 後所構成的集合稱為仿射空間 (affine space),表示為 。 除非 ,否則 不包含零向量,因此 不是 的子空間。雖然如此,在仿射空間中仍可以實現正交投影,這篇短文解說如何將一般子空間投影轉換至仿射空間投影,另外並介紹一個基於最佳化理論的計算方法。(本文源於網友 Liang Dai 留言,以下的例子也是由他所提供。)

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , , , | 4 Comments