Tag Archives: 高斯消去法

翻轉 LU 分解

Posted on 02/09/2017 by ccjou

本文的閱讀等級：初級 愛因斯坦說[1]：「邏輯可以將你由 A 點帶到 B 點，想像則可以帶你到任何地方。」在我想像的翻轉課堂，學生會先在家裡觀看交大出版社發行的線性代數《教學光碟》，沒有購買光碟的學生則到學校圖書館觀看。在教室的時間，學生跟老師一起交流互動，我們經常以問答方式討論課程內容，但學生與老師的角色對調。底下抄錄一段關於 LU 分解的對話，大家可以體驗翻轉課堂的學習情境。

Posted in 線性方程, 線性代數專欄 | Tagged , , | Leave a comment

高斯消去法與高斯─約當法的運算量

Posted on 08/12/2014 by ccjou

本文的閱讀等級：初級 高斯消去法 (Gaussian elimination) 是當今普遍用於解線性聯立方程組的演算法。高斯─約當法 (Gauss-Jordan method) 是高斯消去法的一種變形，主要應用於計算逆矩陣。關於這兩個算法的詳細介紹，請見“高斯消去法”和“高斯─約當法”，本文僅討論它們耗費的運算量。

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

別再算逆矩陣了

Posted on 06/19/2014 by ccjou

本文的閱讀等級：初級 不知道從甚麼時候開始，“三階逆矩陣公式”經常雄踞本站「近期最多人點閱」表單的榜首，每日點閱該文的次數少則幾十，多則上百，下圖是過去一年的瀏覽次數統計 (主要的峰值所在的日期大致與台灣高等院校春秋二季期中和期末考試相吻合)。對於所見的逆矩陣風潮，我感到相當困惑：究竟出於甚麼樣的動機眾多年輕讀者願意不辭勞苦求算 (三階) 逆矩陣？如果尋覓逆矩陣公式的行動單純源於人類天生想要探索未知世界的好奇心，那我沒甚麼意見。不過，倘若只因為要解線性方程而計算逆矩陣，我可就忍不住要奉勸諸位：「省點力氣，別再算逆矩陣了！」

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

利用 Bareiss 算法判別正定矩陣

Posted on 01/14/2014 by ccjou

本文的閱讀等級：中級 若 為一 階實對稱矩陣且任一 維非零實向量 滿足 ，則 稱為正定矩陣 (見“特殊矩陣 (6)：正定矩陣”)。如果 為一 Hermitian 複矩陣，將上述實向量改成複向量，轉置 替換為共軛轉置 即可。正定矩陣有多種判別方式，當下列任一條件成立時， 是正定矩陣 (見“正定矩陣的性質與判別方法”)： 的特徵值皆為正數； 的軸元 (pivot) 皆為正數； 的領先主子陣 (leading principal submatrix) 的行列式皆為正數； 可分解為 ，其中 是一可逆矩陣。 本文介紹一個基於領先主子陣的行列式的正定矩陣判別法，稱為 Bareiss 算法[1]。在開始討論前，我們先說明本文所使用的子陣表達記號。令 代表 階矩陣 的一個 階子陣，其中 是列 (row) 指標集合， 是行 … Continue reading →

Posted in 線性代數專欄, 行列式 | Tagged , , , , | Leave a comment

線性獨立向量集的判定與算法

Posted on 11/19/2013 by ccjou

本文的閱讀等級：初級 令 為一個向量空間。給定向量集合 ，，若僅存在唯一的數組 使得 ， 我們稱 是線性獨立的或線性無關的 (linearly independent)，否則稱之為線性相關的或線性相依的 (linearly dependent)。線性獨立集不具有線性相關性，而線性相關集中至少有一個向量可表示為其餘向量的線性組合 (見“線性獨立俱樂部”)。假設 且 為 的一組基底。任一向量 與其參考基底 的座標向量 有一對一的對應關係 (見“同構的向量空間”)。具體地說，若 ，則 。為裨益矩陣運算，我們可以將每一 用座標向量 表示。底下討論針對座標映射後的幾何向量空間 。如欲延伸至 ，將轉置 改成共軛轉置 即可。   對於 ，其中 ，本文探討底下三個問題： 如何判定 是否為一個線性獨立集？ 如何從 挑選出最大的線性獨立子集？也就是說，該線性獨立子集包含最多的向量？ 如何增添向量至 的最大線性獨立子集使之成為 的一組基底？

