2003/06/17 解析学とコンピュータ 前回と前々回と非線型方程式を解く方法を学んだ 二分法 一次収束 ( あまり速くない ) 適用範囲が広い ( 何時でも使える ) ニュートン法 二次収束 ( 上手く行くと速くない ) 適用範囲が限定される (とんでもないことが興ることがある。) == [今回] 代数方程式 f(x) = \Sum_{i=0}^n{a_i x^i} = 0 の解き方を学ぶ。 f(x) の次数 n が、4 以下ならば、公式があるので、それを適用すればよい i.e.) n = 2 の時 f(x) = ax^2 + bx + c = 0 x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} n = 3 の時 ( カルダン法 ) n = 4 の時 ( フェラリ法 / ブラウン法 ) n > 4 の時 一般的な解の公式が存在しない ( 証明されている ) => 反復法でしかとけない # 公式を適用して、問題を解く方法を「直接(解)法」と呼ぶ # 決りきった手順を行うだけ.. # <=> 二分法、ニュートン法等は、「反復法」と呼ぶ # 収束判定が必要 今迄は、一般的な f(x) => 解の個数さえわからない... 今回の対象は、代数方程式に限定する 代数方程式固有の性質を利用できる # 例えば.. n 次の方程式は ( 重根を含めて.. ) n 個の解がある。 (同じニュートン法を利用するとしても..) 効率よく計算できる可能性がある。 # [余談] # 「二次方程式の解」は生活で利用しますか ? .. # 後期は、「固有値問題」 # 昔は「固有値問題」は「代数方程式」に還元してといた # => 今は「固有値問題」を別の方法で解く # 建築の世界では.. # 3 次、5 次の方程式が出てくる # 奇数次を使うのは、かならず実根があるように.. # 皆の回りでは.. # 4 次方程式 # => 光ファイバ内での光の経路の計算に出てくる.. # しかし.. # 現実の世界では、あまり代数方程式を解く場面は少い... 解法は、ニュートン法 x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} x_0 は適当に # 数学の世界で「適当に」とあったら、 # => 「旨い方法がない」ということを意味する 解法は同じなので、f(x), f'(x) の計算を高速に行う工夫をする ことを考える。 # 「f(x) が代数方程式である」という性質を利用する。 [例題] f(x) = a_3 x^3 + a_2 x^2 + a_1 x + a_0 を計算するのに、何回の計算が必要か ? 単純に考えると.. + 3 回 * 0 + 1 + 2 + 3 = 6 回 工夫 ( ホーナーの方法 ) すると.. f(x) = ( ( a_3 x + a_2 ) x + a_1 ) x + a_0 + 3 回 * 3 回 # かけ算とたし算の演算量の差 # # 今の計算機は、工夫されて同じ位の時間 ( 2 倍程度.. ) # # になっているが.. # # その代わりに、回路が複雑になっている。 # 本来は、桁数 n に対して # + n # * n^2 # なので、かなり違う この方法は、単に速いだけでなく、数値的にも安定している。 # 「安定」: 計算誤差が少いこと.. # 現在利用している PC は 32bit 程度 ( 倍精度でも 64 bit .. ) # => 有限桁数 # 誤差のことを考える必要がある # # 無限桁なら誤差の事を考えなくてもよい。 # # [注意] いくら長い桁でもと、無限桁とはならない # ## 連続と離散の違い f(x) の計算のプログラム手順 Loop と配列を利用する x // x a[i] // a_i i = 0 .. n f // f(x) f = a[ n ]; for ( i = n - 1 ; i >= 0; i-- ) { f = f * x + a[ i ]; } 代数方程式は、複素数で考えた法がよい # 実数だけで考えると根を求めることができない場合がある ## 実根がない場合がある.. 根の公式 => 平方根をうまく利用して、複素根の場合も扱えるようになっている。 反復法(ニュートン法) 実数係数 ( と初期値 ) の関数 f(x) を利用すると、式の形 からして、実数の値しかでてこない.. => 複素根を扱うための仕組が必要 => 複素数を利用しないといけない.. # 数の集合は、そこでの演算と関係がある # + * .. 自然数 # - .. 整数 # / .. 有理数 # 根 .. 複素数 # Fortran なら複素数計算は間単だが、C などだとちょっと大変.. == ニュートン法がなぜ、不安定 ( 初期値によって、変な挙動をする.. ) か ? => ニュートン法が、一次の微係数しか利用していないから.. ニュートン法の一般化 ニュートン法の原理 テーラー展開による関数近似を利用いている.. f(x+h) = f(x) + \frac{h}{1!}f'(x) + \frac{h^2}{2!}f''(x) + .. ニュートン法では、 f(x+h) = f(x) + \frac{h}{1!}f'(x) しか利用しない.. 無限次元のテーラー展開近似を利用して ニュートン法を一般化可能 => この場合は、安定する.. しかし、現実には、無限次元の計算はできない.. ところが.. 代数方程式であれば、有限級数なので、これができる 「平野の方法」 == p.27 ベアストー(ヒッチコック)法 ( 一種のニュートン法.. ) 普通のニュートン法 f(x) = (x-\alpha_1)g(x) という因数分解を行う.. # 一般には、更に g(x) を解いて... # f(x) = a_n \Pi_{i=1}^{n}(x-\alpha_i) # という形になれば「解けた」ことになる ここで、\alpha_i は、複素解.. => 複素数の計算を行う必要がある 実数の世界だけで計算できないか ? 共役複素数 ( 2 次方程式.. ) を利用する f(x) = (x^2 + \beta x + \ganmma)h(x) # 確かに、旨い ( 実数だけしか利用しない.. ) 方法のようだが.. # (実際の計算での..) 現象的には # => 収束しない # 解を同時に二つ求めるから... # => 二兎追うものは一兎も.. # この方法は、あまりよくない # 本にはよく引用されている # 本を書く人は利用してないことがある # => 駄目なのに生き残っている # # ちゃんと調べて本を書いた人 # # 宇野先生、伊理先生 [まとめ] 計算順序を工夫する 速くなる 誤差が少い 答の出てくる空間で計算しなさい 複素数解を求めるなら、複素数の世界で計算する [課題] いきなり、代数方程式を解くのは大変 # Text の例も ベアストー法 ( お勧めしない.. ) なので.. => ホーナー法で、代数関数の値を計算するプログラムを作成しなさい。 例えば、 f(x) = 5 x^5 - 20 x^4 + 50 x^3 - 80 x^2 + 100 x - 5 を計算するプログラムを作成しなさい。 係数は、自分で別のものにしてもよい。