日記帳

プログラミングのことをつぶやく日記です。

ガウスの消去法をプログラムする

ガウスの消去法のプログラムをRubyで作成した。deleteメソッドが前進消去、backward_substitutionが交代代入である。

def delete(a, b)
  n = a.size
  l = Array.new(n, Array.new(n))

  for k in 0..n - 2 do
    for i in k + 1..n - 1 do
      l[i][k] = a[i][k].to_f / a[k][k]
      for j in k + 1..n - 1 do
        a[i][j] = a[i][j] - l[i][k] * a[k][j]
      end
      b[i] = b[i] - l[i][k] * b[k]
    end
  end

  for k in n - 1..0 do
    for j in k + 1..n - 1 do
      b[k] = b[k] - a[k][j] * b[j]
    end
    b[k] = b[k].to_f / a[k][k]
  end
  return a, b
end

# 方程式の解を求める
def backward_substitution(a, b)
  n = a.size
  x = []
  (n - 1).downto(0) do |i|
    sum = b[i]
    # n -1 == i のときは実行しないようにする
    (i + 1).upto(n - 1) do |j|
      sum -= a[i][j] * x[j]
    end
    x[i] = sum / a[i][i]
  end
  return x
end

def print(b, x)
  printf "b=\n"
  b.each { |bb| printf "|%-5s|\n", bb }
  x.each_with_index { |xx, i| printf "x%s=%s\n", i + 1, xx }
end

def gauss_jordan_elimination(a, b)
  a, b = delete(a, b)
  x = solve(a, b)
  return a, b, x
end

a = [
  [1, 2, 3],
  [3, 5, 4],
  [4, 6, 7]
]
b = [
  8,
  17,
  23
]

_, b, x = gauss_jordan_elimination(a, b)
print(b, x)

Aとbはそれぞれ以下の通り

f:id:leokun0210:20211202003313p:plain

実行結果は以下のようになる。

b=
|8    |
|-7.0 |
|5.0  |
x1=1.0
x2=2.0
x3=1.0

アルゴリズムや計算量についても書きたいが、時間が取れないので今回は書かない。