巡回行列を使った線型方程式系の解法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/11 14:46 UTC 版)
「巡回行列」の記事における「巡回行列を使った線型方程式系の解法」の解説
線型方程式系を行列で次のように表す。 C x = b {\displaystyle \ \mathbf {C} \mathbf {x} =\mathbf {b} } ここで、 C {\displaystyle \ C} が大きさ n {\displaystyle \ n} の巡回行列であれば、循環畳み込みとして次のように方程式を表せる。 c ∗ x = b {\displaystyle \ \mathbf {c} *\mathbf {x} =\mathbf {b} } ここで、 c {\displaystyle \ c} は C {\displaystyle \ C} の最初の列であり、ベクトル c {\displaystyle \ c} 、 x {\displaystyle \ x} 、 b {\displaystyle \ b} は双方向に循環的に拡張される。畳み込み定理を使うと、離散フーリエ変換を使って循環畳み込みを次のような形式にできる。 F n ( c ∗ x ) = F n ( c ) F n ( x ) = F n ( b ) {\displaystyle \ {\mathcal {F}}_{n}(\mathbf {c} *\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )} 従って、次のようになる。 x = F n − 1 [ ( ( F n ( b ) ) ν ( F n ( c ) ) ν ) ν ∈ Z ] {\displaystyle \ \mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\nu \in \mathbf {Z} }\right]} このアルゴリズムは通常のガウスの消去法よりも高速であり、特に高速フーリエ変換を使えば高速になる。
※この「巡回行列を使った線型方程式系の解法」の解説は、「巡回行列」の解説の一部です。
「巡回行列を使った線型方程式系の解法」を含む「巡回行列」の記事については、「巡回行列」の概要を参照ください。
- 巡回行列を使った線型方程式系の解法のページへのリンク