Решение СЛАУ

From

Evgenij Masherov (2:5020/175.2)

To

Ilya Rogov

Date

2003-01-17T09:37:40Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Fri Jan 17 2003 03:01, Ilya Rogov wrote to Evgenij Masherov:

 
 EB>>>> Нет ли у кого-нибудь хорошего алгоритма сабж(на худой конец
 EB>>>> нахождения обратной матрицы). Матрица в идеале должна быть
 EB>>>> приличнных размеров, поэтому и алгоритм должен быть более менее
 EB>>>> шустрым.

 IR>>>   А кроме Гаусса ничего нету. По-крайней мере из точных методов.
 IR>>> А Гаусс - n^3.

 EM>> 1. Строго говоря, есть алгоритм решения со сложностью n^(LOG2(7)). Вот
 EM>> только точность его падает драматически, по отзывам реализовавших
 EM>> его...

 IR>    Буду рад узнать. Только вот откуда там 7 ?!? Да и точностью он Гаусса
 IR> не переплюнет, ибо Гаусс абсолютно точен. Ведь можно ввести понятие дроби
 IR> и считать отдельно числитель и знаменатель, деля одно на другое лишь в
 IR> конце. Тогда погрешность от ограниченной разрядной сетки будет
 IR> минимальна. Имхо, так и делается в мат. прогах.

0. Это метод Штрассена. Описан во втором томе Кнута, п.4.6.4 применительно к
умножению матриц.
Основан на итеративном применении тождества
(a b )(A  -C)_(  (a+d)(A+D)-(b+d)(B+D)-d(A-B)-(a-b)D    (a-b)D-a(D-C)  )
(c d )(-B -D)-(  (d-c)A-d(A-B)   (a+d)(A+D)-(a+c)(A+C)-a(D-C)-(d-c)A   )
Обобщение на задачу обращения матриц можно найти у Ахо, Хопкрофт, Ульман.
1. Ну, вот у Вас задача. В которой Вам нужно обратить матрицу 1000х1000.
Операций соответственно будет 10^9. Положим, что исходно числа не более чем
трехразрядные. Тогда в выкладках у Вас будут числа порядка 10^(3*10^9) в
количестве 2*10^6...
Лично мне захочется использовать арифметику обычную, с плавающей точкой. Ну,
может, еще применю итеративное уточнение...

 EM>> 3. Как правило, большие матрицы разрежены или имеют специальную
 EM>> структуру. Поэтому общий алгоритм для них может быть плох.

 IR>    А сильно разреженную матрицу можно по Краммеру посчитать. А если есть
 IR> какая-нить хитрая структура - вообще аналитически, на бумажке.

Угу. При этом все определители считая по определению определителя. Поскольку в
разреженной матрице много нулевых элементов, для большинства потребуется лишь
сравнение с нулем. И мы обойдемся всего лишь
1000!=4,02387260077093773543702433923e+2567 операциями...

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)