1 線形方程式の解法の選択
2 参考文献および参考書の記述
線形方程式, >>> 実対称/複素エルミート, >>> 省メモリ型 >>> 最急降下法


概要

  • CG 法の2次関数最小化として導出過程で現れるアルゴリズム.
  • CG 法と比べて,一般に収束性はあまり良くない. ただし,CG 法で保存する必要のあるベクトルはの計4本であるのに対し,最急降下法ではの3本と少なく,メモリの制約がある場合には選択肢の一つとなりうる.

導出

線形方程式の真の解をと置く. この時, 2次関数

 
 

は, を満たす. そこで, 2次関数の最小化問題

 
・・・(1)
 

を(反復法で)解くことで, 線形方程式の解を得ることを考える.

逐次最小化法

最小化問題(1)を解く単純な反復法として, 適当な初期近似解に対し,

  1. 何らかの方法で, 探索方向ベクトルを定める.
  2. を最小化するようを設定し, のように解を更新する.

を繰り返すアルゴリズムが考えられる. このアルゴリズムは逐次最小化法とよばれ, 1次元最小化の係数として容易に計算出来る.

最急降下法

探索方向ベクトルの設定によって様々な逐次最小化法が存在するが,

 
 

のようににおけるの最急降下方向に選ぶのが最も自然な方法であろう. この方法は最急降下法と呼ばる. 最急降下法は目的関数が単調に減少し, 直感的には優れた方法ではあるものの, 計算精度および収束性の面から実用的でないことが知られている.

アルゴリズム

最急降下法

  1. Set an initial guess
  2. Compute
  3. For
  4.   
  5.   
  6.   
  7. End For

前処理付き最急降下法

  1. Set an initial guess
  2. Compute
  3. For
  4.   
  5.   
  6.   
  7. End For

サンプルプログラム

準備中

適用事例

準備中

参考文献および参考書


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-07-05 (金) 09:59:00 (3287d)