函数逼近

基础

当我们使用插值时经常遇到一个问题，采样点过多怎么办？采样点如果多余真实函数的次数那么就是方程数多余未知量的数目，这时我们反而无法直接得到精确解。因此需要使用逼近的方法得到近似解。

范数

为了对线性空间中的元素大小进行衡量，引入了范数的概念。

范数的定义：

$$||x||_n = \sum_{i=1}^{n} (|x_i |^n )^{\frac{1}{n}}$$

• 1-范数： $||x||1 = \sum{i=1}^{n}|x_i |$
• 2-范数: $||x||2 = \sum{i=1}^{n} (x_i^2 )^{\frac{1}{2}}$
• $\infty -$范数: $||x||_{\infty} = \underset{1 \le i \le n}{max} |x_i |$

根据这个我们可以定义最佳逼近。函数拟合也就是函数逼近，即寻找一条曲线让他和目标曲线的差距最小。而这个差距就可以使用前面所说的范数。

• 最佳一致逼近： 在无穷范数意义下的最小值，即$||f(x) - p^* (x) ||{\infty} = \underset{p \in H_n}{min}||f(x) - p(x)|||{\infty} = \underset{P \in H_n}{min} \underset{a \le x \le b}{max}||f(x) - P(x)|$
• 最佳平方逼近： 二范数意义下的最佳逼近
• 最小二乘拟合： 离散情况二范数意义下的最佳逼近

正交多项式

首先两个向量x = $(x_1 ,x_2 , \dots , x_n )^T$和 $y=(y_1 ,y_2 ,\dots ,y_n )^T$的内积定义为：

$$(x, y) = x_1 y_1 + x_2 y_2 + \dots + x_n y_n$$

如果(x, y) = 0,则称x和y正交

连续情况下的带权正交：

$$(f(x), g(x)) = \int_{a}^{b} \rho(x) f(x)g(x) dx = 0$$

则称f(x)和g(x)在[a, b]上带权$\rho(x)$正交，若函数族$\varphi_0 (x), \varphi_1 (x) …$满足关系：

