Tag Archives: 高斯消去法

《九章算術》的方程術

本文的閱讀等級:初級 《九章算術》是中國最古老的數學典籍之一,成書約於公元前100年,匯集了周朝以來的古代數學知識[1]。全書以問題集形式編纂,共收錄246個問題;在一個或數個問題之後,列出解答與對應解法,但沒有證明。這些問題按性質與解法分為九大類:方田、粟米、衰分、少廣、商功、均輸、盈不足、方程、勾股。今天我們使用的「方程」一詞即源自卷八章名。方程章專門討論線性方程組,共計18題,其中第一個問題給出完整的解法,稱為「方程術」,抄錄於下[2]: 方程:今有上禾三秉,中禾二秉,下禾一秉,實三十九斗;上禾二秉,中禾三秉,下禾一秉,實三十四斗;上禾一秉,中禾二秉,下禾三秉,實二十六斗。問上、中、下禾實一秉各幾何? 答曰:上禾一秉,九斗、四分斗之一,中禾一秉,四斗、四分斗之一,下禾一秉,二斗、四分斗之三。 術曰:置上禾三秉,中禾二秉,下禾一秉,實三十九斗,於右方。中、左禾列如右方。以右行上禾遍乘中行而以直除。又乘其次,亦以直除。然以中行中禾不盡者遍乘左行而以直除。左方下禾不盡者,上為法,下為實。實即下禾之實。求中禾,以法乘中行下實,而除下禾之實。餘如中禾秉數而一,即中禾之實。求上禾亦以法乘右行下實,而除下禾、中禾之實。餘如上禾秉數而一,即上禾之實。實皆如法,各得一斗。

Posted in 線性方程, 線性代數專欄 | Tagged , , | 13 Comments

答林容麟──關於座標變換矩陣的快捷算法

網友林容麟留言: 周老師您好。在 2010/02/problem-set-7-2010 的練習題的第一題(c),要找出 change-of-coordinates matrix from basis to ,請問一下這個矩陣的係數是要怎麼找比較快,像這題答案是 ,那麼若題目的基底(basis)包含4個向量,解出 階 change-of-coordinates matrix 不是很費時嗎?謝謝~   答曰: 我將原問題符號稍做更改,抄錄於下:設 空間中子空間 有兩組 (有序) 基底: 。 求從基底 至基底 的座標變換矩陣 (change-of-coordinates matrix),記為 。

Posted in 答讀者問, 線性變換 | Tagged , , | Leave a comment

PA=LU 分解

本文的閱讀等級:中級 令 是一個 階可逆矩陣。LU 分解 是高斯消去法的一種表達形式,下三角矩陣 記錄消元過程使用的乘數,上三角矩陣 儲存約化結果,其中 和 的主對角元分別滿足 和 (見“LU 分解”)。不過,並非每一可逆矩陣都存在 LU 分解。在執行高斯消去法的化簡程序中,若 出現在軸元 (pivot) 位置,即 元,列取代運算便無法消去軸元底下各元,這時標準 LU 分解不復存在。可逆矩陣 的軸元總數 (即 ) 等於 ,透過列交換運算必能獲得一個 (非零) 軸元,所以仍可繼續下一階段的化簡步驟。從實際面來看,縱使未發生「零軸元」的情況 (軸元所在位置為零),為了避免因不當使用消去法而引發災難,部分軸元法 (partial pivoting) 也會適時地交換列 (見“特殊矩陣 (12):對角佔優矩陣”)。見下例 (取自[1]): 。 從 同時包含數值很小和很大的主對角元可知 不具數值穩定性,也就是說,標準 LU … Continue reading

Posted in 線性方程, 線性代數專欄 | Tagged , , , , | 9 Comments

無相互作用的矩陣積

本文的閱讀等級:初級 考慮下列 矩陣: 。 矩陣 共有 種排列方式,因此產生 6 個矩陣積,即 , 其中 未產生 項,我們稱這些矩陣乘積無「相互作用」(interaction)。本文要探討的問題是:無相互作用的矩陣積必須滿足何種矩陣排列規則?

