線性方程組求解演算法

1. 線性方程組的解法

高斯消元法（Gaussian Elimination）這種演算法，最早記錄於中國的《九章算術》。對於歐洲而言，則是牛頓最早發現了此種方法。不過直到高斯於1810年的發明，此演算法才被廣為接受。故而該演算法在數學界被稱為高斯消元法。

高斯消元法的核心包括三點。

（1）方程組中兩個方程的位置互換，方程的解不變

（2）方程組中的某個方程乘以非零數 k，方程的解不變

（3）方程組的某個方程乘以非零數 k，加上另一個方程，方程的解不變

我們將這三種變換，稱為線性方程組的變換。當然，變換的目的是為了消元（消減方程組中某些方程中未知數的個數），以達到最終求解方程組的目標，而不是無意識的隨機變換。比如線性方程組：

2. 線性方程組的解有哪些規律

D1就是把D中的第1列的數, 換成方程組等號右邊的數。

D2就是把D中的第2列的數, 換成方程組等號右邊的數。

克萊姆法則：是將方程組等式右側的向量，替換到系數矩陣的第幾行，得到新的行列式。

假若有n個未知數，n個方程組成的方程組： 克萊姆法則

a11X1+a12X2+．．．+a1nXn = b1

a21X1+a22X2+．．．+a2nXn = b2

an1X1+an2X2+．．．+annXn = bn

(2)線性方程組求解演算法擴展閱讀：

一般來說，用克萊姆法則求線性方程組的解時，計算量是比較大的。使用克萊姆法則求線性方程組的解的演算法時間復雜度依賴於矩陣行列式的演算法復雜度O(f(n))，其復雜度為O(n·f(n))，一般沒有計算價值，復雜度太高。. 對具體的數字線性方程組，當未知數較多時往往可用計算機來求解。用計算機求解線性方程組目前已經有了一整套成熟的方法。

3. 怎樣用LU分解法解線性方程組

Ax=B，改寫成Ly=B，Ux=y的方程組。就相當於將A=LU分解成了兩個矩陣。稱為矩陣A的三角分解，或LU分解。如果L為單位下三角陣，則叫Doolittle分解，若U為單位上三角陣，則叫Crout分解。只要A的各順序主子式不為零，則A可唯一分解成一個單位下三角陣L與一個上三角陣U的乘積。

•設Ax=b，A=LU，則Ax=LUx=b

於是令Ux=y，則Ly=b

這樣原來方程能化為兩個簡單方程組

在線性代數中， LU分解(LU Decomposition)是矩陣分解的一種，可以將一個矩陣分解為一個單位下三角矩陣和一個上三角矩陣的乘積（有時是它們和一個置換矩陣的乘積）。LU分解主要應用在數值分析中，用來解線性方程、求反矩陣或計算行列式。

(3)線性方程組求解演算法擴展閱讀：

相關演算法：

LU分解在本質上是高斯消元法的一種表達形式。實質上是將A通過初等行變換變成一個上三角矩陣，其變換矩陣就是一個單位下三角矩陣。

這正是所謂的杜爾里特演算法：從下至上地對矩陣A做初等行變換，將對角線左下方的元素變成零，然後再證明這些行變換的效果等同於左乘一系列單位下三角矩陣，這一系列單位下三角矩陣的乘積的逆就是L矩陣，它也是一個單位下三角矩陣。這類演算法的復雜度一般在(三分之二的n三次方) 左右。

4. 高斯消元法解線性方程組

高斯消元法解線性方程組如下：

高斯消元法，是線性代數中求解線性方程組的一種演算法。它通常被理解為在相應的系數矩陣上執行的一系列操作。要對矩陣執行行縮減，可以使用一系列基本行操作修改矩陣，直到矩陣的左下角盡可能地用零填充。

基本行操作有三種類型:

交換兩行

將一行乘以一個非零數字

將一行的倍數添加到另一行

運用以上方法作，一個矩陣總是可以被轉換成一個上三角矩陣，實際上是一個行階梯形。一旦所有的主系數(每一行中最左邊的非零項)都為1，並且包含主系數的每一列在其他地方都為零，這個矩陣就稱為行簡化階梯形。最終的形式是獨特的;換句話說，它與所使用的行操作序列無關。

例如，在接下來的行運算序列中(每一步可能進行多個初等運算)，第三和第四個矩陣是行簡化階梯形矩陣，最終的矩陣是唯一的行簡化階梯形矩陣。

一旦y也從第三行中刪除，結果是三角形形式的線性方程組，因此演算法的第一部分完成。從計算的角度來看，以相反的順序求解變數更快，這一過程被稱為反向替換。人們看到的解決辦法是z= 1,y= 3，和x= 2。所以原始方程組有唯一的解。

第二列描述了剛剛執行了哪些行操作。所以第一步x從...中消除L2通過添加 3 / 2 L一到L2。接下來，x從...中消除L3通過添加L一到L3。