「数値解析」2019

講義科目　「数値解析」（科目コードFEN-AM2d10L1）2019年度A1A2ターム

担当教員：松尾宇泰教授
（メールでの連絡：matsuo(あっと)mist.i.u-tokyo.ac.jp；読み落としが非常に多いので反応がなかったら再送をお願いします）

月曜日 4限（14:55～16:40）駒場キャンパス 12号館 2階 1225講義室

お知らせ
講義「数値解析」では，ある程度プログラミングを前提としてレポート課題を課します．
履修を予定する人は，早めに「数値計算」のプログラミングの練習をしてみることを勧めます．
（このページ末尾の計算環境の例を参照）．

2020/3/23 ものすごく遅くなりましたがレポートについて，一部，コメントをフィードバックしました．ITC-LMSでご確認ください．
12/17 レポート第２回が出題されています．忘れずに提出してください．
12/17 講義資料９（補足）と資料１０（参考）を追加しました．
12/9 講義資料９と常微分方程式の数値解法のプログラムサンプルを追加しました．
12/2 講義資料を追加しました（数値積分まで）．
11/20 サンプルプログラム（不動点反復，Lagrange補間）を追加しました．
11/15 週明けに配付予定の資料とNewton法のサンプルプログラムを追加しました．
11/13 レポート第１回を出題しました．履修者は忘れずに提出してください．
11/13 プログラムをひとつ追加しました．
11/11 講義資料とプログラム等をまとめて更新しました．

成績：　レポートと期末試験により判定する

期末試験：
2020年2月3日，4限（14:55～16:40)
1106教室（駒場キャンパス11号館2階）
A4サイズのメモ（表裏可）持ち込み可．（※自分で作成したものであれば内容は問わない．他人の講義ノートのコピー等は不可．）

講義予定：

  1. 9/30 イントロダクション/数値の表現と誤差
  2. 10/7 連立一次方程式の解法 （直接法，LU分解）
  3. 10/21 連立一次方程式の解法（反復法）
  4. 10/28 固有値問題の解法（べき乗法）
  5. 11/11 固有値問題の解法（QR法）
  6. 11/13 線型計算のその他の話題（特異値分解と最小二乗法，大規模固有値問題）
  7. 11/18 非線形方程式
  8. 11/25 関数の近似と補間
  9. 12/2 数値積分
  10. 12/9 常微分方程式の数値解法
  11. 12/16 偏微分方程式の数値解法

講義目次（修正版）：（講義中破綻を来したので整理します）
1. 数値の表現と誤差
2.線形方程式
　2.1 連立一次方程式
　　2.1.1 導入
　　2.1.2 直接法
　　2.1.3 反復法
　2.2 固有値問題
　　2.2.1 導入
　　2.2.2 べき乗法
　　2.2.3 QR法
　　2.2.4 発展的話題：特異値分解とその応用
　　2.2.5 発展的話題：大規模固有値問題
（以下，予定）
3. 非線形方程式
　3.1 導入
　3.2 不動点反復法
　3.3 Newton法
4. 関数の近似と補間
　4.1 導入
　4.2 Lagrange補間
　4.3 Spline補間
5. 数値積分
　5.1 導入
　5.2 補間に基づく公式
　5.3 変数変換型公式
6. 常微分方程式の解法
　6.1 導入
　6.2 一段法
　6.3 多段法
7. 偏微分方程式の解法
　※講義全体の進捗状況に依る

補足資料
すべてPDFです．

  1. 資料１．数値の表現と誤差（9/30配付）
  2. 資料２．連立一次方程式（直接法）（10/7配付）
  3. 資料３．連立一次方程式（反復法）（10/21配付）
  4. 資料３（補足）．連立一次方程式（CG法の導出）（10/21配付）
  5. 資料３（補足）．連立一次方程式（CG法の実際の挙動）（10/21配付）
  6. 資料４．固有値問題（11/11配付）
  7. 資料４（補足）．固有値問題（Hessenberg QR法の計算量）（11/11配付）
  8. 資料５．発展的話題（特異値分解，大規模固有値問題）（11/11配付）※訂正版：初出はMoore–Penrose逆行列の表記に誤りがありました．
  9. 資料６．非線形方程式の解法（11/18配付）
  10. 資料７．補間（11/25配付）
  11. 資料８．数値積分（12/2配付）
  12. 資料９．常微分方程式（12/9配付）
  13. 資料９（補足）．発展的話題：幾何学的数値解法（12/16配付）
    14. ※訂正版：初出はsymplectic Euler法の定義が誤っていました．
  14. 資料１０（参考）．偏微分方程式の数値解法（12/16配付）

レポート課題
以下のレポートが出ています．

レポート第２回：

  1. レポート課題２（12/16出題；2020/2/14締切）

    2. ITC-LMS経由で提出してください．また，受け取った後の整理で混乱するため，「PDF形式での提出」「ファイルは（ソースファイル（もしあれば）を含め）ひとつのPDFに結合した状態での提出」に協力をお願いします．

