Conditional Number of Matrix

In This post, I will comb the inference of the conditional number of Matrix

WHAT

不得不说，咱们语言文化的博大精深。所谓“千里之堤，溃于蚁穴”，则正是条件数的表示，旨在对某件事物进行轻微的扰动，那么其会产生巨大的影响。

Defenition

所以对于方程组 $Ax=b$， 如果我们给$A$一个轻微的扰动，其解x变化仍在我们可接受的范围之内的话，那么就说这个矩阵是良好的矩阵(Well Done!)，否则，它就是一个病态的矩阵。

针对上述定义，我们引出两个问题

1. 什么是轻微的扰动？

2. 如何评测一个矩阵是否是病态的？

所谓轻微的扰动，并不是指整个矩阵中所有元素变化量的大小，而是说变化元素的个数。通常，我们用

来表示仅在$(i, j)$位置的元素为$\alpha$，其余位置为$0$的矩阵。而轻微扰动，即在$A$的基础之上 append 一些$(1)$的元素。

下面进行条件数的推导。

Inference of the Conditional Number

Neumann Series

在这里只能说诺伊曼牛逼, If $\lim_{n \to \infty} A^n=0$, 那么$I-A$就是非奇异的，并且

这个直接相乘即可验证出来了，诺伊曼给了我们一个估算$(I-A)^{-1}$的级数，太棒了。

Perturbation Term

现在我们假设给予$A$矩阵一些轻微的扰动$B$， 即$A+B$，现在来考虑$Ax=b$的解$x$，与$(A+B)\widetilde{x}=b$的解$\widetilde{x}$的gap。因为$A$可逆，且$B$是轻微扰动，所以说$A+B$是可逆的，所以

从而，我们仅要看$A^{-1}$与$(A+B)^{-1}$的差异即可。下面由诺伊曼级数进行导出。

假设$\lim_{n \to \infty}(A^{-1}B)^n=0$，(这个其实很好满足嘛，直觉上只要$A^{-1}$不要太大就好，因为$B$是轻微扰动项，所以说$B^n$本身很小很小的，这样说不太严谨，但是intuitive)。

为了方便起见，我们仅考虑其一阶估计

可见，右边儿的第二项就是扰动项：$A^{-1}BA^{-1}$。

扰动项 => 条件数

首先我们先得到$x- \widetilde{x}$的上界

这肯定是上界嘛，因为只估算到了一阶。那么，只要这个上界足够小，那么其误差就可能大。

由于解本身有大有小，所以我们不能直接用其差值进行误差的估量，进而采用

其中，由于B是扰动，所以 $\frac{\left |B \right |} {\left |A \right |}$本身很小，所以其上界如果很大，那么肯定是$\kappa$出了问题。

我们称$\kappa$为矩阵$A$的条件数。如果$\kappa$很小，那么其差值上界定然小，如果$\kappa$很大，那么其差值上界就很大，从而其真实的差值就可能大，就是病态矩阵。（注意定然和可能）。

至于这个“小”还是“大”，因为已经经过模的规范化了，所以不同矩阵之间也可以比较。

条件数为多少时才是凉态的？

这里其实可以做一个实验，编写代码画图，构造一些指定条件数的矩阵出来，观察其轻微扰动之后的差值。给出网友的结论：（第一步骤实验！）

首先奇异和病态没有必然的联系，良态、病态、条件数都要针对求解的问题而言，比如说矩阵求逆的性态和矩阵求特征值的性态就完全是两码事 　在2-范数扰动的意义下，矩阵求逆或者解线性方程组的时候奇异矩阵可以认为是最病态（无限病态）的矩阵，因为它有零奇异值（注意，这个问题的性态体现在奇异值而不是特征值） 　至于什么样的矩阵算病态，没有绝对的标准，因为大和小是相对的概念 　通常病态与否也与实际计算的机器精度有关，比如IEEE单精度下K=10^4算比较病态了，但在IEEE双精度下就算比较良态

Fourier

从基础数学的角度理解傅里叶变换

Foundamental Mathematics

以下来自 https://betterexplained.com/

1. 自然数E是所有增量的基数，如果指数为虚数即表示旋转。
2. Euler’s Formula表示的含义是啥，即分别从增量的形式，grid的形式，描述圆周运动。 $$\begin{equation}\label{1} e^{ix}=\cos{(x)} + i\sin{(x)} \end{equation}$$

   傅里叶变换是干啥的

   先阅读以下这里，用一句表示就是，我们可以借助傅里叶变换将收集到的信号分离成频率为(0hz,1hz…N-1hz)的正弦波。

   手写推导

