त्रिविकर्णिक आव्यूह कलनविधि

त्रिविकर्णिक आव्यूह कलनविधि, (अंग्रेजी - Tridiagonal Matrix Algorithm (TDMA)) जिसे थॊमस कलनविधि (Thomas Algorithm) के नाम से भी जाना जाता है, गॊस निरसन (Gauss elimination) का सरलीकृत रूप है जिसका उपयोग त्रिविकर्णिक आव्यूह के समुच्चय को हल करने के लिये किया जाता है।

एक त्रिविकर्णिक आव्यूहों के समुच्चय को इस तरह व्यक्त किया जा सकता है -

$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i},\,\!$,

जहाँ, $a_{1}=0\,$ और $c_{n}=0\,$। आव्यूह स्वरूप में -

$\left[{\begin{matrix}{b_{1}}&{c_{1}}&{}&{}&{0}\\{a_{2}}&{b_{2}}&{c_{2}}&{}&{}\\{}&{a_{3}}&{b_{3}}&\cdot &{}\\{}&{}&\cdot &\cdot &{c_{n-1}}\\{0}&{}&{}&{a_{n}}&{b_{n}}\\\end{matrix}}\right]\left[{\begin{matrix}{x_{1}}\\{x_{2}}\\\cdot \\\cdot \\{x_{n}}\\\end{matrix}}\right]=\left[{\begin{matrix}{d_{1}}\\{d_{2}}\\\cdot \\\cdot \\{d_{n}}\\\end{matrix}}\right].$

ऎसे तंत्र का हल O(n^3) की अपेक्षा O(n) में ही हो जाता है।

विधि

Forward elimination phase

$b'_{1}=b_{1}\,\!$

$d'_{1}=d_{1}\,\!$

for k = 2 step 1 until n do

$m={{a_{k}} \over {b'_{k-1}}}\,\!$

$b'_{k}=b_{k}-mc_{k-1}\,\!$

$d'_{k}=d_{k}-md'_{k-1}\,\!$

end loop (k)

Backward substitution phase

$x_{n}={{d'_{n}} \over {b'_{n}}}\,\!$

for k = n−1 step −1 until 1 do

$x_{k}={{d'_{k}-c_{k}x_{k+1}} \over {b'_{k}}}\,\!$

end loop (k)

विविध-रूप

कुछ स्थितियों में, खासकर तब जब आवर्ती सीमा-दशा (periodic boundary conditions) का योग हो, एक थोङा अलग स्वरूप प्रयुक्त होता है -

$a_{1}x_{n}+b_{1}x_{1}+c_{1}x_{2}=d_{1},\,\!$

$a_{i}x_{i-1}+b_{i}x_{i}+c_{i}x_{i+1}=d_{i},\quad \quad i=2,\ldots ,n-1\,\!$

$a_{n}x_{n-1}+b_{n}x_{n}+c_{n}x_{1}=d_{n}.\,\!$

इस स्थिति में, शेरमॆन-मॊरिसन सूत्र (Sherman-Morrison formula) का प्रयोग गॊस की विधि के अतिरिक्त अभिकलन से बचने पर साथ ही साथ थॊमस अल्गोरिद्म के प्रयोग के लिये किया जाता है।

अन्य दशाओं में, जब तंत्र block tridiagonal हो, जिसमें छोटे अनुव्यूह (submatrices) उपर्युक्त आव्यूह में एक-एक अवयव individual elements के रूप में सजे हों (उदाहरनार्थ - the 2D Poisson problem)। ऎसी स्थितियों के लिये गॊस की निरसन विधि (Gaussian elimination) के सरलीकृत रूप विकसित किये गए हैं।

सन्दर्भ

• Conte, S.D., and deBoor, C. (1972). Elementary Numerical Analysis. McGraw-Hill, New York.सीएस1 रखरखाव: एक से अधिक नाम: authors list (link)
• This article incorporates text from the article matrix algorithm - TDMA (Thomas algorithm) Tridiagonal matrix algorithm - TDMA (Thomas algorithm) on CFD-Wiki that is under the GFDL license.