科列斯基分解
此条目的引用需要进行清理,使其符合格式。 (2017年8月30日) |
线性代数中,科列斯基分解(英语:Cholesky decomposition 或 Cholesky factorization)是指将一个正定的埃尔米特矩阵分解成一个下三角矩阵与其共轭转置之乘积。这种分解方式在提高代数运算效率、蒙特卡罗方法等场合中十分有用。实数矩阵的科列斯基分解由安德烈-路易·科列斯基最先发明。实际应用中,科列斯基分解在求解线性方程组中的效率约两倍于LU分解。[1]
描述
对正定埃尔米特矩阵 进行科列斯基分解,即求矩阵 使下式成立
其中, 是一个下三角矩阵且所有对角元素均为正实数, 表示 的共轭转置。每一个正定埃尔米特矩阵都有一个唯一的科列斯基分解。[2]
当矩阵 是一个半正定的埃尔米特矩阵,若允许 的对角线元素为零,则 也存在上述形式的分解。[3]
当 为实数矩阵,则 也为实数矩阵且科列斯基分解可改写成 。[4]
当 是正定矩阵时,科列斯基分解是唯一的,即只存在一个对角元素均严格大于零的下三角矩阵,使 成立。然而,当 是半正定时,分解则不一定是唯一的。
定理的逆命题自然成立:对于某些可逆矩阵 (下三角矩阵或其他矩阵),如果 可被写成 ,则 是一个正定的埃尔米特矩阵。
LDL分解
经典科列斯基分解的一个变形是LDL分解,即
其中, 是一个单位下三角矩阵, 是一个对角矩阵。
该分解与经典科列斯基分解犹有关系,如下:
或者,由于 的对角元素必须为 ,且 与 都是下三角矩阵,故如果已知经典科列斯基分解 ,则 形式可依下式求出,设S是包含 的对角元素的对角矩阵,
LDL变形如果得以有效执行,构造及使用时所需求的空间及计算的复杂性与经典科列斯基分解是相同的,但是可避免提取平方根。[5]某些不存在科列斯基分解的不定矩阵,也可以执行LDL分解,此时矩阵 中会出现负数元素。因此人们更倾向于使用LDL分解。对于实数矩阵,该种分解的形式可被改写成
此形式通常称为LDLT分解(或LDLT分解)。它与实对称矩阵的特征分解密切相关,因为对于实对称矩阵,存在特征分解 。
实例
以下乃一个实对称矩阵的科列斯基分解︰
以下乃其LDLT分解︰
应用
科列斯基分解主要被用于线性方程组 的求解。如果A是对称正定的,我们可以先求出 ,随后借向后替换法对y求解 ,再以向前替换法对x求解 即得最终解。
另一种可避免在计算 时需要解平方根的方法就是计算 ,然后对y求解 ,最后求解
对于可以被改写成对称矩阵的线性方程组,科列斯基分解及其LDL变形是一个较高效率及较高数值稳定性的求解方法。相比之下,其效率几近为LU分解的两倍。[来源请求]
矩阵求逆
若欲对埃尔米特矩阵直接求逆,可以通过科列斯基分解,类似求解线性方程组一般求出逆矩阵,这需要 次运算( 次乘法运算)。 该方法即便要求逐步计算也非常有效率。
非埃尔米特矩阵 也可以通过下例性质求逆,因为其中 总是埃尔米特矩阵︰
计算
有各种各样的方法用于计算科列斯基分解。 常用的算法的计算复杂度在一般情况下为 。[来源请求]
下面的算法何者较缓存决于执行时的具体条件。总体而言,第一个算法会稍慢,因为其以一种不太寻常的方式读取数据。
科列斯基算法
用于计算矩阵 的科列斯基算法,是以高斯消元法为基础而调整得来的。
递归算法由 开始,令
在步骤 ,矩阵 的形式如下:
其中, 代表 维的单位矩阵。
此时定义矩阵 为
随即 可以被改写成
其中
注意︰在此 是一个外积。
重复此步骤直到 从 到 。 步之后,我们得到 。因此,所求的下三角矩阵 为
科列斯基-巴那齐耶维茨及科列斯基-克劳特算法
写出等式 ,
则得到矩阵 的元素的计算公式如下︰
只要 是实数正定矩阵,则平方根下的表达式恒为正。
对于复埃尔米特矩阵,则适用如下公式:
因此,要计算 只需利用其的左、上方元素的值。计算通常是以以下其中一种顺序进行的。
- 科列斯基-巴那齐耶维茨算法从矩阵L的左上角开始,依行进行计算。
- 科列斯基-克劳特算法从矩阵L的左上角开始,依列进行计算。
若有需要,整个矩阵可以逐个元素计算得出,无论使用何种顺序读取。
计算的稳定性
假设我们要求解一个良置的线性方程组。采用了LU分解的算法,除非进行某种绕轴旋转,否则是不稳定的;如果算法进行了绕轴旋转,则其误差取决于矩阵的增长因子,这个数通常(但非总是)很小。
现在,假设算法适用科列斯基分解。如上所述,算法的效率将会是原来的两倍。此外,无必要进行绕轴旋转且误差总是很小。具体而言,若要求解 , 表示已计算出的解,然后能解出干扰方程组 ,其中
在这里, 是指矩阵2-范数,而 是一个取决于 的小常量, 表示单位舍入。
值得一提的是,科列斯基分解与平方根的使用有关。如果被分解的矩阵是正定的,那么只要运算精确,矩阵中带有平方根的元素的平方根下的数字永远是正数。不幸的是,由于存在舍入误差,这些数字可能为负数,并使算法搁浅。然而,此种情况仅当矩阵为病态时才会出现。一种可解决此问题的方法,是增添一个对角修正矩阵至待分解矩阵,以增加矩阵的正定性。[6] 此法虽或将减少分解的准确性,但有在某些情况却颇有作为;譬如,执行应用于最优化的牛顿法时,若初期值距最优值较远,则此时引入对角矩阵可以提高算法的稳定性。
LDL分解
科列斯基分解的另一种形式——LDL分解的计算方式如下所示,
如果 是实数矩阵,下述之递归计算式适用于矩阵 及 中的所有元素︰
如果 是复埃尔米特矩阵,则矩阵 及 的计算适用以下公式:
同样地,若有需求,该读取顺序可以逐一计算矩阵中的每一个元素。
分块矩阵变形
当 是一个不定矩阵时,LDL分解在未经过谨慎的绕轴旋转的情况下是不稳定的;[7] 特别是,分解出的矩阵的元素可能是任意的。一个可取的改进手段是执行矩阵分块后再执行分解,通常将原矩阵分为包含 的小矩阵的分块矩阵:[8]
在此,矩阵中每一个元素都是一个子矩阵。故此,可依照上述递归公式模拟计算:
上述计算涉及矩阵相乘同精确的求逆,故而实践中不能使用过大的分块矩阵。
修正分解
在实践中经常有修正科列斯基分解的需求。即,经已计算一些矩阵 的科列斯基分解 ,然后在 上稍作修改而产生的矩阵 ,欲对其进行一个修正的科列斯基分解 。问题是,能否用已知的 的分解去修正 的分解。
秩为1的修正(相加)
如果修正矩阵 ,则其修正的分解被称为秩为1的修正(相加)。。
以下是一个 MATLAB 语言写的实现秩为1的修正的小程序:
function [L] = cholupdate(L,x)
n = length(x);
for k=1:n
r = sqrt(L(k,k)^2 + x(k)^2);
c = r / L(k, k);
s = x(k) / L(k, k);
L(k, k) = r;
L(k+1:n,k) = (L(k+1:n,k) + s*x(k+1:n)) / c;
x(k+1:n) = c*x(k+1:n) - s*L(k+1:n,k);
end
end
秩为1的修正(相减)
如果 ,那么只有当 仍然是正定的时候该方法才适用。
此条件下,上面的代码也可用于相减的情况,只需要将r
和L(k+1:n,k)
的赋值式的加号替换成减号。
证明半正定矩阵的科列斯基分解唯一
上面的算法表明,每一个正定矩阵 都有一个科列斯基分解。此结论可以加入一些限制条件后,推广到半正定的情况。但该条件并未被完全创建,例如,它未给出明确的数值算法以计算科列斯基因子。
如果 是一个 的半正定矩阵,则序列 是一个由正定矩阵构成的序列。而且,在算子范数中
在正定的情形下,每一个 都有其科列斯基分解 。根据算子范数的性质,
因而 是算子巴拿赫空间上的一个有界集,因此是相对紧空间(因为基础向量空间是有限维的)。因此,它有一个带有限制 收敛子序列,也记作 。容易验证,矩阵 具有所需的特性,例如,满足 以及 是下三角矩阵且其对角元素非负。对于所有的 和 都有,
因此, 。因为基础向量空间是有限维的,所以算子空间的所有拓扑结构都是等价的。故此,范数上 收敛于 ,意味着, 的每个元素都独立地收敛于 。此同时暗示,由于每个 都是对角元素非负的下三角矩阵, 亦如此。
推广
科列斯基分解可以推广到元素中包含算子的矩阵(称为算子矩阵)。[来源请求]令 是希尔伯特空间上的一个序列。考虑如下算子矩阵
满足直和
其中每一个
都是一个有界算子。如果 是正定或半正定的,即对于有限的 及任意的
都有 ,则存在一个下三角的算子矩阵 使得 。此外也可以把 的对角元素化为正数。
用编程语言实现
- C语言︰GNU科学库提供了几个科列斯基分解的实现。
- Maxima电脑代数系统︰函数Cholesky可用于计算科列斯基分解。
- GNU Octave数值计算系统提供了一些函数以计算,修正和应用科列斯基分解。
- LAPACK库提供了一个高性能的科列斯基分解的实现,可以以Fortran,C语言及其他大多数语言读取。
- 在Python中,numpy.linalg模块中的命令Cholesky可执行科列斯基分解。
- 在Matlab中,chol命令可以简单地对一个矩阵进行科列斯基分解。
- 在R语言中,chol函数可进行科列斯基分解。
- 在Wolfram Mathematica中,函数CholeskyDecomposition可以对一个矩阵执行科列斯基分解。
- 在C++中,armadillo库中的命令chol可执行科列斯基分解。特征库提供了稀疏矩阵和稠密矩阵的科列斯基分解。
- 在Analytica中,函数Decompose提供科列斯基分解。
- Apache Commons数学库中有科列斯基分解的实现,可应用于Java、Scala及任何其他JVM语言。
参见
脚注
- ^ Press, William H.; Saul A. Teukolsky; William T. Vetterling; Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing (second edition). Cambridge University England EPress. 1992: 994 [2017-08-30]. ISBN 0-521-43108-5. (原始内容存档于2018-08-25).
- ^ Golub & Van Loan (1996, p. 143), Horn & Johnson (1985, p. 407), Trefethen & Bau (1997, p. 174)
- ^ Golub & Van Loan (1996, p. 147)
- ^ Horn & Johnson (1985, p. 407)
- ^ Krishnamoorthy, Aravindh; Menon, Deepak. Matrix Inversion Using Cholesky Decomposition 1111: 4144. 2011. Bibcode:2011arXiv1111.4144K. arXiv:1111.4144 .
- ^ Fang, Haw-ren; O’Leary, Dianne P. Modified Cholesky Algorithms: A Catalog with New Approaches (PDF). 8 August 2006 [2017-08-30]. (原始内容存档 (PDF)于2017-05-16).
- ^ Nocedal, Jorge. Numerical Optimization. Springer. 2000.
- ^ Fang, Haw-ren. Analysis of Block LDLT Factorizations for Symmetric Indefinite Matrices. 24 August 2007.
参考文献
- Dereniowski, Dariusz; Kubale, Marek. 5th International Conference on Parallel Processing and Applied Mathematics (PDF). Lecture Notes on Computer Science 3019. Springer-Verlag: 985–992. 2004 [2017-08-30]. ISBN 978-3-540-21946-0. doi:10.1007/978-3-540-24669-5_127. (原始内容 (PDF)存档于2011-07-16).
|contribution=
被忽略 (帮助). - Golub, Gene H.; Van Loan, Charles F. Matrix Computations 3rd. Baltimore: Johns Hopkins. 1996. ISBN 978-0-8018-5414-9.
- Horn, Roger A.; Johnson, Charles R. Matrix Analysis. Cambridge University Press. 1985. ISBN 0-521-38632-2..
- S. J. Julier and J. K. Uhlmann. "A General Method for Approximating Nonlinear Transformations of ProbabilityDistributions".
- S. J. Julier and J.K. Uhlmann, "A new extension of the Kalman filter to nonlinear systems," in Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls, 1997, pp. 182–193.
- Trefethen, Lloyd N.; Bau, David. Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics. 1997. ISBN 978-0-89871-361-9..
外部链接
科学史
- Sur la résolution numérique des systèmes d'équations linéaires, Cholesky's 1910 manuscript, online and analyzed on BibNum(页面存档备份,存于互联网档案馆) (法文) (英文) [for English, click 'A télécharger']
信息
- Hazewinkel, Michiel (编), Cholesky factorization, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
- Cholesky Decomposition. PlanetMath.
- Cholesky Decomposition, The Data Analysis BriefBook
- Cholesky Decomposition(页面存档备份,存于互联网档案馆) on www.math-linux.com
- Cholesky Decomposition Made Simple(页面存档备份,存于互联网档案馆) on Science Meanderthal
电脑代码
- LAPACK(页面存档备份,存于互联网档案馆),一个求解稠密线性代数问题的FORTRAN子程序的集合
- ALGLIB(页面存档备份,存于互联网档案馆),包含部分从LAPACK到C++、C#、Delphi、Visual Basic等的端口
- libflame(页面存档备份,存于互联网档案馆),带有LAPACK功能的C函数库
- 德克萨斯大学奥斯汀分校,有关科列斯基分解高性能实现的笔记及视频
- Google,Library "Ceres Solver"(页面存档备份,存于互联网档案馆).
- MATLAB程序,LDL分解
- Armadillo(页面存档备份,存于互联网档案馆),一个C++线性函数包 (package)
模拟中矩阵的利用
- 生成相关的随机变量,Martin Haugh,哥伦比亚大学
在线计算机
- 在线矩阵运算,可执行科列斯基分解。