삼각행렬 알고리즘

수치 선형 대수학에서, 토마스 알고리즘(Llewellyn Thomas의 이름을 딴)으로도 알려진 삼각형 행렬 알고리즘은 방정식의 삼각형 시스템을 푸는 데 사용될 수 있는 가우스 제거의 단순한 형태이다.n개의 미지수에 대한 삼각형 계는 다음과 같이 쓸 수 있다.

${displaystyle a_{i}x_{i}x_{i}+c_{i}x_{i+1}=d_{i}$

${\displaystyle {여기}_{}}$서 a 1 $=$ ({$displaystyle a_{$1}=$0})$ $및$ ${\displaystyle c_{}}$ ${\displaystyle \mathrm{n}}$ $=$ 0 ({$displaystyle c_{n$}=$0$입니다.

${\displaystyle{\begin{bmatrix}b_{1}&, c_{1}&,&&0\\a_{2}&, b_{2}&, c_{2}&, &, \\&, a_{3}&, b_{3}&, \ddots &, \\&,&\ddots &, \ddots &, c_{n-1}\\0&,&&a_{n}&, b_{n}\end{bmatrix}}\\x_{n}\end{bmatrix}}={\begin{bmatrix}d_{1}\\d_{2}\\d_{3}\\\vdots \\d_{n}\end{{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots.bmatrix}}.}$

이러한 시스템에서는 가우스 제거에 필요한 O${\displaystyle ({n\mathrm{}}^{}}$ 3$)\displaystyle$ O$(n^{3})$가 $n)\displaystyle$ O$($n) $연산$으로 솔루션을 얻을$$ 수 있습니다.${\displaystyle {첫}_{}}$ 번째 스위프에서는$$i\$style a_{$i$\}\text{'}$$s$가 삭제되고 그 후 (약칭) 역치환으로 이어집니다.이러한 행렬의 예는 일반적으로 1D 포아송 방정식과 자연 입방 스플라인 보간법의 이산화에서 발생한다.

Thomas 알고리즘은 일반적으로 안정적이지 않지만 행렬이 대각선 우세(행 또는 열에 의해)이거나 대칭 ^[1][2]양의 유한인 경우 등 여러 특수한 경우에서 안정적이다. Thomas 알고리즘의 안정성에 대한 보다 정밀한 특성화는 Higham Orem ^[3]9.12를 참조하십시오.일반적인 경우 안정성이 필요한 경우 대신 ^[2]부분 피벗(GEP)을 사용한 가우스 제거를 권장합니다.

방법

순방향 스위프는 다음과 같은 새 계수의 계산으로 구성되어 있으며, 소수로 새 계수를 나타냅니다.

${\displaystyle c'_{i}=param{case}{b_{i}},&i=1,\{\param{c_{i}{b_{i}-a_{i}c'_{i-1}}},&i=2,3,\param{i},n-1\end}cases}$

그리고.

