二分法
	一次収束
		一回の計算で 1 bit ずつ決定される。
		横軸に回数、縦軸に精度を取ると、直線になる
	二次収束
		一回目に 1 bit きまれば、二回目には、2 倍の 2 bit 決る
			# 三回目には 4 bit、四回目には 8 bit 決る
		横軸に回数、縦軸に精度を取ると、二次曲線になる
			=> 今日やる、「ニュートン法」

	# 三次以上の収束もあるが、あまり役に立たない。

	一次収束と二次収束では、最初の 1 桁がきまるまでは、一次収束の方が速いことに注意


ニュートン法
	x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}

	\frac{f(x_k)}{f'(x_k)} の部分は、修正項
		[原理] ( テーラ展開 )
			f(x+h) = f(x) + h f'(x) + \frac{h^2}{2} f''(x) + ..
				f(x+h) が 0 となるような h が欲しい
				2 次微分以後は、無視する

				0 = f(x+h) = f(x) + h f'(x)

				から、

				h = \frac{f(x)}{f'(x)}

	ニュートン法は、二次収束
		なので、一度収束が開始されると、吸い込まれるように根に収束する

	# この講義で利用する数学的な知識
	#	テーラ展開
	#	基本変換 ( 線型方程式の根を変えない )
	#	相似変換 ( 固有値を変えない )


ニュートン法の問題点
	f'(x) = 0 の場合に、問題がある
		# 一般に、数値計算の公式では、割り算を含むと、分母が 0 になる場合に破綻
		運が悪いと、f'(x) = 0 

	ヘンリッチの「数値計算入門」
		「ニュートン法」の収束定理
			区間 [a,b] で、
				f(a) と f(b) の符号が異る
				[a,b] で、変曲点を持たない
				      ならば収束する
		# これは、ほとんど「自明」
		#	「ニュートン法」の収束は一般にはいえない
		#		具体的な関数、区間が確定すればもちろん言える
		#		一般化すると、自明なことしかいえない
		#	「ニュートン法」の収束する初期値の区間を色分けすると面白い結果が..

ニュートン法が利用できる ( 値が収束する ) のは、その付近での関数の性質が判っている場合
	実際にそのような場合にだけ利用されている
		物理的な性質が判っている場合
		性質がわかるまで、「二分法」を使う
			平方根 \sqrt{a} の計算は、典型的な例
				f(x) = x^2 - a

	平方根 \sqrt{a} の計算でも、x が大きくなるとグラフが寝てくる
		数値の規格化を行うことよって、問題を単純化する
			a = b x 2^{2n} = b 4^n ( \frac{1}{4} < b <= 1 )
		となる b を求める。
			\sqrt{a} = \sqrt{b 4^n} = \sqrt{b} 2^n

			\frac{1}{4} < b <= 1
		 より
			\frac{1}{2} < \sqrt{b} <= 1
		なので、
			\sqrt{b} の値を表にして、数 (1) 回 ニュートン法を使えばよい
				単精度 24 bit の場合は 6 bit で Okey
					6 x 2 x 2 ( 二回.. ) で 24 bit

		# 永坂秀子/二宮市三/山下真一郎/浜田

n 変数のニュートン法
	\vec{x_k+1} = \vec{x_k} - \frac{F}{F'}
		F が行列
			F' の逆行列が必要になる点がちょっと複雑
				# カーマーカー法

	# 一変数のニュートン法を利用するような応用はすくない。
	# 多変数のニュートン法は利用することは多い。

==

# text p.12

ニュートン法の様々な話題

	p 次収束

	\lim_{k -> \infty} \frac{|x_{k+1} - x^*|}{|x_{k} - x^*|^p} = \lambda
		-> p 次収束

	f'(x) の計算
		f(x) が微分できない場合は ?
			数値微分で頑張る
				f'(x) = \frac{f(x_{k+1})-f(x_k)}{x_{k+1}-x_k}
			で近似
				収束が悪くなる ( 関数の性質による )
					 2 次にならない ( 1.5 次 ?? )
				多次元の場合などでは F' を計算するのが大変なので有効

==

[課題]
	\sqrt{2} の計算をニュートン法で行う

	締切	6/7
	Subject: 6/1 xxxx
	Cc: 自分の address
	本文:
		プログラム
		結果
		考察

	# 反復法の奇妙な振舞い
	#	一回目は理論通りにならない
	#		二度目以後は理論通りになることが多いのですが..

==

	\sqrt{2} の計算のニュートン公式

	x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}
	        = x_k - \frac{x_k^2-2}{2x_k}
	        = \frac{x_k^2+2}{2x_k}
	        = \frac{x_k}{2} + \frac{1}{x_k}

	最後の 3 つの式はどれも (数学的に..) 同じだが、どれがよいか ?
		実は、計算量は、最初のものが多いが、精度も最初の者がよい
		二番目は計算量は多少少いが、精度が悪くなる

	# 補正項は、精度が高い
	#	x_k より h の方が小さいので、結果的に丸め誤差も桁の小さい方まで保つ