|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 17 Jan 2003 10:37:40
To : Ilya Rogov
Subject : Решение СЛАУ
--------------------------------------------------------------------------------
Fri Jan 17 2003 03:01, Ilya Rogov wrote to Evgenij Masherov:
EB>>>> Hет ли у кого-нибудь хорошего алгоритма сабж(на худой конец
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. Hу, вот у Вас задача. В которой Вам нужно обратить матрицу 1000х1000.
Операций соответственно будет 10^9. Положим, что исходно числа не более чем
трехразрядные. Тогда в выкладках у Вас будут числа порядка 10^(3*10^9) в
количестве 2*10^6...
Лично мне захочется использовать арифметику обычную, с плавающей точкой. Hу,
может, еще применю итеративное уточнение...
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
