Eufisky - The lost book

2018年考研试题

证明积分不等式:
 
\[\frac{1}{5}<\int_0^1\frac{xe^xdx}{\sqrt{x^2-x+25}}<\frac{2}{\sqrt{99}}.\]
 
证明  注意到
\[x^2-x+25=\left(x-\frac{1}{2}\right)^2+\frac{99}{4}>\frac{99}{4}, a.e. x\in [0,1],\]
从而
\[\int_0^1\frac{xe^xdx}{\sqrt{x^2-x+25}}<\frac{2}{\sqrt{99}}\int_0^1xe^xdx=\frac{2}{\sqrt{99}}.\]
另一方面, 分部积分, 得到
\[\int_0^1\frac{xe^xdx}{\sqrt{x^2-x+25}}=\frac{(x-1)e^x}{\sqrt{x^2-x+25}}\Big|_0^1+\int_0^1\frac{(x-1)(x-\frac{1}{2})e^x}{\sqrt{(x^2-x+25)^3}}dx=\frac{1}{5}+\int_0^1\frac{(x-1)(x-\frac{1}{2})e^x}{\sqrt{(x^2-x+25)^3}}dx.\]
\[f(x)=\frac{x-\frac{1}{2}}{\sqrt{(x^2-x+25)^3}},g(x)=(x-1)e^x,\]
\[f'(x)=\frac{-2x^2+2x+\frac{97}{4}}{\sqrt{(x^2-x+25)^5}}>0,\forall x\in [0,1],\int_0^1 f(x)dx=0, g'(x)=xe^x,\]
因此$f,g$在$[0,1]$上严格递增. 根据Chebyshev 积分不等式,
\[\int_0^1\frac{(x-1)(x-\frac{1}{2})e^x}{\sqrt{(x^2-x+25)^3}}dx=\int_0^1f(x)g(x)dx>\int_0^1 f(x)dx\int_0^1g(x)dx=0.\]
\[\int_0^1\frac{xe^xdx}{\sqrt{x^2-x+25}}>\frac{1}{5}.\]
最后得到
\[\frac{1}{5}<\int_0^1\frac{xe^xdx}{\sqrt{x^2-x+25}}<\frac{2}{\sqrt{99}}.\]

2018年武汉大学653数学分析
 
一(30分).1.计算极限$$\lim_{n\rightarrow\infty}\sum_{k=n^2}^{(n+1)^2}\frac1{\sqrt k}.$$
    2.计算极限$$\lim_{n\rightarrow\infty}\frac{\int_0^\mathrm\pi\sin^nx\cos^6x\operatorname dx}{\int_0^\mathrm\pi\sin^nx\operatorname dx}$$
    3.已知$x_{n+1}=\ln\left(1+x_n\right)$,且$x_1>0$,计算$$\lim_{n\rightarrow\infty}nx_n$$
 
二.设$f(x),f_1(x)$在$[a,b]$区间上连续,$f_{n+1}(x)=f(x)+\int_a^x\sin\{f_n(t)\}\operatorname dt$,证明:$\{f_n\}$在$[a,b]$一致收敛.
 
 
三.设$$f(x)=\left\{\begin{array}{lc}e^{-\frac1{x^2}}&,\;x\neq0\\0&,\;x=0\end{array}\right.$$证明$f(x)$在$x=0$处任意阶导数存在.
 
 
四.已知$(x_1,x_2,x_3)\in{R}^3$,其中$u=\frac1{\left|x\right|},\left|x\right|=\sqrt{x_1^2+x_2^2+x_3^2}$,计算
$$\oint\limits_S\frac{\partial^2 u}{\partial x_i\partial x_j}{\rm d}S,i,j=1,2,3$$,其中$S:x_1^2+x_2^2+x_3^2=R^2$
 
五.讨论求解方程$f(x)$牛顿切线法.1.推导牛顿切线法迭代公式;
                                                   2.在适当的条件下,证明牛顿切线法收敛
 
六(20分).求极限$$\lim_{n\rightarrow\infty}(nA-\sum_{k=1}^nf(\frac kn))=B$$存在时,$A,B$的值。
 
七.设$u_i=u_i(x_1,x_2),i=1,2$,且关于每个变量为周期1的连续可微函数,求$$\iint\limits_{0\leq x_1,x_2\leq1}det(\delta_{ij}+\frac{\partial u_i}{\partial x_j})dx_1dx_2,$$其中$det(\delta_{ij}+\frac{\partial u_i}{\partial x_j})$是映射$x\mapsto(x_1+u_1,x_2+u_2)$的雅克比行列式.
 
八(40分).设$f(x)$在$[a,b]$上$Riemann$可积,$\varphi(x)$是周期为$T$的连续函数,证明:
        1.存在阶梯函数$g_\varepsilon(x)$使得$$\int_a^b\left|f(x)-g_\varepsilon(x)\right|\operatorname dx<\frac\varepsilon2$$
        2.计算$$\lim_{n\rightarrow\infty}\int_a^b\varphi(nx)\operatorname dx$$
        3.证明$$\lim_{n\rightarrow\infty}\int_a^bf(x)\varphi(nx)\operatorname dx=\frac1T\int_0^T\varphi(x)\operatorname dx\int_a^bf(x)\operatorname dx$$
        4.计算$$\lim_{n\rightarrow\infty}\frac1{\ln n}\int_0^T\frac{\varphi(nx)}xdx,其中函数\frac{\varphi(nx)}x收敛$$

试题(1b):证明\[\lim_{n\to +\infty}\left(\int_0^1\frac{\sin x^n}{x^n}dx\right)^n=\prod_{k=1}^{+\infty}\exp{\left(\frac{(-1)^k}{2k(2k+1)!}\right)}\]
 
作代换$x^n=y$
\[\int_0^1\frac{\sin x^n}{x^n}dx=\frac{1}{n}\int_0^1\frac{\sin y}{y^{2-\frac{1}{n}}}dy\]
\[\int_0^1 y^{\frac{1}{n}-2}\sum_{k=0}^{+\infty}\frac{(-1)^k}{(2k+1)!}y^{2k+1}dy=\int_0^1 y^{\frac{1}{n}-1}dy+\int_0^1\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}y^{2k-1+\frac{1}{n}}dy\]
容易得到
\[\int_0^1 y^{\frac{1}{n}-1}dy=n,\left|\frac{(-1)^k}{(2k+1)!}y^{2k-1+\frac{1}{n}}\right|\le \frac{1}{(2k+1)!}\]
由优级数判别法后一项中的函数项级数一致收敛,可以逐项积分,上式
\[=n+\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\int_0^1 y^{2k-1+\frac{1}{n}}dy=n+\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}\]
最终我们得到
\[\int_0^1\frac{\sin x^n}{x^n}dx=1+\frac{1}{n}\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}\]
取对数,要证明的表达式化为
\[\lim_{n\to+\infty}n\ln \left(1+\frac{1}{n}\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}\right)=\sum_{k=1}^{+\infty}\left(\frac{(-1)^k}{2k(2k+1)!}\right)\]
\[\left|\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}\right|\le \sum_{k=1}^{+\infty}\frac{1}{(2k+1)!}<+\infty\]
\[\lim_{n\to+\infty}\frac{1}{n}\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}=0\]
\[\lim_{n\to+\infty}n\ln \left(1+\frac{1}{n}\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}\right)=\lim_{n\to+\infty}\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+\frac{1}{n}}\]
现在我们希望极限与级数和交换顺序,考虑$[0,1]$上的函数项级数
\[f(x)=\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k+x}\]
仍然由优级数判别法一致收敛,故由$\mathrm{Heine}$定理原式
\[=\lim_{n\to +\infty}f(\frac{1}{n})=f(0)=\sum_{k=1}^{+\infty}\frac{(-1)^k}{(2k+1)!}\frac{1}{2k}\]
作者: TangSong    时间: 昨天 02:00
 
试题(1c):证明
 
\[\lim_{n\to +\infty}\frac{1}{n}\sum_{k=1}^n\ln(1+\frac{k^2-k}{n^2})=\ln 2-2+\frac{\pi}{2}\]
注意到下面式子中第一项是一个$\mathrm{Riemann}$和我们有
\[\lim_{n\to +\infty}\frac{1}{n}\sum_{k=1}^n\ln(1+\frac{k^2}{n^2})=\int_0^1\ln(1+x^2)dx=x\ln(1+x^2)\left|_0^1\right.-\int_0^1\frac{2x^2}{1+x^2}dx=\ln 2-2+\frac{\pi}{2}\]
我们只需要再证明
\[\lim_{n\to +\infty}\frac{1}{n}\sum_{k=1}^n\ln(1+\frac{k^2-k}{n^2})=\lim_{n\to +\infty}\frac{1}{n}\sum_{k=1}^n\ln(1+\frac{k^2}{n^2})\]
利用不等式
\[x,y\ge 0,\left|\ln(1+x)-\ln(1+y)\right|=\left|\frac{x-y}{1+\xi}\right|\le|x-y|\]
\[\left|\frac{1}{n}\sum_{k=1}^n\ln(1+\frac{k^2-k}{n^2})-\frac{1}{n}\sum_{k=1}^n\ln(1+\frac{k^2}{n^2})\right|\le \frac{1}{n}\sum_{k=1}^n\left|\ln(1+\frac{k^2-k}{n^2})-\ln(1+\frac{k^2}{n^2})\right|\]
\[\le \frac{1}{n}\sum_{k=1}^n\frac{k}{n^2}=\frac{n+1}{2n^2}\to 0\]
作者: TangSong    时间: 昨天 02:54
试题(8)
$f(x)$在$[1,+\infty)$上二次可导,$\forall x\in [1,+\infty),f(x)>0,f''(x)\le 0,f(+\infty)=+\infty$
证明
\[\lim_{s\to 0^+}\sum_{n=1}^{+\infty}\frac{(-1)^n}{f^s(n)}\]
存在并求之.
 
