2.2.线性方程组
2.2.1.初等矩阵变换
- 把某一行乘一个非零的数；
- 交换某两行；
- 把某行的若干倍加到另一行上去。
2.2.2.高斯消元解m×n线性方程组\(O(mn^2)\)
\(\begin{cases}a_{11}x_1+\cdots+a_{1n}x_n=b_1\\\vdots\\a_{m1}x_1+\cdots+a_{mn}x_n=b_m\end{cases}\Rightarrow [A,b]=A'_{m×(n+1)}\)
高斯消元化\(A'_{m×(n+1)}\)的A为行最简形，得到\(A''_{m×(n+1)}\)：
h和l都从1开始。借助循环依次处理第1~n列。对于第l列：
- 在第h~m行中，找到第l列系数的绝对值最大的一行\(h_{max}\)。
如果该系数不为0，记录\(key_h=l\)。
否则，第h~m行的第l列全是0，结束本轮循环，不要执行循环底部的h++，只执行l++处理完第l列。
- 将第\(h_{max}\)行与第h行交换。（交换某两行）
- 将交换后的第h行的第一个有效数字（第l列）变成1。（把某一行乘一个非零的数）
- 将上下除第h行外的所有行的第l列清成0。（把某行的若干倍加到另一行上去）
- 执行循环底部的h++。
执行后如果h>m，跳出循环；否则执行l++处理完第l列。
r(A)=h-1。
判断解的个数：
- 有解 \(\Leftrightarrow\) r(A)==r([A,b]) \(\Leftrightarrow\) \(\forall i\in[r(A)+1,m]\cap\mathbb{Z},A''_{i,n+1}==0\)。
- 有唯一解 \(\Leftrightarrow\) r(A) == r([A,b]) == n。
- 否则有无穷多解。
- 否则无解。
求出一个合法解：
令\(x_{key_i}=A''_{i,n+1},i\in[1,r(A)]\cap\mathbb{Z}\)，其余的即为自由变量\(x_j=0\)。
若要求出其他的合法解，则令自由变量\(x_j\)取任意常数，代入方程求出\(x_{key_i}\)。
[code]//i：m；j：nint m,n;double a[M][N],x[N];int ra,key[M];int gauss(){ //高斯消元化A'_{m×(n+1)}的A为行最简形，得到A''_{m×(n+1)} int h,l; for(h=1,l=1;l0) key[h]=l; //如果该系数不为0，记录key_h=l else continue; //否则，第h~m行的第l列全是0，结束本轮循环，不要执行循环底部的h++，只执行l++处理完第l列 //将第h_max行与第h行交换。（交换某两行） for(int j=l;j=l;j--) a[h][j]/=a[h][l]; //将上下除第h行外的所有行的第l列清成0。（把某行的若干倍加到另一行上去） for(int i=1;i=l;j--) //倒序是因为要用到a[l]被清成0之前的值，到l为止是因为a[1~l-1]已经被上面清成0了 a[j]-=a[h][j]*a[l]; //把某行的若干倍加到另一行上去，达到下面所有行的第l列清成0的目的 //思维：此时可以把外层循环i看作定值，且a[h][l]=1 } //执行循环底部的h++ h++; if(h>m) break; //执行后如果h>m，跳出循环；否则执行l++处理完第l列 } ra=h-1; //判断解的个数 for(int i=ra+1;i |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
