テプリッツ・システムの高速解法に関する研究

テプリッツ・システムの解法とは、係数行列としてテプリッツ行列(主対角線に平行した要素が同一の値をとる正方行列)をもつ連立一次方程式を解く手法のことである。テプリッツ・システムの解法としては、対称行列に対して、レビンソンのアルゴリズムが、エルミート行列および一般の行列に対して、トレンチのアルゴリズムが、よく知られている。これらのアルゴリズムは主対角線に沿って部分テプリッツ行列を順次解いてゆくアルゴリズムであるが、部分テプリッツ行列の行列式が1つでも0になるとうまく動作しない。一方、本研究代表者らは、ユークリッド整除法を用いたテプリッツ・システムの解法を開発した。この解法は第2対角線に沿って部分ハンケル行列を順次解いてゆくアルゴリズムであり、部分ハンケル行列の行列式が0になってもうまく動作する。しかしながら、この解法は、計算精度に若干問題がある。そこで、本研究の目的は、主対角線に沿って部分テプリッツ行列を順次解いてゆくアルゴリズムでありながら、部分テプリッツ行列の行列式が0になってもうまく動作するアルゴリズムを開発することにある。そのことによって、従来のものと計算時間は同一でありながら、あらゆる行列に対応でき、かつ精度のよい新しい解法を提供することができる。61年度は、以下のことを実施した。(1)レビンソン・トレンチアルゴリズムを一般化した形式でのユール・ウォーカー方程式の0(t log【^2t】の解法を開発した。(2)レビンソンアルゴリズムを一般化した形式での離散時間ウィナー・ホッフ方程式の0(【t^2】)の解法を開発した。(3)上記の2つの解法をプログラム化し、上記(1)の解法が、ユークリッド整除法に基づく解法よりも、計算精度がよさそうだということを確認した。購入設備は、上記プログラムのシミュレーションに用いられた。

テプリッツ・システムの解法とは、係数行列としてテプリッツ行列(主対角線に平行した要素が同一の値をとる正方行列)をもつ連立一次方程式を解く手法のことである。テプリッツ・システムの解法としては、対称行列に対して、レビンソンのアルゴリズムが、エルミート行列および一般の行列に対して、トレンチのアルゴリズムが、よく知られている。これらのアルゴリズムは主対角線に沿って部分テプリッツ行列を順次解いてゆくアルゴリズムであるが、部分テプリッツ行列の行列式が1つでも0になるとうまく動作しない。一方、本研究代表者らは、ユークリッド整除法を用いたテプリッツ・システムの解法を開発した。この解法は第2対角線に沿って部分ハンケル行列を順次解いてゆくアルゴリズムであり、部分ハンケル行列の行列式が0になってもうまく動作する。しかしながら、この解法は、計算精度に若干問題がある。そこで、本研究の目的は、主対角線に沿って部分テプリッツ行列を順次解いてゆくアルゴリズムでありながら、部分テプリッツ行列の行列式が0になってもうまく動作するアルゴリズムを開発することにある。そのことによって、従来のものと計算時間は同一でありながら、あらゆる行列に対応でき、かつ精度のよい新しい解法を提供することができる。61年度は、以下のことを実施した。(1)レビンソン・トレンチアルゴリズムを一般化した形式でのユール・ウォーカー方程式の0(t log【^2t】の解法を開発した。(2)レビンソンアルゴリズムを一般化した形式での離散時間ウィナー・ホッフ方程式の0(【t^2】)の解法を開発した。(3)上記の2つの解法をプログラム化し、上記(1)の解法が、ユークリッド整除法に基づく解法よりも、計算精度がよさそうだということを確認した。購入設備は、上記プログラムのシミュレーションに用いられた。