中心形式的区间自动微分

中心形式的区间自动微分中心形式的区间自动微分第39卷第3期2011年6月浙江工业大学JOURNALOFZHEJIANGUNIVERSITYOFTECHNOLOGYVo1.39No.3Jun.2011中心形式的区间自动微分何苹,寿华好,缪永伟.(1_浙江工业大学理学院,浙江杭州310023;2.浙江工业大学计算机科学与技术学院,浙江杭州310023)摘要:自动微分是用于计算多变量函数的导数和偏导数的一种微分技术,在给定一个多变量光滑函数值的程序代码后,可以很容易地利用自动微分来实现有关导数和偏导数的精确计算.中心形式的区间算术是一种估计多项式函数取值范围的有效方法.文章将自动微分技术与中心形式的区间算术相结合应用到计算机图形学领域隐式函数曲线绘制的细分算法中,并与以往的几种隐式曲线绘制方法作比较和分析,实验数据表明中心形式的区间自动微分在绘制隐式曲线方面更精确.关键词:自动微分;中心形式;区间算术中图分类号:TP391.41文献标识码:A文章编号:1006—4303(2011)03—0347—04CentredformintervalautomaticdifferentiationHEPing,SHOUHua—hao,MIAOYong—wei(1.CollegeofScience,ZheiiangUniversityofTechnology,Hangzhou310023,China;2.CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023,China)Abstract:Automaticdifferentiationisatechniquetoevaluatethederivativesofafunctiondefinedbyacomputerprogram.Giventheprogramcodeofamultivariatesmoothfunction,wecaneasilyuseautomaticdifferentiationtocalculateitsderivativeandpartia1derivativeaccurately.Thecentredformintervalarithmeticisaneffectivemethodtoestimatetherangeofapolynomialfunction.Automaticdifferentiationtechniqueandcentredformintervalarithmeticarecombinedandappliedtothesubdivisionbasedimplicitcurveplottingalgorithminthispaper.AcomparisonofthisnewmethodwithseveralothermethodsisconductedwhichshowsthatthecentredformintervalautomaticdifferentiationiSmoreprecise.Keywords:automaticdifferentiation;centredform;intervalarithmetic自动微分是一种计算技术,理论上可以计算任意变量任意阶的导数和偏导数,并且非常容易用计算机编程实现.利用自动微分的易编程,高效率及高计算精度等特点来实现计算机图形学里的隐式曲线绘制,既可以降低算法的时间复杂性,又能提高图形绘制的质量[1].中心形式的区间算术是一种估计多项式函数取值范围的有效方法,在估计多项式的界时用中心形式的区间算术比通常的区间算术要更为精确].绘制隐式曲线的细分算法中最关键一步是估计二元函数在矩形区域内的取值范围,将自动微分和中心形式的区间算术相结合,可以利用计算机程序代码更为高效,精确地估计出泰勒展开式余项收稿日期:2010—01—12基金项目:国家自然科学基金资助项目(61070126,61070135);浙江省自然科学基金资助项目(Y1100837)作者简介:何苹(1976一),女,浙江杭州人,硕士研究生,研究方向为计算机辅助几何与图形学,E-mail:hping@126.com.通信作者寿华好教授,E-mail:shh@ziut.edu.cn.浙江工业大学第39卷中偏导数取值范围,这更有利于提高隐式曲线的绘制质量.这里提出了一种新的自动微分技术——中心形式的区间自动微分,并结合泰勒展开法与其他的一些绘制隐式曲线方法(自然区间法,泰勒展开法,区间自动微分+泰勒展开法)对绘制曲线的效果与效率进行比较分析,以揭示中心形式的区间自动微分在隐式曲线绘制中的优势.1自动微分自动微分方法(AD)通过分析原程序对象的数据相关性,是一系列基于链式求导法则的代码转换技术,通过各种预编译手段,可以把一个函数值程序代码转换成对应的计算微分的程序代码[3].自动微分实现的基本出发点是:一个数据相对独立的程序对象(模式,过程,程序段,数值语句乃至数值表达式),无论多么复杂,总可以分解为一系列有限数目的基本函数(如sin,exp,log)和基本运算操作(加,减,乘,除,乘方)的有序复合;对所有这些基本函数及基本运算操作,重复使用链式求导法则,将得到的中间结果自上而下地做正向积分就可以建立起对应的切线性模式,而自下而上地做反向积分就可以建立起对应的伴随模式?4].对于一个给定的函数,首先将其分解为若干个基本操作的组合,每个基本操作中至多有2个操作数,然后再通过对这些基本操作进行求导,从而得出目标函数的梯度.如对于函数Y—COSX1z2+sinx}(1)其梯度计算过程可表示如下,首先进行运算分解,令z3=f3一z1z2z=一?(2)z5一^一z}一6:f6=sinxY=z7一f7Iz4+z6根据式(2)函数组合,y对于z的偏导数利用链式法则可得到ay一碧罄誓+罄afs3x3x3x3x3x?a14az31.651,式中:挚可利用简单求导法则得到.例如:Z.,7一z+z,一一1,:一inz.,a3240X60Z38J:a一一COs一2z1dXtd.T5032'1这样,利用简单求导规则和链式法则即可求得函数的导数.以上讨论的是单值函数,计算的一阶导数是函数的梯度向量.对于多值函数,用同样的方法可计算它的Jacobia矩阵.在AD的实现过程中,通常是先记录目标函数j,=厂()的执行过程,再按照上述过程进行目标函数的梯度信息计算[5].所以自动微分可以实现任意变量任意阶导数和偏导数值的计算,使用切线性模式计算雅可比矩阵一向量乘积的计算精度较高;而使用伴随模式在计算函数的梯度时具有理想的计算代价[6].当自变量个数较大时,自动微分所需的计算量比通常方法所需的计算量小很多,可以提高科学计算的效率.与符号微分,差分近似等微分方法相比,自动微分具有代码简练,计算精度高,投人人力少及适用范围广等优点,在科学计算,工程计算及其应用领域中有着广泛的应用口].2中心形式的区间算术和区间自动微分设一个定义在区域[兰,]×Ey,习上的二元多项式函数f(x,),其表达式可写为f(x,)一??.zyJ,i=0J=0(z,)?[,]×Ey,]设星一zo+z1,,一Y.+Yl,分别是区间[z,×[j,,_]的仿射形式,这里和e分别为噪声元,它们的值是未知的,但假定只在[一1,1]范围内变动,其中z+一XY+歹一X—3g.一,Y.一,z一彳>o,一Yl一?>0所谓的中心形式是将这个二元多项式函数f(x,)通过变量代换一+(兰+)/2,Y=+(+)/2,把坐标原点平移到该区域[z,]×Ey,_]的中心而得到,这里和是新的坐标变量.中心形式的区间算术(Intervalarithmeticon第3期何苹,等:中心形式的区间自动微分thecenteredform,IAC)是将区间算术和中心形式有效地结合在一起,是一种估计多项式函数取值范围的有效方法.在估计多项式界的时候中心形式的区间算术比的仿射算术(Affinearithmetic,AA)要精确而且高效[7].而在一般情况下,标准仿射算术比通常的区间算术要精确,所以我们可以得到中心形式的区间算术要比通常的区间算术更精确且高效.一般地,对于一个二元多项式函数f(x,),在对其泰勒展开的基础上,可以运用以上所述的自动微分方法在计算函数值的同时把偏导数值以及偏导数的界同时计算出来.这里,在利用自动微分技术计算偏导数的界的时候,只要在原来变量z和Y的地方现在分别换成区间[,]和[,],那么原来自动微分过程中的数值运算就变成了区间运算,原来的计算结果即偏导数的值就变成了偏导数的界.这种传统自动微分技术的改进我们称它为区间自动微分技术.在区间自动微分技术的运用过程中,我们做了一些实验发现其区间运算的结果往往跟所使用的区间形式有关,于是就想到了中心形式的区间算术.因为使用中心形式的区间算术的时候,当每次细分后所考虑的区域改变成更小的子区域时,中心形式都一些额外的工作量,但是使得估计更为精确.所以考虑用中心形式的区间算术来代替通常的区间算术做区间自动微分,简称中心形式的区间自动微分.3中心形式的区间自动微分的应用计算机图形学中隐式曲线的绘制并不容易,常用的方法有基于细分的方法.隐式曲线绘制的细分算法中最关键的一步是估计函数f(x,)在区域[z,_]×[,_]上的界[厂,-],不同的估计方法就绘制的效果和绘制的效率而言有差异.一般情况下估计越精确,则绘制效果越好,而要使估计更精确,往往需要更大的计算量,从而会降低算法的效率.显然,效果和效率是一对矛盾.在估计二元函数界的时候由于中心形式的区间算术比通常的区间算术要精确,所以现在我们将中心形式的区间自动微分跟泰勒展开法相结合应用到隐式曲线的绘制中,与以往的常用方法相比图形的质量得到了更进一步的提高.以函数f(x,)一一134-32x一288x4-512z.一256x4-64y一112y4-256xy一256x.Y为例,得到的实验结果见表1和图1—4.该实例取材于必须根据新的子区域进行及时更新,这样虽然需要文献[8].表1各种方法的比较Table1Comparisonofvariousmethods1.O0.8暑0.6半0.4O_2000.20.40.60.81.0长度/cm图1自然区间方法绘制的曲线Fig.1Thecurvedrawnbynaturalrangemethod图2手动零阶泰勒展开法绘制的曲线Fig.2Thecurvedrawnbyorder0Taylormethod浙江工业大学第39卷图3区间自动微分+零阶泰勒展开法绘制的曲线Fig.3Thecurvedrawnbyintervalautomaticdifferentiation+order0Taylormethod图4中心形式区间自动微分+零阶泰勒展开法绘制的曲线Fig.4Thecurvedrawnbycentredformintervalautomaticdifferentiation+order0Taylormethod因为同种方法的零阶和,阶泰勒展开对曲线绘制的效果区分不是很大,为使以上几种方法绘制的图形效果对比明显,现只展示自然区间法,手动泰勒零阶展开法,区间自动微分+零阶泰勒展开法以及中心形式区间自动微分+零阶泰勒展开法4种情况绘制的曲线图,其他3种情况的图形略.从实验结果对比上可以看出,运用中心形式的区间自动微分方法的优势:(1)cPu(CPUTimeused):从CPU的运行时间来看,用自然区间方法显然不可行,与泰勒展开法相比,用区间自动微分+泰勒展开法和中心形式的区间自动微分+泰勒展开法要稍短一些.(2)SUB(Numberofsubdivisions):即细分的次数.好的方法细分的次数少,这便于节约时间和空间,同时还表明算法的收敛速度更快,很明显,中心形式区间自动微分+泰勒展开法在这方面表现最好.(3)PIX(Numberofpixels):即像素数量.像素数量越少,绘制的图形质量越好;反之像素数量越多,绘制的图形质量越差.从这个指标来看也是中心形式区间自动微分+泰勒展开法表现最好.(4)AREA(Percentageofareaclassified):即已探明不包含隐式曲线的空白区域面积所占有的百分比.占有百分比越大的图像质量越好,应用中心形式区间自动微分+泰勒展开法得到的图像质量参数明显较其他3种方法更优.4结论将中心形式区间自动微分与泰勒展开相结合应用到隐式曲线绘制的细分算法中,从效率(CPU占用时间)上来看也略占优势,而且图形的质量有了更进一步提高.一般地,用自然区间法绘制隐式曲线通常得不到满意的图形,而当隐式曲线的函数表达式比较复杂时用手动泰勒展开法绘制隐式曲线根本不可行.在计算机图形学领域里,经常需要绘制任意复杂且高质量的隐式曲线,用中心形式的区间自动微分法来绘制隐式曲线就具有了突出的优势.自动微分在计算机图形学领域大有用武之地,理论上讲任何用到导数的地方都可以用自动微分来完成.中心形式的区间自动微分对区间自动微分技术做了新的改进,这里将中心形式的区间算法和自动微分联系在一起,并把它应用于计算机图形学领域隐式曲线绘制中,它在计算机图形学中的其他应用,值得进一步探索和研究.参考文献:[1]寿华好,何苹,缪永伟.自动微分在隐式曲线绘制中的应用[J].计算机工程与应用,2010,46(1):150-154.[23寿华好.基于场细分曲线曲面绘制算法的研究[D].杭州:浙江大学,2004.r3]BARTHOLOMEW—BIGGSMC,BROWNS,CHRISTIAN—SONB,eta1.Automaticdifferentiationofalgorithms[J].JournalofComputationalandAppliedMathematics,2000,124(1/2):171-190.[4]GRIEWANK.Onautomaticdifferentiation[C_//IRIM,TANABLEK.MathematicalProgramming:RecentDevdopmentsandApplica—tions.Amsterdam:KIuwerAcademicPublishers,1989:83—108.[5]潘雷,谷良贤,龚春林.改进自动微分方法及其在飞行器气动外形优化中的应用口].西北工业大学,2007,25(3):398-401.E6]程强,张海斌,王斌.自动微分的原理和方法[J].计算科学,2009,31(1):1—22.r7]SHOUH,LINH,RMARTIN,eta1.Modifiedaffinearith—meticismoreaccuratethancenteredintervalarithmeticoraf—finearithmetic[J].LectureNotesinComputerScience,2003,2768:355—365.r8]VOICULESCUI.Implicitfunctionalgebrainset-theoreticmodel—ing[D].Bath:PhDThesis,UniversityofBath,2001.1-9]陈晓宇,程强,宋金帅,等.自动微分方法在XIAMEN软件优化中的应用[J].数值计算与计算机应用,2009,30(1):21—29.(责任编辑:刘岩)