由二阶导数非正,$f'(x)$在$[1,+\infty)$单减,容易看出$f'$恒正.事实上若有某个$x_0,f'(x_0)\le 0$则由单调性
\[\forall x\ge x_0,f'(x)\le f'(x_0)\le 0,f(x)\le f(x_0)\]与$f(+\infty)=+\infty$矛盾.因此$f$在$[1,+\infty)$严增.
我们将收敛性的证明与求值放在一起进行.
\[S_{2n}(s)=\sum_{k=1}^n \left(\frac{1}{f^s(2k)}-\frac{1}{f^s(2k-1)}\right)\]
注意和式中每个括号都是负的且级数通项趋于$0$,只需要证明对固定的$s>0,S_{2n}(s)$有下界则
\[\lim_{n\to +\infty}S_{2n}(s)\]存在且等于
\[\sum_{n=1}^{+\infty}\frac{(-1)^n}{f^s(n)}\]
由$\mathrm{Lagrange}$中值定理,
\[\frac{1}{f^s(2k)}-\frac{1}{f^s(2k-1)}=\frac{-sf'(\xi)}{f^{s+1}(\xi)},\xi\in (2k-1,2k)\]
注意$f$单增而$f'$单减我们有
\[\frac{-sf'(2k-1)}{f^{s+1}(2k-1)}\le\frac{1}{f^s(2k)}-\frac{1}{f^s(2k-1)}\le \frac{-sf'(2k)}{f^{s+1}(2k)}\]
\[\sum_{k=1}^n\frac{-sf'(2k-1)}{f^{s+1}(2k-1)}\le S_{2n}(s)\le \sum_{k=1}^n\frac{-sf'(2k)}{f^{s+1}(2k)}\]
利用面积原理的思想来估计左右两端.
由单调性$k\ge 2$时
\[\frac{f'(2k-1)}{f^{s+1}(2k-1)}\le \frac{1}{2}\int_{2k-3}^{2k-1} \frac{f'(t)}{f^{s+1}(t)}dt\]
\[\sum_{k=2}^{+\infty}\frac{f'(2k-1)}{f^{s+1}(2k-1)}\le\frac{1}{2}\int_{1}^{+\infty} \frac{f'(t)}{f^{s+1}(t)}dt=\frac{1}{2}\frac{-1}{sf^s(t)}\left|_{t=1}^{t=+\infty}\right.=\frac{1}{2sf^s(1)}\]
 
$S_{2n}(s)$有下界故极限存在.再次利用面积原理
$k\ge 1$时
\[\frac{f'(2k)}{f^{s+1}(2k)}\ge \frac{1}{2}\int_{2k}^{2k+2} \frac{f'(t)}{f^{s+1}(t)}dt\]
\[\sum_{k=1}^{+\infty}\frac{f'(2k)}{f^{s+1}(2k)}\ge\frac{1}{2}\int_{2}^{+\infty} \frac{f'(t)}{f^{s+1}(t)}dt=\frac{1}{2}\frac{-1}{sf^s(t)}\left|_{t=2}^{t=+\infty}\right.=\frac{1}{2sf^s(2)}\]
 
\[-s\left(\frac{f'(1)}{f^{s+1}(1)}+\frac{1}{2sf^s(1)}\right)\le \lim_{n\to +\infty}S_{2n}(s)\le -s\frac{1}{2sf^s(2)}\]
由前面说明就有
\[-s\left(\frac{f'(1)}{f^{s+1}(1)}+\frac{1}{2sf^s(1)}\right)\le \sum_{n=1}^{+\infty}\frac{(-1)^n}{f^s(n)}\le -s\frac{1}{2sf^s(2)}\]
而上式左右两端在$s\to 0^+$时极限都是$-\frac{1}{2}$故
\[\lim_{s\to 0^+}\sum_{n=1}^{+\infty}\frac{(-1)^n}{f^s(n)}=-\frac{1}{2}\] 

中科院2018研究生入学考试 数学分析+高等代数
数学分析部分
 
01. (15pt) 计算极限
\[\lim_{x\to\infty}\left(\sin\frac1x+\cos\frac1x\right)^{x}\text{.}\]
02. (15pt) 计算极限
\[\lim_{x\to 0} \left(\frac{4+\mathrm{e}^{\frac1x}}{2+\mathrm{e}^{\frac4x}}+\frac{\sin x}{|x|} \right)\text{.}\]
03. (15pt) 判断 (并证明) 函数 $f(x,y)=\sqrt{|{xy}|}$ 在点 $(0,0)$ 处的可微性.
 
04. (15pt) 求三个实常数 $a,b,c$,使得下式成立
\[\lim_{x\to 0}\frac1{\tan x -ax}\int_b^x\frac{s^2}{\sqrt{1-s^2}}\,\mathrm{d}s =c\text{.}\]
05. (15pt) 计算不定积分
\[\int\frac{\mathrm{d}x}{\sin^6 x+\cos^6 x}\text{.}\]
06. (15pt) 设函数 $f(x)$ 在 $[-1,1]$ 上二次连续可微,$f(0)=0$,证明:
\[
\left|\int_{-1}^1 f(x)\,\mathrm{d}x\right|\leq\frac{M}{3},\quad \text{其中 }M=\max_{x\in[-1,1]}\left|f''(x)\right|\text{.}
\]
07. (15pt) 求曲线 $y=\dfrac12x^2$ 上的点,使得曲线在该点处的法线被曲线所截得的线段长度最短.
 
08. (15pt) 设 $x>0$,证明
\[\sqrt{x+1}-\sqrt{x}=\frac1{2\sqrt{x+\theta}}\text{,}\]其中 $\theta=\theta(x)>0$,并且 $\lim\limits_{x\to 0}\theta(x)=\dfrac 14$.
 
09. (15pt) 设
\[u_n(x)=\frac{(-1)^n}{(n^2-n+1)^x}\quad (n\geq 0)\text{,}\]求函数 $f(x)=\sum\limits_{n=0}^{\infty}u_n(x)$ 的绝对收敛、条件收敛以及发散的区域.
 
10. (15pt) 证明
\[\frac15<\int_0^1\frac{x\mathrm{e}^x}{\sqrt{x^2-x+25}}\,\mathrm{d}x<\frac{2\sqrt{11}}{33}\text{.}\]
 
高等代数部分
 
一、(20pt) 设 $p(x),q(x),r(x)$ 都是数域 $\mathbb{k}$ 上的正次数多项式,而且 $p(x)$ 与 $q(x)$ 互素,$\mathrm{deg}(r(x))<\mathrm{deg}(p(x))+\mathrm{deg}(q(x))$.证明:存在数域 $\mathbb{k}$ 上的多项式 $u(x),v(x)$,满足 $\mathrm{deg}(u(x))<\mathrm{deg}(p(x)),\,\mathrm{deg}(v(x))<\mathrm{deg}(q(x))$,使得
\[\frac{r(x)}{p(x)q(x)}=\frac{u(x)}{p(x)}+\frac{v(x)}{q(x)}\text{.}\]
二、(20pt) 设 $n$ 阶方阵 $M_n=\left(|i-j|\right)_{1\leq i,j \leq n}$,令 $D_n=\mathrm{det}(M_n)$ ($M_n$ 的行列式).
  (1) 计算 $D_4$;
  (2) 证明 $D_n$ 满足递推关系式 $D_n=-4D_{n-1}-4D_{n-2}$;
  (3) 求 $n$ 阶方阵 $A_n=\left(\left|\frac1i-\frac1j\right|^{\llap{\phantom{b}}}\right)_{1\leq i,j \leq n}$ 的行列式 $\mathrm{det}(A_n)$.
 
三、(20pt) 设 $A,B$ 均是 $n$ 阶方阵,满足 $AB=0$.证明
  (1) $\mathrm{rank}(A)+\mathrm{rank}(B) \leq n$;
  (2) 对于方阵 $A$ 和正整数 $k\,(\mathrm{rank}(A) \leq k \leq n)$,必存在方阵 $B$,使得
\[\mathrm{rank}(A)+\mathrm{rank}(B)=k\text{.}\]
四、(20pt) 通过正交变换将下面的实二次型化成标准型:
\[q(x_1,x_2,x_3)=5x_1^2+5x_2^2+5x_3^2-2x_1x_2-2x_2x_3-2x_1x_3\text{.}\]
五、(20pt) 设 $A$ 和 $B$ 是两个 $n$ 阶实矩阵,并且 $A$ 是对称正定矩阵,$B$ 是反对称矩阵.证明:$A+B$ 是可逆矩阵.
 
六、(20pt) 设 $A$ 是 $n$ 阶复数矩阵,且 $A=\left(\begin{array}{l} A_1\\ A_2\end{array}\right)$,令
\[V_1=\left\{\,x\in\mathbb{C}^n\,\middle|\,A_1 x=0\,\right\},\quad V_1=\left\{\,x\in\mathbb{C}^n\,\middle|\,A_2 x=0\,\right\}\text{,}
\]证明:矩阵 $A$ 可逆的充分必要条件是向量空间 $\mathbb{C}^n$ 能够表示成子空间 $V_1$ 与 $V_2$ 的直和:$\mathbb{C}^n=V_1 \oplus V_2$.
 
七、(15pt) 证明:$8$ 个满足 $A^3=0$ 的 $5$ 阶复数矩阵中必有两个相似.
 
八、(15pt) $\mathbb{R}$ 上所有 $n\,(n\geq 2)$ 阶方阵构成的线性空间 $V=\mathbb{R}^{n \times n}$ 上的线性变换 $f:\, V \to V$ 定义为
\[f(A)=A+A'\quad \forall A\in V\text{,}\]其中 $A'$ 为 $A$ 的转置.求 $f$ 的特征值、特征子空间、极小多项式.

第九题的解答
 
 
9.  设 $B_R=\{(x,y): x^2+y^2< R^2\},u\in C^2( B_R)\cap C(\overline {B_R})$ .
 
1) 若$\Delta u\geqslant 0$, 证明
\[\max_{(x,y)\in\overline {B_R}} u(x,y)= \max_{(x,y) \in \partial B_R} u(x,y).\]
 
证明 对任意$\varepsilon>0$, 令$v_\varepsilon
(x,y)=u(x,y)+\varepsilon (x^2+y^2)$, 则
\[\Delta v_\varepsilon (x,y)=\Delta u(x,y)+4\varepsilon\geqslant 4\varepsilon.\]
由此用反证法易证
\[\max_{(x,y)\in\overline {B_R}} v_\varepsilon (x,y)= \max_{(x,y) \in \partial B_R} v_\varepsilon(x,y).\]
令$\varepsilon\to 0^+$, 即得
\[\max_{(x,y)\in\overline {B_R}} u(x,y)= \max_{(x,y) \in \partial B_R} u(x,y).\]
 
 
2).  若$\Delta u(x,y)=0$, 则
\[\frac{d}{dr}\left(\frac{1}{2\pi r}\int_{\partial B_r}u(x,y)ds\right)=0, 0\leqslant r\leqslant R.\]
 
 
证  注意到
\[\frac{1}{2\pi r}\int_{\partial B_r}u(x,y)ds=\frac{1}{2\pi}\int_0^{2\pi}u(r\cos\theta,r\sin\theta)d\theta=
\int_{\partial B_1}u(rx,ry)ds.\]从而根据Gauss公式, 得到
 
\begin{align*}\frac{d}{dr}\left(\frac{1}{2\pi r}\int_{\partial
B_r}u(x,y)ds\right)&=\frac{1}{2\pi}\int_{\partial B_1}(u_x(rx,ry)x+u_y(rx,ry)y)ds\\
&=\frac{1}{2\pi}\int_{\partial B_1} \frac{\partial
u(rx,ry)}{\partial
\nu}ds\\
&=\frac{1}{2\pi}\iint\limits_{\overline B_1}\Delta
u(rx,ry)dxdy\\
&=0.\end{align*}
3).  证明 若$\Delta u(x,y)=0$, 则
\[u(0,0)=\frac{1}{2\pi r}\int_{\partial B_r}u(x,y)ds.\]
 
证 根据2), 得到
\[\frac{1}{2\pi r}\int_{\partial B_r}u(x,y)ds=\lim_{r\to 0^+}\frac{1}{2\pi r}\int_{\partial B_r}u(x,y)ds=u(0,0).\]

2017-2018学年北京大学高等代数实验班期末试题2018.1.9
2018.1.9 上午8:30--10:30\\

安金鹏

据悉今年使用的教材是 K. Hoffman, R. Kunze: Linear Algebra

反响好我再发出期中试卷

一、设矩阵$A\in \mathbb{R}^{4\times 4}$的矩阵元均为$1$或$-1$, 求$\det A$的最大值.

二、设$V$是所有从有限域$F_p$到自身的映射构成的$F_p$-线性空间. 定义$T, U\in L(V)$为
$$ T(f)(t)=f(-t), \ \  U(f)(t)=f(t+1)-f(t), \ \ \forall \ f\in V, t\in F_p.$$
求$\det T$和$\det U$.

三、设$V$是有限维$F$-空间, $W$是$V$的子空间, $T\in L(V)$满足$T(W)\subset W$. 定义$T_W\in L(W)$和$T_{V/W}\in L(V/W)$为
$$T_W(\alpha)=T(\alpha), \alpha\in W,$$
$$T_{V/W}(\alpha+W)=T(\alpha)+W, \alpha\in V.$$
证明$\det T=\det T_W \det T_{V/W}$.

四、设$A\in F^{n\times n}$, $V$和$W$是$F^n$的子空间. 证明下述等价:

(a) 对任意的$a\in V-\{0\}$, 存在$\beta\in W$使得$\alpha A\beta^t\neq 0$.

(b) 对任意的$\gamma\in F^n$, 存在$\beta\in W$使得对任意的$\alpha\in V$有$\alpha V\beta^t=\alpha\gamma^t$.

五、设$F$是无限域. 证明对多项式代数$F[x]$的任意有限维子空间$V$, 存在$F[x]$的理想$M$满足
$$V\cap M=\{0\}, \ \ \ V+M=F[x].$$

 

“火腿三明治定理”是什么?

中华民族是一个懂得谦让、不拘小节的民族。正是在这种民族思想的熏陶下,才出现了孔融让梨这种传送千年的佳话。与中华民族的谦让和大气不同,西方国家的朋友却相对严谨。他们更加追求获得公平的机会,不管是男女权利的平等还是法律面前人人平等,都很好地展现了西方国家民众对于公平的追求,这种追求甚至也延伸到了我国民众最不挂怀的事物的平均上。
 
在西方国家中,要说到最常见的事物,三明治绝对能占据一席之地。因此,这种美食的平均分配也成为了外国人重点关注和解决的问题。你别说,外国人还真发明了解决平分三明治的科学定理,而且这个定理的名字真的就叫做“火腿三明治定理”(ham sandwich theorem),由此可见外国人对于追求平等和喜欢吃三明治的程度。
 
这个著名而有意思的”火腿三明治定理”(ham sandwich theorem)的诞生可不是信口开河胡诌的,而是经过专业人士的严谨科学论证得出的结果。得出这一理论的是数学家亚瑟斯通(Arthur Stone)和约翰图基(John Tukey)在 1942 年得出的,而且是测度论中的经典理论。
 
该定理是:任意给定一个火腿三明治,总有一刀能把它切开,使得火腿、奶酪和面包片恰好都被分成两等份。
 
当然,作为一个可定定理,著名的“火腿三明治定理”(ham sandwich theorem)绝不仅仅用来解决平分三明治的问题。该理论产生之后,又被进行了进一步延伸,即如果在n维空间中有n个物体,那么总存在一个n-1维的超平面,它能把每个物体都分成“体积”相等的两份。这些物体可以是任何形状,还可以是不连通的(比如面包片),甚至可以是一些奇形怪状的点集,只要满足点集可测就行了。
 
由此也可以看出,那些看起来十分有趣或者简单的科学理论,很有可能是借助复杂的理论获得的,也有可能被拓展成为复杂和高深的理论。当然,对于那些吃货来说,只要这个理论能成功地帮助他们平分火腿三明治中的火腿、奶酪和面包片就行了。
 
 
http://vip8.wall.49109.com/v2/web/index.php?c=site&a=entry&eid=113

醉鬼能回家,但喝醉的鸟儿可能永远回不了家!

A drunk man will find his way home, but a drunk bird may get lost forever.  —— Kakutani
醉鬼总能找到回家的路;但是喝醉了的鸟儿可能永远回不了家。 —— 角谷静夫
 
 
 
 
今天我们要谈的是一个概率论中的重要结论:Z^d上的随机游走当d≥3时是非常返的,而当d=1,2时是常返的。
 
Z^d在这里表示由d 维欧氏空间中全体整点(即坐标全为整数的点)构成的集合。想象有一只青蛙以秒为时间单位在Z^d上做随机游走,那么它将按如下规则运动:在初始时刻(记为第0秒),青蛙位于原点;在每一秒钟,青蛙都会等概率地跳到某一个与它上一秒所在位置相邻的整点。由于Z^d上的每个整点都有2d个邻居,因此这个概率也就是1/(2d)(见下图)。
 
我们这里介绍的随机游走看似一个简单的数学模型,其实它的应用十分广泛。最常见的例子有物理学中布朗运动,金融市场中股票价格波动等等。
 
那么我们的问题就是,既然青蛙一开始位于原点,那是否总存在一个(随机)时刻T,使得第T秒时青蛙又回到原点呢?如果是,那么我们就称这样随机游走是“常返”的,否则就称是“非常返”的。
 
 
 
事实上,我们总可以假设存在一个介于0和1之间的实数p,它就是青蛙回到原点的概率。仔细想想,其实p的存在性本身也是不平凡的,因为我们知道古典概率论中,事件的概率只涉及到有限个变量,而这里回到原点的行为却与青蛙在无穷时间内的行为有关。当然,在公理化概率论中,通过建立起合适的概率空间,我们可以说明这样的p是存在的。这样,我们通过引入p,判断常返性就转化为判断p是否等于1的问题了,因为“总能回到原点”用概率论的语言来说就是“以概率1回到原点”。
 
下面我们来看随机游走另一个有趣的性质:马氏性。我们注意到,对于任意给定的时刻,比如第100秒,第100秒后的青蛙的位置只取决于第100秒时青蛙的位置,而前100秒的时间里,青蛙如何跳到这一位置方式无关。这就是所谓的“马氏性”,即给定现在,未来和过去独立。随机游走还具有“强马氏性”。所谓“强马氏性”,是指可以把前述的“第100秒”换成任意“只取决于历史的随机时间”(这样的时间又叫停时)。比如我们定义T成为青蛙第一次回到原点的时刻,那么T就是一个停时,并且关于T的强马氏性可以这么理解为:在随机时间T之后发生的事情,与在随机时间T之间发生的事情无关,因为我们知道在第T秒,青蛙又回到原点了,所以在时间T后开始的随机游走与一开始从原点出发的随机游走将遵循同样的规律。
 
如果要解释什么叫“只取决于历史”,不妨看一个买卖股票的例子。比如说你今天想卖出一只股票,你当然希望可以在一天当中最高价的时候卖。但很遗憾,除了碰运气,这是不可能做到的,因为除非一天已经结束了,没人能知道股价什么时候位于最高点。相反,如果你的策略是,“如果股票价格位于过去12个小时内的最高点就卖出股票”,那这就是一个可行的策略。后面这个策略中的交易时间就是一个“只取决于历史”的随机时间,也就是停时,而前者“一天当中的最高价”则不是停时。
 
如果你没看懂上面一大串关于马氏链和停时的描述,没关系,你一定也可以直观地理解以下结论。如果从原点出发的青蛙以概率p会回到原点,那么青蛙一定会以概率p^2(p^n表示p的n次方,下文相同)回到原点两次,这是因为,青蛙回到原点两次=青蛙回到原点1次+青蛙从原点出发再回到原点1次。由强马氏性,拆分后的第二个事件的(条件)概率也是p;因此,青蛙回到原点两次的概率就是p^2。同理,青蛙会以概率p^3回到原点3次,以概率p^4回到原点4次,等等。如果我们把青蛙回到原点的总次数记为N,那么上面的计算表明P(N≥k) = p^k,也就是说N是一个服从几何分布的随机变量。当p=1时,上述论证依然成立,只不过我们得到的N是一个取值恒为+∞的随机变量。
 
于是,根据几何分布的期望公式,我们得到了N的期望为EN = 1/(1-p);同样地,当p=1时,该式理解为EN=+∞。因此,EN是有限还是无穷,就刻画了随机游走是否常返。
 
我们还可以从另一个角度来计算EN。令X(n)为第n秒青蛙所在的位置,而an是取值0和1的随机变量,其中a(n)=1当且仅当X(n)=0,即a(n)=1当且仅当第n秒青蛙位于原点。根据定义我们得到N是全体a(n)的和,也就是N=a(1) + a(2) +…+ a(n) +… 这是显然的,因为整个数列(a(n))中有多少个1,就代表青蛙返回了多少次原点。
 
当我们对以上无穷和式取期望,并根据期望的线性性,交换无穷求和与求期望的顺序(这里能够换序是因为涉及的项an都是非负的,因此满足换序的条件),我们得到
 
EN = E(a(1) + a(2) +…+ a(n) +…) = E a(1)  + E a(2) +...+E a(n) +...
 
等等,E a(n)  是什么呢?根据定义,E a(n) = P(X(n)= 0),正是第n秒青蛙恰好位于原点的概率!计算这个概率就是一个组合问题了,而判断常返性则变成了一个判断无穷级数敛散性的问题。
 
记A(n)= E a(n) = P(X(n)= 0)。下面我们的目标就是对A(n)进行估计,并由此判断无穷级数∑A(n)是否收敛。
 
在一维(d=1)时,如何计算A(n)呢?注意到每一秒钟青蛙必须向左跳或者向后跳。因此在第n秒回到原点的必要条件就是n为偶数。而当n为偶数时,青蛙必须恰好有n/2的时间向左跳,有n/2的时间向右跳,才能在第n秒回到原点。我们知道每秒钟青蛙向左和向右的概率都是1/2,那么利用组合数公式,我们就得到
 
 
对于阶乘,斯特林公式给出了渐近公式:m! ∼(m/e)^n·sqrt(2πn) (sqrt表示开二次根号,下同)。代入A(n)的表达式,我们得到A(n)∼1/n·sqrt(2/π)这个渐近关系当然只限于n为偶数)。微积分中熟知的结论是p级数∑1/n^p收敛当且仅当p>1,否则发散。于是我们得到∑A(n)在d=1时发散,也就是说一维随机游走是常返的。
 
如果我们在高维时采用类似的方法,就能得到A(n) ∼ c· n^(-d/2),其中c是与d有关的一个常数。同样再借助p级数的知识,就能得到当且仅当d/2 > 1时,也就是d ≥3时,随机游走不常返;相反,d=1,2时,随机游走常返。
 
为了避免复杂的组合数估计,我们也可以从另一个简单的事实中看出A(n)的阶就是n^(-d/2)。如果我们令y(n)=X(n)-X(n-1)为第n秒时青蛙的位移,容易看出所有y(n)都是独立同分布的随机单位向量。由中心极限定理,Z(n) :=X(n)/sqrt(n) = (y(1) + y(2) + … y(n))/sqrt(n)将趋向于一个d维正态分布Z。那X(n)=0意味着什么呢?由于X(n)只能取整点,那么X(n)= 0表明Z(n)的取值大约位于原点附近一个边长为的1/sqrt(n)小正方体中。根据中心极限定理,Z(n)的取值落于这个小正方体中的概率与Z是差不多的,而对于后者,这样的概率恰恰就约等于小正方体的体积,(1/sqrt(n))^d(注意到是d维空间),乘以原点处Z的密度函数大小,一个非零的常数。这样我们就很容易得到了A(n) ∼ c· n^(-d/2)这个结论。
 
如果要把这个随机游走的小结论用于生活中,我们也许会为再也不用担心认不得路而感到欣慰,因为二维随机游走是常返的,就算是不认识路随便乱走,也总能到达任何想去的地方!当然这句话既对也错;对的地方在于,由常返性,确实总存在一个时间T,在平面上随机游走的你也能走到任意想去的地方;错的地方在于,更进一步的理论表明,这个随机时间T是一个期望为无穷的随机变量,也就是从平均的意义上说,你永远也到不了目的地!
 
作者:小米

拉格朗日乘数法

咏怀古迹五首·其一
杜甫
 
支离东北风尘际,漂泊西南天地间。
三峡楼台淹日月,五溪衣服共云山。
羯胡事主终无赖,词客哀时且未还。
庾信平生最萧瑟,暮年诗赋动江关。
 
 一个好的外科医生不应该总是在进行补救式的英雄行为,而是应该预测和预防这些不必要的行为。
 
还记得扁鹊三兄弟的故事吗?
 
根据典记,魏文王曾求教于名医扁鹊:「你们家兄弟三人,都精于医术,谁是医术最好的呢?」
 
扁鹊:「大哥最好,二哥差些,我是三人中最差的一个。」
 
魏王不解地说:「为什么呢?请你详细解释下。」 
 
扁鹊说:
 
「大哥治病,是在病情发作之前,那时候病人自己还不觉得有病,但大哥就下药铲除了病根,使他的医术难以被人认可,所以没有名气,只是在我们家中被推崇备至;
 
我的二哥治病,是在病初起之时,症状尚不十分明显,病人也没有觉得痛苦,二哥就能药到病除,使乡里人都认为二哥只是治小病很灵;
 
我治病,都是在病情十分严重之时,病人痛苦万分,病人家属心急如焚。此时,他们看到我在经脉上穿刺,用针放血,或在患处敷以毒药以毒攻毒,或动大手术直指病灶,使重病人病情得到缓解或很快治愈,所以我名闻天下。」
 
魏王大悟。
 
拉格朗日乘数法(Lagrange multiplier)有很直观的几何意义。举个2维的例子来说明:假设有自变量x和y,给定约束条件g(x,y)=c,要求f(x,y)在约束g下的极值。我们可以画出f的等高线图,如下图。此时,约束g=c由于只有一个自由度,因此也是图中的一条曲线(红色曲线所示)。显然地,当约束曲线g=c与某一条等高线f=d1相切时,函数f取得极值。两曲线相切等价于两曲线在切点处拥有共线的法向量。因此可得函数f(x,y)与g(x,y)在切点处的梯度(gradient)成正比。于是我们便可以列出方程组求解切点的坐标(x,y),进而得到函数f的极值。
(相切的时候碰到最高的等高线)
作者:卢健龙
链接:https://www.zhihu.com/question/38586401/answer/105273125
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相亲问题与倒向归纳法

问题假设你是一位大龄男士,准备参加 100 场相亲(别介意具体数字)。你打算依次与每个女士 i 约会,然后根据印象给她打一个分数 X_iX_i 的值介于 [0,1] 之间。如果你对女士 i 很满意,那么就和她结婚,否则就放弃她,参加下一场相亲,当然拒绝了人家可就没有回头的机会了。如果你拒绝了前 99 位女士,那么不论第 100 次相亲结果如何你都只能和最后这位女士结婚。在相亲之前,你对这些女士的情况一无所知,所以姑且假定她们的分数 X_i 都是 [0,1] 上均匀分布的独立的随机变量。问题是:应该采取怎样的相亲策略,才能娶到你最中意的女士?

再费点笔墨解释下。每次相亲结束以后,你可以选择和当前的女士结婚,或者继续见下一位女士,这依赖于你已经相亲的结果:如果你挑挑拣拣到了 90 号女士还拿不定注意,最后发现 “天啊,我快要变剩男了!” 那很可能接下来你就会放低择偶标准,遇到一个还凑合的就结婚了,即使她比你前面拒绝过的很多女士都有不如。当然也不排除你对第一位女士就一见钟情的可能,因此你最终选择的女士的编号 \tau 是一个随机变量,你要做的就是让你的未来太太的期望分数 \mathbb{E}X_\tau 尽可能的高。

那么应该采取怎样的策略为好呢?就像买东西讨价还价时总有一个心理价位一样,应该设定一个心理的期望值,如果遇到的女士的分数大于等于这个值,那就和她结婚;否则就继续下一位女士。这个思路很合理,但是问题是,期望值应该设定为多少呢?

在概率论里面我们学过如下关于顺序统计量的经典结论:设 X_1,\cdots,X_N 是 [0,1] 上独立同分布的均匀随机变量,则 Y=\max\limits_{1\leq i\leq N}X_i 的期望是 \frac{N}{N+1}。在我们的场景中 N=100,所以如果你把 100 次相亲全部进行完,得分最高的女士的期望值理论上应该是 \frac{100}{101},于是你应该把心理门槛设置在 \frac{100}{101},是这样吗?

答案是 NO!首先门槛值应该是一个随着相亲的进行而逐渐降低的数列,这才符合实际的情形:如果前面太挑剔,为了不当剩男你后面的标准就会放低。其次我们会用倒向归纳法计算出最优策略下初始的门槛值并不是最中意的女士的期望值 \frac{100}{101},实际上它更接近于得分第二高的女士的期望值 \frac{99}{101}。这也和现实相符:和你结婚往往不是你最中意的那一个,这就是为什么有那么多婚外情的故事。(The story of the other woman)

倒向归纳法

相亲问题是应用倒向归纳法的一个典型例子。

我们从最后的情形开始分析,假设只剩下一位女士可选,那么你只能去和她结婚,而她的期望值是 1/2,我们记作 a_1=1/2

假设还剩下两位女士可选呢?这种情况下应该先和其中一个相亲,如果她的分数大于等于 1/2,那就应该和她结婚(后者的期望只有 1/2,很可能不如她),而小于 1/2 的话则去和第二位女士相亲(后者的期望是 1/2,所以我没道理现在娶一个分数小于 1/2 的)。而第一位女士分数大于等于 1/2 的概率是 1/2,在大于等于 1/2 的条件下她的分数服从 [1/2,1] 上的均匀分布,期望值是 3/4。所以你以 1/2 的概率娶到一个期望值为 3/4 的女士,以 1/2 的概率娶到一个期望值为 1/2 的女士。因此有两位女士可选时这个策略的期望分数为

a_2=\frac{1}{2}\cdot\frac{3}{4}+\frac{1}{2}\cdot\frac{1}{2}=\frac{5}{8}.

 

同理,假设还剩下 i 位女士的时候你的心理期望值是 a_i, 我们来导出 a_i 和 a_{i+1} 之间的递推关系:首先和其中一位女士相亲,如果她的分数大于等于 a_i 那么就和她结婚,否则就拒绝她(因为后面 i 个人的心理期望是 a_i,我没道理现在娶一个分数小于 a_i 的)。前一种情形的期望是 \frac{1+a_i}{2} 但是发生的概率是 1-a_i,后一种情形的期望是 a_i 发生的概率也是 a_i,因此

a_{i+1}=(1-a_i)(\frac{1+a_i}{2})+a_i\cdot a_i=\frac{1+a_i^2}{2}.

结合初值 a_1=\frac{1}{2} 就可以算出整个序列来,因此我们的相亲策略应该是:

 

如果当前女士(假设编号为 i)的得分大于等于 a_{101-i},那么就和她结婚;否则就继续去见下一位女士。这里序列 \{a_i\} 由 a_1=1/2a_{i+1}=\frac{1+a_i^2}{2} 给出。

在这个策略下,你最终娶到的女士得分期望是 a_{100}

序列 \{a_n\} 的通项公式是求不出来的,只能用计算机来算,这种序列叫做所谓的 Quadratic Map。不过可以估计出 a_{N} 的值小于最优女士的期望值 \frac{N}{N+1} 而且更接近于次优女士的期望值 \frac{N-1}{N+1},这印证了之前说过的:和你结婚的往往不是你最中意的那个。

请注意,虽然我们已经设计出了一个不错的策略,但这个策略到底是不是最优的呢?我们还没有严格证明。而且就算这个策略是最优的,是否只有这一种最优策略呢?没准还有其它最优策略能让你更省时省心地娶到好太太呢!要严格的解释这些,就要用到鞅的理论。

FBI Warning: 接下来的内容要用到概率论中鞅的知识,这通常属于数学专业研究生阶段的内容。

转换为鞅的语言

问题:设 N 是一个给定的正整数,\{\mathcal{F}_n\}_{n=0}^N 是某概率空间上的递增的 \sigma- 域流,\{X_n\}_{n=0}^N 是一列可积的随机变量且 X_k\in\mathcal{F}_k。设 \mathcal{M} 是所有满足 0\leq\tau\leq N 的停时 \tau 组成的集合。我们想求出值函数

V= \sup_{\tau\in\mathcal{M}} \mathbb{E}X_\tau
以及使得这个最大值取到的停时 \tau

 

定义 \{X_n\} 的 Snell 包络

S_n=\left\{\begin{array}{ll}X_N&n=N\\\max\{X_n,\mathbb{E}[S_{n+1}|\mathcal{F}_n]\}& n=N-1,\ldots,0.\end{array}\right.

这里的 S_n 是从 N 开始倒向递归定义的。注意 S_n 关于 \mathcal{F}_n 可测。

 

S_n 的直观意义很好理解,就是在时刻 n 对最佳收益的估计:如果过程在当前时刻结束,那么收益就是 X_n;否则继续前进到下一个时刻 n+1,其期望收益是 \mathbb{E}[S_{n+1}|\mathcal{F}_n](注意这里的条件期望不可少,一般来说 \{X_n\} 之间不是独立的,根据前 n 个时刻获得的信息不同,你在 n+1 时刻对最佳收益的估计也可能不同),二者取最大值即为 n 时刻对最佳收益的估计。

设 \tau=\inf\,\{n:\, S_n=X_n\},则 \tau 是停时。注意由于 S_N=X_N,因此 \tau 的定义合理且 0\leq\tau\leq N\tau 的直观意义就是我们应该采取的最优停止策略:每个时刻,用当前的 X_n 与未来的期望收益 \mathbb{E}[S_{n+1}|\mathcal{F}_n] 比较,见好就收。

定理 1\{S_n\} 是控制 \{X_n\} 的最小上鞅。

证明:由 S_n 的定义直接可见 S_n\geq X_n 以及 \{S_n\} 是上鞅。设 \{Y_n\} 是另一个上鞅且满足 Y_n\geq X_n,我们要证明必有 Y_n\geq S_n。这只要从最后一项 n=N 开始看即可。由定义 Y_N\geq X_N=S_N,这一项没问题。假设 Y_n\geq S_n,两边对 \mathcal{F}_{n-1} 取条件期望可得

Y_{n-1}\geq \mathbb{E}[Y_n|\mathcal{F}_{n-1}] \geq \mathbb{E}[S_n|\mathcal{F}_{n-1}].

其中第一个不等号是因为 \{Y_n\} 是一个上鞅。再结合 Y_{n-1}\geq X_{n-1} 便有 Y_{n-1}\geq S_{n-1},这样递推下来就有 Y_n\geq S_n 对所有 n=N,N-1,\ldots,0 成立。证毕。

 

那么怎么证明 \tau 确实是最优的停止策略呢?想法是这样的:设 T 是任意停时,我们要证明 \mathbb{E}X_\tau\geq \mathbb{E}X_T,为此我们利用 \{S_n\} 和 \{X_n\} 的关系,给式子中间塞进去两项,搭一座桥:

\mathbb{E}X_\tau = \mathbb{E}S_\tau \geq \mathbb{E}S_T\geq \mathbb{E}X_T.

注意第一个等号是根据 \tau 的定义,最后一个不等号是根据定理 1。所以我们只要证明中间的不等号 \mathbb{E}S_\tau\geq \mathbb{E}S_T 即可。

 

我们已经知道 \{S_n\} 是一个上鞅,那么自然不管什么停时 T,统统都有 \mathbb{E}S_T\leq \mathbb{E}S_0。但是关于 \tau 我们可以说的更多:

定理 2\{S_{n\wedge\tau}\} 是一个鞅。

证明

S_{(n+1)\wedge\tau}-S_{n\wedge\tau}=1_{\{\tau>n\}}(S_{n+1}-S_n).

 

对上式右边求条件期望,

\mathbb{E}[1_{\{\tau>n\}}(S_{n+1}-S_n)|\mathcal{F}_n]=1_{\{\tau>n\}}\mathbb{E}[(S_{n+1}-S_n)|\mathcal{F}_n]=0.

 

这是因为如果 \tau>n 的话那么由 \tau 的定义 S_n=\mathbb{E}[S_{n+1}|\mathcal{F}_n]

既然如此,那么就有 \mathbb{E}S_\tau=\mathbb{E}S_0,这样就证明了 \tau 的最优性:

定理 3:设 \mathcal{M} 是所有满足 0\leq T\leq N 的停时 T 组成的集合,则 \tau 是其中最优的:

\mathbb{E}S_0=\mathbb{E}X_\tau=\sup_{T\in\mathcal{M}}\mathbb{E}X_T.

 

至此我们就从数学上严格的论证了为什么前面相亲问题中我们设计的策略是最优的。

如果你回顾一下上面的分析就会发现,我们实际上使用了 \tau 的两个性质:S_\tau=X_\tau和 \{S_{n\wedge\tau}\} 是鞅。这两个性质就保证了 \tau 是最优的停时。那么这是不是说明还有其它最优的策略呢?

定理 4\nu\in\mathcal{M} 是最优停时的充要条件是: 1. S_\nu=X_\nu。 2. \{S_{n\wedge\nu}\} 是鞅。

定理的必要性告诉我们前面采用的 “见好就收” 策略是所有最优停时中最小的:设 \nu 是任一最优停时,则 \tau\leq\nu(回顾一下 \tau 的定义)。换句话说,我们之前设计的相亲策略是所有最优策略中时间成本最低的!

我们还可以给出最优停止策略中 “最大” 的一个来:

定理 5:设 S_n=M_n+A_n 是 \{S_n\} 的 Doob - Meyer 分解,其中 \{M_n\} 是鞅,A_n 是可料递增过程,定义

\tau_\max = \begin{cases}N & A_N=0,\\ \inf\{n\ |\ A_{n+1}>0\} & A_N>0.\end{cases}
则 \tau_\max 是所有最优停时中最大的。

 

定理 4,5 的证明都不难,这里就省略了。

参考文献

Risk-Neutral Valuation: Pricing and Hedging of Financial Derivatives. By Nicholas H. Bingham, Rüdiger Kiesel.

Hurwitz 平方和定理

Hurwitz 平方和定理是有限群表示论的一个精彩应用,本文是若干年前读书时的笔记。
 
Hurwitz 平方和定理
我们都熟悉复数的乘法:如果 z_1=x_1+y_1i,z_2=x_2+y_2i 是两个复数,则 |z_1z_2|=|z_1|\cdot|z_2|,也就是
(x_1^2+y_1^2)(x_2^2+y_2^2)=(x_1x_2-y_1y_2)^2+(x_1y_2+x_2y_1)^2.
1748 年 Euler 发现了如下的 4 平方和等式:
(x_1^2+x_2^2+x_3^2+x_4^2)(y_1^2+y_2^2+y_3^2+y_4^2)=z_1^2+z_2^2+z_3^2+z_4^2.
其中
\begin{align*}&z_1=x_1y_1-x_2y_2-x_3y_3-x_4y_4,\\&z_2=x_1y_2+x_2y_1+x_3y_4-x_4y_3,\\&z_3=x_1y_3+x_3y_1-x_2y_4+x_4y_2,\\&z_4=x_1y_4+x_4y_1+x_2y_3-x_3y_2.\end{align*}
4 平方和等式说的是在 Hamilton 四元数体中范数仍然是乘性的。1848 年 Caley 发现了八元数,从而导出了类似的 8 平方和等式,当然具体写出来会很复杂,这里就按下不表了。
 
一般地,如果能在 n 维欧式空间 \mathbb{R}^n 上定义向量之间的乘法:
\mathbb{R^n}\times\mathbb{R^n}\rightarrow\mathbb{R^n}:(v,w)\rightarrow v\times w
使得 v\times w 对 v,w 都是线性的,而且乘积的范数等于范数的乘积:|v\times w|=|v|\cdot |w|(这里 |\cdot| 是通常的欧式范数),则我们就得到了一个 n 平方和等式。
 
在接下来的 50 年里,人们一直致力于寻找可能的 16 平方和等式,但是都失败了,于是开始怀疑是否没有这样的等式成立。终于在 1898 年 Hurwitz 证明了这样的结论:
 
Hurwitz 平方和定理:设 x=(x_1,\ldots,x_n), y=(y_1,\dots,y_n) 为 \mathbb{R}^n 中的向量。如果存在关于 x,y 的双线性函数 z_1(x,y),\ldots,z_n(x,y) 使得等式
(x_1^2+\cdots+x_n^2)(y_1^2+\cdots+y_n^2)=z_1^2+\cdots+z_n^2
恒成立, 那么 n=1,2,4,8。
正如前面说过的,Huiwitz 平方和定理说的是在实数域 \mathbb{R},复数域 \mathbb{C},四元数 \mathbb{H} 和八元数 \mathbb{O} 中,元素的(欧式)范数和向量的乘法是相容的,而在其它维数的 \mathbb{R}^n 上是不可能定义与欧式范数相容的向量乘法的。
 
Hurwitz 本人的证明是纯线性代数的,线性代数的证明较为初等,不过步骤略长。1943 年 Eckmann 用有限群表示论的方法给了一个漂亮的证明,本文就来介绍这个证明。
 
将问题转化为矩阵方程
 
设 z=(z_1,\ldots,z_n),则 z 关于 y 是线性的,因此存在 n 阶矩阵 A 满足 z=yA,当然矩阵 A 和 x 有关。于是 Hurwitz 定理中的等式变成
(x_1^2+x_2^2+\cdots+x_n^2)yy'=yAA'y'.
由于 y 是不定元,因此
AA'=(x_1^2+\cdots+x_n^2)I_n.
进一步,由于 A 关于 x 也是线性的,因此设 A=A_1x_1+\cdots+A_nx_n,则
AA'=\sum_{i=1}^nA_iA_i'x_i^2+\sum_{1\leq i<j\leq n}(A_iA_j'+A_jA_i')x_ix_j.
从而我们得到一组矩阵方程
A_iA_i'=I_n,\quad A_iA_j'+A_jA_i'=0 \quad \text{for}\ i\ne j.
进一步可以把 A_n 归一化为单位矩阵:令 Q_i=A_iA_n^{-1},于是 Q_1,\ldots,Q_{n-1} 满足
Q_i'=-Q_i,\quad Q_i^2=-I_n,\quad Q_iQ_j=-Q_jQ_i\quad\text{for}\ i\ne j.
显然 n 必须是偶数(奇数阶反对称矩阵行列式都是 0),而 n=2 的时候结论是成立的,所以下面我们都假定 n>2,于是 n 的可能值为 4,6,8,\ldots
 
用群表示论的工具得出矛盾
 
考虑这样一个抽象群 G,它由元素 a,g_1,\ldots,g_{n-1} 生成,且
a^2=1,\quad g_i^2=a,\quad g_ig_j=ag_jg_i\ \text{when}\ i\ne j.
这个群的结构很好分析:
 
|G|=2^n,每个元素形如 a^{e_0}g_1^{e_1}\cdots g_{n-1}^{e_{n-1}},其中 e_i\in\{0,1\}。
G 的中心 Z(G)=\{1,a,g_1g_2\cdots g_{n-1},ag_1g_2\cdots g_{n-1}\}。
G 的换位子群 [G,G]=\{1,a\},从而 G 有 2^{n-1} 个线性表示。
G 的任何非平凡共轭类都只有两个元素 \{g,ag\},从而 G 有 2^{n-1}+2 个共轭类,其不可约复表示的个数也是 2^{n-1}+2。
于是我们知道 G 有 2^{n-1} 个一次表示,还有 2 个次数大于 1 的表示,设它俩的次数分别是 f_1,f_2,根据不可约表示次数的平方和等于 G 的阶,得到方程
f_1^2+f_2^2 =2^{n-1}.
再利用不可约表示的次数整除 G 的阶,知道 f_1 和 f_2 都是 2 的幂,这只有一种可能,就是
f_1=f_2=2^{\frac{n}{2}-1}.
 
现在 Hurwitz 矩阵方程给出了 G 的一个 n 维表示,这个表示可以分解为若干不可约表示的直和,我们断言其中不含有一次表示,从而只能是若干个 2^{\frac{n}{2}-1} 次表示的直和:这是因为元素 a 在这个表示下是 n 阶矩阵 -I_n,从而其在任何不变子空间上的作用都是乘以 -1。但是任何一次表示都把 a\in [G,G] 映射为 1,矛盾!
 
于是 2^{\frac{n}{2}-1}\big| n,设 n=2^r\cdot s,其中 s 为奇数,则 \frac{n}{2}-1\leq r,从而
2^r\leq n\leq 2r+2.
注意 n 是偶数,所以只能是 n=4,6,8,这就完成了 Hurwitz 定理的证明。

连分数理论

1.

向老师的题目

计算积分
\[\int_0^1{\frac{1}{1+a^2x^2}\left[\left(1-\frac{x}{2}\right)\ln\frac{1+x}{1-x}+\frac{\pi^2x^2}{4}\right]^{-1}\textrm{d}x}.\]

解.先作换元$x\to\tanh x$,可得

\begin{align*}&\hspace{0.5cm}\int_0^1{\frac{1}{1+a^2x^2}\left[\left(1-\frac{x}{2}\right)\ln\frac{1+x}{1-x}+\frac{\pi^2x^2}{4}\right]^{-1}\textrm{d}x}\\&=\int_0^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\left(\frac{\coth ^2x-1}{\left(\coth x-x\right)^2+\frac{\pi^2x^2}{4}}\right)\textrm{d}x}\\&=\frac{1}{2}\int_{-\infty}^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\left(\frac{\coth ^2x-1}{\left(\coth x-x\right)^2+\frac{\pi^2x^2}{4}}\right)\textrm{d}x}\end{align*}
于是我们考虑函数$$\displaystyle{f\left(z\right)=\frac{1}{1+a^2\coth ^2z}\cdot\frac{\tanh  ^2z-1}{\tanh  z-z}}$$ 的如下围道积分
注意到$\displaystyle{f\left(z\right)=\frac{1}{1+a^2\coth ^2z}\cdot\frac{\tanh  ^2z-1}{\tanh  z-z}}$ 的极点为$z=0$,$\displaystyle{z=\pm\frac{\pi}{2}\mathrm{i}}$ (这两个极点在围道边界上),以及$1+a^2\coth ^2z=0$的根$\displaystyle{z=\pm\mathrm{i}\cdot\mathrm{arccoth}\left(\frac{\mathrm{i}}{a}\right)=\pm\mathrm{i}\cdot\arctan(a)}$, 因此根据留数定理有
\begin{align*}&\int_{ - \infty  - \frac{\pi }{2}{\rm{i}}}^{\infty  - \frac{\pi }{2}{\rm{i}}} {f\left( z \right){\rm{d}}z}  - \int_{ - \infty  + \frac{\pi }{2}{\rm{i}}}^{\infty  + \frac{\pi }{2}{\rm{i}}} {f\left( z \right){\rm{d}}z} \\&= 2\pi {\rm{i}}\left( {{\rm{Res}}\left[ {f\left( z \right),z = 0} \right] + \left( {{\rm{Res}}\left[ {f\left( z \right),{\rm{i}} \cdot \arctan \left( a \right)} \right] + {\rm{Res}}\left[ {f\left( z \right),z =  - {\rm{i}} \cdot \arctan \left( a \right)} \right]} \right)} \right)\\&+ \pi {\rm{i}}\left( {{\rm{Res}}\left[ {f\left( z \right),z = \frac{\pi }{2}{\rm{i}}} \right] + {\rm{Res}}\left[ {f\left( z \right),z =  - \frac{\pi }{2}{\rm{i}}} \right]} \right)\\&= 2\pi {\rm{i}}\left( {\frac{3}{{{a^2}}} - \frac{a}{{2\left( {a - \arctan \left( a \right)} \right)}} - \frac{a}{{2\left( {a - \arctan \left( a \right)} \right)}}} \right) + \pi {\rm{i}}\left( {1 + 1} \right)\\&= 2\pi {\rm{i}}\left( {\frac{3}{{{a^2}}} - \frac{{\arctan \left( a \right)}}{{a - \arctan \left( a \right)}}} \right).\end{align*}
注意到$\displaystyle{\tanh  \left(z\pm\frac{\pi}{2}\textrm{i}\right)=\coth z,\coth \left(z\pm\frac{\pi}{2}\textrm{i}\right)=\tanh  z}$,于是
\begin{align*}&\int_{-\infty -\frac{\pi}{2}\textrm{i}}^{\infty -\frac{\pi}{2}\textrm{i}}{f\left(z\right)\textrm{d}z}-\int_{-\infty +\frac{\pi}{2}\textrm{i}}^{\infty +\frac{\pi}{2}\textrm{i}}{f\left(z\right)\textrm{d}z}=\int_{-\infty}^{\infty}{f\left(x-\frac{\pi}{2}\textrm{i}\right)\textrm{d}x}-\int_{-\infty}^{\infty}{f\left(x+\frac{\pi}{2}\textrm{i}\right)\textrm{d}x}\\&=\int_{-\infty}^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\cdot\frac{\coth ^2x-1}{\coth x-\left(x-\frac{\pi}{2}\textrm{i}\right)^2}\textrm{d}x}-\int_{-\infty}^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\cdot\frac{\coth ^2x-1}{\coth x-\left(x+\frac{\pi}{2}\textrm{i}\right)^2}\textrm{d}x}\\&=-\pi\textrm{i}\int_{-\infty}^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\cdot\frac{\coth ^2x-1}{\left(\coth x-x\right)^2+\frac{\pi^2}{4}}\textrm{d}x}=2\pi\textrm{i}\left(\frac{3}{a^2}-\frac{\arctan\left(a\right)}{a-\arctan\left(a\right)}\right).\end{align*}
因此
\begin{align*}\int_0^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\cdot\frac{\coth ^2x-1}{\left(\coth x-x\right)^2+\frac{\pi^2}{4}}\textrm{d}x}&=\frac{1}{2}\int_{-\infty}^{\infty}{\frac{1}{1+a^2\tanh  ^2x}\cdot\frac{\coth ^2x-1}{\left(\coth x-x\right)^2+\frac{\pi^2}{4}}\textrm{d}x}\\&=\frac{\arctan\left(a\right)}{a-\arctan\left(a\right)}-\frac{3}{a^2}\end{align*}
 
