चोलेस्की अपघटन

रैखिक बीजगणित में, चोलेस्की अपघटन या चोलेस्की गुणनखंडन (उच्चारण)। /ʃəˈlɛski/ shə-LES-kee) एक हर्मिटियन मैट्रिक्स का एक मैट्रिक्स अपघटन है, निचले त्रिकोणीय मैट्रिक्स और इसके संयुग्मित ट्रांसपोज़ के उत्पाद में सकारात्मक-निश्चित मैट्रिक्स, जो कुशल संख्यात्मक समाधानों के लिए उपयोगी है, उदाहरण के लिए, मोंटे कार्लो सिमुलेशन। वास्तविक मैट्रिक्स के लिए इसकी खोज आंद्रे-लुई चोल्स्की ने की थी और इसे मरणोपरांत 1924 में प्रकाशित किया गया था। जब यह लागू होता है, तो चोलेस्की अपघटन रैखिक समीकरणों की प्रणाली को हल करने के लिए एलयू अपघटन से लगभग दोगुना कुशल होता है।

कथन

हर्मिटियन मैट्रिक्स सकारात्मक-निश्चित मैट्रिक्स ए का चोल्स्की अपघटन, फॉर्म का एक अपघटन है

$\mathbf {A} =\mathbf {LL} ^{*},$

जहां एल वास्तविक और सकारात्मक विकर्ण प्रविष्टियों के साथ एक निचला त्रिकोणीय मैट्रिक्स है, और एल * एल के संयुग्मित स्थानान्तरण को दर्शाता है। प्रत्येक हर्मिटियन सकारात्मक-निश्चित मैट्रिक्स (और इस प्रकार प्रत्येक वास्तविक-मूल्य सममित सकारात्मक-निश्चित मैट्रिक्स) में एक अद्वितीय चोल्स्की अपघटन होता है। उलटा महत्वहीन है: यदि ए को कुछ उलटे एल, निचले त्रिकोणीय या अन्यथा के लिए एलएल * के रूप में लिखा जा सकता है, तो ए हर्मिटियन और सकारात्मक निश्चित है।

जब A एक वास्तविक मैट्रिक्स है (इसलिए सममित सकारात्मक-निश्चित), तो गुणनखंडन लिखा जा सकता है

$\mathbf {A} =\mathbf {LL} ^{\mathsf {T}},$

जहां L सकारात्मक विकर्ण प्रविष्टियों वाला एक वास्तविक निचला त्रिकोणीय मैट्रिक्स है।

सकारात्मक अर्धनिश्चित आव्यूह

यदि हर्मिटियन मैट्रिक्स ए सकारात्मक निश्चित के बजाय केवल सकारात्मक अर्धनिश्चित है, तो इसमें अभी भी फॉर्म का अपघटन होता है A = LL* जहां L की विकर्ण प्रविष्टियों को शून्य होने की अनुमति है। उदाहरण के लिए, अपघटन को अद्वितीय होने की आवश्यकता नहीं है:

${\begin{bmatrix}0&0\\0&1\end{bmatrix}}=\mathbf {L} \mathbf {L} ^{*},\quad \quad \mathbf {L} ={\begin{bmatrix}0&0\\\cos \theta &\sin \theta \end{bmatrix}}.$

हालाँकि, यदि A की रैंक r है, तो बिल्कुल r सकारात्मक विकर्ण तत्वों और n-r कॉलम के साथ एक अद्वितीय निचला त्रिकोणीय L होता है जिसमें सभी शून्य होते हैं। वैकल्पिक रूप से, जब एक धुरी विकल्प तय हो जाता है तो अपघटन को अद्वितीय बनाया जा सकता है। औपचारिक रूप से, यदि A एक है n × n रैंक आर का सकारात्मक अर्धनिश्चित मैट्रिक्स, तो कम से कम एक क्रमपरिवर्तन मैट्रिक्स 'पी' ऐसा है P A P^T रूप का एक अद्वितीय अपघटन है P A P^T = L L^* साथ $\mathbf {L} ={\begin{bmatrix}\mathbf {L} _{1}&0\\\mathbf {L} _{2}&0\end{bmatrix}}$, जहां एल₁ एक r × r सकारात्मक विकर्ण के साथ निचला त्रिकोणीय मैट्रिक्स।

एलडीएल अपघटन

शास्त्रीय चोलेस्की अपघटन का एक निकट से संबंधित संस्करण एलडीएल अपघटन है,

$\mathbf {A} =\mathbf {LDL} ^{*},$

जहां L एक इकाईत्रिकोणीय मैट्रिक्स है|निचली इकाई त्रिकोणीय (एकत्रिकोणीय) मैट्रिक्स है, और D एक विकर्ण मैट्रिक्स मैट्रिक्स है। अर्थात्, अपघटन में एक अतिरिक्त विकर्ण मैट्रिक्स डी को पेश करने की कीमत पर एल के विकर्ण तत्वों को 1 होना आवश्यक है। मुख्य लाभ यह है कि एलडीएल अपघटन की गणना की जा सकती है और अनिवार्य रूप से समान एल्गोरिदम के साथ उपयोग किया जा सकता है, लेकिन वर्गमूल निकालने से बचा जाता है। इस कारण से, एलडीएल अपघटन को अक्सर वर्ग-मूल-मुक्त चोलेस्की अपघटन कहा जाता है। वास्तविक आव्यूहों के लिए, गुणनखंडन का रूप होता है A = LDL^T और इसे अक्सर एलडीएलटी अपघटन (या एलडीएल) के रूप में जाना जाता है^टीअपघटन, या एलडीएल')। यह एक मैट्रिक्स#वास्तविक सममित मैट्रिक्स के eigendecomposition की याद दिलाता है, A = QΛQ^T, लेकिन व्यवहार में यह काफी भिन्न है क्योंकि Λ और D समान आव्यूह नहीं हैं।

एलडीएल अपघटन फॉर्म एलएल* के शास्त्रीय चोल्स्की अपघटन से निम्नानुसार संबंधित है:

$\mathbf {A} =\mathbf {LDL} ^{*}=\mathbf {L} \mathbf {D} ^{1/2}\left(\mathbf {D} ^{1/2}\right)^{*}\mathbf {L} ^{*}=\mathbf {L} \mathbf {D} ^{1/2}\left(\mathbf {L} \mathbf {D} ^{1/2}\right)^{*}.$

