《仿射算法研究综述》3900字_第1页
《仿射算法研究综述》3900字_第2页
《仿射算法研究综述》3900字_第3页
《仿射算法研究综述》3900字_第4页
《仿射算法研究综述》3900字_第5页
已阅读5页,还剩9页未读, 继续免费阅读

下载本文档

kok电子竞技权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

kok电子竞技:文档简介

仿射算法研究综述目录TOC\o"1-2"\h\u28804仿射算法研究综述 1272471仿射算法 1210611.1仿射算法基本概念 1271861.2非仿射算法基本操作 39151.3误差的传播 8260202区间矩阵的仿射运算 9327042.1区间矩阵的基本运算 9204032.2仿射形式逆矩阵 9101052.3矩阵的指数运算 121仿射算法1.1仿射算法基本概念(1)区间的另一种表达式区间也可以用“中点和半径”来表示。假设存在一个区间,由式(2.2)到式(2.4)可以推出区间记为:(1)令,则区间可以表示为:(2)仿射算法由上一章可以得知,区间算法虽然可以求解不确定条件下的边界解,但由于其局限性,区间算法可能会提供一个太宽的边界,即求解出的最值点太保守,可能会包含一些真值永远达不到的区域。为了克服上述过于保守的问题,对式(1)进行改进,对每一个量都分配一个新的系数,并且当两个或者两个以上的量同时出现了不确定性,就会自动地分配同样的系数。添加一个新的噪声系数,且,则新的区间数可以表示成:(2)这种通过添加新的噪声系数的方式即为“仿射方式”,噪声系数代表着对于总体不确定量的独立组成。继续以章节2.1.3的例子为基。渲悼梢杂檬(1)中的仿射形式表示出来:,由于,存在一定的关联,所以两个区间值具有相同的噪声符号,则区间值的仿射形式可以表示为:,则。通过仿射算法改进,消除了区间算法存在的过度估计问题。在噪声模拟等实际环境中,可能会同时存在大量的变化对原始参数产生影响。包含各种不确定项的量的一般仿射形式可以表示为:(3.3)每一个表示一个不确定的独立组成,表示要素的量级。所以我们能很容易地从式(3.3)中得到的上界为,下界为。(3)仿射算法基本操作假设输入的仿射形式为:,之间的操作主要可以分为仿射操作和非仿射操作。仿射操作是对输入的仿射形式进行直接操作,得到的结果不包含二次项的。比如,,和在时的仿射操作分别可以表示为:(3.4)而非仿射操作就是接下来所要研究的内容。1.2非仿射算法基本操作非仿射操作如乘法、除法、倒数、平方根等运算方式会在结果中产生二次项的,在计算过程中需要做的是将新方程转换成线性仿射形式,而转换方式是采取添加新的噪声系数来替换其计算结果中的二次项。(1)乘法运算假设存在两个区间的仿射形式为:和,则,相乘可以得到:(3.5)由结果可知,产生了新的二次项,添加一个新的噪声符号来取代新产生的二次项,可以表示为:(3.6)这种方法虽然也能求出所需的结果的边界,但也会引入新的误差:添加新的噪声符号跳过了它与其他符号的相关性,会出现同区间算法相同的过度估计的问题,同时计算出来的新系数也会计算出最大量级的,同样无法避免过度估计的现象。令,则式(3.5)中的可以优化为:(3.7)在仿射模型中,由于任何区间结果的上界与下界都是关于中心值对称的,因此如果十分趋近区间真实的上界,到上界的距离远远小于到下界的距离,从而导致对前一个点过度估计,如图1所示。图1仿射形式乘法的过度估计另一个问题是在计算过程中添加了一个新的噪声符号。随着计算的复杂程度的增大,噪声符号的数目也会随之增加,反之,计算效率也就会降低。假设存在两个受两个不确定性影响的区间,其仿射形式可以表示为:和,则他们的乘积可以表示为:(3.8)结果中的二次项系数用新的噪声系数替代,则,相应的上下界区间是。然而,更精确的分析表明,二次项系数的确切范围在,因此,的真值区间应该为。由此可见,仿射近似法的相对精度为:这与图1中过高估计的情况相对应,得到的标称值更接近真实的上限,因此在这一侧引入了误差。(2)除法运算除法相对于乘法更为复杂,它可以转换为一个区间乘以另一个区间的倒数的形式:(3.9)为了更好地反求一个实际上是非仿射操作的仿射形式,我们借鉴了“极值仿射逼近”的结论:定理1:设为区间上定义的有界二次可微函数,并且其二阶导数在区间内不变号。令在区间内是其极值仿射逼近。因此:系数表示,直线的斜率只与点和有关在端点范围内,当时,会出现最大绝对误差独立项表示,最大绝对误差为由定理1可知,求近似函数的问题可以转换为求拟合系数的最优解:(10)这就是所谓的“切比雪夫近似”算法。另外一种方法是“最小范围近似法”,它在计算区间倒数的编码中与之相似,但更容易。如图2所示:假设存在,在最值处的切线和与之斜率相同的穿过另外一个最值点,组成和(图2.4中的阴影部分)。虚线代表在区间范围内的中点。图2最小范围近似法注意该区间内不能包含0,对此进行分类讨论。假设区间值全部为正数,则直线的斜率是在时的导数,即。经过端点的虚线可以表示为:对上式进行求解得:(11)将新的噪声符号赋值给新的参数,结果函数表示为:(12)式中表示新的标称值,表示初始噪声符号的系数,用新的符号和组成式(10)计算出的新符号系数。则仿射除法可以表示为:因此,除法是在乘法的基础上进行计算的,但是比乘法更复杂一些,需要先求出区间的倒数形式,再将两者相乘,而这两个过程中都会产生新的噪声符号。另一种情况假设区间内的值全部为负数时,需要进行的操作是相同的,这里就不作重复叙述。(3)指数运算根据定理1中的“切比雪夫近似算法”来计算区间在内的指数算法。即近似求解:(13)如图3.3所示:同时经过端点和的直线1,在区间中有且只有一点的切线斜率与直线1斜率相等。图中阴影部分包含的所有可能值,也就是最小近似范围。阴影部分中间的虚线:与直线1平行,由此,可以求得虚线的斜率为:图3.3切比雪夫近似算法求指数形式两端点之间的最大误差出现在图中所示点,出现了异号,这一点的值为:同样,最大误差的大小被赋予一个新的噪声符号,包括“最坏情况”。参数表示:最终,对所有线性近似值进行筛。钪湛梢员硎疚:(14)表示新的标称值,表示初始噪声符号的系数,表示最大误差。(4)对数运算用“最小范围近似法”求在上的区间的对数运算,比如,估算函,近似参数为:(15)大多数单调函数都可以用上述两种近似方法估算。值得注意的是,仿射算法和近似法不适用于周期函数,如正弦函数。综上,仿射操作可以直接产生仿射形式,不会生成新的二次项;而非仿射操作更为复杂,会产生新的二次项,所以需要先将它转变为仿射形式,将输入的线性组合近似任何非线性函数,仿射和非仿射操作在精度和效率上都比区间方法有很大的提高,结合其他数值技术(如区间分割技术)有望减少过度估计产生的误差。1.3误差的传播上面已经说过,在非仿射算法中,每次单独的操作都会产生附加的噪声符号。在需要做大量乘法的情况下,随机变量的数量会不断增长,这在计算时间上是非常低效的。这里通过给现有的不确定量分配额外的二次项,可以表示为:(16)这种方法没有生成新的不确定量,并且限定了的真实范围,但是,由于没有完整的对其进行严谨的数学理论公式推导,所以缺乏一定的严谨性,并不能达到最佳结果分布。2区间矩阵的仿射运算2.1区间矩阵的基本运算由式(2.6)和(2.7)可以得知,也可以用“中点和半径”的方法表示为:(17)添加一个新的系数给变量进行赋值,则区间矩阵的仿射形式可以表示为:(18)假设存在两个区间矩阵和,其仿射形式可以表示为:由式(3.4)和(3.7)可以得知,区间矩阵的基本运算可以表示为:(19)遗憾的是,由于切比雪夫法和最小范围近似法只适用于标量的求倒和指数运算,不适用矩阵的相关运算。2.2仿射形式逆矩阵区间矩阵的逆矩阵可以表示为:(20)除了标称值外所有的变量区间都包含了随机系数,如果将全部带入运算,计算难度之大,耗费时间精力之多,显然都是不现实的,因此我们必须采取更适合的计算方式来解决这个问题。当计算两个区间矩阵和的逆矩阵,其中一个矩阵可逆时,可以表述为:假设是一个阶可逆区间矩阵,和是维的任意向量,则有下面关系式:(21)其中表示和的输出结果,且。不难发现就是的倒数形式。这个公式仅被应用在秩时。为了快速地得到相应结论,这里假设区间矩阵只包含一个随机系数:,并且矩阵满足秩为1,则有下列关系式:(22)是新的标称值,是的新系数,当且仅当时,秩为。接下来,考虑在式(20)中的标准表达形式,当阶区间矩阵随着任意符号的变化而变化,并且每一个系数矩阵都以阶次排序。为了满足式(21)中对秩的要求,首先要把每个系数矩阵分解为秩的形式:(23)假设存在:(24)则由式(22)可以逐步推导出:(25)其中可以由“误差的传播”方法中的式(16)得出:如此反复,则式(23)矩阵中的第一行可以表示为:(26)两个系数和都可以用式(16)的方法得出:对上述方法作一般性归纳:假设存在元素,下标表示其位置是在矩阵的第行,第列,为前这一行所有噪声符号的和,因此:(27)最后,的求逆计算为:(28)可由式(27)得出。在这种反复运算的过程中,虽然计算步骤繁多,计算效率不高,不适用于大规模矩阵计算,但其优点是矩阵的区间操作不会产生新的随机系数。另外一种方法叫做泰勒扩张法,两个矩阵之和的逆矩阵可以表示为:(29)结合式(20)可得:(3.30)将方程展开为只有三项的泰勒展开式,所有的高阶项都近似为一个新的噪声符号。通过反复求解法得出的式(27)和泰勒展开近似法得出的式(3.30)都得出了精确的数字结果,并且都成功地将区间矩阵转化为相应的矩阵形式。反复求解的方法必须满足区间矩阵秩为1的条件,如果不能满足,就必须对矩阵进行分解。前者在求解小规模矩阵的问题时能更精确也更高效,但如果矩阵较复杂,更适合用泰勒展开法,求解速度更快,效率更高。2.3矩阵的指数运算区间矩阵的指数运算同样可以用泰勒展开近似求解,两个矩阵之和的指数运算的泰勒展开形式可以表示为:(3.31)其中为与A,B相同维度的单位矩阵。由上式不难看出,矩阵的指数运算可以简化为矩阵求和的乘法运算。假设存在区间矩阵其指数运算可以表示为:(3.32)根据式(16)可以求得:(3.33)可以近似的得到仿射形式:(3.34)其中,标称矩阵:系数矩阵:在进行矩阵的指数运算时,可以近似为:(3.35)据此推出:,令,则:(3.36)其中:包括矩阵求逆运算,可以表示为:其中:本文只介绍了泰勒展开法求指数运算,另外还有如双线性法和Pade逼近法等都比泰勒级数展开法更加精确和高效,但应用性不高,因为它们只能在特定条件下使用,比如,矩阵的形式必须是小量级。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

kok电子竞技:最新文档

评论

0/150

提交评论