在开始本文之前,积分镇楼
\[\int_0^1{x^{20}\left[ \left( 1-\frac{x}{2}\ln \frac{1+x}{1-x} \right) ^2+\frac{\pi ^2x^2}{4} \right] ^{-1}\text{d}x}=\frac{5588512716806912356}{374010621408251953125}\]
下面的这些问题其实最开始来自1998年的美国数学月刊征解题
结果1998年的期刊没有答案,1999年以后的期刊又无处可寻,于是我就自己想办法解决这几个题目.我想了好久,突然想到我在前面某一期公众号上解决过类似的问题,于是灵感来了,解决了这几个征解题的同时还导出了几个额外的式子.

设$\displaystyle{\mathrm{Si}(x)=\int_0^x\frac{\sin t}t\mathrm dt}$表示正弦积分函数,求和

\[\sum_{n=1}^\infty\frac{\mathrm{Si}(n\pi)}{n^3}\]

解.[原创]

首先利用分部积分得
\begin{align*}\text{Si}\left( n\pi \right) &=\int_0^{n\pi}{\frac{\sin t}{t}\text{d}t}=\int_0^{\pi}{\frac{\sin nx}{x}\text{d}x}=\int_0^{\pi}{\sin nx\text{d}\left( \ln x \right)}=-n\int_0^{\pi}{\cos nx\ln x\text{d}x}\\&=-n\int_0^{\pi}{\cos nx\text{d}\left( x\ln x-x \right)}=n\left[ \left( -1 \right) ^{n-1}\left( \pi \ln \pi -\pi \right) -n\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x} \right]\end{align*}
于是我们可得
\[\sum_{n=1}^{\infty}{\frac{\text{Si}(n\pi)}{n^3}}=\sum_{n=1}^{\infty}{\frac{\left( -1 \right) ^{n-1}}{n^2}\left( \pi \ln \pi -\pi \right)}-\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x}}\]
而$\displaystyle{\sum_{n=1}^\infty\frac{(-1)^{n-1}}{n^2}=\frac{\pi^2}{12}}$,把后一部分式子再分部积分得
\begin{align*}\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x}}&=\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\sin nx\text{d}\left( \frac{1}{2}x^2\ln x-\frac{3}{4}x^2 \right)}}\\&=\sum_{n=1}^{\infty}{\int_0^{\pi}{\left( \frac{3}{4}x^2-\frac{1}{2}x^2\ln x \right) \cos nx\text{d}x}}.\end{align*}
现在考虑函数\[f\left( x \right) = \left\{ {\begin{array}{*{20}{c}}{\frac{3}{4}{x^2} - \frac{1}{2}{x^2}\ln x,}&{x \in \left( {0,\pi } \right]}\\{0,}&{x = 0}\end{array}} \right..\]作偶对称以后再作$2\pi$周期延拓,则$f(x)$的Fourier余弦级数为
\[\widetilde{f}\left( x \right) =\frac{a_0}{2}+\sum_{n=1}^{\infty}{a_n\cos nx}\]
其中$\displaystyle{a_n=\frac{2}{\pi}\int_0^{\pi}{f\left( x \right) \cos nx\text{d}x}=\frac{2}{\pi}\int_0^{\pi}{\left( \frac{3}{4}x^2-\frac{1}{2}x^2\ln x \right) \cos nx\text{d}x}}$,根据Fourier级数收敛定理可知
\[\frac{a_0}{2}+\sum_{n=1}^{\infty}{a_n}=f(0)=0\]
而$\displaystyle{a_0=\frac2\pi\int_0^{\pi}{\left( \frac{3}{4}x^2-\frac{1}{2}x^2\ln x \right) \text{d}x}=\frac{11}{18}\pi ^2-\frac{1}{3}\pi ^2\ln \pi}$,因此
\[\sum_{n=1}^{\infty}{\int_0^{\pi}{\left( \frac{3}{4}x^2-\frac{1}{2}x^2\ln x \right) \text{d}x}}=\frac{\pi}{2}\sum_{n=1}^{\infty}{a_n}=-\frac{\pi}{4}a_0=\frac{\pi ^3}{12}\ln \pi -\frac{11}{72}\pi ^3\]
于是最后得到
\[\sum_{n=1}^{\infty}{\frac{\text{Si}\left( n\pi \right)}{n^3}}=\frac{\pi ^2}{12}\left( \pi \ln \pi -\pi \right) -\left( \frac{\pi ^3}{12}\ln \pi -\frac{11}{72}\pi ^3 \right) =\frac{5\pi ^3}{72}\]
同样道理我们还能得到
\[\sum_{n=1}^{\infty}{\left( -1 \right) ^n\frac{\text{Si}\left( n\pi \right)}{n^3}}=-\frac{\pi ^2}{6}\left( \pi \ln \pi -\pi \right) -\left( \frac{2\pi ^3}{9}-\frac{\pi ^3}{6}\ln \pi \right) =-\frac{\pi ^3}{18}\]
只不过这时需要利用$\displaystyle{\sum_{n=1}^{\infty}{\frac{1}{n^2}}=\frac{\pi ^2}{6}}$和$\displaystyle{\frac{a_0}{2}+\sum_{n=1}^{\infty}{\left( -1 \right) ^na_n}=f\left( \pi \right) }$即可.在第一步分部积分中我们利用$\ln x$的Fourier展开可得$\displaystyle{\sum_{n=1}^{\infty}{\frac{\left( -1 \right) ^{n-1}\text{Si}\left( n\pi \right)}{n}}=\frac{\pi}{2}}$.

设$\displaystyle{\mathrm{Si}(x)=\int_0^x\frac{\sin t}t\mathrm dt}$表示正弦积分函数,求和

\[\sum_{n=1}^{\infty}{\left( \frac{\text{Si}\left( n\pi \right)}{n} \right) ^2}\]

解.同上,先分部积分得

\[\text{Si}\left( n\pi \right) =-n\int_0^{\pi}{\cos nx\ln x\text{d}x}\]
于是得到
\[\sum_{n=1}^{\infty}{\left( \frac{\text{Si}\left( n\pi \right)}{n} \right) ^2}=\sum_{n=1}^{\infty}{\left( \int_0^{\pi}{\cos nx\ln x\text{d}x} \right) ^2}\]
考虑函数$f(x)=\ln x,x\in(0,\pi)$,作偶函数延拓和$\pi$周期延拓得到的余弦级数为
\[\widetilde{f}\left( x \right) =\frac{a_0}{2}+\sum_{n=1}^{\infty}{a_n\cos nx}\]
其中$\displaystyle{a_n=\frac{2}{\pi}\int_0^{\pi}{\cos nx\ln x\text{d}x}},a_0=2\ln\pi-2$,由Parseval定理得
\[\frac{a_{0}^{2}}{2}+\sum_{n=1}^{\infty}{a_{n}^{2}}=\frac{2}{\pi}\int_0^{\pi}{f^2\left( x \right) \text{d}x}=\frac{2}{\pi}\int_0^{\pi}{\ln ^2x\text{d}x}=4-4\ln \pi +2\ln ^2\pi\]
因此我们最后得到
\[\sum_{n=1}^{\infty}{\left( \frac{\text{Si}\left( n\pi \right)}{n} \right) ^2}=\sum_{n=1}^{\infty}{\left( \int_0^{\pi}{\cos nx\ln x\text{d}x} \right) ^2}=\frac{\pi^2}2\]

好吧,算到这里,虽然解决了这三个美国数学月刊征解题,但是干脆再无聊点,下面我们算两个五次方的级数,其实套路都一样,但是计算量增加很多.

\[\sum_{n=1}^{\infty}{\frac{\text{Si}\left( n\pi \right)}{n^5}}=\frac{269}{43200}\pi ^5,\sum_{n=1}^{\infty}{\frac{\left( -1 \right) ^{n-1}\text{Si}\left( n\pi \right)}{n^5}}=\frac{4}{675}\pi ^5\]

从\begin{align*}\text{Si}\left( n\pi \right) &=\int_0^{n\pi}{\frac{\sin t}{t}\text{d}t}=\int_0^{\pi}{\frac{\sin nx}{x}\text{d}x}=\int_0^{\pi}{\sin nx\text{d}\left( \ln x \right)}=-n\int_0^{\pi}{\cos nx\ln x\text{d}x}\\&=-n\int_0^{\pi}{\cos nx\text{d}\left( x\ln x-x \right)}=n\left[ \left( -1 \right) ^{n-1}\left( \pi \ln \pi -\pi \right) -n\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x} \right]\end{align*}

