- 1. 插值
- 1.1 插值的一些概念
- 1.1.1 插值的定义
- 1.1.2 插值的存在性
- 1.1.3 插值的误差分析
- 1.2 拉格朗日插值(Lagrange Interpolation)
- 1.2.1 拉格朗日插值误差分析
- 1.3 Newton多项式插值
- 1.3.1 Newton多项式插值误差分析
- 1.4 Chebyshev多项式确定插值点
- 1.4.1 Chebyshev多项式性质
- 1.5 有理插值
- 1.5.1 有理插值误差分析
- 1.6 分段插值
- 1.6.1 分段线性插值
- 1.6.2 分段Hermite插值
- 1.6.2.1 Hermite插值误差
- 总结
- 2. 近似
- 2.1 近似的一些概念
- 2.2 帕德近似 (有理近似)
- 3. 拟合
- 3.1 最小二乘拟合
- 3.1.1 线性拟合
- 3.1.2 指数拟合
- 3.1.3 其他形式拟合(线性化思想)
- 3.1.4 一般线性最小二乘法形式
- 3.1.5 非线性最小二乘法
- 3.1.5.1 Levenberg-Marquardt方法
- 3.1.6 多项式拟合
- 3.1.7 拟合的问题
- 3.2 基于优化的拟合
- 3.3 基于概率分布的模型
- 3.4 非线性曲线拟合
- 3.4.1 逻辑回归
- 3.5 三角拟合
- 3.5.1 三角拟合的正交性质
- 3.6 分段三次样条曲线拟合
- 3.7 Bezier曲线拟合
- 3.8 Matlab函数
多项式方程如f(x)=1+x;f(x)=x2+x4f(x)=1+x ; \quad f(x)=x^{2}+x^{4}f(x)=1+x;f(x)=x2+x4
非多项式方程如f(x)=exf(x)=sin(x)ln(x)f(x)=e^{x} \quad f(x)=\sin (x) \ln (x)f(x)=exf(x)=sin(x)ln(x)
多项式方程对于计算机好计算,非多项式方程则不然,可以用多项式方程来计算非多项式方程吗?怎么用一个多项式方程来表示一个非多项式方程,是我们要解决的问题。
1. 插值
1.1 插值的一些概念
1.1.1 插值的定义
插值:给定一组点(x1,y1),(x2,y2),...,(xn,yn)(x_1,y_1),(x_2,y_2),...,(x_n,y_n)(x1,y1),(x2,y2),...,(xn,yn),构造一个函数y=f(x)y=f(x)y=f(x),满足yi=f(xi),i=1,2,...,ny_i=f(x_i),i=1,2,...,nyi=f(xi),i=1,2,...,n
例子:
1.1.2 插值的存在性
设多项式方程为:
Pn(x)=a0+a1x+a2x2+……+anxnPn(xi)=yi,i=0,1,2,…,n,xi≠xjP_{n}(x)=a_{0}+a_{1} x+a_{2} x^{2}+\ldots \ldots+a_{n} x^{\mathrm{n}}\\ P_{n}\left(x_{i}\right)=y_{i}, \quad \mathrm{i}=0,1,2, \ldots, \mathrm{n}, x_{i} \neq x_{\mathrm{j}}Pn(x)=a0+a1x+a2x2+……+anxnPn(xi)=yi,i=0,1,2,…,n,xi=xj
有:
[1x0x02⋯x0n1x1x12⋯x1n1x2x22⋯x2n⋯⋯⋯⋯⋯1xnxn2⋯xnn][a0a1a2⋮an]=[y0y1y2⋮yn]\begin{bmatrix} 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\\ \cdots & \cdots & \cdots & \cdots &\cdots \\ 1 & x_{n} & x_{n}^{2} &\cdots &x_n^n \end{bmatrix}\begin{bmatrix} a_{0} \\ a_{1} \\ a_{2}\\ \vdots\\ a_n \end{bmatrix}=\begin{bmatrix} y_{0} \\ y_{1} \\ y_{2}\\ \vdots\\ y_n \end{bmatrix}111⋯1x0x1x2⋯xnx02x12x22⋯xn2⋯⋯⋯⋯⋯x0nx1nx2n⋯xnna0a1a2⋮an=y0y1y2⋮yn
也即Aa=y\mathbf{Aa}=\mathbf{y}Aa=y的形式。
要求A\mathbf{A}A行列式不等于0,根据vandermonde行列式,我们知道行列式:
∣1x0x02⋯x0n1x1x12⋯x1n1x2x22⋯x2n⋯⋯⋯⋯⋯1xnxn2⋯xnn∣=∏n≥i>j≥0(xi−xj)\left|\begin{array}{ccccc} 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\\ \cdots & \cdots & \cdots & \cdots &\cdots \\ 1 & x_{n} & x_{n}^{2} &\cdots &x_n^n \end{array}\right|=\prod_{n \geq i>j \geq 0}\left(x_{i}-x_{j}\right)111⋯1x0x1x2⋯xnx02x12x22⋯xn2⋯⋯⋯⋯⋯x0nx1nx2n⋯xnn=n≥i>j≥0∏(xi−xj)
1.1.3 插值的误差分析
一般来说,如果点(xi,yi)(x_i,y_i)(xi,yi)是任意选择的,我们无法进行误差分析。
但如果这些点是按顺序从一个已知的函数f(x)f(x)f(x)中抽取的,这意味着(xi,y)=(xi,f(xi))(x_i,y)=(x_i,f(x_i))(xi,y)=(xi,f(xi)),误差R(x)=∣f(x)−Pn(x)∣R(x)=|f(x)-P_n(x)|R(x)=∣f(x)−Pn(x)∣可以被预测到。
1.2 拉格朗日插值(Lagrange Interpolation)
给定一组点(x1,y1),(x2,y2),...,(xN,yN)(x_1,y_1),(x_2,y_2),...,(x_N,y_N)(x1,y1),(x2,y2),...,(xN,yN)
y=PN(x)=y0LN,0(x)+y1LN,1(x)+…+yNLN,N(x)=∑k=0NykLN,k(x)\begin{array}{l} y=P_{N}(x)=y_{0} L_{N, 0}(x)+y_{1} L_{N, 1}(x)+\ldots+y_{N} L_{N, N}(x) \\ =\sum_{k=0}^{N} y_{k} L_{N, k}(x) \end{array}y=PN(x)=y0LN,0(x)+y1LN,1(x)+…+yNLN,N(x)=∑k=0NykLN,k(x)
LN,k(x)=(x−x0)…(x−xk−1)(x−xk+1)…(x−xN)(xk−x0)…(xk−xk−1)(xk−xk+1)…(xk−xN)=∏j=0j≠kN(x−xj)∏j=0j≠kN(xk−xj)LN,k(x0)=0,…,LN,k(x1)=0,LN,k(xk)=1,LN,k(xk+1)=0,…,LN,k(xN)=0\begin{aligned} &L_{N, k}(x) = \frac{\left(x-x_{0}\right) \ldots\left(x-x_{k-1}\right)\left(x-x_{k+1}\right) \ldots\left(x-x_{N}\right)}{\left(x_{k}-x_{0}\right) \ldots\left(x_{k}-x_{k-1}\right)\left(x_{k}-x_{k+1}\right) \ldots\left(x_{k}-x_{N}\right)} = \frac{\prod_{\substack{j = 0 j \neq k}}^{N}\left(x-x_{j}\right)}{\prod_{\substack{j = 0 j \neq k}}^{N}\left(x_{k}-x_{j}\right)} \\ &L_{N, k}\left(x_{0}\right) = 0, \ldots, L_{N, k}\left(x_{1}\right) = 0, L_{N, k}\left(x_{k}\right) = 1, L_{N, k}\left(x_{k+1}\right) = 0, \ldots, L_{N, k}\left(x_{N}\right) = 0 \end{aligned}LN,k(x)=(xk−x0)…(xk−xk−1)(xk−xk+1)…(xk−xN)(x−x0)…(x−xk−1)(x−xk+1)…(x−xN)=∏j=0j=kN(xk−xj)∏j=0j=kN(x−xj)LN,k(x0)=0,…,LN,k(x1)=0,LN,k(xk)=1,LN,k(xk+1)=0,…,LN,k(xN)=0
1.2.1 拉格朗日插值误差分析
定理:假设f(x)f(x)f(x)在[a,b][a,b][a,b]上是(n+1)(n +1)(n+1)阶可微,Ln(x)L_n(x)Ln(x)是拉格朗日函数,那么误差估计如下
Rn(x)=f(x)−Pn(x)=f(n+1)(ξ)(n+1)!∏k=0n(x−xk),ξ∈[x0,xn]R_{n}(x)=f(x)-P_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !} \prod_{k=0}^{n}\left(x-x_{k}\right), \quad \xi \in\left[x_{0}, x_{n}\right]Rn(x)=f(x)−Pn(x)=(n+1)!f(n+1)(ξ)k=0∏n(x−xk),ξ∈[x0,xn]
证明:
设w(x)=∏k=0n(x−xk)令R(t)=f(t)−f(x)−Pn(x)w(x)w(t)−Pn(t)有R(xi)=f(xi)−f(x)−Pn(x)w(x)w(xi)−Pn(xi)=0R(x)=f(x)−f(x)−Pn(x)w(x)w(x)−Pn(x)=0\begin{aligned} 设&w(x) = \prod_{k = 0}^{n}\left(x-x_{k}\right) \\ 令&R(t) = f(t)-\frac{f(x)-P_{n}(x)}{w(x)} w(t)-P_{n}(t) \\ 有&R\left(x_{i}\right) = f\left(x_{i}\right)-\frac{f(x)-P_{n}(x)}{w(x)} w\left(x_{i}\right)-P_{n}\left(x_{i}\right) = 0 \\ &R(x) = f(x)-\frac{f(x)-P_{n}(x)}{w(x)} w(x)-P_{n}(x) = 0 \end{aligned}设令有w(x)=k=0∏n(x−xk)R(t)=f(t)−w(x)f(x)−Pn(x)w(t)−Pn(t)R(xi)=f(xi)−w(x)f(x)−Pn(x)w(xi)−Pn(xi)=0R(x)=f(x)−w(x)f(x)−Pn(x)w(x)−Pn(x)=0于是R(t)R(t)R(t)有n+2n+2n+2个根:x0,x1,⋯,xn,xx_0,x_1,\cdots,x_n,xx0,x1,⋯,xn,x,使用罗尔定理,RRR的n+1n+1n+1阶导数R(n+1)(x)R^{(n+1)}(x)R(n+1)(x)至少有一个根,使得R(n+1)(ξ)=0ξ∈[x0,xn]R^{(n+1)}(\xi)=0\quad \xi\in[x_0,x_n]R(n+1)(ξ)=0ξ∈[x0,xn],于是:
R(n+1)(t)=f(n+1)(t)−f(x)−Pn(x)w(x)w(n+1)(t)−Pn(n+1)(t)=f(n+1)(t)−f(x)−Pn(x)w(x)(n+1)!R(n+1)(ξ)=f(n+1)(ξ)−f(x)−Pn(x)w(x)(n+1)!=0f(x)−Pn(x)=f(n+1)(ξ)w(x)/(n+1)!\begin{aligned} &R^{(n+1)}(t) = f^{(n+1)}(t)-\frac{f(x)-P_{n}(x)}{w(x)} w^{(n+1)}(t)-P_{n}^{(n+1)}(t) \\ &= f^{(n+1)}(t)-\frac{f(x)-P_{n}(x)}{w(x)}(n+1) ! \\ &R^{(n+1)}(\xi) = f^{(n+1)}(\xi)-\frac{f(x)-P_{n}(x)}{w(x)}(n+1) ! = 0 \\ &f(x)-P_{n}(x) = f^{(n+1)}(\xi) w(x) /(n+1) ! \end{aligned}R(n+1)(t)=f(n+1)(t)−w(x)f(x)−Pn(x)w(n+1)(t)−Pn(n+1)(t)=f(n+1)(t)−w(x)f(x)−Pn(x)(n+1)!R(n+1)(ξ)=f(n+1)(ξ)−w(x)f(x)−Pn(x)(n+1)!=0f(x)−Pn(x)=f(n+1)(ξ)w(x)/(n+1)!
可以导出的其他性质:
w(x)=∏k=0n(x−xk)w′(x)=(x−x1)(x−x2)…(x−xn)+(x−x0)(x−x2)…+…Ln,k(x)=(x−x0)…(x−xk−1)(x−xk+1)…(x−xn)/w′(xk)\begin{aligned} &w(x) = \prod_{k = 0}^{n}\left(x-x_{k}\right) \\ &w^{\prime}(x) = \left(x-x_{1}\right)\left(x-x_{2}\right) \ldots\left(x-x_{n}\right)+\left(x-x_{0}\right)\left(x-x_{2}\right) \ldots+\ldots \\ &L_{n, k}(x) = \left(x-x_{0}\right) \ldots\left(x-x_{k-1}\right)\left(x-x_{k+1}\right) \ldots\left(x-x_{n}\right) / w^{\prime}\left(x_{k}\right) \end{aligned}w(x)=k=0∏n(x−xk)w′(x)=(x−x1)(x−x2)…(x−xn)+(x−x0)(x−x2)…+…Ln,k(x)=(x−x0)…(x−xk−1)(x−xk+1)…(x−xn)/w′(xk)
于是有:
∑k=0nLn,k(x)=∑k=0n(x−x0)…(x−xk−1)(x−xk+1)…(x−xn)/w′(xk)≡1\sum_{k=0}^{n} L_{n, k}(x)=\sum_{k=0}^{n}\left(x-x_{0}\right) \ldots\left(x-x_{k-1}\right)\left(x-x_{k+1}\right) \ldots\left(x-x_{n}\right) / w^{\prime}\left(x_{k}\right) \equiv 1k=0∑nLn,k(x)=k=0∑n(x−x0)…(x−xk−1)(x−xk+1)…(x−xn)/w′(xk)≡1
证明: 令f(x)=1,给定一系列点(xi,1), i.e. yi=1,Pn(x)=∑i=0nLn,i(x),R(x)≡0\text { 令} f(x)=1,给定一系列点\left(x_{\mathrm{i}}, 1\right) \text {, i.e. } y_{\mathrm{i}}=1, \quad P_{n}(x)=\sum_{i=0}^{n} L_{n, i}(x), R(x) \equiv 0 令f(x)=1,给定一系列点(xi,1), i.e. yi=1,Pn(x)=i=0∑nLn,i(x),R(x)≡0
如何预测误差的边界
分别找到fn+1f^{n+1}fn+1和w(x)w(x)w(x)的上界有:
∣f(n+1)(x)∣<Mn∣w(x)∣=∣∏k=0n(x−xk)∣<Wn\begin{aligned} &\left|{f}^{({n}+1)}({x})\right|<{M}_{{n}}\\ &|w({x})|=\left|\prod_{k=0}^{n}\left(x-x_{k}\right) \right|<W_{\mathrm{n}}\end{aligned} f(n+1)(x)<Mn∣w(x)∣=k=0∏n(x−xk)<Wn
于是有:
∣Rn(x)∣=∣f(n+1)(ξ)(n+1)!∏k=0n(x−xk)∣<MnWn(n+1)!\left|R_{n}(x)\right|=\left|\frac{f^{(n+1)}(\xi)}{(n+1) !} \prod_{k=0}^{n}\left(x-x_{k}\right)\right|<\frac{M_{n} W_{n}}{(n+1) !}∣Rn(x)∣=(n+1)!f(n+1)(ξ)k=0∏n(x−xk)<(n+1)!MnWn
如果xk=x0+kh,x_{k}=x_{0}+k h, \quadxk=x0+kh, 则W1=h24,W2=2h333,W3=h4W_{1}=\frac{h^{2}}{4}, W_{2}=\frac{2 h^{3}}{3 \sqrt{3}}, W_{3}=h^{4}W1=4h2,W2=332h3,W3=h4
1.3 Newton多项式插值
给定一组点(x1,y1),(x2,y2),...,(xN,yN)(x_1,y_1),(x_2,y_2),...,(x_N,y_N)(x1,y1),(x2,y2),...,(xN,yN)
我们观察这样一个递推序列:
PN(x)=PN−1(x)+aN(x−x0)(x−x1)…(x−xN−1)P_{N}(x)=P_{N-1}(x)+a_{N}\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{N-1}\right)PN(x)=PN−1(x)+aN(x−x0)(x−x1)…(x−xN−1)
怎么求其中的系数呢?例子:给两个点和三个点的插值如下:
我们把三点的插值的a2a_2a2计算一下,可以发现Newton的系数和微分很像!
于是我们可以给出多个点的递推公式:
PN(x)=a0+a1(x−x0)+a1(x−x0)(x−x1)+a1(x−x0)(x−x1)(x−x2)+…+aN(x−x0)(x−x1)…(x−xN−1)ak=f[x0,x1,…,xk]\begin{array}{l} P_{N}(x)=a_{0}+a_{1}\left(x-x_{0}\right)+a_{1}\left(x-x_{0}\right)\left(x-x_{1}\right)+a_{1}\left(x-x_{0}\right)\left(x-x_{1}\right)\left(x-x_{2}\right)+ \\ \quad \ldots+a_{N}\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{N-1}\right) \\ a_{k}=f\left[x_{0}, x_{1}, \ldots, x_{k}\right] \end{array}PN(x)=a0+a1(x−x0)+a1(x−x0)(x−x1)+a1(x−x0)(x−x1)(x−x2)+…+aN(x−x0)(x−x1)…(x−xN−1)ak=f[x0,x1,…,xk]
其中
可以验算一下P2P_2P2
差分计算和微分也很相似,二次经过差分变一次。P(x)P(x)P(x)是nnn次多项式,P′(x)P'(x)P′(x)是n−1n-1n−1次多项式。
性质:如果f(x)f(x)f(x)是nnn次多项式,那么f[x,x0,x1,⋯,xn]=0f[x,x_0,x_1,\cdots,x_n]=0f[x,x0,x1,⋯,xn]=0
1.3.1 Newton多项式插值误差分析
如果f(x)f(x)f(x)是nnn次多项式,误差为:
Rn(x)=f(x)−Pn(x)=f[x,x0,…,xn](x−x0)(x−x1)…(x−xn)R_{n}(x)=f(x)-P_{n}(x)=f\left[x, x_{0}, \ldots, x_{n}\right]\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{n}\right)Rn(x)=f(x)−Pn(x)=f[x,x0,…,xn](x−x0)(x−x1)…(x−xn)
对于拉格朗日插值我们又知道:
Rn(x)=f(n+1)(ξ)(n+1)!(x−x0)(x−x1)…(x−xn)R_{n}(x)=\frac{f^{(n+1)}(\xi)}{(n+1) !}\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{n}\right)Rn(x)=(n+1)!f(n+1)(ξ)(x−x0)(x−x1)…(x−xn)
于是有:
f[x,x0,…,xn]=f(n+1)(ξ)(n+1)!f\left[x, x_{0}, \ldots, x_{n}\right]=\frac{f^{(n+1)}(\xi)}{(n+1) !}f[x,x0,…,xn]=(n+1)!f(n+1)(ξ)
当nnn的0,就变成中值定理。
于是我们知道拉格朗日插值和Newton插值可以互换。只是形式不同。
1.4 Chebyshev多项式确定插值点
根据前面的拉格朗日插值我们知道
我们怎么选择最佳的(x0,x1,…,xN)\left({\left.x_{0}, x_{1}, \ldots, x_{N}\right)}\right.(x0,x1,…,xN)以最小化∣R(x)∣|R(x)|∣R(x)∣呢?
答案是,使用Chebyshev多项式的根。
Chebyshev多项式一般表达式:
注意Tn(x)T_n(x)Tn(x)最高次项的系数是2n−12^{n-1}2n−1, 对于TnT_nTn有nnn个零点。
1.4.1 Chebyshev多项式性质
定理:
max−1≤x≤1∣Tn(x)2n−1∣≤max−1≤x≤1∣w(x)∣max−1≤x≤1∣Tn(x)2n−1∣=12n−1\begin{aligned} &\max _{-1 \leq x \leq 1}\left|\frac{T_{n}(x)}{2^{n-1}}\right| \leq \max _{-1 \leq x \leq 1}|w(x)| \\ &\max _{-1 \leq x \leq 1}\left|\frac{T_{n}(x)}{2^{n-1}}\right|=\frac{1}{2^{n-1}} \end{aligned}−1≤x≤1max2n−1Tn(x)≤−1≤x≤1max∣w(x)∣−1≤x≤1max2n−1Tn(x)=2n−11
使用反证法证明:
假设max−1≤x≤1∣Tn(x)2n−1∣>max−1≤x≤1∣w(x)∣\max _{-1 \leq x \leq 1}\left|\frac{T_{n}(x)}{2^{n-1}}\right| > \max _{-1 \leq x \leq 1}|w(x)|−1≤x≤1max2n−1Tn(x)>−1≤x≤1max∣w(x)∣
具体证明如下:
对于至少n−1n-1n−1次多项式(给定了n+1n+1n+1个点),w(x)−Tn(x)2n−1w(x)-\frac{T_n{(x)}}{2^{n-1}}w(x)−2n−1Tn(x)有nnn个根,矛盾。
这是书里摘出的证明
Tn(x)T_n(x)Tn(x)最高次项的系数是2n−12^{n-1}2n−1的证明。
正交性质
注意xkx_kxk 是Tn+1(x)=0T_{n+1}(x)=0Tn+1(x)=0, 不是Tn(x)=0T_n(x)=0Tn(x)=0的根.
证明:
以下几个图的f(xk)f(x_k)f(xk)和Pn(xk)P_n(x_k)Pn(xk)是一个意思
1.5 有理插值
其中
例子:
1.5.1 有理插值误差分析
E(x)=f(x)−P(x)Q(x)=(x−x0)…(x−xm+n)(m+n+1)!Q2(x)[f(x)Q2(x)]x=ξ(m+n+1)E(x)=f(x)-\frac{P(x)}{Q(x)}=\frac{\left(x-x_{0}\right) \ldots\left(x-x_{m+n}\right)}{(m+n+1) ! Q^{2}(x)}\left[f(x) Q^{2}(x)\right]_{x=\xi}^{(m+n+1)}E(x)=f(x)−Q(x)P(x)=(m+n+1)!Q2(x)(x−x0)…(x−xm+n)[f(x)Q2(x)]x=ξ(m+n+1)
例子:
1.6 分段插值
单段拟合会出现Runge现象
1.6.1 分段线性插值
上图的h=x1−x0h=x_1-x_0h=x1−x0
1.6.2 分段Hermite插值
保证拟合曲线导数的光滑性。
归一化 Hermite Problem 形式
1.6.2.1 Hermite插值误差
对于H3H_3H3
Hermite赫米特多项式误差介于泰勒级数和拉格朗日之间
总结
拉格朗日插值和Newton插值形式不同,但是结果是一样的。可以互相转换。把拉格朗日插值和Newton插值和泰勒展式比较一下:
2. 近似
2.1 近似的一些概念
给出一个一般函数y=f(x)y=f(x)y=f(x),求一个多项式函数y=P(x)y=P(x)y=P(x),满足∣f(x)−P(x)∣<ε(x)|f(x)-P(x)|<\varepsilon(x)∣f(x)−P(x)∣<ε(x)
例子:
2.2 帕德近似 (有理近似)
Rn,m(x)=Pn(x)Qm(x)Pn(x)=p0+p1x+p2x2+…+pnxnQm(x)=1+q1x+q2x2+…+qmxm\begin{aligned} &R_{n, m}(x) = \frac{P_{n}(x)}{Q_{m}(x)} \\ &P_{n}(x) = p_{0}+p_{1} x+p_{2} x^{2}+\ldots+p_{n} x^{n} \\ &Q_{m}(x) = 1+q_{1} x+q_{2} x^{2}+\ldots+q_{m} x^{m} \end{aligned}Rn,m(x)=Qm(x)Pn(x)Pn(x)=p0+p1x+p2x2+…+pnxnQm(x)=1+q1x+q2x2+…+qmxm
共有n+mn+mn+m个未知数。
给定n+mn+mn+m的大小,当n=mn=mn=m或n=m+1n=m+1n=m+1近似误差最小。
例子:
连续形式:
3. 拟合
拟合:问题:给定一个曲线类型和一组点,在该类型的曲线中找出一条与这些点距离最小的曲线。
问题:如何评估误差?
有以下几种形式
3.1 最小二乘拟合
3.1.1 线性拟合
拟合类型:
y=f(x)=Ax+By=f(x)={A} x+{B}y=f(x)=Ax+B
给定点:
(xi,yi),i=1,2,…,n\left(x_{\mathrm{i}}, y_{\mathrm{i}}\right), i=1,2, \ldots, n(xi,yi),i=1,2,…,n
使用最小二乘法
d(A,B)=∑i=1n[f(xi)−yi]2=∑i=1n[Axi+B−yi]2=∑i=1n[A2xi2+B2+yi2+2ABxi−2Axiyi−2Byi]=(∑i=1nxi2)A2+nB2+(2∑i=1nxi)AB−2(∑i=1nxiyi)A−2(∑i=1nyi)B+(∑i=1nyi2)\begin{aligned} d(A, B) &= \sum_{i = 1}^{n}\left[f\left(x_{i}\right)-y_{i}\right]^{2} = \sum_{i = 1}^{n}\left[A x_{i}+B-y_{i}\right]^{2} \\ &= \sum_{i = 1}^{n}\left[A^{2} x_{i}^{2}+B^{2}+y_{i}^{2}+2 A B x_{i}-2 A x_{i} y_{i}-2 B y_{i}\right] \\ & = \left(\sum_{i = 1}^{n} x_{i}^{2}\right) A^{2}+n B^{2}+\left(2 \sum_{i = 1}^{n} x_{i}\right) A B-2\left(\sum_{i = 1}^{n} x_{i} y_{i}\right) A-2\left(\sum_{i = 1}^{n} y_{i}\right) B+\left(\sum_{i = 1}^{n} y_{i}^{2}\right) \end{aligned}d(A,B)=i=1∑n[f(xi)−yi]2=i=1∑n[Axi+B−yi]2=i=1∑n[A2xi2+B2+yi2+2ABxi−2Axiyi−2Byi]=(i=1∑nxi2)A2+nB2+(2i=1∑nxi)AB−2(i=1∑nxiyi)A−2(i=1∑nyi)B+(i=1∑nyi2)
∂d(A,B)∂A=2(∑i=1nxi2)A+2(∑i=1nxi)B−2∑i=1nxiyi=0∂d(A,B)∂B=2nB+2(∑i=1nxi)A−2∑i=1nyi=0\begin{aligned} \frac{\partial d(A, B)}{\partial A} &= 2\left(\sum_{i = 1}^{n} x_{i}^{2}\right) A+2\left(\sum_{i = 1}^{n} x_{i}\right) B-2 \sum_{i = 1}^{n} x_{i} y_{i} = 0 \\ \frac{\partial d(A, B)}{\partial B} &= 2 n B+2\left(\sum_{i = 1}^{n} x_{i}\right) A-2 \sum_{i = 1}^{n} y_{i} = 0 \end{aligned}∂A∂d(A,B)∂B∂d(A,B)=2(i=1∑nxi2)A+2(i=1∑nxi)B−2i=1∑nxiyi=0=2nB+2(i=1∑nxi)A−2i=1∑nyi=0
求解上面的线性方程组可以得到AAA和BBB。
3.1.2 指数拟合
拟合类型
y=f(x)=AxMy=f(x)=A x^{M}y=f(x)=AxM其中MMM是已知的。
给定点:
(xi,yi),i=1,2,…,n\left(x_{\mathrm{i}}, y_{\mathrm{i}}\right), i=1,2, \ldots, n(xi,yi),i=1,2,…,n
应用最小二乘法:
E(A)=∑i=1n(AxiM−yi)2→minE′(A)=2∑i=1n[(AxiM−yi)xiM]=2∑i=1n(Axi2M−xiMyi)=2(∑i=1nxi2M)A−2∑i=1nxiMyi=0A=∑i=1nxiMyi∑i=1nxi2M\begin{aligned} &E(A) = \sum_{i = 1}^{n}\left(A x_{i}^{M}-y_{i}\right)^{2} \rightarrow \min \\ &E^{\prime}(A) = 2 \sum_{i = 1}^{n}\left[\left(A x_{i}^{M}-y_{i}\right) x_{i}^{M}\right] = 2 \sum_{i = 1}^{n}\left(A x_{i}^{2 M}-x_{i}^{M} y_{i}\right) \\ & = 2\left(\sum_{i = 1}^{n} x_{i}^{2 M}\right) A-2 \sum_{i = 1}^{n} x_{i}^{M} y_{i} = 0 \\ &A = \frac{\sum_{i = 1}^{n} x_{i}^{M} y_{i}}{\sum_{i = 1}^{n} x_{i}^{2 M}} \end{aligned}E(A)=i=1∑n(AxiM−yi)2→minE′(A)=2i=1∑n[(AxiM−yi)xiM]=2i=1∑n(Axi2M−xiMyi)=2(i=1∑nxi2M)A−2i=1∑nxiMyi=0A=∑i=1nxi2M∑i=1nxiMyi
另一种形式的指数拟合:
拟合形式:
y=CeAxy=C e^{A x}y=CeAx
给定点:
(xi,yi),i=1,2,…,n\left(x_{\mathrm{i}}, y_{\mathrm{i}}\right), i=1,2, \ldots, n(xi,yi),i=1,2,…,n
应用最小二乘法:
E(A,C)=∑i=1n(CeAxi−yi)2→min∂E∂A=2∑i=1n[(CeAxi−yi)CeAxixi]=2∑i=1n(C2e2Axixi−CeAxixiyi)=0∂E∂C=2∑i=1n[(CeAxi−yi)eAxi]=2∑i=1n(Ce2Axi−eAxiyi)=0\begin{aligned} &E(A, C) = \sum_{i = 1}^{n}\left(C e^{A x_{i}}-y_{i}\right)^{2} \rightarrow \min \\ &\frac{\partial E}{\partial A} = 2 \sum_{i = 1}^{n}\left[\left(C e^{A x_{i}}-y_{i}\right) C e^{A x_{i}} x_{i}\right] = 2 \sum_{i = 1}^{n}\left(C^{2} e^{2 A x_{i}} x_{i}-C e^{A x_{i}} x_{i} y_{i}\right) = 0 \\ &\frac{\partial E}{\partial C} = 2 \sum_{i = 1}^{n}\left[\left(C e^{A x_{i}}-y_{i}\right) e^{A x_{i}}\right] = 2 \sum_{i = 1}^{n}\left(C e^{2 A x_{i}}-e^{A x_{i}} y_{i}\right) = 0 \end{aligned}E(A,C)=i=1∑n(CeAxi−yi)2→min∂A∂E=2i=1∑n[(CeAxi−yi)CeAxixi]=2i=1∑n(C2e2Axixi−CeAxixiyi)=0∂C∂E=2i=1∑n[(CeAxi−yi)eAxi]=2i=1∑n(Ce2Axi−eAxiyi)=0
这是非线性方程不好解得AAA和CCC。求解有两个思路:一是使用优化的方法比如单纯形法,二是使用Newton法迭代,另外可以考虑线性化:
y=CeAxln(y)=Ax+ln(C)Y=AX+B\begin{aligned} & y = C e^{A x} \\ &\ln (y) = A x+\ln (C) \\ &Y = A X+B \end{aligned}y=CeAxln(y)=Ax+ln(C)Y=AX+B
其中
Y=ln(y),X=x,B=ln(C)Y=\ln (y), X=x, B=\ln (C)Y=ln(y),X=x,B=ln(C)
3.1.3 其他形式拟合(线性化思想)
3.1.4 一般线性最小二乘法形式
3.1.5 非线性最小二乘法
在一般最小二乘的基础上添加权重。
由此导出:Levenberg-Marquardt方法
3.1.5.1 Levenberg-Marquardt方法
回顾我们的残差函数
下面推导Gradient descent Method和Gauss-Newton Method下得到的优化方法需要的步长hhh。
Gauss-Newton方法推导步长。
各种方法下的步长对比:
(ρ(h)的表达式\rho(h)的表达式ρ(h)的表达式的推导的第二行是把上面的hlmh_{lm}hlm带进去消掉rrr)
先看下面红色框框的了解迭代的思路:
巧妙得到JJJ的递推式。
(这一页没有讲清楚)
3.1.6 多项式拟合
按照3.1.4. 多项式拟合取
y=f(x)=anxn+an−1xn−1+…+a1x+a0y=f(x)=a_{{n}} x^{{n}}+a_{{n}-1} x^{{n}-1}+\ldots+a_{1} x+a_{0}y=f(x)=anxn+an−1xn−1+…+a1x+a0
转化为解线性方程组求解aja_jaj
3.1.7 拟合的问题
欠拟合和过拟合
多项式摆动
3.2 基于优化的拟合
逻辑回归基于优化的方法(查看本文的3.4.1逻辑回归):
3.3 基于概率分布的模型
3.4 非线性曲线拟合
3.4.1 逻辑回归
优化方法逻辑回归参考3.2 基于优化的方法
3.5 三角拟合
有周期性的数据,可以用三角拟合。
当数据的周期不等于2π2\pi2π,进行延拓。
{xˉi=2πxi/Pyˉi=yi,i=0,1,2,…,n\left\{\begin{array}{c} \bar{x}_{i}=2 \pi x_{i} / P \\ \bar{y}_{i}=y_{i} \end{array}, i=0,1,2, \ldots, n\right.{xˉi=2πxi/Pyˉi=yi,i=0,1,2,…,n
对于拟合确保n>2mn>2mn>2m
三角拟合其实是使用了傅里叶级数,下面展示了连续傅里叶级数和离散的傅里叶级数。
3.5.1 三角拟合的正交性质
我们规定xkx_kxk是[−π,π][-\pi,\pi][−π,π]之中均匀取点,第一个点是−π-\pi−π,最后一个点是π\piπ,xk=−π+2kπn,k=1,⋯,nx_k=-\pi+\frac{2k\pi}{n},k=1,\cdots,nxk=−π+n2kπ,k=1,⋯,n
最小二乘法求系数。
偶函数和基函数下可以简化
3.6 分段三次样条曲线拟合
过点、0阶、1阶、2阶连续,四个条件约束的三次曲线。
和Hermite插值比较:
例子:
3.7 Bezier曲线拟合
3.8 Matlab函数