Решение СЛУ специального вида. Как быстрее решить?

[liter]

Итак, имеем задачу: Дана СЛУ вида:
(A B) (C1)
(-B A) (C2)

где А и В - квадратные матрицы [N x N], о которых ничего не известно (разве что вся эта система ЛНЗ), С1 и С2 - столбцы свободного члена [N х 1].
В итоге имеем матрицу [2*N x 2*N].
Сейчас применяю метод Гаусса (матрица решается 1 раз. То есть в цикле, конечно, раз 500, но при этом меняется и матрица и столбец свободных членов) .
Подскажите, как можно ускорить процесс? Просто нормальным явлением является 500 итераций цикла, в каждом из них решается по 1-й матрице 800 х 800

[Yuri Gendelman]

Можно свести решение Вашей системы порядка 2N к обращению матрицы порядка N и решению системы порядка N:

1. Запишем исходную систему в виде
\left( \begin{array} {cc} A & B \\ -B & A \end{array} \right) \left( \begin{array} {c} X_1 \\ X_2 \end{array} \right) = \left( \begin{array} {c} C_1 \\ C_2 \end{array} \right)

2. Перепишем ее в виде двух матричных уравнений порядка N
A X_1 + B X_2 = C_1
- B X_1 + A X_2 = C_2

3. Из второго
X_2 = A^{-1} C_2 + A^{-1} B X_1

4. Подставим в 1-е:
A X_1 + B A^{-1} C_2 + B A^{-1} B X_1 = C_1
или
\left( A + B A^{-1} B \right) X_1 = C_1 - B A^{-1} C_2

Алгоритм:
- обратить матрицу A;
- решить систему 4-б) и найти X_1;
- подстановкой X_1 найти X_2 из 3)

И еще некоторые замечания:
5. Для решения больших систем итерационные методы часто эффективнее, чем прямые (типа Гаусса). Например, попробуйте метод сопряженных градиентов.
6. Поскольку у Вас ~500 итераций на шаге можно попробовать применить идею преград: на начальных итерациях иногда нет смысла решать СЛУ слишком точно.
7. Если матрица A от шага к шагу меняется мало, можно применить алгоритм корректировки обратной матрицы при изменении элемента / столбца / строки прямой. Алгоритм работает быстро, но неустойчив, так что нужно периодически выполнять обращение.
-

[liter]

Очень интересные мысли. Насчет обращения матрицы А - обмозгую и наверняка применю.
По поводу "7" - матрица меняется мало (метод дискретных вихрей для сингулярного интегрального уравнения). Но матрица меняется вся (элементы матрицы - значение ядра в точке). Вопщем, все попробую. Как сделаю - отпишусь.

[liter]

Еще одна поправка. Исследовал матрицы и увидел: Матрицы А и В тоже имеют особый вид:
А=\left(\begin{array}{ccccc}a_0&a_1&a_2&a_3&a_4\\a_-_1&a_0&a_1&a_2&a_3\\a_-_2&a_-_1&a_0&a_1&a_2\\a_-_3&a_-_2&a_-_1&a_0&a_1\\a_-_4&a_-_3&a_-_2&a_-_1&a_0\end{array}\right)
Матрица В аналогична, но не равна матрице А (в общем случае)
Возможно ли еще ускорить за счет этого замечания (весь вечер парился - ничего не придумал)

[Yuri Gendelman]

Матрицы вида $A_i_j = a_{i-j}$ называются тёплицевыми (теплицевыми, Toeplitz matrix). Можете попробовать копать в эту сторону, т.к. для них существуют быстрые алгоритмы, напоминающие FFT. К сожалению Ваша главная матрица - не теплицева. Матрица в предложенном мною алгоритме: $A + B A^{-1} B$ , скорее всего тоже не теплицева.

[Руст]

Если бы матрицы были цикличными, т.е. $a(i,j)=a_{i-j(mod \ n)}$, то решение действительно бы упростилось. Сойство цикличности матриц сохраняется и для произведений и для обратных, что не верно для теплицевых.

[liter]

Спасибо, буду копать.
Блин, матрицы - вообще не моя специализация. (в смысле, специальные матрицы)

[ГАЗ-67]

В 1984 году я столкнулся с этой же проблемой в этой же задаче . Решается весьма просто .
За праздники постараюсь вспомнить .

[liter]

Буду очень благодарен.
Люди, если кто знает ссылку - киньте плз. Ничего хорошего не нашел.
Кстати, проверил - матрица не циклическая.
Блин. 5 дней осталось до того, как сдавать диплом. Если не успею - придется с методом Гаусса сдавать (не хочется).

[Comga]

liter писал(а):

Сейчас применяю метод Гаусса

Вообще-то принято писать _метод Гаусса с выбором ведущего элемента_.

[liter]

Вообще-то, это один из частных случаев метода Гаусса, ибо:
1) Можно вообще не выбирать ведущий элемент (только в случае нуля). Я так делал на первом курсе. У нас тогда еще ЧМ небыло и никто бы меня не убедил, что это снижает точность.
2) Есть МГ с частичным выбором ведущего элемента
3) Ты можешь выбор элемента заменить чем-нибудь другим. Например, подготовить матрицу заранее. Или доказать, что на главной диагонали все будет хорошо.
4) Когда ты решал на бумаге системы методом Гаусса ты выбирал ведущий элемент?

[liter]

Люди, если у кого есть - киньте плиз алгоритм. Либо исходник. Все равно на чем (почти. На Ассемблере я вряд ли разбиру этот алгоритм). Либо мысль, как решить клеточно-теплицеву матрицу.

[ГАЗ-67]

Алгоритм следующий .
Если обратить внимание на то как меняется столбец свободных членов во время прямого хода Гаусса,
то видно следуещее : каждый новый элемент ,начиная со второго , является линейной комбинацией
предыдущих и старого значения .
Значения для линейной комбинации однозначно определяются во время прямого хода Гаусса из коэффициэнтов матрицы стоящей в левой части и очень удобно размещаются в освободившейся нижней левой треуголке .
Таким образом , при изменении в исходной системе правого столбца ,достаточно произвести пересчет столбца свободных членов пользуясь коэффициэнтами в левой нижней треуголке ,начиная с измененного элемента
и вниз.Для получения нового решения достаточно выполнить обратный ход Гаусса .
Необходимо хранить первоначальный столбец свободных членов .
С удовольствием изложил бы формулы ,но не умею их записывать в данной системе .
Если не понятно ,вопрошайте .Удачи.
P.S.Алгоритм был разработан для неизменой правой части.

[ГАЗ-67]

Черт возьми ! Для неизменной левой ...