इसके विपरीत, शास्त्रीय चोल्स्की अपघटन को देखते हुए $\mathbf {A} =\mathbf {C} \mathbf {C} ^{*}$ एक सकारात्मक निश्चित मैट्रिक्स का, यदि S एक विकर्ण मैट्रिक्स है जिसमें मुख्य विकर्ण शामिल है $\mathbf {C}$, तो A को इस प्रकार विघटित किया जा सकता है $\mathbf {L} \mathbf {D} \mathbf {L} ^{*}$ कहाँ

$\mathbf {L} =\mathbf {C} \mathbf {S} ^{-1}$ (यह विकर्ण तत्व 1 बनाने के लिए प्रत्येक कॉलम को पुनः मापता है),

$\mathbf {D} =\mathbf {S} ^{2}.$

यदि A सकारात्मक निश्चित है तो D के सभी विकर्ण तत्व सकारात्मक हैं। सकारात्मक अर्धनिश्चित ए के लिए, ए $\mathbf {L} \mathbf {D} \mathbf {L} ^{*}$ अपघटन वहां मौजूद है जहां विकर्ण डी पर गैर-शून्य तत्वों की संख्या बिल्कुल ए की रैंक है। कुछ अनिश्चित आव्यूह जिनके लिए कोई चोलेस्की अपघटन मौजूद नहीं है, उनमें डी में नकारात्मक प्रविष्टियों के साथ एलडीएल अपघटन होता है: यह पर्याप्त है कि पहला एन-1 माइनर (रैखिक बीजगणित)#ए के अन्य अनुप्रयोग गैर-एकवचन हैं।

उदाहरण

यहाँ एक सममित वास्तविक मैट्रिक्स का चोलेस्की अपघटन है:

${\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}={\begin{pmatrix}2&0&0\\6&1&0\\-8&5&3\\\end{pmatrix}}{\begin{pmatrix}2&6&-8\\0&1&5\\0&0&3\\\end{pmatrix}}.\end{aligned}}$

और यहाँ इसका एलडीएल है^टी अपघटन:

${\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}&={\begin{pmatrix}1&0&0\\3&1&0\\-4&5&1\\\end{pmatrix}}{\begin{pmatrix}4&0&0\\0&1&0\\0&0&9\\\end{pmatrix}}{\begin{pmatrix}1&3&-4\\0&1&5\\0&0&1\\\end{pmatrix}}.\end{aligned}}$

अनुप्रयोग

चोलेस्की अपघटन का उपयोग मुख्य रूप से रैखिक समीकरणों की प्रणाली के संख्यात्मक समाधान के लिए किया जाता है $\mathbf {Ax} =\mathbf {b}$. यदि A सममित और धनात्मक निश्चित है, तो हम हल कर सकते हैं $\mathbf {Ax} =\mathbf {b}$ सबसे पहले चोल्स्की अपघटन की गणना करके $\mathbf {A} =\mathbf {LL} ^{\mathrm {*} }$, फिर हल करना $\mathbf {Ly} =\mathbf {b}$ y के लिए अग्र प्रतिस्थापन द्वारा, और अंत में हल करके $\mathbf {L^{*}x} =\mathbf {y}$ x के लिए पश्च प्रतिस्थापन द्वारा।

में वर्गमूल लेने से बचने का एक वैकल्पिक तरीका $\mathbf {LL} ^{\mathrm {*} }$ अपघटन एलडीएल अपघटन की गणना करना है $\mathbf {A} =\mathbf {LDL} ^{\mathrm {*} }$, फिर हल करना $\mathbf {Ly} =\mathbf {b}$ y के लिए, और अंत में हल करना $\mathbf {DL} ^{\mathrm {*} }\mathbf {x} =\mathbf {y}$.

रैखिक प्रणालियों के लिए जिन्हें सममित रूप में रखा जा सकता है, बेहतर दक्षता और संख्यात्मक स्थिरता के लिए चोल्स्की अपघटन (या इसका एलडीएल संस्करण) पसंद की विधि है। एलयू अपघटन की तुलना में, यह लगभग दोगुना कुशल है।

रैखिक न्यूनतम वर्ग

ए सममित और सकारात्मक निश्चित के साथ फॉर्म एक्स = बी की प्रणालियाँ अनुप्रयोगों में अक्सर सामने आती हैं। उदाहरण के लिए, रैखिक न्यूनतम वर्ग (गणित) समस्याओं में सामान्य समीकरण इसी रूप के होते हैं। ऐसा भी हो सकता है कि मैट्रिक्स ए एक ऊर्जा कार्यात्मकता से आता है, जो भौतिक विचारों से सकारात्मक होना चाहिए; आंशिक अवकल समीकरणों के संख्यात्मक समाधान में ऐसा अक्सर होता है।

गैर-रेखीय अनुकूलन

न्यूटन की विधि के वेरिएंट का उपयोग करके गैर-रेखीय बहु-भिन्न कार्यों को उनके मापदंडों पर कम किया जा सकता है, जिन्हें अर्ध-न्यूटन विधियां कहा जाता है। पुनरावृत्ति k पर, खोज एक दिशा में आगे बढ़ती है $p_{k}$ हल करके परिभाषित किया गया है $B_{k}p_{k}=-g_{k}$ के लिए $p_{k}$, कहाँ $p_{k}$ कदम की दिशा है, $g_{k}$ ढाल है, और $B_{k}$ प्रत्येक पुनरावृत्ति पर रैंक-1 अपडेट को दोहराकर गठित हेस्सियन मैट्रिक्स का एक अनुमान है। दो प्रसिद्ध अद्यतन फ़ार्मुलों को डेविडन-फ्लेचर-पॉवेल (DFP) और BFGS विधि | ब्रॉयडेन-फ़्लेचर-गोल्डफ़ार्ब-शैनो (BFGS) कहा जाता है। राउंड-ऑफ त्रुटि के माध्यम से सकारात्मक-निश्चित स्थिति के नुकसान से बचा जा सकता है यदि हेसियन के व्युत्क्रम के सन्निकटन को अद्यतन करने के बजाय, कोई हेसियन मैट्रिक्स के सन्निकटन के चोल्स्की अपघटन को अद्यतन करता है। .

मोंटे कार्लो सिमुलेशन

