块三角矩阵指数的增量计算

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Incremental computation of block triangular matrix exponentials with
  application to option pricing》
---
作者：
Daniel Kressner, Robert Luce, Francesco Statti
---
最新提交年份：
2017
---
英文摘要：
  We study the problem of computing the matrix exponential of a block triangular matrix in a peculiar way: Block column by block column, from left to right. The need for such an evaluation scheme arises naturally in the context of option pricing in polynomial diffusion models. In this setting a discretization process produces a sequence of nested block triangular matrices, and their exponentials are to be computed at each stage, until a dynamically evaluated criterion allows to stop. Our algorithm is based on scaling and squaring. By carefully reusing certain intermediate quantities from one step to the next, we can efficiently compute such a sequence of matrix exponentials.
---
中文摘要：
我们以一种特殊的方式研究了块三角矩阵的矩阵指数的计算问题：从左到右逐块列计算。在多项式扩散模型中的期权定价背景下，这种评估方案的需要自然产生。在此设置中，离散化过程生成一系列嵌套块三角矩阵，并在每个阶段计算其指数，直到动态评估的标准允许停止。我们的算法基于缩放和平方。通过从一步到下一步仔细地重用某些中间量，我们可以有效地计算这样一系列矩阵指数。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Numerical Analysis        数值分析
分类描述：Numerical algorithms for problems in analysis and algebra, scientific computation
分析和代数问题的数值算法，科学计算
--
一级分类：Quantitative Finance        数量金融学
二级分类：Pricing of Securities        证券定价
分类描述：Valuation and hedging of financial securities, their derivatives, and structured products
金融证券及其衍生产品和结构化产品的估值和套期保值
--

---
PDF下载：
--> Incremental_computation_of_block_triangular_matrix_exponentials_with_application.pdf (274.03 KB)

2022-5-31 05:14:43 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：Exponentials Quantitative intermediate Exponential Computation

块三角矩阵指数的增量计算及其在期权定价中的应用*罗伯特·卢斯*弗朗西斯科·斯塔蒂*+2017年6月30日摘要我们以一种特殊的方式研究了块三角矩阵的矩阵指数计算问题：从左到右逐块列计算。在多项式微分模型中的期权定价背景下，这种评估方案的需要自然产生。在此设置中，离散化过程生成一系列嵌套块三角矩阵，并在每个阶段计算它们的分量，直到动态评估准则允许停止。我们的算法基于缩放和平方。通过在一个步骤到下一个步骤中小心地重用某些中间量，我们可以高效地计算这样一系列矩阵指数。关键词矩阵表达式、块三角矩阵、多项式微分模型、期权定价1引言我们研究了嵌套块三角矩阵序列的矩阵指数计算问题。为了给出预处理问题的公式，考虑块上三角r矩阵G，G，G。formGn的=G0,0G0,1··G0，nG1,1··G1，n。。。。。。Gn，n∈ Rdn×dn，（1）其中所有诊断块Gn，nare square。换句话说，矩阵giarisefromgi-1通过附加块列（并调整大小）。我们的目标是计算矩阵指数exp（G），exp（G），exp（G）。（2） 当然，可以使用标准技术单独计算每个指数（2）（参见【11】中的概述）。

然而，矩阵指数序列（2）继承了矩阵Gnin（1）的嵌套结构，即。，*\'Ecole Polytechnique F'ed'erale de Lausane，Station 8，1015 Lausane，Switzerland（{daniel.kressner，robert.luce，francesco.statti}@epfl.ch）+根据欧洲联盟第七框架计划（FP/2007-2013）/欧洲研究理事会第307465号拨款协议（ERC Grant Agreement n.307465-POLYTE）通过欧洲研究理事会支持的研究。exp（Gn-1） 是exp（Gn）的主要子矩阵。实际上，只需要计算exp（Gn）的last blockcolumn，本文的目标是解释如何以数字安全的方式实现这一点。在对角线块Gn、NAR的光谱分离的特殊情况下，Parlett方法[13]原则上产生了一个有效的计算方案：分别计算F0,0：=exp（G0,0）和F1,1：=exp（G1,1），然后exp（G）的缺失（1，2）块作为Sylvester方程G0,0X的唯一解X给出- XG1,1=F0,0G0,1- G0,1F1,1。以这种方式继续计算（2）所需的所有o f-对角线块可以从求解Sylvester方程中获得。然而，众所周知（见[8]第9章），只有当对角块的光谱被很好地分离时，Parlett方法才是数值安全的，因为所有涉及的Sylvester方程都是条件良好的。由于我们认为区块结构是固定的，因此施加此类条件将严重限制应用范围；我们下面讨论的应用程序肯定无法满足这一要求。指数增量计算的一类一般应用来自线性算子G：V的矩阵表示→ V受限于给定的有限维向量空间V的一系列嵌套的有限维子空间。更准确地说，我们从有限维子空间Vof V开始，以B为基础。

