Algoogle

Algorithm for Programming Contest

線形方程式の解(Givens)

基本情報


解説


Givens回転を用いたQR分解によって線形方程式を解く.
参考資料 : 競技プログラミングでの線型方程式系
スライドのコードはミスがあった気がするので注意.

コード


(givens.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define mkrot(x,y,c,s) { double r = sqrt(x*x+y*y); c = x/r; s = y/r;}
#define rot(x,y,c,s) { double u = c*x+s*y; double v = -s*x+c*y; x = u; y = v;}
arr givens(mat A, arr b) {
    const int n = b.size();
    for(int i = 0; i < n; ++i)
        for(int j = i+1; j < n; ++j) {
            double c, s;
            mkrot(A[i][i], A[j][i], c, s);
            rot(b[i], b[j], c, s);
            for (int k = i; k < n; k++) rot(A[i][k],A[j][k],c,s);
        }
    for(int i = n-1; i >= 0; --i) {
        for(int j = i+1; j < n; ++j)
            b[i] -= A[i][j] * b[j];
        b[i] /= A[i][i];
    }
    return b;
}

問題


Comments