正交多项式与函数逼近
最后更新时间:
引言
寻找函数逼近的之前考虑以下问题： - 已知函数解析形式，但过于复杂不变计算，希望有更简单的函数来代替原函数 - 不知道函数的解析形式，但知道一些离散点的值，同样想要找到一个较为简单的函数来逼近离散数据
通常的简单函数包括：多项式函数、三角函数、指数函数等，但本节只会讨论多项式函数。（明显多项式比其他的还有简单hhh）
寻找函数逼近，实际上就是想要找到下面这个式子
\[ ||f(x)-P(x)|| \]
在某种范数意义下，尽可能小，同时多项式的次数也尽可能小。
常见的范数： - 2范数----------平方逼近 - 无穷范数--------一致逼近
还有就是，离散数据的最佳平方逼近多项式，就是通常所说的“最小二乘法”，这是在自然科学当中及其常用的方法。
本节介绍函数逼近之前先从介绍正交多项式开始。 正交多项式理论有助于我们寻找函数逼近，在最佳一致逼近和最佳平方逼近中都有应用。并且在后续章节中也能看到正交多项式的身影（Gauss求积公式）
正交多项式
前提须知（内积空间理论）
定义
- 内积空间
- 正交的定义
- 由内积诱导的范数
- Cauchy-Schwarz不等式
\[ |<f,g>|\leq ||f||||g|| \]
- 范数是什么 （满足非负性、线性和三角不等式性质的函数）
- 线性附范空间 （给内积空间配以范数）
- 权函数 （在开区间上定义的正的、连续的、可积的函数）
正交多项式的概念和性质
设\(P_n\)为次数不超过n次的多项式的集合.在\(P_n\)上定义内积
\[ <p_n,p_m>=\int_{a}^{b}\rho(x)p_n(x)p_m(x)\,dx,\quad \forall p_n(x)p_m(x)\in P_n \]
其中\(\rho(x)\)为定义在\((a,b)\)上的权函数.相应的诱导范数为
\[ ||p_n||^{2}_{2}=\int_{a}^{b}\rho(x)p_n^2(x)\,dx \]
正交多项式系
定义:设\(\rho(x)\)为定义在\((a,b)\)上的权函数,如果多项式序列\(\{p_j\},j=0,1\cdots\)满足一下条件: - \(p_j\)的次数为j -
\[ <p_k,p_j>=\int_{a}^{b}\rho(x)p_k(x)p_j(x)\,dx=\left\{\begin{matrix} 0 \quad k\neq j\\ \neq 0 \quad k=j \end{matrix}\right. \]
则称\(\{p_j\},j=0,1\cdots\)为正交多项式序列.
生成首1的正交多项式
一般可以通过以下两种办法生成: (1)Gram-Schmidt正交化
设\(p_0(x)=1\),假设\(\{p_j\},j=0,1\cdots,n\)已经存在并且正交,下面将构造\(p_{n+1}(x)\).令
\[ q(x)=x^{n+1}-\sum_{j=0}^{n}a_jp_j(x) \]
其中,
\[ a_j=\frac{<x^{n+1},p_j>}{<p_j,p_j>},j=0,1\cdots,n \]
显然\(q(x)\)是次数为n+1且首系数为1的多项式,
下面验证它与其他的多项式正交,对\(i=0,1\cdots,n\)
\[ <q,p_i>=<x^{n+1}-\sum_{j=0}^{n}a_jp_j(x),\,p_i>=<x^{n+1},p_j>-\sum_{j=0}^{n}a_j<p_j,p_i> \]
\[ =<x^{n+1},p_j>-a_j<p_j,p_j>=<x^{n+1},p_j>-\frac{<x^{n+1},p_j>}{<p_j,p_j>}<p_j,p_j>=0 \]
故\(q(x)\)就是我们要找的\(p_{n+1}(x)\). 值得说明的是:这样的构造方法,每新增一项要用到其他所有的多项式,这显然是不便于我们计算的,因此这种方法的理论价值大于实际应用价值.
下面介绍的构造方法只用到的相邻的前两项.
(2)三项递推公式
\[ \begin{aligned} \begin{cases} &p_0(x)=1\\ &p_1(x)=(x-a_0)p_0(x)=x-a_0\\ &p_{n+1}(x)=(x-a_n)p_n(x)-b_{n-1}p_{n-1}(x) \end{cases}\end{aligned} \]
其中,
\[ a_n=\frac{<xp_n,p_n>}{<p_n,p_n>} \]
\[ b_n=\frac{<p_n,p_n>}{<p_{n-1},p_{n-1}>} \]
证明: 数学归纳法.
重要命题
命题: 由上面两种方式生成的正交多项式\(p_n(x),n\geq 1\)在定义域\([a,b]\)内有n个不同的实零点.
证明: - 反证不保号(假设\(p_n(x)\)保号) - 反证无重根(假设\(x_1\)是二重根) - 反证有\(n\)个实根(假设有\(j\)个根,\(j<n\))
定理 Christoffel-Darbourx恒等式
略一下
Legendre 正交多项式系
Legendre 正交多项式系的定义域为\([-1,1]\),权函数\(\omega(x)=1\) 其表达为,
\[ P_n(x)=\frac{1}{2^n n!}\frac{d^n}{dx^n}\{(x^2-1)^2\} \]
性质
- 首项系数
\[ \frac{(2n)!}{2^n (n!)^2} \]
- 正交性质
\[ <P_n,P_m>=\int_{-1}^{1}P_n(x)P_m(x)\,dx=\begin{cases}0,m\neq n\\ \frac{2}{2n+1},m=n\end{cases} \]
- 三项递推公式
\[ \begin{cases}P_0(x)=1\\ P_1(x)=x\\ (n+1)P_{n+1}(x)=(2n+1)xP_n(x)+nP_{n-1}(x)\end{cases} \]
- 奇偶性
\[ P_n(-x)=(-1)^{n}P_n(x) \]
- 特征方程
\[ \frac{d}{dx}((1-x^2)y')+\lambda y=0,\quad \lambda = n(n+1) \]
- 边界值
\[ P_n(1)=1 \]
\[ P_n'(1)=\frac{n(n+1)}{2} \]
Tchebyshev 正交多项式系
Chebyshev正交多项式系的定义域为\([-1,1]\),权函数\(\rho (x)=\frac{1}{\sqrt{1-x^2}}\) 其表达为,
\[ T_n(x)=\cos(n\arccos(x)) \]
性质
- 三项递推公式
\[ \begin{cases}T_0(x)=1\\ T_1(x)=x\\ T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)\end{cases} \]
简要说明,令\(x=\cos\theta\),则
\[ T_{n+1}(x)=\cos((n+1)\theta) \\ T_{n-1}(x)=\cos((n-1)\theta)\\T_{n+1}(x)+T_{n-1}(x)=2\cos\theta\cos(n\theta)=2xT_{n}(x) \]
- 首项系数 从三项递推公式得出
\[ 2^{n-1} \]
- 正交性质
\[ <T_n,T_m>=\int_{-1}^{1}\frac{T_n(x)T_m(x)}{\sqrt{1-x^2}}\,dx=\begin{cases}0,m\neq n\\ \frac{\pi}{2},m= n\neq 0\\ \pi,m=n=0\end{cases} \]
- 奇偶性
\[ T_n(-x)=(-1)^{n}T_n(x) \]
数学归纳法简要证明:
\[ T_{n+1}(-x)=-2xT_n(-x)-T_{n-1}(-x) \]
由归纳假设
\[ T_{n+1}(-x)=-2x(-1)^nT_n(x)-(-1)^{n-1}T_{n-1}(x) \]
\[ T_{n+1}(-x)=2x(-1)^{n+1}T_n(x)-(-1)^{n-1+2}T_{n-1}(x) \]
\[ T_{n+1}(-x)=(-1)^{n+1}T_{n+1}(x) \]
故得证。 - 关于\(T_n\)的零点:它有n个实零点,表达式为,
\[ x_k=\cos(\frac{2k-1}{2n}\pi),\quad k=1,\cdots,n \]
简证
\[ 0=T_{n}(x)=\cos(n\theta) \]
于是得到, \(n\theta = \frac{(2k-1)\pi}{2}\Rightarrow x=\cos(\frac{2k-1}{2n}\pi)\quad k=1,\cdots,n\) - \(T_{n}(x)\) 在\(\tilde{x}_k,k=0,1,\cdots,n\)上交错取到\(\pm 1\)
\[ \tilde{x}_k=\cos(\frac{2k}{2n}\pi)=\cos(\frac{k}{n}\pi)\quad k=0,1,\cdots,n \]
与上一条的证明一样 - 在\([-1,1]\)上与零函数偏差最小的首1的n次多项式为:!!!!!!!!!!!!!!!!!!!!!!!(及其重要)
\[ \tilde{T}_n(x)=\frac{T_n(x)}{2^{n-1}} \]
其最小偏差为\(\frac{1}{2^{n-1}}\) 证明:(反证法)假设存在一个首1的n次多项式使得,
\[ \max_{-1\leq x\leq1}{|Q(x)|}\leq \frac{1}{2^{n-1}} \]
令\(q(x)=Q(x)-\tilde{T}_n(x)\in P_{n-1}([-1,1])\),在\(\tilde{x}_k\)处取值\(\tilde{T}_{n}(x)\) 在\(\tilde{x}_k,k=0,1,\cdots,n\)上交错取到\(\pm\frac{1}{2^{n-1}}\)
\[ q(\tilde{x}_k )=\begin{cases}\leq 0 ,\quad k \ is\ even \\ \geq 0 ,\quad k \ is \ odd\end{cases}\quad k=0,1,\cdots,n \]
推出\(q(x)\)有n个零点,而\(q\)的次数为\(n-1\),由此推得矛盾. 故最佳的多项式是\(\tilde{T}_n(x)\)
Laguerre 正交多项式系
略 ## Hermit 正交多项式系 略 # 最佳一致逼近 问题: \(f\in C([a,b])\),若\(q\in V\)使得,
\[ ||f(x)-p(x)||_{\infty}=\min_{q\in V}||f(x)-q(x)||_{\infty} \]
如果\(V=P_n\),则\(p(x)\)称为\(f(x)\)的最佳一致逼近多项式.
最佳一致逼近多项式的存在性
下面的定理说明了,多项式的次数不受限制时,可以逼近任意给定的精度. 定理(Weierstress逼近定理): \(\forall \epsilon >0,f\in C([a,b])\),那么一定存在多项式\(p(x)\)使得,
\[ ||f(x)-p(x)||_{\infty}=\max_{a\leq x\leq b}|f(x)-p(x)|\leq \epsilon \]
注意:\(\epsilon\)的大小和多项式p的次数我们不能同时固定住.
下面定理说明的是,n固定时,最佳一致逼近多项式的存在性. 定理: 设\(f\in C([a,b])\),那么存在\(p\in P_n\)使得,
\[ ||f(x)-p(x)||_{\infty}=\min_{p\in P_n}||f(x)-p(x)||_{\infty} \]
证明: 令\(p(x)=\sum_{i=0}^{n}C_i x^i\), 记\(E(C)=||f(x)-\sum_{i=0}^{n}C_i x^i||_{\infty},\quad C\in \mathcal{R}^{n+1}\) 分三步证明: (1) E是连续函数;
\[ |E(\lambda)-E(\mu)|=|\ ||f(x)-\sum_{i=0}^{n}\lambda_i x^i||_{\infty}-||f(x)-\sum_{i=0}^{n}\mu_i x^i||_{\infty} \ | \]
\[ \leq \max_{a\leq x\leq b}|f(x)-\sum_{i=0}^{n}\lambda_i x^i-f(x)+\sum_{i=0}^{n}\mu_i x^i|\leq \max_{a\leq x\leq b}| \sum_{i=0}^{n}(\lambda_i-\mu_i )x^i| \]
\[ \leq\sum_{i=0}^{n}|\lambda_i-\mu_i |\,||x^i||_{\infty}\leq \max_{a\leq x\leq b}| \lambda_i-\mu_i |M \]
其中,
\[ \max_{a\leq x\leq b}(\sum_{i=0}^{n}||x^i||) \]
只要令,
\[ \max_{a\leq x\leq b}| \lambda_i-\mu_i |<\frac{\epsilon}{M} \]
就有,
\[ |E(\lambda)-E(\mu)|<\epsilon \]
故连续性得证.
(2)定义有界闭集
\[ S=\{(c_0,c_1,\cdots,c_n)\in \mathcal{R}^{n+1}|E(c_0,c_1,\cdots,c_n)\leq||f||_{\infty}+1\} \]
又由于,
\[ E(0,0,\cdots,0)=||f||_{\infty}\leq ||f||_{\infty}+1 \]
故S不为空集.因此在S中存在E的极值点.不妨设E在S中的极值小点为\((c_0^*,c_1^*,\cdots,c_n^*)\),极小值为d.由于\((0,0,\cdots,0)\in S\),所以有,
\[ d=E(c_0^*,c_1^*,\cdots,c_n^*)\leq E(0,0,\cdots,0)=||f||_{\infty} \]
(3)另一方面,根据S的定义,我们知道,
\[ E(c_0,c_1,\cdots,c_n)>||f||_{\infty}+1,\forall (c_0,c_1,\cdots,c_n)\in \mathcal{R}^{n+1}-S \]
也就是说,如果\((c_0,c_1,\cdots,c_n)\notin S\)那么就有,
\[ E(c_0,c_1,\cdots,c_n)>d+1>d \]
故,E在S中的极小值也是E在\(\mathcal{R}^{n+1}\)中的极小值.即E在\(\mathcal{R}^{n+1}\)中的极小值点也为\((c_0^*,c_1^*,\cdots,c_n^*)\),因此由\((c_0^*,c_1^*,\cdots,c_n^*)\)确定的多项式
\[ p^*(x)=\sum_{i=0}^{n}c^*_i x^i \]
为\(f\)的最佳一致逼近多项式.
最佳一致逼近多项式的性质
问题导入
例:\(f\in C([a,b])\)单调递增,那么他的零次最佳一次逼近多项式是什么?
\[ P_0=\frac{1}{2}(f(a)+f(b)) \]
如果不单调呢?
\[ P_0=\frac{1}{2}(f_{max}(x)+f_{min}(x)) \]
直觉地,我们可以发现交错最大偏差的绝对值相同,零次的多项式有两个交错偏差,那么一次的多项式有三个交错偏差,以此类推n次多项式有n+2个交错偏差
定理(De la Valle Poussin定理)
定理内容: 设\(f\in C([a,b]),r\in P_n\),又存在\([a,b]\)上的\(n+2\)个点\(x_0<\cdots<x_n\)使得
\[ f(x_i)-r(x_i) \]
与
\[ f(x_{i+1})-r(x_{i+1}) \]
异号,那么有,
\[ \min_{p\in P_n}||f(x)-p(x)||_{\infty}\geq \min_{i\in \{0,1,\cdots,n+1\}}|f(x_i)-r(x_i)|_{\infty} \]
定理内涵:只要我们找到的多项式不是最佳一致逼近多项式,就可以找到一个偏差比最佳一致逼近多项式的偏差要小.
例题: \(r(x)\in P_3\),如果正负交错偏差点小于3+2=5个的时候,我们就可以找到一个更好的修正\(r^*(x)\)使得偏差更小.
Chebyshev定理
定理内容:设\(f\in C([a,b])\),若\(p_n\in P_n\)为\(f\)在\([a,b]\)上的最佳一种逼近多项式.当且仅当 设\(f-p_n\)在\([a,b]\)上至少有\(n+2\)个交错偏差点.
这个定理上课时没有去证.
Chebyshev定理的应用
- 利用Chebyshev定理可以证明最佳一致逼近多项式的唯一性 定理:(唯一性):设\(f\in C([a,b]),r\in P_n\),则存在唯一的\(n\)次最佳一致逼近多项式.
证明: (反证法)假设\(q_n,p_n\)都是\(f\)在\([a,b]\)上的最佳一致逼近多项式,且\(q_n\neq p_n\). 首先,我们有,
\[ E_n(f)=||f-q_n||_{\infty}=||f-p_n||_{\infty} \]
令\(h(x)=\frac{1}{2}(p_n+q_n)\),那么,
\[ \begin{split} 2||f-h||_{\infty}=&||f-p_n+f-q_n||_{\infty}\\\leq &||f-p_n||_{\infty}+||f-q_n||_{\infty}\\=&2E_n(f)\\ \Rightarrow||f-h||_{\infty}&\leq E_n(f) \end{split} \]
由于\(q_n,p_n\)都是\(f\)在\([a,b]\)上的最佳一致逼近多项式,因此只能有,
\[ ||f-h||_{\infty}= E_n(f) \]
即\(h\)也是\(f\)在\([a,b]\)上的最佳一致逼近多项式. 那么由Chebyshev定理,我们知道\(f-h\)至少有\(n+2\)个交错偏差点\(x_i,i=0,\cdots,n+1\),
\[ |f(x_i)-h(x_i)|=E_n(f) \]
等价于
\[ 2|f(x_i)-h(x_i)|=|f(x_i)-p_n(x_i)+f(x_i)-q_n(x_i)|=2E_n(f) \]
- 另一个应用 定理: 设\(f\)在\([a,b]\)上的\(n+1\)阶导数存在,且\(f^{(n+1)}\)在\([a,b]\)上保号.若\(p_n\)为\(f\)在\([a,b]\)上的最佳一致逼近多项式,则\(a,b\)在\(f-p_n\)的交错偏差点组内.
证明: (反证)假设\(a\)或者\(b\)不在\(f-p_n\)的交错偏差点组内. 那么至少有\(n+1\)个交错偏差点在开区间\((a,b)\)内部, 因此误差函数\(e(x)=f(x)-p_n(x)\)在\((a,b)\)内至少有\(n+1\)个驻点,记为\(x_i,i=0,\cdots,n\)即,
\[ e'(x_i)=0,\quad x_i\in(a,b),i=0,\cdots,n \]
应用Rolle定理,则存在\(\xi\in(a,b)\),使得,
\[ 0=e^{(n+1)}(\xi)=f^{(n+1)}(\xi)-p_n^{(n+1)}(\xi)=f^{(n+1)}(\xi) \]
而这与\(f^{(n+1)}\)在\([a,b]\)上保号矛盾.
例题: 设\(f\in C^2([a,b])\),\(f''\)在\([a,b]\)上保号, 求\(p_1(x)=a_1+a_2x\)是\(f\)在\([a,b]\)上的一次最佳一致逼近多项式.
解: 假设交错偏差点\(a,b,c\)
\[ f(a)-p_1(a)=-(f(c)-p_1(c))=f(b)-p_1(b) \]
\[ f'(c)-p_1'(c)=0 \]
三个方程三个未知数.
最佳一致逼近多项式的近似方法
例子
Remez迭代方法求
迭代的方法永远不是精确的!!!!!!!! 计算量很大,解是近似解不是精确解
近似方法 - Lagrange插值法
\[ f(x)-L_n(x)=\frac{f^{(n+1)}}{(n+1)!}\pi_(n+1)(x)=\frac{f^{(n+1)}}{(n+1)!}(x-x_0)\cdots(x-x_n) \]
- Chebyshev级数截断法 假设\(f\in C([a,b])\),\(f\)可在正交多项式系\(T_n(x)\)下展开,
\[ f(x)=\frac{a_0}{2}+\sum_{i=1}^{\infty}a_iT_i(x) \]
\[ a_i=\frac{-2}{\pi}\int_{-1}^{1}\frac{f(x)T_i(x)}{\sqrt{1-x^2}}\,dx \]
\[ f(x)\approx\frac{a_0}{2}+\sum_{i=1}^{n}a_iT_i(x)=P_n(x) \]
当\(n\)足够大时,
\[ a_n\sim \frac{f^{(n)}(0)}{n!2^{n-1}} \]
可以发现\(a_n\)随着\(n\)变大,(大于)指数级下降,那么
\[ f(x)-p_n(x)\approx a_{n+1}T_{n+1}(x) \]
注意到\(T_{n+1}(x)\)有\(n+2\)个交错偏差点.
最佳平方逼近
问题: \(f\in C([a,b])\),若\(q\in V\)使得,
\[ ||f(x)-p(x)||_{2}=\min_{q\in V}||f(x)-q(x)||_{2} \]
如果\(V=P_n\),则\(p(x)\)称为\(f(x)\)的最佳平方逼近多项式.
唯一性
定理: 设\(\varphi_0,\cdots,\varphi_n\in L^2_{\rho}([a,b])\) 则,\(\varphi_0,\cdots,\varphi_n\)线性无关,当且仅当\(det(G_n)\neq 0\) 其中,
\[ \begin{pmatrix} <\varphi _0,\varphi _0> & \cdots & <\varphi _0,\varphi _n>\\ \vdots & \ddots &\vdots \\ <\varphi _n,\varphi _0> & \cdots & <\varphi _n,\varphi _n> \end{pmatrix} \]
高代学过>_<
定理:(唯一性) 设\(f \in L^2_{\rho}([a,b])\),则\(f\)在\(P_n\)中存在唯一的最佳平方逼近多项式\(S^*(x)\).
证明: (1)法方程有唯一
(2)解是最佳平方逼近多项式. 记
\[ s^*(x)=\sum_{i=0}^{n}a_i^*\varphi_i(x) \]
\[ \begin{split} &||f-s||^2_2- ||f-s^*||^2_2\\&=<f,f>-2<f,s>+<s,s>-(<f,f>-2<f,s^*>+<s^*,s^*>)\\ &= \end{split} \]
定理: 若\(P\)为\(f\in L^{2}_{\rho}([a.b])\)在\([a,b]\)上的最佳平方逼近多项式,则
\[ <f-p,q>=0,\quad q\in P_n \]
Hilbert矩阵
例题:
正交多项式在最佳平方逼近的应用
若\(\varphi_i,\quad i=0,1,\cdots,n\)是一组正交多项式,那么
\[ <\varphi_i,\varphi_j>=0,i\neq j \]
法方程,
\[ \begin{pmatrix} <\varphi_0,\varphi_0>&0&\cdots&0\\ 0&<\varphi_1,\varphi_1>&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&<\varphi_n,\varphi_n> \end{pmatrix} \begin{pmatrix} 0\\ 0\\ 0\\ -\\ \end{pmatrix}= \begin{pmatrix} 0\\ 0\\ 0\\ -\\ \end{pmatrix} \]
命题: 若\(f\in L^{2}_{\rho}([a.b])\)且\(\{\varphi_0,\cdots,\varphi_n\}\)是\(L^{2}_{\rho}([a.b])\)中的一组正交多项式,那么,
\[ \sum_{i=0}^{n}\frac{|<f,\varphi_i>|^2}{||\varphi||^2_2}\leq||f||^2_2 \]
证明: 令\(e_i=\frac{\varphi_i}{||\varphi||_2}\),
\[ \begin{split} 0&\leq||f-\sum_{i=0}^{n}<f,e_i>e_i||_2^2\\&=<f,f>-2<f,\sum_{i=0}^{n}<f,e_i>e_i>+<\sum_{i=0}^{n}<f,e_i>e_i,\sum_{i=0}^{n}<f,e_i>e_i>\\ &= \end{split} \]
几何意义 最佳平方逼近多项式是原函数在某个多项式空间中的投影.
最佳一致逼近多项式与最佳平方逼近多项式的比较
(1) 通常情况下,最佳一致逼近多项式\(\neq\)最佳平方逼近多项式
(2)当\(n\)足够大时,最佳一致逼近多项式解决最佳平方逼近多项式.
定理: 设\(n\geq 0,\quad f\in C[a,b]\),又设\(p_n\in P_n\)是\(f\)的最佳平方逼近多项式,则 \(f-p_n\)在\([a,b]\)内至少变化了\(n+1\)次符号.
证明: \(<f-p_n,1>=0\Rightarrow f-p_n\)在\([a,b]\)上不保号,不妨设\(f-p_n\)有\(k\)个零点\(\xi_i,i=1,\cdots,k\)
(3)最佳平方逼近多项式提高次数时只需要增加一项.
\[ \begin{split} &\quad p_{n+1}=p_n+\gamma_{n+1}\varphi_{n+1}\\ &\Rightarrow<f-p_{n+1},\varphi_{n+1}>=0\\ &\Rightarrow<f-p_n-\gamma_{n+1}\varphi_{n+1},\varphi_{n+1}>=0\\ &\Rightarrow<f-p_{n},\varphi_{n+1}>=\gamma_{n+1}<\varphi_{n+1},\varphi_{n+1}>\\ &\Rightarrow \gamma_{n+1}=\frac{<f-p_{n},\varphi_{n+1}>}{<\varphi_{n+1},\varphi_{n+1}>}=\frac{<f,\varphi_{n+1}>}{<\varphi_{n+1},\varphi_{n+1}>} \end{split} \]
最小二乘法
问题引入
数据(采样点) - 有误差 - 数据过多(百万级,插值不划算)
定义:(数据拟合 fitting) 用简单函数\(P(x)\)取逼近数据集,使得误差\(\delta_i=P(x_i)-y_i\)在某种意义下达到最小.
常见误差度量方式: - 无穷范数:\(||\delta||_{\infty}=\max_{0\leq i\leq n}|\delta_i|\) - 1范数:\(||\delta||_{1}=\sum_{i=0}^{n}|\delta_i|\) - 2范数:\(||\delta||_{2}^2=\sum_{i=0}^{n}\delta_i^2\)
最小二乘拟合
内积:
\[ <p,q>=\sum_{i=0}^{n}\rho_ip_iq_i,\qquad p,q\in\mathcal{R}^{n+1} \]
范数:
\[ ||p||_2^2=\sum_{i=0}^{n}\rho_ip_i^2 \]
最小二乘法的目的:
\[ ||p-y||^2_2=||\delta||_2^2=\min_{q\in P_n}||q-y||_2^2 \]
令\(p(x)=\sum_{j=0}^{m}a_j\varphi_j(x),\quad p\in P_m\)
\[ \begin{split} E(a_0,\cdots,a_m)&=||p-y||^2_2\\ &= \end{split} \]
一般情况: 设线性无关函数系\(\varphi_i(x)=x^m,i=0,\cdots,m\),且权系数为\(\rho_i=1\),拟合多项式为,
\[ p(x)=\sum_{j=0}^{m}a_jx^j \]
相应的法方程为:
\[ \left(\begin{array}{cccc} \sum_{i=0}^{n} 1 & \sum_{i=0}^{n} x_{i} & \ldots & \sum_{i=0}^{n} x_{i}^{m} \\ \sum_{i=0}^{n} x_{i} & \sum_{i=0}^{n} x_{i}^{2} & \ldots & \sum_{i=0}^{n} x_{i}^{m+1} \\ \vdots & \vdots & & \vdots \\ \sum_{i=0}^{n} x_{i}^{m} & \sum_{i=0}^{n} x_{i}^{m+1} & \ldots & \sum_{i=0}^{n} x_{i}^{2 m} \end{array}\right)\left(\begin{array}{c} a_{0} \\ a_{1} \\ \vdots \\ a_{m} \end{array}\right)=\left(\begin{array}{c} d_{0} \\ d_{1} \\ \vdots \\ d_{m} \end{array}\right) \]
但是,当\(m\)较大时,上面方程的系数矩阵(法矩阵)是病态的,通过数值软件解得的结果是不可靠的.
正交多项式拟合
为了避免求解病态法方程带来的麻烦,可以通过正交多项式来构造拟合多项式.
设所选择的线性无关函数系具有正交性质,于是法方程可简化为:
\[ \begin{pmatrix} <\varphi_0,\varphi_0>&0&\cdots&0\\ 0&<\varphi_1,\varphi_1>&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&<\varphi_n,\varphi_n> \end{pmatrix} \begin{pmatrix} a_0\\ a_1\\ \vdots\\ a_n\\ \end{pmatrix}= \begin{pmatrix} d_0\\ d_1\\ \vdots\\ d_n\\ \end{pmatrix} \]
！！！！！ ## 例题 (1). 非线性的情况 尽量想办法变成线性
(2). 超定方程 - 高代角度:
\(A^TAX=A^TC\) - 数据拟合角度