Решение линейной системы
$A \times X = B$, имеющей циркулянтную или блок циркулянтную матрицу коэффициентов существенно быстрее получить используя быстрое преобразование Фурье. Когда матрица BCCB имеет правильную квадратную форму , т.е.
$M = N$ и BCCB в форме
$N^2 \times N^2$ , тогда Block Circulant с Circulant Block (BCCB) матрица полностью описывается своим первым столбцом.
Пример матрицы BCCB размера
$4 \times 4$:
$A = \left(\begin{array}{сссс} 95 & 62 & 31 & 76 \\ 62 & 95 & 76 & 31 \\ 31 & 76 & 95 & 62 \\ 76 & 31 & 62 & 95 \end{array}\right)$$A = \left(\begin{array}{сс} M1 & M2 \\ M2 & M1 \end{array}\right)$подматрица
$M1$ - это циркулянтная матрица
$\left(\begin{array}{сс} 95 & 62 \\ 62 & 95 \end{array}\right)$подматрица
$M2$ - это циркулянтная матрица
$\left(\begin{array}{сс} 31 & 76 \\ 76 & 31 \end{array}\right)$правая часть системы линейных уравнений:
$B = \left(\begin{array}{с} 75 \\ 61 \\ 49 \\ 27 \end{array}\right)$$C = \left(\begin{array}{с} 95 \\ 62 \\ 31 \\ 76 \end{array}\right)$ - первый столбец BCCB матрицы A.
$fftB = fft1(B)$$fftC = fft1(C)$Решение линейной системы
$A \times X = B$ на основе преобразования Фурье
$Y = ifft1\left(\frac{fftB}{fftC}\right)$Здесь
$fft1$ представляет собой одно-мерное быстрое преобразование Фурье,
$ifft1$ обозначает соответствующее обратное преобразование, а деление является покомпонентным.
$Y = \left(\begin{array}{с} -0.410845 \\ 1.246657 \\ -0.687639 \\ 0.654858 \end{array}\right)$Но верное решение полученное методом Гаусса будет:
$Y_{ист} = \left(\begin{array}{с} -0.274883 \\ 1.276399 \\ -0.823601 \\ 0.625117 \end{array}\right)$Почему FFT решение системы не совпадает с решением по методу Гаусса в случае когда матрица
$А$ это матрица BCCB?
В случае же когда матрица коэффициентов
$A$ является циркулянтной матрицей, решение на основе FFT совпадает с верным решением, я проверял это.
Спасибо.
Редактировалось 1 раз(а). Последний 10.11.2017 14:28.
