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

विकिपीडिया, एक मुक्त ज्ञानकोष से

त्रिविकर्णिक आव्यूह कलनविधि, (अंग्रेजी - 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.।
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.

"http://hi.wikipedia.org../../../%E0%A4%A4/%E0%A5%8D/%E0%A4%B0/%E0%A4%A4%E0%A5%8D%E0%A4%B0%E0%A4%BF%E0%A4%B5%E0%A4%BF%E0%A4%95%E0%A4%B0%E0%A5%8D%E0%A4%A3%E0%A4%BF%E0%A4%95_%E0%A4%86%E0%A4%B5%E0%A5%8D%E0%A4%AF%E0%A5%82%E0%A4%B9_%E0%A4%95%E0%A4%B2%E0%A4%A8%E0%A4%B5%E0%A4%BF%E0%A4%A7%E0%A4%BF.html" से लिया गया

श्रेणियाँ: बीजगणित | गणित