${\displaystyle d'_{i}=param {d_{i}}{b_{i}}},&i=1,\{\param {d_{i}-a_{i}d'_{i-1}},{b_{i}-a_{i}c'_{i-1}}},&i=2,3\parames,\parames,{i}.$

그런 다음 백 치환을 통해 솔루션을 얻을 수 있습니다.

$({displaystyle x_{n}=d'_{n})$

$\displaystyle x_{i}=d'_{i}-c'_{i}x_{i+1},\display i=n-1,n-2,\ldots,1.}$

위의 방법에서는 원래 계수 벡터는 수정하지 않지만 새 계수를 추적해야 합니다.계수 벡터를 변경할 수 있는 경우 부기가 적은 알고리즘은 다음과 같습니다.

${\displaystyle i}$ ${\displaystyle =2}$,${\displaystyle 3}$,${\displaystyle \dots ,}$ n$,$ {\$displaystyle$ i$=2,3,\display,$ n$,}의 경우$,

$({displaystyle w=syslogac {a_{i}}{b_{i-1}}})$

$(\displaystyle b_{i}-wc_{i-1})$

$\displaystyle d_{i}:=d_{i}-wd_{i-1}$

백 치환에 이어

${\displaystyle x_{n}=syslogac {d_{n}}{b_{n}}},$

${displaystyle x_{i}=syslogac {d_{i}-c_{i}x_{i+1}}{b_{i}}\text{i}}i=n-1,n-2,\text,1}$

계수 벡터를 보존하지 않고 VBA 서브루틴에 실장하는 방법:

후보선수 삼각_행렬_알고리즘(N%, A#(), B#(), C#(), D#(), X#())     어둡다 i%, W#     위해서 i = 2 로. N         W = A(i) / B(i - 1)         B(i) = B(i) - W * C(i - 1)         D(i) = D(i) - W * D(i - 1)     다음 분. i     X(N) = D(N) / B(N)     위해서 i = N - 1 로. 1 걸음 -1         X(i) = (D(i) - C(i) * X(i + 1)) / B(i)     다음 분. i 끝. 후보선수 

파생

삼각행렬 알고리즘의 도출은 가우스 제거의 특별한 경우이다.

미지수는 ${\displaystyle {x\mathrm{}}_{}}$1,${\displaystyle \dots ,}$ ${\displaystyle x_{}}$n(\$displaystyle x_{1},\ldots,x_{n$이며, 풀어야 할 공식은 다음과 같습니다.

${\displaystyle{argentat}{4}&b_{1}x_{1}&+c_{1}x_{2}&=d_{1}\&a_{i}x_{i-1}&+b_{i}x_{i}&+c_{i}x_{i}x_{i}&=d_{i},\dots,-1\\&a_n}&{i}&{i}&n}&n}&n}&a_{i-1}&n}&a_n}&n}&a_n}&\end {alignedat}}$

