त्रिविकर्णीय मैट्रिक्स

रैखिक बीजगणित में, एक त्रिविकर्ण आव्यूह एक बैंड आव्यूह होता है जिसमें केवल मुख्य विकर्ण, उपविकर्ण/निचले विकर्ण (इसके नीचे पहला विकर्ण), और सुप्राडियागोनल/ऊपरी विकर्ण (मुख्य विकर्ण के ऊपर पहला विकर्ण) पर गैर-शून्य तत्व होते हैं। उदाहरण के लिए, निम्नलिखित आव्यूह (गणित) त्रिविकर्ण आव्यूह एल्गोरिदम होता hotaहै:

${\begin{pmatrix}1&4&0&0\\3&4&1&0\\0&2&3&4\\0&0&1&3\\\end{pmatrix}}.$

एक त्रिविकर्ण आव्यूह का निर्धारक उसके तत्वों के सातत्य (गणित) द्वारा दिया जाता है। एक सममित (या हर्मिटियन) आव्यूह का त्रिदिकोणीय रूप में ऑर्थोगोनल परिवर्तन लैंज़ोस एल्गोरिदम के साथ किया जा सकता है।

गुण

एक त्रिविकर्ण आव्यूह एक आव्यूह है जो ऊपरी और निचले हेसेनबर्ग आव्यूह दोनों है। विशेष रूप से, एक त्रिविकर्ण आव्यूह p 1-by-1 और q 2-by-2 आव्यूह का सीधा योग है जैसे कि p + q/2 = n- त्रिविकर्ण का आयाम होता है। चूंकि एक सामान्य त्रिविकर्ण आव्यूह आवश्यक रूप से सममित आव्यूह या हर्मिटियन आव्यूह नहीं है, उनमें से कई जो रैखिक बीजगणित समस्याओं को हल करते समय उत्पन्न होते हैं उनमें इनमें से एक गुण होता है। इसके अतिरिक्त , यदि एक वास्तविक त्रिविकर्ण आव्यूह A सभी k के लिए, a_k,k+1 a_k+1,k > 0 को संतुष्ट करता है, जिससे की इसकी प्रविष्टियों के चिह्न सममित हों, तो यह आधार आव्यूह के विकर्ण परिवर्तन द्वारा हर्मिटियन आव्यूह के समान (रैखिक बीजगणित) होता है। इसलिए, इसके ईजेनमान ​​​​वास्तविक होते हैं। यदि हम सख्त असमानता को a_k,k+1 a_k+1,k ≥ 0 से प्रतिस्थापित करते हैं तो निरंतरता से, आइगेनवैल्यू अभी भी वास्तविक होने की गारंटी होती है, किन्तु आव्यूह को अब हर्मिटियन आव्यूह के समान होने की आवश्यकता नहीं है।

सभी n × n त्रिविकर्ण आव्यूहों का समुच्चय (गणित) एक 3n-2 आयामी सदिश बिन्दु बनाता है।

कई रैखिक बीजगणित कलन विधि को विकर्ण आव्यूह पर लागू होने पर अधिक कम संगणनात्मक जटिलता सिद्धांत की आवश्यकता होती है, और यह सुधार अधिकांशतः त्रिविकर्ण आव्यूह पर भी लागू होता है।

निर्धारक

Main article: अनुवर्ती ( गणितकार)

क्रम n के त्रिविकर्ण आव्यूह A के निर्धारक की गणना तीन-अवधि के पुनरावृत्ति संबंध से की जा सकती है। लिखें f₁ = |a₁| = a₁ (अर्थात , f₁ 1 बटा 1 आव्यूह का निर्धारक है जिसमें केवल a₁ सम्मलित होते है), और जाने

$f_{n}={\begin{vmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{vmatrix}}.$

अनुक्रम (f_i) को सतत (गणित) कहा जाता है और पुनरावृत्ति संबंध को संतुष्ट करता है

$f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}$

प्रारंभिक मूल्यों के साथf₀ = 1और f₋₁ = 0 इस सूत्र का उपयोग करके एक त्रिविकर्ण आव्यूह के निर्धारक की गणना करने की लागत n में रैखिक है, जबकि एक सामान्य आव्यूह के लिए लागत घन होता है।