About Matrix

About Algorithm Design

Abstract

听君一席话，在下如拨云见日，茅塞顿开啊（\狗头，可怜的楚团长）.本文符号记法随前文。上回提到，任何一个从$U->V$空间的线性变换T，在给定$U、V$的基$B、B’$之后，都有其矩阵表示$[T]_{BB’}$。现我们给出约束：

1. 输入空间等于输出空间：$U=V=R^{n}$。
2. 输入空间的基等于输出空间的基：$B=B’$。
   那么，如果$T$在$B=B’=B_{1}$的矩阵为$[T]_{B_1}$，$T$在$B=B’=B_{2}$的矩阵为$[T]_{B_2}$，记$P=[I]_{B_1B_2}$则
   \begin{equation}\label{1}
   [T]_{B_1} = P^{-1}[T]_{B_1}P
   \end{equation}
   而我们知道，对角矩阵就是线性代数的神，其拥有很多良好的性质，所以我们可不可以选择一组基，使得该线性变换的矩阵为对角矩阵呢？

这里先给结论：在结合上述约束的情况下，如果线性变换的矩阵有n个特征向量，那么就可以选择一组合适的基，使得该线性变换的矩阵表示为对角矩阵。

Invariant Subspaces

Definition

给定$U=V, \chi \subseteq V$， $\chi=R^{r}.r \leqslant n$，$T$是$V$上的线性算子，如果
\begin{equation}\label{2}
T(\chi)= \chi
\end{equation}
我们就称$\chi$是$V$中$T$下的不变子空间。说人话就是，$T$作用在$\chi$中的任一元素后，结果仍然在$\chi$中。

Restricted Operator

有了不变子空间的定义后我们很自然地可以引入restricted operator，由于$T$作用在$\chi$上与$V$中的其他元素无关，那么就好像$\chi$是一个baby $V$，我们定义一个只作用在$\chi$上的作用相同的变换$T_{/\chi}$。此即restricted operator。

The matrix representation of restricted operator

定义$\chi$的一组基为$B_x={x_1,x_2···x_r}$，故，根据线性变换基的矩阵表示的定义，可得：
\begin{equation}\label{3}
[A/\chi]_{B_x} = ([A/\chi(x_1)]_{B_x}|[A/\chi(x_2)]_{B_x}|···|[A/\chi(x_r)]_{B_x}])
\end{equation}

The matrix of $T$ involved $T/\chi$

如果我们把$\chi$的基$B_x$作为$V$输入基$B$的一部分，那么此时的$[T]_B$的形式是怎样的呢？emm..interesting.
令$B=(x_1,x_2…x_r,y_1,y_2…y_q)$是$V$的一组基，那么，
\begin{equation}\label{4}
[T]_B=([T(x_1)]_B|···|[T(x_r)]_B|[T(q_1)]_B···|[T(y_q)]_B)
\end{equation}

由于$x_1->x_r$是不依赖于后面的$y$的，所以
\begin{equation}\label{5}
\begin{matrix}
T(x_j)=\sum_{i=1}^{r}\alpha_{ij}x_i &
[T(x_j)]_B = \begin{pmatrix}
\alpha_{1j}\\
···\\
\alpha{rj}\\
0\\
···\\
0
\end{pmatrix}\end{matrix}
\end{equation}

\begin{equation}\label{6}
\begin{matrix}
T(y_j)=\sum_{i=1}^{r}\beta_{ij}x_i + \sum_{i=1}^{q}\gamma_{ij}y_i &
[T(y_j)]_B = \begin{pmatrix}
\beta_{1j}\\
···\\
\beta_{rj}\\
\gamma_{1j}\\
···\\
\gamma_{qj}
\end{pmatrix}\end{matrix}
\end{equation}

从而，可得出：
\begin{equation}\label{7}
[T]_B =
\begin{pmatrix}
\alpha_{11} & ··· & \alpha_{1r} & \beta_{11} & ··· & \beta_{1q}\\
·& ··· & · & · & ··· & ·\\
\alpha_{r1} & ··· & \alpha_{rr} & \beta_{r1} & ··· & \beta_{rq}\\
0& ··· & 0 & \gamma_{11} & ··· & \gamma_{1q}\\
·& ··· & · & · & ··· & ·\\
0& ··· & 0 & \gamma_{q1} & ··· & \gamma_{qq}
\end{pmatrix}
\end{equation}

左上角部分即为$[T_{/\chi}]_{B_{\chi}}$。

联想到特征向量以及特征空间

