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个方程，就能得到一个线性方程组，采用浮点型高斯消元求解即可。

参考程序