加治/数値計算の基礎/3章
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[加治/2010夏休み]]
&size(30){第3章 〜連立1次方程式の解法〜};
#contents
*ガウスの消去法 [#a28c5ff7]
例として次の連立4元1次方程式を考えてみよう:
#texvc(\begin{eqnarray}4x+3y+2z+&u&&=&9 \\ 2y-4z+&3u&&=&8 \\ 4z-&u&&=&2 \\ &3u&&=&6\end{eqnarray})
この連立1次方程式は、その形から上三角形((なんて読むの?))の連立1次方程式とよばれる。
**解き方 [#b5c98dfc]
-まず、一番下の方程式に着目すれば、
#texvc(u=\frac{6}{3}=2)
となる。
-次に、この値を下から2番目の方程式に代入すると、
#texvc(4z-2=2)
となるが、これは$z$に対する単独の1次方程式であるから、直ちに
#texvc(z=1)
となる。
-さらに、$z$と$u$を下から3番目の方程式に代入すれば、
#texvc(2y-4+6=8)
すなわち$y=3$
が得られる。
-最後にこれらの値を一番上の方程式に代入して
#texvc(4x+9+2+2=9)
すなわち$x=-1$
となる。このように上三角形の連立1次方程式は下から順に解いていけば、簡単に解が求まる。このことは連立1次方程式が何元であっても同じである。
**普通の連立1次方程式 [#ea9516e6]
以下の連立1次方程式を考える。
#texvc(\begin{eqnarray}4x+3y+2z+&u&&=&20 \\ 2x+5y-3z-&2u&&=&-5 \\ x-4y+8z-&u&&=&13 \\ -3x+2y-4z+&5u&&=&9\end{eqnarray})
この方程式がもし上で述べた上三角形に変形できれば簡単に解ける。そこで解き方の方針として上三角形に変形することを考える。
-まず第1番目の方程式を利用して2番目以降の方定式から$x$を消去する。それには、第1番目の方程式と他の方程式の$x$の係数を合わせた上で差をとれば良い。具体的には&br;
(2番目の方程式)-(1番目の方程式)$\times\frac{2}{4}$&br;
(3番目の方程式)-(1番目の方程式)$\times\frac{1}{4}$&br;
(4番目の方程式)-(1番目の方程式)$\times(-\frac{2}{4})$&br;
とする。その結果、2番目以降には$x$の無い連立1次方程式
#texvc(\begin{eqnarray}4x+3y+2z+u&=&20 \\ \frac{7}{2}y-4z-\frac{5}{2}u&=&-15 \\ -\frac{19}{4}y+\frac{15}{2}z-\frac{5}{4}u&=&8 \\ \frac{17}{14}y-\frac{5}{2}z+\frac{23}{4}u&=&-24\end{eqnarray})
が得られる。
-次に1番目の方程式はひとまず忘れることにすると、2番目以降の方定式は$y$,$z$,$u$に対する連立3元1次方程式になっている。そこで上と同様の手続きをとる。すなわち、この連立3元1次方程式のはじめの式(元の方程式では2番目の式)を用いて残りの式から$y$を消去する。
-そうして、残りの方程式も同様に文字を消去していくと、
#texvc(\begin{eqnarray}4x+3y+&2z&+&u=&20 \\ \frac{7}{2}y-&4z&-&\frac{5}{2}u=&-15 \\ &\frac{29}{14}z&-&\frac{65}{4}u=&-\frac{173}{14} \\ &&&\frac{408}{29}u=&\frac{1632}{29}\end{eqnarray})
という上三角型方程式が得られる。
-あとは下から順に代入して解けばよい。
***ここまでのまとめ [#n551416f]
この方法は、連立1次方程式の元数によらずに適用できる。この手順、すなわち一般の連立1次方程式を上三角型に直す手順を''前進消去''という。いったん上三角型になおれば、あとは下から順に簡単に解くことができる。これを''後退代入''という。以上、前進消去と後退代入を行って連立1次方程式を解く方法を''ガウスの消去法''とよんでいる。
**注意 [#pab486da]
#texvc(\begin{eqnarray}x+y+z+u&=&\alpha \\ z+u&=&\beta \\ y+z+u&=&\gamma \\ y+z-u&=&\delta\end{eqnarray})
のように、対角線上に項が並ばなくなってしまった場合は、消去が続けられなくなるが、方程式を入れ替えれば問題ない。
ガウスの消去法で唯一困ることは、場合によっては''ピボット''((消去の段階で対角戦上に並ぶ項))が0になるという現象が起こることである。しかし、そのような場合でも方程式の入れ替えを行えば問題は解決する。もし、行の入れ替えを行っても消去が続けられなくなった場合は、元の連立1次方程式が解を持たないか、解を持っても一通りに決まらない場合のどちらかである。
**誤差の問題 [#hf73be9f]
ピボットが0にならなくとも、計算の結果非常に絶対値の小さな数になることがある。その場合、変数を消去する場合にピボットで割り算をするが、その結果、絶対値の非常に大きな数が現れ、この絶対値の大きな数と他の数の差をとる段階で情報落ちの可能性がでてくる。この現象を防ぐためには、消去の段階でピボットが0にならなくても方程式の入れ替えを行えばよい。
具体的には、ある数を用いてそれより下にある方程式から変数を消去する場合、その変数の絶対値が最大である方程式と元の式を入れ替えるようにすれば良い。これを''部分ピボットの選択''という。
**ピボット選択を考慮したガウスの消去法のアルゴリズム [#af577d5a]
#texvc(\begin{eqnarray}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=&b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n&=&b_2 \\ \vdots\\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n&=&b_n\end{eqnarray})
+$l=1,2,\cdots,n-1$に対して次の演算を行う:
++各$l$について、$i=l+1,\cdots,n$に対して$a_{il}$の絶対値が最大になる$i$を見つける。
++$m=l,l+1,\cdots,n$に対して$a_{im}$と$a_{lm}$を入れ替える。
++各$l$について、$j=l+1,\cdots,n$に対して次の演算を行う。
+++$m_{jl}=a_{jl}/a_{ll}$
+++$k+l+1,\cdots,n$に対して次の演算を行う。
#texvc(a_{jk}=a_{jk}-m_{jl}a_{lj})
+++$b_j=b_j-m_{jl}b_l$
+$x_n=b_n/a_nn$
+$j=n-1,n-2,\cdots,1$の順に次の演算を行う.($k$が$n$より大きければ総和は計算しない)
#texvc(\displaystyle x_j=(b_j-\sum_{k=j+1}^{n}a_{jk}x_k)/a_{jj})
このアルゴリズムで、1.が前進消去、2.と3.が後退代入の部分である。また、bとcの式中の$=$は右辺を計算した結果を左辺に代入するという意味である。
*掃き出し法 [#p705aaaa]
**とは [#s99060c2]
ガウスの消去法の変形バージョン。ガウスの消去法では着目している行より下の行にある方程式から変数を消去したが、掃き出し法では同時に上の行の方程式からも変数を消去する。
**アルゴリズム [#q6b422f8]
#texvc(\begin{eqnarray}x_1&&&&+a_{14}a_4+\cdots +a_{1n}x_n&=&b_1 \\ &x_2&&&+a_{24}x_4+\cdots +a_{2n}x_n&=&b_2 \\ &&&x_3&+a_{34}x_4+\cdots +a_{3n}x_n&=&b_3\end{eqnarray})
という式があったとして、線形代数の1次方程式系を解く感じで最終的に
#texvc(\begin{eqnarray}x_1&&&&&&&=&b_1 \\ &x_2&&&&&&=&b_2 \\ &&&x_3&&&&=&b_3 \\ &&&&&&&\vdots& \\ &&&&&x_n&&=&b_n\end{eqnarray})
が得られれば良いみたいな。
*反復法の応用、''ヤコビの反復法'' [#w3291e95]
[[1.2節>数値解析の基礎/第1章#u5d87fd7]]での反復法を連立1次方程式に適用する。
**手順 [#d6faba61]
ここでは例として連立4元1次方程式を考える。
#texvc(\begin{eqnarray}&9x&+&2y&+&z&+&u&=&20& \\ &2x&+&8y&-&2z&+&u&=&16& \\ -&x&-&2y&+&7z&-&2u&=&8& \\ &x&-&y&-&2z&+&6u&=&17&\end{eqnarray});
+上から順に対角線上にある変数について解く
#texvc(\begin{eqnarray}x=(&20&&&-&2y&-&z&-&u&)/9 \\ y=(&16&-&2x&&&+&2z&-&u&)/8 \\ z=(&8&+&x&+&2y&&&+&2u&)/7 \\ u=(&17&-&x&+&y&+&2z&&&)/6\end{eqnarray});
+$x,y,z,u$として適当な値(初期値または出発値という)を仮定し、それらを右辺に代入して値を計算する。
+新たに得られた左辺の値を$x',y',z',u'$とすれば、それは一般的にははじめの$x,y,z,u$とは異なっている。(たまたま同じであれば初期値が解)
そこで上式を
#texvc(\begin{eqnarray}x'=(&20&&&-&2y&-&z&-&u&)/9 \\ y'=(&16&-&2x&&&+&2z&-&u&)/8 \\ z'=(&8&+&x&+&2y&&&+&2u&)/7 \\ u'=(&17&-&x&+&y&+&2z&&&)/6\end{eqnarray});
と書く。
+上式は方程式を用いたため少しは解に近づいている。そこで、$x',y',z',u'$を$x,y,z,u$に置き換えてまた上式の上辺に代入。
+上記プロセスを繰り返す。
+このような手続きを何回も続けているうちに右辺に代入した$x,y,z,u$と計算した後の$x',y',z',u'$の値がほとんど変化しなくなったとする。その時、
#texvc(x'=x, y'=y, z'=z, u'=u);
と見なせるから、方程式は近似的に解けたことになる。
***上記プロセスを漸化式の形で表すと [#rbac2630]
#texvc(\begin{eqnarray}x_{n+1}=(&20&&&-&2y_n&-&z+n&-&u_n&)/9 \\ y_{n+1}=(&16&-&2x_n&&&+&2z_n&-&u_n&)/8 \\ z_{n+1}=(&8&+&x_n&+&2y_n&&&+&2u_n&)/7 \\ u_{n+1}=(&17&-&x_n&+&y_n&+&2z_n&&&)/6\end{eqnarray});
となる。''反復前後の差''があらかじめ指定した許容値$\varepsilon$より小さくなれば終わりにすれば良い。
**ガウス・ザイデル法 [#tbc82f7e]
-ヤコビの反復法の収束をさらに速めたもの。
***理論 [#n6b31f45]
上の例で得られた漸化式で、上から順に計算していく際、1番目の式を計算し終えてから2番目の式に移るが、その段階で1番目の方程式を計算し終えているわけだから、1番目の式の$x$の値は更新されている。よって、この$x$を2番目の式の$x$として用い、さらに、3番目、4番目の式を計算する際にも、既に計算し終えた値を利用することによって、次に示す漸化式となる。
#texvc(\begin{eqnarray}x_{n+1}=(&20&&&-&2y_n&-&z+n&-&u_n&)/9 \\ y_{n+1}=(&16&-&2x_{n+1}&&&+&2z_n&-&u_n&)/8\end{eqnarray});
#texvc(\begin{eqnarray}z_{n+1}=(&8&+&x_{n+1}&+&2y_{n+1}&&&+&2u_n&)/7 \\ u_{n+1}=(&17&-&x_{n+1}&+&y_{n+1}&+&2z_{n+1}&&&)/6\end{eqnarray});
となる。一般に、ガウス・ザイデル法の収束の速さはヤコビ法の2倍程度になることが知られている。
----
#comment
終了行:
[[加治/2010夏休み]]
&size(30){第3章 〜連立1次方程式の解法〜};
#contents
*ガウスの消去法 [#a28c5ff7]
例として次の連立4元1次方程式を考えてみよう:
#texvc(\begin{eqnarray}4x+3y+2z+&u&&=&9 \\ 2y-4z+&3u&&=&8 \\ 4z-&u&&=&2 \\ &3u&&=&6\end{eqnarray})
この連立1次方程式は、その形から上三角形((なんて読むの?))の連立1次方程式とよばれる。
**解き方 [#b5c98dfc]
-まず、一番下の方程式に着目すれば、
#texvc(u=\frac{6}{3}=2)
となる。
-次に、この値を下から2番目の方程式に代入すると、
#texvc(4z-2=2)
となるが、これは$z$に対する単独の1次方程式であるから、直ちに
#texvc(z=1)
となる。
-さらに、$z$と$u$を下から3番目の方程式に代入すれば、
#texvc(2y-4+6=8)
すなわち$y=3$
が得られる。
-最後にこれらの値を一番上の方程式に代入して
#texvc(4x+9+2+2=9)
すなわち$x=-1$
となる。このように上三角形の連立1次方程式は下から順に解いていけば、簡単に解が求まる。このことは連立1次方程式が何元であっても同じである。
**普通の連立1次方程式 [#ea9516e6]
以下の連立1次方程式を考える。
#texvc(\begin{eqnarray}4x+3y+2z+&u&&=&20 \\ 2x+5y-3z-&2u&&=&-5 \\ x-4y+8z-&u&&=&13 \\ -3x+2y-4z+&5u&&=&9\end{eqnarray})
この方程式がもし上で述べた上三角形に変形できれば簡単に解ける。そこで解き方の方針として上三角形に変形することを考える。
-まず第1番目の方程式を利用して2番目以降の方定式から$x$を消去する。それには、第1番目の方程式と他の方程式の$x$の係数を合わせた上で差をとれば良い。具体的には&br;
(2番目の方程式)-(1番目の方程式)$\times\frac{2}{4}$&br;
(3番目の方程式)-(1番目の方程式)$\times\frac{1}{4}$&br;
(4番目の方程式)-(1番目の方程式)$\times(-\frac{2}{4})$&br;
とする。その結果、2番目以降には$x$の無い連立1次方程式
#texvc(\begin{eqnarray}4x+3y+2z+u&=&20 \\ \frac{7}{2}y-4z-\frac{5}{2}u&=&-15 \\ -\frac{19}{4}y+\frac{15}{2}z-\frac{5}{4}u&=&8 \\ \frac{17}{14}y-\frac{5}{2}z+\frac{23}{4}u&=&-24\end{eqnarray})
が得られる。
-次に1番目の方程式はひとまず忘れることにすると、2番目以降の方定式は$y$,$z$,$u$に対する連立3元1次方程式になっている。そこで上と同様の手続きをとる。すなわち、この連立3元1次方程式のはじめの式(元の方程式では2番目の式)を用いて残りの式から$y$を消去する。
-そうして、残りの方程式も同様に文字を消去していくと、
#texvc(\begin{eqnarray}4x+3y+&2z&+&u=&20 \\ \frac{7}{2}y-&4z&-&\frac{5}{2}u=&-15 \\ &\frac{29}{14}z&-&\frac{65}{4}u=&-\frac{173}{14} \\ &&&\frac{408}{29}u=&\frac{1632}{29}\end{eqnarray})
という上三角型方程式が得られる。
-あとは下から順に代入して解けばよい。
***ここまでのまとめ [#n551416f]
この方法は、連立1次方程式の元数によらずに適用できる。この手順、すなわち一般の連立1次方程式を上三角型に直す手順を''前進消去''という。いったん上三角型になおれば、あとは下から順に簡単に解くことができる。これを''後退代入''という。以上、前進消去と後退代入を行って連立1次方程式を解く方法を''ガウスの消去法''とよんでいる。
**注意 [#pab486da]
#texvc(\begin{eqnarray}x+y+z+u&=&\alpha \\ z+u&=&\beta \\ y+z+u&=&\gamma \\ y+z-u&=&\delta\end{eqnarray})
のように、対角線上に項が並ばなくなってしまった場合は、消去が続けられなくなるが、方程式を入れ替えれば問題ない。
ガウスの消去法で唯一困ることは、場合によっては''ピボット''((消去の段階で対角戦上に並ぶ項))が0になるという現象が起こることである。しかし、そのような場合でも方程式の入れ替えを行えば問題は解決する。もし、行の入れ替えを行っても消去が続けられなくなった場合は、元の連立1次方程式が解を持たないか、解を持っても一通りに決まらない場合のどちらかである。
**誤差の問題 [#hf73be9f]
ピボットが0にならなくとも、計算の結果非常に絶対値の小さな数になることがある。その場合、変数を消去する場合にピボットで割り算をするが、その結果、絶対値の非常に大きな数が現れ、この絶対値の大きな数と他の数の差をとる段階で情報落ちの可能性がでてくる。この現象を防ぐためには、消去の段階でピボットが0にならなくても方程式の入れ替えを行えばよい。
具体的には、ある数を用いてそれより下にある方程式から変数を消去する場合、その変数の絶対値が最大である方程式と元の式を入れ替えるようにすれば良い。これを''部分ピボットの選択''という。
**ピボット選択を考慮したガウスの消去法のアルゴリズム [#af577d5a]
#texvc(\begin{eqnarray}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n&=&b_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n&=&b_2 \\ \vdots\\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n&=&b_n\end{eqnarray})
+$l=1,2,\cdots,n-1$に対して次の演算を行う:
++各$l$について、$i=l+1,\cdots,n$に対して$a_{il}$の絶対値が最大になる$i$を見つける。
++$m=l,l+1,\cdots,n$に対して$a_{im}$と$a_{lm}$を入れ替える。
++各$l$について、$j=l+1,\cdots,n$に対して次の演算を行う。
+++$m_{jl}=a_{jl}/a_{ll}$
+++$k+l+1,\cdots,n$に対して次の演算を行う。
#texvc(a_{jk}=a_{jk}-m_{jl}a_{lj})
+++$b_j=b_j-m_{jl}b_l$
+$x_n=b_n/a_nn$
+$j=n-1,n-2,\cdots,1$の順に次の演算を行う.($k$が$n$より大きければ総和は計算しない)
#texvc(\displaystyle x_j=(b_j-\sum_{k=j+1}^{n}a_{jk}x_k)/a_{jj})
このアルゴリズムで、1.が前進消去、2.と3.が後退代入の部分である。また、bとcの式中の$=$は右辺を計算した結果を左辺に代入するという意味である。
*掃き出し法 [#p705aaaa]
**とは [#s99060c2]
ガウスの消去法の変形バージョン。ガウスの消去法では着目している行より下の行にある方程式から変数を消去したが、掃き出し法では同時に上の行の方程式からも変数を消去する。
**アルゴリズム [#q6b422f8]
#texvc(\begin{eqnarray}x_1&&&&+a_{14}a_4+\cdots +a_{1n}x_n&=&b_1 \\ &x_2&&&+a_{24}x_4+\cdots +a_{2n}x_n&=&b_2 \\ &&&x_3&+a_{34}x_4+\cdots +a_{3n}x_n&=&b_3\end{eqnarray})
という式があったとして、線形代数の1次方程式系を解く感じで最終的に
#texvc(\begin{eqnarray}x_1&&&&&&&=&b_1 \\ &x_2&&&&&&=&b_2 \\ &&&x_3&&&&=&b_3 \\ &&&&&&&\vdots& \\ &&&&&x_n&&=&b_n\end{eqnarray})
が得られれば良いみたいな。
*反復法の応用、''ヤコビの反復法'' [#w3291e95]
[[1.2節>数値解析の基礎/第1章#u5d87fd7]]での反復法を連立1次方程式に適用する。
**手順 [#d6faba61]
ここでは例として連立4元1次方程式を考える。
#texvc(\begin{eqnarray}&9x&+&2y&+&z&+&u&=&20& \\ &2x&+&8y&-&2z&+&u&=&16& \\ -&x&-&2y&+&7z&-&2u&=&8& \\ &x&-&y&-&2z&+&6u&=&17&\end{eqnarray});
+上から順に対角線上にある変数について解く
#texvc(\begin{eqnarray}x=(&20&&&-&2y&-&z&-&u&)/9 \\ y=(&16&-&2x&&&+&2z&-&u&)/8 \\ z=(&8&+&x&+&2y&&&+&2u&)/7 \\ u=(&17&-&x&+&y&+&2z&&&)/6\end{eqnarray});
+$x,y,z,u$として適当な値(初期値または出発値という)を仮定し、それらを右辺に代入して値を計算する。
+新たに得られた左辺の値を$x',y',z',u'$とすれば、それは一般的にははじめの$x,y,z,u$とは異なっている。(たまたま同じであれば初期値が解)
そこで上式を
#texvc(\begin{eqnarray}x'=(&20&&&-&2y&-&z&-&u&)/9 \\ y'=(&16&-&2x&&&+&2z&-&u&)/8 \\ z'=(&8&+&x&+&2y&&&+&2u&)/7 \\ u'=(&17&-&x&+&y&+&2z&&&)/6\end{eqnarray});
と書く。
+上式は方程式を用いたため少しは解に近づいている。そこで、$x',y',z',u'$を$x,y,z,u$に置き換えてまた上式の上辺に代入。
+上記プロセスを繰り返す。
+このような手続きを何回も続けているうちに右辺に代入した$x,y,z,u$と計算した後の$x',y',z',u'$の値がほとんど変化しなくなったとする。その時、
#texvc(x'=x, y'=y, z'=z, u'=u);
と見なせるから、方程式は近似的に解けたことになる。
***上記プロセスを漸化式の形で表すと [#rbac2630]
#texvc(\begin{eqnarray}x_{n+1}=(&20&&&-&2y_n&-&z+n&-&u_n&)/9 \\ y_{n+1}=(&16&-&2x_n&&&+&2z_n&-&u_n&)/8 \\ z_{n+1}=(&8&+&x_n&+&2y_n&&&+&2u_n&)/7 \\ u_{n+1}=(&17&-&x_n&+&y_n&+&2z_n&&&)/6\end{eqnarray});
となる。''反復前後の差''があらかじめ指定した許容値$\varepsilon$より小さくなれば終わりにすれば良い。
**ガウス・ザイデル法 [#tbc82f7e]
-ヤコビの反復法の収束をさらに速めたもの。
***理論 [#n6b31f45]
上の例で得られた漸化式で、上から順に計算していく際、1番目の式を計算し終えてから2番目の式に移るが、その段階で1番目の方程式を計算し終えているわけだから、1番目の式の$x$の値は更新されている。よって、この$x$を2番目の式の$x$として用い、さらに、3番目、4番目の式を計算する際にも、既に計算し終えた値を利用することによって、次に示す漸化式となる。
#texvc(\begin{eqnarray}x_{n+1}=(&20&&&-&2y_n&-&z+n&-&u_n&)/9 \\ y_{n+1}=(&16&-&2x_{n+1}&&&+&2z_n&-&u_n&)/8\end{eqnarray});
#texvc(\begin{eqnarray}z_{n+1}=(&8&+&x_{n+1}&+&2y_{n+1}&&&+&2u_n&)/7 \\ u_{n+1}=(&17&-&x_{n+1}&+&y_{n+1}&+&2z_{n+1}&&&)/6\end{eqnarray});
となる。一般に、ガウス・ザイデル法の収束の速さはヤコビ法の2倍程度になることが知られている。
----
#comment
ページ名: