科列斯基分解

線性代數中，科列斯基分解是指將一個正定的埃爾米特矩陣分解成一個下三角矩陣與其共軛轉置之乘積。這種分解方式在提高代數運算效率、蒙特卡羅方法等場閤中十分有用。實數矩陣的科列斯基分解由安德烈-路易·科列斯基最先發明。實際應用中，科列斯基分解在求解線性方程組中的效率約兩倍於LU分解。描述.對正定埃爾米特矩陣formula_1進行科列斯基分解，即求矩陣formula_2使下式成立formula_3其中，formula_2是一個下三角矩陣且所有對角元素均為正實數，formula_5表示formula_2的共軛轉置。每一個正定埃爾米特矩陣都有一個唯一的科列斯基分解。當矩陣formula_1是一個半正定的埃爾米特矩陣，若允許formula_2的對角線元素為零，則formula_1也存在上述形式的分解。當formula_1為實數矩陣，則formula_2也為實數矩陣且科列斯基分解可改寫成formula_12。當formula_1是正定矩陣時，科列斯基分解是唯一的，即只存在一個對角元素均嚴格大於零的下三角矩陣，使formula_3成立。然而，當formula_1是半正定時，分解則不一定是唯一的。定理的逆命題自然成立：對於某些可逆矩陣formula_2，如果formula_1可被寫成formula_18，則formula_1是一個正定的埃爾米特矩陣。LDL分解.經典科列斯基分解的一個變形是LDL分解，即formula_20其中，formula_2是一個單位下三角矩陣，formula_22是一個對角矩陣。該分解與經典科列斯基分解猶有關聯，如下：formula_23或者，由於formula_2的對角元素必須為formula_25，且formula_26與formula_2都是下三角矩陣，故如果已知經典科列斯基分解formula_26，則formula_29形式可依下式求出，設S是包含formula_30的對角元素的對角矩陣，formula_31formula_32LDL變形如果得以有效執行，構造及使用時所需求的空間及計算的複雜性與經典科列斯基分解是相同的，但是可避擴音取平方根。某些不存在科列斯基分解的不定矩陣，也可以執行LDL分解，此時矩陣formula_22中會出現負數元素。因此人們更傾向於使用LDL分解。對於實數矩陣，該種分解的形式可被改寫成formula_34此形式通常稱為LDLT分解。它與實對稱矩陣的特徵分解密切相關，因為對於實對稱矩陣，存在特徵分解formula_35。例項.以下乃一個實對稱矩陣的科列斯基分解︰formula_36以下乃其LDLT分解︰formula_37應用.科列斯基分解主要被用於線性方程組formula_38的求解。如果A是對稱正定的，我們可以先求出formula_12，隨後借向後替換法對y求解formula_40，再以向前替換法對x求解formula_41即得最終解。另一種可避免在計算formula_42時需要解平方根的方法就是計算formula_43，然後對y求解formula_44，最後求解formula_45對於可以被改寫成對稱矩陣的線性方程組，科列斯基分解及其LDL變形是一個較高效率及較高數值穩定性的求解方法。相比之下，其效率幾近為LU分解的兩倍。#重定向矩陣求逆.若欲對埃爾米特矩陣直接求逆，可以透過科列斯基分解，類似求解線性方程組一般求出逆矩陣，這需要formula_46次運算。 "該方法即便要求逐步計算也非常有效率。"非埃爾米特矩陣formula_48也可以透過下例性質求逆，因為其中formula_49總是埃爾米特矩陣︰formula_50計算.有各種各樣的方法用於計算科列斯基分解。 常用的演演算法的計算複雜度在一般情況下為formula_51。#重定向下面的演算法何者較快取決於執行時的具體條件。總體而言，第一個演算法會稍慢，因為其以一種不太尋常的方式讀取資料。科列斯基演算法.用於計算矩陣formula_2的科列斯基演算法，是以高斯消元法為基礎而調整得來的。遞迴演算法由formula_53開始，令formula_54在步驟formula_55，矩陣formula_56的形式如下：formula_57其中，formula_58代表formula_59維的單位矩陣。此時定義矩陣formula_60為formula_61隨即formula_62可以被改寫成formula_63其中formula_64注意︰在此formula_65是一個外積。重複此步驟直到formula_55從formula_25到formula_68。formula_68步之後，我們得到formula_70。因此，所求的下三角矩陣formula_71為formula_72科列斯基-巴那齊耶維茨及科列斯基-克勞特演演算法.寫出等式formula_3，formula_74則得到矩陣formula_2的元素的計算公式如下︰formula_76formula_77只要formula_1是實數正定矩陣，則平方根下的表示式恆為正。對於複埃爾米特矩陣，則適用如下公式：formula_79formula_80因此，要計算formula_81只需利用其的左、上方元素的值。計算通常是以以下其中一種順序進行的。若有需要，"整個矩陣可以逐個元素計算得出"，無論使用何種順序讀取。計算的穩定性.假設我們要求解一個良置的線性方程組。採用了LU分解的演算法，除非進行某種繞軸旋轉，否則是不穩定的；如果演算法進行了繞軸旋轉，則其誤差取決於矩陣的"增長因子"，這個數通常很小。現在，假設演算法適用科列斯基分解。如上所述，演算法的效率將會是原來的兩倍。此外，無必要進行繞軸旋轉且誤差總是很小。具體而言，若要求解formula_82，formula_83表示已計算出的解，然後能解出"幹擾方程組"formula_84，其中formula_85在這裡，formula_86是指矩陣2-範數，而formula_87是一個取決於formula_68的小常數，formula_89表示。值得一提的是，科列斯基分解與平方根的使用有關。如果被分解的矩陣是正定的，那麼只要"運算精確"，矩陣中帶有平方根的元素的平方根下的數字永遠是正數。不幸的是，由於存在捨入誤差，這些數字可能為負數，並使演算法擱淺。然而，此種情況僅當矩陣為病態時才會出現。一種可解決此問題的方法，是增添一個對角修正矩陣至待分解矩陣，以增加矩陣的正定性。 此法雖或將減少分解的準確性，但有在某些情況卻頗有作為；譬如，執行應用於最最佳化的牛頓法時，若初期值距最優值較遠，則此時引入對角矩陣可以提高演演算法的穩定性。LDL分解.科列斯基分解的另一種形式——LDL分解的計算方式如下所示，formula_90如果 是實數矩陣，下述之遞迴計算式適用於矩陣  及  中的所有元素︰formula_91formula_92如果 是複埃爾米特矩陣，則矩陣  及 的計算適用以下公式：formula_93formula_94同樣地，若有需求，"該讀取順序可以逐一計算矩陣中的每一個元素。"分塊矩陣變形.當formula_1是一個不定矩陣時，LDL分解在未經過謹慎的繞軸旋轉的情況下是不穩定的； 特別是，分解出的矩陣的元素可能是任意的。一個可取的改進手段是執行矩陣分塊後再執行分解，通常將原矩陣分為包含formula_96的小矩陣的分塊矩陣：formula_97在此，矩陣中每一個元素都是一個子矩陣。故此，可依照上述遞迴公式類比計算：formula_98formula_99上述計算涉及矩陣相乘同精確的求逆，故而實踐中不能使用過大的分塊矩陣。"修正"分解.在實踐中經常有"修正"科列斯基分解的需求。即，經已計算一些矩陣formula_1的科列斯基分解formula_3，然後在formula_1上稍作修改而產生的矩陣formula_103，欲對其進行一個修正的科列斯基分解formula_104。問題是，能否用已知的formula_1的分解去修正formula_106的分解。秩為1的修正.如果"修正"矩陣formula_107，則其修正的分解被稱為秩為1的修正。。以下是一個 MATLAB 語言寫的實現秩為1的修正的小程式：function [L] = cholupdate(L,x)n = length(x);for k=1:nr = 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);endend秩為1的修正.如果formula_108，那麼只有當formula_109仍然是正定的時候該方法才適用。此條件下，上面的程式碼也可用於相減的情況，只需要將codice_1和codice_2的賦值式的加號替換成減號。證明半正定矩陣的科列斯基分解唯一.上面的演演算法表明，每一個正定矩陣formula_110都有一個科列斯基分解。此結論可以"加入一些限制條件"後，推廣到半正定的情況。但該"條件"並未被完全建立，例如，它未給出明確的數值演演算法以計算科列斯基因子。如果formula_110是一個formula_112的半正定矩陣，則序列formula_113是一個由正定矩陣構成的序列。而且，在運算元範數中formula_114在正定的情形下，每一個formula_115都有其科列斯基分解formula_116。根據運算元範數的性質，formula_117因而formula_118是運算元巴拿赫空間上的一個有界集，因此是。因此，它有一個帶有限制formula_2收斂子序列，也記作formula_118。容易驗證，矩陣formula_2具有所需的特性，例如，滿足formula_122以及formula_2是下三角矩陣且其對角元素非負。對於所有的formula_124和formula_125都有，formula_126因此，formula_3。因為基礎向量空間是有限維的，所以運算元空間的所有拓撲結構都是等價的。故此，範數上formula_128收斂於formula_2，意味著，formula_128的每個元素都獨立地收斂於formula_2。此同時暗示，由於每個formula_128都是對角元素非負的下三角矩陣，formula_2亦如此。推廣.科列斯基分解可以推廣到元素中包含運算元的矩陣。#重定向formula_135滿足直和formula_136其中每一個formula_137都是一個有界運算元。如果formula_1是正定或半正定的，即對於有限的formula_139及任意的formula_140都有formula_141，則存在一個下三角的運算元矩陣formula_2使得formula_143。此外也可以把formula_2的對角元素化為正數。