2
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Thomas法による数値解析

Last updated at Posted at 2019-11-24

Thomas法が使える条件

係数行列が3重対角行列である連立一次方程式に対してこのThomas法を用いることで効率よく解を求めることができます.
スクリーンショット 2019-11-24 23.12.44.png

流れ

  1. 前進消去法で係数aの部分を0にする
  2. 前進消去法で係数bの部分を1にする
  3. 後退代入によって解を求める

前進消去

前進消去のざっくりとした手法のイメージとしては上(1行目)にある行から順番に行列を整理していくイメージです.今回であれば係数aを0、係数bを1にする作業を上にある行から行っていくイメージです.

まずはじめに係数a,bは0,1に変化させた時に対応する係数c,dの変数名をc',d'と置くことにします.
なので前進消去後の目標とする行列の形はこんな感じ.
スクリーンショット 2020-01-07 16.03.24.png

1行目の処理

1行目で考えることとしては$b_1$を1にすることなので
$c_1' = c_1/b_1$
$d_1' = d_1/b_1$

k行目

とりあえず2行目で考えます.(すみませんちょっと数式markdownで書くの大変になってきたので手書きで..)

ファイル_001.png こんな感じの状態なので、この状態から係数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)

後退代入

上の項までで前進代入だ終了してこのような形に行列がなりました.
スクリーンショット 2020-01-07 16.03.24.png

後退代入では名前の通り行列の右下の成分から計算を行っていきます.ここで前進消去によって対角成分が1になっていることが効いてきます.しっくり来ない場合は前進消去後の行列と解Xの積を実際に手で計算してみるとわかるかと思います.

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

プログラム

既知である行列bと解の行列は次元数が同じなのでメモリ削減のために解は配列bに格納しています.また係数c', d'はp,qに置き換わっています.

.cpp
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法は拡散シミュレーションなどで用いられる陰解法の中で連立方程式を解くために用いられる.

参考

https://www1.gifu-u.ac.jp/~tanaka/numerical_analysis.pdf
http://www.mri-jma.go.jp/Publish/Technical/DATA/VOL_47/47_023.pdf
http://nas2008.akita-pu.ac.jp/~ozawa/Lecture/Grad_Schl/HandOut10.pdf

2
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?