今日から本番 しばらく ( 前期 ) は、「方程式を解く」ことを学ぶ 方程式 (の分類 ) # 分け方としては、かなりいい加減 線型方程式 答えがあるかどうかが解る 非線型方程式 答えの個数がわかるとは限らない cf. f(x) = \sin(x) - \alpha # 答が無限にあるかもしれないし、0 かも 代数方程式 n 次元の多項式 f(x) = \Sum_{i=0}^n a_i x^i に対して f(x) = 0 の形をしたもの。 n < 5 ならば、公式がある cf. 二次方程式の根の方程式 => 「直接法」 # n=3, カルダン法 n >= 5 ならば公式がない # 存在しないことが証明されている # アーベル ( 19 才の時 !! ) 一般の方程式 f(\alpha)=0 ならば、\alpha は f(x)=0 の解 # ある関数方程式の定理の証明 # 定理 : ... # 証明 : じっとにらめば解る 偶然、解の候補を考え、多項式に代入すると偶然 0 になれば良いが.. => そうは上手く行かない => じゃあどうするか ? 増減表を作ってみる 代入してだめだったら、それを修正する 何度か繰り返せば、答えが出るだろう.. => 反復方法 # ポイントは「どう修正するか ?」 答えが一つわければ、後はなんとか.. 方程式の解法 直接法 ( 定数回数で終了することが保証されたアルゴリズムがある. ) 反復法 関数の計算 + 修正の方法 # 線型方程式は直接法がある 線型方程式を直接法で解くと \frac{1}{3}n^3 位の時間が係る => これは、密行列の場合 しかし、一般には、疎行列を解く場合が多い => 直接法だと、疎でも密と同じだけ時間がかかる => 反復法ならば、疎の性質を利用してサボれる。 # 本日学ぶ内容は、直接法がないので、ある意味で簡単 ( 反復法しかないので.. ) == [二分方法] ( 来週は、「ニュートン法」 ) # 「修正法」は色々考えらえるが、実質利用する価値があるのはこの二つ 二分方法 単純かつ、タフ ( ロバスト ) だが、遲い ニュートン法 上手く行けば速い 上手くゆかない場合があり、その時には発散する ロバストネスと、速さは矛盾する # 物理の「不確定性原理」によく似ている cf. 培風館、一松先生の翻訳 ニュートン法の収束性に関する定理がある 当りまえの結果すぎて役に立たない 二分法なら、確実に収束する 二分方法の最初の状況 f(a) > 0, f(b) < 0 となる a, b があるとする # この仮定はすごく狡い。 # このような a, b を求めることが、そもそも大変。 # この仮定が成立すれば、区間 [a,b] に、少くても一つ ( 一般には奇数個 ) の解の存在がわかってしまう。 m = \frac{a+b}{2} として、 f(m) > 0 ならば、 a <- m f(m) < 0 ならば、 b <- m とする。 もちろん、 f(m) = 0 ( 実際には、 |f(m)| < \epslon ) ならば、 m が答 # 計算量 ( どの位で、計算が済むか ? ) 今の計算機における単精度実数は、24 bit 程度の精度を持つ 二分法では、一回の反復で、1 bit ずつ決定している => 最大 23 回行えば、答が出る # 繰り返し回数は、欲しい精度による # 十進三桁であれば、二進十桁なので、10 回反復すればよい 二分法は、ロバスト(タフ)なので、確実に答えが得られる # 答 ( の性質 ) が良くわかっている問題は、ニュートン法を使う 本当に答が解らない ( 新しい問題 ) 場合は、二分法でやる # 新しい問題をニュートン法で解いて、答えがでなかったら... # そもそも解のない問題だったのかそれともニュートン法に問題が ? # 二分法で答がでなければ、そもそも問題に答がないといえる # => 開始の a, b がそもそも見付からない # なぜ、ニュートン法で解けない場合があるのか ? ( 来週詳しく説明する ) # f'(x) が 0 になるとだめ # => アルゴリズムそのものの欠点 # ただ、ニュートン法だと、単精度の場合で 5, 6 回で答がでる # 単精度 倍精度 # 二分法 24 52 # ニュートン法 5, 6 5, 7 最初の a, b, を求めるには ? => 一般的な方法はない 普通はグラフをかいてみる # グラフを書くことは、ほぼ、方程式をといているのと同じ # 線型の場合は簡単 ( 必ず、作れる ) # 非線型の場合は、どんな方法に対しても、その反例となる例が作れる # 数学的はよくわからないが.. 通常問題を解くのは、物理の問題であり、物理的には、「ここらへんに答えがある」ことは予め解っていることが多い ## なぜ、「物理の問題」は「解がある」か ? ## 連続が保証されている ( 慣性があるため.. ) ## 「堅い」問題は、解くのが楽 ## 紙が風にふかれてたなびくような計算は大変 ## 鉄板に力がかかるような問題なら計算は楽 ## cf. ## 木の葉が落るような場合の予測は難しい ## 簡単な摂動で、解が大きく変る ## 石が落るような場合の予測は簡単 # 教科書には、色々な解法が解てあるが... この二つさえ押えておけば Okey == p. 240 では、収束判定をせずに 20 回繰りしたら終りにしている [問題] f(x) = \cos(x) - x