• 论文 • 上一篇    下一篇

基于Newton迭代法的最小二乘渐进迭代逼近

兰林, 朱春钢   

  1. 大连理工大学数学科学学院, 大连 116024
  • 收稿日期:2021-08-24 出版日期:2022-03-14 发布日期:2022-03-07
  • 通讯作者: 朱春钢,Email:cgzhu@dlut.edu.cn
  • 基金资助:
    国家自然科学基金(12071057,11671068)资助.

兰林, 朱春钢. 基于Newton迭代法的最小二乘渐进迭代逼近[J]. 数值计算与计算机应用, 2022, 43(1): 88-111.

Lan Lin, Zhu Chungang. LEAST SQUARE PROGRESSIVE ITERATIVE APPROXIMATION BASED ON NEWTON ITERATIVE METHOD[J]. Journal on Numerica Methods and Computer Applications, 2022, 43(1): 88-111.

LEAST SQUARE PROGRESSIVE ITERATIVE APPROXIMATION BASED ON NEWTON ITERATIVE METHOD

Lan Lin, Zhu Chungang   

  1. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
  • Received:2021-08-24 Online:2022-03-14 Published:2022-03-07
最小二乘渐进迭代逼近(LSPIA)是一种有效的大规模数据拟合方法.针对LSPIA的加速问题,基于Newton迭代法,本文提出曲线曲面的两类最小二乘渐进迭代逼近格式.首先构造一个以控制顶点为变量的多元函数,其Hessian矩阵为正定矩阵,多元函数存在极小值,且其极小值所对应的控制顶点与LSPIA的收敛结果一致.对多元函数极小值问题,采用Newton迭代法进行求解.然后对Newton迭代格式中的Hessian矩阵和调整向量分别采用奇异值分解法和共轭梯度法求解,从而给出两种LSPIA迭代格式,分别记为NLSPIA和INLSPIA.最后给出两种迭代格式收敛性的理论证明.数值实例验证了文中方法的有效性和可行性,也表明了在相同条件下,NLSPIA与INLSPIA的收敛速度和计算时间都优于经典LSPIA.
The least square progressive iterative approximation (LSPIA) is an efficient method for large-scale data fitting. To accelerate the convergence rate of LSPIA, we propose two kinds of LSPIA for curves and surfaces based on Newton iterative method. Firstly, we construct a multivariate function with control points as variables, whose Hessian matrix is a positive definite matrix. The control points corresponding to the minimal value of the multivariate function are consistent with the convergence results of LSPIA. Meanwhile, the Newton iterative method is applied to solve the minimal value of the multivariate function. Then we obtain two LSPIA iterative schemes by using singular value decomposition and the conjugate gradient method respectively to deal with the Hessian matrix and adjustment vectors, which are named NLSPIA and INLSPIA respectively. Finally, we also give the theoretical proof of the convergence of the proposed schemes. Numerical examples verify the effectiveness and feasibility of the proposed methods, and also show that the convergence rate and the calculation time of NLSPIA and INLSPIA are both better than those of the classical LSPIA under the same conditions.

MR(2010)主题分类: 

