共役勾配法の解法について

質問

Ax = b の形の式を共役勾配法で解く方法は，インターネットでいくつか見つけることができました．

しかしながら，Ax = b　の解が１つでない場合などに，
||Ax-b||^2+α||Cx||^2
（ノルムは２ノルム）を最小にする問題を，共役勾配法によって解く方法がわかりません．

最小自乗法に関する知識が必要なのかと思うのですが，どうにもならないのが現状です．

どなたかご存知ありませんでしょうか？

回答No.2

stomachman · ベストアンサー

> Ax = b　の解が１つでない場合
というんだから、おそらく、Ax = bは一次独立な式の数が変数の数より少ないのでしょう。で、追加の式
Cx=0
があって、これを含めると、一次独立な式の数が変数の数と丁度同じか、あるいは多いのだと思われます。ならば
Ax = b
(√α)Cx = 0
を両方合わせてひとつの連立方程式系だと思えば、
E(x) = ||Ax-b||^2+α||Cx||^2
を目的関数とする共役勾配法に帰着するでしょう。

補足

回答有り難うございます．

両方合わせて１つの目的関数として考えるという方法は思いつきもしませんでした．

共役勾配法には何回かの反復的処理が必要であると思われるのですが，反復の度にxだけでなくαの値も変化させた場合，適切な解は求まりますでしょうか？

共役勾配法は「今まで探索した方向には探索しない」という手法であると考えているので，αの値を更新する方法がわかりません．

また，実際にE(x)を特に当たっての反復式の作り方について，何か参考になるような文献，ホームページなどございませんでしょうか？

回答No.1

fuuraibou0

最小自乗法は、ｘ　と　ｙ　の１組のデータ（ｘ，ｙ）が　ｎ個あるとき、
ｙ＝ａｘ＋ｂ　で表したいなら、次の連立方程式を解けばよいですよ。

┌　　　　　　┐　┌　┐　┌　　　　┐
｜Σx^2 　Σｘ｜　｜ａ｜　｜Σｘ＊ｙ｜
｜　　　　 　 ｜＊｜ ｜＝｜　　　　｜
｜ Σｘ　　ｎ　｜　｜ｂ｜　｜　Σｙ　｜
└　　　　　　┘　└　┘　└　　　　┘

∴　逆行列（－１）を用いて、２行×２列を解くと、ａ、ｂ　が得られる。

┌　┐　┌　　　　　　┐－１　┌　　　　┐
｜ａ｜　｜Σx^2 　Σｘ｜　 　 ｜Σｘ＊ｙ｜
｜ ｜＝｜　　　　　　｜　＊　｜　　　　｜
｜ｂ｜　｜ Σｘ　　 ｎ ｜　　　｜　Σｙ　｜
└　┘　└　　　　　　┘　　　└　　　　┘

補足

最小自乗法の解法について回答いただき，ありがとうございました．

ただ，やはりこれによって||Ax-b||^2+α||Cx||^2なる問題を解く方法はわかりません・・・（涙