उलटा

एक गैर-एकवचन त्रिविकर्ण आव्यूह टी का व्युत्क्रम आव्यूह

$T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}$

द्वारा दिया गया है

$(T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i<j\\\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i=j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ if }}i>j\\\end{cases}}$

जहां θ_i पुनरावृत्ति संबंध को संतुष्ट करें

$\theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\qquad i=2,3,\ldots ,n$

प्रारंभिक शर्तों के साथ θ₀ = 1, θ₁ = a₁ और ϕ_i संतुष्ट करना

$\phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\qquad i=n-1,\ldots ,1$

प्रारंभिक शर्तों के साथ ϕ_n+1 = 1 और ϕ_n = a_n

संवृत रूप समाधानों की गणना विशेष स्थतियों के लिए की जा सकती है जैसे कि सभी विकर्ण और ऑफ-विकर्ण तत्वों के साथ सममित आव्यूह या टोएप्लिट्ज़ मैट्रिसेस और सामान्य मामले के लिए भी. सामान्यतः, त्रिविकर्ण आव्यूह का व्युत्क्रम एक अर्धविभाज्य आव्यूह होता है और इसके विपरीत होते है।

रैखिक प्रणाली का समाधान

Main article: त्रिविकर्ण आव्यूह एल्गोरिदम

समीकरणों की एक प्रणाली Ax=b$b\in \mathbb {R} ^{n}$ गाऊसी उन्मूलन के एक कुशल रूप द्वारा हल किया जा सकता है जब ए त्रिविकर्ण आव्यूह एल्गोरिथ्म कहलाता है, जिसके लिए O(n) संचालन की आवश्यकता होती है।

आइजेनवैल्यू

जब एक त्रिदिकोणीय आव्यूह टोएप्लिट्ज़ आव्यूह भी होता है, तो इसके eigenvalues ​​​​के लिए एक सरल संवृत रूप त्:

$a+2{\sqrt {bc}}\cos \left({\frac {k\pi }{n+1}}\right),\qquad k=1,\ldots ,n.$

एक वास्तविक सममित आव्यूह त्रिदिकोणीय आव्यूह में वास्तविक eigenvalues ​​​​होते हैं, और यदि सभी ऑफ-विकर्ण तत्व गैर-शून्य हैं तो सभी eigenvalues ​​​​eigenvalues ​​​​और eigenvectors बीजगणितीय बहुलता विशिष्ट (सरल) होते हैं। यादृच्छिक रूप से परिमित परिशुद्धता के लिए एक वास्तविक सममित त्रिदिकोणीय आव्यूह के eigenvalues ​​​​की संख्यात्मक गणना के लिए कई विधियां सम्मलित होते हैं, सामान्यतः इसकी आवश्यकता होती है $O(n^{2})$ आकार के आव्यूह के लिए संचालन $n\times n$, चूंकि तेज़ एल्गोरिदम सम्मलित हैं जिनकी (समानांतर गणना के बिना) केवल आवश्यकता होती है $O(n\log n)$ एक साइड नोट के रूप में, एक असंतुलित सममित त्रिदिकोणीय आव्यूह एक आव्यूह है जिसमें त्रिदिकोण के गैर-शून्य ऑफ-विकर्ण तत्व होते हैं, जहां आइगेनवैल्यू अलग-अलग होते हैं जबकि आइजेनवेक्टर एक स्केल फैक्टर तक अद्वितीय होते हैं और परस्पर ऑर्थोगोनल होते हैं।

सममित त्रिविकर्ण आव्यूह से समानता

असममित या गैर सममित त्रिदिकोणीय आव्यूह के लिए कोई समानता परिवर्तन का उपयोग करके ईगेंडेरचना की गणना कर सकता है। एक वास्तविक त्रिविकर्णीय, गैरसममितीय आव्यूह दिया गया है

$T={\begin{pmatrix}a_{1}&b_{1}\\c_{1}&a_{2}&b_{2}\\&c_{2}&\ddots &\ddots \\&&\ddots &\ddots &b_{n-1}\\&&&c_{n-1}&a_{n}\end{pmatrix}}$