出发,可得
\[\sum_{n=1}^{\infty}{\frac{\text{Si}(n\pi)}{n^5}}=\sum_{n=1}^{\infty}{\frac{\left( -1 \right) ^{n-1}}{n^4}\left( \pi \ln \pi -\pi \right)}-\sum_{n=1}^{\infty}{\frac{1}{n^3}\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x}}\]
而$\displaystyle{\sum_{n=1}^\infty\frac{(-1)^{n-1}}{n^4}=\frac{7\pi^4}{720}}$(利用$\zeta(4)$即可),把后一部分式子再分部积分得
\begin{align*}\sum_{n=1}^{\infty}{\frac{1}{n^3}\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x}}&=\sum_{n=1}^{\infty}{\frac{1}{n^3}\int_0^{\pi}{\sin nx\text{d}\left( \frac{1}{2}x^2\ln x-\frac{3}{4}x^2 \right)}}\\&=\sum_{n=1}^{\infty}\frac1{n^2}{\int_0^{\pi}{\left( \frac{3}{4}x^2-\frac{1}{2}x^2\ln x \right) \cos nx\text{d}x}}\\&=\sum_{n=1}^{\infty}{\frac{1}{n^2}\int_0^{\pi}{\cos nx\text{d}\left( \frac{11}{36}x^3-\frac{1}{6}x^3\ln x \right)}}\\&=\left( \frac{11}{36}\pi ^3-\frac{\pi ^3}{6}\ln \pi \right) \sum_{n=1}^{\infty}{\frac{\left( -1 \right) ^n}{n^2}}+\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\left( \frac{11}{36}x^3-\frac{x^3}{6}\ln x \right) \sin nx\text{d}x}}\\&=-\left( \frac{11}{36}\pi ^3-\frac{\pi ^3}{6}\ln \pi \right) \frac{\pi ^2}{12}+\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\left( \frac{11}{36}x^3-\frac{x^3}{6}\ln x \right) \sin nx\text{d}x}}.\end{align*}
\begin{align*}\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\left( \frac{11}{36}x^3-\frac{x^3}{6}\ln x \right) \sin nx\text{d}x}}&=\sum_{n=1}^{\infty}{\frac{1}{n}\int_0^{\pi}{\sin nx\text{d}\left( \frac{25}{288}x^4-\frac{1}{24}x^4\ln x \right)}}\\&=\sum_{n=1}^{\infty}{\int_0^{\pi}{\left( \frac{25}{288}x^4-\frac{1}{24}x^4\ln x \right) \cos nx\text{d}x}}.\end{align*}
下面考虑函数\[f\left( x \right) = \left\{ {\begin{array}{*{20}{c}}{\frac{{25}}{{288}}{x^4} - \frac{1}{{24}}{x^4}\ln x,}&{x \in \left( {0,\pi } \right]}\\{0,}&{x = 0}\end{array}} \right.\]及其余弦级数可得\[\frac{a_0}{2}+\sum_{n=1}^{\infty}{a_n}=f\left( 0 \right) =0\]
其中$\displaystyle{a_n=\frac{2}{\pi}\int_0^{\pi}{\left( \frac{25}{288}x^4-\frac{1}{24}x^4\ln x \right) \cos nx\text{d}x},a_0=\frac{\pi ^4\left( 137-60\ln \pi \right)}{3600}}$,于是$\displaystyle{\sum_{n=1}^{\infty}{a_n}=-\frac{a_0}{2}=-\frac{\pi ^4\left( 137-60\ln \pi \right)}{7200}}$,因此我们最后得到
\[\sum_{n=1}^{\infty}{\frac{\text{Si}\left( n\pi \right)}{n^5}}=\frac{7\pi ^4}{720}\left( \pi \ln \pi -\pi \right) +\frac{\pi ^2}{12}\left( \frac{11\pi ^3}{36}-\frac{\pi ^3}{6}\ln \pi \right) -\frac{\pi}{2}\cdot \frac{\pi ^4\left( 137-60\ln \pi \right)}{7200}=\frac{269}{43200}\pi ^5\]
第二个级数同理.

最后再算一个级数

\[\sum_{n=1}^{\infty}{\frac{\text{Si}^2\left( n\pi \right)}{n^4}}=\frac{\pi ^4}{27}\]

解.首先

\[\frac{\text{Si}\left( n\pi \right)}{n^2}=\frac{\left( -1 \right) ^{n-1}}{n}\left( \pi \ln \pi -\pi \right) -\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x}\]
把上式两边乘以$\sin nx$求和,利用Fourier级数的收敛定理得
\begin{align*}\sum_{n=1}^{\infty}{\frac{\text{Si}\left( n\pi \right)}{n^2}\sin nx}&=\left( \pi \ln \pi -\pi \right) \sum_{n=1}^{\infty}{\frac{\left( -1 \right) ^{n-1}}{n}\sin nx}-\sum_{n=1}^{\infty}{\sin nx\int_0^{\pi}{\sin nx\left( x\ln x-x \right) \text{d}x}}\\&=\frac{\left( \pi \ln \pi -\pi \right) x}{2}-\frac{\pi \left( x\ln x-x \right)}{2}.\end{align*}
最后利用Paserval定理得
\[\sum_{n=1}^{\infty}{\frac{\text{Si}^2\left( n\pi \right)}{n^4}}=\frac{2}{\pi}\int_0^{\pi}{\left( \frac{\left( \pi \ln \pi -\pi \right) x}{2}-\frac{\pi \left( x\ln x-x \right)}{2} \right) ^2\text{d}x}=\frac{\pi ^4}{27}\]

