非線形方程式の反復解法
非線形方程式 f(x) ＝ 0 の解を各種の反復法によって効率的に求めよう．
基礎知識
基本的な反復解法の概要は次の通り．
- 反復写像
- 代数的な数式変形：f(x) = 0 → x = g(x)
この手法には，数式の変形方法によって様々なバリエーションがある．
- 漸化式：xn+1 = g(xn)
- 収束条件：任意の x に対して |g'(x)| ＜ 1
実際には任意の x でなくてもよい．
最低限，反復過程内で取り得る x の値の範囲内で |g'(x)| ＜ 1 であれば収束する．
- ニュートン法
- 反復写像の変種．
- 漸化式： xn+1 = xn - f(xn)／f'(xn)
要するに写像関数を
g(xn) ＝ xn - f(xn)／f'(xn)
と定義した反復写像でもある．
ただし，これはあくまでも近似式であり，
厳密には数式 x = g(x) = x - f(x)／f'(x) は成立しない．
- 収束条件：f(x) が単調増加関数または単調減少関数
- 試行錯誤法
- 収束条件：f(x) が単調増加関数または単調減少関数
- 単調増加関数の場合：
- もし f(xn）＞ 0 ならば xn ＞ x なので，
xn+1 ＝ xn ー δn とする．
- もし f(xn）＜ 0 ならば xn ＜ x なので，
xn+1 ＝ xn ＋ δn とする．
- 単調減少関数の場合：単調増加の逆．
この手法には，刻み幅 δn の設定方法によって
様々なバリエーションがある．
- 二分法
- 試行錯誤法の一種．刻み幅を δn+1＝δn／2 とする．
- 収束条件：試行錯誤法と同じ．
- 反復回数 n に対して，誤差が 1／2n に比例して小さくなる．
なお，単調増加／単調減少とは次のような性質である．
また，f'(x) ＝ df(x)／dx である．
実験
平方根 √A の計算の基本プログラム
sqrt.c（DL）について，
以下の作業に取り組め．
- まずは，sqrt.c のコードおよびコメントを熟読せよ．
- ソースファイルに記述されている「実験(1) ニュートン法」を実行し，
解析結果が正しいことを確認せよ．
また，ニュートン法と二分法の反復回数を比較せよ．
さらに，関数f(x) の定義を単調増加 → 単調減少へ変更し，
二分法が失敗することを確認せよ．
ニュートン法の動作イメージ |
二分法の動作イメージ |
- 「実験(2) 反復写像の不適切な使用例」を実行し，
解析に失敗する（収束しない）ことを確認せよ．
そして，その原因を考察せよ．
Hint：Lipschitz 条件の成立する範囲は？
- 「実験(3) 反復写像の適切な使用例」を実行し，
解析に成功することを確認せよ．
そして，その原因を考察せよ．
Hint：同上
不適切な反復写像の動作イメージ |
適切な反復写像（縮小写像）の動作イメージ |
課題
基本プログラムを元にして，
ニュートン法および二分法による
立方根3√A の計算プログラム cbrt.c を作成せよ．
結果が正しいかどうかは，３乗してAと比較すれば確認できる．
ただし，二分法については，
関数f(x) が単調増加／単調減少のどちらの場合であっても
適切に動作するように実装せよ．
（基本プログラムでは単調増加の場合だけしか対応していない．）
この場合，f(x) がどちらの性質をもつのか？
自動判別する機能も追加する必要がある．
Hint: 初期値（下限値と上限値）を入れ替えると簡単．
例えば，f(x0)＞0 なら x0 を上限値，
x1 を下限値にする．
x1＞x0（下限値＞上限値）だとしても気にしないでよい．
Why?：単調増加から単調減少への変更は，
厳密にはY軸の反転（グラフの上下反転）ではあるのだが，
右上がりか？左上がりか？という大まかな性質にだけ注目すると，
X軸の反転（グラフの左右反転）でもあるので，
x の上限値と下限値を交換しても構わない．
なお，不要なコードについてはすべて取り除いておくこと．
コメント文や表示内容についても適切に変更しておくこと．
(c) 2017, yanagawa@kushiro-ct.ac.jp