Thomas법을 사용할 수 있는 조건

계수 행렬이 3중 대각 행렬인 연립 1차 방정식에 대해 이 토마스법을 이용함으로써 효율적으로 해를 구할 수 있다.

흐름

전진 소거법으로 계수 a의 부분을 0으로 한다

전진 소거법으로 계수 b의 부분을 1로 한다

후퇴 대입으로 해를 구한다

전진 소거

전진 소거의 거친 방법의 이미지로서는 위(1행째)에 있는 행으로부터 차례로 행렬을 정리해 가는 이미지입니다. 이번이라면 계수 a를 0, 계수 b를 1로 하는 작업을 위의 행에서 가는 이미지입니다.

우선, 계수 a, b는 0, 1로 변화했을 때에 대응하는 계수 c, d의 변수명을 c', d'로 둔다.
그래서 전진 소거 후의 목표로 하는 행렬의 형태는 이런 느낌.

첫 번째 행 처리

1행째로 생각하는 것으로는 $b_1$를 1로 하는 것이므로
$c_1' = c_1/b_1$
$d_1' = d_1/b_1$

k 라인

우선 2행째로 생각합니다. (죄송합니다 조금 수식 markdown으로 쓰는 것이 힘들어 왔기 때문에 필기로 ..)


이런 느낌의 상태이므로, 이 상태로부터 계수 a를 0, b를 1로 하는 것을 생각하면 좋기 때문에
$(② - ①*a_2)/(b_2-c_1'*a_2)$입니다.
따라서 $c_2'=c_2/(b_2 - c_1' * a_2 )$, $ d_2' = (d_2 - d_1' * a_2)/(b_2 - c_1' * a_2) $입니다.

일반화하고 쓰면

c_k'=c_k / (b_k - c_{k-1}' * a_k ) \\
d_k' = (d_k - d_{k-1}' * a_k)/(b_k - c_{k-1}' * a_k)

후퇴 대입

위의 항까지로 전진 대입이 끝나고 이런 형태로 행렬이 되었습니다.


후퇴 대입에서는 이름대로 행렬의 우하의 성분으로부터 계산을 실시해 갑니다. 여기서 전진 소거에 의해 대각 성분이 1이 되어 있는 것이 효과가 있습니다. 제대로 오지 않는 경우는 전진 소거 후의 행렬과 해X의 곱을 실제로 손으로 계산해 보면 알 수 있을까 생각합니다.

x_n = d_n' \\ 
x_k = d_k - c_kx_{k+1} \;\;\;\; (1<=k<n)

프로그램

알려진 행렬 b과 솔루션 행렬은 차원 수가 같기 때문에 메모리를 줄이기 위해 솔루션은 배열 b에 저장됩니다. 또한 계수 c ', d'는 p, q로 대체됩니다.

void Thomas(double *a, double *b, double *c, vector<double> d){
    vector<double> p, q;
    p.push_back(c[0] / b[0]);
    q.push_back(d[0] / b[0]);
    int n = d.size();


    for(int i = 1; i < n; i++){
        if(i < n-1){
            double _p = c[i] / (b[i] - c[i-1] * a[i]);
            p.push_back(_p);
        }
        double _q = (b[i] - a[i] * q[i-1]) / (b[i] - p[i-1] * a[i]);
        q.push_back(_q);
    }

    b[n-1] = q[n-1];
    for(int i = n-2; i >= 0; i--){
        b[i] = q[i] - p[i]*b[i+1];
    }

    for(int i = 0; i < n; i++){
        cout << d[i] << endl;
    }
}

(*실제로 제대로 움직이고 있는지는 이 사이트 를 사용해 확인해 보면 좋을지도 모릅니다)

비고

이번에 소개한 Thomas법은 확산 시뮬레이션 등에서 사용되는 음해법 중 연립 방정식을 풀기 위해 사용된다.

참고

htps //w w1. 기후. 아 c. jp/~타나카/누메리카 l_아나 lys s. pdf
h tp // w w. m-j 뭐. . jp / pub sh / ch ch 또는 l / data / ら L_47/47_023. pdf
htp // s2008. 아키타 뿌. 아 c. jp / ~ Ozawa / ㎇ 꼬임 / G 등 d_Schl / 접시 t10. pdf