注:从这里,其实我们发现了对任意整数$k$,$\displaystyle{\sum_{n=1}^{\infty}{\frac{\text{Si}\left( n\pi \right)}{n^{2k-1}}}(k>1),\sum_{n=1}^{\infty}{\left( -1 \right) ^{n-1}\frac{\text{Si}\left( n\pi \right)}{n^{2k-1}}},\sum_{n=1}^{\infty}{\frac{\text{Si}^2\left( n\pi \right)}{n^{2k}}}}$都可以算出来,只是当次数增加时,这个计算量会越来越大,所以再往上算的话估计只有欧拉和拉马努金这种人去了,不知道这个结果是否可以用类似伯努利数的方法给出通项呢?我也解决不了.

 
最后再做一点额外补充:我把这些题目放到了数学贴吧,某位吧友也提出了一个不错的方法,就是利用下面的Fourier级数
比如
\begin{align*}\sum_{n=1}^{\infty}{\frac{\text{Si}\left( n\pi \right)}{n^3}}&=\sum_{n=1}^{\infty}{\frac{1}{n^3}\int_0^{\pi}{\frac{\sin nx}{x}\text{d}x}}=\sum_{n=1}^{\infty}{\frac{1}{n^3}\int_0^{\pi}{\sin nx\text{d}x}\int_0^{+\infty}{\text{e}^{-xy}\text{d}y}}\\&=\int_0^{+\infty}{\text{d}y}\int_0^{\pi}{\text{e}^{-xy}}\frac{x^3-3\pi x^2+2\pi ^2x}{12}\text{d}y=\frac{5}{72}\pi ^3.\end{align*}
类似的也可以处理,只不过这些Fourier级数光算出来计算量已经不得了了,如果提高到五次或者更高次,计算量更大了,不过对于有平方的式子,恐怕还只能利用Parseval定理了.好了,本期的问题就到这里了,下一期暂时没想好写什么QAQ.