上面我们已经得出一般形式，不难发现，$[T]_B$的n个特征向量（前面我们的约束），都是$T$下的不变子空间，那么有意思的来了，把这n个特征向量作为$V$的基$B=(x_1,x_2,···,x_n)$，那么$[T]_B$的形式就是一个对角矩阵了，对角线元素为特征值$\lambda$，interesting。

Notation

1. $[T]_B$表示，以$B、B$为输入、输出基下，$T$变换的矩阵表示
2. $[I]_{BB’}$表示分别以$B、B’$为输入、输出基下，$I$变换的矩阵表示。
3. $[x_1]_{B’}$表示$x_1$这个object在$B’$下的坐标表示。上述

Abstract

关于基变换算子的一些理解，(秃头进行中…)基变换算子是什么，我们可以用基变换算子干嘛？

1. 用基变换算子，当然是对物体object进行基变换的鸭
2. 探索对于同一个线性变换，在给定不同的输入基以及输出基下，其对应的矩阵有什么联系

什么是基变换算子

这一点是我学习时非常困扰的一点，把一切抛之于脑后，不去想基变换，就把它看成是一种变换，这样就好解释了。首先我们说明：基变换是一种线性变换，这个自己验证即可，而一个从$U->V$的线性变换是客观存在的，只有当我们给定$U、V$的一组基后，这个线性变换的矩阵表示才被确定下来。

我们知道，给定$U、V$空间的一组基$B=[u_1,u_2…u_n]，B’=[v_1,v_2…v_m]$从$U->V$空间的任意线性变换$T$，都对应着一个矩阵表示。现在我们引出一个问题：基变换也是线性变换，那么我们给定一组基$B=[u_1,u_2…u_n]、B’=[v_1,v_2…v_n]$,基变换是从基$B1->B1’$，请问$B、B’$与$B1、B1’$之间都是基，那他们有什么联系呢？

这是我学习时非常非常困惑的一点，按照我的理解，这两者没有任何联系，他们所表示的内容是两个不同的概念：

把基变换算子就抽象出一个变换，其输入空间与输出空间都是$R^n$（管它什么基变换不变换的，就看成是一个变换），而一个线性变换要在给定输入空间的一组输入基、输出空间的一组输出基下，才能给出其唯一的矩阵表示。上面的输入、输出基，即是$B、B’$。那么可能就有人问了：“那$B1、B1’$是啥呢？”，我们只要把$B1与B1$’看作是这个线性变换里边儿的元素就可以了。

对应，李老师直接给出线性变换的定义：给定两个基$B=(x_1,x_2…x_n)，B’=(y_1,y_2…y_n)$。把$B$变换为$B’$的T表示为
\begin{equation}\label{1}
T(y_i)=x_i
\end{equation}

tips：上述定义之中的基$B、B’$是T要变换的东西，而不是T所在的基，好绕啊…

基变换算子的作用之一

假设$P$是一个基变换算子$T$的矩阵表示$P=[T]_{BB’}$，x是一个object，其在$B$下的坐标表示为$[x]_{B}$，其在$B’$下的坐标表示为$[x]_{B’}$，那么$[x]_{B’}=P·[x]_{B}$。

基变换算子的矩阵表示是啥

不给定输入基与输出基谈变换的矩阵表示都是耍流氓，上述我们给出了基变换算子的定义，却并未给出该变换输入空间的输入基，输出空间的输出基。来看一下这个表达式

\begin{equation}\label{2}
P=[T]_{BB}=[T]_{B’B’}=[I]_{BB’}=([x_1]_{B’}|[x_2]_{B’}|···|[x_n]_{B’})
\end{equation}

我个人觉得的就是，由于基变换算子太饶了，而我们可以用一个简单的形式来等价表示，即$[I]_{BB’}$，那我们就干脆用$[I]_{BB’}$来表示从B到B’的线性变换的矩阵了。

Prove Equation 3

根据定义，我们可以得到：

\begin{equation}\label{3}
T(y_i)=x_i=\sum_{j=1}^n \alpha_jy_j
\end{equation}

$[\alpha_1, \alpha_2···\alpha_n]$即表示$x_i$这个object，在$B’$下的坐标表示，即$\alpha=[x_i]_{B’}$。现在，我们同时考虑对等式3左右两边同时进行T变换：

\begin{equation}\label{4}
T(x_i)=\sum_{j=1}^n\alpha_j·T(y_j) = \sum_{j=1}^n\alpha_jx_j
\end{equation}

这个式子很有趣啊，表示$T(x_i)$在$B$下的坐标表示也为$\alpha$，即$\alpha=[T(x_i)]_{B}$，结合等式3，那么就是

