光滑函数实根计算的渐进显式公式  

Explicit formulae for progressively computing a real root of the smooth function

作　　者：祝平 陈小雕[1,2] 马维银 姜霓裳[3] ZHU Ping;CHEN Xiaodiao;MA Weiyin;JIANG Nichang(School of Computer,Hangzhou Dianzi University,Hangzhou 310018,China;Department of Mechanical Engineering,City University of Hong Kong,Hong Kong,China;School of Science,Hangzhou Dianzi University,Hangzhou 310018,China)

机构地区：[1]杭州电子科技大学计算机学院,浙江杭州310018 [2]香港城市大学机械工程学系,中国香港 [3]杭州电子科技大学理学院,浙江杭州310018

出　　处：《浙江大学学报（理学版）》2021年第2期143-150,共8页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(61972120)。

摘　　要：求根问题在计算机图形学、机器人技术、地磁导航等领域应用广泛。基于重新参数化方法(reparamaterization-basedmethod,RBM),给出了用于计算给定光滑函数在某区间内唯一实根的渐进式显式公式。给定光滑函数f(t),用有理多项式Ai(s)对曲线C(t)=(t,f(t))进行插值,得到重新参数化函数t=φ_(i)(s),使得A_(i)(s_(j))=C(φ_(i)(s_(j)))。提出了基于重新参数化函数φ_(i)(s)的显式公式用于渐进式逼近f(t)对应的实根,在n个函数计算的成本下,收敛阶可达到3·2^(n-2),其中n≥3。与类牛顿法相比,本文方法提高了计算稳定性,且收敛速度更快、计算效率更高。与裁剪法相比,本文方法不需要求解包围多项式,且可用于非多项式函数计算,计算效率更高。数值实例表明,每增加一个插值点,逼近阶可提高一倍,且可获得较传统裁剪法更高的计算效率。The issue of finding the roots of equations has wide applications in computer graphics,robotics,and geomagnetic navigation.Based on the reparameterization technique,this paper presents an explicit formula for computing the real root of a smooth function within a certain interval.Given a smooth function f(t),by using the rational polynomial A_(i)(s)to interpolate the curve C(t)=(t,f(t)),it deduces a reparameterization function t=φi(s)such that A_(i)(s_(j))=C(φ_(i)(s_(j))).This paper proposes an explicit formula based on the reparameterized functionφ_(i)(s)to progressively approximate the root of f(t),which can achieve the convergence order of 3·2^(n-2) at the cost of n functions,where n≥3.Compared with the Newton-like method,it improves the computational stability,and can achieve faster convergence rate and better efficiency.Compared with the clipping methods,it does not need to solve the bounding polynomial,and is applicable for solving non-polynomial functions.Numerical examples show that each time one more interpolation point is added,the approximation order will be doubled,hence much better computational efficiency than traditional clipping methods.

关 键 词：求根计算 重新参数化 裁剪方法 数值迭代法 收敛阶 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]