त्रिविकर्णिक आव्यूह कलनविधि
त्रिविकर्णिक आव्यूह कलनविधि, (अंग्रेजी - Tridiagonal Matrix Algorithm (TDMA)) जिसे थॊमस कलनविधि (Thomas Algorithm) के नाम से भी जाना जाता है, गॊस निरसन (Gauss elimination) का सरलीकृत रूप है जिसका उपयोग त्रिविकर्णिक आव्यूह के समुच्चय को हल करने के लिये किया जाता है।
एक त्रिविकर्णिक आव्यूहों के समुच्चय को इस तरह व्यक्त किया जा सकता है -
- <math>
a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i, \,\!</math>,
जहाँ, <math> a_1 = 0\, </math> और <math> c_n = 0\, </math>। आव्यूह स्वरूप में -
<math> \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]. </math>
ऎसे तंत्र का हल O(n^3) की अपेक्षा O(n) में ही हो जाता है।
विधि
Forward elimination phase
- <math>b'_1 = b_1 \,\!</math>
- <math>d'_1 = d_1\,\!</math>
- for k = 2 step 1 until n do
- <math>m = {{a_k } \over {b'_{k - 1} }} \,\!</math>
- <math> b'_k = b_k - mc_{k - 1} \,\!</math>
- <math> d'_k = d_k - md'_{k - 1} \,\!</math>
- end loop (k)
Backward substitution phase
- <math> x_n = {{d'_n } \over {b'_n }} \,\!</math>
- for k = n−1 step −1 until 1 do
- <math> x_k = {{d'_k - c_k x_{k + 1} } \over {b'_k }} \,\!</math>
- end loop (k)
विविध-रूप
कुछ स्थितियों में, खासकर तब जब आवर्ती सीमा-दशा (periodic boundary conditions) का योग हो, एक थोङा अलग स्वरूप प्रयुक्त होता है -
- <math>
a_1 x_{n} + b_1 x_1 + c_1 x_2 = d_1, \,\! </math>
- <math>
a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} = d_i,\quad\quad i = 2,\ldots,n-1 \,\! </math>
- <math>
a_n x_{n-1} + b_n x_n + c_n x_1 = d_n. \,\! </math>
इस स्थिति में, शेरमॆन-मॊरिसन सूत्र (Sherman-Morrison formula) का प्रयोग गॊस की विधि के अतिरिक्त अभिकलन से बचने पर साथ ही साथ थॊमस अल्गोरिद्म के प्रयोग के लिये किया जाता है।
अन्य दशाओं में, जब तंत्र block tridiagonal हो, जिसमें छोटे अनुव्यूह (submatrices) उपर्युक्त आव्यूह में एक-एक अवयव individual elements के रूप में सजे हों (उदाहरनार्थ - the 2D Poisson problem)। ऎसी स्थितियों के लिये गॊस की निरसन विधि (Gaussian elimination) के सरलीकृत रूप विकसित किये गए हैं।