如何开启深度学习之旅?这三大类125篇论文为你导航(附资源下载)

选自Github

作者:songrotek

机器之心编译

参与:晏奇、黄小天

如果你现在还是个深度学习的新手,那么你问的第一个问题可能是「我应该从哪篇文章开始读呢?」在 Github 上,songrotek 准备了一套深度学习阅读清单,而且这份清单在随时更新。至于文中提到的 PDF,读者们可点击阅读原文下载机器之心打包的论文,或点开下面的项目地址下载自己喜欢的学习材料。

项目地址:https://github.com/songrotek/Deep-Learning-Papers-Reading-Roadmap

这份清单依照下述 4 条原则建立:

·         从整体轮廓到细节

·         从过去到当代

·         从一般到具体领域

·         聚焦当下最先进技术

你会发现很多非常新但很值得一读的论文。这份清单我会持续更新。

1、深度学习的历史与基础知识

1.0 书籍

[0] Bengio, Yoshua, Ian J. Goodfellow, and Aaron Courville. 深度学习(Deep learning), An MIT Press book. (2015). (这是深度学习领域的圣经,你可以在读此书的同时阅读下面的论文)。

1.1 调查类:

[1] LeCun, Yann, Yoshua Bengio, and Geoffrey Hinton. 深度学习 (Deep learning), Nature 521.7553 (2015): 436-444. (深度学习三位大牛对各种学习模型的评价)

1.2 深度信念网络(DBN)(深度学习前夜的里程碑)

[2] Hinton, Geoffrey E., Simon Osindero, and Yee-Whye Teh. 一个关于深度信念网络的快速学习算法(A fast learning algorithm for deep belief nets), (深度学习的前夜)

[3] Hinton, Geoffrey E., and Ruslan R. Salakhutdinov. 使用神经网络降低数据的维度(Reducing the dimensionality of data with neural networks), (里程碑式的论文,展示了深度学习的可靠性)

1.3 ImageNet 的演化(深度学习从这里开始)

[4] Krizhevsky, Alex, Ilya Sutskever, and Geoffrey E. Hinton. 使用深度卷积神经网络进行 ImageNet 分类任务(Imagenet classification with deep convolutional neural networks)(AlexNet, 深度学习的突破)

[5] Simonyan, Karen, and Andrew Zisserman. 针对大尺度图像识别工作的的超深卷积网络(Very deep convolutional networks for large-scale image recognition) (VGGNet, 神经网络开始变得非常深!)

