手机移动端网站怎么做的,Wordpress创建数据库的文件,免费企业邮箱登录入口,住建局证件查询系统移动最小二乘法#xff08;Moving Least Square#xff0c;MLS#xff09;主要应用于曲线与曲面拟合#xff0c;该方法基于紧支撑加权函数#xff08;即函数值只在有限大小的封闭域中定义大于零#xff0c;而在域外则定义为零#xff09;和多项式基函数#xff0c;通过…移动最小二乘法Moving Least SquareMLS主要应用于曲线与曲面拟合该方法基于紧支撑加权函数即函数值只在有限大小的封闭域中定义大于零而在域外则定义为零和多项式基函数通过加权最小二乘法建立适合散点Scattered points模型的拟合函数。其主要特点是
不需对拟合和插值区域进行划分只需散点模型由于 MLS 引入了紧支撑权函数因此具有局部拟合或插值特点。改变基函数的多项式次数可以方便地控制曲线曲面拟合或插值精度改变权函数可以改变曲线曲面的光滑度。
一、移动最小二乘法原理
曲线与曲面拟合是寻找一个相对简单的函数来逼近一个数据集的过程。通过按距离加权的方法计算近似函数值和给定数据值的差的平方和来度量拟合的性能这就是加权最小二乘法的基本思想。移动最小二乘法的提出是对传统加权最小二乘方法更一般性的推广。并特别强调加权函数的紧支撑性因此具有局部数值分析的特点。
在拟合区域的一个局部子域上假设需要拟合的函数 F ( x ) F(x) F(x) 的近似函数 F ^ ( x ) \hat{F}(x) F^(x)可表达为 F ^ ( x ) ∑ j 1 m b j ( x ) a j ( x ) b T ( x ) a T ( x ) (1) \hat{F}(x)\sum_{j1}^mb_j(x)a_j(x)\pmb{b^T(x)a^T(x)}\tag{1} F^(x)j1∑mbj(x)aj(x)bT(x)aT(x)(1)
这里 m m m 是基函数的项数 b j ( x ) b_j(x) bj(x) 是基函数 a j ( x ) a_j(x) aj(x) 是其系数。假定基函数 b j ( x ) b_j(x) bj(x) 是多项式则具有如下形式
一次多项式线性基 { b T ( 1 , x ) 1 D b T ( 1 , x , y ) 2 D \begin{cases} \pmb{b^T}(1,x)\quad 1D\\[2ex] \pmb{b^T}(1,x,y)2D \end{cases} ⎩ ⎨ ⎧bT(1,x)bT(1,x,y)1D2D
二次多项式二次基 { b T ( 1 , x , x 2 ) 1 D b T ( 1 , x , y , x 2 , x y , y 2 ) 2 D \begin{cases} \pmb{b^T}(1,x,x^2)\quad 1D\\[2ex] \pmb{b^T}(1,x,y,x^2,xy,y^2)2D \end{cases} ⎩ ⎨ ⎧bT(1,x,x2)bT(1,x,y,x2,xy,y2)1D2D
立方基 { b T ( 1 , x , x 2 , x 3 ) 1 D b T ( 1 , x , y , x 2 , x y , y 2 , x 3 , x 2 y , x y 2 , y 3 ) 2 D \begin{cases} \pmb{b^T}(1,x,x^2,x^3)\quad 1D\\[2ex] \pmb{b^T}(1,x,y,x^2,xy,y^2,x^3,x^2y,xy^2,y^3)2D \end{cases} ⎩ ⎨ ⎧bT(1,x,x2,x3)bT(1,x,y,x2,xy,y2,x3,x2y,xy2,y3)1D2D
由1式利用加权最小二乘方法构成二次形式 J ∑ i 1 n w ( x − x i ) [ ∑ j 1 m b j ( x i ) a j ( x ) − f i ] 2 (2) J\sum_{i1}^nw(x-x_i)\Big[\sum_{j1}^mb_j(x_i)a_j(x)-f_i\Big]^2\tag{2} Ji1∑nw(x−xi)[j1∑mbj(xi)aj(x)−fi]2(2)
这里 n n n 是 x x x 附近的影响节点数。 w ( x − x i ) w(x-x_i) w(x−xi) 是节点 x i x_i xi 具有紧支撑性质的光滑连续权函数在 x i x_i xi 紧支持域内部 w i w ( x − x i ) 0 w_iw(x-x_i)0 wiw(x−xi)0在其边界和外部 w i 0 w_i0 wi0。 f i f_i fi 是 x i x_i xi 节点值。
式2对系数 a ( x ) a(x) a(x) 求导得 ∂ J ∂ a j 2 ∑ i 1 n b k ( x i ) w ( x − x i ) [ ∑ j 1 m b j ( x i ) a j ( x ) − f i ] 0 (3) \frac{\partial J}{\partial a_j}2\sum_{i1}^nb_k(x_i)w(x-x_i)\Big[\sum_{j1}^mb_j(x_i)a_j(x)-f_i\Big]0\tag{3} ∂aj∂J2i1∑nbk(xi)w(x−xi)[j1∑mbj(xi)aj(x)−fi]0(3)
上式写成 A ( x ) a ( x ) D ( x ) f (4) \pmb{A(x)a(x)D(x)f}\tag{4} A(x)a(x)D(x)f(4)
则 a ( x ) A − 1 ( x ) D ( x ) f (5) \pmb{a(x)A^{-1}(x)D(x)f}\tag{5} a(x)A−1(x)D(x)f(5)
其中 A B T W ( x ) B , D B T W ( x ) \pmb{AB^TW(x)B,\quad DB^TW(x)} ABTW(x)B,DBTW(x)
其中 B [ b 1 ( x 1 ) b 2 ( x 1 ) ⋯ b m ( x 1 ) b 1 ( x 2 ) b 2 ( x 2 ) ⋯ b m ( x 2 ) ⋮ ⋮ ⋮ b 1 ( x n ) b 2 ( x n ) ⋯ b m ( x n ) ] W ( x ) [ w ( x − x 1 ) 0 ⋯ 0 0 w ( x − x 2 ) ⋯ 0 ⋮ ⋮ ⋮ 0 0 ⋯ w ( x − x n ) ] \pmb{B}\left[\begin{matrix} b_1(x_1) b_2(x_1) \cdots b_m(x_1)\\ b_1(x_2) b_2(x_2) \cdots b_m(x_2)\\ \vdots \vdots \vdots\\ b_1(x_n) b_2(x_n) \cdots b_m(x_n)\\ \end{matrix}\right]\\[3ex] \pmb{W(x)}\left[\begin{matrix} w(x-x_1) 0 \cdots 0\\ 0 w(x-x_2) \cdots 0\\ \vdots \vdots \vdots\\ 0 0 \cdots w(x-x_n)\\ \end{matrix}\right] B b1(x1)b1(x2)⋮b1(xn)b2(x1)b2(x2)⋮b2(xn)⋯⋯⋯bm(x1)bm(x2)⋮bm(xn) W(x) w(x−x1)0⋮00w(x−x2)⋮0⋯⋯⋯00⋮w(x−xn)
将5式代入1式 F ^ ( x ) \hat{F}(x) F^(x) 可表达为 F ^ ( x ) b T A − 1 ( x ) D ( x ) f \hat{F}(x)\pmb{b^TA^{-1}(x)D(x)f} F^(x)bTA−1(x)D(x)f
特别地当基函数为常数即 b 1 b1 b1 时 J ∑ i 1 n w ( x − x i ) [ a 1 − f i ] 2 J\sum_{i1}^nw(x-x_i)[a_1-f_i]^2 Ji1∑nw(x−xi)[a1−fi]2 J J J 对 a 1 a_1 a1 求导令其为 0 ∂ J ∂ a 1 2 ∑ i 1 n w ( x − x i ) [ a 1 − f i ] 0 \frac{\partial J}{\partial a_1}2\sum_{i1}^nw(x-x_i)[a_1-f_i]0 ∂a1∂J2i1∑nw(x−xi)[a1−fi]0
求得 a 1 ∑ i 1 n w ( x − x i ) f i ∑ i 1 n w ( x − x i ) a_1\dfrac{\sum_{i1}^nw(x-x_i)f_i}{\sum_{i1}^nw(x-x_i)} a1∑i1nw(x−xi)∑i1nw(x−xi)fi
所以 F ^ ( x ) ∑ i 1 n w ( x − x i ) f i ∑ i 1 n w ( x − x i ) \hat{F}(x)\dfrac{\sum_{i1}^nw(x-x_i)f_i}{\sum_{i1}^nw(x-x_i)} F^(x)∑i1nw(x−xi)∑i1nw(x−xi)fi
二、紧支撑权函数
移动最小二乘法曲线曲面拟合或插值计算中权函数在其中具有非常重要的作用。这里的权函数必须具有紧支撑性使其有能力在处理大规模曲线与曲面拟合时局部修改更容易。紧支撑权函数的选择应遵循几个原则
每点的权函数值在紧支撑域内是大于零的正数而在该点紧支撑域边界和外部为零必须具有单位分解性权函数必须光滑连续可导在支撑域内愈远离该点权值愈小即保证权值与距离成反比关系。
1紧支撑域及生成算法
紧支撑权函数的引入导致移动最少二乘法具有局部拟合或插值性质大大提高了计算效率和规模。MLS 进行局部拟合或插值时参与局部拟合或插值的相邻节点对 “计算点” 的影响是由给定拟合或插值节点的局部紧支撑域决定。
MLS 近似计算之前先要生成每个节点的局部紧支撑域一个节点的局部紧支撑域形状可以是 “圆” “椭圆” 或 “矩形” 等下面以 “圆” 紧支撑域为例说明如何由离散节点模型自动形成各节点的紧支撑域。该算法确定 N 个节点的离散模型的紧支撑域。
紧支撑域形成算法
赋 N 个节点的每一个 “圆” 紧支撑域的大小 h i 0 h_i0 hi0以每个节点为原点确定各象限与该点距离最近的点其自动计算得到 4 个象限内的距离分别为 h i 1 、 h i 2 、 h i 3 、 h i 4 h_{i1}、h_{i2}、h_{i3}、h_{i4} hi1、hi2、hi3、hi4 确定 h i max { h i 1 , h i 2 , h i 3 , h i 4 } h_i\max\{h_{i1},h_{i2},h_{i3},h_{i4}\} himax{hi1,hi2,hi3,hi4}保证紧支持域包含各个方向合适的节点如图所示。循环 N 个节点引入紧支撑域大小的影响系数 β \beta β每个节点 h i h_i hi 乘系数 β \beta β根据实际情况适当扩大紧支撑域大小以提高拟合或插值精度一般取 β 1.2 ∼ 2.5 \beta1.2\sim 2.5 β1.2∼2.5。
上面算法称为四象限法则每个节点支撑域的大小由该法则确定。 移动最小二乘法中权函数紧支撑域大小选取要合适既要保证所有离散节点的支撑域形成对拟合或插值全域的覆盖又要使域内需拟合或插值 “计算点” 有足够多的邻近节点覆盖以保证精度和使 A A A 矩阵可逆从而使 MLS 算法可行。当选取线性基函数时曲线拟合影响节点不得小于 2 个曲面拟合影响节点不得少于不在同直线上的 3 个节点。
2‘‘计算点” 的影响节点确定
拟合或插值域内任意一点往往同时处于好几个节点的支撑域相交部分。如图所示 x 1 , x 2 , x 3 , x 4 , x 5 x_1,x_2,x_3,x_4,x_5 x1,x2,x3,x4,x5 的支撑域均覆盖住 “计算点 x x x”即计算 “计算点” 时需考虑这五个节点的影响通常称为 “计算点 x x x” 的影响节点该 “计算点” 的函数值及其导数值的计算皆需以此作为依据进行拟合或插值。图中 x 6 x_6 x6 点的支撑域大小如图中的 “虚线圆” 不能盖住 “计算点 x x x ”因此不参与 “计算点 x x x ” 的相关计算。
三、基函数的正交化
多项式基函数的项数选取越多则矩阵 A A A 阶数越高其求逆就越费时。随着 “计算点” 的增多每点的 A A A 矩阵不同皆需求逆计算量很大。因此为了避免方程中 A A A 的求逆减少计算量可以利用 Schmidt 正交化过程由基函数 b j ( x ) , j 1 , ⋯ , m b_j(x),\quad j1,\cdots,m bj(x),j1,⋯,m 构造正交形式的基函数 q j ( x ) , j 1 , ⋯ , m q_j(x),\quad j1,\cdots,m qj(x),j1,⋯,m由此得到的 A A A 矩阵将是对角矩阵。基函数的正交化不仅避免了矩阵 A A A 的求逆而且可以避免可能出现的病态矩阵。
Schmidt 正交化过程 首先因为基函数系数 a ( x ) a(x) a(x) 的 x x x 和 b ( x ) b(x) b(x) 中的 x x x 意义不同所以在正交化过程和最小二乘中区分两个 x x x 非常必要。以下将 a ( x ) a(x) a(x) 的 x x x 记为 x ˉ \bar{x} xˉ b ( x ) b(x) b(x) 中的 x x x 记为 x x x。
对给定的多项式基函数 b j ( x ) , j 1 , ⋯ , m b_j(x),\quad j1,\cdots,m bj(x),j1,⋯,m存在正交形式的基函数 q j ( x , x ˉ ) , j 1 , ⋯ , m q_j(x,\bar{x}),\quad j1,\cdots,m qj(x,xˉ),j1,⋯,m并且 q 1 ( x , x ˉ ) b 1 ( x ) q j ( x , x ˉ ) b j ( x ) − ∑ J 1 j − 1 α j J ( x ˉ ) q J ( x , x ˉ ) , j 2 , ⋅ , m q_1(x,\bar{x})b_1(x)\\ q_j(x,\bar{x})b_j(x)-\sum_{J1}^{j-1}\alpha_{jJ}(\bar{x})q_J(x,\bar{x}),\quad j2,\cdot,m q1(x,xˉ)b1(x)qj(x,xˉ)bj(x)−J1∑j−1αjJ(xˉ)qJ(x,xˉ),j2,⋅,m
其中 α j J ∑ i 1 n w i ( x ˉ ) b j ( x i ) q J ( x i , x ˉ ) ∑ j 1 n w i ( x ˉ ) q J 2 ( x i , x ˉ ) \alpha_{jJ}\frac{\sum_{i1}^nw_i(\bar{x})b_j(x_i)q_J(x_i,\bar{x})}{\sum_{j1}^nw_i(\bar{x})q_J^2(x_i,\bar{x})} αjJ∑j1nwi(xˉ)qJ2(xi,xˉ)∑i1nwi(xˉ)bj(xi)qJ(xi,xˉ)
一维情况下的正交基函数为 { q 0 ( x , x ˉ ) 1 q 1 ( x , x ˉ ) x − α 1 q k 1 ( x , x ˉ ) ( x − α k 1 ) q k ( x , x ˉ ) − β k 1 q k − 1 ( x , x ˉ ) α k 1 ( x ˉ ) ( x q k , q k ) ( q k , q k ) ∑ i 1 m w i ( x ˉ ) x i q k 2 ( x i , x ˉ ) ∑ i 1 m w i ( x ˉ ) q k 2 ( x i , x ˉ ) β k 1 ( x ˉ ) ( q k , q k ) ( q k − 1 , q k − 1 ) ∑ i 1 m w i ( x ˉ ) q k 2 ( x i , x ˉ ) ∑ i 1 m w i ( x ˉ ) q k − 1 2 ( x i , x ˉ ) \begin{cases} q_0(x,\bar{x})1\\[1ex] q_1(x,\bar{x})x-\alpha_1\\[1ex] q_{k1}(x,\bar{x})(x-\alpha_{k1})q_k(x,\bar{x})-\beta_{k1}q_{k-1}(x,\bar{x})\\[1ex] \alpha_{k1}(\bar{x})\dfrac{(xq_k,q_k)}{(q_k,q_k)}\dfrac{\sum_{i1}^mw_i(\bar x)x_iq_k^2(x_i,\bar x)}{\sum_{i1}^mw_i(\bar x)q_k^2(x_i,\bar x)}\\[3ex] \beta_{k1}(\bar x)\dfrac{(q_k,q_k)}{(q_{k-1},q_{k-1})}\dfrac{\sum_{i1}^mw_i(\bar x)q_k^2(x_i,\bar x)}{\sum_{i1}^mw_i(\bar x)q_{k-1}^2(x_i,\bar x)} \end{cases} ⎩ ⎨ ⎧q0(x,xˉ)1q1(x,xˉ)x−α1qk1(x,xˉ)(x−αk1)qk(x,xˉ)−βk1qk−1(x,xˉ)αk1(xˉ)(qk,qk)(xqk,qk)∑i1mwi(xˉ)qk2(xi,xˉ)∑i1mwi(xˉ)xiqk2(xi,xˉ)βk1(xˉ)(qk−1,qk−1)(qk,qk)∑i1mwi(xˉ)qk−12(xi,xˉ)∑i1mwi(xˉ)qk2(xi,xˉ) 令 β 1 0 \beta_10 β10 其中 k 0 , 1 , ⋯ , m − 1 k0,1,\cdots,m-1 k0,1,⋯,m−1
由2.3式可知 ∑ i 1 n w i ( x ˉ ) ∑ j 1 m b k ( x i ) b j ( x i ) a j ( x ˉ ) ∑ i 1 n w i ( x ˉ ) b k ( x i ) f i ∑ k , j 1 m ( ∑ i 1 n ( w i ( x ˉ ) b k ( x i ) b j ( x i ) ) ) a j ( x ˉ ) ∑ i 1 n w i ( x ˉ ) b k ( x i ) f i (6) \sum_{i1}^nw_i(\bar x)\sum_{j1}^mb_k(x_i)b_j(x_i)a_j(\bar x)\sum_{i1}^nw_i(\bar x)b_k(x_i)f_i\\ \sum_{k,j1}^m\Big(\sum_{i1}^n(w_i(\bar x)b_k(x_i)b_j(x_i))\Big)a_j(\bar x)\sum_{i1}^nw_i(\bar x)b_k(x_i)f_i\tag{6} i1∑nwi(xˉ)j1∑mbk(xi)bj(xi)aj(xˉ)i1∑nwi(xˉ)bk(xi)fik,j1∑m(i1∑n(wi(xˉ)bk(xi)bj(xi)))aj(xˉ)i1∑nwi(xˉ)bk(xi)fi(6)
由加权正交基定义 ( b k , b j ) ∑ i 1 n w i ( x ˉ ) b k ( x i ) b j ( x i ) ( b k , f ) ∑ i 1 n w i ( x ˉ ) b k ( x i ) f i (b_k,b_j)\sum_{i1}^nw_i(\bar x)b_k(x_i)b_j(x_i)\\ (b_k,f)\sum_{i1}^nw_i(\bar x)b_k(x_i)f_i (bk,bj)i1∑nwi(xˉ)bk(xi)bj(xi)(bk,f)i1∑nwi(xˉ)bk(xi)fi
因此式6表示为 ∑ j 1 m ( b k , b j ) a j ( x ) ( b k , f ) k , j 1 , ⋯ , m \sum_{j1}^m(b_k,b_j)a_j(x)(b_k,f)\quad k,j1,\cdots,m j1∑m(bk,bj)aj(x)(bk,f)k,j1,⋯,m ( b k , b j ) (b_k,b_j) (bk,bj) 生成的矩阵是满阵可以通过 Schmidt 正交化中的正交基函数 q j ( x ) ( j 1 , ⋯ , m ) q_j(x)\ (j1,\cdots,m) qj(x) (j1,⋯,m) 将其对角化。由正交基的性质得到 F ^ ( x ) ∑ j 1 m q j ( x , x ˉ ) a j ( x ˉ ) \hat{F}(x)\sum_{j1}^mq_j(x,\bar x)a_j(\bar x) F^(x)j1∑mqj(x,xˉ)aj(xˉ)
由此推得 ∑ j 1 m ( q k , q j ) a j ( x ) ( q k , f ) \sum_{j1}^m(q_k,q_j)a_j(x)(q_k,f) j1∑m(qk,qj)aj(x)(qk,f)
因为 ( q k , q j ) { 0 k ≠ j ≠ 0 k j (q_k,q_j) \begin{cases} 0\quad k\neq j\\ \neq 0 kj \end{cases} (qk,qj){00kjkj
矩阵 A A A 是对角矩阵 a j ( x ) a_j(x) aj(x) 的求解无需求逆即 a j ( x ˉ ) ( q j , f ) ( q j , q j ) ∑ i 1 n w i ( x ˉ ) q j ( x i , x ˉ ) f i ∑ i 1 n w i ( x ˉ ) q j 2 ( x i , x ˉ ) a_j(\bar x)\dfrac{(q_j,f)}{(q_j,q_j)}\dfrac{\sum_{i1}^nw_i(\bar x)q_j(x_i,\bar x)f_i}{\sum_{i1}^nw_i(\bar x)q_j^2(x_i,\bar x)} aj(xˉ)(qj,qj)(qj,f)∑i1nwi(xˉ)qj2(xi,xˉ)∑i1nwi(xˉ)qj(xi,xˉ)fi
令 d i ( x ˉ ) ∑ i 1 n w i ( x ˉ ) q j 2 ( x i , x ˉ ) d_i(\bar x)\sum_{i1}^nw_i(\bar x)q_j^2(x_i,\bar x) di(xˉ)i1∑nwi(xˉ)qj2(xi,xˉ) x , x ˉ x,\quad \bar x x,xˉ 的区分只是最小二乘法过程需要这一过程完成后就不再有区分的必要最终得到 F ^ ( x ) ∑ i 1 n φ i f i φ i w i ( x ) ∑ j 1 m q j ( x i , x ) q j ( x i , x ) d i ( x ) \hat{F}(x)\sum_{i1}^n\varphi_if_i\\ \varphi_iw_i(x)\sum_{j1}^m\frac{q_j(x_i,x)q_j(x_i,x)}{d_i(x)} F^(x)i1∑nφifiφiwi(x)j1∑mdi(x)qj(xi,x)qj(xi,x)
当基函数次数增加时只需要计算 a m 1 a_{m1} am1 以及 Schmidt 正交化过程中的 α m 1 \alpha_{m1} αm1 和 β m 1 \beta_{m1} βm1 即可不需要重新计算矩阵 A A A 中所有元素减少了计算量降低了误差。