\begin{equation}\label{5}
[x_i]_{B’} = [T(x_i)]_B
\end{equation}

这样我们可以得到如下：

\begin{equation}\label{6}
[T]_b = ([T(x_1)]_B,[T(x_2)]_B···[T(x_n)]_B) = ([x_1]_{B’},[x_2]_{B’}···,[x_n]_B’) = [T]_{B’}
\end{equation}

证明$[I]_{BB’}$与他们相等也很简单

\begin{equation}\label{7}
[I]_{BB’}=[[I(x_n)]_{B’},[I(x_2)]_{B’}···,[I(x_n)]_{B’}]=[[x_1]_{B’},[x_2]_{B’}···,[x_n]_{B’}]=[T]_{B’}
\end{equation}

我靠，这也太神奇了，从而，研究从$B->B’$的基变换算子，我们就可以研究$[I]_{BB’}$这个矩阵了。

基变换算子的作用之二

考虑这样一种情况，$A$是在$V$上的一个线性算子(linear operator)，$B、B’$分别是$V$的两组基，那么$[A]_B$与$[A]_{B’}$这两个矩阵既然表示同样线性变换，那么它们有什么联系呢？

\begin{equation}\label{8}
[A]_B = P^{-1}[A]_{B’}P
\end{equation}

where $P = [I]_{BB’}$，这个很好理解嘛，我们把两边都乘以$[x]_B$，即

\begin{equation}\label{9}
[A]_B[x]_B = P^{-1}[A]_{B’}P[x]_B
\end{equation}

学废了吗？因为这个东西，所以如果我们已知一个线性变换的矩阵表示$[A]_B$，那么我们通过变换基，可以得到其更好的矩阵表示形式$[A]_{B’}$，这样在特定情况下就可以方便问题求解了。（一定要注意：线性变换是客观存在的，上述讨论的只是线性算子，即输入空间、输出空间是一样的。并且仅考虑输入空间、输出空间的基也是一样的。就相当于控制变量嘛，有同学可能要问了，那诸如投影算子这些呢，它们输入、输出空间肯定不一样鸭。这种情况不在我们的讨论范围之内，因为这样的话它的矩阵表示肯定不是满秩了，肯定会有维度的损失。）

Abstract

我在上篇文章中复现了李老师的证明：“在给定基下，任意线性变换都有其对应的矩阵表示”。然后关于这个矩阵表示是啥就没有写了，近些日子有些盆友(大妹子！)来问小雷同学，想着还是写出来吧，矩阵表示也蛮trivial的，just as a remainder。

Notation

令$U$、$V$的基分别是{B = u₁, u₂,…,u_n}、{B’=v₁, v₂,…,v_m}。$(\xi_1, \xi_2…\xi_n)^T=[u]_B$(tips: 即object u在基B下的坐标表示)。$T$是从$U->V$的一个线性变化。目的: 需要求给定基下，该变换的矩阵表示$A$。

得出过程

换句话说，即一个Object$u$在$U$下坐标$[u]_B = (\xi_1, \xi_2…\xi_n)^T$，左乘$A$后$A[u]_B$为$u$在经过$T$变换后在$V$下的坐标表示$[u]_{B’} = (\sigma_1, \sigma_2…\sigma_m)^T$。

\begin{equation}\label{1}
u=\xi_1u_1+\xi_2u_2···\xi_nu_n
\end{equation}

我们知道

\begin{equation}\label{2}
T(u_1) = \sigma_{11}v_1+\sigma_{21}v_2+···+\sigma_{m1}v_m
\end{equation}
\begin{equation}\label{3}
T(u_2) = \sigma_{12}v_1+\sigma_{22}v_2+···+\sigma_{m2}v_m
\end{equation}
···
\begin{equation}\label{4}
T(u_n) = \sigma_{1n}v_1+\sigma_{2n}v_2+···+\sigma_{mn}v_m
\end{equation}

因为$T$是线性变换，所以
\begin{equation}\label{5}
T(u) = T(\xi_1u_1)+T(\xi_2u_2)+···+T(\xi_nu_n)
\end{equation}

根据线性变化，把它提出来，然后再展开，可以得到
\begin{equation}\label{6}
T(u_1) = \xi_1(\sigma_{11}v_1+···+\sigma_{m1}v_m) + \xi_2(\sigma_{12}v_1+···+\sigma_{m2}v_m) + \xi_n(\sigma_{1n}v_1+···+\sigma_{mn}v_m)
\end{equation}