[6] Szegedy, Christian, et al. 更深的卷积(Going deeper with convolutions)(GoogLeNet)

[7] He, Kaiming, et al. 图像识别的深度残差学习(Deep residual learning for image recognition)(ResNet,超级超级深的深度网络!CVPR--IEEE 国际计算机视觉与模式识别会议-- 最佳论文)

1.4 语音识别的演化

[8] Hinton, Geoffrey, et al. 语音识别中深度神经网络的声学建模(Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups)(语音识别中的突破)

[9] Graves, Alex, Abdel-rahman Mohamed, and Geoffrey Hinton. 用深度循环神经网络进行语音识别(Speech recognition with deep recurrent neural networks)(RNN)

[10] Graves, Alex, and Navdeep Jaitly. 面向端到端语音识别的循环神经网络(Towards End-To-End Speech Recognition with Recurrent Neural Networks)

[11] Sak, Haşim, et al. 语音识别中快且精准的循环神经网络声学模型(Fast and accurate recurrent neural network acoustic models for speech recognition)(谷歌语音识别系统)

[12] Amodei, Dario, et al. Deep speech 2:英语和汉语的端到端语音识别(Deep speech 2: End-to-end speech recognition in english and mandarin)(百度语音识别系统)

[13] W. Xiong, J. Droppo, X. Huang, F. Seide, M. Seltzer, A. Stolcke, D. Yu, G. Zweig,在对话语音识别中实现人类平等(Achieving Human Parity in Conversational Speech Recognition) (最先进的语音识别技术,微软)

当你读完了上面给出的论文,你会对深度学习历史有一个基本的了解,深度学习建模的基本架构(包括了 CNN,RNN,LSTM)以及深度学习如何可以被应用于图像和语音识别问题。下面的论文会让你对深度学习方法,不同应用领域中的深度学习技术和其局限有深度认识。我建议你可以基于自己的兴趣和研究方向选择下面这些论文。

2 深度学习方法

2.1 模型

[14] Hinton, Geoffrey E., et al. 通过避免特征检测器的共适应来改善神经网络(Improving neural networks by preventing co-adaptation of feature detectors)(Dropout)

[15] Srivastava, Nitish, et al. Dropout:一种避免神经网络过度拟合的简单方法(Dropout: a simple way to prevent neural networks from overfitting)

[16] Ioffe, Sergey, and Christian Szegedy. Batch normalization:通过减少内部协变量加速深度网络训练(Batch normalization: Accelerating deep network training by reducing internal covariate shift)(2015 年一篇杰出论文)

[17] Ba, Jimmy Lei, Jamie Ryan Kiros, and Geoffrey E. Hinton.层归一化(Layer normalization)(批归一化的升级版)

[18] Courbariaux, Matthieu, et al. 二值神经网络:训练神经网络的权重和激活约束到正 1 或者负 1(Binarized Neural Networks: Training Neural Networks with Weights and Activations Constrained to+ 1 or−1)(新模型,快)

[19] Jaderberg, Max, et al. 使用合成梯度的解耦神经接口(Decoupled neural interfaces using synthetic gradients)(训练方法的发明,令人惊叹的文章)

[20] Chen, Tianqi, Ian Goodfellow, and Jonathon Shlens. Net2net:通过知识迁移加速学习(Net2net: Accelerating learning via knowledge transfer) (修改之前的训练网络以减少训练)

[21] Wei, Tao, et al. 网络形态(Network Morphism)(修改之前的训练网络以减少训练 epoch)

2.2 优化

[22] Sutskever, Ilya, et al. 有关深度学习中初始化与动量因子的研究(On the importance of initialization and momentum in deep learning) (动量因子优化器)

[23] Kingma, Diederik, and Jimmy Ba. Adam:随机优化的一种方法(Adam: A method for stochastic optimization)(可能是现在用的最多的一种方法)

[24] Andrychowicz, Marcin, et al. 通过梯度下降学习梯度下降(Learning to learn by gradient descent by gradient descent) (神经优化器,令人称奇的工作)

[25] Han, Song, Huizi Mao, and William J. Dally. 深度压缩:通过剪枝、量子化训练和霍夫曼代码压缩深度神经网络(Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding) (ICLR 最佳论文,来自 DeePhi 科技初创公司,加速 NN 运行的新方向)

[26] Iandola, Forrest N., et al. SqueezeNet:带有 50x 更少参数和小于 1MB 模型大小的 AlexNet-层级精确度(SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and< 1MB model size.) (优化 NN 的另一个新方向,来自 DeePhi 科技初创公司)

2.3 无监督学习/深度生成模型

[27] Le, Quoc V. 通过大规模无监督学习构建高级特征(Building high-level features using large scale unsupervised learning.) (里程碑,吴恩达,谷歌大脑,猫)

[28] Kingma, Diederik P., and Max Welling. 自动编码变异贝叶斯(Auto-encoding variational bayes.) (VAE)

[29] Goodfellow, Ian, et al. 生成对抗网络(Generative adversarial nets.)(GAN, 超酷的想法)

[30] Radford, Alec, Luke Metz, and Soumith Chintala. 带有深度卷曲生成对抗网络的无监督特征学习(Unsupervised representation learning with deep convolutional generative adversarial networks.)(DCGAN)

[31] Gregor, Karol, et al. DRAW:一个用于图像生成的循环神经网络(DRAW: A recurrent neural network for image generation.) (值得注意的 VAE,杰出的工作)

[32] Oord, Aaron van den, Nal Kalchbrenner, and Koray Kavukcuoglu. 像素循环神经网络(Pixel recurrent neural networks.)(像素 RNN)

[33] Oord, Aaron van den, et al. 使用像素 CNN 解码器有条件地生成图像(Conditional image generation with PixelCNN decoders.) (像素 CNN)

2.4 RNN/序列到序列模型

[34] Graves, Alex. 带有循环神经网络的生成序列(Generating sequences with recurrent neural networks.)(LSTM, 非常好的生成结果,展示了 RNN 的力量)

[35] Cho, Kyunghyun, et al. 使用 RNN 编码器-解码器学习词组表征用于统计机器翻译(Learning phrase representations using RNN encoder-decoder for statistical machine translation.) (第一个序列到序列论文)

[36] Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. 运用神经网路的序列到序列学习(Sequence to sequence learning with neural networks.」)(杰出的工作)

[37] Bahdanau, Dzmitry, KyungHyun Cho, and Yoshua Bengio. 通过共同学习来匹配和翻译神经机器翻译(Neural Machine Translation by Jointly Learning to Align and Translate.)

[38] Vinyals, Oriol, and Quoc Le. 一个神经对话模型(A neural conversational model.)(聊天机器人上的序列到序列)

2.5 神经图灵机

[39] Graves, Alex, Greg Wayne, and Ivo Danihelka. 神经图灵机器(Neural turing machines.)arXiv preprint arXiv:1410.5401 (2014). (未来计算机的基本原型)

[40] Zaremba, Wojciech, and Ilya Sutskever. 强化学习神经图灵机(Reinforcement learning neural Turing machines.)

[41] Weston, Jason, Sumit Chopra, and Antoine Bordes. 记忆网络(Memory networks.)

[42] Sukhbaatar, Sainbayar, Jason Weston, and Rob Fergus. 端到端记忆网络(End-to-end memory networks.)

[43] Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. 指示器网络(Pointer networks.)

[44] Graves, Alex, et al. 使用带有动力外部内存的神经网络的混合计算(Hybrid computing using a neural network with dynamic external memory.)(里程碑,结合上述论文的思想)

2.6 深度强化学习

[45] Mnih, Volodymyr, et al. 使用深度强化学习玩 atari 游戏(Playing atari with deep reinforcement learning.) (第一篇以深度强化学习命名的论文)

[46] Mnih, Volodymyr, et al. 通过深度强化学习达到人类水准的控制(Human-level control through deep reinforcement learning.) (里程碑)

[47] Wang, Ziyu, Nando de Freitas, and Marc Lanctot. 用于深度强化学习的决斗网络架构(Dueling network architectures for deep reinforcement learning.) (ICLR 最佳论文,伟大的想法 )

[48] Mnih, Volodymyr, et al. 用于深度强化学习的异步方法(Asynchronous methods for deep reinforcement learning.) (当前最先进的方法)

[49] Lillicrap, Timothy P., et al. 运用深度强化学习进行持续控制(Continuous control with deep reinforcement learning.) (DDPG)

[50] Gu, Shixiang, et al. 带有模型加速的持续深层 Q-学习(Continuous Deep Q-Learning with Model-based Acceleration.)

[51] Schulman, John, et al. 信赖域策略优化(Trust region policy optimization.) (TRPO)

[52] Silver, David, et al. 使用深度神经网络和树搜索掌握围棋游戏(Mastering the game of Go with deep neural networks and tree search.) (阿尔法狗)

2.7 深度迁移学习/终身学习/尤其对于 RL

[53] Bengio, Yoshua. 表征无监督和迁移学习的深度学习(Deep Learning of Representations for Unsupervised and Transfer Learning.) (一个教程)

[54] Silver, Daniel L., Qiang Yang, and Lianghao Li. 终身机器学习系统:超越学习算法(Lifelong Machine Learning Systems: Beyond Learning Algorithms.) (一个关于终生学习的简要讨论)

[55] Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. 提取神经网络中的知识(Distilling the knowledge in a neural network.) (教父的工作)

[56] Rusu, Andrei A., et al. 策略提取(Policy distillation.) (RL 领域)

[57] Parisotto, Emilio, Jimmy Lei Ba, and Ruslan Salakhutdinov. 演员模仿:深度多任务和迁移强化学习(Actor-mimic: Deep multitask and transfer reinforcement learning.) (RL 领域)

[58] Rusu, Andrei A., et al. 渐进神经网络(Progressive neural networks.)(杰出的工作,一项全新的工作)

2.8 一次性深度学习

[59] Lake, Brenden M., Ruslan Salakhutdinov, and Joshua B. Tenenbaum. 通过概率程序归纳达到人类水准的概念学习(Human-level concept learning through probabilistic program induction.)(不是深度学习,但是值得阅读)

[60] Koch, Gregory, Richard Zemel, and Ruslan Salakhutdinov. 用于一次图像识别的孪生神经网络(Siamese Neural Networks for One-shot Image Recognition.)

[61] Santoro, Adam, et al. 用记忆增强神经网络进行一次性学习(One-shot Learning with Memory-Augmented Neural Networks ) (一个一次性学习的基本步骤)

[62] Vinyals, Oriol, et al. 用于一次性学习的匹配网络(Matching Networks for One Shot Learning.)

[63] Hariharan, Bharath, and Ross Girshick. 少量视觉物体识别(Low-shot visual object recognition.)(走向大数据的一步)

3 应用

3.1 NLP(自然语言处理)

[1] Antoine Bordes, et al. 开放文本语义分析的词和意义表征的联合学习(Joint Learning of Words and Meaning Representations for Open-Text Semantic Parsing.)

[2] Mikolov, et al. 词和短语及其组合性的分布式表征(Distributed representations of words and phrases and their compositionality.) (word2vec)

[3] Sutskever, et al. 运用神经网络的序列到序列学习(Sequence to sequence learning with neural networks.)

[4] Ankit Kumar, et al. 问我一切:动态记忆网络用于自然语言处理(Ask Me Anything: Dynamic Memory Networks for Natural Language Processing.)

[5] Yoon Kim, et al. 角色意识的神经语言模型(Character-Aware Neural Language Models.)

[6] Jason Weston, et al. 走向人工智能-完成问题回答:一组前提玩具任务(Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks.) (bAbI 任务)

[7] Karl Moritz Hermann, et al. 教机器阅读和理解(Teaching Machines to Read and Comprehend.)(CNN/每日邮件完形风格问题)

[8] Alexis Conneau, et al. 非常深度卷曲网络用于自然语言处理(Very Deep Convolutional Networks for Natural Language Processing.) (在文本分类中当前最好的)

[9] Armand Joulin, et al. 诡计包用于有效文本分类(Bag of Tricks for Efficient Text Classification.)(比最好的差一点,但快很多)

3.2 目标检测

[1] Szegedy, Christian, Alexander Toshev, and Dumitru Erhan. 深度神经网路用于目标检测(Deep neural networks for object detection.)

[2] Girshick, Ross, et al. 富特征层级用于精确目标检测和语义分割(Rich feature hierarchies for accurate object detection and semantic segmentation.)(RCNN)

[3] He, Kaiming, et al. 深度卷曲网络的空间金字塔池用于视觉识别(Spatial pyramid pooling in deep convolutional networks for visual recognition.) (SPPNet)

[4] Girshick, Ross. 快速的循环卷曲神经网络(Fast r-cnn.)

[5] Ren, Shaoqing, et al. 更快的循环卷曲神经网络:通过区域建议网络趋向实时目标检测(Faster R-CNN: Towards real-time object detection with region proposal networks.)

[6] Redmon, Joseph, et al. 你只看到一次:统一实时的目标检测(You only look once: Unified, real-time object detection.) (YOLO, 杰出的工作,真的很实用)

[7] Liu, Wei, et al. SSD:一次性多盒探测器(SSD: Single Shot MultiBox Detector.)

