# Math in anywhere | Funciton

# Functions

# Space Concept

函数空间：即我们使用如干简单函数（这部分称之为” 基函数 “）通过线性组合（乘法和加法）的方式张成一个函数空间。

$$L = span\{f_1,f_2,\cdots,f_n\} = \{\sum_{i=1}^na_i f_i(x)| a_i\in R\}$$

$f_n (n \in R)$：代表函数空间中的元素

函数空间中的元素，总能表达成 n 个$a_i f_i(x)$ 的加和，其中把系数提取出来就能够获得系数向量

$$(a_1,a_2,\cdots,a_n)$$

具体的实例说明

• 多项式的函数空间，幂基$$

  $$f(x) = \sum_{k = 0}^n w_kx^k$$

• 三角函数的函数空间，三角函数基$$

  $$f(x) = a_0 + \sum_{k=1}^n (a_k \cos kx + b_k \sin kx)$$

本质上就是确定函数的类型，然后去确定系数向量

# Weierstrass approximation theorem

定理一：设 $f(x)$ 闭区间 $[a, b]$ 上的连续函数，则存在多项式序列 $P_n(x)$ 在 $[a, b]$ 上一致收敛于 $f(x)$。也就是对任意给定的 ϵ > 0，存在多项式 $P(x)$，使得：

$$|P(x) - f(x)| < \epsilon$$

对一切$x \in [a,b]$ 成立。

定理二：设 $f(x)$ 是以 2π 为周期的连续函数，则存在三角多项式序列一致收敛于 $f(x)$。也就是对于任意给定的 ϵ > 0，存在三角多项式 $T(x)$，使得:

$$|T(x) -f(x)| < \epsilon$$

对一切$x \in [-\infty,\infty]$ 成立。

# Fourier series

客观世界最常见的最简单周期函数：

$$f(t) = A \sin(wt + \varphi)$$

这里 t 表示时间，A 表示振幅，ω 为角频率，$\varphi$ 为初相位。

因为大多数周期信号并没有这么简单，但是傅里叶在《热的解析理论》中推导出使用一系列最简单的三角函数来组合复杂的周期函数，这些都基于三角函数的基本变化规律，如下图。

可以看这个视频，让你更直观的了解傅里叶级数：

傅里叶推导出的公式为：

$$f(t) = A_0 + \sum_{n=1}^\infty A_n \sin(nwt + \varphi_n)$$

由 $\varphi_n$ 为常数，$A_n$ 也是常数，则对上式的$A_n \sin(nwt + \varphi_n)$ 进行变形：

$$A_n \sin(nwt + \varphi) = A_n \sin \varphi_n \cos(nwt) + A_n \cos \varphi_n \sin(nwt)$$

记$a_n = A_n \sin \varphi_n , b_n = A_n \cos \varphi_n$ 然后进行替换公式 9，然后代进去公式 8

$$f(t) = A_0 + \sum_{n=1}^\infty (a_n \cos(nwt) + b_n\sin(nwt))$$

这里面的参数的计算：

$$A_0 = \frac{1}{2\pi}\int_{-\pi}^{\pi}f(t)$$

$$a_n = \frac{1}{\pi} \int_{-\pi}^{\pi}{f(t) \cdot \cos(nwt) dt}$$

$$b_n = \frac{1}{\pi} \int_{-\pi}^{\pi}{f(t) \cdot \sin(nwt) dt}$$

这个视频能够帮助你系统的了解傅里叶级数和傅里叶变换

# Data Fitting

数据拟合需要我们抓住问题的要点，实际应用问题能够进行抽象成一个数据模型，获取输入，找到合适的函数，优化函数。而这里的核心便是如何找到合适的函数，这里分为三步：

• 确定函数空间
  • 这一步就需要我们对数据进行观察，然后根据数据的趋势选取合适的函数空间。
• 确定度量方式
  • 根据实际情况的不同，会分为两种不同的目标：
    • 对数据集进行函数插值
    • 对数据集进行函数逼近
• 求解与优化
  • 根据实际的目标来选择合适的数学方法
    • 对数据集的插值
      • Lagrange 插值
      • Newton 插值
    • 对数据集的逼近
      • 最小二乘法

插值：就是无误差，数据集的每一个点都刚好可以通过函数变换而来。

# Function interpolation

在许多实际问题中，某个函数 $f(x)$ 往往很复杂、没有解析表达或者未知。我们往往只能通过某些手段观测到反映该函数的一些采样数据。我们希望通过这些观测的采样数据来估计该函数的信息，并预测函数在其他观测点的值。这时，我们从观测数据来求得一个函数 $\phi(x)$ 来近似 $f(x)$。