()
[1] 齐东旭, 田自贤, 张玉心, 冯家斌.曲线拟合的数值磨光方法[J].数学学报, 1975(03):173-184.
[2] de Boor C.How does Agee's smoothing method work?[R]Washington D C:Army Research Office, 1979.
[3] Lin Hongwei, Wang Guojin, Dong Chenshi.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.
[4] Lin Hongwei, Bao Hujun, Wang Guojin.Totally positive bases and progressive iteration approximation[J].Computers and Mathematics with Applications, 2005, 50(3):575-586.
[5] 史利民, 王仁宏.NURBS曲线曲面拟合数据点的迭代算法[J].数学研究与评论, 2006(04):735-743.
[6] Delgado J, Pea J M.Progressive iterative approximation and bases with the fastest convergence rates[J].Computer Aided Geometric Design, 2006, 24(1):10-18.
[7] 陈杰, 王国瑾, 金聪健.两类推广的渐近迭代逼近[J].自动化学报, 2012, 38(01):135-139.
[8] Lu Lizheng.Weighted progressive iteration approximation and convergence analysis[J].Computer Aided Geometric Design, 2009, 27(2):129-137.
[9] 张莉, 赵林, 檀结庆.带互异权值的渐进迭代逼近算法及其应用[J].浙江大学学报(理学版), 2017, 44(01):22-27.
[10] 刘晓艳, 邓重阳.非均匀三次B样条曲线插值的Jacobi-PIA算法[J].计算机辅助设计与图形学学报, 2015, 27(03):485-491.
[11] Lin Hongwei, Zhang Zhiyu.An extended iterative format for the progressive-iteration approximation[J].Computers&Graphics, 2011, 35(5):967-975.
[12] Deng Chongyang, Lin Hongwei.Progressive and iterative approximation for least squares B-spline curve and surface fitting[J].Computer Aided Design, 2014, 47:32-44.
[13] 蔺宏伟.几何迭代法及其应用综述[J].计算机辅助设计与图形学学报, 2015, 27(04):582-589.
[14] Lin Hongwei, Maekawa Takashi, Deng Chongyang.Survey on geometric iterative methods and their applications[J].Computer-Aided Design, 2018, 95:40-51.
[15] 王仁宏, 李崇君, 朱春钢.计算几何教程[M].北京:科学出版社, 2008.
[16] 邓少辉, 汪国昭.渐进迭代逼近方法的数值分析[J].计算机辅助设计与图形学学报, 2012, 24(07):879-884.
[17] Liu Chengzhi, Liu Zhongyun.Progressive iterative approximation with preconditioners[J].Mathematics, 2020, 8(9):1503.
[18] 陈景良, 陈向晖.特殊矩阵[M].北京:清华大学出版社, 2001.
[19] Lin Hongwei.Local progressive-iterative approximation format for blending curves and patches[J].Computer Aided Geometric Design, 2010, 27(4):322-339.
[20] Ando T.Totally positive matrices[J].Linear Algebra and Its Applications, 1987, 90:165-219.
[21] 朱春钢, 李彩云.数值逼近与计算几何[M].北京:高等出版社, 2020.
[22] 张宏伟, 金光日, 施吉林, 董波.计算机科学计算[M].北京:高等教育出版社, 2005.
[1] 金鑫, 汪韬. 两阶段Arrhenius方程参数优化算法[J]. 数值计算与计算机应用, 2022, 43(3): 329-342.
[2] 牛善洲, 刘宏, 朱赟, 喻高航, 马建华. 基于广义惩罚加权最小二乘的低剂量CT重建方法[J]. 数值计算与计算机应用, 2021, 42(3): 289-302.
[3] 陈世军, 卢民荣. 单变量矩阵方程子矩阵约束下牛顿-MCG算法[J]. 数值计算与计算机应用, 2020, 41(4): 306-314.
[4] 王丽. 三类新的求解广义最小二乘问题的预处理GAOR方法[J]. 数值计算与计算机应用, 2020, 41(4): 282-296.
[5] 徐正伟, 王皓, 胡兵, 张世全. 基于非线性最小二乘的Arrhenius方程参数估计[J]. 数值计算与计算机应用, 2019, 40(4): 279-290.
[6] 张文生, 庄源. 频率域声波方程全波形反演[J]. 数值计算与计算机应用, 2017, 38(3): 167-196.
[7] 张舰齐, 王丽琼, 左瑞亭. 区域气候数值模式预测误差的非线性预估及订正应用试验[J]. 数值计算与计算机应用, 2017, 38(1): 11-25.
[8] 乐航睿, 杨庆之. 求解正则化最小二乘问题的一个非精确交替方向乘子法[J]. 数值计算与计算机应用, 2016, 37(3): 223-232.
[9] 邓远北, 刘莹, 杨娟. 几种特殊循环矩阵的PROCRUSTES问题[J]. 数值计算与计算机应用, 2016, 37(1): 11-24.
[10] 张凯院, 宁倩芝. 实矩阵两类广义逆的迭代算法[J]. 数值计算与计算机应用, 2015, 36(2): 81-90.
[11] 张艳君, 赵金玲, 徐尔. 求解多集分裂可行问题的一种共轭梯度法[J]. 数值计算与计算机应用, 2013, 34(4): 249-256.
[12] 刘新, 张慧娟, 孙彬彬, 王艳超. 基于角点检测和奇异值分解的多重数字水印算法[J]. 数值计算与计算机应用, 2013, 34(4): 279-285.
[13] 张凯院, 宋卫红, 王娇. 一类广义Riccati矩阵方程对称解的双迭代算法[J]. 数值计算与计算机应用, 2013, 34(4): 286-294.
[14] 吴洋, 赵永华, 纪国良. 一类大规模稀疏矩阵特征问题求解的并行算法[J]. 数值计算与计算机应用, 2013, 34(2): 136-146.
[15] 张春敏,  杨月婷. 两种混合共轭梯度法的全局收敛性[J]. 数值计算与计算机应用, 2012, 33(2): 92-98.
阅读次数
全文


摘要