Решение СЛАУ

From

Evgenij Masherov (2:5020/175.2)

To

Ilya Rogov

Date

2003-01-18T09:35:45Z

Area

RU.ALGORITHMS

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

Sat Jan 18 2003 01:21, Ilya Rogov wrote to Evgenij Masherov:
.

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

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

 IR>    1. Чегой-то я не совсем понял твою хитрую запись этого хитрого
 IR> тождества. Да и с разрядностью чисел ты перепутал ...

Ну, поищите в книгах по ссылке. А что до разрядности - желая представлять
числа в виде рациональных, приходится закладываться на то, что числитель и
знаменатель при каждой операции могут быть представлены числом,длина которого
равна сумме длин исходных числителя и знаменателя.

 IR>    2. Никто не собирается решать разреженную матрицу 1000х1000 Гауссом. Я
 IR> не   уверен, что речь шла о ТАКИХ размерностях.

А ведь это достаточно скромная размерность, по крайней мере для разреженных
матриц...

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

 IR>    А что, детерминант СИЛЬНО разреженной матрицы мы можем считать только
 IR> по рекурсивному определению ?? Смеха ради, попробую придумать методу ...

Это попытка тактично намекнуть, что теоретически пригодный алгоритм (решать
уравнения Крамером) может быть... эээ... не вполне практичен.

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

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