先週まで、非線型方程式の解法を学んだ 今週から、前期中は、連立一次方程式 ( 線型方程式 ) の解法を学ぶ。 線型方程式 A\vec{x} = \vec{b} 例えば、3 元連立方程式だと.. A = \left(\begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}\right) \vec{x} = \left(\begin{array}{ccc} x_1 & x_2 & x_3 \end{array}\right) \vec{b} = \left(\begin{array}{ccc} b_1 & b_2 & b_3 \end{array}\right) == 既に、数学の方で、クラーメルの公式で与えられている。 x_i = \frac{\delta_i}{\delta} しかし、計算機の世界では利用されない、 why ? 計算量が多いから。 \delta ( 行列式の計算 ) に O(n^3) だけかかる 結局全ての x_i ( n 個ある ) を求めるのに n * O(n-3) = O(n^4) だけかかる。 現実の世界は ？ ガウスの消去法 O(n^3) ( 直接法 ) or 反復法 ( 次回以降、学ぶ ) == 「連立方程式を解く」とは Ax=b を A'x=b' の形に変形できればよい。 where A' は対角化行列 => 割り算を計算するだけでよい。 # 計算量は 2/3 n^3 ( + n ) くらい.. => ガウス＝ジョルダン法 または... where A' は、上三角行列 => 下の方から解を求め、代入して解けばよい。 # 計算量は 1/3 n^3 + 1/2 n^2 位なので、少し、速い n が大きくなると、後者の方が、2 倍くらい速い.. # n が大きくなると、1/2 n^2 は無視できるほど小くなる.. => ガウスの消去法 数値計算的には、ガウスの消去法の方が、高速なだけでなく、誤差も少い。 == 具体的な解法 # まず、誤った解法 ?.. A の対角要素以外の要素を無条件に 0 にした A" を作ったらどうか ? => 形の上では、確かに「解けて」いる # しかし... この結果として、求められる答は、元の方程式を満すとは限らない => 誤った解答が得られる。 => 問題を解くために、問題の形を変形 ( 変換 ) する場合には、「そ の変形によって、答が変らない」ような変形を用いなければいけない。 # 変換には色々ある。特に、「答を変えない」変形は、「求 # めたい答」の性質、すなわち、問題の性質によって異なる。 ## 問題が異れば、適用できる変形手段が異なる ## cf. 固有値問題 (Ax = \lambda x となる \lambda を求める..) == 連立方程式の答をかえない、行列の変換方法 # 線型代数における「基本変換 (=基本行列との積を求めること)」 => 「ある行の定数倍を他の行に加える」 この「基本操作」を繰り返すことによって、問題を変形すること によって、求める ( 答が簡単に求められるような.. ) 問題を得る。 目的は、対角要素以外の係数を 0 にすること.. => 上三角行列にしたい。 一つの操作を行うと一つの要素を 0 にするのは簡単 でも、もし、その操作によって、他の ( 既に 0 にした.. ) 要素が 0 じゃなくなると、意味がない ( いつまでたっても 計算が終らないかもしれなくなる.. )。 => 操作を行う対象の順番を工夫すれば、このような ことはおきない。 操作手順 a_{ij} に対して、左上の a_{21} から、上から下へ左から 右へと操作を加えればよい。 # なぜなら、この順で実行すると、既に 0 にした # 要素は、他の計算の影響をうけず、0 のままになる。 # 連立方程式の場合は、この順で Okey だが、固有値問題では、 # 他の方法を用い、この時には、一旦 0 にした要素がまた 0 じゃなく # なることがある。 => 左下の要素を全部消して、上三角行列にすること.. ( 前進消去 ) => ガウスの消去法では、これでおしまい。 => 右上の要素も全部消して、対角角行列にすること.. ( 後退代入 ) => ガウス=ジョルダン == 前進消去法の問題点 要素の消去の時に、割り算が行われるが、この時に分母が 0 になっている とこまる => ピボット選択の問題 ピボット選択 一つの列に 0 以外の要素は一つだけあればよい 0 以外の要素 ( = ピボット ) を一つ探し出すこと => ピボット選択 # 数学的には、0 以外であればなんでもよいが、数値計算的には、 # 絶対値の最大なものを利用すれば、誤差が少くなる。 == 連立方程式が利用される場面 ( 応用 ) => 偏微分方程式の離散解法 方程式を離散化 ( 微分を差分に変形する ) => 普通に物理現象では、対角項が大きくなる。 # なぜなら.. # 次の状況は、自分と回りから決る # が影響としては、もちろん、自分 # からの影響が大きい つまり、ピボット選択はいらない.. => 逆に、ピボット選択が必要になるのは、 番号つけ失敗する.. 対角要素が大きい行列は、解が安定している # 計算すると、対角要素が大きくなる # (対角優位) => 現象的に安定しているものをちゃんとモデル化 すれば、対角要素が大きくなる。 # ちゃんとモデル化しても、対角要素が小さい # => 現象も安定しない == 普通 ( 物理現象を相手にした場合.. ) は、ピボット選択は不要なはず、 => まずは、アルゴリズムを理解し、ピボット選択は後で考える == 前進消去の計算量 一つの要素を 0 にするには、 最初は n 回の演算が必要。 # 後になると、段々減る 要素数は 1/2 (n-1)^2 個なので、結局 1/2 n^3 の計算量が必要。 == プログラミング 横のループ ( 1 - n ) # k 縦のループ ( 1 - n ) # i 1 行の計算 ( 1 - n ) # j 全部 1-n だと n^3 ( 立方体の体積 ) だが、 縦のループ、1 行のループは、段々減るので 丁度、三角垂の体積となるので 1/3 n^3 の計算量となる。 # 本によって、i,j,k の順番を変えた解法に別の名前がついているこ # とがある # => 騙されてはいけない、本質的には同じもの... ## この違いは、全く意味がないわけではない。計算機アーキテク ## チャによっては、速度に差が生じる。 == 今週の課題 Text p.38 の連立方程式をガウスの消去法を解く ピボット選択は不要 # 教科書の例では、ピボット選択が入って # いるが削除してよい。 係数行列は、好きに選び、キーボードから入力することが 望ましいが、プログラムに埋め込みでよい。 係数行列も、テキストのものを利用してよい。 # 変に、解のないもの選んでも詰まらない..