चॉलेस्की अपघटन का उपयोग आमतौर मोंटे कार्लो विधि पद्धति में कई सहसंबद्ध चर वाले सिस्टम के अनुकरण के लिए किया जाता है। सहप्रसरण मैट्रिक्स को निम्न-त्रिकोणीय एल देने के लिए विघटित किया जाता है। इसे असंबद्ध नमूनों के एक वेक्टर पर लागू करने से आप मॉडल किए जा रहे सिस्टम के सहप्रसरण गुणों के साथ एक नमूना वेक्टर लू उत्पन्न करते हैं। निम्नलिखित सरलीकृत उदाहरण चोलेस्की अपघटन से प्राप्त अर्थव्यवस्था को दर्शाता है: मान लीजिए कि लक्ष्य दो सहसंबद्ध सामान्य चर उत्पन्न करना है $x_{1}$ और $x_{2}$ दिए गए सहसंबंध गुणांक के साथ $\rho$. इसे पूरा करने के लिए, पहले दो असंबद्ध गॉसियन यादृच्छिक चर उत्पन्न करना आवश्यक है $z_{1}$ और $z_{2}$, जो बॉक्स-मुलर ट्रांसफ़ॉर्म का उपयोग करके किया जा सकता है। आवश्यक सहसंबंध गुणांक दिया गया है $\rho$, सहसंबद्ध सामान्य चर परिवर्तनों के माध्यम से प्राप्त किए जा सकते हैं $x_{1}=z_{1}$ और ${\textstyle x_{2}=\rho z_{1}+{\sqrt {1-\rho ^{2}}}z_{2}}$.

कलमैन फ़िल्टर

तथाकथित सिग्मा बिंदुओं का एक सेट चुनने के लिए असुगंधित कलमैन फ़िल्टर आमतौर पर चोल्स्की अपघटन का उपयोग करते हैं। कलमन फिल्टर एक सिस्टम की औसत स्थिति को एन लंबाई के वेक्टर एक्स और एन × एन मैट्रिक्स पी के रूप में सहप्रसरण के रूप में ट्रैक करता है। मैट्रिक्स पी हमेशा सकारात्मक अर्ध-निश्चित होता है और इसे एलएल में विघटित किया जा सकता है।^टी. L के स्तंभों को माध्य x से जोड़कर 2N वैक्टर का एक सेट बनाया जा सकता है, जिन्हें सिग्मा पॉइंट कहा जाता है। ये सिग्मा बिंदु सिस्टम स्थिति के माध्य और सहप्रसरण को पूरी तरह से पकड़ लेते हैं।

मैट्रिक्स व्युत्क्रम

हर्मिटियन मैट्रिक्स के स्पष्ट व्युत्क्रम मैट्रिक्स की गणना चोल्स्की अपघटन द्वारा, रैखिक प्रणालियों को हल करने के समान तरीके से की जा सकती है, का उपयोग करके $n^{3}$ संचालन (${\tfrac {1}{2}}n^{3}$ गुणन).संपूर्ण व्युत्क्रम को उसी स्थान पर कुशलतापूर्वक निष्पादित किया जा सकता है।

एक गैर-हर्मिटियन मैट्रिक्स बी को निम्नलिखित पहचान का उपयोग करके उलटा भी किया जा सकता है, जहां बीबी * हमेशा हर्मिटियन होगा:

$\mathbf {B} ^{-1}=\mathbf {B} ^{*}(\mathbf {BB} ^{*})^{-1}.$

गणना

चोल्स्की अपघटन की गणना के लिए विभिन्न विधियाँ हैं। आमतौर पर उपयोग किए जाने वाले एल्गोरिदम की कम्प्यूटेशनल जटिलता O(n) है³) सामान्यतः। नीचे वर्णित सभी एल्गोरिदम में लगभग (1/3)एन शामिल है³ फ्लॉप (एन^{वास्तविक स्वादों के लिए 3}/6 गुणन और समान संख्या में जोड़) और (4/3)एन^{जटिल स्वादों के लिए 3 फ्लॉप, जहां n मैट्रिक्स 'ए' का आकार है। इसलिए, उनके पास LU अपघटन की आधी लागत है, जो 2n का उपयोग करता है3/3 फ्लॉप (देखें ट्रेफेथेन और बाउ 1997)।}

नीचे दिया गया कौन सा एल्गोरिदम तेज़ है यह कार्यान्वयन के विवरण पर निर्भर करता है। आम तौर पर, पहला एल्गोरिदम थोड़ा धीमा होगा क्योंकि यह कम नियमित तरीके से डेटा तक पहुंचता है।

चोलेस्की एल्गोरिथ्म

चोलेस्की एल्गोरिदम, जिसका उपयोग अपघटन मैट्रिक्स एल की गणना करने के लिए किया जाता है, गॉसियन उन्मूलन का एक संशोधित संस्करण है।

पुनरावर्ती एल्गोरिदम i := 1 और से शुरू होता है

ए⁽¹⁾ := ए.

चरण i पर, मैट्रिक्स ए⁽ⁱ⁾ का निम्नलिखित रूप है:

$\mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},$

जहां मैं_i−1 आयाम i - 1 के पहचान मैट्रिक्स को दर्शाता है।

यदि अब हम मैट्रिक्स 'एल' को परिभाषित करते हैं_i द्वारा

$\mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},$

(ध्यान दें कि ए_i,i > 0 चूंकि ए⁽ⁱ⁾सकारात्मक निश्चित है), तो हम 'ए' लिख सकते हैं⁽ⁱ⁾जैसे

$\mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}$

कहाँ

$\mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.$

ध्यान दें कि बी_i बी*_i एक बाहरी उत्पाद है, इसलिए इस एल्गोरिदम को (गोलब और वैन लोन) में बाहरी-उत्पाद संस्करण कहा जाता है।

हम इसे i से 1 से n तक दोहराते हैं। n चरणों के बाद, हमें 'A' मिलता है⁽ⁿ⁺¹⁾ = 'मैं'। इसलिए, हम जिस निचले त्रिकोणीय मैट्रिक्स L की तलाश कर रहे हैं उसकी गणना इस प्रकार की जाती है

$\mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.$

चॉलेस्की-बानाचीविक्ज़ और चॉलेस्की-क्राउट एल्गोरिदम

5×5 मैट्रिक्स पर इन-प्लेस चोल्स्की-बानाचीविक्ज़ एल्गोरिदम के लिए एक्सेस पैटर्न (सफ़ेद) और लेखन पैटर्न (पीला)

यदि हम समीकरण लिखते हैं

${\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\begin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\end{pmatrix}}\\[8pt]&={\begin{pmatrix}L_{11}^{2}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}$

हमें निम्नलिखित प्राप्त होता है:

${\begin{aligned}\mathbf {L} ={\begin{pmatrix}{\sqrt {A_{11}}}&0&0\\A_{21}/L_{11}&{\sqrt {A_{22}-L_{21}^{2}}}&0\\A_{31}/L_{11}&\left(A_{32}-L_{31}L_{21}\right)/L_{22}&{\sqrt {A_{33}-L_{31}^{2}-L_{32}^{2}}}\end{pmatrix}}\end{aligned}}$

और इसलिए एल की प्रविष्टियों के लिए निम्नलिखित सूत्र:

$L_{j,j}=(\pm ){\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{2}}},$

$L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right)\quad {\text{for }}i>j.$

जटिल और वास्तविक मैट्रिक्स के लिए, विकर्ण और संबंधित ऑफ-विकर्ण तत्वों के अप्रासंगिक मनमाने ढंग से संकेत परिवर्तन की अनुमति है। यदि A वास्तविक और सकारात्मक-निश्चित है तो वर्गमूल के अंतर्गत अभिव्यक्ति हमेशा सकारात्मक होती है।

जटिल हर्मिटियन मैट्रिक्स के लिए, निम्नलिखित सूत्र लागू होता है:

$L_{j,j}={\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{j,k}}},$

$L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{i,k}\right)\quad {\text{for }}i>j.$

इसलिए यदि हम बाईं और ऊपर की प्रविष्टियों को जानते हैं तो हम (i, j) प्रविष्टि की गणना कर सकते हैं। गणना आमतौर पर निम्नलिखित में से किसी एक क्रम में व्यवस्थित की जाती है:

• 'चोलेस्की-बानाचीविक्ज़ एल्गोरिदम' मैट्रिक्स एल के ऊपरी बाएं कोने से शुरू होता है और पंक्ति दर पंक्ति मैट्रिक्स की गणना करने के लिए आगे बढ़ता है।

for (i = 0; i < dimensionSize; i++) {
    for (j = 0; j <= i; j++) {
        float sum = 0;
        for (k = 0; k < j; k++)
            sum += L[i][k] * L[j][k];

        if (i == j)
            L[i][j] = sqrt(A[i][i] - sum);
        else
            L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));
    }
}

उपरोक्त एल्गोरिदम को फोरट्रान जैसी वेक्टरकृत प्रोग्रामिंग भाषाओं में एक डॉट उत्पाद और मैट्रिक्स गुणन के संयोजन के रूप में संक्षेप में व्यक्त किया जा सकता है,

do i = 1, size(A,1)
    L(i,i) = sqrt(A(i,i) - dot_product(L(i,1:i-1), L(i,1:i-1)))
    L(i+1:,i) = (A(i+1:,i) - matmul(conjg(L(i,1:i-1)), L(i+1:,1:i-1))) / L(i,i)
end do

कहाँ conjg तत्वों के जटिल संयुग्मन को संदर्भित करता है।

• चॉलेस्की-क्राउट एल्गोरिदम मैट्रिक्स एल के ऊपरी बाएं कोने से शुरू होता है और कॉलम द्वारा मैट्रिक्स कॉलम की गणना करने के लिए आगे बढ़ता है।

  for (j = 0; j < dimensionSize; j++) {
      float sum = 0;
      for (k = 0; k < j; k++) {
          sum += L[j][k] * L[j][k];
      }
      L[j][j] = sqrt(A[j][j] - sum);
  
      for (i = j + 1; i < dimensionSize; i++) {
          sum = 0;
          for (k = 0; k < j; k++) {
              sum += L[i][k] * L[j][k];
          }
          L[i][j] = (1.0 / L[j][j] * (A[i][j] - sum));
      }
  }
  

उपरोक्त एल्गोरिदम को फोरट्रान जैसी वेक्टरकृत प्रोग्रामिंग भाषाओं में एक डॉट उत्पाद और मैट्रिक्स गुणन के संयोजन के रूप में संक्षेप में व्यक्त किया जा सकता है,

do i = 1, size(A,1)
    L(i,i) = sqrt(A(i,i) - dot_product(L(1:i-1,i), L(1:i-1,i)))
    L(i,i+1:) = (A(i,i+1:) - matmul(conjg(L(1:i-1,i)), L(1:i-1,i+1:))) / L(i,i)
end do

कहाँ conjg तत्वों के जटिल संयुग्मन को संदर्भित करता है।

यदि वांछित हो तो पहुंच का कोई भी पैटर्न संपूर्ण गणना को उसी स्थान पर निष्पादित करने की अनुमति देता है।

गणना की स्थिरता

मान लीजिए कि हम रैखिक समीकरणों की एक स्थिति संख्या|सुव्यवस्थित प्रणाली को हल करना चाहते हैं। यदि LU अपघटन का उपयोग किया जाता है, तो एल्गोरिथ्म अस्थिर है जब तक कि हम किसी प्रकार की धुरी रणनीति का उपयोग नहीं करते हैं। बाद वाले मामले में, त्रुटि मैट्रिक्स के तथाकथित विकास कारक पर निर्भर करती है, जो आमतौर पर (लेकिन हमेशा नहीं) छोटा होता है।

अब, मान लीजिए कि चोल्स्की अपघटन लागू है। जैसा कि ऊपर बताया गया है, एल्गोरिदम दोगुना तेज़ होगा। इसके अलावा, कोई धुरी तत्व आवश्यक नहीं है, और त्रुटि हमेशा छोटी होगी। विशेष रूप से, यदि हम Ax = b को हल करना चाहते हैं, और y गणना किए गए समाधान को दर्शाता है, तो y परेशान प्रणाली (A + E)y = b को हल करता है, जहां

$\|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.$

यहाँ ||·||₂ मैट्रिक्स मानदंड है|मैट्रिक्स 2-मानदंड, सी_nn के आधार पर एक छोटा स्थिरांक है, और ε इकाई राउंड-ऑफ को दर्शाता है।

