はじめに
プログラミング云々ばかり言っていても、それがどのように計算されているかを知らないと仕様が無い。ということで数値解析を学んでいく。
基本的には
を参照しつつ、他書で補足する。
前回の復習
2. 非線形方程式の解
2.2 具体的な反復法
2.2.1 2分法
反復法の一種ではあるがより簡単な方法である2分法をまずは扱う。
2分法は中間値の定理を数学的な基礎とする。すなわちが
で連続であるとして、もし
となるような
が存在すれば、
となるような
が
の間に少なくとも1つ存在する。これを基に以下のようなアルゴリズムを基に近似解を求める。
を満たすようなとある
を
の値として取る。また収束判定用に
を設定する。
- 新たにを定義する。
- もし
ならば
に進む。そうでなければ
に進む。
- もし
ならば
ならば
として
に進む。
ならば
に進む。
とする。
収束判定条件に着目すると、初めて収束判定条件を満たすような反復回数をとおくと
が成り立つ。したがってを満たすような最小の
がこのアルゴリズムの計算量である。
2.2.2 Newton法
二分法は安全確実ではあるものの計算に時間がかかる。より高速な方法が法である。
微分可能な関数のグラフの解
の付近の領域を考える。
の適当な初期値
を取る。次に点
における
の接線を引き、この接線と
軸の交点を
とおく。更に点
における
の接線を引き、この接線と
軸の交点を同様に
とおく。この操作を
回続けることで得た交点を
とすれば、点
における
の接線は
で与えられる。これととの交点
を求めれば、
が得られる。こうして定義できる数列を用いることで近似解を求めることができる。
いま求めたい方程式の解を含む適当な区間
において
は
級かつ
とすれば、
を得る。したがってを含む適当な区間
を取れば、系2の仮定が満たされるから、
法は
の解
に収束する。
法では現在の
の値が真の解に近づいているかを知る確実な方策が無い。そのため、ある正数
を与え、
となった時点で計算を終了させ、とする。
以上をまとめると、法は以下のようなアルゴリズムで定義できる:
- 初期値
および
を設定する。
とおく。
ならば
に移り、そうでなければ
に移る。
とおき、
に戻る。
として計算を終了する。
法の計算量は、2分法よりも少なく高速である。求めたい方程式の解を
とし、
とおく。このとき
と
との関係を考えると、
である。と書き換えることができることから、
の定理より
を満たすようなが存在する。これらを代入し、
を考慮すれば、
を得る。これは法が急速に誤差を収束させていることを意味する(またこれは反復列
が2次収束することを意味する。)。
他方で2分法に比べ、法は計算に失敗する確率が高い。これは与えられた
と初期値
に由来する。
前回示した反復法の収束条件を基に法の収束性を示す。
(
が成り立つから、が成り立ち、特に
である。
)
なお法以外にも反復列を得る方法はいくつか存在する。
反復する度にを計算するのが難しければ、簡易
法
を用いる方法がある。また微分値を求めること自体が難しい場合は、
に注意して、セカント法
が利用できる。1次収束も2次収束もしないものの、その中間くらいの収束性を示すことがある。ただしこの方法にはに加え
も初期値として用いる必要がある。
今回の復習
- 2分法の基礎となる定理を述べよ。
法のアルゴリズムを説明せよ。
参考文献
- 伊理正夫・藤野和建(1985)「数値計算の常識」(共立出版)
- 菊地文雄・齊藤宣一(2016)「数値解析の原理 現象の解明をめざして」(岩波書店)
- 齊藤宣一(2012)「数値解析入門」(東京大学出版)
- 齊藤宣一(2017)「数値解析」(共立出版)
- 高橋大輔(1996)「理工系の基礎数学8 数値計算」(岩波書店)
- 山本哲朗(2003)「数値解析入門[増訂版]」(サイエンス社)
- 日本応用数理学会 監修・ 櫻井 鉄也 編・ 松尾 宇泰 編・ 片桐 孝洋 編(2018)「数値線形代数の数理とHPC」(共立出版)
- Ridgway Scott, Larkin (2011), "Numerical Analysis", (Princeton University Press)