コンピュータシミュレーション前期中間考査まとめ

コンピュータシミュレーション前期中間考査まとめ
1. 数値解析と計算量・オーダ
a. 解法の種類
与えられた問題に対して、実用的な結果を数値的に求めるための方法を数値解析という。解析方法には以下の 2
種類が存在する。
(Ⅰ)解析的解法 … 定義式や公式から解を求める
(Ⅱ)数値的解法 … 電卓や計算を利用して近似解を求める(解法とプログラムが準備されていることが前提)
b. アルゴリズムと計算量
ある解を求めるために必要な手順を示したものをアルゴリズムという。
計算機が答えを出すために必要とする資源のことを計算量といい、以下の 2 種類が存在する。
(Ⅰ)時間的計算量 … アルゴリズムが答えを出すために必要な時間演算や処理の回数によって決まる
(Ⅱ)空間的計算量 … アルゴリズムを実行するために必要な記憶容量の大きさ
また、アルゴリズムの入力値を大きくした時の計算量の増加を表したものをオーダという。解を出すまでに必要
な演算回数などから求めるのが主で、𝑂�𝑓(𝑛)� で表す。
𝑓(𝑛) では、実際の計算量を表す式から増加量が最大の項を取り出し、更に係数を取り除く。具体的な例として
は、計算量がサイズに比例するなら𝑂(𝑛) と表し、サイズが２倍になると 1 増加するならO(log 2 𝑛) と表される。
1 つの問題に対して解法は唯一ではないので、アルゴリズムの効率を計算量やオーダから考える事が必要である。
[例] 𝑦 = ∑𝑛𝑖=0 𝑎𝑖 𝑥 𝑛−𝑖 の式のオーダを求めよ。
<解>
2. 数列の計算
そのまま計算すると
1
1
1
∑𝑛𝑖=1 𝑛 = 𝑛(𝑛 − 1) = 𝑛2 + 𝑛
2
2
2
ホーナー法を用いると 𝑦＝�⋯ �(𝑎0 𝑥 + 𝑎1 )𝑥 + 𝑎2 �𝑥 + ⋯ 𝑎𝑛−1 �𝑥 + 𝑎𝑛
となるので、𝑂(𝑛2 )
となるので、𝑂(𝑛)
a. 反復法
漸化式を用いて方程式を解く方法。反復法において用いる漸化式のことを特に反復式という。
[例] 𝑦 = ∑𝑛𝑖=0 𝑎𝑖 𝑥 𝑛−𝑖 の式を(𝑥 − 𝛼) で割った時の商の係数と余りを求めるための解法を、反復式を用いて求めよ。
𝑖
<解> 商を𝑔(𝑥) = ∑𝑛−1
𝑖=0 𝑏𝑖 𝑥 とすると、
反復式 : 𝑏𝑖 = 𝑏𝑖−1 𝛼 + 𝑎𝑖 ( 𝑏0 = 𝑎0 , 𝑏𝑛 が余りとなる )
※組立除法という
[例] 𝑥𝑖+1 = 1 + 1�𝑥𝑖 , 𝑥1 = 1 の収束値が、𝑥 2 − 𝑥 − 1 = 0 の解の 1 つに一致することを示せ。
<解> 実際に求めてみると自明だが、反復式の収束値を𝑥 とおいて反復式に代入すると、
𝑥 = 1 + 1�𝑥
3. 誤差
∴ 𝑥2 − 𝑥 + 1 = 0
となるので、収束値𝑥 は 𝑥 2 − 𝑥 − 1 = 0 を満足する。
a. 数値計算における誤差の種類
(Ⅰ)丸め誤差 … 四捨五入(零捨一入)により生じる誤差
(Ⅱ)打切誤差 … 真値が無限和で与えられる計算を適当なところで打ち切る際に生じる誤差
-1-
b. 誤差の原因
計算機が保持できる桁数には限界があるため、以下のような問題点が生じる。
(Ⅰ)情報落ち … 桁数が大きく異なる数の和を計算する際に小さな誤差が無視されること
(Ⅱ) 桁落ち … あたいが近い数値の差を計算する際に、本来の有効数字の桁数が減ってしまうこと
これを起こさないためにはアルゴリズムを工夫しなければならない。
4. 非線形方程式の解法
a. 1 変数スカラーの方程式
𝑓(𝑥) = �左辺� − �右辺� の式が𝑥 軸と交わる点が方程式の解となることを利用する。
(Ⅰ) ニュートン法 … 解が求められない場合がある
𝑓(𝑥) の方程式の接線を引き、その𝑥 軸との交点を探し、𝑥 軸と交わる点を見つけていく。具体的には、
(ⅰ) 𝑥0 を適当に選び、所望の精度に応じて ε > 0 を決める。𝑖 = 0 とする。
(ⅱ) 𝑥𝑖 における接線の方程式が𝑥𝑖+1 で 𝑥 軸と交わったとしてそれを変形した式
𝑥𝑖+1 = 𝑥𝑖 −
を計算して𝑥𝑖+1 の値を決める。
𝑓(𝑥𝑖 )
𝑓 ′ (𝑥𝑖 )
(ⅲ) |𝑓(𝑥𝑖+1 )| < 𝜀 ならば解が𝑥𝑖+1 であるとして終了する。そうでなければ𝑖 + + して(ⅱ)へ戻る。
(Ⅱ) 割線法
ニュートン法を差分で代用したもの。初期値を２つ選ばないといけない。
(Ⅲ) ２分法 … 上の２つに比べて処理速度は遅いが解を確実に求められる
解を探索する領域を２つに分け、解が存在する範囲を絞ることを繰り返していく。具体的には、
(ⅰ) 𝑓(𝑎) ∙ 𝑓(𝑏) < 0 を満たす 𝑎, 𝑏 を与え、解を捜索する範囲𝑎 ≤ 𝑥 ≤ 𝑏 を決める。また、所望の精度に応じて
ε > 0 を決める。
(ⅱ) |𝑏 − 𝑎| < 𝜀 ならば、𝑎 もしくは 𝑏 を解として終了する。
(ⅲ) 𝑎 ≤ 𝑐 ≤ 𝑏 を満たす 𝑐 を決める。決め方については、中間を取る２分法と、黄金比(1 ∶
金分割法、２点を結んだ線と𝑥 軸との交点をとる挟撃法がある。
1+√5
2
)に分割する黄
(ⅳ) 𝑓(𝑎) ∙ 𝑓(𝑏) < 0 ならば𝑏 = 𝑐 、そうでなければ𝑎 = 𝑐 として(ⅱ)に戻る。
5. 連立一次方程式の解法
a. 掃き出し法 … 行の基本変形
下の”ガウスの消去法”の変形 ver.
(ⅰ) 𝑖 = 1 とする。
(ⅱ) |𝑎𝑖𝑖 | < 𝜀 の場合は、𝑗 = 𝑖~𝑛 の範囲において、絶対値が最大となる𝑗 を探して𝑖 行目と𝑗 行目を入れ替える。
(ⅲ) 𝑘 = 𝑖~𝑛 の範囲において、𝑎𝑖𝑘 および 𝑏𝑖 を 𝑎𝑖𝑖 で割る。
(ⅳ) 𝑙 ≠ 0 , 𝑚 = 𝑖~𝑛 の範囲において、𝑎𝑙𝑚 = 𝑎𝑙𝑚 − 𝑎𝑙𝑖 𝑎𝑖𝑚 , 𝑏𝑙 = 𝑏𝑙 − 𝑎𝑙𝑖 𝑏𝑖 と置き換え、(ⅱ)に戻る。
b. ガウスの消去法
行列𝐴 を行の基本変形で上三角行列𝐴′ へ基本変形し、連立方程式の解を求める。この基本変形において、行列の
下三角成分を 0 にしていく動作のことを前進消去、下の方程式から得られた解を上の方程式に代入して解を求め
ていくことを後退代入という。
-2-
(ⅰ) 𝑖 = 1 とする。また、𝜀 を微小な生の実数とする。
(ⅱ) |𝑎𝑖𝑖 | < 𝜀 の場合は、𝑗 = 𝑖~𝑛 の範囲において、絶対値が最大となる𝑗 を探して𝑖 行目と𝑗 行目を入れ替える。
(ⅲ) 𝑘 = 𝑖 + 1~𝑛 , 𝑙 = 𝑖~𝑛 の範囲において、𝑎𝑘𝑙 = 𝑎𝑘𝑙 − 𝑎𝑖𝑙 ∙
(ⅳ) 𝑖 < 𝑛 ならば(ⅱ)へ戻る。
(ⅴ) 𝑥𝑛 =
算する。
𝑎𝑘𝑖
𝑎𝑖𝑖
, 𝑏𝑘 = 𝑏𝑘 − 𝑏𝑖 ∙
𝑎𝑘𝑖
𝑎𝑖𝑖
を置き換え、𝑖 + + する。
𝑏𝑛�
𝑛
1
𝑎𝑛𝑛 を計算する。そして 𝑚 = 𝑛 − 1~1 の範囲において、𝑥𝑚 = �𝑎𝑚𝑚 ∙ �𝑏𝑚 − ∑𝑝=𝑚+1 𝑎𝑚𝑝 𝑥𝑝 � を計
a.(ⅱ)や b.(ⅱ)のように、𝑎𝑖𝑖 の絶対値が非常に小さい場合に誤差が生じてしまうため、同じ列の要素で絶対値が最
大の行と入れ替えを行う、この操作のことをピボット選択という。
c. ヤコビ法 … 連立方程式の𝑖 行目の式を𝑥𝑖 について得られる式から漸化式を作り、反復法を行うもの
(ⅰ) 初期値として𝑥𝑗0 (𝑗 = 1~𝑛) を適当に定め、𝑖 = 0 とする。また、𝜀 を微小な生の実数とする。
(ⅱ) 𝑗 = 1~𝑛 の範囲について、
を計算して、𝑥𝑗𝑖+1
𝑥𝑗𝑖+1 =
を求める。
1
�𝑏 − � 𝑎𝑗𝑘 𝑥𝑘𝑖 �
𝑎𝑗𝑗 𝑗
𝑘≠𝑗
(ⅲ) �𝑥 𝑖+1 − 𝑥 𝑖 � < 𝜀 ならば𝑥 𝑖+1 を解として終了し、そうでなければ(ⅱ)に戻る。( �𝑥 𝑖+1 − 𝑥 𝑖 � はベクトルの長さ )
ちなみに、対角要素の絶対値が非対角要素の絶対値に比べて十分に大きい時、連立方程式の反復計算は収束する。
これは対角優位と呼ばれている。
𝑎𝑗𝑗 = 0 の場合、このアルゴリズムは実行できず、また、𝑎𝑗𝑗 の絶対値が０に近い場合は桁落ちが発生すること
が考えられる。
d. ガウス・ザイデル法
ヤコビ法について、はやく計算を終わらせるために、なるべく指数の値が大きいものを計算に使用しているもの。
(ⅰ) 初期値として𝑥𝑗0 (𝑗 = 1~𝑛) を適当に定め、𝑖 = 0 とする。また、𝜀 を微小な生の実数とする。
(ⅱ) 𝑗 = 1~𝑛 の範囲について、
を計算して、𝑥𝑗𝑖+1
𝑥𝑗𝑖+1 =
を求める。
𝑗−1
𝑛
𝑘=1
𝑘=𝑗+1
1
�𝑏 − � 𝑎𝑗𝑘 𝑥𝑘𝑖+1 − � 𝑎𝑗𝑘 𝑥𝑘𝑖 �
𝑎𝑗𝑗 𝑗
(ⅲ) �𝑥 𝑖+1 − 𝑥 𝑖 � < 𝜀 ならば𝑥 𝑖+1 を解として終了し、そうでなければ(ⅱ)に戻る。( �𝑥 𝑖+1 − 𝑥 𝑖 � はベクトルの長さ )
e. SOR 法 … ガウス・ザイデル法から得られた𝑥𝑗𝑖+1 に対する更新方向(𝑥𝑗𝑖+1 − 𝑥𝑗𝑖 )の延長線上に解を取り直し、アル
ゴリズムを更に加速させる
(ⅰ) 初期値として𝑥𝑗0 (𝑗 = 1~𝑛) を適当に定め、𝑖 = 0 とする。また、𝜀 を微小な生の実数とする。
(ⅱ) 𝑗 = 1~𝑛 の範囲について、
𝑥𝑗−𝑖+1 =
𝑗−1
𝑛
1
�𝑏 − � 𝑎𝑗𝑘 𝑥𝑘𝑖+1 − � 𝑎𝑗𝑘 𝑥𝑘𝑖 �
𝑎𝑗𝑗 𝑗
𝑥𝑗𝑖+1
=
𝑘=1
𝑥𝑗𝑖
+
𝜔(𝑥𝑗−𝑖+1
𝑘=𝑗+1
− 𝑥𝑗𝑖 )
を計算して、𝑥𝑗𝑖+1 を求める。ここで𝜔 は加速パラメータと呼ばれ、通常1 < 𝜔 < 2 で適当に決まる。
(ⅲ) �𝑥 𝑖+1 − 𝑥 𝑖 � < 𝜀 ならば𝑥 𝑖+1 を解として終了し、そうでなければ(ⅱ)に戻る。( �𝑥 𝑖+1 − 𝑥 𝑖 � はベクトルの長さ )
-3-
f. 固有値問題
(Ⅰ) ヤコビ法 … 𝐵 = 𝑃−1 𝐴𝑃 = 𝑃𝑡 𝐴𝑃 (ただし、𝑃 は正則直交行列)を用いて問題を解く
(ⅰ) 𝐴1 = 𝐴 とし、𝑖 = 1 とする。また、𝜀 を微小な生の実数とする。
(ⅱ) 𝐴𝑖 の非対角要素で絶対値が最大の要素((𝑝, 𝑞)成分とする)を選び、その絶対値が𝜀 未満であれば終了する。
1
(ⅲ) 𝜃 = tan−1
2
2𝑎𝑝𝑞
𝑎𝑞𝑞 −𝑎𝑝𝑝
から𝜃 を求めて、単位行列の(𝑝, 𝑝)成分と(𝑞, 𝑞)成分をcos 𝜃 、(𝑝, 𝑞)成分をsin 𝜃 、(𝑞, 𝑝)成
分を− sin 𝜃 とした行列𝑀𝑖 を作る。
(ⅳ) 𝐴𝑖+1 = 𝑀𝑖−1 𝐴𝑖 𝑀𝑖 = 𝑡𝑀𝑖 𝐴𝑖 𝑀𝑖 から𝐴𝑖+1 を計算し、(ⅱ)へ戻る。
(Ⅱ) 累乗法 … 絶対値が最大の固有値のみを求めることができる
行列𝐴 の固有値を絶対値の大きいもの順に𝜆1 , 𝜆2 , ⋯ , 𝜆𝑛 , 固有ベクトルを𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 , とし、
𝑣 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
を作った時、𝑣𝑚+1 = 𝐴𝑣𝑚 による反復計算は、最大値固有値に対する固有ベクトルに収束することを用いる。
(ⅰ) 𝑣1 を適当に決め、𝑖 = 0 とする。また、𝜀 を微小な生の実数とする。
1
(ⅱ)𝑣𝑖+1 を𝑣𝑖+1 = ‖𝐴𝑣 ‖ 𝐴𝑣𝑖 から算出する。
𝑖
(ⅲ) ‖𝑣𝑖+1 − 𝑣𝑖 ‖ < 𝜀 ならアルゴリズムを終了する。この時、最大固有値は‖𝐴𝑣𝑖 ‖ で、固有ベクトルは𝑣𝑖+1 となる。
-4-

Download Report