चोल्स्की अपघटन के संबंध में एक चिंता का विषय वर्गमूलों का उपयोग है। यदि गुणनखंडित किया जा रहा मैट्रिक्स आवश्यकतानुसार सकारात्मक निश्चित है, तो सटीक अंकगणित में वर्गमूल के नीचे की संख्याएँ हमेशा सकारात्मक होती हैं। दुर्भाग्य से, राउंड-ऑफ़ त्रुटियों के कारण संख्याएँ नकारात्मक हो सकती हैं, ऐसी स्थिति में एल्गोरिथम जारी नहीं रह सकता है। हालाँकि, यह तभी हो सकता है जब मैट्रिक्स बहुत खराब स्थिति में हो। इसे संबोधित करने का एक तरीका सकारात्मक-निश्चितता को बढ़ावा देने के प्रयास में विघटित होने वाले मैट्रिक्स में एक विकर्ण सुधार मैट्रिक्स जोड़ना है। हालाँकि इससे अपघटन की सटीकता कम हो सकती है, यह अन्य कारणों से बहुत अनुकूल हो सकता है; उदाहरण के लिए, अनुकूलन में न्यूटन की विधि का प्रदर्शन करते समय, एक विकर्ण मैट्रिक्स जोड़ने से इष्टतम से दूर होने पर स्थिरता में सुधार हो सकता है।

एलडीएल अपघटन

एक वैकल्पिक रूप, जब A सममित हो तो वर्गमूल लेने की आवश्यकता को समाप्त करना, सममित अनिश्चित गुणनखंडन है

${\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}D_{1}&&(\mathrm {symmetric} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}.\end{pmatrix}}.\end{aligned}}$

निम्नलिखित पुनरावर्ती संबंध डी और एल की प्रविष्टियों के लिए लागू होते हैं:

$D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}^{2}D_{k},$

$L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}D_{k}\right)\quad {\text{for }}i>j.$

यह तब तक काम करता है जब तक डी में उत्पन्न विकर्ण तत्व गैर-शून्य रहते हैं। तब अपघटन अद्वितीय होता है। यदि A वास्तविक है तो D और L वास्तविक हैं।

जटिल हर्मिटियन मैट्रिक्स ए के लिए, निम्नलिखित सूत्र लागू होता है:

$D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}L_{jk}^{*}D_{k},$

$L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}D_{k}\right)\quad {\text{for }}i>j.$

फिर, पहुंच का पैटर्न यदि वांछित हो तो संपूर्ण गणना को उसी स्थान पर निष्पादित करने की अनुमति देता है।

ब्लॉक वैरिएंट

जब अनिश्चित मैट्रिक्स पर उपयोग किया जाता है, तो एलडीएल* फ़ैक्टराइज़ेशन को सावधानीपूर्वक धुरीकरण के बिना अस्थिर माना जाता है; विशेष रूप से, गुणनखंडन के तत्व मनमाने ढंग से बढ़ सकते हैं। एक संभावित सुधार ब्लॉक उप-मैट्रिस पर गुणनखंडन करना है, आमतौर पर 2 × 2:

${\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}\mathbf {I} &0&0\\\mathbf {L} _{21}&\mathbf {I} &0\\\mathbf {L} _{31}&\mathbf {L} _{32}&\mathbf {I} \\\end{pmatrix}}{\begin{pmatrix}\mathbf {D} _{1}&0&0\\0&\mathbf {D} _{2}&0\\0&0&\mathbf {D} _{3}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {I} &\mathbf {L} _{21}^{\mathrm {T} }&\mathbf {L} _{31}^{\mathrm {T} }\\0&\mathbf {I} &\mathbf {L} _{32}^{\mathrm {T} }\\0&0&\mathbf {I} \\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}\mathbf {D} _{1}&&(\mathrm {symmetric} )\\\mathbf {L} _{21}\mathbf {D} _{1}&\mathbf {L} _{21}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {D} _{2}&\\\mathbf {L} _{31}\mathbf {D} _{1}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{31}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}\mathbf {L} _{32}^{\mathrm {T} }+\mathbf {D} _{3}\end{pmatrix}},\end{aligned}}$

जहां उपरोक्त आव्यूहों में प्रत्येक तत्व एक वर्ग उपमैट्रिक्स है। इससे, ये अनुरूप पुनरावर्ती संबंध अनुसरण करते हैं:

$\mathbf {D} _{j}=\mathbf {A} _{jj}-\sum _{k=1}^{j-1}\mathbf {L} _{jk}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} },$

$\mathbf {L} _{ij}=\left(\mathbf {A} _{ij}-\sum _{k=1}^{j-1}\mathbf {L} _{ik}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} }\right)\mathbf {D} _{j}^{-1}.$

इसमें मैट्रिक्स उत्पाद और स्पष्ट उलटा शामिल है, इस प्रकार व्यावहारिक ब्लॉक आकार सीमित है।

अपघटन को अद्यतन करना

एक कार्य जो व्यवहार में अक्सर उठता है वह यह है कि किसी को चोलेस्की अपघटन को अद्यतन करने की आवश्यकता होती है। अधिक विवरण में, कोई पहले ही चोल्स्की अपघटन की गणना कर चुका है $\mathbf {A} =\mathbf {L} \mathbf {L} ^{*}$ कुछ मैट्रिक्स का $\mathbf {A}$, फिर कोई मैट्रिक्स बदलता है $\mathbf {A}$ किसी अन्य मैट्रिक्स में, मान लीजिए ${\tilde {\mathbf {A} }}$, और कोई अद्यतन मैट्रिक्स के चोल्स्की अपघटन की गणना करना चाहता है: ${\tilde {\mathbf {A} }}={\tilde {\mathbf {L} }}{\tilde {\mathbf {L} }}^{*}$. अब सवाल यह है कि क्या कोई चॉलेस्की अपघटन का उपयोग कर सकता है $\mathbf {A}$ इसकी गणना पहले चोलेस्की अपघटन की गणना करने के लिए की गई थी ${\tilde {\mathbf {A} }}$.

रैंक-एक अद्यतन

