介紹一種求解線性方程組的算法-高斯消除法

啊，我終于可以寫(xiě)文章了！最近兩天好累哇，先繼續(xù)寫(xiě)上面的算法文章。

這篇文章寫(xiě)的算法是高斯消元，是數(shù)值計(jì)算里面基本且有效的算法之一：是求解線性方程組的算法。

這里再細(xì)寫(xiě)一下：

在數(shù)學(xué)中，高斯消元法，也稱(chēng)為行約簡(jiǎn)，是一種求解線性方程組的算法。它由對(duì)相應(yīng)的系數(shù)矩陣執(zhí)行的一系列操作組成。此方法還可用于計(jì)算矩陣的秩、方陣的行列式和可逆矩陣的逆矩陣。該方法以卡爾·弗里德里希·高斯 ( Carl Friedrich Gauss ，1777-1855)的名字命名，盡管該方法的一些特例——盡管沒(méi)有證明——早在公元 179 年左右就為中國(guó)數(shù)學(xué)家所知。

為了對(duì)矩陣執(zhí)行行縮減，可以使用一系列基本行操作來(lái)修改矩陣，直到矩陣的左下角盡可能地用零填充。基本行操作分為三種類(lèi)型：

1.交換兩行，

2.將一行乘以一個(gè)非零數(shù)，

3.將一行的倍數(shù)添加到另一行。（減法可以通過(guò)將一行乘以 -1 并將結(jié)果添加到另一行來(lái)實(shí)現(xiàn)）

使用這些操作，矩陣總是可以轉(zhuǎn)換為上三角矩陣，實(shí)際上是行梯形矩陣。一旦所有前導(dǎo)系數(shù)（每行中最左邊的非零條目）都為 1，并且包含前導(dǎo)系數(shù)的每一列在其他地方都為零，則稱(chēng)該矩陣為簡(jiǎn)化行梯形形式。這種最終形式是獨(dú)一無(wú)二的；換句話說(shuō)，它與所使用的行操作序列無(wú)關(guān)。例如，在下面的行操作序列中（在第一步和第三步對(duì)不同行進(jìn)行兩個(gè)基本操作），第三和第四個(gè)矩陣是行梯形矩陣，最后一個(gè)矩陣是唯一的簡(jiǎn)化行梯隊(duì)形式。

一個(gè)矩陣的簡(jiǎn)化

使用行操作將矩陣轉(zhuǎn)換為簡(jiǎn)化的行梯形形式有時(shí)稱(chēng)為Gauss-Jordan 消元法。在這種情況下，術(shù)語(yǔ)高斯消元是指過(guò)程，直到它達(dá)到其上三角形或（未簡(jiǎn)化的）行梯形形式。出于計(jì)算原因，在求解線性方程組時(shí)，有時(shí)最好在矩陣完全約簡(jiǎn)之前停止行操作。

我們對(duì)其實(shí)現(xiàn)的操作只有這三個(gè)

如果矩陣與線性方程組相關(guān)聯(lián)，則這些操作不會(huì)更改解集。因此，如果一個(gè)人的目標(biāo)是求解線性方程組，那么使用這些行操作可以使問(wèn)題變得更容易。

對(duì)于矩陣中的每一行，如果該行不只包含零，則最左邊的非零條目稱(chēng)為該行的前導(dǎo)系數(shù)（或樞軸）。因此，如果兩個(gè)前導(dǎo)系數(shù)在同一列中，則可以使用類(lèi)型 3的行操作使這些系數(shù)之一為零。然后通過(guò)使用行交換操作，總是可以對(duì)行進(jìn)行排序，以便對(duì)于每個(gè)非零行，前導(dǎo)系數(shù)位于上一行的前導(dǎo)系數(shù)的右側(cè)。如果是這種情況，則稱(chēng)矩陣為行梯形. 所以矩陣的左下部分只包含零，并且所有的零行都在非零行的下方。這里使用“梯隊(duì)”一詞是因?yàn)榭梢源致缘卣J(rèn)為行是按大小排列的，最大的位于頂部，最小的位于底部。

例如，下面的矩陣是行梯形的，它的前導(dǎo)系數(shù)用紅色表示：

就像這樣

它是梯形的，因?yàn)榱阈性诘撞?，第二行（第三列）的領(lǐng)先系數(shù)在第一行（第二列）的領(lǐng)先系數(shù)的右側(cè)。

