2005/06/14 数値解析学と演習 福井 先生 先週は、ニュートン法、先々週は、二分法 # 今回は、非線形方程式の解法の最後 収束次数 二分法 1 遲い/タフ ニュートン法 2 速い/答がでないことがある => 使い分けがポイント # ここまでの解法は、一般の非線型方程式だが、次の解法は、特別な非線型方程式 ( 代数方程式 ) 固有の解法 == [代数方程式] # 非線型方程式としては、特別な形なのだが、色々な所で良く利用される非線型方程式 [一般形] \Sum_{i=0}^n a_i x^i = 0 n = 2 ax^2 + bx + c =0 n = 3 a_3x^3 + a_2x^2 + a_1x + a_0=0 # n = 4 までは、根の公式が存在するので、それが使える。 # => カルダン法、フェラリ法 # n > 4 の時には公式がないので、反復法で解くしかない.. # => どうするか.. ? ## まず、「代数方程式を解く」とはどうゆうことか ? 代数方程式が因数分解できれば、解けたと考える a_n(x-\alpha_1)(x-\alpha_2)..(x-\alpha_n)=0 # 頭がよければ、特別な場合に因数分解できるかもしれないだろうが.. # => 一般には無理 前回まで行った解法は、n 個の根の内の一つを求める方法だと考えればよい => 1) 反復法で、答 ( \alpha_1 ) を一つ求める # 普通は、方程式の形が解っているのでニュートン法を使うことが多い。 2) g(x) = \frac{f(x)}{x - \alpha_1} として、 減次 ( 次元を減らす ) して、 n) 一次元になるまで繰り返す。 # 考え方としては、これだけ # 処が普通にやるとだめ ( 「有限桁」の問題 !! ) # => 旨い方法がある ( 福井先生の更に先生の平野先生が研究された.. ) # => この講議ではそこまで詳しくできないかも .. ( 時間が少い.. ) # 代数方程式を解く場合の他の手法 [ベアスト・ヒッチホック法] 二次の項(二次因子)で因数分解する # あまり、考えていない、数値計算法の本にはかいてある a_n(x^2+\beta_1x+\ganmma_1)(x^2+\beta_2x+\ganmma_2)..(x-\alpha_n)=0 [メリット] 実数係数の代数方程式 => 根は、実数か、共役複素数の対 => 二次の項目の係数は実数にできる 複素数を扱う必要がない !! # 二次方程式を解くと根としては出てくるが、実質、複素数の計算を行う必要はない : 根の公式に代入するだけだから.. # 40 年前は、計算機で、複素数を扱うのは大変だった ## 複素数の割り算をするとオバーフローを起すような場合もあった !! [デメリット] 不安定 !! ( ほとんど、使う意味はない !! ) # Why ? 根を二つ同時に求める計算なため.. ? # 上手く行かない例 # 複素空間の問題を実数空間だけで解こうとすると、極を跨ぐ必要がでてくる可能性があり、そこで、オーバフローが生れることがありうる # 複素空間で計算を行えば、極を迂回することができる可能性がある ( ニュートン方法は、答の小さいものを探す方法なので、自動的に迂回される.. ) ## 「数値計算で誤差を減らすには.. ?」 ## (答が大きいのはしょうがないが、そうでなければ..) ## 途中でできるだけ値が大きくならないようにすればよい ## cf. 高橋英俊先生 ( 物理の先生 ) 二重指数計算 ## => ローラン展開のいやな部分を迂回する仕組 ### ベアスト法はつかっちゃだめ !! # 今はどうするか ? # 複素数のニュートン法を使うのがポイント ( 平野の方法 !! ) ## 代数方程式は、どのような空間で、根をもつか ? ## => どのような係数であっても、複素数の中にある ## 複素数は、代数方程式の根を求める演算にかんして閉じている。 == 代数方程式上でのニュートン法 ( 複素数版 ) x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{\Sum_{i=0}^n a_i x^i}{\Sum_{i=1}^{n} i a_i x^{i-1}} [初期値問題] # 初期値はどうするか ? # 佐藤公平先生 # ある特定の方程式に関して、どこから始めれば収束するかの絵 ( マッピング ) を書いた # # 研究としては面白いが、「答を出す」という観点では、余り意味がない.. # # 答を探すには.. # # 「確実に収束する初期値を探すアルゴリズム」 # # こっちは難しい。 # # 「どの初期値でも収束するアルゴリズム」 # # こちらの方が簡単 ( ただし、オーバフローの問題は残る ) # # => 平野の方法 ( n 次のニュートン法 ) : どこから始めても答に収束する # 一般の非線形方程式では、次元を上げてもあまりメリットがなかったが、代数方程式は、形が解っているので、この方法が効果的。特に、n 回微分が簡単に計算できる点も良い。 [ニュートン法の理解 => テーラ展開の理解] テーラ展開とは ? 無限な微係数が判れば、全空間の関数値が解る !! 代数方程式は、n 回目で微係数が 0 になるので、扱い安い !! # (普通の一次の..)ニュートン法は、一つしか利用していなので、収束したり、しなかったりする。 ## 無限次元ならば、そんなことはない !! ### 代数方程式は、有限の計算で、無限次元の計算をやることができる : 平野の方法 平野の方式 : 0 から開始すれば、必ず収束する ( 0 でなくても、どこからでも Okey なのだが、0 で始めるのは、オーバフローをさけるため.. ) # 実際は、全ての微係数ではなく、最も、効果的に影響を及ぼしている微係数の所で考えて、効率化しているが、原理的には、n 次元のニュートン法 [減次の問題] 途中で値が大きくなったら(誤差が沢山入って..)困る => 次元の低い方と高い方の両方から計算し、大きくならない方を採用する [DKA 法(text p.261)] # 少し前に流行った => でも勧められない ニュートン法を、全ての根に関して、同時に行う => 計算量は平野の方法の二倍位 # 平野の方法は減次するので、後半の根の計算では、次数が減るので、計算量が減る # DKA は、全ての根にかんして n 次元で計算するので、そこが損 # [代数方程式を解く場合の最良の方法] # 基本は、「複素数のニュートン法」を使うこと # 収束が気になるなら、「平野の方法]を使う 代数方程式を解くニーズ 高次元の代数方程式を直接解くアプリケーションはない 鉄筋の計算が 5 次元位 最近は、光ファイバーの計算で、4 次元 昔の数値計算では、 固有値問題を代数方程式に還元 ( 40 年前 ) 今は、他の直接法 ( ハウスホルダ法 ) # ここらへんは、後期に詳しく説明する # 亀高先生の問題 ( 無限次元の代数方程式の根 ) # 暗号化等で、応用があるかも ? # モノを作る分野では、あまり応用例がない.. # 問題を解く方法を考えるには、元々の問題の性質と、答の性質を考えて解くとよい # 代数方程式は、複素係数で、複素根を持つ !! n 次元の代数方程式は n 個の根 ( 重複根を含む ) があることが解っているので、話が楽く # 一般的な非線形方程式は、そもそも根があるのかどうか、あるいは、あるとしてもいくつあるのか解らないことが多いので、大変 ( 根の存在や個数の特定は、数学的な証明を (計算とは別に..) 必要とすることになる )。 == [代数方程式での数値計算の問題点] # f(x) の計算そのものがまず、問題 計算量を減らすにはどうすればよいか ? f(x) = \Sum_{i=0}^n a_i x^i を素直に計算すると... \frac{n(n+1)}{2} 回の掛け算 n = 10 の時で、55 回 n = 100 の時で、5050 回 !! n 回の足し算 # ところが、工夫すれば、掛け算の回数を n 回に減らせる ホーナー法 (組み立て除法) # なんで「除法」なのかは良くわからないが... f(x) = ( .. ((a_n x + a_{n-1})x + a_{n-2})x + a_{n-2})x .. )x+a_0 の形で計算する # プログラム的には A = a_n for ( i = n - 1; i >= 0; i-- ) { A = A x + a_i; } # とする。 n 回数の掛け算ですむ # n = 100 の時には、50 倍も違う !!! この方法は、実は、「安定性」も良い ( つまり誤差が少い ) why ? 値が大きくなる部分 ( 高次の項 ) を、小さい数の内に、先に足し算の計算している # 素直に a_nx^n から計算すると、これは大きな数になるので、その後の足し算で、どんどん誤差が入ってしまう # 他に、ブラウン法などの他の方法もあるが、まあ、 == [演習] 本当は平野の方法を試してほしいが.. ( 三年位かかるかも.. ) # 福井先生が、平野先生から、資料をもらっても半年理解にかかった !! ## まあ、利用するだけならば、ライブラリを使うだけだが.. ## => phase ( Web で get しよう ) ### 本日は、理論的な内容だけでも理解して欲しい 06/14 ホーナー法で、方程式の値を計算する 次元 : n = 10 係数 : a_10 = 1 a_9 = -2 a_8 = 3 a_7 = -4 a_6 = 5 a_5 = -6 a_4 = 7 a_3 = -8 a_2 = 9 a_1 = -10 a_0 = 11 添付ファイルはやめよう。 読むのが大変 Computer Virus と判断されて読まない人もいる 夜中に出すのはやめよう 体を壊す !! # 多少遅れても Okey ( まあ、溜めないよう ) # 数値計算の演習でまず、重要なこと !! 電卓を用意する : 答が明らかな場合を、実際に計算してみる。その計算に、電卓が役立つ