Math concepts / 数学概念

Following are some basic math concepts I read or summarized in my learning process, I wrote them down here to share with those who need them.

（1）奇异函数

奇异函数是一种理想化的函数，它具有一个或多个间断点，在这些点上无法确定函数或其导数值。常用的有阶跃函数和冲激函数。

（2）奇点

所有不满足整体性质的个别点，在数学上都可以称为奇点。

如果奇点出现在分母极限为0的情况，通常来说就是产生无穷大解的表达式，在这种情况下数学计算失效。 

在复变函数中，奇点的定义：若函数（复变函数）f(z)在某点z₀不解析，但在z₀的任一邻域内都有f(z)的解析点，则z₀称为f(z)的奇点（singular point）。

“奇点”是复变函数里的一个概念。在一个区域内可导的复变函数，称为这个区域内的解析函数，如果一个复变函数在挖掉点z的区域内解析，但在点z处不解析，则z称为这个解析函数的奇点。解析函数的奇点总是孤立的，奇点按其性质，可以分为：可去奇点、极点和本性奇点三大类。 

“病态多项式”是与病态代数方程的概念相关的。

在代数方程中，有的多项式系数有微小扰动时其根变化很大，这种根对系数变化的敏感性称为不稳定性（instability），这种方程就是病态多项式方程。通常重根的方程是病态的，有几个根彼此很靠近，则这些根对系数的扰动也是敏感的，有时根看起来分隔得很好，但同样可能是病态的——这段话来自《现代应用数学手册：计算与数值分析卷》一书。

由于在计算机数值算法中，求根过程总是通过迭代来完成的，而迭代过程又是通过一个初始解，不断地修改这个解，最后达到某个收敛标准为止，而一个病态多项式的系数微小变化就会引起根的很大变化，因此在迭代过程中可能导致求出的根不可信。

病态多项式的一个例子：

（4）超线性收敛
如果一种方法（这里指算法），是以前一次迭代的一阶幂乘以一个小于1的因子的速度收敛，则称这种方法为线性收敛（例如二分法），而以高阶幂收敛的方法称为超线性收敛。

具体描述：

设算法产生点列  $\left\{ {{x^{\left( k \right)}}} \right\}$ ，收敛到解  ${x^ * }$ ，且 ${x^{\left( k \right)}} \ne {x^ * },\;\forall k$  ，则

A）线性收敛： $\frac{{\left\| {{x^{\left( {k + 1} \right)}} - {x^ * }} \right\|}}{{\left\| {{x^{\left( k \right)}} - {x^ * }} \right\|}} < 1$  ，当 $k$ 充分大时成立

B）超线性收敛： $\mathop {\lim }\limits_{k \to \infty } \frac{{\left\| {{x^{\left( {k + 1} \right)}} - {x^ * }} \right\|}}{{\left\| {{x^{\left( k \right)}} - {x^ * }} \right\|}} = 0$  

C）二阶收敛： $\exists \alpha > 0$  ，当 $k$ 充分大时有：  $\frac{{\left\| {{x^{\left( {k + 1} \right)}} - {x^ * }} \right\|}}{{{{\left\| {{x^{\left( k \right)}} - {x^ * }} \right\|}^2}}} \le \alpha$

我们知道上面的符号||……||是范数的符号，范数可以用来度量向量之间的距离。对最简单的情况——一维向量来说——上面的各个相减的式子就可以表示两点之间的距离。

（5）卷积
http://www.codelast.com/?p=994

（6）最小二乘的理论依据
http://www.codelast.com/?p=1027

（7）Powell算法
http://www.codelast.com/?p=388

（8）黄金比例搜索算法
http://www.codelast.com/?p=434

（9）奇异方程组
行退化或列退化的方程组称为奇异方程组。

（10）奇异值分解
一种处理奇异问题的方法，有时能将奇异问题转为非奇异问题来解决。

在很长时间内，奇异值分解都无法并行处理（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵）。

2007年初，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，这是 Google中国对世界的一个贡献。

（11）主元
在解线性方程组时，通过加减乘除，将系数矩阵的a₀₀，a₁₁，a₂₂，……（即主对角线上的元素）化为单位矩阵的形式（其他元素均化为零），在每一次计算过程中，用作除数的元素即为主元/主元素。如果计算过程中完全没有“行交换”或“列交换”，则这种方法称为“不选主元”的方法。

（12）完全主元法 & 部分主元法
在解线性方程组的选主元法中，如果只有行交换操作，则称该方法为部分主元法；如果行交换和列交换操作都有，则称该方法为完全主元法。

（13）矩阵的初等变换
a、交换矩阵的两行（列）；

b、用一个不为零的数乘矩阵的某一行(列)；

c、用一个数乘矩阵某一行（列）加到另一行（列）上。

（14）外推法
一种 “根据已知的数值推断已知数值范围以外的数值” 的方法。

（15）Ridders求导算法
http://www.codelast.com/?p=1419

（16）线性/非线性规划
第一次看到这个名词的时候，你一定有一种它好高深的感觉，但实际上它不过是“最优化”问题的一种“特例”罢了。当最优化问题中的自变量的定义域是有限维空间中的一个子集时，这种问题就称为线性/非线性规划。举个简单的例子来说，对一个自变量为1维的函数f(x)=ax+b，自变量的定义域为（1, 9.8），它是1维空间的一个子集，那么，通过最优化方法来求解a、b的问题，就称为线性规划。但是要注意，当x只能取几个值时，例如x只能取1、5、9.8这几个值，则这种最优化问题就不叫线性/非线性规划了，而是叫组合优化。有时候这些界限划分得很清晰的概念反而让人觉得很混淆，我认为它们确实对理解问题起到了负面的作用。

