Category Archives: 仿射幾何

答William──關於凸包的映射問題

網友William留言: 老師,您好!我不是您的學生,但是又有一個問題苦無解決辦法,因此想向老師尋求協助。問題是這樣的:群組A內有 ,,五個點。其中 ,,, 為一矩形的四個端點,而 位於矩形的範圍內或邊線上。群組B內有 ,,五個點。現在假設存在一張對應表: 查表後的值為 ,,求 查表後的值 ,並以 ,,和 ,,表示。我不知道這個問題是否適合由線性代數解決,也不曉得應該從那裡下手。懇請老師提供意見。謝謝。 Advertisements

Posted in 答讀者問, 仿射幾何 | Tagged , , , , | Leave a comment

保長、保角與共形映射

本文的閱讀等級:中級 令 為一 階實矩陣。我們可以將 視為一個從幾何向量空間 映至 的線性變換:,其中 。如果線性變換 不改變向量長度,則 稱為保長 (length-preserving) 映射或等距同構 (isometry)。保長映射 有下列等價的定義方式 (見“等距同構與么正矩陣”): 是一實正交矩陣 (orthogonal matrix),即 。 對於每一 ,。 對於任何 ,。 對於任何 ,。 保長映射的定義條件相當嚴苛,我們可以將它稍微放鬆。兩個實向量 和 的內積定義為 (見“內積的定義”) , 其中 是 和 的夾角。對於任意非零向量 ,若線性變換 不改變 和 的夾角,也就是說, , 則 … Continue reading

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

凸優化──凸函數的最小化

本文的閱讀等級:中級 凸優化 (convex optimization) 是最佳化理論的一個分支。顧名思義,凸優化探討定義於一個凸集的凸函數最小化問題[1]。令 為凸集且 為凸函數。我們的目標要找出一個點 ,使得每一 滿足 。在最佳化理論中, 稱為可行域 (feasible set), 稱為目標函數, 稱為全域最佳解[2]。任一凸優化問題皆可表示為下列標準型: 其中 是凸函數, 是仿射函數,即 ,,。最小平方法與線性規劃是兩種常見的凸優化問題。令 為一個 階實矩陣, 為 維實向量, 為 維實向量。最小平方法是一個無約束 (unconstrained) 最佳化問題: 。 線性規劃標準型問題具有下列形式 (見“線性規劃 (一):標準型問題”): 本文介紹凸優化的一個重要性質:任一局部最佳解 (亦稱相對最佳解) 即為全域最佳解。所謂局部最佳解 是指存在 使得集合 中每一點 滿足 。

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

凸函數

本文的閱讀等級:中級 令 為一個非空凸集,也就是說,給定任意兩點 和 ,點 屬於 (見“凸組合、凸包與凸集”)。凸函數 (convex function) 是一個實函數 滿足下列性質:對於任意 且 , 。 若定義式等號僅發生於 和 ,我們稱 是一個嚴格凸函數。相反的,若 是一個 (嚴格) 凸函數,則 稱為 (嚴格) 凹函數。圖一顯示一個單變量凸函數 ,任一弦 (連結點 和 的紅色線段) 必位於函數 (藍色曲線) 的上方。下面列舉一些單變量凸函數:,, 和 。對於 ,仿射函數 和向量 -範數 ,,都是凸函數 (見“向量範數”)。本文將討論凸函數的一些性質和判別方法。

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

多胞形

本文的閱讀等級:中級 在最佳化領域,多胞形 (polytope) 是一種應用廣泛的特殊凸集[1]。多胞形可以存在於任何有限維的幾何座標空間,多邊形是二維多胞形,多面體是三維多胞形, 的多胞形稱為 多胞形。淺白地說,多胞形的邊界都是平的。本文討論的多胞形限定為有界閉集,定義如下:若 是屬於 的有限向量集,凸包 稱為一多胞形。因為凸包是凸集,凸包定義的多胞形自然是一有界閉凸集 (見“凸組合、凸包與凸集”)。本文將介紹多胞形的幾何性質,並推導有界閉凸集的一個重要定理,它指引了一條解決線性規劃問題的捷徑。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , | Leave a comment

超平面

本文的閱讀等級:初級 在最佳化與機器學習領域,譬如線性規劃、線性判別分析 (linear discriminant analysis)、Logit 模型 (logistic regression) 和多層類神經網路 (multilayer network),超平面 (hyperplane) 是一個常見的模型元件。許多最佳化方法,如梯度下降法、Lagrange 乘數法和對偶理論,也都與超平面有關。本文從幾何與代數兩種觀點介紹超平面的基礎知識,並以凸集為例說明超平面於分割向量空間的應用 (見“凸組合、凸包與凸集”)。

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

凸組合、凸包與凸集

本文的閱讀等級:初級 幾何座標空間 的一個向量 表示該向量端點的座標。點與座標向量具有一對一的對應關係,因為這個緣故,我們經常以座標向量代表點。本文介紹一種別於子空間與仿射空間 (子空間的平移) 的向量集。我們稱一個向量集 是凸集 (convex set),若給定任兩點 和 ,點 屬於 。淺白地說,在凸集中,任兩個點皆可「看見」彼此,連接這兩點的直線段不含集合以外的點。見圖一的例子。比較特別的是, 所包含的子空間與仿射空間都是凸集。

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

仿射獨立

本文的閱讀等級:初級 考慮 中三向量 。如果存在不全為零的組合權重 使得 , 我們稱向量集 線性相關 (否則稱為線性獨立),這時候其中一個向量可以表示為其他二向量的線性組合。若 的端點 (向量代表點座標) 位於同一直線上,則其中一向量為其他二向量的仿射組合 (見“仿射組合與仿射空間”)。設 , 其中 。將上式改寫為 , 可知 不僅線性相關,且組合權重之和等於零。這個結果引出下面的定義:對於 ,若存在不全為零的實數 使得 , 並滿足 ,我們稱向量集 仿射相關 (affine dependent),否則稱為仿射獨立 (affine independent)。以下討論限定於幾何向量空間 。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , | 1 Comment

仿射組合與仿射空間

本文的閱讀等級:初級 考慮線性方程 ,所有可能的解稱為通解,具有下列形式: , 其中特解 是指滿足 的任一解,齊次解 則滿足 。除非齊次解僅包含平凡解 ,否則特解和齊次解皆不唯一,故通解有無窮多種表達式。見下例: 的通解可以表示為 , 上式中, 是任意實數,改變 數值即產生新的特解 ,齊次解則為 。幾何空間向量可用其端點表示,上例通解 (即所有特解構成的集合) 是 中一不穿越原點的直線,故不為子空間 (任一子空間必定包含原點)。另一方面,所有的齊次解都位於穿越原點的平行直線上,此即 的零空間 (見“Ax=b 和 Ax=0 的解集合有什麼關係?”)。所以,通解與齊次解之間具有點對點的平移關係,而該平移量可以是任一滿足線性方程的特解 。通解、特解和齊次解之間的關係常令學者感到困惑,本文介紹兩個新概念──仿射組合與仿射空間,希望藉此得以釐清特解和齊次解的幾何意義。

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

仿射投影

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

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