Posted in 線性代數專欄, 向量空間 | Tagged , , , , , , | Leave a comment

定常迭代法──線性方程的數值解法

Posted on 08/22/2013 by ccjou

本文的閱讀等級：中級 高斯消去法是當今最常被使用的線性方程解法 (見“高斯消去法”)，它是一種直接法，即一次性地解決問題。對於一個 階方陣，高斯消去法耗用的運算量是 。如果我們面對的是一個大型的稀疏矩陣，這時可用迭代法來求解。所謂迭代法是指從一個初始估計值出發，尋找一系列近似解以期解決問題的方法。大致上，應用於解線性方程的迭代法可區分為兩類：定常迭代法 (stationary iterative method) 和 Krylov 法。定常迭代法相對古老，容易瞭解與實現，惟效果通常不佳。Krylov 法相對年輕，雖然較不易理解分析，但效果普遍優異。本文介紹定常迭代法，並討論其中三種主要方法。

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

牛頓法──非線性方程的求根方法

Posted on 07/08/2013 by ccjou

本文的閱讀等級：初級 牛頓法 (Newton’s method) 或稱牛頓─拉弗森法 (Newton-Raphson method) 是一個極有效的非線性方程 的求根方法。令 為一個連續可導函數。設 為 的一根的估計值，寫出泰勒級數 。 如果 足夠小，我們可以忽略截斷 (truncated) 誤差 。解線性方程 可得近似根： 。 上式的幾何意義是 為函數 於點 的切線與x-軸的交點。我們期待 比 更接近真實根，遂以迭代程序連續逼近：對於 ， 。

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

答JERRY──關於相似變換矩陣的解法

Posted on 05/23/2013 by ccjou

網友JERRY留言： 已知 和 是二階方陣，怎麼找 使得 ？   答曰： 我們先舉一些例子看會發生何種情況。若 ，其中 是單位矩陣，則任一可逆矩陣 皆為解，因為 。若 ，則所有非零純量矩陣 ，，皆滿足要求，因為 。如果 使得 ，則對於任何 ，都有 。換句話說，當 是一致時 (即存在解)，必有無窮多組解。另一方面， 是否可能無解？是的。例如，，，則 。針對任意二階方陣 和 ，下面介紹兩種 的解法：線性方程與對角化。

Posted in 特徵分析, 答讀者問 | Tagged , , | Leave a comment

高斯消去法

Posted on 02/20/2013 by ccjou

本文的閱讀等級：初級 解線性方程組是線性代數處理的核心問題之一。考慮包含 個未知數 的線性方程式 ， 其中係數 與 是給定的純量 (實數或複數)。若線性方程組有 個方程式，則可表示為陣列形式： 線性方程組的解 必須滿足上面 個方程式，也就是說方程組的解是 個方程式各自解的交集。線性方程組的系統化解法最早出現於公元前100年的中國古籍《九章算術》(見“《九章算術》的方程術”)，隨後傳入日本和歐洲。今天，我們稱此算法為高斯消去法或高斯消元法 (Gaussian elimination) 以紀念德國數學家高斯 (Carl Friedrich Gauss) 的廣泛使用故而推廣了這個方法。

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

利用高斯消去法計算特徵值與特徵向量

Posted on 12/12/2012 by ccjou

本文的閱讀等級：初級 很久很久以前，在一所大學的教室裡，年邁的老教授講解完高斯消去法於求解線性方程的應用，猛地發現台下學生大多已睡成一團。老教授從講義夾抽出一頁泛黃的單行紙，在黑板上抄寫了一個 階矩陣 。 隨後他喚醒眾生，聲音嘶啞地說道：「同 (讀音“統”) 學們，現在用你們剛學過的高斯消去法找出滿足 的純量 和非零解 。」語畢，老教授慈祥地望著這群或沉思默想，或奮筆疾書的年輕學子，諾大的教室頓時出奇地安靜。

Posted in 特徵分析, 線性代數專欄 | Tagged , , , , , | 1 Comment