平常看到的很多资料中，对这些类似的概念故弄玄虚的解释什么的，最让人不舒服了！

（17）凸集
凸集在最优化领域占有重要地位。其数学定义是：设有N维空间的子集D，如果对于任意的向量（也可以说是N维空间中的点）X₁，X₂∈D，以及任意的实数a∈[0, 1]，都有aX₁+(1-a)X₂∈D，则称D为凸集。凸集的几何意义是：如果D为非空集合，则连接D中任意两个点X₁、X₂的线段仍属于该集合。

这似乎有点令人费解：aX₁+(1-a)X₂与两点之间的连线有什么关系呢？它表示连接这两点的线段上的任意一点。简单推导如下：假设X为线段X₁X₂上的任一点，则向量X₂X（向量应该打上箭头，但是为了书写方便，我就省略了）平行于向量X₂X₁，且0≤ |X₂X| ≤ |X₂X₁| 。因此，存在a∈[0, 1]，使得 X₂X = a X₂X₁，即：X - X₂ = a (X₁ - X₂)，即 X = aX₁+(1-a)X₂ 。由于X是线段X₁X₂上任一点，因此前面的结论不言自明。

（18）半正定矩阵
n×n的矩阵M，若对于任意非零的x∈Rⁿ，有x^TMx≥0，则称M为半正定矩阵。

（19）奇异矩阵
首先，一个矩阵必须是方阵，才有奇异或非奇异的概念。其次，若该矩阵的行列式为0，则其为奇异矩阵，否则就是非奇异矩阵。

可逆矩阵是非奇异矩阵，非奇异矩阵也是可逆矩阵。

（20）最速下降法/steepest descent，牛顿法/newton，共轭方向法/conjugate direction，共轭梯度法/conjugate gradient，etc.

http://www.codelast.com/?p=2573

（21）水平集

假设X∈Rⁿ，则集合 S = {X∈Rⁿ | f(X) ≤ a} 称为一个水平集，其中a为常数。

（22）由两两线性无关的列向量构成的矩阵是满秩的

先看wikipedia的定义，就很容易明白了：两两线性无关的列向量构成的矩阵必然是满秩的。

（23）线性流形

“流形”（manifold）是数学中用于描述几何形体的一个概念，它是指局部具有欧几里得空间性质的空间。 欧几里得空间就是最简单的流形的实例。欧几里得空间也被理解为线性流形。

这个词听起来挺怪的，我想，要记住它，可以从表面含义来看：“流形”——流动的形状，光滑的；“线性”——连续的。结合起来，N维欧几里得空间Rⁿ就是这么回事。

（24）满秩与正定的一个关系

设C为满秩矩阵，A为正定的实对称矩阵，则C^TAC是正定的。因此可推出：若C是由两两线性无关的向量构成的矩阵（则其为满秩的），则C^TAC正定。

（25）二次型

二次型是一些变量上的二次齐次多项式。齐次多项式是指各项的总次数均相同的多项式 ，例如 x⁵ + 2x³y² + 9xy⁴ 就是一个五次的双变元（x和y）齐次多项式，其各项的总次数都是5。

（26）正定二次型

设有实二次型 f = X^TAX，若对于任何X≠0，都有 f(X)>0，则称 f 为正定二次型，并且称对称矩阵A为正定的。反之，若 f(X)<0，则称 f 为负定二次型。

（27）正定矩阵均可逆，并且其逆也是正定矩阵

（28）柯西不等式/柯西-施瓦茨不等式/Cauchy–Schwarz inequality

相当有用的一个不等式，表达式如下：

若把这个式子写成两个向量u，v的形式，则为：

（29）大O和小o：同阶无穷小与高阶无穷小

大O和小o分别代表同阶无穷小与高阶无穷小，注意不要弄混了。例如，β与α是同阶无穷小，记作β=O(α)；β是比α高阶的无穷小，记作β=o(α) 。

（30）稀疏矩阵：元素大部分为0的矩阵

（31）关于正定矩阵共轭的非零向量组线性无关

（32）实对称矩阵A正定的充分必要条件是存在可逆矩阵C，使得 A=C^TC。由于可逆矩阵是正定矩阵，所以对称正定矩阵A满足：存在正定矩阵D，使得A=D^TD

（33）每一个秩一矩阵都可以化为一个列向量与一个行向量之积

例如A为n×n的秩一矩阵，则存在n×1向量u，v，使得A=uv^T

（34）驻点及鞍点

驻点：一阶导数为0的点。它包括3种类型：极小点、极大点、鞍点。

鞍点：沿某些方向是极小点；沿另一些方向是极大点，这样的点称为鞍点。想像一下马鞍的形状：马鞍凹下去的那部分的最低点，就是鞍点的一个例子（图片来源于网络，感谢原作者）：

（35）雅可比矩阵（Jacobi matrix）不一定是方阵（n×n的矩阵）

（36）无解的线性方程组被称为是不相容的，有一或无穷多个解的线性方程组被称为是相容的

（37）若一个矩阵经过一系列行初等变换可以变成另一个矩阵，则称这两个矩阵是行等价的

（38）一元二次方程 $a{x^2} + bx + c = 0\;(a \ne 0)$ 的求根公式