作者：老李
时间：2019-10-26

目标：

给出一组非线性相关的函数作为基底，通过有限点集$(x_k,y_k)$，构造拟合函数

过程：

我们设这个基底为 { f i ( x ) } , i = 1 , 2 , . . . M \left \{f _{i}(x)\right \},i= 1,2,...M {fi​(x)},i=1,2,...M
我们的目标是,对于每一个$x_k$寻找一系列$c_i$,使得$E={\sum }_{k=1}^n(c_i{f}_i(x_k)-y_k{)}^2$最小。

我们使用最一般的方法：将E对每一个参数$c_i$进行求导，然后令其导函数为零，最后求出其值。

$$\frac{\partial E}{\partial c_i}=\sum _{k=1}^N((\sum _{j=1}^M{c}_j{f}_j(x_k))-y_k)f_i(x_k)=0,i=1,2,...M\text{\hspace{1em}(1)}$$

为了实现矩阵化操作，我们想要将所求的系数$c_i$分离出来，于是我们改变求和的次序，可得：$$\sum _{j=1}^M(\sum _{k=1}^N{f}_i(x_k)f_j(x_k))c_j=\sum _{k=1}^N{f}_i(x_k)y_k\text{\hspace{1em}(2)}$$

最后我们对其实现矩阵化操作：
我们令$$F=\left[\begin{array}{cccc}{f}_1(x_1)& f_2(x_1)& \cdots & f_M(x_1)\\ f_1(x_2)& f_2(x_2)& \cdots & f_M(x_2)\\ ⋮& ⋮& \ddots & ⋮\\ f_1(x_N)& f_2(x_N)& \cdots & f_M(x_N)\end{array}\right]$$可以将（2）式用矩阵表达出来$$F^{\prime }FC=F^{\prime }Y$$
求得的系数矩阵$C$为$$C=(F^{\prime }F{)}^{-1}{F}^{\prime }Y$$
我用matlab实现了这个过程，代码如下：
吐槽一点，csdn粘贴matlab代码挺麻烦的

function [ C ,err] = leastSquareApprox( X,Y,fun)
%leastSquareApprox: least square approximation by linear combination of nonlinear correlation equations
%   Input: X is the 1*n abscissa vector
%        : Y is the 1*n ordinate vector
%        : fun is the n*1 based function
%  Output: C is the coefficient list for the function
%        : err is the maximum of the least square approximation for each point
if  (length(X) ~= length(Y))
    error('wrong size');