以$V$提出公因式
\begin{equation}\label{7}
(\xi_1\sigma_{11}+\xi_2\sigma_{12}+···+\xi_n\sigma_{1n})v_1 + ··· + (\xi_1\sigma_{m1}+\xi_2\sigma_{m2}+···+\xi_n\sigma_{mn})v_m
\end{equation}

$v_i$的系数即是变换后的object在$V$上的系数，写成矩阵形式，其系数为

$
\begin{bmatrix}
\sigma_{11} &··· &\sigma_{1n} \\
···& ··· & ··· \\
\sigma_{m1}& ··· & \sigma_{mn}
\end{bmatrix}

\begin{bmatrix}
\xi_1\\
···\\
\xi_n
\end{bmatrix}
$

左边这个矩阵就是这个啦。
再次强调，$T(u_1)$里面的$u_1$始终表示的对象，同理，等式右边也是对象。注意我sigma下标的定义，后面自然就明白了。

abstract

今天上完liao(致敬)李保滨老师的矩阵分析课程，对线性变换有了更进一步的理解，李老师与Gilbert的课程还是有差异的，个人感觉Gilbert老师的18.06对线代的基础（4个基本子空间）讲的更透彻，而李老师再线性变换处更明了

prerequisite

矩阵乘法AB=C的意义、C的行列与A、B行列的关系、线性变换、向量空间。这要搞清楚，这里不展开。

基本概念

首先我们想一个问题，如何表示一个物体，其实小时候大家都做过这样的数学题，在坐标轴（笛卡尔棒棒）上对一些坐标标点，最后把这些点连起来，最终就会得到一个可爱的猫猫啦。可见，坐标可以用来描述物体。但是，仅仅是坐标就足够了吗。look, here’s the deal（poor Biden…），当然不是的，题目给出坐标时，默认了我们都在空间的标准基(standard basis)里。所以，除了坐标之外，我们还需要空间的基。

比如说，我们说一点(object)的coordinate是c = (1,2,3)，实际上我们默认是在说这个object = c1*e1 + c2*e2 + c3*e3。只是我们选择的基太tricky了，所以可以用coordinate stand for that object directly(important)。

这样，用基和坐标,就可以表述出我们的猫猫（客观物体object）了。

tips：Gilbert的书中貌似有点说不清楚object与coordinate的关系(当然是我太菜了)，李老师证明了：在给定基下，每一个线性变换都有其矩阵表示。

Prove: 在给定基下，每一个线性变换都有其矩阵表示

证明思路：联想到普通情况，令{e1, e2, e3}为$R^3$的基，我们如何证明在$R^3$空间中的任一目标，都能表示出来呢？obviously，令一个系数向量C(3x1)代表坐标，一个矩阵代表基B(3x3)，那么，BC就可以唯一表示这个object了。同理，李老师的证明过程如下：

1. $U$与$V$分别代表两个向量空间$U=R^n$, $V=R^m$，把从U->V的所有线性变换放到一个集合里，记作L(U, V)，那么L(U, V)是一个向量空间。
2. 令$U$、$V$的基分别是B={u₁, u₂,…,u_n}、B'={v₁, v₂,…,v_m}。定义$T_{ji}(u)=\xi_jv_i$，$(\xi_1, \xi_2…\xi_n)^T=[u]_B$(tips: 即object u在基B下的坐标表示)`，那么，我们可以得出下面结论3:
3. $ T_L = \left \{ T_{ji}\right \}_{j=1…n}^{i=1…m} $是L(U, V)的一组基。
4. 如果有了结论3，那么得证。 即给定空间U、V的基，任意一个从U -> V的线性变换，我们都可以用这组基$T_L$来表示，而表示的坐标coordinate，即是：在U、V的给定基下，从U -> V线性变换T的矩阵表示。

证明$ T_L = \left \{ T_{ji}\right \}_{j=1…n}^{i=1…m} $是L(U, V)的一组基

证明思路：1.$T_L$是线性无关的。2.$L(U, V)$中的任意一个元素，都能用$T_L$中的元素表示。

