矩阵分析及其在线性代数中的应用(1-2)

1.线性方程

1.2 高斯消元

(A_{m imes n})
三种基本行变换：

交换第i行和第j行
将第i行乘以(alpha)倍
将第i行的(alpha)倍加到第j行

高斯消元：

向下向右寻找非零 pivot element (设为(i,j))
(如果是0则将该 i-th 行与 pivot position 下面的某包含非零项(j-th列上)的行交换)
采用第三种变换将 (i+1)-th 到 m-th 行的第j列均置为0
采用代入法求出所有未知变量的值

复杂度为(O(N^{3}))

1.3 高斯-约当法

在高斯消元的基础上：

采用第二种行变换将每个pivot element转换为1
采用第三种变换将pivot-element所在列的 1-th 到 (i-1)-th行，以及 (i+1)-th 到 m-th 行均置为0
增广矩阵的最后一列即为所求

复杂度为(O(N^{3}))

实践中主要用高斯消元，高斯-约当用于理论推导，求逆等

1.5 让高斯消元法工作起来

大部分的线性方程组的求解都在计算机完成，我们不得不考虑舍入误差的影响：大数吃小数

浮点数下：

(fl(a+b) eq fl(a)+fl(b))
(fl(a imes b) eq fl(a) imes fl(b))

解决策略1：

partial pivot
在每次行变换之前，搜索pivot position(i,j)所在列下方(包含第i行)的所有数字，选出绝对值最大者(设其所在行号为i_max)
交换第 i 行和第 i_max 行，然后在新的 pivot element上执行操作

相对高斯消元，增加的复杂度可以忽略不计

解决策略2：

complete pivot
在每次行变换之前，搜索pivot position(i,j)所在列下方和右方的所有数字，即第 i-th 行到第 m 行，第 j 列到第 n 列，选出绝对值最大者(设其所在行号为i_max， j_max)
交换第 i 行和第 i_max 行，再交换第 j 列和第 j_max 列(记得求得的解，该两列的解需要交换回来)，然后在新的 pivot element上执行操作

相对高斯消元，增加的复杂度很客观

实际计算中，对于非稀疏的矩阵，一般采用 partial pivot法

1.6 病态系统(ill-conditioned system)

病态线性系统
线性方程系统的微小扰动(即增广矩阵中数字的微小变化)，使得扰动前和扰动后求得的精确解相差巨大。
“差之毫厘，失之千里”。
反之即为良态(well-conditioned)

病态方程造成的原因 -> 几何上：每一行代表的线接近平行，微小的扰动将使得交点变化巨大
对于病态方程，并未有数值计算的解决策略

带来的一系列问题：

将求得的解带入原方程，计算左右两边的差值(residuals)大小来判断解的正确性。词条在病态方程上无法实现。
本人的一个联想：最小二乘以及机器学习中赖以生存的residual目标函数是否会受影响

检测是否为病态方程：(我称之为，有病推定)

随即选取一些增广矩阵中的系数，认为制造微小扰动。计算扰前扰后，精确解的差异。
如果差异巨大，则为病态方程
差异不大，则该线性方程系统暂时不是病态。

解决病态的一些方式：

实际中尽可能精确测定系数，以减少可能的扰动

2. 矩形系统和梯形形式(rectangular system and echelon form)

2.1 行梯形形式和秩(row echelon form and rank)

行列数不一致，即为矩形线性系统。
高斯消元过程中，可能出现某pivot position 及其下一列均为0
解决方式：改进版高斯消元
假设 U 是经历了 i-1 次消元步骤之后的增广矩阵。第 i 步如下进行：

在 U 中从左向右，找到在第 i 行或其下的，包含非零元的第一列(假设为(U_{*j}))
第 i 步的pivot position是(i,j)
若非零元所在行(如 i_new)不等于 i ，那么请交换第i和i_new行，然后利用第三种行变换，将该pivot position正下方的元素全部变为0
如果第i行(U_{i*})以及其下面的每一行均为0,那么消元过程停止

行梯形形式(row echelon form):"stair-step" 类型的三角形式
一个 (m imes n)的矩阵 E，行为(E_{i*})，列为(E_{*j}),其为行梯形形式的条件是：

如果(E_{i*})为全零行，那么(E_{i*})下方的每一行均为全零行，即所有的0都在矩阵E的底部
如果(E_{i*})的第一个非零元在第j列，那么位于该非零元下方的列(E_{*1}),(E_{*2}),...,(E_{*j})均为0
即所有的pivots在其所在行从左往右数的第一个非零元

矩阵A确定之后，其最终的行梯形形式E的“样子”(即行梯形形式中的pivots的位置)就唯一确定。
矩阵的秩：
假设矩阵A的行梯形形式为E，那么矩阵A的秩定义为rank(A):

pivots的个数
E各种非零行的个数
A中基本列的个数