else
    n = length(X);
    X0 = reshape(X,n,1);
    F = subs(fun, X0);
    C = (pinv(F'*F))*F'*Y;
    
    Xt = min(X):0.1:max(X);
    ft = subs(fun, Xt')*C;
    
    scatter(X,Y);
    hold on;
    plot(Xt,ft,'r');
    hold off;
    f0 = subs(fun, X)*C;
    err = max((f0-Y).^2);
end
end

这里需要特别注意的一点是输入的fun这个参数，是我们作为最小二乘拟合(最佳平方逼近)的函数。

这里我来展示一下怎么去实现这个基函数。
这里，我的基函数通过符号变量来表达，
我们可以选择多项式作为基底，当我们输入记得的数量n时，该基底可以表示为
$$\left\{1,x,x^2,x^3,\cdots ,x^{n-1}\right\}$$
(如果我们不去讨论这组基的具体在所张成的空间的定义，或者说不一定要符合在该空间多定义出的的正交这一性质的话，也就是说我们只要保证基底中的元素不能直接相互表示的话)
我们可以写一段程序来实现它：(syms和sym 用来定义符号变量)

n = input('please input the size of the data ');
syms x;
B = sym(zeros(1,n));
for i = 0:n-1   
    B(i+1) = x.^i;
end

这样，我们就把作为基底的多项式输出出来了。

效果

假设我们只输入五个点：对应的自变量X=[1，2，3，4，5]和因变量Y=[15，64，84，12，34]
这里我先选用3个基底（n=3）来进行拟合，也就是二次函数拟合：
得到的效果如下：

输出的数值为：

其中误差为d

关于误差的讨论

已知i我们输入的为5个点，n为基底中元素的个数

当我们令n=5时，由范德蒙德行列式，我们可以知道，当我们输入的点不同时，该行列式的值不为0，也就是说，插值函数是具有唯一性的。也就是说，无论我们用的是拉格朗日插值还是牛顿插值，还是这里用到的矩阵运算，我们得到的东西是一样的。而不同的插值方法的功效主要还是体现在计算机的运行效率上，比如牛顿插值用到了递归的方法从而节约了运算的时间。

当我们把n变为>5的数，我们可以保证逼近出来的曲线是过每一个点的，所得出来的误差应该为0。但由于插值函数的唯一性，我们不应该认为这是插值，但这样的一个方法应该叫什么，我现在并不清楚，也许以后会学到并理解。

我们这里把n设为8
结果如下：

写在最后

1.在计算机实现逼近的过程中，输入的变量与输出的变量一定是离散且有限的，也就是说，在计算机数值计算中，我们用的大多为$\sum$而不是$\int$。

2.假如我们输入的是N个点，假如我们使用的基底（不能相互表示）中元素的数量是>=N的，那我们逼近出来的曲线一定是过我们输入的每一个点的，（=N的时候是为插值）。

3.同样，我们也可以注意到，其实DFT算法的核心思想与我今天所写的其实是一致的。唯一不同的是他运用的是$e^{-\frac{2\pi im}{N}}$作为基底，其中$m=0,1,2,\cdots ,N-1$。

过程有点麻烦，我直接贴照片吧，参考自《线性代数（李尚志）》2.7节 子空间的交与和 例4

一、线性规划求解

---

在上一篇博客 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 中 , 将线性规划的等式表示为以下形式 :

$$B{X}_B+N{X}_N=b$$

写成上述形式之后 , 就可以表示出上述等式的解 , 如果上述等式解满足线性规划约束变量的要求 , 即所有的变量都大于等于 0 , 那么该解就是线性规划的解 ;

上述式子中 , $X_N$ 非基变量 , 是可以随意取值的变量 ;

只要非基变量 $X_N$ 取定一组解 , 基变量 $X_B$ 就可以被唯一确定 ;

$\left(\begin{array}{c}{X}_B\\ X_N\end{array}\right)$ 就是 方程组完整的解 ;

二、根据非基变量的解得到基变量解

---

如何根据非基变量 $X_N$ 的解 , 确定基变量 $X_B$ 的解 ?

基矩阵 $B$ 是可逆的 , 那么 $B$ 的逆矩阵 $B^{-1}$ 是存在的 , 上述方程 $B{X}_B+N{X}_N=b$ 左右两端 , 都乘以 $B^{-1}$ , 如下计算 :

$$\begin{array}{lcl}B{X}_B+N{X}_N& =& b\\ & & \\ (B{X}_B+N{X}_N)\times B^{-1}& =& B^{-1}b\\ & & \\ I\times X_B+B^{-1}N{X}_N& =& B^{-1}b\\ & & \\ X_B& =& B^{-1}b-B^{-1}N{X}_N\end{array}$$

其中 $I$ 是单位阵 , 单位阵乘以矩阵 $X_B$ 其结果还是 $X_B$ ;

关于单位阵 , 参考 单位矩阵 - 百度百科

上述式子最终得到 $X_B=B^{-1}b-B^{-1}N{X}_N$ , 此时 如果非基变量的值 $X_N$ 已经解出来 , 那么 基变量 $X_B$ 可以通过上述表达式表示出来 ;

三、基解

---

给定一个基矩阵 $B$ , 约束方程可以转化成 $X_B=B^{-1}b-B^{-1}N{X}_N$ 形式 , 只要给定一组 $X_N$ 的解 , 就可以 得到一组 $X_B$ 的解 ;

非基变量 $O$ 解 : 找到 $X_N$ 的一组最简单的解 , 这里随意找一组 $X_N$ 的解都可以 , 最简单的一组解就是 $X_N$ 的所有值都是 $0$ , 即让所有的非基变量等于 $0$ , 此时 $X_N$ 为零矩阵 , 使用 $O$ 表示 ;

对应基变量的解 : 将所有的非基变量等于 $0$ , 即 $X_N=O$ 的条件代入 $X_B=B^{-1}b-B^{-1}N{X}_N$ 中 , 有 :

$$X_B=B^{-1}b$$

此时线性规划的解为 : $\left(\begin{array}{c}{B}^{-1}b\\ O\end{array}\right)$ , 其中 $O$ 是零矩阵 ; 该解就是线性规划的基解 ;

基矩阵 $B$ -> 非基变量解 $O$ -> 基变量解 $B^{-1}b$ : 基解最根本是先确定基矩阵 $B$ , 确定 基矩阵 $B$ 之后 , 就可以将变量分为基变量 和 非基变量 , 此时将非基变量取值为零矩阵 $O$ , 得到基变量的解 $B^{-1}b$ ;

基解 $X_B$ 是由基矩阵 $B$ 唯一确定的 ; 只要给定基矩阵 , 就可以唯一确定基解 ;

基解个数 : 一个线性规划中的基解个数 , 就是基矩阵可数 , 就是可逆矩阵个数 ;

通常情况下的基解个数 : 系数矩阵 $A$ , 是 $m\times n$ 维的矩阵 , $m$ 行等式 , $n$ 个变量 , 其任意 $m$ 列向量 , 组成的 $m$ 阶方阵 , 都是可逆矩阵 , 其有 $C(n,m)$ 个基矩阵 , 也有 $C(n,m)$ 组基解 ;

基解定义 : 确定一个 $m\times n$ 阶系数矩阵的基矩阵 $B$ , 令非基变量 $X_N$ 等于 $0$ , 有约束条件 $X_B=B^{-1}b-B^{-1}N{X}_N$ 可以解出其基变量 $X_B$ , 这组 $\left(\begin{array}{c}{B}^{-1}b\\ O\end{array}\right)$ 解 , 称为基解 ; 基解中的变量取非 $0$ 值的个数 , 不超过等式个数 $m$ , 基解总数不超过 $C(n,m)$ ;

四、基可行解

---

完整的线性规划标准形式如下 :

$$\begin{array}{l}maxZ={\sum }_{j=1}^n{c}_j{x}_j\\ \\ s.t\{\begin{array}{ll}{\sum }_{j=1}^n{a}_{ij}{x}_j=b_i& i=1,2,\cdots ,m\\ & \\ x_j\ge 0& j=1,2,\cdots ,n\end{array}\end{array}$$

上述的基解 , 只是根据 ${\sum }_{j=1}^n{a}_{ij}{x}_j=b_i(i=1,2,\cdots ,m)$ 约束条件等式解出的 ;

还需要满足 $x_j\ge 0(j=1,2,\cdots ,n)$ 条件 ;

基可行解定义 : 满足线性规划中的 $x_j\ge 0(j=1,2,\cdots ,n)$ 约束条件的 基解 , 称为 基可行解 ;

给定线性规划系数矩阵 $m\times n$ 阶 :

• 其可行解个数是无限的 , 因为其非基变量 $X_N$ 可以有无限种取值 , 对应的基变量 $X_B$ 也有无限种取值 ;
• 其基解个数是有限的 , 因为非基变量只能取 $O$ 零矩阵 , 对应的基变量也是有限的 , 不超过 $C_n^m$ 个 ;

可行解有无穷多个 , 基解是有限个 , 如果一个解既是基解 , 又是可行解 , 那么称该解是基可行解 ;

基解个数是有限的 , 基可行解 是 基解 与 可行解 的交集 , 基可行解的个数必然也是有限的 ;

迭代思想 : 在解里面找到一个解 , 看该解是否是最优的 , 如果不是 , 就迭代到下一个解 , 继续重复查看该解是否是最优 ; 如果迭代的集合是有限的 , 其肯定要比无限的集合简单很多 ;

因此线性规划中 , 在有限个基可行解中 , 迭代查找最优解 , 将搜索范围从无限个可行解 , 变成了有限个基可行解 ;

五、可行基

---

可行基 : 基可行解 对应的 基矩阵 $B$ , 就是 可行基 ;

使用 $X_B=B^{-1}b-B^{-1}N{X}_N$ , 代入 $X_N=O$ , 解出其基变量 $X_B$ , 这组 $\left(\begin{array}{c}{B}^{-1}b\\ O\end{array}\right)$ 基解 , $X_N$ 中的非基变量解肯定是大于等于 $0$ 的 , 如果 $B^{-1}b$ 中有负分量 , 那么该解不是基可行解 , 对应的基矩阵 $X_B$ 不是可行基 ;