反復法の収束性

連立一次方程式の解の計算では、解の精度は行列の条件数に大きく影響されます。

方程式$Ax=b$ について、$b$に変化があるとき、方程式の解$x$がどのように変化するか、という問題を検討するとき、「条件数」という概念が利用されています。

条件数が大きいとき、$b$の小さい変動に対して、方程式の解$x$に大きい変化が発生します。このとき、解の計算が不安定であり、近似解の誤差が発生しやすいです。特に、反復計算法を利用して方程式の近似解を計算するとき、より多くの反復計算回数が必要となっています。

対称正規行列の場合、行列の条件数は以下のように定義されます。

$$ \kappa(A) = \frac{\lambda_{max}(A)}{\lambda_{min}(A)} $$

ここで、$\lambda_{max}(A)$は行列$A$の絶対値の最大固有値であり、$\lambda_{min}(A)$は行列$A$の絶対値の最小固有値です。

条件数のより詳細な検討は Wikipediaのページを参考にしてください。

今回の授業では、Hilbert行列の例を利用して行列の条件数と反復法の収束性を検討してみます。

1 準備

Hilbert行列を作成します。MATLABではhilb(n)という命令で$n\times n$のHilbert行列を作成することができます。

$$ H=( h_{ij})_{n \times n}, \quad h_{ij}=\frac{1}{i+j-1}\:. $$

Hilbert行列の性質を調べます。

(ill-posed, well-posed)

2. 反復法で連立一次方程式を解く

SOR法を使って、Ax=bの解を求めてください。ここで、$b$のすべての成分を1とする。

以下のコードでは、SOR法が関数として定義されています。特に、trilとtriuを使って、行列の下三角行列と上三角行列を取ることができます。

(下記のコードではなく、自分で書いたコードを利用しても良いです。)

課題1

3. ガウス消去法で連立一次方程式を解く

ガウス消去法を使って、Ax=bの解を求めてください。ここで、$b$のすべての成分を1とする。

以下、自分で書いたガウス消去法によって近似解を求めてください。(ピボット選択の使用は自由です。)

課題2

$N=3,4,5,6$の場合、Hilbert行列の条件数を調べて、ガウス法で得られた近似解の誤差との関係を検討してみてください。