1.根据定义即证明$\sum_{j,i}\eta_{ji}T_{ji} = 0$中的所有$\eta_{ji}只能等于0$。这个鬼东西怎么证明呢，用到了一个小trick（tips:我这非数学专业就不去想那些老头子怎么想出来的了）
\begin{equation}\label{1}
T_{ji}(u_k) = \left\{\begin{matrix}
v_i & j=k\\
0 & j≠k
\end{matrix}\right.
\end{equation}

现在把要证的等式两端同时乘以$u_k$，即基组$U$的第k个基，得到
\begin{equation}\label{2}
(\sum_{j,i}\eta_{ji}T_{ji})(u_k) = 0
\end{equation}
去括号，相当于把$u_k$做${T_{ji}}$变换。
\begin{equation}\label{3}
\sum_{j,i}\eta_{ji}T_{ji}(u_k) = 0
\end{equation}
结合公式1，即可得出
\begin{equation}\label{4}
\sum_{i=1}^{m}\eta_{ki}v_i = 0
\end{equation}
因为${v_1,v_2,v_3..v_m}$是输出空间空间$V$的一组基底，所以所有 $\eta$ 都等于0，得证。

要证第二个，首先要搞清楚$L(U, V)$中的元素是什么,exactly。这个集合里面存放的是：从$U$ -> $V$的所有线性变换。

现从$L(U,V)$中任取一个元素$T’$，now, enjoying this formulation,hahaha
\begin{equation}\label{5}
T(u) = T(\sum_{j=1}^{n}\xi_ju_j) = \sum_{j=1}^{n}\xi_jT(u_j) = \sum_{j=1}^{n}\xi_j \sum_{i=1}^{m}\alpha_{ij}v_i = \sum_{i, j}\alpha_{ij}\xi_jv_i = \sum_{i, j}T_{ji}(u)
\end{equation}
非常漂亮的过程。

现在，我们想证明的都证明完了，就可以说, 在给定输入空间$U$、输出空间$V$，以及他们自个的基$B$、$B’$下，每一个从$U$到$V$的线性变换都有其矩阵表示。

Brain Expansion

上述表述有一个flaw我没有提，你看那个第3点，为什么我们要把$T_{ji}(u)=\xi_jv_i$, $(\xi_1, \xi_2…\xi_n)^T=[u]_B$, $ T_L = \left \{ T_{ji}\right \}_{j=1…n}^{i=1…m} $作为L(U, V)的一组基呢，它代表着啥含义。这点老师上课也没有讲(or 我走神了?)下面我简单分析一下

首先我们看一下这个表达式
\begin{equation}\label{6}
T_{ji}(u_k) = \left\{\begin{matrix}
v_i & j=k\\
0 & j≠k
\end{matrix}\right.
\end{equation}

将上面三个带入就发现这是成立的，即经过$T_{ki}$变换，$u_k$变换成了$v_i$，并且这个$T_{ki}$将其他的基$u_z(z≠k)$变成了0。穷举法，任意一个变换可能将原来空间的基$u_{1,2…n}$，变换成任意一个输出空间基的倍数$v_{1,2…m}$。所以，将这mxn朴素变换(我瞎说的词)进行线性组合，既可以组合成任意在给定输入空间$U$、输出空间$V$，以及他们自个的基$B$、$B’$下，从$U$到$V$的线性变换。想出这个证明的人，我愿称之为现代王！

再往下延拓就是如何将这个变换用矩阵表示出来了，具体做法也很简单，这里就不说了

Summary

我在读Gilbert的setction 8的时候，总是分不清其表达式$T(u)=u$的这两个u到底是代表的object还是coordinate。但是李老师讲解的过程$T(u)$很明确，就是说对object u 进行 $T$变换。不过遗憾的是，李老师这堂课的视频并没有放出来，我上面的东西估计只有我自己能看懂hhh，(tips: 大家不妨试试@一下UCAS的教务处^-^)。（再tips:上课已一月有余，北京的冷空气让我的厚衣服屁用都没有了)。

• 目的：在初步学习之后，已了解slurm平台工作流程，slurm实则是一个计算节点之间的管理工具，其本身并无计算能力，要实现计算的功能还需另外安装mpi的实现，此处安装openMPI。
• 准备：注意版本，slurm-17.02.11；openmpi-4.0.5，这套配置能够解决依赖问题。

一：准备工作

1.前三步骤见 https://giganticray.github.io/2020/07/13/%E7%94%A8ubuntu%E6%90%AD%E5%BB%BAslurm%E5%B9%B3%E5%8F%B0/

二：配置slurm

2.配置slurm
在slurm官方下载页面下载slurm（注意版本），在/opt下新建Slurm文件夹，默认是在/usr/local下的，但这样容易与其他程序搞混，故放在/opt下。二者差别可看这里。将下载的包解压，在解压目录执行

1
2
3
4
5
6
7
8
9
10

1. # 安装依赖
apt-get install hwloc libhwloc-dev libmunge-dev libmunge2 munge mariadb-server libmysqlclient-dev（slave节点不需要最后两个sql）
2. ./configure --prefix=/opt/Slurm (即指定目录安装)
3. sudo make install
4. # 安装完成后进入 slurm-xxxx/etc
cp slurm.conf.example slurm.conf, 然后根据上述博客进行配置，配置完成后将slurm.conf拷贝到集群所有节点上面
scp slurm.conf slave1@192.168.1.105:/tmp
5. # 在slave1节点将slurm.conf文件拷贝进入安装目录
cp /tmp/slurm.conf /home/slave1/slurmxxxx/etc
6. 将/opt/Slurm/sbin与/opt/Slurm/bin添加进环境变量 /etc/profile

配置文件解释可在这里

注意，见slurm.conf中有两个slurmctld.log与slurmd.log日志文件，需要自己手动创建。到这里slurm配置完成。

另外，可以在/opt/Slurm/sbin下执行sudo ./slurmctld -D(主节点)。sudo ./slurmd -D(计算节点)来验证是否成功。

三：配置openmpi

这就是为啥要选用slurm17版本的原因，slurm17x之后（具体多少搞忘了），其吧pmi.h分离了出去，我原先用slurm20版本的始终无法安装openmpi成功，吐了。
在openmpi官方下载包，新建/opt/OpenMPI

1 2 3

1. 解压后在解压目录执行 2. sudo ./configure --with-pmi=/opt/Slurm/include/slurm --with-pmi-libdir=/opt/Slurm/lib --prefix=/opt/OpenMPI CPPFLAGS=-I/opt/Slurm/include/slurm LDFLAGS=-L/opt/Slurm/lib 3. sudo make install

四: 问题汇总

1. 版本不匹配问题

   在slurm17以后，安装之后在/*/include/slurm下总是没有pmi.h，这样在安装openmpi的时候就会找不到pmi.h文件，安装失败，遂降低版本，查阅文件发现在slurm17以后，slurm官方就把pmi.h分离出来了，需要的话要另外编译，此处为了偷懒，就直接用以前的版本了。

2. openmpi编译成功后，但是在intall阶段处，出现缺少pmi.h的错误，查资料，在这里发现在编译openmpi的时候要另外加两个参数，遂加上，编译成功。

最近半月都在练习驾照、Iterative methods也间断地看完了第一章（期间配合着Gilbert的Linear圣经夯实了线代的基础）。今天学习Discretization of PDES。

参考书籍：Iterative methods for sparse linear system

一：初识

本章大致是在讲对偏微分方程进行离散化求近似解(当然，精确解我们能够用数值计算方法计算得出)。离散化的意思是用Taylor series expansion，将一个方程用幂函数之和来表示。关于Taylor series的解释，这个知乎问题下的高赞回答简直是经典！section 2.1介绍了两个经典的微分方程：椭圆操作器的Poisson方程、Convection Diffusion equation（对流扩散方程）。然后2.2开始介绍有限差分法，根据维基百科的定义，有限差分法即通过有限差分来近似导数、，从而求微分方程的近似解。

二：搁置

在阅读的过程中发现对新的数学基础有要求、先修一下ma691课程。

参考章节目录

1. Iteriative Methods for Sparse Linear Systems P12
2. MATH 5330: Computational Methods of Linear Algebra—Lecture Note 10: Householder Transformation—Xianyi Zeng—Department of Mathematical Sciences, UTEP

Abstract

关于A=QR的分解，有三种方法：Gram、Givens、Householder，Givens我不熟悉、但好像和旋转有关、可以保留A’s columns的长度。HouseHolder也有这个优点。

大致了解

Gram-Schmidt的方法是通过一步一步地将新的列A_j，减去其在已正交化的q₁，q₂，q_(j-1)的投影从而得到新的正交项以此构成Q，HouseHolder采取了另外一种完全的方法，其一步一步地将待分解矩阵A，分解成Echelon matrix，当然这个分解过程不是简单的Gaussian Decomposition，而是用了HouseHolder算子，下面翻译一下参考书目1中的分解步骤

什么是Householder算子（Householder矩阵的几何表示）

Householder算子是一个矩阵，其形式是P = I - 2ww^T，这里我一般记作P_w，因为P是由w决定的，后续我们也是针对待分解矩阵的每一列来构造对应的w，从而得出针对每一列的P。

易证，P是Ortogonal矩阵、且是Symmetric矩阵：P^T=P，P^TP=I。

注意，我们后续在选择w的时候，要让其是2-norm unity的向量。

从几何上来看，Px表示的就是x,关于空间{w}^⊥的镜像。画图表示就是

v就是上文中的w、H_v就是上文中的P_w。

如何为每一列X_j构造每一个HouseHolder矩阵P_j

• 针对向量x、构造其P_w

  一直在强调，HouseHolder矩阵P_j的作用就相当于Gaussian Elimination的消除矩阵（应该这么叫吧）。下面以第一列为例，假设第一列是x，那么目的肯定是
  
  α是一个张量，后面我们会知道其实就是x的长度。现在将P的表达式代入:
  
  
  

至此、我们就用通过x、求得了一个w，使得x在P_w的作用下可以变换至||x||e₁，w的表达式如下

• 针对矩阵的每一列，进行构造P

  先看矩阵的第一列x₁，我们直接用x₁替换掉1.17中的x，即得出w₁，从而得出P₁。记X₁是第一次HouseHolder变换后的矩阵（形如已经完成一次Gaussian Elimination的矩阵）
  
  X₁的第一个元素为α，其余元素为0。

现在我们看一下第k次HouseHolder变换的情况，操作对象当然是已经完成k-1次的矩阵了鸭。表达式如下：

矩阵在列k-1前是一个上三角矩阵。进行下一步时，前k-1列保持不变，根据第k列的向量x_k，确定一个w，然后生成P。w的形状是1至k-1个元素都是0，这样才保证了前k-1列不变。P_k的推导如下

当k=0时，即第一次变换的P，此时的β=αe₁，符合上文的描述。

构造A=QR

到这里，我们就描述完了整个X的分解过程，使得x可以分解成

这里仅需要一小步、就可以将上式变成A=QR的美丽式子了鸭。(下面这个过程，即将R那部分中的0，转移到P中去，形成Q).我们将1.22表示成下面的式子1.23，R是mxm的矩阵。

我们在前面给出了P_i是对称、且正交的，所以我们把P放到右边:

我们用E_m表示I的前m列，shape=(n,m)。可表示如下

令Q=P^TE_m，这表示取P^T的前m列。我们可以验证：

所以，Q是我们想要的Q(Orthonomal)。分解成功！

Pseudo Code

参考书籍：《统计学习方法》

参考网络资源：信息增益比details/82317369

熵的意义

书中P60描述，熵是表示随机变量不确定性的度量。that’s right，经常看见什么：“宇宙是熵增的”这种句子，实际上是在说，宇宙的发展过程，是慢慢从有序的状态，发展至无序的状态。这里熵的定义，就不难理解了，一个随机变量越随机，它的熵就越大。聪明的Rudolf Clausius归纳了这样一个表达式（将可见的现象，用抽象的数学公式表达出来，厉害）

关于这个表达式，承认就是了，书上P60给了一个很直观的例子，即随机变量X只有两个取值，每个取值的概率都是1/2的情况。很好理解

关于H(X)这个符号的解释

H(X)，X是一个随机变量，我们可以看作是一个集合。由于H(X)表示该集合的混乱程度，换句话说即从某种意义上表示了X的分布，所以可以用H(p)来表示。

关于条件熵表达式H(Y|X)的解释。

集合Y中的元素有很多个特征，每个特征的取值决定了集合中个体的类别。H(Y|X)就表示，我们在已经知道特征X的取值情况以后，集合Y的混乱程度。数学表达式为

解释：这个p_i即p(x=x_i)，如上所示，整个表达式表达的意思是，我们已经知道了X特征的分布情况下Y的混乱程度。

信息增益

信息增益就很简单啦，集合D的个体，有很多个特征，特征A对训练数据D的信息增益即：“集合D原来的熵、减去已知A的分布后集合D的熵”

信息增益比

决策树对应有几个经典的算法，区别就是他们采用的计算“信息增益”的方式不一样，c4.5采用的就是信息增益比的方式。

这里我们要承认一点：信息增益的方法，存在偏向于选择取值较多的特征的问题。如上文的例子中，如果以日期作为候选特征，那么它的信息增益很大（一想就通嘛，每天一个日期，就分出来了一个分支，分支下只有一个样本，那肯定是有序的啊），但是很明显，这样划分并没有什么用。造成这个的原因就是： 日期这个特征，可选择的取值较多。

解决办法：增加一个惩罚项。通常来说，增加一个惩罚项是用加法嘛，比如取值越多的特征，就给其信息增益减去一个数值。信息增益比这里用了除法。

惩罚原则：首先还是要保持要选择能够增益信息较大的特征，同时特征可选择的值越多，那么惩罚越大，把惩罚放到分母上，即分母越小。惩罚项是“A的内部信息(intrinsic information of an attribution)”，在我看来，这个惩罚项可以用D关于A的条件熵来替代吧，因为A的可取值选择越多、理应H(D|A)越小（即在A的帮助下D变得不再凌乱了）。或许只是H(D|A)计算麻烦才没有使用罢了。