विशिष्ट मामला, जहां अद्यतन मैट्रिक्स ${\tilde {\mathbf {A} }}$ मैट्रिक्स से संबंधित है $\mathbf {A}$ द्वारा ${\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {x} \mathbf {x} ^{*}$, रैंक-वन अपडेट के रूप में जाना जाता है।

यहाँ एक समारोह है मैटलैब सिंटैक्स में लिखा गया है जो रैंक-वन अपडेट का एहसास कराता है:

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;
        if k < n
            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
end

रैंक-एन अपडेट वह है जहां मैट्रिक्स के लिए $\mathbf {M}$ एक अपघटन को इस प्रकार अद्यतन करता है ${\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {M} \mathbf {M} ^{*}$. इसे प्रत्येक कॉलम के लिए क्रमिक रूप से रैंक-एक अपडेट करके प्राप्त किया जा सकता है $\mathbf {M}$.

रैंक-एक डाउनडेट

रैंक-वन डाउनडेट रैंक-वन अपडेट के समान है, सिवाय इसके कि जोड़ को घटाव द्वारा प्रतिस्थापित किया जाता है: ${\tilde {\mathbf {A} }}=\mathbf {A} -\mathbf {x} \mathbf {x} ^{*}$. यह केवल तभी काम करता है जब नया मैट्रिक्स हो ${\tilde {\mathbf {A} }}$ अभी भी सकारात्मक निश्चित है.

ऊपर दिखाए गए रैंक-वन अपडेट के लिए कोड को आसानी से रैंक-वन डाउनडेट करने के लिए अनुकूलित किया जा सकता है: किसी को केवल असाइनमेंट में दो अतिरिक्त को बदलने की आवश्यकता है r और L((k+1):n, k) घटाव द्वारा.

पंक्तियों और स्तंभों को जोड़ना और हटाना

यदि हमारे पास एक सममित और सकारात्मक निश्चित मैट्रिक्स है $\mathbf {A}$ ब्लॉक रूप में दर्शाया गया है

$\mathbf {A} ={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}$

और इसका ऊपरी चोलेस्की कारक

$\mathbf {L} ={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}},$

फिर एक नए मैट्रिक्स के लिए ${\tilde {\mathbf {A} }}$, जो वैसा ही है $\mathbf {A}$ लेकिन नई पंक्तियों और स्तंभों के सम्मिलन के साथ,

${\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}$

हम चॉलेस्की गुणनखंड को खोजने में रुचि रखते हैं ${\tilde {\mathbf {A} }}$, जिसे हम कहते हैं ${\tilde {\mathbf {S} }}$, संपूर्ण अपघटन की सीधे गणना किए बिना।

${\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}.\end{aligned}}$

लिखना $\mathbf {A} \setminus \mathbf {b}$ के समाधान के लिए $\mathbf {A} \mathbf {x} =\mathbf {b}$, जो त्रिकोणीय मैट्रिक्स के लिए आसानी से पाया जा सकता है, और ${\text{chol}}(\mathbf {M} )$ चोलेस्की अपघटन के लिए $\mathbf {M}$, निम्नलिखित संबंध पाए जा सकते हैं:

${\begin{aligned}\mathbf {S} _{11}&=\mathbf {L} _{11},\\\mathbf {S} _{12}&=\mathbf {L} _{11}^{\mathrm {T} }\setminus \mathbf {A} _{12},\\\mathbf {S} _{13}&=\mathbf {L} _{13},\\\mathbf {S} _{22}&=\mathrm {chol} \left(\mathbf {A} _{22}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{12}\right),\\\mathbf {S} _{23}&=\mathbf {S} _{22}^{\mathrm {T} }\setminus \left(\mathbf {A} _{23}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{13}\right),\\\mathbf {S} _{33}&=\mathrm {chol} \left(\mathbf {L} _{33}^{\mathrm {T} }\mathbf {L} _{33}-\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}$

यदि हम पंक्ति और स्तंभ आयामों को उचित रूप से (शून्य सहित) सेट करते हैं, तो इन सूत्रों का उपयोग किसी भी स्थिति में पंक्तियों या स्तंभों के सम्मिलन के बाद चॉलेस्की कारक को निर्धारित करने के लिए किया जा सकता है। उलटी समस्या, जब हमारे पास है

${\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}$

ज्ञात चोलेस्की अपघटन के साथ

${\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}\end{aligned}}$

और चोलेस्की कारक का निर्धारण करना चाहते हैं

${\begin{aligned}\mathbf {L} &={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}}\end{aligned}}$

मैट्रिक्स का $\mathbf {A}$ पंक्तियों और स्तंभों को हटाकर,

${\begin{aligned}\mathbf {A} &={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}},\end{aligned}}$

निम्नलिखित नियम उत्पन्न करता है:

