欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

最优化用到线性代数基础

这是一篇笔记,帮助我自己快速回忆线性代数相关的知识。

线性无关

如果方程:

\(\alpha_1\mathbf{a_1} + \alpha_2 \mathbf{a_2} +...+\alpha_k \mathbf{a_k} = \mathbf{0}\)

满足的时候所有系数 \(\alpha_i(i=1,...,k)\) 等于零,那么称向量集{ \(\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k}\) }是线性无关的。

线性相关

如果向量集合{ \(\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k}\) }不是线性无关,那么就是线性相关。线性相关可以直观的理解为至少其中一个向量可以使用剩余向量表示。

线性组合

如果给定向量 \(\mathbf{a}\) ,存在标量 \(\alpha_1,\alpha_2,...,\alpha_k\) 使得:

\(\mathbf{a}=\alpha_1\mathbf{a_1} + \alpha_2 \mathbf{a_2} +...+\alpha_k \mathbf{a_k}\)

矩阵的秩

矩阵 \(\mathbf{A}\)线性无关列的最大数目成为A的秩,记为 \(rank \mathbf{A}\)

子空间

假定 \(\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k}\)\(R^n\) 中的任意向量,他们中所有线性组合的集合称为{ \(\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k}\) }张成的子空间,记为:

\(span[\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k} ] = \left\{\begin{matrix} \sum_{i=1}^{k}{\alpha_i \mathbf{a_i}} \end{matrix}\right\}\)

逆序数

逆序数的定义很简单,就是一个序列中每个数后面比它小的数的个数之和。例如有三个数分别为1、2、3,这三个数组成的序列有3!种,序列123的逆序数为0,序列132的逆序数为1,312的逆序数为2。逆序数有很多很有意思的性质,行列式的定义和逆序数的「奇偶性」密切相关。

逆序数有一个很重要的性质需要牢记于心:

交换两个序列中的两个数的位置,逆序数的奇偶性必然发生改变。

行列式

行列式的定义:行列式的定义非常奇怪,追溯行列式的定义源头和物理意义是一件比较有意思的事情,将来单独写一篇文章研究吧。这里直接给出来行列式计算的方法:

\(\begin{vmatrix}a_{11} &a_{12} &... &a_{1n} \\a_{21} &a_{22} &... &a_{2n}\\\vdots & \vdots& &\vdots \\a_{n1}&a_{n2} &... &a_{nn}\end{vmatrix}=\sum{(-1)^\tau a_{1p_1}a_{2p_2}...a_{np_n}}\)

其中 \(p_1p_2..p_n\) 是列标, \(\tau\) 表示 \(p_1p_2..p_n\) 的逆序数。

矩阵 \(A = [\mathbf{a_1},\mathbf{a_2},...,\mathbf{a_k}]\) 的行列式是各列的线性函数,即对于任意的 \(\alpha,\beta \in R \)\(\mathbf{a}_k^{1},\mathbf{a}_k^{2} \in R^n\) ,都有:

\(det[A]=det[\mathbf{a_1}, ...,\mathbf{a_{k-1}},\alpha \mathbf{a_k^1} +\beta \mathbf{a_k^2},...,\mathbf{a_{k+1}},...\mathbf{a_n}] \\=\alpha \ det[\mathbf{a_1}, ...,\mathbf{a_{k-1}},\mathbf{a_k^1},...,\mathbf{a_{k+1}},...\mathbf{a_n}] \\+\beta \ det[\mathbf{a_1}, ...,\mathbf{a_{k-1}},\mathbf{a_k^2},...,\mathbf{a_{k+1}},...\mathbf{a_n}]\)

行列式还有一些别的性质,其实都可以站在逆序数的角度理解。

如果一个方阵的行列式值为非0,那么这个方阵可逆。

线性方程组

给定n个未知量的m个方程:

\(a_{11}x_1 + a_{12}x_2, ...,+a_{1n}x_n = b_1 \\a_{21}x_1 + a_{22}x_2, ...,+a_{2n}x_n = b_2\\.\\.\\a_{m1}x_1 + a_{m2}x_2, ...,+a_{mn}x_n = b_m\)

通过矩阵可以表示为:

\(Ax=b\)

曾广矩阵的定义为:

\([A,b]=[a_1,a_2,...,a_n,b]\)

线性变换

矩阵的乘法可以看做是在进行线性变换,例如 \(AB\) 相当于对B进行行变换,对A进行列变换。线性方程 \(Ax=b\) 可以看做是对x进行行变换。

 特征值和特征向量

定义:A为n阶矩阵,如果存在数 \(\lambda\) 和n维非零向量 \(q\) ,使得下式成立,

\(Aq=\lambda q\)

则称 \(\lambda\) 为「特征值」非零向量 \(q\) 为特征向量。

上式也可以写成:

\((A-\lambda)q=0 \ \ \ q \ne 0\)

q可以看做是齐次线性方程组 \((A-\lambda E)x = 0\) 的非零解,存在非零解的充要条件是行列式 \(det(A-\lambda) = 0\) 。这个描述有点拗口,翻译成大白话就是,如果q不为0的情况下想要乘积为0,也就是对矩阵 \(A-\lambda\) 存在一种列变换,使得某一列变为0,所以矩阵 \(A-\lambda\) 是奇异的,行列式的值一定是0。所以要求出来所有满足条件的 \(\lambda\) 只需要根据行列式展开这个矩阵,然后解一个一元n次方程即可:

\(det[A-\lambda E]=\lambda^n + a_{n-1}\lambda^{n-1}+...+a_1\lambda + a_0 = 0\)

性质

  1. 如果方阵有n个特征根,那么他就有n个不同的线性不相关的特征向量。
  2. 方阵A可对角化的充要条件是,方阵A有n个线性无关的特征向量。
  3. 一个实对称矩阵的所有特征值都是实数。
  4. 一个实堆成矩阵任何两个特征向量正交。

二次型

二次型函数f: \(R^n\rightarrow R\) 定义为具有如下形式的函数:

\(f(x) = x^t Qx\)

对上式Q的作用可以理解为:

  1. 穷举所有的 \(x_i x_j\) 的乘积组合
  2. 确定系数
  3. 加到一起

如果对任意非零x都有f(x)>0,则说明二次型是正定的,如果f(x)>=0则说明是半正定。

定理:对称矩阵Q是正定(半正定),当且仅当Q的所有特征值是正的(非负的)。

矩阵范数

矩阵范数有很多种定义,下面是其中一种。矩阵A的范数可以记为||A||,他是满足如下条件的任意函数:

  1. 如果 \(A \ne O\) ,那么有||A||>0,||O||=0,O是一个零矩阵。
  2. 对任意 \(c \in R\) ,有||cA|| = |c| ||A||。
  3. \(||A+B|| \le ||A|| + ||B||\)

参考文献

《最优化导论》Edwin K.P.Chong Stanislaw H. Zak

《线性代数》朱玉清

未经允许不得转载:大数据算法 » 最优化用到线性代数基础

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站