线性代数基础
参考资料:
- 3blue1brown,从几何的角度介绍线代,推荐观看,一共十几个视频,每个视频不到 15分钟。官方地址
https://www.patreon.com/3blue1brown/posts
- 《线性代数及其应用》,工科强烈推荐阅读
- immersivemath,交互式线性代数学习网站
- 《程序员的数学3——线性代数》
常见概念
-
向量,空间内的点、有向线段(超空间),二维和三维向量可以类比对应空间的矢量;向量默认为列向量
-
张成空间,(span{v_1, v_2, ....,v_p}) 与 (c_1v_1+c_2v_2+c_3v_3...+c_pv_p) 是等价的,其中 (c_x) 为标量
-
秩定理,如果一个矩阵 (A) 有 (n) 列,则 (rank A + dim Nul A = n)
- 列空间,矩阵的列空间是的各列的线性组合的集合,记作 (Col A)
- 零空间,矩阵的零空间是齐次方程 (Ax=0) 的所有解的集合,记为 (Nul A)
-
矩阵,空间到空间的映射(变换)。(vec y = A vec x),使用矩阵 A 将向量 (vec x) 映射到 (vec y)。矩阵的乘积=映射的合成
- 系数矩阵、增广矩阵(系数矩阵加上等号右侧的结果列)
- 先导元素、阶梯型、简化阶梯形,可以参考《线代及其应用》 第 1.2 节
- 主元位置,矩阵对应简单阶梯形先导元素 1 的位置。主元列是含主元位置的列
-
行列式,矩阵映射对应的“体积扩大率”。行列式结果为负,表示空间定向发生了变化,对于二维空间而言负数意味着平面的翻转
- 行列式的递归定义:(operatorname{det} A=sum_{j=1}^{n}(-1)^{1+j} a_{1 j} operatorname{det} A_{1 j})
- 行列式的值为 0 意味着原始空间将被降维
- 行列式性质:(operatorname{det} A^{-1}=frac{1}{operatorname{det} A})
-
基向量,基向量是向量空间的基础:任何向量都可以使用基向量表示;这种表示方式必须唯一
-
零矩阵,两个非零矩阵之积可能为 0 ,如下矩阵 A 和 B。即使矩阵本身不为 0 ,其平方也可能为0,如下 C
[A=left(egin{array}{ll} {1} & {0} \ {0} & {0} end{array} ight), quad B=left(egin{array}{ll} {0} & {1} \ {0} & {1} end{array} ight), quad C=left(egin{array}{ll} {0} & {-1} \ {0} & {0} end{array} ight) ] -
对角矩阵,对角元素不为 0,其他位置元素为 0。按照映射的思想,对角阵的作用是沿着坐标轴伸缩
-
逆矩阵,逆映射,我们可以从高维降维但不能从低维上升到高维(因为丢失了部分信息,即被压缩),所以行列式值为 0 的矩阵不存在逆矩阵。存在逆矩阵的方阵 A,称为正则矩阵(非奇异矩阵)
-
范数
- L0,矢量中值不为零的元素个数
- L1,矢量中所有元素绝对值之和,曼哈顿距离
- L2,矢量所有元素平方和的平方根,欧氏距离
- max-norm,矢量最大的元素绝对值即为当前矢量的 max-norm,
np.linalg.norm([-1,-2],np.inf)=2
线性方程组
常见概念
线性组合
下图是 (mathbf{v}_{1}=left[egin{array}{r}-1 \1end{array} ight]) 和 (mathbf{v}_{2}=left[egin{array}{l} 2 \1end{array} ight]) 在二维空间线性组合的示例
方程组的解与相容性
-
相容/不相容,方程组有一个解或者无穷多个解。充要条件:线性方程组的增广矩阵的最右列不是主元列,即增广矩阵的阶梯形没有形如 ([0 ... 0 b], b eq 0) 的行
-
简化方程的三种基本操作
- 交换方程的位置(对换变换)
- 把方程所有项乘以一个非零的常数(倍乘变换)
- 把某个方程与另一个方程的倍数相加(倍加变换)
-
基本变量 & 自由变量,基本变量:对应主元列的未知量 (x) ;自由变量:非主元列的未知变量 (x)
-
向量方程 & 矩阵方程 & 增广矩阵,同一个线性问题(线性相关性)可以从三个不同的角度考虑,这三者的解集相同
- 矩阵方程: (A f x = f b) ,通过系数矩阵 A 的秩判断方程是否一定有解;
- 向量方程:(x_{1} overrightarrow {a_1} + x_{2} overrightarrow a_{2}+cdots+x_{n} overrightarrow a_{n}=overrightarrow b) , 从列向量的线性组合观点描述方程是否有解
- 增广矩阵:([overrightarrow a_1 overrightarrow a_2 overrightarrow a_3 ... overrightarrow a_n overrightarrow b]), 从主元位置来判断方程是否有解
矩阵
线性变换
-
定义域 & 余定义域(取值空间)
- 由 (R^n) 到 (R^m) 的一个变换 (T) (变换/映射)是一个规则((x ightarrow Ax),(A) 是 (m imes n) 的矩阵),把 (R^n) 中每个向量 (x) 对应以 $R^m $ 中的一个向量 (T(x)) ,集 (R^n) 称为 (T) 的定义域,而 (R^m) 称为 (T) 的余定义域 。对于 (R^n) 中的向量 (x) ,(R^m) 中的向量 (T(x)) 称为 (x) (在 (T) 的作用下)的像,所有像 (T(x)) 的集合称为 (T) 的值域
-
线性变换(齐次与叠加)
- 若 (T) 是线性变换则 (T(0) = 0),且对于 (T) 的定义域中一切向量 (u) 和 (v) 以及数 (c, d) 有:(T(xu + dv) = cT(u)+dT(v))
- 直观来看线性变换
- 原点位置不变
- 变换前后,所有直线依旧为直线
- 线性变换的特点
- 变换前后向量与各自空间的基向量之间的关系保持不变,这里的基向量在两个空间是对应的
- 根据上面的特性,变换前后只要知道基向量的变换结果就可以得到其他所有向量的变换结果
线性变换示例
从空间上讲,线性变换将矢量从一个空间转换到另一个空间,维度可增可减
低维向量转换到高维向量之后信息并未增加,这意味着低维平面映射到高维空间后依旧是在一个高维平面中。以下图为例,二维平面上的点映射到三维空间后,所有点都位于空间中由矢量(left[egin{array}{rr}1 & -3 \3 & 5 \-1 & 7end{array} ight])组成的平面中
高维向量转换到低维空间中将丢失信息,如投影操作
投影 && 剪切 & 旋转
下图中代表了比较常见的几种线性变换:投影、剪切和旋转(逆时针旋转90度)
-
满射&单射&双射
- 满射,即像集合 B 中的每个元素在 A 中都有一个或一个以上的原像
- 单射,即像集合 B 中的每个元素在 A 中最多有一个原像
- 双射,既是单射亦是满射,亦称为一一映射
-
矩阵计算和普通标量计算不同
- (AB eq BA),交换剪切和对称操作的顺序会得到不同的结果
- (AB = AC),并不能说明 (B=C) ,可以参照二维空间的投影操作,不同的结果可以有相同的投影结果(见下)
- (AB = 0),并不能判定 (A=0) 或者 (B=0),例如:(left(egin{array}{cc} 3 & -6 \ -1 & 2 end{array} ight)left(egin{array}{cc} 2 c & 2 d \ c & d end{array} ight)=left(egin{array}{cc} 0 & 0 \ 0 & 0 end{array} ight))
-
矩阵的转置(主对角线为轴进行翻转)
[egin{aligned} &A=left[egin{array}{ll} a & b \ c & d end{array} ight], B=left[egin{array}{rr} -5 & 2 \ 1 & -3 \ 0 & 4 end{array} ight], C=left[egin{array}{rrrr} 1 & 1 & 1 & 1 \ -3 & 5 & -2 & 7 end{array} ight]\ &A^{mathrm{T}}=left[egin{array}{cc} a & c \ b & d end{array} ight], B^{mathrm{T}}=left[egin{array}{rrr} -5 & 1 & 0 \ 2 & -3 & 4 end{array} ight], C^{mathrm{T}}=left[egin{array}{cc} 1 & -3 \ 1 & 5 \ 1 & -2 \ 1 & 7 end{array} ight] end{aligned} ] -
方阵的逆,下面给出二阶方阵逆的计算公式:
[A^{-1}=frac{1}{a d-b c}left[egin{array}{rr} d & -b \ -c & a end{array} ight] ]- 假设 (A) 可逆,则(A^{-1}Ax=x)。矩阵乘法对应着空间变换。 线性变换 (T: R^n
ightarrow R^n) 可逆,则 (其中 (S) 为 (T) 的逆过程)
- 对 (R^n) 中的所有 (x) ,(S(T(x)) = x)
- 对 (R^n) 中所有的 (x),(T(S(x))=x)
- 假设 (A) 可逆,则(A^{-1}Ax=x)。矩阵乘法对应着空间变换。 线性变换 (T: R^n
ightarrow R^n) 可逆,则 (其中 (S) 为 (T) 的逆过程)
-
如果方阵 (A) 是可逆的,当且仅当 (A) 行等价于 (I_n) (与 (A) 相同尺寸的单位阵)
-
将增广矩阵 ([A I]) 进行行化简,若 (A) 行等价于 (I), 则 ([A I]) 行等价于 ([I A^{-1}]) ,否则 (A) 没有逆
-
互为逆矩阵矩阵乘法满足交换律(互为逆运算)
-
证明:设 (B) 的逆矩阵为 (A),则 (A) 的逆矩阵为 (B) 。假设 (B) 的逆矩阵为 (A),(A) 的逆矩阵为 (C) 则下面证明 (A) 和 (B) 互逆
[egin{aligned} &A B=E\ &Rightarrow CAB=CE\ &Rightarrow(CA)B=C\ &Rightarrow B=C end{aligned} ] -
(AA^{-1}=E) 表明 (A^{-1}) 的每一列都是 (A) 对应行方程 ({f a}x=1) 的解,求解逆矩阵部分内容时可以使用当前方法
-
-
使用反证法证明逆的唯一性:设 (A) 可逆且 (B) 和 (C) 为 (A) 不同的逆矩阵
[egin{aligned} &A B=E=A C\ &Rightarrow B(A B)=B(A C)\ &Rightarrow(B A) B=(B A) C\ &Rightarrow E B=E C\ &Rightarrow B=C end{aligned} ]
-
-
初等矩阵
- 把单位矩阵进行初等变换即得初等矩阵
-
病态矩阵:一个可逆的矩阵,某些元素稍微发生变化(必然舍入误差)就会变为奇异矩阵,随着计算中累计误差的增长,病态矩阵对计算的影响会逐渐增大
-
分块矩阵 ,利用分块矩阵思想可以提高矩阵乘法的计算速度,特别是在内存或者 cache 不足的情况下
- (AB) 的行列展开[egin{aligned} A B &=left[operatorname{col}_{1}(A) quad operatorname{col}_{2}(A) quad cdots quad operatorname{col}_{n}(A) ight]left[egin{array}{c} operatorname{row}_{1}(B) \ operatorname{row}_{2}(B) \ vdots \ operatorname{row}_{n}(B) end{array} ight] \ &=operatorname{col}_{1}(A) operatorname{row}_{1}(B)+cdots+operatorname{col}_{n}(A) operatorname{row}_{n}(B) end{aligned} ]
- (AB) 的行列展开
-
子空间
- 基:(R^n) 中子空间 (H) 的一组基时 (H) 中一个线性无关集
矩阵与线性变换
对于 (Ax = b),通常把 (A) 当作一种对象,它通过乘法作用于向量 (x) 将其映射到另一个空间(同维或者异维),产生的新向量称为 (Ax) 。这种关于矩阵的观点(映射变换)是使用线性代数建立数学模型的关键
不同角度思考 (AB=C)
下面从不同的角度来考虑矩阵乘法 (AB = C) ,从不同的角度思考矩阵乘法可以有不同的应用场景。使用分块计算的角度可以将大矩阵分解为小矩阵然后进行计算,可以有效的利用 CPU cache 从而提高 cache 命中率以提高计算效率
从矩阵((A))的列
-
观点 1: (AB) **的每一列都是 (A) 的各列的线性组合,以 (B) 的对应列的元素为权 **
-
观点 2:(A) 的每一列都可以看作目标空间中 (B) 的基坐标 ,通过基坐标的变化,我们可以推测 A 对原空间的变化方式
在直角坐标系中我们常用的两个基向量是:(e_x = (1,0)^T e_y = (0,1)^T),分别对应着直角坐标系中 (x) 轴和 (y) 轴方向的单位向量
假设变换后原来空间基向量转换为:((a,c)^T) 和 ((b, d)^T) ,那么根据上面变换前后向量和基向量关系不变的特性(???),变换之前的向量 ((x,y)^T) 在转换后的结果为:(x imes(a,c)^T+y imes(b,d)^T),使用矩阵表示如下
由上可知,所有二维平面线性变换都可以使用二维方阵表示
未作任何变换的原始线性空间可以表示如下
使用 (A) 表示上式左侧的二维方阵,那么 (A) 的两个列向量分别为线性空间的两个基向量。推广一下,变换后的线性空间中 ((a,c)^T) 和 ((b, d)^T) 分别为新空间的一组基向量
我们从另一个角度来考虑线性变换,我们假设将直角坐标系中原始的基向量逆时针旋转 90 度,则可得到一组新的基向量:
经过变换后的向量 (vec y),与原坐标系向量 $vec x $ 的关系为 (vec y = Avec x)
矩阵相乘可以看作变换的叠加,如下式,先旋转后剪切的操作可等价为一个矩阵运算(注意矩阵运算从右向左)
这同时也给出了一个矩阵相乘不满足交换律的一个例子,先旋转后剪切和先剪切后旋转的结果是不同的
从线性变换的角度看一个列子:
其中 (A = [T(e_1) T(e_2)] = T([e_1, e_2])) 。使用上面的方式重写 (AB=C) 可得:
可以把 (A) 的每一个列看作变换后新坐标系的基坐标与原坐标系之间的映射关系,(A) 的每一个列向量都是一个新的 基向量
如何将 (R^2) 中的每一个点绕原点逆时针旋转 (alpha) 度?
具体操作过程是将原坐标系整体逆时针旋转 (varphi) 度:([1 0]^T) 旋转成为 ([cos(varphi) sin(varphi)]^T) ;([0 1]^T) 旋转成为 ([-sin(varphi) cos(varphi)]^T),即:
则 (T(x) = Ax) 获得的值空间相对于原空间而言,所有点逆时针旋转 (varphi) 度(实例可以参考线代及应用的1.9节)
其他比较常见的 (R^2) 空间线性变换有(为理解下面的内容,推荐观看 3blue1brown 中的 p3、p4、p5):
- 关于 (x) 轴的对称:(left[egin{array}{rr}1 & 0 \ 0 & -1 end{array} ight]) ,关于 (y) 周的对称:(left[egin{array}{rr} -1 & 0 \ 0 & 1 end{array} ight])
- 关于 (y = x) 的对称:(left[egin{array}{ll} 0 & 1 \ 1 & 0 end{array} ight])
- (y) 方向上的拉伸:(left[egin{array}{ll} 1 & 0 \ 0 & k end{array} ight])
- 水平剪切变换:(left[egin{array}{ll} 1 & k \ 0 & 1 end{array} ight]) ,垂直剪切变换: (left[egin{array}{ll} 1 & 0 \ k & 1 end{array} ight])
- 投影到 (x) 轴:(left[egin{array}{ll} 1 & 0 \ 0 & 0 end{array} ight]) ,投影到 (y) 轴:(left[egin{array}{ll} 0 & 0 \ 0 & 1 end{array} ight])
从 A/B 的行或者 B 的列
从计算的角度,(AB) 将得到 (m) 行 (n) 列的矩阵,其中 (m) 为 (A) 的行数,(n) 为 (B) 的列数
可以将 (AB) 的结果,看作拆分 (A) 的每一行乘以 (B) ,最后将所有行整合的过程。那么 (A) 的每一行与 (B) 相乘可以看作使用 (A) 的每一行对 (B) 做行的线性组合 ,这个角度同时涉及到了 (A) 和 (B) 的行
同理,可以将 (AB) 的结果看作拆分 (B) 的每一列和 (A) 做乘法((A x),(x) 是 (B)的某一列向量),最后将所有列整合的过程。那么 (A) 与 (B) 每一列的相乘((Ax_n))可以看作使用 (B) 的每一列对 (A) 做列的线性组合
矩阵变换在计算机图形学(CV)中的应用
如果使用坐标的形式记录图像在屏幕每个像素的位置,那么一个图就可以使用矩阵的形式进行保存,将图像矩阵与变换矩阵相乘,就可以得到变换后图像在屏幕中新的坐标信息
齐次坐标
(R^2) 中的每个点 ((x,y)) 都对应于 (R^3) 中的点 ((x,y,1)) ,我们称 ((x,y)) 有其次坐标 ((x,y,1))
平移操作
可以将左侧矩阵的每一列看作新坐标系的单位向量,就可以了解为什么下面的方式可行
旋转、镜像和伸缩
三维空间的齐次坐标 & 投影(略)
矩阵与线性方程组
Gauss-Jordan Elimination
高斯-若尔当消元法使用增广矩阵来求解方程组的解
初等变换与逆矩阵求解
用初等变换求解逆矩阵
假如我们要求下面矩阵 A 的逆矩阵
先构造下面的矩阵 ((A|I))
使用初等变换方法将 A 转化为 I,则右侧即为 A 的逆矩阵
根据矩阵的分块计算规则,上面初等变换过程可以表示为:((P)(A|I)=(PA|PI)=(I|P)),其中矩阵 (P) 为将左侧矩阵变换为单位阵的初等变换过程。由上可得 (PA=I),即变换矩阵 (P) 为矩阵 (A) 的逆矩阵
矩阵因式分解
矩阵的因式分解是把矩阵表示为两个或者更多矩阵的乘积,矩阵乘法是数据的综合,把多个矩阵结合为一个矩阵
矩阵分解有很多意义,比如提高后续矩阵的计算速度
LU 分解
将矩阵转化为下三角(Lower)和上三角(Upper)矩阵之积的形式即为矩阵的 LU 分解
因为 LU 分解后得到的是三角矩阵,所以求解方程会更加方便快速:(Ax=L(Ux)=Ly={f b}) , (Ly={f b}) 和 (Ux=y)
仅使用行倍加变换将矩阵转换为阶梯型 (U),则变换过程和变换过程的逆 (L) 可以证明是下三角矩阵,过程如下:
时间复杂度
对于稠密矩阵,且 n 比较大时(n>30)
- 计算 A 的 LU 分解,大约需要 (2n^3/3) 次浮点计算
- 解 (Ly=b) 和 (Ux=y) 需要 (2n^2) 浮点计算
- 计算 (A^{-1}) 大约需要 (2n^3) 次浮点计算
对于稀疏矩阵,LU 对计算速度的增益可能更加明显
缩放基向量再相加
有意义的参考文献
- 文献 6
2.3 恶性问题