${\begin{aligned}\mathbf {L} _{11}&=\mathbf {S} _{11},\\\mathbf {L} _{13}&=\mathbf {S} _{13},\\\mathbf {L} _{33}&=\mathrm {chol} \left(\mathbf {S} _{33}^{\mathrm {T} }\mathbf {S} _{33}+\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}$

ध्यान दें कि ऊपर दिए गए समीकरणों में एक नए मैट्रिक्स के चोल्स्की अपघटन को ढूंढना शामिल है, सभी फॉर्म के हैं ${\tilde {\mathbf {A} }}=\mathbf {A} \pm \mathbf {x} \mathbf {x} ^{*}$, जो उन्हें पिछले अनुभाग में विस्तृत अद्यतन और डाउनडेट प्रक्रियाओं का उपयोग करके कुशलतापूर्वक गणना करने की अनुमति देता है।

सकारात्मक अर्ध-निश्चित मैट्रिक्स के लिए प्रमाण

सीमित तर्क द्वारा प्रमाण

उपरोक्त एल्गोरिदम दर्शाते हैं कि प्रत्येक सकारात्मक निश्चित मैट्रिक्स $\mathbf {A}$ चॉलेस्की अपघटन है। इस परिणाम को एक सीमित तर्क द्वारा सकारात्मक अर्ध-निश्चित मामले तक बढ़ाया जा सकता है। तर्क पूरी तरह से रचनात्मक नहीं है, यानी, यह चोल्स्की कारकों की गणना के लिए कोई स्पष्ट संख्यात्मक एल्गोरिदम नहीं देता है।

अगर $\mathbf {A}$ एक $n\times n$ सकारात्मक-निश्चित मैट्रिक्स|सकारात्मक अर्ध-निश्चित मैट्रिक्स, फिर अनुक्रम ${\textstyle \left(\mathbf {A} _{k}\right)_{k}:=\left(\mathbf {A} +{\frac {1}{k}}\mathbf {I} _{n}\right)_{k}}$ सकारात्मक-निश्चित मैट्रिक्स से युक्त है। (यह, उदाहरण के लिए, बहुपद कार्यात्मक कलन के लिए वर्णक्रमीय मानचित्रण प्रमेय का तत्काल परिणाम है।) इसके अलावा,

$\mathbf {A} _{k}\rightarrow \mathbf {A} \quad {\text{for}}\quad k\rightarrow \infty$ ऑपरेटर मानक में. सकारात्मक निश्चित मामले से, प्रत्येक $\mathbf {A} _{k}$ चॉलेस्की अपघटन है $\mathbf {A} _{k}=\mathbf {L} _{k}\mathbf {L} _{k}^{*}$. ऑपरेटर मानदंड की संपत्ति के अनुसार,

$\|\mathbf {L} _{k}\|^{2}\leq \|\mathbf {L} _{k}\mathbf {L} _{k}^{*}\|=\|\mathbf {A} _{k}\|\,.$

$\leq$ h> इसलिए धारण करता है $M_{n}(\mathbb {C} )$ ऑपरेटर मानदंड से सुसज्जित एक C* बीजगणित है। इसलिए $\left(\mathbf {L} _{k}\right)_{k}$ ऑपरेटरों के बनच स्थान में एक घिरा हुआ सेट है, इसलिए अपेक्षाकृत कॉम्पैक्ट है (क्योंकि अंतर्निहित वेक्टर स्पेस परिमित-आयामी है)।

नतीजतन, इसका एक अभिसारी परिणाम है, जिसे इसके द्वारा भी दर्शाया जाता है $\left(\mathbf {L} _{k}\right)_{k}$, सीमा के साथ $\mathbf {L}$. यह आसानी से जांचा जा सकता है कि यह $\mathbf {L}$ वांछित गुण हैं, अर्थात $\mathbf {A} =\mathbf {L} \mathbf {L} ^{*}$, और $\mathbf {L}$ गैर-नकारात्मक विकर्ण प्रविष्टियों के साथ निचला त्रिकोणीय है: सभी के लिए $x$ और $y$,

$\langle \mathbf {A} x,y\rangle =\left\langle \lim \mathbf {A} _{k}x,y\right\rangle =\langle \lim \mathbf {L} _{k}\mathbf {L} _{k}^{*}x,y\rangle =\langle \mathbf {L} \mathbf {L} ^{*}x,y\rangle \,.$

इसलिए, $\mathbf {A} =\mathbf {L} \mathbf {L} ^{*}$. क्योंकि अंतर्निहित वेक्टर स्थान परिमित-आयामी है, ऑपरेटरों के स्थान पर सभी टोपोलॉजी समतुल्य हैं। इसलिए $\left(\mathbf {L} _{k}\right)_{k}$ आदत है $\mathbf {L}$ सामान्य अर्थ में $\left(\mathbf {L} _{k}\right)_{k}$ आदत है $\mathbf {L}$ प्रवेशवार. इसका तात्पर्य यह है कि, प्रत्येक के बाद से $\mathbf {L} _{k}$ गैर-नकारात्मक विकर्ण प्रविष्टियों के साथ निचला त्रिकोणीय है, $\mathbf {L}$ ई आल्सो।

क्यूआर अपघटन द्वारा प्रमाण

होने देना $\mathbf {A}$ एक सकारात्मक-निश्चित मैट्रिक्स बनें|सकारात्मक अर्ध-निश्चित हर्मिटियन मैट्रिक्स। फिर इसे मैट्रिक्स के वर्गमूल के उत्पाद के रूप में लिखा जा सकता है, $\mathbf {A} =\mathbf {B} \mathbf {B} ^{*}$. अब क्यूआर अपघटन को लागू किया जा सकता है $\mathbf {B} ^{*}$, जिसके परिणामस्वरूप $\mathbf {B} ^{*}=\mathbf {Q} \mathbf {R}$ , कहाँ $\mathbf {Q}$ एकात्मक है और $\mathbf {R}$ ऊपरी त्रिकोणीय है. अपघटन को मूल समानता में सम्मिलित करने से परिणाम प्राप्त होते हैं $A=\mathbf {B} \mathbf {B} ^{*}=(\mathbf {QR} )^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {Q} ^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {R}$. सेटिंग $\mathbf {L} =\mathbf {R} ^{*}$ प्रमाण पूरा करता है.

सामान्यीकरण

चोल्स्की गुणनखंडन को सामान्यीकृत किया जा सकता है से (आवश्यक रूप से परिमित नहीं) ऑपरेटर प्रविष्टियों के साथ मैट्रिक्स। होने देना $\{{\mathcal {H}}_{n}\}$ हिल्बर्ट स्थानों का एक क्रम बनें। ऑपरेटर मैट्रिक्स पर विचार करें

$\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}&\;\\\mathbf {A} _{12}^{*}&\mathbf {A} _{22}&\mathbf {A} _{23}&\;\\\mathbf {A} _{13}^{*}&\mathbf {A} _{23}^{*}&\mathbf {A} _{33}&\;\\\;&\;&\;&\ddots \end{bmatrix}}$

प्रत्यक्ष योग पर कार्य करना

${\mathcal {H}}=\bigoplus _{n}{\mathcal {H}}_{n},$

जहां प्रत्येक

$\mathbf {A} _{ij}:{\mathcal {H}}_{j}\rightarrow {\mathcal {H}}_{i}$

एक परिबद्ध संचालिका है. यदि A इस अर्थ में धनात्मक (अर्धनिश्चित) है कि सभी परिमित k के लिए और किसी के लिए भी

$h\in \bigoplus _{n=1}^{k}{\mathcal {H}}_{k},$

अपने पास $\langle h,\mathbf {A} h\rangle \geq 0$, तो एक निचला त्रिकोणीय ऑपरेटर मैट्रिक्स L मौजूद है जैसे कि A = LL*। कोई व्यक्ति L की विकर्ण प्रविष्टियों को भी सकारात्मक मान सकता है।

प्रोग्रामिंग पुस्तकालयों में कार्यान्वयन