定义：$f(x)$ 为定义在区间 $[a, b]$ 上的函数，$x_0, x_1, \cdots, x_n$ 为区间上 n + 1 个互不相同的点，$\Phi$ 为给定的某一函数类。求 $\Phi$ 上的函数 $\phi(x)$，满足：

$$\phi(x_i) = f(x_i), i = 0,1,\cdots,n$$

则称 $\phi(x)$ 为 $f(x)$ 关于节点$x_0, x_1, \cdots, x_n$ 在$\Phi$ 上的插值函数。称$x_0, x_1, \cdots, x_n$ 为插值节点，称$(x_i, f(x_i))$ 为插值点。

多项式插值定理

定理：若 $x_i$ 两两不同，则对任意给定的$y_i$，存在唯一的次数至多是 n 次的多项式 $p_n$，使得$p_n(x_i)=y_i ,i = 0, \cdots , n$。

证明：在幂基 $\{1, x, \cdots , x_n\}$ 下待定多项式 $p$ 的形式为：

$$p(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$$

由插值定理可知，可以得到如下的方程

$$\left[ \begin{matrix} 1 & x_{0} & x_0^2& \cdots & x_0^n\\ 1 & x_{1} & x_1^2& \cdots & x_1^n\\ 1 & x_{2} & x_2^2& \cdots & x_2^n\\ \vdots & \vdots & \vdots &\ddots \vdots & \vdots \\ 1 & x_{n} & x_n^2& \cdots & x_n^n\\ \end{matrix}\right] \left[ \begin{matrix} a_{0} \\ a_{1} \\ a_{2} \\ \vdots\\ a_{n} \end{matrix}\right] = \left[ \begin{matrix} y_{0} \\ y_{1} \\ y_{2} \\ \vdots\\ y_{n} \end{matrix}\right]$$

系数矩阵为 Vandermonde 矩阵，其行列式非零，因此方程组有唯一解。

关于$n \times n$ 阶 Vandermonde 矩阵的行列式计算公式如下：

$$\det A_n = \prod_{1\le j \le n}(x_i - x_j)$$

因为我们知道$x_i$ 是彼此相异的，代入公式 (17)，可知$\det A_n \ne 0$，A 是可逆的，因此方程式必定存在唯一解。

Lagrange 插值

定义：给定一组$k+1$ 数据$（x_ {0}，y_ {0}），\ldots，（x_ {j}，y_ {j}），\ldots，（x_ {k}，y_ {k}）$, 其中没有两个 $\displaystyle x_{j}$ 相同，拉格朗日插值多项式是：

$$L（x）:= \sum_{ j = 0 }^k y_j \ell_j( x )$$

其中$\ell_{j}(x)$ 是拉格朗日基函数：

$$\ell_{j}(x):= \prod_{\begin{smallmatrix} 0 \leq m \leq k \\ m \neq j \end{smallmatrix} }{\frac{x-x_{m} }{x_{j}-x_{m} } } = {\frac{x-x_0}{x_j - x_0} } \cdots {\frac{x-x_{j - 1} }{x_{j} - x_{j-1} } {\frac {（x-x_ {j+1}）} {（x_ {j} -x_ {j+1}）} } \cdots \frac{x - x_k}{x_j - x_k}, 0\le j \le k}$$

拉格朗日基本多项式${\displaystyle \ell _{j}(x)}$ 的特点是在${\displaystyle x_{j} }$ 上取值为 1，在其它的点${\displaystyle x_{i},i\neq j}$ 上取值为 0 看例子可知。

Example：

假设有二次多项式函数$f$，已知它在三个点的值为$(4,10) ,(5,5.25) ,(6,1)$，求二次多项式

$$\ell _{0}(x)={\frac {(x-5)(x-6)}{(4-5)(4-6)} } \\ {\displaystyle \ell _{1}(x)={\frac {(x-4)(x-6)}{(5-4)(5-6)} } }\\ {\displaystyle \ell _{2}(x)={\frac {(x-4)(x-5)}{(6-4)(6-5)} } }$$

$${\displaystyle {\begin{aligned} p(x) & = f(4)\ell _{0}(x)+f(5)\ell _{1}(x)+f(6)\ell _{2}(x) \\ & = 10\cdot {\frac {(x-5)(x-6)}{(4-5)(4-6)} }+5.25\cdot {\frac {(x-4)(x-6)}{(5-4)(5-6)} }+1\cdot {\frac {(x-4)(x-5)}{(6-4)(6-5)} } \\ & = \frac{1}{4}(x^{2}-28x+136) \end{aligned} } }$$

优缺点：

• 拉格朗日插值法的公式结构整齐紧凑，在理论分析中十分方便
• 在计算中，当插值点增加或减少一个时，所对应的基本多项式就需要全部重新计算，于是整个公式都会变化，非常繁琐。
  • 这时可以用重心拉格朗日插值法或牛顿插值法来代替。
• 当插值点比较多的时候，拉格朗日插值多项式的次数可能会很高，因此具有数值不稳定的特点，也就是说尽管在已知的几个点取到给定的数值，但在附近却会和 “实际上” 的值之间有很大的偏差（如下图）。这类现象也被称为龙格现象。
  • 解决的办法是分段用较低次数的插值多项式。

Barycentric Form

为了解决数据增多情况下，拉格朗日插值法庞大计算量的问题。可以使用重心拉格朗日形式。首先我们定义一个多项式：

$$l(x) = (x-x_0)(x-x_1)\cdots(x-x_k)$$

公式 (19) 上下同时乘以$(x-x_j)$，然后将公式 (24) 代进去，可得

$$\ell_j = \frac{l(x)}{x-x_j} \cdot \frac{1}{\prod_{i=0,i\ne j}^k (x_j - x_i)}$$

然后我们将$\frac{1}{\prod_{i=0,i\ne j}^k (x_j - x_i)}$ 拿出来，将其定义为重心权：(这一步就是简化的关键)

$$w_j = \frac{1}{\prod_{i=0,i\ne j}^k (x_j - x_i)}$$

如果此时又加了一个数，那么新的$w_j$ 只需要再除以$(x_j-x_i)$

那么原公式就能变换为：

$$\ell_j(x) = \ell(x)\frac{w_j}{x-x_j}$$

进而得出重心拉格朗日插值：

$$L（x）:= \sum_{j = 0}^{k} y_{j} \ell_{j}(x) = l(x) \sum_{j=0}^k \frac{w_j}{x-x_j} y_j$$

进一步的我们还能对该公式进行变换，设有函数满足：

$$g(x)\equiv 1$$

$$\forall x,\,g(x)=\ell (x)\sum _{ {j=0} }^{k}{\frac {w_{j} }{x-x_{j} } }$$

将$L(x)$ 除以$g(x)$ 后可得到：

$$L(x)={\frac {\sum _{ {j=0} }^{k}{\frac {w_{j} }{x-x_{j} } }y_{j} }{\sum _{ {j=0} }^{k}{\frac {w_{j} }{x-x_{j} } } } }$$

优点

当插值点的个数增加一个时，将每个$w_{j}$ 都除以$(x_{j}-x_{ {k+1} })$，就可以得到新的重心权$w_{ {k+1} }$，计算复杂度为${\mathcal O}(n)$，比重新计算每个基本多项式所需要的复杂度${\mathcal O}(n^{2})$ 降了一个量级。

Newton 插值

定义：给定一组$k+1$ 数据$（x_ {0}，y_ {0}），\ldots，（x_ {j}，y_ {j}），\ldots，（x_ {k}，y_ {k}）$, 其中没有两个 $\displaystyle x_{j}$ 相同，牛顿插值多项式是：

$$N(x):=\sum _{ {j=0} }^{ {k} }a_{ {j} }n_{ {j} }(x)$$

其中$n_{ {j} }(x)$ 为牛顿基本多项式基函数，其表达式为：中

$$n_{j}(x):=\prod _{ {i=0} }^{ {j-1} }(x-x_{i}) \space \\ j>0，n_{0}(x)\equiv 1$$

而$a_j := [y_{0},\ldots ,y_{j}]$ 作为基函数的系数，而$[y_{0},\ldots ,y_{j}]$ 表示差商（也叫均差，是递归除法过程）

均差定义有两种方式：

• 向前均差

$${\displaystyle {\begin{aligned}{\mathopen {[} }y_{\nu }]&=y_{\nu },\quad \nu \in \{0,\ldots ,n\}\\{\mathopen {[} } y_{\nu },\ldots ,y_{\nu +j}]&={\frac {[y_{\nu +1},\ldots ,y_{\nu +j}]-[y_{\nu },\ldots ,y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu } } },\quad \nu \in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\}\\\end{aligned} } }$$