レポート第１回はすでに締め切りました．
レポート１課題を配付した際，紙ベースでの提出と表示しましたが，学生の皆さんの意見も聞いた結果，LMS提出（＝電子提出）に切り替えました．本件についてはLMSも参照してください．

技術的な理由で電子提出が困難な場合は，松尾まで連絡をください．
  1. レポート課題１（11/13出題；12/13締切）

サンプルプログラム
講義で紹介した話題について，サンプルプログラムをいくつか提供します．

  • MATLAB実行例(PDF)：10/7の講義で実演したMATLAB実行例（対話的）です．簡単な計算や確認であればこのように対話的にやるのが簡単です．
  • 上のMATLABプログラムコード（m形式）：上記をMATLABのプログラムコードとしてMATLAB m形式ファイルとして用意したものです．このように，複雑な手順の実験を繰り返すときは，対話的にやるよりは「プログラムソースコード」を書いて，それを「実行」する形で行う方がシステマティックで便利です．
  • CG法の実行例（m形式）：MATLABの前処理付きCG法ルーチン（pcg）を用いて，実際にCG法を動かすためのサンプルプログラムです．
  • QR法（原型）の動作例（m形式）：QR分解と行列積でQR法の原型を動かしてみる動作例です．実際に世の中で実装され使われているQR法実装とはかなり乖離があり，動作は遅く複素固有値ペアがある場合固有値は求まりませんが，簡単な場合には上三角行列への収束を確認できます．
    追記：行列の副対角の取り出しは，reshape(tril(A,-1), [], 1); が速いようです（田中健一郎准教授案）
  • Newton法の動作例（m形式）：単純なスカラー方程式の場合のNewton法の実装・動作サンプルです．初期値を色々変えてみるとNewton法の挙動の不安定性が観察できて楽しいです．
  • 不動点反復の動作例（m形式）：講義で説明した例題の不動点反復の動作例です．根を2つ持つ問題なので注意してください．色々な初期値から始めてみると収束・発散の様子が観察できて楽しいです．
  • Lagrange補間の例（m形式）：等間隔標本点，およびChebyshev点によるLagrange補間の例です．点数を増やしても必ずしも収束しないことに注意してください．被近似関数は2種類用意してありますが，その他の関数も試してみることをお薦めします．
  • 微分方程式の数値解法の例（m形式）：単純な，Dahlquist のテスト方程式の場合のサンプルプログラムです．テスト方程式の係数と時間刻み幅の積が安定領域に入るかどうかで挙動が変わる様子が観察できます．

参考書：

  • 『数値解析入門[増訂版]』（山本哲朗；サイエンス社）数学寄り
  • 『数値解析[第２版]』（森正武；共立出版）物理・直観寄り
  • 『数値解析入門』（齊藤宣一；東大出版界）中間
  • 『MATLAB/Scilab で理解する数値計算』（櫻井鉄也；東京大学出版会）MATLAB/Scilabに特化，バージョンはやや古い

計算機環境の例：
特に環境は定めませんが，例えば以下のようなものがあります．

  • Scilab：無料の数値計算環境．上記のような参考書のほか，ネット上に各種解説もある．一般のプログラミング言語より数値計算環境が整えられており，比較的手軽に計算しやすい．
    なお公式の解説文書はこのあたりにあります．
  • MATLAB：プロの研究者もよく使っている数値計算環境．様々な数値計算手法がすでに用意されており，なるべく苦労せずに数値計算を実行するには極めて有効．ただしその分，実行時のオーバーヘッドが大きく，大規模数値計算には向かない（メモリと実行時間の両方の面で）．本来有償ソフトウェアだが，東大では2019年度より大学全体でサイトライセンス契約を結び，東大所属者であれば所属期間中自由に使えるようになった（私物PCにもインストールできる；インストールはこちらを参照．巨大ファイルのダウンロードが伴うので作業環境には注意！）．なお上記Scilabは，このMATLABにほぼ互換．
  • C言語，FORTRAN，Java等：数値計算用とは限らない一般のプログラミング言語を用いてもよい．GNU系を中心に無料のものを色々入手可能．機械学習方面はPythonが主力（数値計算には，ライブラリnumpyが必要）．また，最近はJuliaが数値計算も高速だと話題になっている（が松尾はまだ使ったことなし）．

計算データの例 実際のデータを使って計算をしてみる場合は，例えば以下で入手できる．

  • SuiteSparse Matrix Collection：様々な応用分野の行列データがストックされているアーカイブ．MATLABにすぐ読み込める mat 形式のほか，いくつかの形式でデータが提供されている．「対称」「正方」「正定値」など属性を指定して行列を検索できる．Pythonでも scipy の io.mmread ルーチンで読み込めるらしい（伝聞；未確認）．