$$(\varphi_j , \varphi_k ) = \int_{a}^{b} \rho(x) \varphi_j (x) \varphi_k (x) dx = \left\{\begin{matrix} 0 & j \ne k\\ A_k > 0 & j = k \end{matrix}\right.$$

则称$\varphi_k (x)$是[a, b]上的正交函数族， 若$A_k = 1$，则成为标准正交函数族

例如： 1, cosx , sinx, cos2x, sin2x, …

• $\rho(x)$: 权函数，一般情况下都是1，但是有些时候权函数不为1可以让函数有更多变化

正交多项式的性质：

• 如果$\varphi_k (x)$是带权$\rho(x)$正交多项式，则有如下性质：

$$\begin{aligned} \varphi_{n+1} (x) &= (x - a_n ) \varphi_n (x) - \beta_n \varphi_{n-1}(x)\\ a_n &= (x\varphi_n (x),\varphi_n (x))/(\varphi_n (x), \varphi_n (x))\\ \beta_n &= (\varphi_n (x), \varphi_n (x))/(\varphi_{n-1}(x), \varphi_{n-1}(x)) \end{aligned}$$

• $\varphi_n (x)$在[a, b]上有n个不同的零点

勒让德多项式

勒让德多项式权函数为1，并且由{1, x, $\dots , x^n , \dots$)正交化得到的多项式。

表达式:

$$P_0 (x) = 1 , \quad P_n (x) = \frac{1}{2^n n!}\frac{d^n}{dx^n} (x^2 - 1)^n$$

求n阶导数后可得：

$$P_n (x) = \frac{1}{2^n n!}(2n)(2n-1)\dots (n+1)x^n + a_{n-1}x^{n-1} + \dots + a_0$$

其中$a_n = \frac{(2n)!}{2^n (n!)^2}$

性质：

• 正交性： $$\int_{-1}^{1} P_n (x) P_m (x) dx = \left\{\begin{matrix} 0 & m \ne n\\ \frac{2}{2n+1} & m = n \end{matrix}\right.$$
• 奇偶性： $P_n (-x) = (-1)^n P_n (x)$
• 递推关系： $xPn (x) = a_0 P_0 (x) + a_1 P_1 (x) + \dots + a{n+1}P_{n+1}(x)$

切比雪夫多项式

切比雪夫多项式的权函数为$\rho(x) = \frac{1}{\sqrt{1-x^2}}$，并且区间为[-1, 1]

它的表达式为：

$$T_n (x) = cos(n arccos x)$$

切比雪夫多项式的性质为：

• 递推关系：

$$T_{n+1} (x) = 2xT_n (x) - T_{n-1}(x)\\ T_0 (x) = 1 , \, T_1 (x) = x$$

• 正交结果为：

$$\int_{-1}^{1} \frac{T_n (x) T_m (x)}{\sqrt{1-x^2}}dx = \left\{\begin{matrix} 0 & m \ne n\\ \frac{\pi}{2} & n=m\ne0\\ \pi & n = m = 0 \end{matrix}\right.$$

• $T_n$ (x)在[-1, 1]上有n个零点，并且零点位置为 $x_k = cos \frac{2k-1}{2n} \pi$

• $T_n (x)$的首项$x^n$的系数为$2^{n-1}$

  根据这条性质我们可以使$T_n (x)$的首项变成1，只要令$\widetilde{T}_0 (x) = 1, \widetilde{T}_n (x) = \frac{1}{2^{n-1}} T_n (x)$

• 设$\widetilde{T}_n (x)$是首项为1的切比雪夫多项式，则

$$\underset{-1 \le x \le 1}{max} |\widetilde{T}_n (x)| \le \underset{-1 \le x \le 1}{max} |P(x)|$$

且

$$\underset{-1 \le x \le 1}{max} |\widetilde{T}_n (x) | = \frac{1}{2^{n-1}}$$

其中P(x)是任意n次多项式函数

这条定理说明了$\widetilde{T}_n (x)$的最大值小于所有多项式函数的最大值，通过它我们可以对函数最大值进行约束。

[a, b]区间上的零点

切比雪夫多项式在[-1, 1]上的零点值为$x_k = cos \frac{2k-1}{2n} \pi$

首先乘以$\frac{1}{2}$到[-1/2, 1/2]然后再向右移动1/2到[0, 1],可得：

$$x_k = \frac{1}{2} cos \frac{2k-1}{2n} \pi + 1/2$$

然后再加上a并且乘上b-a就可以得到最终结果

$$x_k = \frac{b-a}{2} cos \frac{2k-1}{2n} \pi + \frac{b+a}{2}$$

使用这些点作为插值点，就可以得到最佳结果，我们知道多项式的误差项为$\frac{f^{n+1}(\xi )}{(n+1)!} \omega{n+1}(x)$，他只会对$\omega{n+1}(x)$这一项有影响，约束了它的上界的最大值，但是对导数没有影响，因此无法完全避免龙格现象

最佳平方逼近

问题：

$$\begin{aligned} ||f(x) - S^* (x) ||_2^2 &= \underset{S(x) \in \varphi}{min} ||f(x) - S(x)||_2^2\\ &= \underset{S(x) \in \varphi}{min} \int_a^b \rho(x)[f(x) - S(x)]^2 dx \end{aligned}$$

其中S(x)就是我们拟合函数，并且它是多项式函数，它等价于q求

$$I(a_0 , a_1 , \dots , a_n ) = \int_a^b \rho(x)[\sum_{j=0}^{n}a_j x^n - f(x)]^2 dx$$

现在问题变成了求一个$a_0 , a_1 , \dots , a_n$使得误差最下化，也就是

$$\frac{\partial I}{\partial a_k} = 2\int_a^b \rho(x) [\sum_{j=0}^{n} a_j \varphi_j (x) -f(x)] \varphi_k (x) dx =0$$

也就是要求：

$$\sum_{j=0}^{n} (\varphi_k (x) , \varphi_j (x)) a_j = (f(x) ,\varphi_k (x))$$

如果$S^(x) = a_0^ + a_1^ x + \dots + a_n^ x^n$，则

$$(\varphi_k (x) , \varphi_j (x)) = \int_0^1 x^{k+j} dx = \frac{1}{k+j+1}\\ (f(x) ,\varphi_k (x)) = \int_0^1 f(x)dx = d_k$$

我们使用Ha = d进行求解，其中H称为希尔伯特矩阵，它的形式为：

$$\begin{bmatrix} 1 & \frac{1}{2} & \dots & \frac{1}{n+1}\\ \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n+2}\\ \vdots & \vdots & & \vdots\\ \frac{1}{n+1} & \frac{1}{n+2} & \dots & \frac{1}{2n+1} \end{bmatrix}$$

而d为：

$$\int_0^1 f(x) x^k dx$$

使用正交函数族

如前面所示，使用正交函数族会极大的简化$(\varphi_k (x) , \varphi_j (x))$的求解，因为$(\varphi_k (x) , \varphi_j (x)) = 0 \quad 当k \ne j$

于是我们需要求解的a的解变为：

$$a_k^* = (f(x), \varphi_k (x)) / (\varphi_k (x), \varphi_k (x))$$

因此最佳逼近函数为：

$$S^* (x) = \sum_{k=0}^{n} \frac{(f(x), \varphi_k (x))}{||\varphi_k (x)||_2^2} \varphi_k (x)$$

最小二乘法

在实际应用中，我们往往得到的是一组试验点数据，而我们要凭借它去拟合曲线。也就是我们要寻找一个函数$S^* (x)$使得：

$$|| \delta || = \sum_{i=0}^{m} \delta^2 = \underset{S(x) \in \varphi}{min} \sum_{i=0}^{m}[S(x_i ) - y_i ]^2$$

并且$S(x) = a_0 \varphi_0 (x) + \dots + a_n \varphi_n (x)$

和上面类似，经过求导和变换之后问题可以变成$\sum_{j=0}^{n}(\varphi_k , \varphi_j ) a_j = d_k$，也就是Ga = d，其中G为

$$\begin{bmatrix} (\varphi_0 , \varphi_0 ) & (\varphi_0 , \varphi_1 ) & \dots & (\varphi_0 , \varphi_n )\\ (\varphi_1 , \varphi_0 ) & (\varphi_1 , \varphi_1 ) & \dots & (\varphi_1 , \varphi_n )\\ \vdots & \vdots & & \vdots\\ (\varphi_n , \varphi_0 ) & (\varphi_n , \varphi_1 ) & \dots & (\varphi_n , \varphi_n ) \end{bmatrix}$$

同样使用正交多项式可以简化求解。因为正交多项式满足

$$(\varphi_j , \varphi_k ) = \int_{a}^{b} \rho(x) \varphi_j (x) \varphi_k (x) dx = \left\{\begin{matrix} 0 & j \ne k\\ A_k > 0 & j = k \end{matrix}\right.$$

因此前面的解可以转化为

$$a_k^* = \frac{f , \varphi_k}{\varphi_k , \varphi_k} = \frac{\sum_{i=0}^{m} \omega (x_i ) f(x_i ) \varphi_k (x_i )}{\sum_{i=0}^{m} \omega (x_i ) \varphi_k^2 (x_i )}$$

这里的$\varphi_k$可以使用递推公式进行求解，并且现在P(x)就是$\varphi(x)$

$$\begin{aligned} & P_0 (x) = 1\\ & P_1 (x) = (x-a_1 ) P_0 (x)\\ & P_{k+1} (x) = (x - a_{k+1}) P_k (x) - \beta_k P_{k-1} (x) \end{aligned}$$

其中$a_{k+1}$和$\beta_k$的值为

$$\alpha_{k+1} = \frac{(xP_k (x) , P_k (x))}{(P_k (x) , P_k (x))} = \frac{(xP_k , P_k )}{(P_k , P_k )}\\ \\ \beta_k = \frac{(P_k , P_k )}{(P_{k-1} , P_{k-1})}$$

并且拟合曲线为：

$$y = S(x) = a_0^* P_0 (x) + a_1^* P_1 (x) + \dots + a_n^* P_n (x)$$

function square_fit_ans = square_fit(x, y, n, stage, test_x, m)
    alpha_factor = zeros(1, stage+1);
    p = zeros(stage+1, n+1);
    alpha = zeros(1, stage+1);
    beta = zeros(1, stage+1);
    alpha(2) =  sum(x) / (n+1);
    p(1, :) = 1;
    for i=1:n+1
        p(2, i) = x(i) - alpha(2);
    end
    
    for i=3:stage+1%计算alpha beta p
        a = 0;%分子
        b = 0;%分母
        b1 = 0;%beta的分母
        for k=1:n+1
            temp = p(i-1, k) * p(i-1, k);
            b = b + temp;
            a = a + x(k) * temp;
            b1 = b1 + p(i-2, k) * p(i-2, k);
        end
        alpha(i) = a / b;
        beta(i) = b / b1;
        for k=1:n+1
            p(i, k) = (x(k) - alpha(i)) * p(i-1, k) - beta(i) * p(i-2, k);
        end
    end
    
    for i=1: stage+1 % 计算alpha*
        a = 0;
        b = 0;
        for k=1:n+1
            a = a + y(k) * p(i, k);
            b = b + p(i, k) * p(i, k);
        end
        alpha_factor(i) = a / b;
    end
    
    square_fit_ans = zeros(1, m);
    for i=1:m
        p1 = 1;
        p2 = (test_x(i) - alpha(2));
        square_fit_ans(i) = alpha_factor(1) + alpha_factor(2) * p2;
        for k=3:stage+1
            temp = (test_x(i) - alpha(k)) * p2 - beta(k) * p1;
            square_fit_ans(i) = square_fit_ans(i) + alpha_factor(k) * temp;
            p1 = p2;
            p2 = temp;
        end
    end
end