• 向后均差 (我们主要使用这种)

  $${\displaystyle {\begin{aligned}{\mathopen {[} }y_{\nu }]&=y_{\nu },\quad \nu \in \{0,\ldots ,n\}\\{\mathopen {[} }y_{\nu },\ldots ,y_{\nu -j}]&={\frac {[y_{\nu },\ldots ,y_{\nu -j+1}]-[y_{\nu -1},\ldots ,y_{\nu -j}]}{x_{\nu }-x_{\nu -j} } },\quad \nu \in \{j,\ldots ,n\},\ j\in \{1,\ldots ,n\}\\\end{aligned} } }$$

递归的过程通过下图来理解：

$$\begin{aligned}\mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} \\ \mathopen[y_0,y_1,y_2] &= \frac{\mathopen[y_1,y_2]-\mathopen[y_0,y_1]}{x_2-x_0} \\ \mathopen[y_0,y_1,y_2,y_3] &= \frac{\mathopen[y_1,y_2,y_3]-\mathopen[y_0,y_1,y_2]}{x_3-x_0} \\ \mathopen[y_0,y_1,\dots,y_n] &= \frac{\mathopen[y_1,y_2,\dots,y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_0} \end{aligned}$$

$$\begin{matrix} x_0 & [y_0] = y_0 & & & \\ & & [y_0,y_1] & & \\ x_1 & [y_1] = y_1 & & [y_0,y_1,y_2] & \\ & & [y_1,y_2] & & [y_0,y_1,y_2,y_3]\\ x_2 & [y_2] = y_2 & & [y_1,y_2,y_3] & \\ & & [y_2,y_3] & & \\ x_3 & [y_3] = y_3 & & & \\ \end{matrix}$$

然后将$n_{ {j} }(x)$ 和$a_j$ 带入方程就可以获得，牛顿多项式的这种形式：

$$N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{ {k-1} })$$

