Решение СЛАУ

From

Ilya Rogov (2:5030/1334.1024)

To

Evgenij Masherov

Date

2003-01-17T03:01:50Z

Area

RU.ALGORITHMS

    Привет тебе, Evgenij, с того света от Ильи.

 Давным-давно, 13 Jan 03 10:01, когда земля была ещё тёпленькая
 и по ней бегали мамонты, Evgenij Masherov и Ilya Rogov говорили про Решение СЛАУ:

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

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

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

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

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

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

                                                        Ilya Rogov
... Бредить помогали вопли моих соседей
---
 * Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)