2.1 高斯消元法求解線性方程組

有多個變量，且每個變量的次數均為一次的方程組成的方程組被稱為線性方程組，其形式為：

高斯消元法求解線性方程組的基本思想是通過一系列的加減消元運算得到類似kx=b的式子，然后逐一回代求解x向量。例如，給出線性方程組如下：

首先，進行消元。

將(1)除以3，把x1的系數化為1，得方程(1)′：。再令(2)-2×(1)′，(3)-4×(1)′，則將方程(2)和(3)中的x1消去，得線性方程組如下：

再將(2)'除以2/3，把x2的系數化為1，得方程(2)″：x2+2x3=0。再令(3)′-(-14/3)×(2)″，則將方程(3)′的x2消去，得線性方程組如下：

則由(3)″得，x3=-1。

然后，進行回代，由(2)″得，x2=2；再由(1)′得，x1=1。

線性方程組用矩陣形式表示如下：

，簡記為Ax=b。

采用高斯消元法，構造增廣矩陣B=(A|b)，然后對B進行矩陣的初等行變換，直至A變為上三角矩陣。以上述的線性方程組為例，首先，對增廣矩陣B進行矩陣的初等行變換，直至A變為上三角矩陣：

然后回代，得解：。

對增廣矩陣采用消元法，當消元完畢后，如果有一行系數項都為0，但是常數項不為0，則對應的線性方程組無解。例如有，則對應的線性方程組無解。

當消元完畢后，如果有多行的系數項和常數項均為0，則對應的線性方程組有多個解。例如有，則對應的線性方程組有多個解。有幾行全為0，就有幾個自由變量，即變量的值可以任取，有無數種情況可以滿足給出的線性方程組。

采用高斯消元法求解線性方程組浮點類型解的程序模板如下。在編程實現的過程中，對增廣矩陣進行矩陣的初等行變換，自上而下處理每一行，在處理第i行時，先選擇一個r≥i且絕對值最大的ari，然后交換第r行和第i行，即保證交換后的air不等于0。

采用高斯消元法求解線性方程組浮點類型解的標準程序段如下。

題目2.1.1和2.1.2是應用高斯消元法求解線性方程組的范例。

【2.1.1 Kind of a Blur】

當被拍攝物偏離出焦距以外時，就會造成失焦，導致成像模糊。對給出的模糊的原始圖像進行恢復是圖像處理中最有趣的課題之一。這一過程被稱為去模糊，這也是本題要完成的任務。

在本題中，所有的圖像都是灰色的（沒有顏色）。一個圖像表示為一個實數的二維矩陣，其中每個元素是對應像素的亮度。一個清晰的圖像被模糊化，就是將距離每個像素（包括該像素本身）的某個曼哈頓距離內（小于或等于）的所有像素的值取平均值，賦給這個像素。圖2.1-1所示是一個如何計算模糊距離為1的3×3圖像的模糊度的示例。

本題給出一幅圖像的模糊版本，要求恢復原始圖像。本題設定給出的圖像是模糊的，如上所述。

兩點之間的曼哈頓距離（也被稱為出租車距離）是它們坐標的絕對值的差的總和。

圖2.1-2所示的網格給出了與灰色單元格之間的曼哈頓距離。

輸入

輸入包含若干測試用例。每個測試用例有H+1行，第一行給出三個非負整數，分別表示模糊圖像的寬度W、高度H，以及模糊距離D，其中，W≥1、H≤10且D≤min(W/2,H/2)。接下來的H行給出模糊圖像中每個像素的灰度，每行給出W個非負實數，實數保留小數點后兩位，所有給出的實數值都小于100。

在測試用例之間可能是零行，也可能有多行（完全由空格組成）。輸入的最后一行由三個零組成。

輸出

對于每個測試用例，輸出一個W×H的實數矩陣，表示圖像去模糊之后的版本。矩陣中的每個元素精確到兩位小數，并在寬度為8的字段中向右對齊。用一個空行分隔兩個連續的測試用例的輸出。在最后一個測試用例之后不要輸出空行。本題設定每個測試用例都有一個唯一的解。

試題來源：2009 ICPC Africa/Middle East-Africa and Arab

在線測試：HDOJ 3359，UVA4741

試題解析

本題題意：圖像的去模糊版本是一個W×H的實數矩陣A，對于其中的每個元素A[i][j]，從它出發到其他的曼哈頓距離小于等于D的點的所有值的和S[i][j]除以可達點的數目，就是表示模糊圖像的矩陣B。本題給出矩陣B，求矩陣A。

本題的求解是將矩陣A的所有元素作為變量，共有W×H個變量；而矩陣B的每個元素表示為這些變量的表達式，對于B[i][j]，曼哈頓距離在D以內的A[x][y]的系數為1，其他的A[x][y]為0，列出方程，這樣就變成了W×H個變量和W×H個方程的線性方程組，采用高斯消元法求解線性方程組浮點類型解的方法進行求解。

因為本題設定每個測試用例都有一個唯一的解，所以不必考慮無解和多解的情況。但是，進行浮點數消元的時候為了避免精度誤差，每次進行矩陣行變換，都使在對角線上的值的絕對值最大，這樣可將誤差降到最小。

參考程序

【2.1.2 BiliBili】

Shirai Kuroko是一名高一學生。學校里幾乎每個人都有超能力，Kuroko的超能力是“遠距離傳送”，可以使人在十一維空間中轉移，也就是在一般人眼里瞬間移動。

事實上，這一超能力的理論很簡單。每一次，Kuroko都計算出在十一維空間中一些已知物體與目的地之間的距離，這樣Kuroko就可以獲得她想去的目的地的坐標，然后用她的超能力到達目的地。

本題給出在十一維空間中12個物體的坐標Vi=(Xi1,Xi2,…,Xi11)，還給出目的地和物體之間的距離Di，1≤i≤12。請編寫一個程序來計算目的地的坐標。本題設定答案是唯一的，12個物體中的任何4個都不會在同一平面上。

輸入

輸入的第一行給出整數T，表示有T個測試用例。每個測試用例12行，每行給出12個實數，表示Xi1,Xi2,…,Xi11和Di。T小于100。

輸出

對于每個測試用例，輸出11個實數，表示目的地的坐標。實數要四舍五入到小數點后兩位。

在線測試：ZOJ 3645

試題解析

在十一維空間中有一個未知點，已知12個點的十一維坐標及其與這個未知點的距離，求這個未知點的十一維坐標。

設未知點的十一維坐標是(p1,p2,…,p11)，則對于已知點的十一維坐標(Xi1,Xi2,…,Xi11)，以及和未知點之間的距離Di，有(Xi1-p1)2+(Xi2-p2)2+…+(Xi11-p11)2=，1≤i≤12。則將前11個方程，減去第12個方程，就能得到一個線性方程組，采用浮點型高斯消元求解即可。

參考程序