2003/06/10 前回から、非線型方程式の解法を学び始めた。 # 最初に学んだ方法は「二分法」 非線型方程式の解法を特徴付けるポイント o 収束の速さ f(x) の計算の回数 二分法の場合は、1 次収束 計算回数と精度が比例する (一次式で表現できる) o 収束の安定性 ( 収束半径の大きさ ? ) 二分法の場合は「安定」 # 収束半径が無限大(?) # 初期値点がどこでも必ず収束する # 一般に、収束の速さ安定性は、相反する ## というか、精度も安定精が両立する方法があれば、他の ## 方法はいらないし、また、共に成立しない方法は、とっくの ## 昔に、相手にされなくなっている。 ### ということで、「トーレドオフ」できる手法が知られている.. 本日学ぶ方法「ニュートン法」 => 収束速度 二次収束 精度が二倍二倍になってゆく # 二分法 # 24 bit -> 1 2 3 4 .. 24 の 24 回 # ニュートン法 # 24 bit -> 1 2 4 8 16 32 の 6 回 収束の安定性 不安定な時がある == ニュートン法 f(x) と 初期値 x0 が与えられたときに次の値 x1 を 点、(x0,f(x0)) での接線 (傾きは f'(x)) と x 軸の交点の x 座標 とする。 # f(x) = a x + b ( つまり一次式 ) の場合は、一度に根が求め # られる ## これが、f(x) が一次式であることの定義(?) ニュートン法では、f が微分可能でなければならない( 適用のための制限条件 )。 # 工学の世界では、だいたい微分可能なので、あまり # 制限にならない。 具体的にニュートン法を利用する場合、 点 ( x0, f(x0) ) を通り傾き f'(x0) の接線の式 y - f(x0) = f'(x0)( x - x0 ) これと x 軸 ( y = 0 ) の交点を求めると、 0 - f(x0) = f'(x0)( x - x0 ) より、 x = x0 - f(x0)/f'(x0) (*) が得られるので、この式を利用することにより、 x_{n+1} = x_n - f(x_n)/f'(x_n) として、漸化式を定義し、繰り返し、計算を行う。 収束判定は | f(x_n) | < ε ( ε は十分に小さな数 ) で行う # 非常にシンプルな方法で、ニュートンの時代から利用.. # シンプルな方法が結局生き残る # => 線型方程式も結局、「ガウスの消去法」が.. ニュートン法の安定性 (*) 式から直接導かれる問題点 f'(x) が 0 になると不味い => 一般論として f'(x) が 0 に近い点が困る.. # ニュートン法の利点 # 微係数の情報を利用している ( ので高速.. ) # => 微係数の情報に振り回される.. ( ので不安定 ) # 二分法 # 予測する点と、関数の値の符号 ( 正負の 1 bit ) だけを # 利用 ニュートン法は、予め、「収束すること」がわかっていれば、良い 収束することの条件が、あまり明確でない cf. ベンリーチ「数値解析の基礎」 # 絵を書けば明かなのだが.. 物理的な条件から収束性が明確ならば Okey 収束性がわからないと.. 二分法と併用してある程度範囲を狭めてから.. # でも、どこで、切り換えるかはやっぱり、問題 # 結局は、なんらかの方法 ( たとえば数学的な証明等.. ) で、 # 「外」で、「安定性」を提供すればよい。 ニュートン法の適用 ex) \sqrt(2) f(x) として何をえらべばよいか ? 基本 x = \sqrt(2) より、 x - \sqrt(2) = 0 なので、 f(x) = x - \sqrt(2) の 0 点を求める「でも」よい.. しかし.. \sqrt(2) を求めたいのにその計算で \sqrt(2) を利用するのはナンセンス どうするか .. 基本に戻って x = \sqrt(2) これより、両辺を 2 乗して、 x^2 = 2 よって x^2 - 2 = 0 つまり、 f(x) = x^2 - 2 の 0 根をもとめればよい # 実は、この形にすると、解が二つになってしまう # => 初期値によって、どちらができるかがきまる # => 上手に初期値を指定する必要がある.. # \sqrt(a) の場合 ( 1 + a ) / 2 がよい.. x_{n+1} = x_n - f( x_n ) / f'( x_n ) = x_n - ( x_n ^ 2 - 2 ) / 2 x_n = (1/2) ( x_n - 2 / x_n ) # n 乗根も同様に.. ニュートン法の変形 f'(x) を計算したくない 差分を利用する f'(x_k) := (f(x_k) - f(x_{k-1})) / ( x_k - x_{k-1} ) で、近似 => 微分を計算しない ( 計算速度が速くなる.. ) 代りに 精度が悪くなる。 # 関数そのものでなく、関数値だけが与えられる場合.. 数学的な関数は、色々あって大変 # ゴルゴモルフの「間数論」 物を作る世界 現象そのものが安定している 現象を表す関数も安定している => あまり収束性が問題にならない 計算で、色々と不都合なことがおきる場合 => 現象自身が不安定な性質をもっている.. ex) 均質な板を両側から圧縮すると、どちらかに折れる => どちらに折れるかどうかはわからない => 計算も大変 (解の分岐:バイパケーション..) 実際には、「均質でない」ので、 結果は確定的 問題にならない 木の葉を落したときにどのように振舞うか => やはり難しい 現実の世界は、安定なものが多い 計算が不安定になっているとしたら、( それは、 計算 Model が表現している現実世界の不安定さを 意味するので..[現実の安定性と矛盾するから.. ) それは計算 ( Model 化手法を含む.. ) そのもの がすでに、誤っている。 == [演習] 06/10 \sqrt{a} の計算をニュートン法で解く # a は自分で决める ( 2 とか 4 とか.. ) # f(x) = x^2 - a で解く Subject は 06/10 1234 ^^^^^ ^^^^ | +--- 学生番号 +-------- 出題日時 自分に Cc: することをわすれない。 == 「収束の速さ安定性は、相反する」 広く成立する条件 あたらしい方法 悪化している条件があるはず 収束範囲 収束速度 適用範囲 etc.. そうでなければ、 従来の方法が本当にひどかった.. (無駄が多い..)