接着，向量空间Vis扩展到V 五、 ···  V通过生成嵌套基序列B B B ···.假设GVn Vn对于所有n=0，1，考虑G相对于Bn的矩阵表示的序列。由于碱基的嵌套性，GNI由Gn构建-通过添加列来表示G toBn的操作-因此，我们得到了一个矩阵序列，其结构如（1）所示。上述塞纳里奥的一个具体例子出现在计算金融领域，即基于多项式差异模型的期权定价；参见【6】。正如我们在第3节中更详细地解释的那样，在这种情况下，G是随机微分方程（SDE）的生成器，V是多变量多项式的嵌套子空间。一些定价技术需要计算某些条件矩，这些条件矩可以从矩阵指数中提取出来（2）。虽然增加n可以更好地近似期权价格，但获得所需精度所需的n值通常是未知的。自适应选择n的算法依赖于整个序列的增量计算（2）。块三角矩阵的指数也在其他情况下进行了研究。对于two-by-two-block三角矩阵，Dieci和Papini在[4]中研究了条件问题，并在[3]中讨论了使用Pad'eapproximants到指数函数的缩放参数的选择。在ma矩阵也是oblock-Toeplitz的情况下，文[2]提出了一种快速求幂算法。本文的其余部分组织如下。在第2节中，我们详细描述了增量计算块三角矩阵指数的算法，如（1）所示。

在第3节中，我们讨论了多项式微分模型，以及一些需要使用这种增量算法的定价技术。最后，数值结果在第4.2节增量缩放和平方中给出。由于共形分区块tr正则矩阵集形成一个代数，并且exp（Gn）是Gn中的多项式，因此矩阵exp（Gn）具有与Gn相同的块上三角结构，即exp（Gn）=exp（G0,0）* ··· *exp（G1,1）。。。。。。。。。*exp（Gn，n）∈ Rdn×dn。正如简介中所述，我们的目标是从左到右逐块列计算exp（Gn）block column。我们的算法基于缩放和平方方法，下面我们简要总结一下。2.1缩放和平方法概述缩放和平方法使用有理函数近似指数函数，通常包括三个步骤。用rk表示，m（z）=pk，m（z）qk，m（z）表示（k，m）-Pad'e对经验函数的逼近，这意味着分子是k次多项式，而表示符是m次多项式。这些Pad'e逼近非常接近原点，并且在第一步中，输入矩阵G将按2的幂进行缩放，因此k2-sGk足够小，可以保证精确的近似值rk，m（2-sG）≈ exp（2-sG）。第二步包括计算有理近似rk，m（2-最后，在第三步中，通过重复分析结果，即exp（G），获得exp（G）的近似值≈ rk，m（2-sG）s.标度参数s和近似度的不同选择，以及不同特征的产量方法。