Example：

已知它在五个点的值为$(-\frac{3}{2},-14.1014) ,(-\frac{3}{4},-0.931596) ,(0,0),(\frac{3}{4},0.931596)(\frac{3}{2},14.1014)$，求牛顿多项式插值。（构造目标为$f(x) = \tan (x)$）

首先计算出差商表

$${\begin{matrix}-{\tfrac {3}{2} }&-14.1014&&&&\\&&17.5597&&&\\-{\tfrac {3}{4} }&-0.931596&&-10.8784&&\\&&1.24213&&4.83484&\\0&0&&0&&0\\&&1.24213&&4.83484&\\{\tfrac {3}{4} }&0.931596&&10.8784&&\\&&17.5597&&&\\{\tfrac {3}{2} }&14.1014&&&&\\\end{matrix} }$$

然后就能够写出多项式：

$$-14.1014+17.5597(x+{\tfrac {3}{2} })-10.8784(x+{\tfrac {3}{2} })(x+{\tfrac {3}{4} })+4.83484(x+{\tfrac {3}{2} })(x+{\tfrac {3}{4} })(x)+0(x+{\tfrac {3}{2} })(x+{\tfrac {3}{4} })(x)(x-{\tfrac {3}{4} }) \\ =-0.00005-1.4775x-0.00001x^{2}+4.83484x^{3}$$

这里我们能够观察到，数据点的增多并不会使得所有计算需要重新进行，只需要计算新的差商，然后多加一个多项式。

但是牛顿插值也会使得整体的多项式次数过高。

# Function approximation

给出一组离散的点，需要确定一个函数来逼近原函数。由于离散数据通常是由观察或测试得到的，所以不可避免的会有误差。我们需要的逼近原函数的手段要满足如下两个条件：

• 不要求过所有的点（可以消除误差影响）
• 尽可能表现数据的趋势，靠近这些点

用数学的语言来说即是，需要在给定的函数空间 Φ 上找到函数 ϕ，使得 ϕ 到原函数$f$ 的距离最小。这里的距离指的是某种度量，不同的度量对应着不同的拟合方法。则函数 ϕ(x) 称为 $f(x)$ 在空间 Φ 上的拟合曲线。

$$R_2 = \sqrt{\sum_{i=0}^m(\phi(x_i) - f(x_i))^2}$$

一般我们采用最小二乘法来处理这一类问题，这里我们首先给出离散内积的概念，内积这个计算概念主要是将公式中的项抽离出来的，所以不需要理解他的几何概念。

定义：函数$f,g$ 的关于离散点列$\{x_i\}_{i=0}^m$ 的离散内积为：

