ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   18 Jan 2003  10:35:45
 To : Ilya Rogov
 Subject : Решение СЛАУ
 -------------------------------------------------------------------------------- 
 

 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. Hу, вот у Вас задача. В
  EM>> которой Вам нужно обратить матрицу 1000х1000. Операций соответственно
  EM>> будет 10^9. Положим, что исходно числа не более чем трехразрядные.
  EM>> Тогда в выкладках у Вас будут числа порядка 10^(3*10^9) в количестве
  EM>> 2*10^6... Лично мне захочется использовать арифметику обычную, с
  EM>> плавающей точкой. Hу, может, еще применю итеративное уточнение...
 
  IR>    1. Чегой-то я не совсем понял твою хитрую запись этого хитрого
  IR> тождества. Да и с разрядностью чисел ты перепутал ...
 
 Hу, поищите в книгах по ссылке. А что до разрядности - желая представлять
 числа в виде рациональных, приходится закладываться на то, что числитель и
 знаменатель при каждой операции могут быть представлены числом,длина которого
 равна сумме длин исходных числителя и знаменателя.
 
  IR>    2. Hикто не собирается решать разреженную матрицу 1000х1000 Гауссом. Я
  IR> не   уверен, что речь шла о ТАКИХ размерностях.
 
 А ведь это достаточно скромная размерность, по крайней мере для разреженных
 матриц...
 
  EM>> Угу. При этом все определители считая по определению определителя.
  EM>> Поскольку в разреженной матрице много нулевых элементов, для
  EM>> большинства потребуется лишь сравнение с нулем. И мы обойдемся всего 
  EM>> лишь 1000!=4,02387260077093773543702433923e+2567 операциями...
 
  IR>    А что, детерминант СИЛЬHО разреженной матрицы мы можем считать только
  IR> по рекурсивному определению ?? Смеха ради, попробую придумать методу ...
 
 Это попытка тактично намекнуть, что теоретически пригодный алгоритм (решать
 уравнения Крамером) может быть... эээ... не вполне практичен.
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Решение СЛАУ   Evgenij Masherov   13 Jan 2003 11:01:36   Решение СЛАУ   Andrew Kuksov   13 Jan 2003 14:42:40   Re: Решение СЛАУ   Maxim Balagansky   14 Jan 2003 09:46:16   Re: Решение СЛАУ   Kropov Valentine   18 Jan 2003 00:26:14   Re^2: Решение СЛАУ   Maxim Balagansky   20 Jan 2003 11:12:36   RE: Re[2]: Решение СЛАУ   Kropov Valentine   21 Jan 2003 10:47:53   Re: Решение СЛАУ   Sergei Katkovsky   22 Jan 2003 12:19:25   Решение СЛАУ   Evgenij Masherov   14 Jan 2003 10:27:25   Решение СЛАУ   Andrew Kuksov   14 Jan 2003 20:58:24   Решение СЛАУ   Vladimir Vassilevsky   15 Jan 2003 04:18:38   Решение СЛАУ   Evgenij Masherow   15 Jan 2003 11:47:07   Решение СЛАУ   Vladimir Vassilevsky   15 Jan 2003 18:33:59   Решение СЛАУ   Evgenij Masherov   15 Jan 2003 20:35:33   Решение СЛАУ   Evgenij Masherov   17 Jan 2003 11:34:53   Решение СЛАУ   Vladimir Vassilevsky   17 Jan 2003 18:00:59   Re: Решение СЛАУ   Sergei Katkovsky   14 Jan 2003 15:52:34   Re: Решение СЛАУ   Sergej Tarasov   14 Jan 2003 21:07:30   Re: Решение СЛАУ   Sergei Katkovsky   14 Jan 2003 21:36:35   Re^2: Решение СЛАУ   Maxim Balagansky   15 Jan 2003 09:50:10   Re: Решение СЛАУ   Sergei Katkovsky   15 Jan 2003 17:16:42   Re: Решение СЛАУ   Sergej Tarasov   16 Jan 2003 00:45:11   Re: Решение СЛАУ   Sergei Katkovsky   16 Jan 2003 02:28:41   Re^2: Решение СЛАУ   Maxim Balagansky   16 Jan 2003 12:39:20   Re: Решение СЛАУ   Sergei Katkovsky   16 Jan 2003 13:06:49   Re^2: Решение СЛАУ   Maxim Balagansky   17 Jan 2003 11:09:20   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:41:32   Re^2: Решение СЛАУ   Maxim Balagansky   16 Jan 2003 12:37:00   Re^2: Решение СЛАУ   Sergej Tarasov   17 Jan 2003 01:03:42   Re^3: Решение СЛАУ   Maxim Balagansky   17 Jan 2003 11:18:30   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:43:36   Re^2: Решение СЛАУ   Maxim Balagansky   20 Jan 2003 11:26:12   Re: Решение СЛАУ   Sergei Katkovsky   20 Jan 2003 11:04:34   Re^2: Решение СЛАУ   Maxim Balagansky   21 Jan 2003 10:13:50   Re: Решение СЛАУ   Sergei Katkovsky   21 Jan 2003 07:17:14   Re^2: Решение СЛАУ   Maxim Balagansky   22 Jan 2003 10:29:24   Re: Решение СЛАУ   Sergei Katkovsky   22 Jan 2003 12:23:31   Re^2: Решение СЛАУ   Maxim Balagansky   23 Jan 2003 10:08:22   Re: Решение СЛАУ   Sergei Katkovsky   27 Jan 2003 03:57:38   Re^2: Решение СЛАУ   Maxim Balagansky   24 Jan 2003 14:54:16   Re: Решение СЛАУ   Sergei Katkovsky   27 Jan 2003 04:00:09   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:40:29   Re^2: Решение СЛАУ   Maxim Balagansky   16 Jan 2003 12:28:12   Re: Решение СЛАУ   Sergei Katkovsky   16 Jan 2003 13:07:20   Re^2: Решение СЛАУ   Maxim Balagansky   17 Jan 2003 10:40:52   Re: Решение СЛАУ   Sergei Katkovsky   17 Jan 2003 16:41:32   Решение СЛАУ   Ilya Rogov   17 Jan 2003 04:01:50   Решение СЛАУ   Evgenij Masherov   17 Jan 2003 10:37:40   Решение СЛАУ   Ilya Rogov   18 Jan 2003 02:21:15   Решение СЛАУ   Evgenij Masherov   18 Jan 2003 10:35:45   Решение СЛАУ   Konstantin Polyakov   14 Jan 2003 20:14:35