这些参数的选择对于近似质量和计算效率至关重要，请参见【8，第10章】。在下文中，我们描述了允许使用缩放和平方对块三角形矩阵ix（1）的矩阵分量进行增量评估的技术。这些技术可用于实际基础缩放和平方方法的任何选择，通过参数s、k和m.2.2工具定义，用于指数增量计算在解释算法之前，我们首先介绍一些贯穿始终的符号。矩阵Gnfrom（1）可以写成GN=G0,0···G0，n-1G0，n。。。。。。。。。Gn公司-1，n-1Gn-1，nGn，n=:Gn公司-1gn0 Gn，n（3） 其中Gn-1.∈ Rdn公司-1×dn-1，Gn，n∈ Rbn×bn，因此gn∈ Rdn公司-10亿。设s为标度参数，r=pq为有理函数，在近似中使用（对于隐式，我们通常会忽略指数k和m）。我们用▄Gn：=2表示缩放材料ix-我们按照（3）对其进行分区。该算法的出发点在于使用缩放和平方方法计算指数exp（G）=exp（G0,0）的Pad'e近似值。然后，通过重用先前获得的每一步量，递增地计算matr ix指数（2）的序列。所以更一般地说，假设exp（Gn-1） 已通过使用平方和平方法进行近似。获得exp（Gn）的Pad'e近似值的三个主要计算步骤是（i）计算多项式p（▄Gn），q（▄Gn），（ii）计算p（▄Gn）-1q（~Gn）和（iii）重复对其进行方形化。

我们现在分别讨论这些步骤中的每一步，注意每次迭代中要保留的数量。2.2.1从p（~Gn）计算p（~Gn），q（~Gn）-1） ，q（▄Gn-1） 与（3）类似，我们从写Pn：=p（▄Gn）和Qn：=q（▄Gn）asPn开始=Pn编号-1pn0 Pn，n, Qn公司=Qn公司-1qn0 Qn，n.为了评估Pn，我们首先需要计算▄Gn的单项式，对于l=1，k，可写为s▄Gln=▄Gln-1毫升-1j=0Gjn-1▄gn▄Gl-j-1n，n  Gln，n#。用Xl表示：=Pl-1j=0Gjn-1▄gn▄Gl-j-1n，n▄Gln的上o f对角线块，那么我们有关系xl=▄Gn-1Xl码-1+▄gn▄Gl-1n，n，对于l=2，···，k，X：=▄gn，因此所有的单项式▄Gln，l=1，k、 可以计算inO（bn+dn-10亿+dn-10亿）。设p（z）=Pkl=0αlzl是r的分子多项式，那么我们得到了pn=Pn编号-1Pkl=0αlXlp（~Gn，n）, （4） 可在O（bn+dn）中组装-10亿），因为只需要计算最后一个块列。算法1总结了PNI的完整评估。算法1使用Pn评估Pn-1输入：Gn-1，Gn，n，Gn，Pn-1，Pad'e系数αl，l=0，···，k。输出：Pn。1： gn← 2.-sgn，Gn，n← 2.-sGn，n，~Gn-1.← 2.-新加坡元-12： X个← gn3：对于l=2，3，···，k do4：计算▄Gln，n5：Xl=▄Gn-1Xl码-1+▄gn▄Gl-1n，n6：结束7:X← 0dn-1×bn8：计算Pn的对角块：Pkl=0αlXl。9： 计算p（▄Gn，n）=Pkl=0αl▄Gln，n10：在（4）中组装PNA类似地，从Qn计算qnf-1、再次使用ma trices Xl。2.2.2评估Q-1npn用矩阵Pn，Qnat，我们现在需要计算有理逼近Q-1nPn。我们假设Qnis条件良好，特别是非奇异，这是通过选择标度参数和Pad'e近似得到的，参见，例如，[9]。我们关注计算成本。

