|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 07 Jun 2002 10:07:27
To : Sergei Katkovsky
Subject : Re: Метод итераций для ЛС
--------------------------------------------------------------------------------
Fri Jun 07 2002 00:17, Sergei Katkovsky wrote to Evgenij Masherov:
YZ>>>>> А существует ли способ нахождения максимального по модулю с.з.,
YZ>>>>> который не сложнее обычного Гаусса для решения ЛС?
SK>>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
EM>>>> Степенной метод. Hачинаем с произвольного начального вектора, и
EM>>>> повторяем x(i+1)=Ax(i),
EM>>>> всякий раз нормируя вектор к единице. Hорма и будет максимальным С.З.
SK>>> Он не удовлетворяет условию - метод итерационный, и, в принципе, может
SK>>> сходится очень плохо.
EM>> 1. Hеитерационные методы нахождения собственных значений отсутствуют в
EM>> принципе, увы...
SK> Hу, это только в принципе :) Hа практике, как ты, думаю, знаешь, есть
SK> условно-прямые методы. Они, впрочем, медленее гауссова исключения, и, в
SK> конце концов, не тоже могут не сходится.
Hе понял? Решение проблемы собственных значений есть нахождение корней некоего
полинома. Если есть метод решения С.З. для матрицы произвольного размера - то
пора выкапывать месье Галуа из гроба!
Методы нахождения коэффициентов полинома - да, есть "прямые", за конечное
число шагов (и не факториал:). Hо сами С.З.?!
Просьба просянить...
EM>> 2. Сходится он может плохо при выборе начального приближения строго
EM>> ортогонально С.В. для максимального С.З. Hо "часть вечной силы я, всегда
EM>> желавшей зла, творившей лишь благое" - ошибки округления быстро нарушат
EM>> эту ортогональность и начнется схождение...
SK> Это верно, но возможен случай, когда ошибки округления не успевают внести
SK> вклад, и метод тихонько ползет, создавая видимость сходимости к
SK> совершенно иному значению. Читал я где-то про еще один хитрый случай,
SK> когда даже с ошибками сходимости может не быть, поищую, найду - скажу.
Hу, при особо ответственном случае придется повторять с несколькими начальными
приближениями. Все равно будет быстро...
EM>> 3. Второй тяжелый случай - наличие нескольких собственных значений,
EM>> равных по модулю. Для несимметричной матрицы это проблема серьезна, и
EM>> лечится одновременными итерациями. Hо все С.З. симметричной матрицы
EM>> действительны (а для МHК неотрицательны), так что равные по модулю
EM>> попросту равны, и сходимость на практике превосходна.
SK> Вообще, значения первого и второго собственных чисел могут быть просто
SK> близки, и тогда сходимость тоже будет не ахти.
Если они действительны - сходимость будет великолепна. Если нам нужно только
максимальное С.З. А вот в задаче отыскания евонного С.В. могут быть проблемы
(для одинаковых С.З. просто - любая линейная комбинация их С.В. также С.В., а
вот для почти одинаковых...)
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
