数値線形計算の期末試験終了

いやぁ危うく黒歴史の一ページを更新するところだった．11時頃，教科書を読みながらふっとベッドに横たわって，意識が戻ったら試験開始X分前（爆
開始予定時刻10分遅刻程度で済んでよかった．実際の試験開始は予定時刻の5分過ぎくらいだったので実害は5分．
思い出すのは1年の夏，やはり寝坊で記号論理学Iの試験に30分遅刻したこと... あれはやばかった．おかげで（？）可だったし．

（自分の）講評

$\left(\begin{matrix} a_1 & b_1 \\ c_1 & a_2 & b_2 \\ & \vdots & \vdots & \vdots \\ & & & c_{n-1} & a_n \end{matrix}\right)$

LU分解について
1. ↑の三重対角行列をLU分解
  LU分解の手続きそのものはともかく，↑の行列に適用したらUの対角成分（とLの対角1つ下）があらわな式では求まらなかった．急いでいたので「 $X_k$ は $X_1=a_1$ , $X_{k+1}=a_{k+1} - b_1c_1/X_1$ に従う数列」とか導入してゴマかす．まぁLは三重対角かつ単位下三角に，Uは三重対角かつ上三角になったんでいいじゃないの？
2. 上のLU分解を用いてAx=dを解く手続き
  LもUも1行に2成分しか並んでないので（しかもLは対角が1），Ux=yの後退代入もLy=dの前進代入も楽．
3. それらの処理が食う演算量，記憶容量
  加減算，乗算ともにn+n+nくらい．記憶容量はあからさまな疎行列なので(3n+n+2n+n+n+n)*2word程度か（xはdに上書きできることはできるが...）
固有値問題のQR法について
1. Hessenberg形とは何か，それがQR法で役立つ理由
  i>j+1で $a_{ij}=0$ ，はいいんだが，今気付いたが「役立つ理由」書き忘れてた orz
2. HessenbergなAに対するQR法の手続きを書き，反復過程でHessenbergが保たれることを説明（証明）せよ
  *1 これは結局書き終らなかった．まず $A_k=QR$ とQR分解してから $A_{k+1}\equiv RQ$ とするのがQR法で，このとき登場するQ, R, RQがHessenbergを保つことを言うわけだ．修正Gram-Schmidt*2で作られたQとRについて，Aを成分で書いてうんぬんしてたら時間切れ．
以下から任意の2つを選んで解け*3
1. 行列の条件数とは何か，いつ役に立つか
  条件数κ= $||A||\cdot||A^{-1}||$ （ノルムは適当）はAx=bを解いたときの相対誤差の見積りに使われる：
  $\frac{||\Delta x||}{||x||}$ < $\approx$ $\kappa\left(\frac{||\Delta A||}{||A||} + \epsilon\frac{||\Delta b||}{||b||}\right)$
  それとCG法での収束を調べるのに使われる：
  $\phi(x_{k+1})$ < $\approx$ $4\phi(x_k) \left(\frac{ \sqrt{\kappa}-1 }{ \sqrt{\kappa}+1 }\right)^{2k}$ （←記憶を便りに書いたのでちょっと間違えた．誤差eがこうやって縮小するんだと思ってた）
  κ>>1なる行列についてのAx=bは悪条件であると言われ，特異に近いとみなされる．実際に定義に従って計算することは稀で，LAPACK等のルーチン（DGESVXなど）が付随的に算出したもので事後判断をする．
2. 共役勾配法が直接法と反復法の両方の性格を併せ持つと言われる理由
  CG法においては最適化の方向vector $p_k$ をA-共役となるように選ぶことで $x_0$ + span[ $p_1$ , ..., $p_k$ ] における大域的な最適化を実現しており，空間の次元をnとしたときn回以下で（誤差を無視すれば）厳密解x s.t. Ax=bと一致する解を算出できる．しかし（誤差のせいで破綻の可能性があったりするし）実際にn回のiterationを経ずに「解」とみなしたりと，反復法の性格もある/利用できる．