多元一次方程组
形如
{
a
1
,
1
x
1
+
a
1
,
2
x
2
+
⋯
+
a
1
,
n
x
n
=
b
1
a
2
,
1
x
1
+
a
2
,
2
x
2
+
⋯
+
a
2
,
n
x
n
=
b
2
⋮
a
n
,
1
x
1
+
a
n
,
2
x
2
+
⋯
+
a
n
,
n
x
n
=
b
n
\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\vdots\\a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,n}x_n=b_n\\\end{cases}
⎩
⎨
⎧a1,1x1+a1,2x2+⋯+a1,nxn=b1a2,1x1+a2,2x2+⋯+a2,nxn=b2⋮an,1x1+an,2x2+⋯+an,nxn=bn 的方程组叫做多元一次方程组,又称线性方程组。
手算都会吧
高斯消元
考虑加减消元。
对于原系数矩阵
A
=
[
a
1
,
1
a
1
,
2
⋯
a
1
,
n
b
1
a
2
,
1
a
2
,
2
⋯
a
2
,
n
b
2
⋮
⋮
⋱
⋮
⋮
a
n
,
1
a
n
,
2
⋯
a
n
,
n
b
n
]
A=\begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}&b_1\\a_{2,1}&a_{2,2}&\cdots&a_{2,n}&b_2\\\vdots&\vdots&\ddots&\vdots&\vdots\\a_{n,1}&a_{n,2}&\cdots&a_{n,n}&b_n\end{bmatrix}
A=
a1,1a2,1⋮an,1a1,2a2,2⋮an,2⋯⋯⋱⋯a1,na2,n⋮an,nb1b2⋮bn
我们考虑
x
1
x_1
x1,尝试将系数
a
2
,
1
a_{2,1}
a2,1 到
a
n
,
1
a_{n,1}
an,1 消去。
易得:
a
i
,
j
′
=
a
i
,
j
−
a
1
,
j
⋅
a
i
,
1
a
1
,
1
a_{i,j}'=a_{i,j}-a_{1,j}\cdot\frac{a_{i,1}}{a_{1,1}}
ai,j′=ai,j−a1,j⋅a1,1ai,1
同理我们将矩阵化为
A
′
=
[
a
1
,
1
′
a
1
,
2
′
⋯
a
1
,
n
′
b
1
′
a
2
,
2
′
⋯
a
2
,
n
′
b
2
′
⋱
⋮
⋮
a
n
,
n
′
b
n
′
]
A'=\begin{bmatrix}a_{1,1}'&a_{1,2}'&\cdots&a_{1,n}'&b_1'\\&a_{2,2}'&\cdots&a_{2,n}'&b_2'\\&&\ddots&\vdots&\vdots\\&&&a_{n,n}'&b_n'\end{bmatrix}
A′=
a1,1′a1,2′a2,2′⋯⋯⋱a1,n′a2,n′⋮an,n′b1′b2′⋮bn′
此时解得
x
n
=
b
n
′
a
n
,
n
′
x_n=\frac{b_n'}{a_{n,n}'}
xn=an,n′bn′
将
x
n
x_n
xn 代入上一行,解得
x
n
−
1
x_{n-1}
xn−1,同理解得所有未知数。
注:若代入时系数为
0
0
0,即为无解或非唯一解的情况。
优化
此时会存在精度误差,所以我们需要用 a i , 1 a_{i,1} ai,1 最大的那个来消元,具体实现参考代码。
算法参数
- 时间复杂度: O ( n 3 ) O(n^3) O(n3)
- 空间复杂度: O ( n 2 ) O(n^2) O(n2)
实现代码
#include<bits/stdc++.h>
using namespace std;
int n;
double a[110][110],ans[110],eps=1e-10;
int main(){
cin>>n;
for (int i=1;i<=n;i++) for (int j=1;j<=n+1;j++) cin>>a[i][j];
for (int i=1;i<=n;i++){
int cur=i;
for (int j=i+1;j<=n;j++) if (fabs(a[cur][i])<fabs(a[j][i])) cur=j;
if (fabs(a[cur][i])<eps){cout<<"No Solution"s;return 0;}
if (i!=cur) swap(a[i],a[cur]);
double div=a[i][i];
for (int j=i;j<=n+1;j++) a[i][j]/=div;
for (int j=i+1;j<=n;j++){
div=a[j][i];
for (int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*div;
}
}
ans[n]=a[n][n+1];
for (int i=n-1;i>=1;i--){
ans[i]=a[i][n+1];
for (int j=i+1;j<=n;j++) ans[i]-=a[i][j]*ans[j];
}
for (int i=1;i<=n;i++) printf("%.10lf\n",ans[i]);
return 0;
}
练习
- P3389
- P2455
注:P2455可能做不了,需要高斯-约旦消元。