高斯消元

高斯消元是一种在 \(O(n^3)\) 的时间复杂度下解线性方程组的算法，方程组形如：

\[\left\{\begin{aligned}&a_{1,1}x_{1}+a_{1,2}x_{2}+\dots+a_{1,n}x_{n}=b_1\\&a_{2,1}x_{1}+a_{2,2}x_{2}+\dots+a_{2,n}x_{n}=b_2\\&\dots\\&a_{n,1}x_{1}+a_{n,2}x_{2}+\dots+a_{n,n}x_{n}=b_n\end{aligned}\right.\]
算法思路

1. 高斯消元

发现线性方程组的系数和等号右侧的常数是解方程的关键，因此我们可以把系数和常数拎出来，形成一个矩阵。
比如：

\[\left\{\begin{aligned}3x_1+7x_2+8x_3&=14\\6x_1-x_2-2x_3&=7\\-12x_1+x_2-x_3&=-10\\\end{aligned}\right.\]
可以改写为：

\[\left(\begin{array}{ccc|c}3& 7& 8& 14\\6& -1& -2& 7\\-12& 1& -1& -10\end{array}\right)\]
这样的矩阵被称为增广矩阵。
回忆解多元一次方程组的过程，我们发现我们可以对方程组进行如下操作：

• 交换任意两个方程的位置；
  
• 将一个方程加上另一个方程；
  
• 将整个方程乘上一个数。
  

对应到增广矩阵中，就是：

• 交换任意两行；
  
• 将某一行的数分别加上另一行对应的数；
  
• 将某一行的所有数乘上同一个数。
  

高斯消元的目的，就是通过上面的三种操作，将增广矩阵变为形式如下的上三角矩阵，得到 \(x_n\) 的值，然后依次代入得到整个方程的解：

\[\left(\begin{array}{ccc|c}\times& \times& \times& \times\\\times& \times& \times& \times\\\times& \times& \times& \times\end{array}\right)\Rightarrow\left(\begin{array}{ccc|c}\times& \times& \times& \times\\0& \times& \times& \times\\0& 0& \times& \times\end{array}\right)\Rightarrow\left(\begin{array}{ccc|c}\times& 0& 0& \times\\0& \times& 0& \times\\0& 0& \times& \times\end{array}\right)\]
考虑每次对一个未知数进行消元（即一列），设当前未知数为 \(x_i\)（第 \(i\) 列），我们按照以下步骤消元：
1. 无解判断

若这一列从第 \(i\) 行往下都是 \(0\)，说明这个未知数无解或为任意解，判无解。
2. 选主元

选择这一列从第 \(i\) 行往下系数绝对值最大的那一个作为主元，将这一行与第 \(i\) 行交换
比如：

\[\\left(\begin{array}{ccc|c}3& 7& 8& 14\\6& -1& -2& 7\\-12& 1& -1& -10\end{array}\right)\Rightarrow\left(\begin{array}{ccc|c}\underline{3}& 7& 8& 14\\\underline{6}& -1& -2& 7\\\boxed{-12}& \underline{1}& \underline{-1}& \underline{-10}\end{array}\right)\Rightarrow\left(\begin{array}{ccc|c}-12& 1& -1& -10\\6& -1& -2& 7\\3& 7& 8& 14\end{array}\right)\]
这一操作的目的是减少误差（原因见下文）。
3. 消元

对于第 \(j\) 行（\(j>i\)），为了使 \(a_{j,i}\) 消为 \(0\) ，我们需要将第 \(j\) 行减去第 \(i\) 行（主元行）的 \(\frac{a_{j,i}}{a_{i,i}}\) 倍，这样 \(a_{j,i}-a_{i,i}\times\frac{a_{j,i}}{a_{i,i}}=0\)。
注意，消第 \(i\) 个未知数时，只需要将第 \(i\) 列第 \(i\) 行下面的数消为 \(0\) 即可。

\[\begin{aligned}&\left(\begin{array}{ccc|c}-12& 1& -1& -10\\6& -1& -2& 7\\3& 7& 8& 14\end{array}\right)\\\Rightarrow&\left(\begin{array}{ccc|c}\color{red}{-12}& \color{red}{1}& \color{red}{-1}& \color{red}{-10}\\6-(\textcolor{red}{-12})\times\textcolor{blue}{\frac{6}{-12}}& -1-\textcolor{red}{1}\times\textcolor{blue}{\frac{6}{-12}}& -2-(\textcolor{red}{-1})\times\textcolor{blue}{\frac{6}{-12}}& 7-(\textcolor{red}{-10})\times\textcolor{blue}{\frac{6}{-12}}\\3-(\textcolor{red}{-12})\times\textcolor{green}{\frac{3}{-12}}& 7-\textcolor{red}{1}\times\textcolor{green}{\frac{3}{-12}}& 8-(\textcolor{red}{-1})\times\textcolor{green}{\frac{3}{-12}}& 14-(\textcolor{red}{-10})\times\textcolor{green}{\frac{3}{-12}}\end{array}\right)\\\Rightarrow&\left(\begin{array}{ccc|c}-12& 1& -1& -10\\\underline{0}& -0.5& -2.5& 2\\\underline{0}& 7.25& 7.75& 11.5\end{array}\right)\end{aligned}\]
从左往右对每个未知数（每一列）进行以上三步操作，得到上三角矩阵：

\[\left(\begin{array}{ccc|c}-12& 1& -1& -10\\0& 7.25& 7.75& 11.5\\0& 0& -\frac{114}{58}& \frac{81}{29}\end{array}\right)\]
4. 得到答案

将上三角矩阵写成方程式，有

\[\left\{\begin{aligned}-12x_1+x_2-x_3&=-10\\7.25x_2+7.75x_3&=11.5\\-\frac{114}{58}x_3&=\frac{81}{29}\end{aligned}\right.\]
发现最后一个未知数的解我们已经知道了，将解依次代回就可以得到方程组的解了。

\[\left\{\begin{aligned}x_1&=\frac{-10-x_2+x_3}{-12}=1.210526\\x_2&=\frac{11.5-7.75x_3}{7.25}=3.105263\\x_3&=-1.421053\\\end{aligned}\right.\]
5.误差问题

考虑这样一组数据：

\[\left\{\begin{aligned}0.3 \times 10^{-11}x_1+x_2&=0.7\\x_1+x_2&=0.9\end{aligned}\right.\]
如果以第一行为主元进行消元，则有：

\[\left(\begin{array}{cc|c}0.3\times 10^{-11}& 1& 0.7\\0& 1-\frac{10}{3}\times10^{11}\times1& 0.9-\frac{10}{3}\times10^{11}\times0.7\end{array}\right)\]
会得到：

\[\left\{\begin{aligned}x_1&=0.000000\\x_2&=0.700000\end{aligned}\right.\]
但如果以第二行为主元消元，则有：

\[\left(\begin{array}{cc|c}1& 1& 0.9\\0& 1-0.3\times10^{-11}\times1& 0.7-0.3\times10^{-11}\times0.9\end{array}\right)\]
会得到：

\[\left\{\begin{aligned}x_1&=0.200000\\x_2&=0.700000\end{aligned}\right.\]
明显更接近正解。
所以，在高斯消元中，应选择系数绝对值最大的一行作为主元行，使 \(\frac{a_{j,i}}{a_{i,i}}\) 中的 \(a_{i,i}\) 绝对值更大，原分数值更小，减少计算时的误差。
时间复杂度 \(O(n^3)\)。
模版代码

洛谷模版 P3389
[code]#include#include#include#includeusing namespace std;const double eps=1e-7;int n;double a[105][105],ans[105];int main(){        scanf("%d",&n);        for(int i=1;i