反復法を用いた連立方程式の解法

0.はじめに

本記事は学校の課題でレポートを作成する際に、「scrapboxで作れば楽なのでは？」という発想の下に作られたものです。

なので、構成や言葉遣いなどが記事っぽくない箇所があります。

ですが、反復法の説明としては...まぁそこそこ？...中の下くらいの価値はあるでしょうし、何よりも「折角、作ったのに消すのが勿体無い」と感じてしまったので残っています。

1.連立方程式のアルゴリズム的解法

連立方程式をアルゴリズム的に解く手法としては以下のようなものがある。

フラメルの公式

ガウス・ジョルダン法(はきだし法)

ガウスの消去法

LU分解

これらの手法は一般的には「代数的手法」と呼ばれる。

こららの代数的手法の特徴は厳密に値を求めるところにある。

従って、この手法の評価点は精密さよりも処理速度にある。

2. 反復法

今回実装する手法は

ヤコビ法

ガウス・ザイデル法

の二つである。

この二つの手法は理論が似通っているため習得に連続性が期待できる。

また、近似前の初期値となる値も定める必要があり、その初期値の要素数は連立方程式の変数の個数と同当分が必須となる。

3.反復法における収束性

4.ヤコビ法

ヤコビ法という呼称の数学手法は二つあるとされるが、本稿で扱うのは「連立一次方程式を近似的に解く手法」のヤコビ法であることに留意して頂きたい。

例

例のような行列式のときに上の式に注目する。

$ a_1x + b_1y +c_1 = D_1

$ x = \tfrac{D_1 - b_1y - c_1z}{ a_1}

この操作を二番目の式はyに三番目の式はzにそれぞれ行う。

すると、各式に初期値を代入した際に、その更新値が得られるので、再度その更新値を初期値としてヤコビ法を行う。

これが反復法と言われる所以である。

5.ガウス・ザイデル法

例

例のような行列式のときに上の式に注目する。

$ a_1x + b_1y +c_1 = D_1

$ x = \tfrac{D_1 - b_1y - c_1z}{ a_1}

この操作を二番目の式はyに三番目の式はzにそれぞれ行う。

ヤコビ法は全体に値を代入し、一括で処理を行っていたが、ガウス・ザイデル法は逐次的に値を代入し、最底辺式まできたらそれらの値を初期値として反復法としてガウス・ザイデル法を行う。

6.実験結果

本実験では以下の行列式を二つの手法で解き、比較するというものである。

6.1 ヤコビ法

代数的手法と比較すると早く値に近づいている。

近似後は近似値付近の増減(振動)を繰り返していた。

具体的数値だと更新が5回の時点で落ち着いてきており、総計は20回なのでなかなかに優秀であるといえる。

プログラムのソースコードをリスト7.1として以下に添付する。

https://gyazo.com/051fffb6235ddcbce257aa2e19530790

図1.ヤコビ法での近似推移

code:jacobi.py

import random

import math

import matplotlib.pyplot as plt

eps = 0.000001

num = []

array = []

ans = []

ct =0

if int(input("Homework => 1 \nRandom =>0 \n===>")) == 0:

retu = int(input("How long RETU?"))

result = []

for i in range(retu):

result.append(0)

ans.append(random.randint(1,10))

for j in range(retu):

array = []

for i in range(retu):

array.append(random.randint(1,10))

num.append(array)

else:

retu = 3

print("Question")

for i in range(retu):

plot_y = []

flag =0

while flag == 0:

flag = 1

Bresult = []

if ("inf" in str(result)) or ("-inf" in str(result)):

print("Unfortunately, this equation didn't seem to converge because it doesn't seem to be dominant diagonal.I can't get results. ")

exit()

for i in range(len(result)):

for i in range(len(result)):

for l in range(len(result)):

if i != l:

ct = ct + 1

for i in range(len(result)):

flag = 0

break

for i in range(len(result)):

print(result)

print("Answer")

for i in range(retu):

print("calculation ct = " + str(ct))

print(plot_y)

for i in range(len(result)):

for l in range(int(ct/len(result))):

print(l)

print(plot_result)

plt.legend()

plt.show()

6.2 ガウス・ザイデル法

収束がヤコビ法と比較すると早い。

近似自体は特に早く、グラフのほとんどが近似値での振動であった。

具体的数値だと更新が1~2回の時点でかなり近似しており、総計も8回なのでかなり優秀であるといえる。

プログラムのソースコードをリスト7.2として以下に添付する。

https://gyazo.com/77388f895d30a4b6c12dda992642bfe4

図2.ガウス・ザイデル法での近似推移

code:seidel.py

import random

import math

import matplotlib.pyplot as plt

eps = 0.000001

num = []

array = []

ans = []

ct =0

if int(input("Homework => 1 \nRandom =>0 \n===>")) == 0:

retu = int(input("How long RETU?"))

result = []

for i in range(retu):

result.append(0)

ans.append(random.randint(1,10))

for j in range(retu):

array = []

for i in range(retu):

array.append(random.randint(1,10))

num.append(array)

else:

retu = 3

print("Question")

for i in range(retu):

plot_y = []

flag =0

while flag == 0:

flag = 1

Bresult = []

if ("inf" in str(result)) or ("-inf" in str(result)):

print("Unfortunately, this equation didn't seem to converge because it doesn't seem to be dominant diagonal.I can't get results. ")

exit()

for i in range(len(result)):

for i in range(len(result)):

for l in range(len(result)):

if i != l:

ct = ct + 1

for i in range(len(result)):

flag = 0

break

print(result)

print("Answer")

for i in range(retu):

print("calculation ct = " + str(ct))

print(plot_y)

for i in range(len(result)):

for l in range(int(ct/len(result))):

print(l)

print(plot_result)

plt.legend()

plt.show()