Posted in 線性方程, 線性代數專欄 | Tagged , , , | 2 Comments

行空間與零空間的互換表達

本文的閱讀等級:初級 對於一 階實矩陣 ,行空間 (column space) 乃 的行向量於 中擴張而成的子空間: 零空間 (nullspace) 則是齊次方程 所有解形成的一個屬於 的子空間: 在一般情況下,矩陣行空間採用明確的 (explicit) 建構式 (即擴張) 定義,而零空間則以隱含的 (implicit) 限制條件 (即線性方程組) 來定義。本文探討如何運用簡約列梯形式 (reduced row echelon form) 解決下面兩個子空間互換表達問題:給定 ,將零空間 表示成明確的向量集擴張,也就是說,求矩陣 使得 ;另一方面,行空間 也可以表示為隱含的限制條件,亦即求矩陣 使得 。

Posted in 線性代數專欄, 向量空間 | Tagged , , , , , | 9 Comments

LU 分解

本文的閱讀等級:初級 令 為一個 階矩陣。LU 分解是指將 表示為兩個 階三角矩陣的乘積 , 其中 是下三角矩陣, 是上三角矩陣,如下例, 。 LU 分解的本質是高斯消去法的一種表達形式,矩陣 記錄消去法化簡 的過程,而矩陣 則儲存化簡結果 (見“高斯消去法”)。LU 分解的外表看似平淡無奇,但它可以用來解線性方程,逆矩陣和計算行列式,堪稱是最具實用價值的矩陣分解式之一。

Posted in 線性方程, 線性代數專欄 | Tagged , , , , | 15 Comments

秩分解──目視行秩等於列秩

本文的閱讀等級:初級 矩陣的行空間的維數稱為行秩 (column rank),列空間的維數稱為列秩 (row rank)。子空間的維數由最大的線性獨立的向量數決定,“行秩=列秩”一文曾基於此性質通過操作矩陣乘法運算證明了矩陣的行秩等於列秩。證明歸證明,讀者心中可能依然困惑:「矩陣的線性獨立行向量數怎麼會恰好等於線性獨立的列向量數呢?」本文再提供一個論證,想法很簡單:利用高斯消去法挑選出矩陣的線性獨立行與列,並以一個特殊分解式呈現獨立行與獨立列。這個證明屬計算導向,雖未直接表達行秩等於列秩的幾何特性,但由所得的矩陣分解式我們可以「目視」原矩陣的行空間和列空間,兩者確實擁有相等的基底向量數。

Posted in 線性代數專欄, 向量空間 | Tagged , , , , , , , , | 2 Comments

每週問題 April 5, 2010

本週問題是從高斯消去法使用的基本矩陣重現原矩陣的行空間。 點選問題↓ Pow-April-5-10 參考解答↓ PowSol-April-5-10

Posted in pow 向量空間, 每週問題 | Tagged , , , | Leave a comment

特殊矩陣 (12):對角佔優矩陣

本文的閱讀等級:初級 如果一 階矩陣 每一列 (row) 的主對角元的絕對值大於該列非主對角元絕對值之和,也就是說,對於 , , 我們稱 為嚴格對角佔優 (strictly diagonally dominant)。若每一 滿足 ,則稱為非嚴格對角佔優。例如, 是嚴格對角佔優矩陣因為

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , | 4 Comments

可逆矩陣定理

本文的閱讀等級:初級 可逆矩陣定理貫穿線性代數的許多重要主題,如線性方程、線性獨立、向量空間、行列式、特徵值和奇異值;不論準備考試或自我充實,可逆矩陣定理好比「線代雞湯」是極佳的觀念複習濃縮菁華。本文解釋部分陳述並說明常用的推論路徑,並未給出可逆矩陣定理的完整證明。

Posted in 線性代數專欄, 二次型 | Tagged , , , | 3 Comments