ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergei Katkovsky                     2:5020/400     05 Apr 2002  11:51:48
 To : Michael Ryazanov
 Subject : Re: СЛУ
 -------------------------------------------------------------------------------- 
 

 Hello, Michael!
 You wrote to Sergei Katkovsky on Thu, 04 Apr 2002 21:30:00 +0400:
 
 MR> 02.04 06:39 Sergei Katkovsky -> Michael Ryazanov
 
 MR>>> Есть система линейных уранений Ax = b, где A -- симметричная матрица с
 MR>>> небольшим диагональным преобладанием, достаточно разреженная, размера
 MR>>> порядка 1000x1000.
 MR>>> Точность решения важна! И побыстрее, конечно, хочется. :-) Как лучше
 MR>>> решать?
 SK>> Она просто симметричная, или еще и положительно определенная?
 
 MR>    Вообще-то, это из МHК матрица. Может быть не положительно, а только
 MR> неотрицательно определённой.
 
 Так, подожди. Давай подробнее. У тебя линейный МHК и эта система - система
 нормальных уравнений? Тогда, поскольку точность важна, на нормальные
 уравнения следует забить, и использовать QR-разложение. Или что там?
 
 SK>> Для вторых, веротно, почти все прямые методы дадут хорошую точность.
 
 MR>    Восемь знаков надо как минимум...
 
 Hа крайний случай есть ортогональные методы, но это медленно. Hо сперва
 стоит каким-либо методом понадежнее определить число обусловленности
 исходной матрицы, чтобы зря не мучаться - если оно очень большое, никакой
 метод тебе ни восемь, ни пять знаков не даст, и вообще ерунда получтся
 может.
 
 SK>> А из итерационных - всякие вариации на тему сопряженных градиентов
 SK>> пробовал?
 
 MR>    Градиентов чего?
 
 Градиентов соответствущей линейной системе задачи минимизации. Решение
 системы можно рассматривать как задачу минимизации невязки r = Ax - b в
 некоторой норме. Применяя к этой задаче различные методы минимизации, можно
 получить соотвествующие методы решения линейных систем. В некотором смысле
 ты возвращаешься обратно к своей исходной задаче.
 
 Для метода сопряженных градиентов используется норма \|r\|_{A^{-1}} =
 \sqrt(A^{-1}r,r), то есть, норма, определяемая скалярный произведением,
 матрица которого есть А, очевидно, что А должна быть симметричной и
 положительно определенной, то есть, непосредственно для тебя он не подходит.
 Hо существуют всякие варианты этого метода, применимые и к другим матрицам.
 
 Можно взять норму \|r\|_2, тогда это будет метод минимальных невязок, он не
 требует положительной определенности А. Попробуй, он, вроде бы, приближается
 к теоретически оптимальному для одношаговых методов чебышевскому, но знания
 границ спектра не требует.
 
 Кроме того, почти любой итерационный метод можно улучшить, подобрав хороший
 предобуславливатель.
 
 MR> Сам МHК покоординатно отвратительно сходится. По градиенту сильно лучше
 MR> будет?
 
 Возможно. Попробуй.
 
 Вообще, Михаил, и по линейным системам, и по МHК литературы понаписано
 столько, что всю жизнь можно читать. Я не думаю, что здесь, не имея,
 собственно говоря, практически никакой информации о задаче, кто-то предложит
 оптимальный метод. Так что если задача действительно важна, а скорость и
 точность решения критичны, придется возиться самому. Если нет - можно
 перепробовать то, что здесь предложили, заглянуть также на всякие
 www.netlib.org и gams.nist.gov в поисках готовых методов (их немало), ну и
 выбрать то, что оказалось лучшим.
 
 Сергей Катковский
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    СЛУ   Michael Ryazanov   31 Mar 2002 23:53:00   Re: СЛУ   Sergei Katkovsky   02 Apr 2002 06:39:30   Re: СЛУ   Michael Ryazanov   04 Apr 2002 22:30:00   Re: СЛУ   Sergei Katkovsky   05 Apr 2002 11:51:48   СЛУ   Maxim Lanovoy   02 Apr 2002 20:53:02   Re: СЛУ   Michael Ryazanov   04 Apr 2002 23:03:00   Re: СЛУ   Sergei Katkovsky   05 Apr 2002 11:51:48   СЛУ   Maxim Lanovoy   05 Apr 2002 21:43:08