A的基本列指A中的包含pivotal positions的列

2.1 约简的行梯形形式

将高斯-约当法用于矩形线性系统，得到约简(reduced)的行梯形形式:
一个矩阵(E_{m imes n})为约简行梯形形式的条件是：

E是行梯形形式
非零行的第一个非零元(每个 pivot)均为1
每个pivot正上方均为0

矩阵A确定之后，其最终的约简行梯形形式E(包括其中的元素)就唯一确定(无论采取的消元方法和顺序是怎样)。
(E_{A})记号：代表A的约简行梯形形式

A和(E_{A})中的列关系：

(E_{A})中的每个非基本列(E_{*k})是在(E_{*k})左边的(E_{A})中基本列的线性组合。即，
(egin{aligned}
E_{k} &= mu_{1}E_{b_{1}} + mu_{1}E_{b_{1}} + cdots + mu_{j}E_{b_{j}}
end{aligned})
其中(E_{*b_{j}})(第(b_{j})项为1，其余为0的列向量)是(E_{*k})左边的基本列,乘子(mu_{j})是(E_{*k})的第j项。
(E_{A})中的列关系与Ａ中的列关系是一致的:
(egin{aligned}
A_{k} &= mu_{1}A_{b_{1}} + mu_{1}A_{b_{1}} + cdots + mu_{j}A_{b_{j}}
end{aligned})
其中(A_{*b_{j}})是(A_{*k})左边的基本列,乘子(mu_{j})是(E_{*k})的第j项

用于数据压缩：
对于一堆数据(大量列向量),最有效的方式是存储"独立数据"(A中的基本列),以及上面从(E_{A})中得到的乘子(mu_{j})的集合。这样一来，所有的列向量都能根据上面的式子重建出来

2.3 线性系统的一致性

m个线性方程，n个未知量的系统是一致的，意味着该系统存在至少一个解。
一致性的判断：下述每个条件均等价于增广矩阵([A|b])是一致的

在([A|b])的约简行梯形形式中，不存在如下形式的行：((0quad 0 quadcdotsquad 0quad |quadalpha))，其中(alpha eq 0)
b是([A|b])中的非基本列
rank([A|b])=rank(A)，即b中不存在pivot position
b是A中基本列的线性组合

2.4 齐次系统

右端项b全为0的系统

令(A_{m imes n})为包含m个方程，n个未知量的齐次系统的系数矩阵，并假设rank((A)=r)。那么有如下性质：

基本列(pivotal positions)所在的未知量为基本变量，剩余的非基本列所在的未知量为自由变量
基本变量的个数为r，自由变量的个数为n-r
使用高斯消元将A约简为行梯形形式，再反向求解出，基于自由变量的基本变量。这个过程产生的通解是：(x = x_{f_{1}}h_{1} + x_{f_{2}}h_{2} + cdots + x_{f_{n-r}}h_{n-r}),
其中项(x_{f_{1}},x_{f_{2}},cdots,x_{f_{n-r}})是自由变量，(h_{1},h_{2},cdots,h_{n-r})均是代表该齐次系统的特解((n imes 1))。(h_{i})独立于行梯形形式。伴随自由变量(x_{f_{i}})的随意取值，该通解就产生出所有可能的解
齐次系统只拥有一个解(平凡的全0解) 等价于 rank((A)=n)，即这里不存在自由变量

我的发现:

(h_{i})由约简行梯形形式(唯一的)中，第i个自由变量对应的非基本列的元素，按一定位置，组成，再取负

2.5 非齐次系统

右端项b至少存在一个非零值

令([A|b])是一致的(m imes n)的非齐次系统的增广矩阵，其中rank((A)=r)。那么有如下性质：

使用高斯消元将([A|b])约简为行梯形形式，然后求解出，基于自由变量的基本变量，得到通解：(x = p + x_{f_{1}}h_{1} + x_{f_{2}}h_{2} + cdots + x_{f_{n-r}}h_{n-r})。伴随自由变量(x_{f_{i}})的随意取值，该通解就产生出所有可能的解
列向量(p)是该非齐次系统的特解
表达式 (x_{f_{1}}h_{1} + x_{f_{2}}h_{2} + cdots + x_{f_{n-r}}h_{n-r})是相关齐次系统("associated homogeneous system")，即([A|0])，的通解
(p)和(h_{i})和([A|b])约简过来的行梯形形式无关，实际上由通过高斯-约当法产生的约简行梯形形式唯一决定
该系统有唯一解等价于下列任一条件满足：
1. rank((A)=n)=未知量个数
2. 不存在自由变量
3. 相关齐次系统("associated homogeneous system")只存在平凡解(即全零解)
  我的发现:
(p)由约简行梯形形式(唯一的)中的右端项的元素(epsilon_{i})，按一定位置，组成。该解是所有自由变量取0值时，该方程的解。