• सी प्रोग्रामिंग भाषा: जीएनयू वैज्ञानिक पुस्तकालय चोलेस्की अपघटन के कई कार्यान्वयन प्रदान करता है।
• मैक्सिमा (सॉफ्टवेयर) कंप्यूटर बीजगणित प्रणाली: फ़ंक्शन cholesky चोल्स्की अपघटन की गणना करता है।
• जीएनयू ऑक्टेव संख्यात्मक संगणना प्रणाली चोल्स्की अपघटन की गणना, अद्यतन और लागू करने के लिए कई कार्य प्रदान करती है।
• LAPACK लाइब्रेरी चोलेस्की अपघटन का उच्च प्रदर्शन कार्यान्वयन प्रदान करती है जिसे फोरट्रान, सी (प्रोग्रामिंग भाषा) और अधिकांश भाषाओं से एक्सेस किया जा सकता है।
• पायथन (प्रोग्रामिंग भाषा) में, फ़ंक्शन cholesky से numpy.linalg मॉड्यूल चॉलेस्की अपघटन करता है।
• मतलब में, chol फ़ंक्शन चोल्स्की अपघटन देता है। ध्यान दें कि chol डिफ़ॉल्ट रूप से इनपुट मैट्रिक्स के ऊपरी त्रिकोणीय कारक का उपयोग करता है, अर्थात यह गणना करता है $A=R^{*}R$ कहाँ $R$ ऊपरी त्रिकोणीय है. इसके बजाय निचले त्रिकोणीय कारक का उपयोग करने के लिए एक ध्वज पारित किया जा सकता है।
• आर (प्रोग्रामिंग भाषा) में, द chol फ़ंक्शन चोल्स्की अपघटन देता है।
• जूलिया (प्रोग्रामिंग भाषा) में, cholesky से कार्य करें LinearAlgebra मानक पुस्तकालय चोल्स्की अपघटन देता है।
• गणित में, फ़ंक्शनCholeskyDecompositionमैट्रिक्स पर लागू किया जा सकता है।
• C++ में, एकाधिक रैखिक बीजगणित पुस्तकालय इस अपघटन का समर्थन करते हैं:
  • आर्माडिलो (C++ लाइब्रेरी) कमांड की आपूर्ति करता है chol चोलेस्की अपघटन करने के लिए।
  • Eigen (C++ लाइब्रेरी) विरल और सघन मैट्रिक्स दोनों के लिए चॉलेस्की गुणनखंड प्रदान करता है।
  • जड़ पैकेज में, TDecompChol क्लास उपलब्ध है.

• एनालिटिका (सॉफ्टवेयर) में, फ़ंक्शन Decompose चोल्स्की अपघटन देता है।
• Apache Commons Math लाइब्रेरी का एक कार्यान्वयन है जिसका उपयोग जावा, स्काला और किसी भी अन्य JVM भाषा में किया जा सकता है।

यह भी देखें

• साइकिल रैंक
• अधूरा चोलेस्की गुणनखंडन
• मैट्रिक्स अपघटन
• न्यूनतम डिग्री एल्गोरिदम
• मैट्रिक्स का वर्गमूल
• सिल्वेस्टर का जड़त्व का नियम
• प्रतीकात्मक चोल्स्की अपघटन

संदर्भ

• Dereniowski, Dariusz; Kubale, Marek (2004). "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs". 5th International Conference on Parallel Processing and Applied Mathematics (PDF). Lecture Notes on Computer Science. Vol. 3019. Springer-Verlag. pp. 985–992. doi:10.1007/978-3-540-24669-5_127. ISBN 978-3-540-21946-0. Archived from the original (PDF) on 2011-07-16.
• Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. 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 (1997). Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9.
• Osborne, Michael (2010). Bayesian Gaussian Processes for Sequential Prediction, Optimisation and Quadrature (PDF) (thesis). University of Oxford.
• Ruschel, João Paulo Tarasconi, Bachelor degree "Parallel Implementations of the Cholesky Decomposition on CPUs and GPUs" Universidade Federal Do Rio Grande Do Sul, Instituto De Informatica, 2016, pp. 29-30.

बाहरी संबंध

विज्ञान का इतिहास

• रैखिक समीकरणों की प्रणालियों के संख्यात्मक रिज़ॉल्यूशन पर, चोलेस्की की 1910 की पांडुलिपि, ऑनलाइन और BibNum पर विश्लेषित की गई है। (in French and English) [for English, click 'A télécharger']

जानकारी

• "Cholesky factorization", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• चोल्स्की डीकंपोजिशन, डेटा एनालिसिस ब्रीफबुक
• Cholesky Decomposition www.math-linux.com पर
• Cholesky Decomposition made Simple विज्ञान मेन्डरथल पर

कंप्यूटर कोड

• LAPACK घने रैखिक बीजगणित समस्याओं को हल करने के लिए फोरट्रान सबरूटीन्स का एक संग्रह है (DPOTRF, DPOTRF2, विवरण प्रदर्शन)
• ALGLIB में C++, C#, डेल्फ़ी, विज़ुअल बेसिक आदि के लिए LAPACK का आंशिक पोर्ट शामिल है (spdmatrixcholesky, hpdmatrixcholesky)
• libflame LAPACK कार्यक्षमता वाली एक C लाइब्रेरी है।
• नोट्स और वीडियो ऑस्टिन में टेक्सास विश्वविद्यालय में चोल्स्की फैक्टराइजेशन के उच्च-प्रदर्शन कार्यान्वयन पर।
• Cholesky: TBB + Threads + SSE एक पुस्तक है जो TBB, थ्रेड्स और SSE (स्पेनिश में) के साथ CF के कार्यान्वयन की व्याख्या करती है।
• लाइब्रेरी सेरेस सॉल्वर Google द्वारा।
• एलडीएल अपघटन मैटलैब में दिनचर्या।
• आर्मडिलो एक C++ रैखिक बीजगणित पैकेज है
• रोसेटा कोड एक प्रोग्रामिंग क्रिस्टोमैथी साइट है। पेज विषय पर।
• AlgoWiki एल्गोरिदम के गुणों और उनके कार्यान्वयन की विशेषताओं का एक खुला विश्वकोश है पेज विषय पर
• Intel® oneAPI गणित कर्नेल लाइब्रेरी संख्यात्मक कंप्यूटिंग के लिए इंटेल-अनुकूलित गणित लाइब्रेरी outines/lapack-linear-eqation-routines/lapack-linear-equation-computational-routines/matrix-factorization-lapack-computational-routines/potrf.html#potrf ?potrf, पैक-रूटीन्स/लैपैक-रैखिक-समीकरण-रूटीन्स/लैपैक-रैखिक-समीकरण-कम्प्यूटेशनल-रूटीन्स/सॉल्विंग-सिस्टम्स-ऑफ-लीनियर-इक्वेशन्स-लैपैक-कम्प्यूटेशनल-रूटीन्स/पोटर्स.html#potrs ?potrs

सिमुलेशन में मैट्रिक्स का उपयोग

• सहसंबद्ध यादृच्छिक चर और स्टोकेस्टिक प्रक्रियाएं उत्पन्न करना, मार्टिन हॉफ, कोलंबिया विश्वविद्यालय

ऑनलाइन कैलकुलेटर

• ऑनलाइन मैट्रिक्स कैलकुलेटर ऑनलाइन मैट्रिक्स का चॉलेस्की अपघटन करता है।

श्रेणी:संचालक सिद्धांत श्रेणी:मैट्रिक्स अपघटन श्रेणी:संख्यात्मक रैखिक बीजगणित श्रेणी: उदाहरण MATLAB/ऑक्टेव कोड वाले लेख