利用径向基函数进行微分方程数值解的动点算法研究与应用
|
摘要
近几十年来,径向基函数的逼近能力有目共睹.基于它的优良性质,上世纪80年代以来人们开始用径向基函数处理微分方程数值解问题,也就是无网格径向基函数法.最早使用径向基函数做微分方程数值解的是用径向基插值.但这样做的缺点是每次求解过程中涉及大型方程组的求解问题,也就是大规模矩阵的求逆问题.为了避免这个问题,90年代Wu等利用径向基函数的拟插值(如MQ拟插值)求解微分方程.
利用MQ拟插值方法时固定时间层上任意点的函数值都是已知的.由于MQ拟插值在节点选取上的优越性,Wu利用MQ拟插值做自适应微分方程数值解法,在求解激波等大曲率曲线时效果良好.本文在此基础上给出新的动点算法.
首先,第一二章对本文的主要内容和预备知识做了简要介绍.介绍了径向基函数和微分方程数值解的发展历史,动点算法的背景知识以及基于偏微分方程的图像分割方法的背景知识.
第三章对Huang提出的几种移动网格偏微分方程(MMPDE)方法进行了分析.我们给出了这几种MMPDE的收敛条件和收敛阶,并给出几种新的MMPDE第四章我们给出了一个动点方程.我们给出了算法和误差估计.基于误差估计我们证明了新的动点算法的稳定性和网格缠绕问题.数值结果表明我们的方法能处理更陡峭动荡的偏微分方程.
基于MQ拟插值在微分方程数值解中的良好应用,尤其是对激波和大曲率的问题也具有良好的拟合能力,第五章我们应用MQ拟插值拟合边缘检测模型.与水平集方法相比,我们的方法具有拟合时间短以及描述精确的优点.
第六章讨论MQ拟插值在微分方程数值解中的应用.应用一种MQ拟插值(?)D解决了一个既具有理论意义又具有广泛应用的经典方程Burgers-Fisher方程,结合它的解析解,我们给出了本方法的误差估计并与B样条拟插值方法进行了比较.实验结果表明,我们的方法不仅简单,易操作,而且拟合方程的效果好.
第七章我们对目前工作做了一个总结,给出了我们未来的工作方向.
Based on radial basis function'good capability of approximation, since1980s, peo-ple have began to use the radial basis function for the numerical solutions of partial differential equations(PDE),that is the meshless radial basis function method.
In1990s Wu et al. applied one kind of radial basis function called MQ quasi-interpolation to solve PDEs. Considering the superiority of MQ quasi-interpolation in the freedom of node selection, Wu apply the MQ quasi-interpolation for adaptive methods of partial differential equations. Based on this, we give some moving knots equations in the thesis.
An introduction to the main work and prior knowledge of this article is given in the first two chapters. In chapter3we analyze the4kinds of moving mesh partial differential equations (MMPDEs) proposed by Huang. Based on the analysis we give several new MMPDEs that performs better. Then a dynamical moving knots equation that considering both spatially and temporally combined with the MQ quasi-interpolation is given in chapter4. We give the algorithm and the error estimation. Numerical results show that our method can handle more steep turbulence.
Since MQ quasi-interpolation performs well in numerical methods of PDEs especially the shock wave equation and high curvature turbulence equations. In chapter5we apply MQ quasi-difference for simulating boundary detection models. Compared with the level set method, our approach costs little time and be able to get the boundaries more precisely.
Chapter6gives a simple method to simulate the famous Burgers-Fisher equation using one kind of MQ quasi-interpolation L_D Posteriori error estimate of this method is given.
Chapter7presents a work summary and gives the plan of our future work.
利用MQ拟插值方法时固定时间层上任意点的函数值都是已知的.由于MQ拟插值在节点选取上的优越性,Wu利用MQ拟插值做自适应微分方程数值解法,在求解激波等大曲率曲线时效果良好.本文在此基础上给出新的动点算法.
首先,第一二章对本文的主要内容和预备知识做了简要介绍.介绍了径向基函数和微分方程数值解的发展历史,动点算法的背景知识以及基于偏微分方程的图像分割方法的背景知识.
第三章对Huang提出的几种移动网格偏微分方程(MMPDE)方法进行了分析.我们给出了这几种MMPDE的收敛条件和收敛阶,并给出几种新的MMPDE第四章我们给出了一个动点方程.我们给出了算法和误差估计.基于误差估计我们证明了新的动点算法的稳定性和网格缠绕问题.数值结果表明我们的方法能处理更陡峭动荡的偏微分方程.
基于MQ拟插值在微分方程数值解中的良好应用,尤其是对激波和大曲率的问题也具有良好的拟合能力,第五章我们应用MQ拟插值拟合边缘检测模型.与水平集方法相比,我们的方法具有拟合时间短以及描述精确的优点.
第六章讨论MQ拟插值在微分方程数值解中的应用.应用一种MQ拟插值(?)D解决了一个既具有理论意义又具有广泛应用的经典方程Burgers-Fisher方程,结合它的解析解,我们给出了本方法的误差估计并与B样条拟插值方法进行了比较.实验结果表明,我们的方法不仅简单,易操作,而且拟合方程的效果好.
第七章我们对目前工作做了一个总结,给出了我们未来的工作方向.
Based on radial basis function'good capability of approximation, since1980s, peo-ple have began to use the radial basis function for the numerical solutions of partial differential equations(PDE),that is the meshless radial basis function method.
In1990s Wu et al. applied one kind of radial basis function called MQ quasi-interpolation to solve PDEs. Considering the superiority of MQ quasi-interpolation in the freedom of node selection, Wu apply the MQ quasi-interpolation for adaptive methods of partial differential equations. Based on this, we give some moving knots equations in the thesis.
An introduction to the main work and prior knowledge of this article is given in the first two chapters. In chapter3we analyze the4kinds of moving mesh partial differential equations (MMPDEs) proposed by Huang. Based on the analysis we give several new MMPDEs that performs better. Then a dynamical moving knots equation that considering both spatially and temporally combined with the MQ quasi-interpolation is given in chapter4. We give the algorithm and the error estimation. Numerical results show that our method can handle more steep turbulence.
Since MQ quasi-interpolation performs well in numerical methods of PDEs especially the shock wave equation and high curvature turbulence equations. In chapter5we apply MQ quasi-difference for simulating boundary detection models. Compared with the level set method, our approach costs little time and be able to get the boundaries more precisely.
Chapter6gives a simple method to simulate the famous Burgers-Fisher equation using one kind of MQ quasi-interpolation L_D Posteriori error estimate of this method is given.
Chapter7presents a work summary and gives the plan of our future work.
引文
[1]李俊.基于曲线演化的图像分割方法及应用研究.博士学位论文.上海交通大学,1：10-15,2001.
[2]吴宗敏.径向基函数,散乱数据拟合与无网格偏微分方程数值解.工程数学学报,19(2)：1-12,2002.
[3]吴宗敏.散乱数据拟合的模型,方法和理论.科学出版社,2007.
[4]S. Adjerid and J.E. Flaherty. A moving finite element method with error estimation and refinement for one-dimensional time dependent, partial differential equations. SIAM Journal on Numerical Analysis, pages 778-796,1986.
[5]S. Atluri and S. Shen. The meshless method. Forsyth:Tech. Sei. Press USA,2002.
[6]E. Babolian and J. Saeidian. Analytic approximate solutions to burgers, fisher, huxley equations and two combined forms of these equations. Communications in Nonlinear Science and Numerical Simulation,14(5):1984-1992,2009.
[7]RK Beatson and MJD Powell. Univariate multiquadric approximation:quasi-interpolation to scattered data. Constructive Approximation,8(3):275-288,1992.
[8]MD Buhmann. Multivariate interpolation in odd-dimensional euclidean spaces using multiquadrics. Constructive Approximation,6(1):21-34,1990.
[9]M.D. Buhmann. Radial basts functions:theory and implementations, volume 12. Cambridge Univ Pr,2003.
[10]M.D. Buhmann and C.A. Micchelli. Multiquadric interpolation improved. Com-puters (?) Mathematics with Applications,24(12):21-25,1992.
[11]V. Caselles, F. Catte, T. Coll, and F. Dibos. A geometric model for active contours in image processing. Numerische Mathematik,66(1):1-31,1993.
[12]V. Caselles, R. Kimmel, and G. Sapiro. Geodesic active contours. International journal of computer vision,22(1):61-79,1997.
[13]T.F. Chan and L.A. Vese. Active contours without edges. Image Processing, IEEE Transactions on,10(2):266-277,2001.
[14]R. Chen and Z. Wu. Applying multiquadric quasi-interpolation to solve burgers' equation. Applied mathematics and computation,172(1):472-484,2006.
[15]M.M. Cheng, F.L. Zhang, N.J. Mitra, X. Huang, and S.M. Hu. Repfinder:finding approximately repeated scene elements for image editing. ACM Transactions on Graphics (TOG),29(4):83,2010.
[16]EA Dorfi and L.O.C. Drury. Simple adaptive grids for 1-d initial value problems. Journal of Computational Physics,69(1):175-195,1987.
[17]J. Duchon. Splines minimizing rotation-invariant semi-norms in sobolev spaces. Constructive theory of functions of several variables, pages 85-100,1977.
[18]N. Dyn. Interpolation and approximation by radial and related functions. Approx-imation theory Ⅵ, 1(s 1),1989.
[19]R. Franke. Scattered data interpolation:Tests of some methods. Math. Comput., 38(157):181-200,1982.
[20]RM Furzeland, JG Verwer, and PA Zegeling. A numerical study of three moving-grid methods for one-dimensional partial differential equations which are based on the method of lines. Journal of Computational Physics,89(2):349-388,1990.
[21]A. Golbabai and M. Javidi. A spectral domain decomposition approach for the generalized burger's-fisher equation. Chaos, Solitons (?) Fractals,39(1):385-392, 2009.
[22]R.L. Hardy. Multiquadric equations of topography and other irregular surfaces. Journal of Geophysical Research,76(8):1905-1915,1971.
[23]R.L. Hardy. Theory and applications of the multiquadric-biharmonic method. 20 years of discovery 1968-1988. Computers (?) Mathematics with Applications, 19(8):163-208,1990.
[24]W. Huang, Y. Ren, and R.D. Russell. Moving mesh methods based on moving mesh, partial differential equations. Journal of Computational Physics,113(2):279-290, 1994.
[25]W. Huang, Y. Ren, and R.D. Russell. Moving mesh partial differential equations (mmpdes) based on the equidistribution principle. SIAM Journal on Numerical Analysis, pages 709-730,1994.
[26]H.N.A. Ismail and A.A.A. Rabboh. A restrictive pade approximation for the solution of the generalized fisher and burger-fisher equations. Applied Mathematics and Computation,154(1):203-210,2004.
[27]A. Jaun, J. Hedin, and T. Johnson. Numerical methods for partial differential equations. Swedish Netuniversity,1999.
[28]M. Javidi. Spectral collocation method for the solution of the generalized burger fisher equation. Applied mathematics and computation,174(1):345-352,2006.
[29]M. Kass, A. Wit kin, and D. Terzopoulos. Snakes:Active contour models. Interna-tional journal of computer vision,1(4):321-331,1988.
[30]D. Kaya and S.M. El-Sayed. A numerical simulation and explicit solutions of the generalized burgers-fisher equation. Applied mathematics and computation, 152(2):403-413,2004.
[31]L. Ma and Z. Wu. Approximation to the k-th derivatives by multiquadric quasi-interpolation method. Journal of computational and applied mathematics,231(2):925-932,2009.
[32]L.M. Ma and Z.M. Wu. Stability of multiquadric quasi-interpolation to approximate high order derivatives. Science China Mathematics,53(4):985-992,2010.
[33]C.A. Micchelli. Interpolation of scattered data:distance matrices and conditionally positive definite functions. Constructive Approximation,2(1):11-22,1986.
[34]RE Mickcns and AB Gumcl. Construction and analysis of a non-standard finite difference scheme for the burgers-fisher equation. Journal of Sound Vibration, 257:791-797,2002.
[35]K. Miller. Moving finite elements, ⅱ. SI AM Journal on Numerical Analysts, pages 1033-1057,1981.
[36]S. Osher and J.A. Sethian. Fronts propagating with curvature-dependent speed:al-gorithms based on hamilton-jacobi formulations. Journal of computational physics, 79(1):12-49,1988.
[37]M.J.D. Powell. Radial basis functions for multivariable interpolation:a review. In Algorithms for approximation, pages 143-167. Clarendon Press,1987.
[38]MM Rai and DA Anderson. Application of adaptive grids to fluid-flow problems with asymptotic solutions. In AIAA, Aerospace Sciences Meeting, volume 1,1981.
[39]Y. Ren and R.D. Russell. Moving mesh techniques based upon equidistribution, and their stability. SI AM journal on scientific and. statistical computing,13:1265, 1992.
[40]R. Schaback and Z. Wu. Operators on radial functions. Journal, of computational and applied mathematics,73(1):257-270,1996.
[41]K. Somkantha, N. Theera-Umpon, and S. Auephanwiriyakul. Boundary detection in medical images using edge following algorithm based on intensity gradient and texture gradient features. Biomedical Engineering, IEEE Transactions on, (99):1-1, 2011.
[42]E.M. Stein and G.L. Weiss. Introduction to Fourier analysis on Euclidean spaces, volume 32. Princeton Univ Pr,1971.
[43]R. Wang. Multivariate spline functions and their applications, volume 529. Kluwer Academic Publishers,2001.
[44]A.M. Wazwaz. The tanh method for generalized forms of nonlinear heat conduction and burgers-fisher equations. Applied mathematics and computation,169(1):321-338,2005.
[45]A.M. Wazwaz. Analytic study on burgers, fisher, huxley equations and combined forms of these equations. Applied Mathematics and Computation,19-5(2):754-761, 2008.
[46]A.M. Wazwaz and A. Gorguis. An analytic study of fisher's equation by using adomi-an decomposition method. Applied Mathematics and Computation,154(3):609-620, 2004.
[47]H. Wendland. Piecewise polynomial, positive definite and compactly supported ra-dial functions of minimal degree. Advances in computational Mathematics,4(1):389-396,1995.
[48]Z. Wu. Compactly supported positive definite radial functions. Advances in Com-putational Mathematics,4(1):283-292,1995.
[49]Z. Wu. Solving pde with radial basis function and the error estimation. Adv. Comput. Math. Lectures in Pure (?) Applied Mathematics,202,1998.
[50]Z. Wu. Dynamical knot and shape parameter setting for simulating shock wave by using multi-quadric quasi-interpolation. Engineering analysis with boundary elements,29(4):354-358,2005.
[51]C. Xu and J.L. Prince. Snakes, shapes, and gradient vector flow. Image Processing, IEEE Transactions on,7(3):359-369,1998.
[52]Q. Zhang. Numerical solutions for partial differential equations.2012.
[53]S.H. Zhang, T. Chen, Y.F. Zhang, S.M. Hu, and R.R. Martin. Vectorizing car-toon animations. Visualization and Computer Graphics, IEEE Transactions on, 15(4):618-629,2009.
[54]C.G. Zhu and W.S. Kang. Numerical solution of burgers-fisher equation by cubic b-spline quasi-interpolation. Applied Mathematics and Computation,216(9):2679-2686,2010.
[55]W. Zongmin. Hermite-birkhoff interpolation of scattered data by radial basis func-tions. Approximation Theory and its Applications,8(2):1-10,1992.
[2]吴宗敏.径向基函数,散乱数据拟合与无网格偏微分方程数值解.工程数学学报,19(2)：1-12,2002.
[3]吴宗敏.散乱数据拟合的模型,方法和理论.科学出版社,2007.
[4]S. Adjerid and J.E. Flaherty. A moving finite element method with error estimation and refinement for one-dimensional time dependent, partial differential equations. SIAM Journal on Numerical Analysis, pages 778-796,1986.
[5]S. Atluri and S. Shen. The meshless method. Forsyth:Tech. Sei. Press USA,2002.
[6]E. Babolian and J. Saeidian. Analytic approximate solutions to burgers, fisher, huxley equations and two combined forms of these equations. Communications in Nonlinear Science and Numerical Simulation,14(5):1984-1992,2009.
[7]RK Beatson and MJD Powell. Univariate multiquadric approximation:quasi-interpolation to scattered data. Constructive Approximation,8(3):275-288,1992.
[8]MD Buhmann. Multivariate interpolation in odd-dimensional euclidean spaces using multiquadrics. Constructive Approximation,6(1):21-34,1990.
[9]M.D. Buhmann. Radial basts functions:theory and implementations, volume 12. Cambridge Univ Pr,2003.
[10]M.D. Buhmann and C.A. Micchelli. Multiquadric interpolation improved. Com-puters (?) Mathematics with Applications,24(12):21-25,1992.
[11]V. Caselles, F. Catte, T. Coll, and F. Dibos. A geometric model for active contours in image processing. Numerische Mathematik,66(1):1-31,1993.
[12]V. Caselles, R. Kimmel, and G. Sapiro. Geodesic active contours. International journal of computer vision,22(1):61-79,1997.
[13]T.F. Chan and L.A. Vese. Active contours without edges. Image Processing, IEEE Transactions on,10(2):266-277,2001.
[14]R. Chen and Z. Wu. Applying multiquadric quasi-interpolation to solve burgers' equation. Applied mathematics and computation,172(1):472-484,2006.
[15]M.M. Cheng, F.L. Zhang, N.J. Mitra, X. Huang, and S.M. Hu. Repfinder:finding approximately repeated scene elements for image editing. ACM Transactions on Graphics (TOG),29(4):83,2010.
[16]EA Dorfi and L.O.C. Drury. Simple adaptive grids for 1-d initial value problems. Journal of Computational Physics,69(1):175-195,1987.
[17]J. Duchon. Splines minimizing rotation-invariant semi-norms in sobolev spaces. Constructive theory of functions of several variables, pages 85-100,1977.
[18]N. Dyn. Interpolation and approximation by radial and related functions. Approx-imation theory Ⅵ, 1(s 1),1989.
[19]R. Franke. Scattered data interpolation:Tests of some methods. Math. Comput., 38(157):181-200,1982.
[20]RM Furzeland, JG Verwer, and PA Zegeling. A numerical study of three moving-grid methods for one-dimensional partial differential equations which are based on the method of lines. Journal of Computational Physics,89(2):349-388,1990.
[21]A. Golbabai and M. Javidi. A spectral domain decomposition approach for the generalized burger's-fisher equation. Chaos, Solitons (?) Fractals,39(1):385-392, 2009.
[22]R.L. Hardy. Multiquadric equations of topography and other irregular surfaces. Journal of Geophysical Research,76(8):1905-1915,1971.
[23]R.L. Hardy. Theory and applications of the multiquadric-biharmonic method. 20 years of discovery 1968-1988. Computers (?) Mathematics with Applications, 19(8):163-208,1990.
[24]W. Huang, Y. Ren, and R.D. Russell. Moving mesh methods based on moving mesh, partial differential equations. Journal of Computational Physics,113(2):279-290, 1994.
[25]W. Huang, Y. Ren, and R.D. Russell. Moving mesh partial differential equations (mmpdes) based on the equidistribution principle. SIAM Journal on Numerical Analysis, pages 709-730,1994.
[26]H.N.A. Ismail and A.A.A. Rabboh. A restrictive pade approximation for the solution of the generalized fisher and burger-fisher equations. Applied Mathematics and Computation,154(1):203-210,2004.
[27]A. Jaun, J. Hedin, and T. Johnson. Numerical methods for partial differential equations. Swedish Netuniversity,1999.
[28]M. Javidi. Spectral collocation method for the solution of the generalized burger fisher equation. Applied mathematics and computation,174(1):345-352,2006.
[29]M. Kass, A. Wit kin, and D. Terzopoulos. Snakes:Active contour models. Interna-tional journal of computer vision,1(4):321-331,1988.
[30]D. Kaya and S.M. El-Sayed. A numerical simulation and explicit solutions of the generalized burgers-fisher equation. Applied mathematics and computation, 152(2):403-413,2004.
[31]L. Ma and Z. Wu. Approximation to the k-th derivatives by multiquadric quasi-interpolation method. Journal of computational and applied mathematics,231(2):925-932,2009.
[32]L.M. Ma and Z.M. Wu. Stability of multiquadric quasi-interpolation to approximate high order derivatives. Science China Mathematics,53(4):985-992,2010.
[33]C.A. Micchelli. Interpolation of scattered data:distance matrices and conditionally positive definite functions. Constructive Approximation,2(1):11-22,1986.
[34]RE Mickcns and AB Gumcl. Construction and analysis of a non-standard finite difference scheme for the burgers-fisher equation. Journal of Sound Vibration, 257:791-797,2002.
[35]K. Miller. Moving finite elements, ⅱ. SI AM Journal on Numerical Analysts, pages 1033-1057,1981.
[36]S. Osher and J.A. Sethian. Fronts propagating with curvature-dependent speed:al-gorithms based on hamilton-jacobi formulations. Journal of computational physics, 79(1):12-49,1988.
[37]M.J.D. Powell. Radial basis functions for multivariable interpolation:a review. In Algorithms for approximation, pages 143-167. Clarendon Press,1987.
[38]MM Rai and DA Anderson. Application of adaptive grids to fluid-flow problems with asymptotic solutions. In AIAA, Aerospace Sciences Meeting, volume 1,1981.
[39]Y. Ren and R.D. Russell. Moving mesh techniques based upon equidistribution, and their stability. SI AM journal on scientific and. statistical computing,13:1265, 1992.
[40]R. Schaback and Z. Wu. Operators on radial functions. Journal, of computational and applied mathematics,73(1):257-270,1996.
[41]K. Somkantha, N. Theera-Umpon, and S. Auephanwiriyakul. Boundary detection in medical images using edge following algorithm based on intensity gradient and texture gradient features. Biomedical Engineering, IEEE Transactions on, (99):1-1, 2011.
[42]E.M. Stein and G.L. Weiss. Introduction to Fourier analysis on Euclidean spaces, volume 32. Princeton Univ Pr,1971.
[43]R. Wang. Multivariate spline functions and their applications, volume 529. Kluwer Academic Publishers,2001.
[44]A.M. Wazwaz. The tanh method for generalized forms of nonlinear heat conduction and burgers-fisher equations. Applied mathematics and computation,169(1):321-338,2005.
[45]A.M. Wazwaz. Analytic study on burgers, fisher, huxley equations and combined forms of these equations. Applied Mathematics and Computation,19-5(2):754-761, 2008.
[46]A.M. Wazwaz and A. Gorguis. An analytic study of fisher's equation by using adomi-an decomposition method. Applied Mathematics and Computation,154(3):609-620, 2004.
[47]H. Wendland. Piecewise polynomial, positive definite and compactly supported ra-dial functions of minimal degree. Advances in computational Mathematics,4(1):389-396,1995.
[48]Z. Wu. Compactly supported positive definite radial functions. Advances in Com-putational Mathematics,4(1):283-292,1995.
[49]Z. Wu. Solving pde with radial basis function and the error estimation. Adv. Comput. Math. Lectures in Pure (?) Applied Mathematics,202,1998.
[50]Z. Wu. Dynamical knot and shape parameter setting for simulating shock wave by using multi-quadric quasi-interpolation. Engineering analysis with boundary elements,29(4):354-358,2005.
[51]C. Xu and J.L. Prince. Snakes, shapes, and gradient vector flow. Image Processing, IEEE Transactions on,7(3):359-369,1998.
[52]Q. Zhang. Numerical solutions for partial differential equations.2012.
[53]S.H. Zhang, T. Chen, Y.F. Zhang, S.M. Hu, and R.R. Martin. Vectorizing car-toon animations. Visualization and Computer Graphics, IEEE Transactions on, 15(4):618-629,2009.
[54]C.G. Zhu and W.S. Kang. Numerical solution of burgers-fisher equation by cubic b-spline quasi-interpolation. Applied Mathematics and Computation,216(9):2679-2686,2010.
[55]W. Zongmin. Hermite-birkhoff interpolation of scattered data by radial basis func-tions. Approximation Theory and its Applications,8(2):1-10,1992.