$$(f,g)_h = \sum_{i=0}^n f(x_i)g(x_i)$$

上述定义中的下标 h 表示对离散内积与离散范数的指代

定义：函数$f$ 的离散范数为：

$$||f||_h = \sqrt {(f,f)_h}$$

然后我们将上面离散内积和离散范数运用到最小二乘法中：

设${\displaystyle \Phi=span\{\phi_0,\phi_1,\cdots,\phi_n\} }$

$$\phi(x) = a_0\phi_0(x) + a_1\phi_1(x) + \cdots + a_n\phi_n(x)$$

进一步最小二乘为：

$${\begin{aligned}||f(x)-\phi(x)||_h = ||f(x) - a_0\phi_0(x) + a_1\phi_1(x) + \cdots + a_n\phi_n(x) ||_h \end{aligned} }$$

然后我们需要获取关于系数$\{a_0,a_1,\cdots,a_n\}$ 最小，我们可以计算 2 范数

$${\displaystyle {\begin{aligned}||f(x)-\phi(x)||_h^2 & = ||f(x) - a_0\phi_0(x) + a_1\phi_1(x) + \cdots + a_n\phi_n(x) ||_h^2\\ & = ||f||_h^2 - 2f(x)[(a_0\phi_0(x) + a_1\phi_1(x) + \cdots + a_n\phi_n(x))] + ||a_0\phi_0(x) + a_1\phi_1(x) + \cdots + a_n\phi_n(x)||_h^2 \\ & = ||f||_h^2 - 2\sum_{k=0}^n a_k(f,\phi_k)_h + \sum_{i,k =0}^n a_ia_k(\phi_i,\phi_k)_h \end{aligned} } }$$

我们将这个函数变成$Q(a_i)$ 的函数：

$$Q(a_i) = ||f||_h^2 - 2\sum_{k=0}^n a_k(f,\phi_k)_h + \sum_{i,k =0}^n a_ia_k(\phi_i,\phi_k)_h$$

为了使得系数的值最小，因此我们对函数求一阶导数，获得函数的极值点：

$$\frac{\partial Q}{\partial a_i} = 0 , i= 0,1,\cdots,n \\ (f,\phi_i)_h = \sum_{k =0}^n a_k(\phi_i,\phi_k)_h$$

然后改为矩阵形式：

$$\left[ \begin{matrix} (\phi_0,\phi_0)_h & \cdots & (\phi_0,\phi_n)_h \\ \vdots &\ddots& \vdots \\ (\phi_n,\phi_0)_h & \cdots & (\phi_n,\phi_n)_h \end{matrix}\right] \left[ \begin{matrix} a_{0} \\ \vdots\\ a_{n} \end{matrix}\right] = \left[ \begin{matrix} (f,\phi_0)_h \\ \vdots\\ (f,\phi_n)_h \\ \end{matrix}\right]$$

Example：

取 $Φ$ 为线性多项式空间，函数空间的基为 $\{1, x, x^2\}$, 拟合曲线为 $y = a_0 + a_1x + a_2x^2$，则法方
程为:

$$\left[ \begin{matrix} (1,1)_h & (1,x)_h & (1,x^2)_h \\ (x,1)_h & (x,x)_h & (x,x^2)_h \\ (x^2,1)_h & (x^2,x)_h & (x^2,x^2)_h \\ \end{matrix}\right] \left[ \begin{matrix} a_{0} \\ a_{1} \\ a_{2} \end{matrix}\right] = \left[ \begin{matrix} (f,1)_h \\ (f,x)_h \\ (f,x^2)_h \\ \end{matrix}\right]$$

最小二乘拟合（岭回归正则项）$A\{a_0,a_1,\cdots,a_n\}$，函数表达式：

$$min||Y - A\Phi||^2 + \mu ||A||_2^2$$

其中$\mu$ 为权重，就是对参数的值的大小的权重控制。

依据同样的思想，稀疏正则化：

$$min ||Y - A\Phi||^2 + \mu||W||_0$$

$||W||_0$ 表示非零的元素。

拟合的问题：

• 欠拟合

  • 选取适合的基函数去拟合

• 过拟合

  • 数据去噪

    • 剔除训练样本中噪声

  • 数据增广

  • 增加样本数，或者增加样本的代表性和多样性

  • 模型简化

    • 预测模型过于复杂，拟合了训练样本中的噪声

    • 选用更简单的模型，或者对模型进行裁剪

  • 正则约束

    • 适当的正则项，比如 方差正则项、稀疏正则项