GS-PIA算法的收敛性证明
|
摘要
非均匀三次B样条曲线插值的GS-PIA算法具有简单、稳定及收敛速度较快等优点.文中详细阐述了GS-PIA算法的几何意义,严格证明了算法的收敛性.首先定义算法配置矩阵的比较矩阵,借助矩阵理论的正则分裂证明比较矩阵对应的迭代矩阵的收敛性;然后利用矩阵的相似性,证明了非均匀三次B样条曲线插值的GS-PIA算法的收敛性.为GS-PIA算法的进一步研究及其在计算机图形学等相关领域的应用打下了理论基础.
The GS-PIA algorithm for non-uniform cubic B-spline curve interpolation has the advantages of simplicity, stability, fast convergence and so on. In this paper, we elaborate the detailed geometric meaning of the GS-PIA algorithm and prove the convergence of the algorithm. We first define comparison matrix of configuration matrix of the algorithm. And the convergence of the iterative matrix corresponding to the comparison matrix is proved by the regular splittings of the matrices. Using the similarity of the matrices, we prove that the GS-PIA algorithm for non-uniform cubic B-spline curve interpolation is convergent. It lays out a theoretical foundation for further research of GS-PIA algorithm and applications in computer graphics and related fields.
The GS-PIA algorithm for non-uniform cubic B-spline curve interpolation has the advantages of simplicity, stability, fast convergence and so on. In this paper, we elaborate the detailed geometric meaning of the GS-PIA algorithm and prove the convergence of the algorithm. We first define comparison matrix of configuration matrix of the algorithm. And the convergence of the iterative matrix corresponding to the comparison matrix is proved by the regular splittings of the matrices. Using the similarity of the matrices, we prove that the GS-PIA algorithm for non-uniform cubic B-spline curve interpolation is convergent. It lays out a theoretical foundation for further research of GS-PIA algorithm and applications in computer graphics and related fields.
引文
[1]Qi Dongxu,Tian Zixian,Zhang Yuxin,et al.The method of numeric polish in curve fitting[J].Acta Mathematica Sinica,1975,18(3):173-184(in Chinese)(齐东旭,田自贤,张玉心,等.曲线拟合的数值磨光方法[J].数学学报,1975,18(3):173-184)
[2]de Boor C.How does Agee’s smoothing method work?[OL].[2018-01-12].http://ftp.cs.wisc.edu/Approx/agee.pdf
[3]Qi Dongxu.Some notes on mathematical methods in computer aided geometric modeling[J].Journal of the Northern Industrial University,1991,3(1):1-8(in Chinese)(齐东旭.关于计算机辅助几何造型数学方法的若干注记[J].北方工业大学学报,1991,3(1):1-8)
[4]Lin H W,Wang G J,Dong C S.Constructing iterative non-uniform B-spline curve and surface to fit data points[J].Science in China Series:Information Sciences,2004,47(3):315-331
[5]Lin H W,Bao H J,Wang G J.Totally positive bases and progressive iteration approximation[J].Computers&Mathematics with Applications,2005,50(3/4):575-586
[6]Cheng F H,Fan F T,Lai S H,et al.Loop subdivision surface based progressive interpolation[J].Journal of Computer Science and Technology,2009,24(1):39-46
[7]Chen Z X,Luo X N,Tan L,et al.Progressive interpolation based on Catmull-Clark subdivision surfaces[J].Computer Graphics Forum,2008,27(7):1823-1827
[8]Chen J,Wang G J.Progressive iterative approximation for triangular Bézier surfaces[J].Computer-Aided Design,2011,43(8):889-895
[9]Lin H W,Maekawa T,Deng C Y.Survey on geometric iterative methods and their applications[J].Computer-Aided Design,2018,95:40-51
[10]Delgado J,Pe?a J M.Progressive iterative approximation and bases with the fastest convergence rates[J].Computer Aided Geometric Design,2007,24(1):10-18
[11]Lu L Z.Weighted progressive iteration approximation and convergence analysis[J].Computer Aided Geometric Design,2010,27(2):129-137
[12]Deng C Y,Ma W Y.Weighted progressive interpolation of Loop subdivision surfaces[J].Computer-Aided Design,2012,44(5):424-431
[13]Liu Xiaoyan,Deng Chongyang.Jacobi-PIA algorithm for non-uniform cubic B-spline curve interpolation[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(3):485-491(in Chinese)(刘晓艳,邓重阳.非均匀三次B样条曲线插值的Jacobi-PIA算法[J].计算机辅助设计与图形学学报,2015,27(3):485-491)
[14]Lin H W,Zhang Z Y.An extended iterative format for the progressive-iteration approximation[J].Computers&Graphics,2011,35(5):967-975
[15]Lin H W,Zhang Z Y.An efficient method for fitting large data sets using T-splines[J].SIAM Journal on Scientific Computing,2013,35(6):A3052-A3068
[16]Deng C Y,Lin H W.Progressive and iterative approximation for least squares B-spline curve and surface fitting[J].Computer-Aided Design,2014,47:32-44
[17]Liu Xiaoyan,Deng Chongyang.Non-uniform cubic B-spline curve interpolation algorithm of GS-PIA[J].Journal of Hangzhou Dianzi University:Natural Sciences,2015,35(2):79-82(in Chinese)(刘晓艳,邓重阳.非均匀三次B样条曲线插值的GS-PIA算法[J].杭州电子科技大学学报:自然科学版,2015,35(2):79-82)
[18]Xu Zhong,Lu Quan,Zhang Kaiyuan,et al.Theory and applications of H-matrices[M].Beijing:Science Press,2013:36-342(in Chinese)(徐仲,陆全,张凯院,等.H-矩阵类的理论及应用[M].北京:科学出版社,2013:36-342)
[2]de Boor C.How does Agee’s smoothing method work?[OL].[2018-01-12].http://ftp.cs.wisc.edu/Approx/agee.pdf
[3]Qi Dongxu.Some notes on mathematical methods in computer aided geometric modeling[J].Journal of the Northern Industrial University,1991,3(1):1-8(in Chinese)(齐东旭.关于计算机辅助几何造型数学方法的若干注记[J].北方工业大学学报,1991,3(1):1-8)
[4]Lin H W,Wang G J,Dong C S.Constructing iterative non-uniform B-spline curve and surface to fit data points[J].Science in China Series:Information Sciences,2004,47(3):315-331
[5]Lin H W,Bao H J,Wang G J.Totally positive bases and progressive iteration approximation[J].Computers&Mathematics with Applications,2005,50(3/4):575-586
[6]Cheng F H,Fan F T,Lai S H,et al.Loop subdivision surface based progressive interpolation[J].Journal of Computer Science and Technology,2009,24(1):39-46
[7]Chen Z X,Luo X N,Tan L,et al.Progressive interpolation based on Catmull-Clark subdivision surfaces[J].Computer Graphics Forum,2008,27(7):1823-1827
[8]Chen J,Wang G J.Progressive iterative approximation for triangular Bézier surfaces[J].Computer-Aided Design,2011,43(8):889-895
[9]Lin H W,Maekawa T,Deng C Y.Survey on geometric iterative methods and their applications[J].Computer-Aided Design,2018,95:40-51
[10]Delgado J,Pe?a J M.Progressive iterative approximation and bases with the fastest convergence rates[J].Computer Aided Geometric Design,2007,24(1):10-18
[11]Lu L Z.Weighted progressive iteration approximation and convergence analysis[J].Computer Aided Geometric Design,2010,27(2):129-137
[12]Deng C Y,Ma W Y.Weighted progressive interpolation of Loop subdivision surfaces[J].Computer-Aided Design,2012,44(5):424-431
[13]Liu Xiaoyan,Deng Chongyang.Jacobi-PIA algorithm for non-uniform cubic B-spline curve interpolation[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(3):485-491(in Chinese)(刘晓艳,邓重阳.非均匀三次B样条曲线插值的Jacobi-PIA算法[J].计算机辅助设计与图形学学报,2015,27(3):485-491)
[14]Lin H W,Zhang Z Y.An extended iterative format for the progressive-iteration approximation[J].Computers&Graphics,2011,35(5):967-975
[15]Lin H W,Zhang Z Y.An efficient method for fitting large data sets using T-splines[J].SIAM Journal on Scientific Computing,2013,35(6):A3052-A3068
[16]Deng C Y,Lin H W.Progressive and iterative approximation for least squares B-spline curve and surface fitting[J].Computer-Aided Design,2014,47:32-44
[17]Liu Xiaoyan,Deng Chongyang.Non-uniform cubic B-spline curve interpolation algorithm of GS-PIA[J].Journal of Hangzhou Dianzi University:Natural Sciences,2015,35(2):79-82(in Chinese)(刘晓艳,邓重阳.非均匀三次B样条曲线插值的GS-PIA算法[J].杭州电子科技大学学报:自然科学版,2015,35(2):79-82)
[18]Xu Zhong,Lu Quan,Zhang Kaiyuan,et al.Theory and applications of H-matrices[M].Beijing:Science Press,2013:36-342(in Chinese)(徐仲,陆全,张凯院,等.H-矩阵类的理论及应用[M].北京:科学出版社,2013:36-342)