कहाँ $b_{i}\neq c_{i}$. मान लें कि ऑफ-विकर्ण प्रविष्टियों का प्रत्येक उत्पाद है केवल सकारात्मक $b_{i}c_{i}>0$ और एक परिवर्तन आव्यूह को परिभाषित करें $D$ द्वारा

$D:=\operatorname {diag} (\delta _{1},\dots ,\delta _{n})\quad {\text{for}}\quad \delta _{i}:={\begin{cases}1&,\,i=1\\{\sqrt {\frac {c_{i-1}\dots c_{1}}{b_{i-1}\dots b_{1}}}}&,\,i=2,\dots ,n\,.\end{cases}}$

आव्यूह समानता $D^{-1}TD$ एक सममित त्रिविकर्ण आव्यूह उत्पन्न करता है $J$ द्वारा:

$J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}&a_{n}\end{pmatrix}}\,.$

ध्यान दें कि $T$ और $J$ समान eigenvalues ​​​​हैं।

कंप्यूटर प्रोग्रामिंग

एक परिवर्तन जो एक सामान्य आव्यूह को हेसेनबर्ग रूप में कम कर देता है, एक हर्मिटियन आव्यूह को त्रिविकर्ण रूप में कम कर देगा। इसलिए, कई eigenvalue एल्गोरिथ्म, जब हर्मिटियन आव्यूह पर लागू होते हैं, तो पहले चरण के रूप में इनपुट हर्मिटियन आव्यूह को (सममित वास्तविक) त्रिविकर्ण रूप में कम कर देते हैं। एक विशेष आव्यूह प्रतिनिधित्व का उपयोग करके एक त्रिविकर्ण आव्यूह को सामान्य आव्यूह की तुलना में अधिक कुशलता से संग्रहीत किया जा सकता है। उदाहरण के लिए, LAPACK फोरट्रान पैकेज तीन एक-आयामी सरणियों में क्रम n के एक असममित त्रिविकर्ण आव्यूह को संग्रहीत करता है, एक लंबाई n में विकर्ण तत्व होते हैं, और दो लंबाई n - 1 में उपविकर्ण और अतिविकर्ण तत्व होते हैं।

अनुप्रयोग

एक आयामी प्रसार या ऊष्मा समीकरण के स्थान में विवेकीकरण

${\frac {\partial u(t,x)}{\partial t}}=\alpha {\frac {\partial ^{2}u(t,x)}{\partial x^{2}}}$

दूसरे क्रम के केंद्रीय परिमित अंतर का उपयोग करने से परिणाम मिलता है

${\begin{pmatrix}{\frac {\partial u_{1}(t)}{\partial t}}\\{\frac {\partial u_{2}(t)}{\partial t}}\\\vdots \\{\frac {\partial u_{N}(t)}{\partial t}}\end{pmatrix}}={\frac {\alpha }{\Delta x}}{\begin{pmatrix}-2&1&0&\ldots &0\\1&-2&1&\ddots &\vdots \\0&\ddots &\ddots &\ddots &0\\\vdots &&1&-2&1\\0&\ldots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}(t)\\u_{2}(t)\\\vdots \\u_{N}(t)\\\end{pmatrix}}$

विवेकाधीन स्थिरांक के साथ $\Delta x$. आव्यूह त्रिविकर्णीय है $a_{i}=-2$ और $b_{i}=c_{i}=1$. ध्यान दें: यहां कोई सीमा शर्तों का उपयोग नहीं किया गया है।

यह भी देखें

• पंचकोणीय आव्यूह
• जैकोबी आव्यूह (ऑपरेटर)

बाहरी संबंध

• Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
• Moawwad El-Mikkawy, Abdelrahman Karawia (2006). "Inversion of general tridiagonal matrices" (PDF). Applied Mathematics Letters. 19 (8): 712–720. doi:10.1016/j.aml.2005.11.012. Archived from the original (PDF) on 2011-07-20.
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form
• Tridiagonal linear system solver in C++