첫 번째 방정식을 사용하여 ${\displaystyle \mathrm{두}}$ 번째$($ = 2 {$display i=2$ 방정식을 다음과 같이 수정하는 것을 고려합니다.

$\displaystyle({\mbox{flash2}})\cdot b_{1}-({\mbox{flash1})\cdot a_{2}}$

그 결과 다음과 같이 됩니다.

${\displaystyle(b_{2}b_{1}-c_{1}a_{2}x_{1}=d_{2}b_{1}-d_{1}a_{2}x_{2}.}$

${\displaystyle {x\mathrm{}}_{}}$ 1$(\$은 두 번째 방정식에서 제외되었습니다.세 번째 방정식의 수정된 두 번째 방정식에 대해 유사한 전략을 사용하면 다음과 같은 결과를 얻을 수 있습니다.

$({displaystyle (b_{3}(b_{2}b_{1}-c_{1}a_{2})-c_{2}b_{1}(b_{2}b_{1}-c_{1}-{1}a_{2}x_{3}{b}_{2})$

$이번$에는 $($ 스타일 $x_{2})$가 제외되었습니다.${\displaystyle {이}^{}}$ 절차를 n ${\displaystyle t^{}}$h 행($변경$) $n{\displaystyle {}^{}}$ ${\displaystyle t^{}}$h { $display style$ n^ { $th$} )까지 반복하면 x $(\$ style $x_{n$이라는 미지의 식만 관련됩니다.이 ${\displaystyle \mathrm{문제}}$는${\displaystyle }$(${\displaystyle n^{}}$- 1)$$ ($n-1)^{$th$$$}$방정식을 푸는 데 사용할 수 있습니다.또한 모든 미지의 문제가 해결될 때까지 계속됩니다.

분명히, 수정된 방정식의 계수는 명시적으로 언급될 경우 점점 더 복잡해집니다.절차를 검토함으로써 수정된 계수(틸드로 표기)를 재귀적으로 정의할 수 있습니다.

${\displaystyle {a}}_{i}=0,}$

${\displaystyle {b}}_{1}=b_{1},}$

${\displaystyle {b}_{i}=b_{i}{\tilde {b}_{i-1}-{\tilde {c}}_{i-1}a_{i},}$

${\displaystyle {c}}_{1}=c_{1},}$

${\displaystyle {c}_{i}=c_{i}{\tilde {b}}_{i-1},$

${\displaystyle {d}}_{1}=d_{1},}$

${\displaystyle {d}_{i}=d_{i}{\tilde {b}_{i-1}-{\tilde {d}}_{i-1}a_{i}}.\,}$

솔루션 프로세스를 더욱 빠르게 진행하기 위해 b${\displaystyle {\stackrel{}{}}_{}}$~$(\$})를 분할할 수 있습니다(위험이 0으로 분할되지 않은 경우). 새로운 수정 계수는 각각 소수(prime)로 표시됩니다.

${\displaystyle a'_{i}=0,}$

${\displaystyle b'_{i}=1,}$

${\displaystyle c'_{1}=syslogfrac {c_{1}}{b_{1}},},$

$({displaystyle c'_{i}=b_{i}-c'_{i-1}a_{i}}},$

${\displaystyle d'_{1}=syslogfrac {d_{1}}{b_{1}},},$

$({displaystyle d'_{i}=bfrac {d_{i}-d'_{i-1}a_{i}}{b_{i}-c'_{i-1}a_{i}}},)$

이는 위의 원래 시스템에 대해 정의된 것과 동일한 미지수와 계수를 가진 다음 시스템을 제공합니다.

${\displaystyle {array}{lcl}x_{i}x_{i+1}=d'_{i}\qquad & guaren\i=1,\ldots,n-1\x_{n}=d'_{n}\qquad & suaren\i=n.\\\end{array}},$

마지막 방정식은 오직 한 가지 알려지지 않은 것과 관련이 있다.이 문제를 차례로 풀면 다음 마지막 방정식이 미지수로 감소하므로 이 역치환을 사용하여 미지수를 모두 찾을 수 있습니다.

${\displaystyle x_{n}=d'_{n},}$

$\displaystyle x_{i}=d'_{i}-c'_{i}x_{i+1}\qquad;\i=n-1,n-2,\ldots,1.}$

변종

일부 상황, 특히 주기적인 경계 조건을 포함하는 상황에서는 약간 교란된 형태의 삼각형 시스템을 해결해야 할 수 있다.

${\displaystyle{alignedat}{4}&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}x_{i}&=d_{i},\dots,-1\\&a_n}&{i}&{i}&n}&n}&n}&a_{i-1}&n}&a_n}&n}&a_n}&\end {alignedat}}$

이 경우 Sherman-Morrison 공식을 사용하여 가우스 제거의 추가 연산을 방지하고 Thomas 알고리즘을 사용할 수 있습니다.이 방법은 입력 및 희박한 보정 벡터 모두에 대해 시스템의 수정된 비순환 버전을 해결한 다음 솔루션을 결합해야 합니다.이는 순수 삼각행렬 알고리즘의 정방향 부분을 공유할 수 있기 때문에 두 솔루션을 동시에 계산하면 효율적으로 수행될 수 있습니다.

다음으로 나타내는 경우:

${\displaystyle A={\begin{bmatrix}b_{1}&, c_{1}&,&&a_{1}\\a_{2}&, b_{2}&, c_{2}&, &, \\&, a_{3}&, b_{3}&, \ddots &, \\&,&\ddots &, \ddots &, c_{n-1}\\c_{n}&,&&a_{n}&, b_{n}\end{bmatrix}},x={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}},d={\begin{bmatrix}d_{1}\\d_{2}\\d_{3}\\\vdo.이익 \\d_{n}\end{bmatrix}}}$

다음으로 해결해야 할 시스템은 다음과 같습니다.

${\displaystyle Ax=d}$

이 경우 $계수{\displaystyle {}_{}}$ $(\$과 $(\$은 일반적으로 0이 아니기 때문에 이들 계수의 존재는 Thomas 알고리즘을 직접 적용할 수 없습니다.따라서 다음과 같이 B$$R${\displaystyle {}^{}}$× n \ $displaystyle$B \ $in$ \$mathbb$ { R$}^$ { n \ times $n$$$} $및{\displaystyle }$u , ${\$ ${\displaystyle {}^{}}$ n \ $displaystyle u$ , $v$ \ $in$ \$mathbb$ { R$} ^$ { n }을 생각할 수 있습니다.

${\displaystyle B={\begin{bmatrix}b_{1}-\gamma&c_{1}&,&&0\\a_{2}&, b_{2}&, c_{2}&, &, \\&, a_{3}&, b_{3}&, \ddots &, \\&,&\ddots, \ddots & &, c_{n-1}\\0&,&&a_{n}&, b_{n}-{\frac{c_{n}a_{1}}{\gamma}}\end{bmatrix}},u={\begin{bmatrix}\gamma \\0\\0\\\vdots \\c_{n}\end{bmatrix}},v={\begin{bmatrix}1.\\0\\0\\\vdots \\a_{1}/\gamma \end{bmatrix}}.}$

여기서 $\gamma {\displaystyle R\mathbb{}}${\$displaystyle \gamma \in \mathbb {R}}$은 선택하는 파라미터입니다.$행렬{\displaystyle }$ A$(\displaystyle$ A$)$는 A${\displaystyle =B+{}^{}}$ ${\displaystyle v^{}}$ T$(\$ A$=B+uv^{)$로 $재구성$할 수 있습니다.$T$ 그 다음 다음과 같은 방법으로 ^[4]해답이 얻어집니다.먼저 토마스 알고리즘을 적용한 두 개의 삼각형 방정식을 풀겠습니다.

${\displaystyle By=d\qquad\qquad Bq=u}$

그런 다음 Shermann-Morrison 공식을 사용하여 $솔루션{\displaystyle }$x(\$style$ x$)$를 재구성합니다.

${\displaystyle}x&=A^{-1}d=(B+uv^{)T)^{-1}d=B^{-1}d-{\frac {B^{-1}uv^{-1}B^{-1}}{1+v^{T}B^{-1}u}}d=y-{\frac {qv^{}T}y}{1+v^{T}q}}\end {aligned}}$

계수 벡터를 보존하지 않고 Dev-C++로 구현:

유형화된 구조{  이중으로 하다 A[n+2];   이중으로 하다 B[n+2];  이중으로 하다 C[n+2];  이중으로 하다 D[n+2]; } 계수;  //Thomas Alg. 적용, 알 수 없는 x[1], ..., x[n] 무효 토마스알그(이중으로 하다 x[n+1],계수* 쿠프){  이중으로 하다 u[n+1]={},v[n+1]={};  이중으로 하다 y[n+1]={},q[n+1]={};  이중으로 하다* A=쿠프->A, *B=쿠프->B,*C=쿠프->C,*D=쿠프->D;  이중으로 하다 가치=0;  이중으로 하다 w;  인트 i;    u[1]=감마;  u[n]=C[n];    v[1]=1;  v[n]=A[1]/감마;    //행렬 B 작성  A[1]=0;  B[1]=B[1]-감마;  B[n]=B[n]-(C[n]*A[n])/감마;  C[n]=0;    위해서(i=2;i< >n+1;i++){   w=A[i]/B[i-1];    B[i]=B[i]-w*C[i-1];   D[i]=D[i]-w*D[i-1];   u[i]=u[i]-w*u[i-1];  }  y[n]=D[n]/B[n];  q[n]=u[n]/B[n];    위해서(i=n-1;i>0;i--){   y[i]=(D[i]-C[i]*y[i+1])/B[i];   q[i]=(u[i]-C[i]*q[i+1])/B[i];  }  가치=(v[1]*y[1]+v[n]*y[n])/(1+v[1]*q[1]+v[n]*q[n]);    위해서(i=1;i< >n+1;i++){   x[i]=y[i]-q[i]*가치;  } } 

위에서 ^[5]설명한 삼각형 시스템의 약간 교란된 형태를 해결할 수 있는 또 다른 방법이 있습니다.치수 $({\displaystyle n}$ -${\displaystyle 1}$) × (${\displaystyle n}$ -${\displaystyle 1}$ $){$ $displaystyle$($n-1$)\$times$( $n-1$) $\}$의 2개의 보조 선형 시스템을 생각해 보겠습니다.

${\displaystyle {aligned} \qquad \ \ b_{2}u_{2}+c_{2}u_{3}&=d_{2}\a_{3}u_{2}+b_{3}}u_{3}+c_{3}}u_{4}&=d_{3}\\a_{i}u_{i-1}+b_{i}u_{i}+c_{i}u_{i+1}u_{i}&\c\c\c\a_{n}u_{n}u_{n}u_{n}&quad}&d_{i}u}u_{i}u}u_{i-1}&{i-1}u}u}u}u_{i-1}u}u}u}u_quad}+{i-1}u}\end{aligned}\dots i=4,\ldots,n-1\qquad \qquad \\b_{2}v_{2}+c_{2}v_{3}&=-a_{2}v_{2}\\\a_{2}v_{3}{3}_c}_qquad\c}\end{aligned}\syslog i=4,\ldots,n-1}$

