微积分初步
hihihi198
·
·
个人记录
导数
定义
函数 y=f(x) 在 x=x_0 时产生的增量 \Delta x 趋近于 0 时，\dfrac{\Delta y}{\Delta x} 如果存在，即为在 x_0 处的导数，记为 f'(x_0) 或 \dfrac{\mathrm d}{\mathrm dx}f(x_0)，并称这一点可导。其中 y'=\dfrac{\mathrm dy}{\mathrm dx}=\lim_{\Delta x\to 0}\dfrac{\Delta y}{\Delta x}。
$$
f'(x)=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h}
$$
另外，$f'(x)$ 的导函数记作 $f''(x)$，称为 $f(x)$ 的二阶导数。定义 $f(x)$ 的 $n$ 阶导函数为对 $f(x)$ 进行 $n$ 次求导后得到的函数，记作 $f^{(n)}(x)$。注意必须保证每次求导在一定范围内可导。
## 导数的运算
### 公式
设 $u=f(x),v=g(x)$。则有：
$$
(u\pm v)'=u'\pm v'
$$
$$
(uv)'=u'v+uv'
$$
$$
(\frac uv)'=\frac{u'v-uv'}{v^2}
$$
设 $v=g(x),u=f(v)$，则有
$$
u'=\frac{\mathrm du}{\mathrm dv}v'
$$
最后一个式子的意义为
$$
(f(g(x)))'=f'(g(x))g'(x)
$$
### 证明
第一个公式根据定义显然成立。
$$
\begin{aligned}
(f(x)g(x))'&=\lim_{h\to 0}\frac{f(x+h)g(x+h)-f(x)g(x)}{h}\\
&=\lim_{h\to 0}\frac{(f(x)+hf'(x))(g(x)+hg'(x))-f(x)g(x)}{h}\\
&=\lim_{h\to 0}f(x)g'(x)+f'(x)g(x)+hf'(x)g'(x)\\
&=f(x)g'(x)+f'(x)g(x)\\
(\frac{f(x)}{g(x)})'&=\lim_{h\to 0}\frac 1h(\frac{f(x+h)}{g(x+h)}-\frac{f(x)}{g(x)})\\
&=\lim_{h\to 0}\frac 1h(\frac{g(x)f(x+h)}{g(x)g(x+h)}-\frac{g(x+h)f(x)}{g(x+h)g(x)})\\
&=\lim_{h\to 0}\frac{g(x)(f(x)+hf'(x))-(g(x)+hg'(x))f(x)}{hg(x)(g(x)+hg'(x))}\\
&=\lim_{h\to 0}\frac{hf'(x)g(x)-hf(x)g'(x)}{hg(x)^2+h^2g(x)g'(x)}\\
&=\frac{f'(x)g(x)-f(x)g'(x)}{(g(x))^2}\\
u'&=\frac{\mathrm du}{\mathrm dx}\\
&=\frac{\mathrm du}{\mathrm dv}\cdot\frac{\mathrm dv}{\mathrm dx}\\
&=\frac{\mathrm du}{\mathrm dv}v'
\end{aligned}
$$
## 简单函数的导数
### 公式
| $f(x)$ | $f'(x)$ |
| :----------: | :----------: |
| $x^n$ | $nx^{n-1}$ |
| $e^x$ | $e^x$ |
| $a^x$ | $a^x\ln a$ |
| $\ln x$ | $\dfrac 1x$ |
| $\log_a x$ | $\dfrac{1}{x\ln a}$ |
### 证明
$$
\begin{aligned}
e&=\lim_{x\to\infty}(1+\frac 1x)^x\\
e&=\lim_{h\to 0}(1+h)^{\frac 1h}\\
\lim_{h\to 0}e^h&=1+h\\
(e^x)'&=\lim_{h\to 0}\frac{e^{x+h}-e^x}{h}\\
&=\lim_{h\to 0}\frac{(1+h)e^x-e^x}{h}\\
&=e^x
\end{aligned}
$$
---
$$
\begin{aligned}
y&=\ln x\\
e^y&=x\\
(e^y)'&=1\\
e^{\ln x}y'&=1\\
y'&=\frac 1x
\end{aligned}
$$
---
$$
\begin{aligned}
y&=x^n\\
\ln y&=\ln x^n\\
(\ln y)'&=(n\ln x)'\\
\frac{y'}y&=\frac nx\\
y'&=nx^{n-1}
\end{aligned}
$$
---
$$
\begin{aligned}
(a^x)'&=((e^{\ln a})^x)'\\
&=((e^x)^{\ln a})'\\
&=(\ln a)(e^x)^{(\ln a)-1}e^x\\
&=a^x\ln a
\end{aligned}
$$
---
$$
\begin{aligned}
(\log_a x)'&=(\frac{\ln x}{\ln a})'\\
&=\frac{x^{-1}\ln a}{\ln^2 a}\\
&=\frac{1}{x\ln a}
\end{aligned}
$$
# 积分
## 不定积分
按我的理解，不定积分应该是求导的逆运算。
例如，若 $g(x)=\dfrac{\mathrm d}{\mathrm dx}f(x)$。则
$$
\int g(x)\mathrm dx=f(x)+C
$$
其中 $C$ 是一个常数。
## 定积分
若 $g(x)=f'(x)$，则
$$
\int_a^bg(x)\mathrm dx=f(x)\vert^b_a=f(b)-f(a)
$$
容易证明，它是函数 $g(x)$ 的图像在 $[a,b]$ 内与 $x$ 轴围成的区域的面积，其中 $x$ 轴上方为正，下方为负。
证明如下：
$$
\begin{aligned}
f(b)-f(a)&=\lim_{h\to 0}\sum_{t=0}^{\frac{b-a-h}{h}}f(a+th+h)-f(a+th)\\
&=\lim_{h\to 0}\sum_{t=0}^{\frac{b-a-h}{h}}hg(a+th)
\end{aligned}
$$
也就是把面积分成无数小矩形的和。
由此可以得出：
$$
\sum_{i=a}^{b-1}g(i)\approx\int_a^bg(x)\mathrm dx
$$
这在分析复杂度时很有用。
## 简单函数的积分
### 公式
| $f(x)$ | $\int f(x)\mathrm dx-C$ |
| :----------: | :----------: |
| $x^n(n\ne -1)$ | $\dfrac{x^{n+1}}{n+1}$ |
| $x^{-1}$ | $\ln x$ |
| $e^x$ | $e^x$ |
| $a^x$ | $\dfrac{a^x}{\ln x}$ |
| $\ln x$ | $x\ln x-x$ |
| $\log_a x$ | $\dfrac{x\ln x-x}{\ln a}$ |
### 证明
只有最后两个要证明，其他的都显然。
$$
\begin{aligned}
\int(\ln x)\mathrm dx&=\int(\ln x)x'\mathrm dx\\
&=x\ln x-\int \mathrm dx\\
&=x\ln x-x+C\\
\int(\log_ax)\mathrm dx&=\int(\frac{\ln x}{\ln a})\mathrm dx\\
&=\frac{1}{\ln a}\int(\ln x)\mathrm dx\\
&=\frac{x\ln x-x}{\ln a}+C
\end{aligned}
$$
## 分部积分法
### 对于不定积分
$$
\int uv'\mathrm dx=uv-\int u'v\mathrm dx
$$
或写作：
$$
\int u\mathrm dv=uv-\int v\mathrm du
$$
证明：
$$
\begin{aligned}
(uv)'&=uv'+u'v\\
uv'&=(uv)'-u'v\\
\int uv'\mathrm dx&=uv-\int u'v\mathrm dx
\end{aligned}
$$
### 对于定积分
与不定积分类似。
$$
\int_a^buv'\mathrm dx=(uv)|^a_b-\int_a^bu'v\mathrm dx
$$
## 换元积分法
### 第一类
设 $v=g(x),u=f(v)$。则
$$
\int uv'\mathrm dx=\int u\mathrm dv=f(v)+C=f(g(x))+C
$$
有时候可以把对于复合函数的积分凑出上面的形式，然后套用公式。或者有时候发现积分就是上面的形式，直接套用公式。
例如，若已知 $f(x)=g'(x)$，则
$$
\begin{aligned}
\int f(ax+b)\mathrm dx&=\int\frac{1}{a}f(ax+b)(ax+b)'\mathrm dx\\
&=\frac{1}{a}\int f(ax+b)\mathrm d(ax+b)\\
&=\frac{g(ax+b)}{a}+C
\end{aligned}
$$
上面是把 $ax+b$ 换元，省略了换元过程。
定积分也差不多。但是注意，如果真的要把 $\mathrm dx$ 换成 $\mathrm df(x)$，上下界要从 $\int_a^b$ 改成 $\int_{f(a)}^{f(b)}$，当然是在这一段可积的前提下。
### 第二类
将 $x$ 对新的元求导来将 $\mathrm dx$ 转化为其它元的变化量。
举百度百科上的一个例子：设 $t=\sqrt x$，则 $x=t^2$，将 $x$ 对 $t$ 求导得 $\dfrac{\mathrm dx}{\mathrm dt}=2t$ 即 $\mathrm dx=2t\mathrm dt$。可以得到：
$$
\begin{aligned}
\int\frac{\sqrt x}{1+\sqrt x}\mathrm dx&=\int\frac{t}{1+t}2t\mathrm dt\\
&=2\int\frac{t^2}{1+t}\mathrm dt\\
&=2\int\frac{(t^2-1)+1}{1+t}\mathrm dt\\
&=2\int(t-1+\frac{1}{1+t})\mathrm dt\\
&=t^2-2t+2\ln(1+t)+C\\
&=x-2\sqrt x+2\ln(1+\sqrt x)+C
\end{aligned}
$$
其中第四步到第五步运用了第一类中证明的公式。
定积分的注意事项同第一类。
## 应用
### 证明埃氏筛的时间复杂度
即求证：
$$
\sum_{i=1}^{\pi(n)}\frac{n}{p_i}=O(n\log\log n)
$$
其中 $\pi(n)$ 为 $[1,n]$ 中的质数个数，$p_n$ 为第 $n$ 小的质数。
证明：
根据[素数定理](https://baike.baidu.com/item/%E7%B4%A0%E6%95%B0%E5%AE%9A%E7%90%86)，$\pi(n)\sim\dfrac{n}{\ln n}$，$p_n\sim n\ln n$，另外有 $\ln n=\dfrac{\log n}{\log e}=\Theta(\log n)$。
$$
\begin{aligned}
\sum_{k=1}^{\pi(n)}\frac{1}{p_k}&=\frac 12+\Theta(\sum_{k=2}^{\pi(n)}\frac{1}{k\ln k})\\
&=\frac 12+\Theta(\int_2^{\pi(n)}\frac{\mathrm dx}{x\ln x})
\end{aligned}
$$
可以发现
$$
\frac{\mathrm dx}{x\ln x}=(\ln x)'\frac{\mathrm dx}{\ln x}=\frac{\mathrm d(\ln x)}{\ln x}
$$
就是上面所说换元积分法的第一类公式。所以有
$$
\begin{aligned}
\sum_{k=1}^{\pi(n)}\frac{1}{p_k}&=\frac 12+\Theta(\int_{\ln 2}^{\ln\pi(n)}\frac{\mathrm d(\ln x)}{\ln x})\\
&=\frac 12+\Theta(\ln\ln\pi(n)-\ln\ln 2)\\
&=\Theta(\log\log\pi(n))\\
&=O(\log\log n)
\end{aligned}
$$
故
$$
\sum_{i=1}^{\pi(n)}\frac{n}{p_i}=O(n\log\log n)
$$
### 证明杜教筛的时间复杂度
杜教筛利用的公式为
$$
\mathbf S(n)=\sum_{i=1}^n(\mathbf{f*g})(i)-\sum_{d=2}^n\mathbf g(d)\mathbf S(\lfloor\frac nd\rfloor)
$$
在 [杜教筛学习笔记](https://www.luogu.com.cn/blog/hihihi198/note-of-du-sieve) 中我们已经证明了 $\mathbf S$ 的自变量取值一定是某个 $\lfloor\dfrac nx\rfloor$，所以只有 $O(\sqrt n)$ 种状态。最多的时候状态集合为 $\{x\mid x\in\mathbb N\cap[1,\sqrt n]\}\cap\{\lfloor\dfrac nx\rfloor\mid x\in\mathbb N\cap[1,\sqrt n]\}$。而计算一个状态 $x$ 的时间复杂度为 $O(\sqrt x)$。所以如果不预处理，总的时间复杂度为
$$
\begin{aligned}
O(\sum_{i=1}^{\sqrt n}\sqrt i+\sum_{i=1}^{\sqrt n}\sqrt{\lfloor\frac ni\rfloor})&=O(\sum_{i=1}^{\sqrt n}\sqrt{\lfloor\frac ni\rfloor})\\
&=O(\int_1^{\sqrt n}\sqrt{\frac nx}\mathrm dx)\\
&=O(\sqrt n\int_1^{\sqrt n}\frac 1{\sqrt x}\mathrm dx)\\
&=O(n^{\frac 12}\int_1^{\sqrt n}x^{-\frac 12}\mathrm dx)\\
&=O(n^{\frac 34})
\end{aligned}
$$
如果线性预处理出 $[1,n^a]$ 的答案且 $a>\dfrac 12$，则时间复杂度为
$$
\begin{aligned}
O(n^a+\sum_{i=1}^{n^{1-a}}\sqrt{\lfloor\frac ni\rfloor})&=O(n^a+\int_1^{n^{1-a}}\sqrt{\frac nx}\mathrm dx)\\
&=O(n^a+n^{\frac 12}\int_1^{n^{1-a}}x^{-\frac 12}\mathrm dx)\\
&=O(n^a+n^{1-\frac{a}{2}})
\end{aligned}
$$
可以看出，$a$ 取 $\dfrac 23$ 时最优，时间复杂度为 $O(n^{\frac 23})$。
# 泰勒展开
## 用多项式逼近
有一个函数 $f(x)=\sin x$，希望找到一个多项式 $p(x)$，使它们在 $x=0$ 附近接近。
如果 $p(x)$ 是一个常函数，记 $p(x)=a_0$，那么我们只能做到在 $x=0$ 时两个函数的函数值相等，即取 $a_0=\sin 0=0$。
如果 $p(x)$ 是一个一次函数，记 $p(x)=a_0+a_1x$，不但可以使之在 $x=0$ 时的函数值相等，还可以让它们此时的导数相等，即 $p'(0)=f'(0)=\cos 0=1$，得 $a_1=1$。
如果 $p(x)$ 是一个多次函数，可以让这两个函数在 $x=0$ 时的函数值、导数、二阶导数、三阶导数、$n$ 阶导数都相等。如果使用画图软件模拟这个过程，可以发现 $p(x)$ 次数越高，它就越逼近 $\sin x$。
当 $p(x)$ 是一个 $n$ 次多项式时，记 $p(x)=\sum_{i=0}^na_ix^i$，可以得到：
$$
i!a_i=p^{(i)}(0)=f^{(i)}(0)
$$
即：
$$
p(x)=\sum_{i=0}^n\frac{f^{(i)}(0)x^i}{i!}
$$
## 麦克劳林展开
如果上面的多项式有无穷项，记 $p(x)=\sum_{n\ge 0}a_nx^n$，可以发现：
$$
a_n=\frac{f^{(n)}(0)}{n!}\qquad p(x)=\sum_{n\ge 0}\frac{f^{(n)}(0)x^n}{n!}
$$
这样的 $p(x)=f(x)$ 就是麦克劳林展开。
例如：
$$
\begin{aligned}
\sin x&=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots\\
\cos x&=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\cdots
\end{aligned}
$$
这两个的证明比较容易。
$$
e^x=\sum_{n\ge 0}\frac{x^n}{n!}
$$
这个比较重要，可以从 $(e^x)'=e^x$ 得出。
## 一般的泰勒展开
上面说的麦克劳林展开是泰勒展开的特殊形式：关于原点的泰勒展开。
函数 $f(x)$ 关于 $x=x_0$ 的泰勒展开表述为：
$$
p(x)=\sum_{n\ge 0}\frac{f^{(n)}(x_0)(x-x_0)^n}{n!}
$$
上面推导泰勒展开的方法很不严谨，仅供感性理解。
## 应用
### 求 $\ln(1+x)$ 的幂级数形式
设 $f(x)=\ln(1+x)$。则有：
$$
\begin{aligned}
f'(x)&=(1+x)^{-1}\\
f''(x)&=-(1+x)^{-2}\\
f'''(x)&=2(1+x)^{-3}\\
\cdots\\
f^{(n)}(x)&=(-1)^{n-1}(n-1)!(1+x)^{-n}
\end{aligned}
$$
故
$$
f(x)=\sum_{n\ge 0}\frac{f^{(n)}(0)}{n!}x^n=\sum_{n>0}\frac{(-1)^{n-1}x^n}{n}
$$
### 求 $\ln\dfrac{1}{1-x}$ 的幂级数形式
设 $f(x)=\ln\dfrac{1}{1-x}$。则有：
$$
\begin{aligned}
f'(x)&=(1-x)^{-1}\\
f''(x)&=(1-x)^{-2}\\
\cdots\\
f^{(n)}(x)&=(n-1)!(1-x)^{-n}
\end{aligned}
$$
故
$$
f(x)=\sum_{n\ge 0}\frac{f^{(n)}(0)}{n!}x^n=\sum_{n>0}\frac{x^n}{n}
$$
其实也可以这样：
$$
\ln\frac{1}{1-x}=-\ln(1+(-x))=-\sum_{n>0}\frac{(-1)^{n-1}(-x)^n}{n}
$$