• 3.4 齐次方程组基础解系


    基本解法

      在线性空间求基的时候,经常会遇到齐次方程组基础解系的问题,比如以下齐次线性方程组:
    ( 3 2 1 0 0 0 0 0 0 ) v = ( 0 0 0 ) (321000000)

    300200100
    v =(000)
    000
    300200100 v= 000
      这种秩为1的三维矩阵,我们知道,它的基础解系肯定是2个向量,那么未知数肯定有6个,我们只有三个已知数,要求六个未知数,怎么办?数字简单还可以配出来,数字复杂了,很多人就不知道怎么搞了?其实技巧很简单,把齐次方程转变为非齐次方程就好了。以上面的齐次线性方程为例子,基础解系肯定是下面的样子:
    v = k 1 ( a b c ) + k 2 ( d e f ) v=k_1(abc)
    abc
    +k_2(def)
    def
    \\
    v=k1 abc +k2 def

      先让两个基的坐标正交,也就是 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=1c=3f=2
      所以基础解系为:
    v = k 1 ( 1 0 − 3 ) + k 2 ( 0 1 − 2 ) v=k_1(103)
    103
    +k_2(012)
    012
    \\
    v=k1 103 +k2 012

      其实就是把两个变量作为自由变量,这里是把 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)
    10c
    +x_2(01f)
    \\
    v=x1 10c +x2 01f

      看成两部分,第一部分:
    x 1 ( 1 0 c ) x_1(10c)
    x1 10c

      这部分,只受 x 1 x_1 x1影响, x 2 x_2 x2的取值被它乘以了 0 0 0.第二部分:
    x 2 ( 0 1 f ) x_2(01f)
    \\
    x2 01f

      这部分,只受 x 2 x_2 x2影响, x 1 x_1 x1的取值被它乘以了 0 0 0.

    Java代码实现

      编程的思路是:

    1. 先变成上三角矩阵;
    2. 判断矩阵的秩r,如果 r = n r=n r=n,只有零解,线性空间为零空间;
    3. 如果 r < n rr<n,则是有解的,解系的向量数为 n − r n-r nr,未知数个数为 n ( n − r ) n(n-r) n(nr);
    4. 基的坐标逐个为1,代入原方程组,有了 r ( n − r ) r(n-r) r(nr)个方程。
    5. 最终还差 ( n − r ) 2 (n-r)^2 (nr)2个方程,按单位正交的思想生成方程,解出所有未知数。

      考虑到如果某行只有1个非零列,那么这列对应的所有基坐标必须为0,所以不能像上例一样生成方程了,举个例子:
      
    ( 1 1 1 0 1 0 0 0 0 ) v = ( 0 0 0 ) (111010000)

    v =(000)
    100110100 v= 000
      对于这种情况,我们就必须标记基里必须为零的坐标。排除必须为0的,然后再用单位正交的方法去生成方程。那么前面的流程就又可以改一下:

    1. 如果 r < n rr<n,则是有解的,解系的向量数为 n − r n-r nr
    2. 如果有 x x x行只有一个非零列,那么每个基可以减少 x x x个未知数,未知数个数为 ( n − x ) ( n − r ) (n-x)(n-r) (nx)(nr);
    3. 基的坐标逐个为1,代入原方程组,有了 ( r − x ) ( n − r ) (r-x)(n-r) (rx)(nr)个方程。
    4. 最终还差 ( n − r ) 2 (n-r)^2 (nr)2个方程,按单位正交的思想生成方程,解出所有未知数。

      再思考下,如果基的坐标中只有1个是1,其余的都是0的话,其实每个基都是孤立的,我们一个个基去解决就完事了。这个基中有 x x x个已知数,只剩下 n − x n-x nx个未知数。所以求每个基的步骤如下:

    1. 假设是第 i i i个基,先把基代入 r − x r-x rx行;
    2. 再在基的第i个自由位置设置为1,其余自由位置为0,产生了 n − r n-r nr个方程;
    3. 解出该方程,成为一个基。
        步骤出来了,代码就相当容易了。因为篇幅有限,我只贴关键代码:
         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()));
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120

      完整代码在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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

      测试结果完全正确:

    基为:
    [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]
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
  • 相关阅读:
    外辐射源雷达信号模型
    D. Weight the Tree(思维 + 树形dp)(好题!)
    Python 函数转命令行界面库 -- Argsense CLI
    【Spring】bean的实例化
    C#:实现动态规划背包求解器算法(附完整源码)
    Python模块ADB的, 已经 pyadb
    2022年数据泄露平均成本高达435万美元,创历史新高!
    【数据结构】-----二叉树(递归、层次实现二叉树的遍历)
    【经典】请求拦截,相应拦截vue3封装,使用dom封装typescript接口
    mysql 常用操作
  • 原文地址:https://blog.csdn.net/m0_66201040/article/details/127918900