2005/07/19	数値解析学と演習 福井 先生

すこし、まとめをやって、その後 10:00 から、一時間位 (前期) Test

最初の 3 回は、計算機のしくみの話

# 5 月から本番

==

やったこと.. 「方程式を解く」
	非線型方程式
		# 問題としては、こちらの方が難しいが、プログラミングはこちらが簡単
		二分法
		ニュートン法
			この二つは一般的
		代数方程式
			特別な非線型方程式
	線型方程式
		ガウスの消去法
		LU 分解
		ヤコビ法
		ガウスザイデル法
		SOR 法

# 最適化以外の数値解析の殆どの話題が入っている。
#	幅広い視野で、広く浅く話題にしている。

==

[計算機のしくみ]
	ノイマン型計算機
		ストアード・プログラム方式
			# キャッシュの仕組とか..

	プログラムやデータをメモりに保存する形式
		文字 : 対応コードを决めるだけ
		二進法 : 十進法との違いを理解 ( 桁上りが違うだけ.. )
			# 現理的には簡単だが、慣れないと理解りにくい
			#	二進法と十進法の違いが理解れば、他の一般的な進数も解る
			#		cf. 60 進法 : 時計 ( 他にも日常的に利用している )
			負の数の扱い ( 表現方法 )
			 	=> 「2 の補数」を使っている
					正の数のパターンを 0-1 反転し、1 を加える



[非線型方程式]
	一般的には、答の個数を予測することができない
		# 個別の方程式が与えられれば個数が解ることもあるが.. (一般的には解らない)
		代数方程式場合には、n 個の解を持つことが解っている ( 複素数の範囲で )
			=> 実根に関してはわからない

		# 問題としては、こちらの方が難しいが、プログラミングはこちらが簡単

	[二分法]
		一次収束 ( 一度の反復に 1 ビット )
			1 -> 2 -> 3 -> 4 -> 5		# 24 bit に 23 回
	[ニュートン法]
		二次収束 ( 一度の反復で倍の精度が出る )
			1 -> 2 -> 4 -> 8 -> 16		# 24 bit に 6 回
			# 最初の 1 bit が大変
			#	一度、収束を始めると、直に収束する
	[代数方程式]
		平方根が出てくるの、その内部が負ならば、複素数
			=> 実根の場合は、個数が解らない ( 係数に依存する )

[線型方程式]
	連立方程式の解法
		数学的には、クラーメルの公式があるが..
			計算量が多いの数値計算では利用されない ( n^4 )


	数値計算の手法
		直接方法 ( 根の公式と同様に、定数回数の処理で、直接答を求める )
			=> 手法そのものには、誤差が含まれないが、計算機で計算すると誤差がしょうじる。
			=> 方程式に関する(詳細な..)知識が必要

		反復方法 ( 根の改良を繰り返すことにより、近似根を求める方法 )
			=> 手法自身が、誤差を含んでいる
				=> 方程式が与えられていれば Okey ( 条件が弱くてよい )
			=> 実行回数は、実際にやってみないと解らない
				# 根の性質や、初期値によって異る。

	[ガウスの消去法] # 典型的な「直接法」
		「『ある行(=式)の定数倍を他の行に加える』という操作を加えても、方程式の答が変らない」という性質を利用して、係数を、次々に 0 にするという方針で問題を解く
			# 行列の基本操作 ( この操作をしても、方程式の根を変ていない !!)
			## 他の問題を解く場合は、別の操作が必要 ( いつでも「基本操作」で良いわけではない cf. 後期に学ぶ「固有値」の場合)
			=> 順番を間違えなければ、一度 0 にした係数は 0 のまま計算が続けられる。
				=> \frac{1}{3}n^3 で、処理が終る

		基本は、3 重 Loop になる
			=> Loop の構成方式によって、色々な手法があるが、本質的には一つ
				# 他の方法はない => 違っていた、間違っている !!!

	[LU 分解]
		係数行列 A を、下三角行列 L と上三角行列 U の二つ行列の積に分解する
			A = LU
		方程式は、
			Ax = b
		を
			LUx = b
		とし、
			Ly = b
			Ux = y
		の二つの ( 特殊な ) 方程式を解く
			この個々の方程式は簡単に解ける ( n^2 位の時間で Okey )
			問題は、A を LU に分解する時に時間がかかる ( n^3 )

		# 結局、L, U は、「ガウスの消去法の手順」を覚えているだけ !!

		## 教科書では、ガウスの消去法と LU 分解は異る手法として説明しているが、結局、本質的な中身は同じ ( 考えてみれえば、そもそも、同じ問題を同じ方針で解く手法なので、手順が同じなのは当然 !! )。
		### プログラムを何度も記述してみると自然に解る。

	[ヤコビ法] # 反復法の例
		偏微分方程式を解く場合に、「対角要素が強い」という性質を利用して、修正の式を考える
			Ax = b に対して

			x' = Λ^{-1}(b - (A-ΛE)x )

					    a_11
				where Λ = (      a_22       )
				      			a_33


	[ガウスザイデル法]
		ヤコビ法で、計算の途中で新しい x を利用している

	[SOR 法]
		ガウスザイデル法で、修正する差分係数を、 1 ではなく 0 < ω < 2 とする
			=> 偏微分方程式の場合は ω = 1.8 - 1.99 が良いことが知られている
				# ω は係数行列 A によって、異ることに注意 !! ( 演習の問題では 0.8 位がよかった.. )

==

10:00 位から、試験開始