편의상 ${\displaystyle \mathrm{u}}$ 1 $=$0 {\$displaystyle u_{$1}=$0$ 및$$ ${\displaystyle {v\mathrm{}}_{}}$ 1$=$ ${\displaystyle 1}$ {{$displaystyle v_{$1}=1$}$을 추가로 $정의$합니다. 이제 솔루션${\displaystyle }${$u$ 2,${\displaystyle {}_{}{}_{}{}_{}}$3${\displaystyle {}_{}}$${\displaystyle \dots ,}$ ${\displaystyle u_{}}$ n ${\displaystyle {}_{}}$ {$displaystyle$\{$2}, u_{3$}\$displaystyle, u_{$n$$$\}{\displaystyle {}_{}}$및 ${\displaystyle {v\_n}_{}}$$}$ ${\displaystyle \{\},}$2개의 보조 삼각형 시스템에 대한 알고리즘으로 사용됩니다.

${\displaystyle {}_{}}$으로${\displaystyle {}_{}}$ {${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, x${\displaystyle {}_{}}$2${\displaystyle }$…, x ${\displaystyle n_{}}$ $}$ { $displaystyle$ \ ${x_{1}, x_{2}\dots, x_{n}\}$을(를) 다음 형식으로 나타낼 수 있습니다.

$\displaystyle x_{i}=u_{i}+x_{1}v_{i}\qquad i=1,2,\display,n}$

실제로, 두 번째 보조 시스템의 각 $방정식$에 $({$1$\})$을 곱하고, 첫 번째 보조 시스템의 해당 방정식에 ${\displaystyle {}_{}}$ $=$ + ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {vi}_{}}$({$displaystyle x_{i$}=$u_{i}+x_{1}v_{$i$\}\})$를 사용하면, 즉 $된다$.$원래$ 시스템의 $le$2$$ ~$n{\displaystyle }$({$displaystyle$ n$}$은$($는) 만족합니다. $방정식{\displaystyle \mathrm{}}$ 1$({displaystyle$1)을 만족시키려면 i ${\displaystyle =}$ $({displaystyle$ i=2$$$}$및 i ${\displaystyle =}$ $({displaystyle$ i$=n})$의 공식을 $고려$하고 x 2$$ ${\displaystyle {u\mathrm{}}_{}}$ 2 + ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {v\mathrm{}}_{}}$ ${\displaystyle {}_{}}$({$displaystyle x_${2$}}) =u_2_2_1$}{$x}{x}{1$}{x}을 대체하십시오.}} $및{\displaystyle {}_{}}$ ${\displaystyle x_{}}$ n${\displaystyle {}_{}}$=${\displaystyle {}_{}{}_{}}$ n + ${\displaystyle {}_{}{}_{}}$ 1$$ n {\$displaystyle x_{$n}=$u_{$n}+$x_{1}v_{$n$$}을$($를) 원래$$ 시스템의 첫 번째 방정식으로 만듭니다.${\displaystyle {이}_{}}$를 통해 x 1$({$에 $대해{\displaystyle {}_{}}$ 1개의 스칼라 방정식이 생성됩니다.

$({displaystyle b_{1}x_{1}+c_{1}(u_{2}+x_{1}v_{2})+a_{1}(u_{n}+x_{1}v_{n})=d_{1}})$

그 결과, 이하를 알 수 있습니다.

${\displaystyle x_{1}=snfrac {d_{1}-a_{1}u_{2}}:{b_{1}+a_{1}v_{n}+c_{1}v_{2}}}}$

계수 벡터를 보존하지 않고 Dev-C++로 구현:

유형화된 구조{  이중으로 하다 A[n+2];   이중으로 하다 B[n+2];  이중으로 하다 C[n+2];  이중으로 하다 D[n+2]; } 계수;  //Thomas Alg. 적용, 알 수 없는 x[1], ..., x[n] 무효 토마스알그(이중으로 하다 x[n+1],계수* 쿠프){  이중으로 하다 u[n+1]={},v[n+1]={};  이중으로 하다* A=쿠프->A, *B=쿠프->B,*C=쿠프->C,*D=쿠프->D;  이중으로 하다 w,F[n+1]={};  F[2]=-A[2];  F[n]=-C[n];  인트 i;  u[1]=0;  v[1]=1;  위해서(i=3;i< >n+1;i++){   w=A[i]/B[i-1];    B[i]=B[i]-w*C[i-1];   D[i]=D[i]-w*D[i-1];   F[i]=F[i]-w*F[i-1];  }  u[n]=D[n]/B[n];  v[n]=F[n]/B[n];  위해서(i=n-1;i>1;i--){   u[i]=(D[i]-C[i]*u[i+1])/B[i];   v[i]=(F[i]-C[i]*v[i+1])/B[i];  }  x[1]=(D[1]-A[1]*u[n]-C[1]*u[2])/(B[1]+A[1]*v[n]+C[1]*v[2]);    위해서(i=2;i< >n+1;i++){   x[i]=u[i]+x[1]*v[i];  } } 

두 경우 모두 풀어야 할 보조 시스템은 진정으로 3중으로 처리되므로, ${\displaystyle \mathrm{시스템}}$ A x $=$ ${\displaystyle d}$ {\$displaystyle$ Ax$=d$$\}$의 전체 계산 복잡도는 $시스템{\displaystyle }$n의 치수, 즉 $n)$ {\$displaystyle$ O$(n}$ 산술$$ 연산에 대해 선형으로 유지됩니다.

다른 상황에서 방정식 시스템은 블록 삼각형(블록 매트릭스 참조)일 수 있으며, 위의 행렬 시스템에서 개별 요소로 배열된 작은 하위 행렬이 있습니다(예: 2D 포아송 문제).이러한 ^[6]상황을 위해 단순화된 형태의 가우스 제거가 개발되었다.

Quarteroni, Sacco 및 Saleri의 교과서 수치 수학에는 일부 나눗셈을 사용하지 않는 수정된 알고리즘이 나열되어 있으며, 이는 일부 컴퓨터 아키텍처에서 유용합니다.

병렬 3각 솔버는 GPU를 포함한^[7] 다수의 벡터 및 병렬 아키텍처용으로 공개되어 있습니다.

평행 삼각형 및 블록 삼각형 솔버의 광범위한 처리는 다음을 참조하십시오.

레퍼런스

Wikibook Algorithm Implementation에는 다음 항목에 대한 페이지가 있습니다.삼각행렬 알고리즘

• Conte, S. D.; de Boor, C. (1972). Elementary Numerical Analysis. McGraw-Hill, New York. ISBN 0070124469.
• 이 문서에서는 GFDL 라이선스에 의거한 CFD-Wiki의 기사 Tridiangularnal_matrix_algorithm_-_TDMA_(Thomas_algorithm)의 텍스트를 포함하고 있습니다.

• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Section 2.4". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.