对未来的最大慷慨，是把一切献给现在。
函数逼近需要解决的问题
给定区间上的复杂连续函数逼近问题
第一类问题：我们已知在给定区间上的连续函数，但是这个函数不方便直接计算，我们需要用更加简单的函数来逼近它。比如让你计算$\sin2$，这是不太好直接计算出来的，再比如给定[0,1]上的函数$\sqrt{x^2+1}$，求$x=0.5$时的值，直接算也是不太好算的，因为要开根号，那么我们希望在这个给定区间上找到一个简单函数去逼近这个已知的复杂函数从而方便计算。假设要用一个一次多项式$P_1(x)$来对$\sqrt{x^2+1}$逼近，我们容易得想到用泰勒展开式，$x=0$处的泰勒展开式为$P_1(x)=1$，这明显与原函数的误差很大。如果在$x=0,1$处使用一次插值多项式，那么可以得到$P_1(x)=(\sqrt{2}-1)x+1$，在两个端点是没有误差的，但在[0,1]的中点附近误差很大。如果我们在曲线中间部分做个切线呢？比如我们平移$P_1(x)=(\sqrt{2}-1)x+1$，使得它与原函数相切，近似得到$P_1(x)=0.4142x+0.9060$，这个函数虽然在中点处的误差小了，但是在两端的误差又变大了。
实际上，我们从图形可以很直观的看出来，最优的直线逼近是处在红绿两条线之间某一个位置上，需要把红色的直线向下平移一点，或者把绿色的直线向上平移一点，找到一个“中间的位置”，能够保证总体的误差比较小。那么这个平移我们是怎么想到的呢？这个问题我们是很容易能够看出来的，如果是更加复杂的函数呢？或者不是二维而是高维的函数呢？因此，我们需要一个更加一般化的方法，找一条简单的曲线，跟给定区间上的复杂函数整体逼近比较好，那么什么样算是逼近效果好，什么样的是不好呢？我们也需要一个更加一般化的度量方法，去判断逼近的好坏和差异。
给定数据点下的函数逼近问题
第二类问题：给定了一组数据，我们怎用简单函数来逼近它。我们只知道一个函数的一些点信息，并不知道原函数的表达式到底是什么样子。比如对于人口增长曲线，是一个S型的曲线，已知的是数据点的信息，那么用什么样的一条曲线去逼近呢？根据经验，可以采用logistic函数，但是这是凭经验了，数据分布的区间不是很大还可以，如果数据分布的区间很大很复杂，是很难用一个简单的函数去很好的逼近的。所以我们也需要去讨论一个更一般化的方法。
小节
从上述两类问题我们可以抽象出函数逼近需要解决的几个核心问题：
在给定区间$[a,b]$上用简单函数逼近已知复杂函数，寻找一种一般化的方法构造这个简单函数
寻找一种度量逼近好坏的工具，帮助我们判断逼近的好坏
标准定义：
函数逼近，是指对函数类A中给定的函数$f(x)$，记为$f(x)\in A$，要求在另一类简单的便于计算的函数类B中求函数$p(x)\in B$，使$p(x)$与$f(x)$的误差在某种度量意义下最小。其中函数类A通常是区间$[a,b]$上的连续函数，记作$C[a,b]$，称为连续函数空间，而函数类B通常为$n$次多项式，有理函数或分段低次多项式等。
预备知识
—————高能预警，前方涉及的概念相当抽象，如有不适请先服用线性代数—————
集合与函数空间
数学上常把在各种集合中引入某些不同的确定关系称为赋予集合以某种空间结构，并将这样的集合称为空间。
例如：将所有实$n$维向量组成的集合，按向量加法及向量与数的乘法构成实数域上的线性空间，记作$\mathbb {R}^n$，称为$n$维向量空间。
类似的，对于次数不超过$n$的实系数多项式全体，按通常多项式与多项式加法以及多项式与数的乘法也构成数域$\mathbb {R}$上的一个线性空间，用$H_n$表示，称为多项式空间。
所有定义在$[a,b]$上的连续函数集合，按函数加法和函数与数的乘法构成数域$\mathbb{R}$上的线性空间，记作$C[a,b]$。类似地，记$C^p[a,b]$为具有$p$阶连续导数的函数空间。
上述内容十分抽象，我自己理解起来也是模棱两可。简单谈一谈我自己理解，为什么要在这里提函数空间的问题，实际上，从线性代数里面就可以知道，$n$维向量空间中的任何一个向量，都可以通过两个线性无关的$n$维向量的向量加法和向量与数的乘法进行构造。这里的函数逼近正是利用了这个思想，它将一个复杂函数看成是函数空间中的一个向量，然后利用简单多项式构造函数空间中的基，从而通过基的向量相加和数乘对复杂函数进行”表示”（事实上连续函数空间是无限维的，是无法通过有限的基完全表示的）和逼近。还记得在线性代数的本质：线性组合讲到得“向量可以是任何东西，只要保证两个向量相加以及数字与向量相乘是有意义得”吗？我认为这里就利用了这个思想，所以一个函数也可以看成是向量，而所有函数的集合，再加上加法和数乘两种运算以后，就构成了一个线性函数空间。
对于线性空间（这里不仅仅是n维向量空间了）上的线性相关的定义，其实是和以前没有差别的：
设集合$S$是数域$P$上的线性空间，元素$x_1,x_2,\cdots, x_n\in S$，如果存在不全为零的数$\alpha_1,\alpha_2,\cdots,\alpha_n\in P$，使得
则称$x_1,x_2,\cdots,x_n$线性相关，否则若只对$\alpha_1=\alpha_2=\cdots=\alpha_n=0$成立，则称$x_1,x_2,\cdots,x_n$线性无关。
若线性空间$S$是由$n$个线性无关元素$x_1,x_2,\cdots,x_n$生成的，即对$\forall x\in S$都有
则称$x_1,x_2,\cdots, x_n$是空间$S$的一组基，记为$S = \mathbf{span}\{x_1,x_2,\cdots,x_n\}$，并称空间$S$为$n$维空间，系数$\alpha_1,\alpha_2,\cdots,\alpha_n$称为$x$在基$x_1,x_2,\cdots, x_n$下的坐标，记作$( \alpha_1,\alpha_2,\cdots,\alpha_n)$，如果$S$中有无限个线性无关元素$x_1,x_2,\cdots, x_n,\cdots$，则称$S$为无限维线性空间。
对于次数不超过$n$的多项式集合$H_n$，其元素$p(x)\in H_n$表示为：
它由$n+1$个系数$(a_0,a_1,a_2,\cdots,a_n)$唯一确定。$1,x,x^2,x^3,\cdots x^n$线性无关，它是$H_n$的一组基，即$H_n = \mathbf{span}\{1,x,x^2,x^3,\cdots,x_n\}$，且$(a_0,a_1,a_2,\cdots,a_n)$是$p(x)$的向量坐标
对连续函数$f(x)\in C[a,b]$，它不能用有限个线性无关的函数表示，故$C[a,b]$是无限维的，但它的任一元素$f(x)\in C[a,b]$均可用有限维的$p(x)\in H_n$逼近，使误差$\underset{a \le x \le b }{\operatorname{max}}|f(x)-p(x)|<\epsilon$（$\epsilon$为任给的小正数），这就是著名的Weierstrass定理
因此Weierstrass定理给函数逼近提供了一条思路，通过有限维线性多项式空间中的向量（也就是由若干基的线性组合）来逼近无限维连续函数空间中的向量（也就是已知的连续函数）
范数与赋范线性空间
如果说我们能用有限维多项式空间中的向量来“表示”无限维连续函数空间中的向量，那么我们应该如何来衡量这两个向量的大小，也就是说判断我们这个逼近的好坏呢？这时候就需要引入范数的概念。
为了对线性空间中元素大小进行衡量，需要引进范数定义，它是$\mathbb {R}^n$空间中向量长度概念的直接推广。对于在$\mathbb {R}^n$上的向量$\vec x=(x_1,x_2,\cdots,x_n)^T\in \mathbb R^n$，有三种常用范数：
$\infty$-范数或最大范数：
1-范数：
2-范数：
类似地对于连续函数空间$C[a,b]$，若$f\in C[a,b]$可定义三种常用范数如下：
$\infty$-范数：
1-范数：
2-范数：
内积与内积空间
有关内积的内容夹杂在后文中（TODO：内积与范数的区别，参考线性代数应该这样学P107页补充这一部分）
正交多项式
离散点集上的正交多项式
定义：设有点集$\{x_i\}_{i=0,1,\cdots,m}$，函数$f(x)$和函数$g(x)$在离散意义下的内积定义为$(f,g)=\sum_{i=0}^mw_if(x_i)g(x_i)$其中，$w_i>0$在这里是给定的权数，也就是两个函数对应的函数值相乘再乘上一个权重的总和，称为内积。在离散意义下，函数$f(x)$的2-范数的定义为：$||f||_2=\sqrt{(f,f)}$
为什么要定义这个内积呢？在给定一些数据点的时候，只是告诉了一些元素，相当于是告诉了我们一个集合。集合中的元素如何做运算并没有说，如果连怎么样做运算都没说那么就谈不上点与点之间的距离，没有距离那我们就无法衡量最近和最远。所以数学中讲空间，是要有运算的，平时可能我们讲空间的时候不太注意，认为空间可能就是一个容纳东西的一个范围，比如一个间教室就是一个空间，但是这其中还隐含着这个教室里面坐第一排的学生和坐最后一排的学生是有一个距离存在的，这个距离是有一种计算的方式的，比如欧氏距离，现实生活中的空间就已经有运算的含义在里面了。那么对于数学中的空间呢？只告诉了元素是不够的，必须要讲明怎么算，如果没有讲清楚怎么算，那么这一些元素我们只能称之为集合，一个集合里面有元素，那么这个集合中的元素再加上运算我们才能讲空间。有了内积之后，我们就可以衡量一个东西的大小，实际上也就可以衡量距离了。比如给你一个函数，这个函数有多大呢？用函数自身与自身的内积再开平方，就是这个函数的大小，也就是2-范数，记为$||f||_2$。这里的2指的是度量的方法，举个例子，用不同的单位长度表示一段距离，米和英寸的数字结果表示是不一样的，有很多种度量的方法，2-范数就是指用乘积再开方的方式算出来的距离。
有了内积我们才好谈误差，逼近的好坏就体现在误差的大小上。那么正交呢？正交就是指内积等于零。从几何的角度，正交就是垂直，那么现在对于函数，这个垂直就不那么形象了，我们就说内积等于零称为正交。自身与自身的内积一般是不等于零的，除非这个函数在所有点上的值都为零。内积等于零是两个函数之间的正交，那么多个函数正交呢？有下面的定理：若多项式组$\{\phi(x)\}_k=0,1,\cdots,n$在离散意义下的内积满足：
也就是多项式组中任意两个函数的内积都为零，但自身与自身的内积大于零。注意一下这里包括之前定义内积使用的数学符号，数据点集是有$m$个，多项式组中的函数有$n+1$个，即第i个函数和第j个函数在所有点上的函数值的乘积再乘上权数求和，就是内积$(\phi_i,\phi_j)=\sum_{k=0}^{m} w_k\phi_i(x_k)\phi_j(x_k)$。接下来我们就再看怎么把这个正交多项式给“造”出来，正交函数到底是一个什么样的函数？有下列公式：给定点集$\{x_i\}_{i=0,1,\cdots,m}$和权数$\{w_i\}_{i=0,1,\cdots,m}$，并且点集$\{x_i\}_{i=0,1,\cdots,m}$中至少有n+1个互异，则由下列三项递推公式：
例如$P_2(x)=(x-a_1)P_1(x)-b_1P_0(x)=(x-a_1)(x-a_0)-b_1$，按照这个形式，可以一直递推下去。但是$a_0,a_1,b_1,\cdots,a_k,b_k$这些变量我们还不知道，通过这些系数保证我们的多项式是正交的。令
这个方程中除了$a_0$以外所有的值我们都知道，所以可以可以求解这个方程得到
从而也就确定了$P_1(x)$。可以看到计算$a_0$的这个方程很大，不方便记忆，所以我们就尽量把这个记号化成我们熟悉的记号
这里$(x,1)$就是$x$在$k$点的值和1在$k$点的值的乘积的和，就是$x$和1的内积，$(1,1)$也是同样的道理。
那么类似的我们可以推导$a_1,b_1$，比如$P_2(x)$，它里面有$a_1,b_1$两个未知数，而且它同时要和$P_0(x),P_1(x)$正交，也就是要令$(P_0,P_2)=0，(P_1,P_2)=0$，那么这两个形成的等式就正好可以把两个未知数解出来。当把每个递推函数中的未知量用内积的符号来表示了之后，就很简洁了：
看一个例子：已知点集$\{x_i\}_{i=0,1,\cdots,4}={0,0.25,0.5,0.75,1}$和权数$\{w_i\}_{i=0,1,\cdots,4}={1,1,1,1,1}$，试用三项递推公式求关于该点集的正交多项式$P_0(x),P_1(x),P_2(x)$
$P_0(x)=1,P_1(x)=x-a_0$,$a_0=\frac {(xP_0,P_0)}{(P_0,P_0)}=\frac{(x,1)}{(1,1)}=2.5/5=0.5$，所以$P_1(x)=x-0.5$，显而易见，$P_1(x)$和$P_0(x)$在数据点上的值相乘，求和以后是等于零的。
注意这里的权数都为1，意味着我们不对这些点集的重要性加以区分，每个点的权重都是一样的。而点集里元素的多少跟多项式个数的多少是完全无关的，不是说点集里面有5个点，多项式就只能做5个，它们之间不存在这样的关系，只要你愿意递推下去，你想要多少多项式就可以做出多少多项式。后面的多项式的计算以此类推。
连续区间上的正交多项式
上面讨论得是离散点的正交多项式，现在我们讨论连续区间上的正交多项式。我们已知的不是离散点，而是[a,b]区间上的函数。正交的概念与上面还是一样的，内积等于零。正交多项式的推导过程也与上面一样是三项递推公式。但是需要注意的是，两个函数在离散点上求内积的时候是两者在离散点上的函数值的乘积的和，而两个连续函数在区间上有无数个函数值，无数个函数值是无法进行乘积再求和的，因此这个时候就不能单一的乘积做和了，而是使用积分，对于每个点的权数$w_i$也在这里变为了权函数$w(x)$。函数$f(x)$和$g(x)$在连续意义下的内积定义为$(f,g)=\int_a^bw(x)f(x)g(x)dx,f,g\in C[a,b]$。
离散意义下的正交多项式，直接把离散点带进去，用三项递推公式，算出来多少就是多少。而对于连续区间上的正交多项式，我们可以事先把一些常用的、性质比较好的正交多项式建立起来，然后方便在其他问题中使用。
Legendre多项式
当区间为[-1,1]，权函数$w(x)=1$时，由$\{1,x,\cdots,x^n,\cdots\}$正交化得到的多项式称为Legendre多项式，记为$\{P_i(x)\}_{i=0}^n$，由三项递推公式得
$P_n(x)=\frac{1}{2^nn!}\frac{d^n}{dx^n}(x^2-1)^n$这个公式是对Legendre多项式不同的定义产生的，我们在计算机上编程序算的过程中喜欢用三项递推公式，很方便。但是在分析它的一些性质的时候，这个表达式比三项递推公式更加方便。例如：
- 正交性：$(P_n,P_m)=\int_{-1}^1P_n(x)P_m(x)dx=\begin {cases} 0, n\neq m\\ \frac{2}{2n+1}, n=m\end{cases}$
虽然Legendre多项式是在[-1,1]这个具体区间上定义的，但是并不影响其一般性，也就是说如果是在区间[a,b]上也是可以的，只需要做一个平移，把区间[a,b]化为[-1,1]。因此Legendre多项式实际上是在有限区间上带权函数为1的正交多项式。转换的方法也很简便，例如$x\in[a,b]$，设$t=\alpha x+\beta$，然后找到$\alpha$和$\beta$使得$t\in[-1,1]$就可以了，也就是$\begin {cases} \alpha a+\beta=-1\\ \alpha b+\beta=1\end{cases}$，解出来就OK。
Chebyshev多项式
当权函数$w(x)=\frac{1}{\sqrt{1-x^2}}$，区间为[-1,1]时，由$\{1,x,\cdots,x^n,\cdots\}$正交化得到的多项式称为Chebyshev多项式，也称第一类Chebyshev多项式，由三项递推公式得
那么两个函数的内积为$(T_i,T_j)=\int_{-1}^{1}\frac {T_i(x)T_j(x)}{\sqrt{1-x^2}}$
$T_n(x)=\cos (n \arccos x), |x|\le1$，是个假的三角函数