如果矩陣的所有前導(dǎo)系數(shù)都等于 1（這可以通過(guò)使用類(lèi)型 2 的基本行操作來(lái)實(shí)現(xiàn)），并且在包含前導(dǎo)系數(shù)的每一列中，則稱(chēng)矩陣為簡(jiǎn)化行梯形。該列中的其他條目為零（可以通過(guò)使用類(lèi)型 3 的基本行操作來(lái)實(shí)現(xiàn)）。

假如我們求解這個(gè)方程的解

下表是同時(shí)應(yīng)用于方程組及其相關(guān)增廣矩陣的行縮減過(guò)程。在實(shí)踐中，通常不會(huì)用方程來(lái)處理系統(tǒng)，而是使用更適合計(jì)算機(jī)操作的增廣矩陣。行縮減過(guò)程可以概括如下：從L1以下的所有方程中消除x，然后從L2以下的所有方程中消除y。這將使系統(tǒng)變成三角形。然后，使用反向替換，可以解決每個(gè)未知數(shù)。

就好像這樣

其實(shí)還有內(nèi)容，但是公式編輯實(shí)在不會(huì)哇，這里給出程序的偽代碼：

高斯消元法將給定的m × n矩陣A轉(zhuǎn)換為行梯形矩陣。

在下面的偽代碼中，A[i, j]表示矩陣A在第i行和第j列中的條目，索引從 1 開(kāi)始。轉(zhuǎn)換在原地執(zhí)行，這意味著原始矩陣丟失，最終被其行梯形形式替換。

看不懂？沒(méi)有關(guān)系，大致懂就行

程序的實(shí)現(xiàn)上面，我們導(dǎo)入這些內(nèi)容

為了精度，導(dǎo)入float64

以及導(dǎo)入的一個(gè)N維的數(shù)組，在內(nèi)部是所以ndarray封裝的

這樣學(xué)習(xí)的態(tài)度是不對(duì)的，我們需要看看Numpy文檔寫(xiě)的：

64位精度浮點(diǎn)數(shù)類(lèi)型：符號(hào)位、11位指數(shù)、52位尾數(shù)。

沒(méi)關(guān)系，你不懂的官網(wǎng)文檔滿足你

NDarray在這里

可在運(yùn)行時(shí)用于鍵入具有給定 dtype 和未指定形狀的數(shù)組。

系數(shù)矩陣，向量是輸入的參數(shù)，后面是返回的數(shù)據(jù)類(lèi)型。

對(duì)shape函數(shù)感興趣不，內(nèi)部是這樣的

這個(gè)也是注解的寫(xiě)法，意思是返回一個(gè)數(shù)組，用0填充：

zeros函數(shù)的樣子

第一個(gè)參數(shù)，元組，說(shuō)明樣子。后面參數(shù)是類(lèi)型，這里寫(xiě)float。返回值是具有給定形狀、數(shù)據(jù)類(lèi)型和順序的零數(shù)組。

首先，reversed 函數(shù)返回一個(gè)反轉(zhuǎn)的迭代器。這個(gè)為什么倒著算呢？是因?yàn)榈怪銓?duì)算法來(lái)講有一些優(yōu)點(diǎn)。

內(nèi)部再套一個(gè)函數(shù)，內(nèi)部對(duì)列處理，下面的代碼就是實(shí)現(xiàn)使用倍數(shù)的關(guān)系對(duì)一整行處理，[]是相當(dāng)于數(shù)組的index寫(xiě)法，下面是將處理結(jié)果應(yīng)用到行，最后打印X。

上面這個(gè)函數(shù)是高斯函數(shù)的一個(gè)子函數(shù)，作用是給出最簡(jiǎn)的階梯行列式。

我們要算這個(gè)

輸入的時(shí)候這樣輸入，先別繼續(xù)看，我們看高斯分解

這個(gè)檢查寫(xiě)的很簡(jiǎn)單

接下來(lái)

連接我們的矩陣，要求有相應(yīng)的形狀

這個(gè)例子不錯(cuò)

0是按照行展開(kāi)，1是列，None是直接接龍。

這段實(shí)現(xiàn)的是上面的偽代碼

一個(gè)很有趣的變量名

調(diào)用的時(shí)候就是這樣，輸入一個(gè)大元組，里面有兩個(gè)小元組

審核編輯：劉清