为了简单起见，我们引入了符号▄Fn=F0,0·······F0，n。。。。。。Fn，n:= Q-1nPn，Fn=F0,0···F0，n。。。。。。Fn，n:=~Fsn，我们看到▄Fn=Q-1nPn=Q-1n-1.-Q-1n-1qnQ-1n，n0 Q-1n，nPn编号-1pn0 Pn，n=Fn-1季度-1n-1（pn- qnQ公司-1n，nPn，n）0 Q-1n，nPn，n.（5） 求解线性系统Q-1n，nPn，nw我们计算一个LU分解，对Qn，n进行部分激励，需要O（bn）运算。此LU分解已保存以备将来使用，因此我们可以假设，我们已经从以前的计算中获得了所有直径块的LU分解：∏lQl，l=LlUl，l=0，n- 1.（6）此处，∏l∈ Rbl×bl，l=0，n- 1重新排列矩阵；Ll公司∈ Rbl×bl，l=0，n- 1是下正则矩阵和Ul∈ Rbl×bl，l=0，n- 1是上三角矩阵。设置Yn：=pn- qnQ公司-1n，nPn，n∈ Rdn公司-1×bn，并对其进行asYn分区=Y0，n。。。Yn公司-1，n.然后我们计算Q-1n-1Ynby块向后替换，使用对角块的分解。此计算的操作总数为henceO（dn-10亿+dn-10亿），因此计算▄fn的操作数为O（bn+dn-10亿+dn-10亿）。算法2描述了计算▄Fn的完整过程。2.2.3平方相位的计算值为▄Fn，我们将其写为▄Fn=Fn-1fnfn，n,我们现在需要计算该矩阵的s重复平方，即▄Fln=▄Fln-1毫升-1j=0Fl-1+jn-1▄fn▄Fjn，n▄Fln，n#，l=1，s、 （7）算法2▄Fn=Q的评估-1NPN输入：Qn、pn和数量（6）输出：▄Fn=Q-Qn的np和LU分解，n.1：计算∏nQn，n=lnunan，并保留它以备将来使用（6）2：计算 Fn，n：=Q-1n，nPn，n3：Yn=pn- qnQ公司-1n、nPn、n4：▄Fn-1，n=U-1n-1升-1n-1∏n-1年-1，n5：对于l=n- 2，n-3，···，0 do6：~Fl，n=U-1升-1l∏l（Yl，n-Pn编号-1j=l+1Ql，jFj，n）7：结束8：组装（5）中的FNA，使Fn=Fsn。设置Zl：=Pl-1j=0Fl-1+jn-1▄fj▄Fjn，n，我们有循环ZL=▄Fl-1n-1兹尔-1+Zl-1Fl-1n，n，Z：=▄fn。

因此，如果我们存储了计算Fn得到的中间平方-1，即▄Fln-1，l=1，s（8）我们可以计算所有的量Zl，l=1，O中的s（dn-10亿+dn-10亿），因此计算Fn（和▄Fn的中间平方）的总成本为O（dn-10亿+dn-10亿+10亿）。再次，我们总结了以下算法中的平方阶段。算法3 Fn的评估=▄FsnInput：▄Fn-1、~fn、~fn、n、数量（8）。输出：fn和更新的中间体。1： Z←fn2：对于l=1，2，···，s do3：计算▄Fln，n4：Zl=▄Fl-1n-1兹尔-1+Zl-1Fl-1n，n5：在（7）中装配▄Flnas，并将其保存6:end FOR 7:Fn←Fsn2.3总体算法使用上一节中的技术，我们现在对总体算法进行简要描述。我们假设方程式（6）和（8）中列出的量存储在内存中，空间要求为O（dn-1） 。鉴于此，我们假设Fn-1并计算了上述中间量。算法4描述了计算Fn和更新中间产物的总体过程；我们继续使用（3）中介绍的符号。如前一节所述，算法4中每个步骤的操作数为O（dn-10亿+dn-10亿+10亿），使用第2.2节开头的符号。

如果只是从头开始计算fn，而不使用中间物，则进行平方和平方运算的操作数将为O（（dn-10亿多欧元）。算法4 Fn的计算≈ exp（Gn），使用Fn-1输入：方框列gn、对角方框gn、n、数量（6）和（8）。输出：Fn和更新的中间体。1： 出口Pn-1使用算法1，并类似地形成Qn2：计算Fn使用算法23：在dn-1.>> bn，后一复杂度界中的主导项是dn-1，不在算法4的复杂度范围内。为了解决我们原来的问题，计算序列exp（G），exp（G），exp（G），我们重复使用算法4；算法5显示了生成的过程。算法5 exp（G），exp（G）。输入：Pad'e近似参数k、m和sOutput：F≈ exp（G），F≈ exp（G）。1： 计算融合缩放和平方，存储算法42的中间产物：对于n=1，2。do3：从Fn计算Fn-1使用算法44：如果满足终止条件，则5:return6:end if7:end for我们现在得出算法5中所用操作数的复杂性界限。为便于记法，我们考虑所有对角块大小相等的情况，即bk≡ b∈ N、 因此，dk=（k+1）b。在迭代k时，算法4中的运算量s因此为O（kb）。假设算法5中使用的ter mina TIONCriteria影响在计算ofFn后停止该过程。