3.3 视觉跟踪

[1] Wang, Naiyan, and Dit-Yan Yeung. 学习视觉跟踪用的一种深度压缩图象表示(Learning a deep compact image representation for visual tracking.) (第一篇使用深度学习进行视觉跟踪的论文,DLT 跟踪器)

[2] Wang, Naiyan, et al. 为稳定的视觉跟踪传输丰富特征层次(Transferring rich feature hierarchies for robust visual tracking.)(SO-DLT)

[3] Wang, Lijun, et al. 用全卷积网络进行视觉跟踪(Visual tracking with fully convolutional networks.) (FCNT)

[4] Held, David, Sebastian Thrun, and Silvio Savarese. 用深度回归网络以 100FPS 速度跟踪(Learning to Track at 100 FPS with Deep Regression Networks.) (GOTURN, 作为一个深度神经网络,其速度非常快,但是相较于非深度学习方法还是慢了很多)

[5] Bertinetto, Luca, et al. 对象跟踪的全卷积 Siamese 网络(Fully-Convolutional Siamese Networks for Object Tracking.) (SiameseFC, 实时对象追踪的最先进技术)

[6] Martin Danelljan, Andreas Robinson, Fahad Khan, Michael Felsberg. 超越相关滤波器:学习连续卷积算子的视觉追踪(Beyond Correlation Filters: Learning Continuous Convolution Operators for Visual Tracking.)(C-COT)

[7] Nam, Hyeonseob, Mooyeol Baek, and Bohyung Han. 在视觉跟踪的树结构中传递卷积神经网络与建模(Modeling and Propagating CNNs in a Tree Structure for Visual Tracking.)(VOT2016 Winner,TCNN)

3.4 图像说明

[1] Farhadi,Ali,etal. 每幅图都讲述了一个故事:从图像中生成句子(Every picture tells a story: Generating sentences from images.)

[2] Kulkarni, Girish, et al. 儿语:理解并生成图像的描述(talk: Understanding and generating image deions.)

[3] Vinyals, Oriol, et al. 展示与表达:一个神经图像字幕生成器(Show and tell: A neural image caption generator)

[4] Donahue, Jeff, et al. 视觉认知和描述的长期递归卷积网络(Long-term recurrent convolutional networks for visual recognition and deion)

[5] Karpathy, Andrej, and Li Fei-Fei. 产生图像描述的深层视觉语义对齐(Deep visual-semantic alignments for generating image deions)

[6] Karpathy, Andrej, Armand Joulin, and Fei Fei F. Li. 双向图像句映射的深片段嵌入(Deep fragment embeddings for bidirectional image sentence mapping)

[7] Fang, Hao, et al. 从字幕到视觉概念,从视觉概念到字幕(From captions to visual concepts and back)

[8] Chen, Xinlei, and C. Lawrence Zitnick. 图像字幕生成的递归视觉表征学习「Learning a recurrent visual representation for image caption generation

[9] Mao, Junhua, et al. 使用多模型递归神经网络(m-rnn)的深度字幕生成(Deep captioning with multimodal recurrent neural networks (m-rnn).)

[10] Xu, Kelvin, et al. 展示、参与与表达:视觉注意的神经图像字幕生成(Show, attend and tell: Neural image caption generation with visual attention.)

3.5 机器翻译

一些里程碑式的论文在 RNN 序列到序列的主题分类下被列举。

[1] Luong, Minh-Thang, et al. 神经机器翻译中生僻词问题的处理(Addressing the rare word problem in neural machine translation.)

[2] Sennrich, et al. 带有子词单元的生僻字神经机器翻译(Neural Machine Translation of Rare Words with Subword Units)

[3] Luong, Minh-Thang, Hieu Pham, and Christopher D. Manning. 基于注意力的神经机器翻译的有效途径(Effective approaches to attention-based neural machine translation.)

[4] Chung, et al. 一个机器翻译无显式分割的字符级解码器(A Character-Level Decoder without Explicit Segmentation for Neural Machine Translation)

[5] Lee, et al. 无显式分割的全字符级神经机器翻译(Fully Character-Level Neural Machine Translation without Explicit Segmentation)

[6] Wu, Schuster, Chen, Le, et al. 谷歌的神经机器翻译系统:弥合人与机器翻译的鸿沟(Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation)

3.6 机器人

[1] Koutník, Jan, et al. 发展用于视觉强化学习的大规模神经网络(Evolving large-scale neural networks for vision-based reinforcement learning.)

[2] Levine, Sergey, et al. 深度视觉眼肌运动策略的端到端训练(End-to-end training of deep visuomotor policies.)

[3] Pinto, Lerrel, and Abhinav Gupta. 超大尺度自我监督:从 5 万次尝试和 700 机器人小时中学习抓取(Supersizing self-supervision: Learning to grasp from 50k tries and 700 robot hours.)

[4] Levine, Sergey, et al. 学习手眼协作用于机器人掌握深度学习和大数据搜集(Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection.)

[5] Zhu, Yuke, et al. 使用深度强化学习视觉导航目标驱动的室内场景(Target-driven Visual Navigation in Indoor Scenes using Deep Reinforcement Learning.)

[6] Yahya, Ali, et al. 使用分布式异步引导策略搜索进行集体机器人增强学习(Collective Robot Reinforcement Learning with Distributed Asynchronous Guided Policy Search.)

[7] Gu, Shixiang, et al. 深度强化学习用于机器操控(Deep Reinforcement Learning for Robotic Manipulation.)

[8] A Rusu, M Vecerik, Thomas Rothörl, N Heess, R Pascanu, R Hadsell. 模拟实机机器人使用过程网从像素中学习(Sim-to-Real Robot Learning from Pixels with Progressive Nets.)

[9] Mirowski, Piotr, et al. 学习在复杂环境中导航(Learning to navigate in complex environments.)

3.7 艺术

[1] Mordvintsev, Alexander; Olah, Christopher; Tyka, Mike (2015). 初始主义:神经网络的更深层(Inceptionism: Going Deeper into Neural Networks)(谷歌 Deep Dream)

[2] Gatys, Leon A., Alexander S. Ecker, and Matthias Bethge. 一个艺术风格的神经算法(A neural algorithm of artistic style.) (杰出的工作,目前最成功的算法)

[3] Zhu, Jun-Yan, et al. 自然图像流形上的生成视觉操纵(Generative Visual Manipulation on the Natural Image Manifold.)

[4] Champandard, Alex J. Semantic Style Transfer and Turning Two-Bit Doodles into Fine Artworks. (神经涂鸦)

[5] Zhang, Richard, Phillip Isola, and Alexei A. Efros. 多彩的图像彩色化(Colorful Image Colorization.)

[6] Johnson, Justin, Alexandre Alahi, and Li Fei-Fei. 实时风格迁移和超分辨率的感知损失(Perceptual losses for real-time style transfer and super-resolution.)

[7] Vincent Dumoulin, Jonathon Shlens and Manjunath Kudlur. 一个艺术风格的学习表征(A learned representation for artistic style.)

[8] Gatys, Leon and Ecker, et al. 神经风格迁移中的控制感知因子(Controlling Perceptual Factors in Neural Style Transfer.) (控制空间定位、色彩信息和全空间尺度方面的风格迁移)

[9] Ulyanov, Dmitry and Lebedev, Vadim, et al. 纹理网络:纹理和风格化图像的前馈合成(Texture Networks: Feed-forward Synthesis of Textures and Stylized Images.) (纹理生成和风格迁移)

3.8 对象分割

[1] J. Long, E. Shelhamer, and T. Darrell, 用于语义分割的全卷积网络(Fully convolutional networks for semantic segmentation)

[2] L.-C. Chen, G. Papandreou, I. Kokkinos, K. Murphy, and A. L. Yuille. 具有深度卷积网络和全连接的条件随机场的语义图像分割(Semantic image segmentation with deep convolutional nets and fully connected crfs)

[3] Pinheiro, P.O., Collobert, R., Dollar, P. 学习如何分割候选对象(Learning to segment object candidates)

[4] Dai, J., He, K., Sun, J. 基于多任务网络级联的实例感知语义分割(Instance-aware semantic segmentation via multi-task network cascades)

[5] Dai, J., He, K., Sun, J. 实例敏感的全卷积网络(Instance-sensitive Fully Convolutional Networks)

十个利用矩阵解决的经典题目

来源:http://blog.csdn.net/fun_zero/article/details/48685661

经典题目1 给定n个点,m个操作,构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转

    这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转(两种情况),旋转则以原点为中心。如果对每个点分别进行模拟,那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵,然后每个点与该矩阵相乘即可直接得出最终该点的位置,总共耗时O(m+n)。假设初始时某个点的坐标为x和y,下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来,再乘以(x,y,1),即可一步得出最终点的位置。

     

经典题目2 给定矩阵A,请快速计算出A^n(n个A相乘)的结果,输出的每个数都mod p。

    由于矩阵乘法具有结合律,因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论:当n为偶数时,A^n = A^(n/2) * A^(n/2);当n为奇数时,A^n = A^(n/2) * A^(n/2) * A (其中n/2取整)。这就告诉我们,计算A^n也可以使用二分快速求幂的方法。例如,为了算出A^25的值,我们只需要递归地计算出A^12、A^6、A^3的值即可。根据这里的一些结果,我们可以在计算过程中不断取模,避免高精度运算。

经典题目POJ3233 (感谢rmq)
    
题目大意:给定矩阵A,求A + A^2 + A^3 + ... + A^k的结果(两个矩阵相加就是对应位置分别相加)。输出的数据mod mk<=10^9
    这道题两次二分,相当经典。首先我们知道,A^i可以二分求出。然后我们需要对整个题目的数据规模k进行二分。比如,当k=6时,有:
    A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3)

    应用这个式子后,规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3,即可得到原问题的答案。

POJ3233题解: Matrix Power Series


经典题目4 VOJ1049
    题目大意:顺次给出m个置换,反复使用这m个置换对初始序列进行操作,问k次置换后的序列。m<=10, k<2^31。
    首先将这m个置换“合并”起来(算出这m个置换的乘积),然后接下来我们需要执行这个置换k/m次(取整,若有余数则剩下几步模拟即可)。注意任意一个置换都可以表示成矩阵的形式。例如,将1 2 3 4置换为3 1 2 4,相当于下面的矩阵乘法:
     
    置换k/m次就相当于在前面乘以k/m个这样的矩阵。我们可以二分计算出该矩阵的k/m次方,再乘以初始序列即可。做出来了别忙着高兴,得意之时就是你灭亡之日,别忘了最后可能还有几个置换需要模拟。

经典题目5 《算法艺术与信息学竞赛》207页(2.1代数方法和模型,[例题5]细菌,版次不同可能页码有偏差)
    大家自己去看看吧,书上讲得很详细。解题方法和上一题类似,都是用矩阵来表示操作,然后二分求最终状态。

经典题目6 给定n和p,求第n个Fibonacci数mod p的值,n不超过2^31
    根据前面的一些思路,现在我们需要构造一个2 x 2的矩阵,使得它乘以(a,b)得到的结果是(b,a+b)。每多乘一次这个矩阵,这两个数就会多迭代一次。那么,我们把这个2 x 2的矩阵自乘n次,再乘以(0,1)就可以得到第n个Fibonacci数了。不用多想,这个2 x 2的矩阵很容易构造出来:
     

经典题目7 VOJ1067
    我们可以用上面的方法二分求出任何一个线性递推式的第n项,其对应矩阵的构造方法为:在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1,矩阵第n行填对应的系数,其它地方都填0。例如,我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项:
     
    利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。

 

经典题目8 给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值

    把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。同理,如果要求经过k步的路径数,我们只需要二分求出A^k即可。

例:HDU 2254   HDU 5302

 

经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案,M<=5,N<2^31,输出答案mod p的结果
     
    我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上,从右往左一列一列地进行填充。其中前n-2列已经填满了,第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满,将状态转移到第n列上去。由于第n-1列的状态不一样(有8种不同的状态),因此我们需要分情况进行讨论。在图中,我把转移前8种不同的状态放在左边,转移后8种不同的状态放在右边,左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复,状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌(例如左边第2种状态不能转移到右边第4种状态),否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图,那么问题就变成了这样:从状态111出发,恰好经过n步回到这个状态有多少种方案。比如,n=2时有3种方案,111->011->111、111->110->111和111->000->111,这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
    后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。

经典题目10 POJ2778
    题目大意是,检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段,每个片段长度不超过10。数据规模n<=2 000 000 000。
    下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例,说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀,把n位DNA分为以下7类:以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”,它可以是任一字母,只要这个字母不会让它所在的串成为某个病毒的前缀。显然,这些分类是全集的一个划分(交集为空,并集为全集)。现在,假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数,我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如,从AT不能转移到AA,从AT转移到??有4种方法(后面加任一字母),从?A转移到AA有1种方案(后面加个A),从?A转移到??有2种方案(后面加G或C),从GG到??有2种方案(后面加C将构成病毒片段,不合法,只能加A和T)等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后,我们就把这个图转化成矩阵,让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
    题目中的数据规模保证前缀数不超过100,一次矩阵乘法是三方的,一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n),AC了。