在线性空间求基的时候,经常会遇到齐次方程组基础解系的问题,比如以下齐次线性方程组:
(
3
2
1
0
0
0
0
0
0
)
v
=
(
0
0
0
)
(321000000)
这种秩为1的三维矩阵,我们知道,它的基础解系肯定是2个向量,那么未知数肯定有6个,我们只有三个已知数,要求六个未知数,怎么办?数字简单还可以配出来,数字复杂了,很多人就不知道怎么搞了?其实技巧很简单,把齐次方程转变为非齐次方程就好了。以上面的齐次线性方程为例子,基础解系肯定是下面的样子:
v
=
k
1
(
a
b
c
)
+
k
2
(
d
e
f
)
v=k_1(abc)
先让两个基的坐标正交,也就是
k
1
,
k
2
k_1,k_2
k1,k2正交,得到两个方程,如下:
k
1
=
1
,
k
2
=
0
,
⇒
3
a
+
2
b
+
c
=
0
k
1
=
0
,
k
2
=
1
,
⇒
3
d
+
2
e
+
f
=
0
k_1=1,k_2=0,\Rightarrow 3a+2b+c=0\\ k_1=0,k_2=1,\Rightarrow 3d+2e+f=0\\
k1=1,k2=0,⇒3a+2b+c=0k1=0,k2=1,⇒3d+2e+f=0
因为这里的基的三个坐标可以任意取值,所以每个基的前两个坐标单位正交,去生成另外4个方程:
a
=
1
b
=
0
d
=
0
e
=
1
⇒
c
=
−
3
f
=
−
2
a=1\\ b=0\\ d=0\\ e=1\\ \Rightarrow c=-3\\ f = -2
a=1b=0d=0e=1⇒c=−3f=−2
所以基础解系为:
v
=
k
1
(
1
0
−
3
)
+
k
2
(
0
1
−
2
)
v=k_1(10−3)
其实就是把两个变量作为自由变量,这里是把
x
1
,
x
2
x_1,x_2
x1,x2作为自由变量,将解变成这样:
v
=
x
1
(
1
0
c
)
+
x
2
(
0
1
f
)
v=x_1(10c)
看成两部分,第一部分:
x
1
(
1
0
c
)
x_1(10c)
这部分,只受
x
1
x_1
x1影响,
x
2
x_2
x2的取值被它乘以了
0
0
0.第二部分:
x
2
(
0
1
f
)
x_2(01f)
这部分,只受
x
2
x_2
x2影响,
x
1
x_1
x1的取值被它乘以了
0
0
0.
编程的思路是:
考虑到如果某行只有1个非零列,那么这列对应的所有基坐标必须为0,所以不能像上例一样生成方程了,举个例子:
(
1
1
1
0
1
0
0
0
0
)
v
=
(
0
0
0
)
(111010000)
对于这种情况,我们就必须标记基里必须为零的坐标。排除必须为0的,然后再用单位正交的方法去生成方程。那么前面的流程就又可以改一下:
再思考下,如果基的坐标中只有1个是1,其余的都是0的话,其实每个基都是孤立的,我们一个个基去解决就完事了。这个基中有 x x x个已知数,只剩下 n − x n-x n−x个未知数。所以求每个基的步骤如下:
private List<T[]> homogeneousSolution(T[][] ts) {
// 首先计算秩
int n = ts.length;
int rank = 0;
List<Integer> mustZeroLines = new ArrayList<>();
List<Integer> mustZeroColumns = new ArrayList<>();
for (; rank < n; rank++) {
// 非零列数量
int nonZero = 0;
int firstNonZeroColumn = 0;
T[] line = ts[rank];
for (int j = 0; j < line.length; j++) {
T x = line[j];
if (!this.zeroValue().equals(x)) {
nonZero++;
firstNonZeroColumn = j;
}
}
if (nonZero == 0) {
break;
} else if (nonZero == 1) {
mustZeroLines.add(rank);
mustZeroColumns.add(firstNonZeroColumn);
}
}
// 满秩只有零解
if (rank == n) {
final T[] o = this.newArray(n);
Arrays.fill(o, this.zeroValue());
return Collections.singletonList(o);
}
/*
* 转成齐次线性方程组,未知数为num * n个。
* 将基座标分别取正交,baseNum * r个方程
* 所以还需要 baseNum * num个方程
* 生成方程,方程有(n−x)(n−r)个未知数
* mustZeroColumns是必须为0的列
*/
List<Integer> freeZeroColumns = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!mustZeroColumns.contains(i)) {
freeZeroColumns.add(i);
}
}
// 基数量
int baseNum = n - rank;
List<T[]> solutions = new ArrayList<>();
// 方程
// 对每个基进行正交
for (int i = 0; i < baseNum; i++) {
T[] solution = getBase(ts, rank, mustZeroLines, mustZeroColumns, i);
solutions.add(solution);
}
return solutions;
}
private T[] getBase(T[][] ts, int rank, List<Integer> mustZeroLines, List<Integer> mustZeroColumns, int baseIndex) {
int n = ts.length;
int x = mustZeroColumns.size();
// 本质上是只取一个向量
// 一个基得出一个解系,一个向量
// 基的第一个为1的坐标
List<T[]> equations = new ArrayList<>();
for (int j = 0; j < rank; j++) {
if (mustZeroLines.contains(j)) {
continue;
}
T[] equation = this.newArray(n - x + 1);
Arrays.fill(equation, this.zeroValue());
// 这个向量代入原方程
// 比如1 2 3 4 5.其中2列非得为9
T[] freeColumns = removeMustZero(ts[j], mustZeroColumns);
System.arraycopy(freeColumns, 0, equation, 0, freeColumns.length);
equations.add(equation);
}
// 首先代入非零行
// 然后是第一个为1,其余为0
for (int j = 0; j < n - rank; j++) {
T[] equation = this.newArray(n - x + 1);
Arrays.fill(equation, this.zeroValue());
equation[j]=this.oneValue();
if (j == baseIndex) {
equation[n - x]=this.oneValue();
} else {
equation[n - x]=this.zeroValue();
}
equations.add(equation);
}
final T[][] array = equations.toArray(this.newArray(n - x, n - x + 1));
final Matrix<T> matrix = this.createMatrix(array);
T[] solution = matrix.solution().get(0);
// 这个解还需要拼接必须为0的列
final T[] result = this.newArray(n);
for (int i=0,j=0;i<n;i++) {
if (mustZeroColumns.contains(i)) {
result[i] = this.zeroValue();
} else {
result[i]= solution[j++];
}
}
return result;
}
private T[] removeMustZero(T[] line, List<Integer> mustZero) {
List<T> ts = new ArrayList<>();
for (int i = 0; i < line.length; i++) {
if (!mustZero.contains(i)) {
ts.add(line[i]);
}
}
return ts.toArray(this.newArray(line.length - mustZero.size()));
}
完整代码在https://e.coding.net/buildt/math/matrix.git。
package com.youngthing.matrix.test.image;
import com.youngthing.matrix.DoubleMatrix;
import org.junit.Test;
import java.util.Arrays;
import java.util.List;
/**
* 11/18/2022 9:43 PM 创建
*
* @author 花书粉丝
*/
public class HomogeneousTest {
@Test
public void homogeneousTest() {
printSolution(new Double[][]{
{3d, 2d, 1d, },
{0d, 0d, 0d,},
{0d, 0d, 0d}});
printSolution(new Double[][]{
{3d, 2d, 1d, 1d},
{0d, 1d, 0d, 0d},
{0d, 0d, 1d, 0d},
{0d, 0d, 0d, 1d}});
printSolution(new Double[][]{
{3d, 2d, 1d, },
{0d, 1d, 0d,},
{0d, 0d, 0d}});
printSolution(new Double[][]{
{3d, 2d, 1d, 1d},
{0d, 0d, 0d, 0d},
{0d, 0d, 0d, 0d},
{0d, 0d, 0d, 0d}});
}
private void printSolution(Double[][] matrix) {
final List<Double[]> solution = new DoubleMatrix(matrix).solution();
System.out.println("基为:");
for (Double[] x : solution) {
System.out.println(Arrays.toString(x));
}
}
}
测试结果完全正确:
基为:
[1.0, 0.0, -3.0]
[0.0, 1.0, -2.0]
基为:
[0.0, 0.0, 0.0, 0.0]
基为:
[1.0, 0.0, -3.0]
基为:
[1.0, 0.0, -0.0, -3.0]
[0.0, 1.0, -0.0, -2.0]
[0.0, 0.0, 1.0, -1.0]