Re: Метод итераций для ЛС

From

Evgenij Masherov (2:5020/175.2)

To

Sergei Katkovsky

Date

2002-06-07T10:07:27Z

Area

RU.ALGORITHMS

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

Fri Jun 07 2002 00:17, Sergei Katkovsky wrote to Evgenij Masherov:

 YZ>>>>> А существует ли способ нахождения максимального по модулю с.з.,
 YZ>>>>> который не сложнее обычного Гаусса для решения ЛС?

 SK>>>                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

 EM>>>> Степенной метод. Начинаем с произвольного начального вектора, и
 EM>>>> повторяем x(i+1)=Ax(i),
 EM>>>> всякий раз нормируя вектор к единице. Норма и будет максимальным С.З.

 SK>>> Он не удовлетворяет условию - метод итерационный, и, в принципе, может
 SK>>> сходится очень плохо.

 EM>> 1. Неитерационные методы нахождения собственных значений отсутствуют в
 EM>> принципе, увы...

 SK> Ну, это только в принципе :) На практике, как ты, думаю, знаешь, есть
 SK> условно-прямые методы. Они, впрочем, медленее гауссова исключения, и, в
 SK> конце концов, не тоже могут не сходится.

Не понял? Решение проблемы собственных значений есть нахождение корней некоего
полинома. Если есть метод решения С.З. для матрицы произвольного размера - то
пора выкапывать месье Галуа из гроба!
Методы нахождения коэффициентов полинома - да, есть "прямые", за конечное
число шагов (и не факториал:). Но сами С.З.?!
Просьба просянить...

 EM>> 2. Сходится он может плохо при выборе начального приближения строго
 EM>> ортогонально С.В. для максимального С.З. Но "часть вечной силы я, всегда
 EM>> желавшей зла, творившей лишь благое" - ошибки округления быстро нарушат
 EM>> эту ортогональность и начнется схождение...

 SK> Это верно, но возможен случай, когда ошибки округления не успевают внести
 SK> вклад, и метод тихонько ползет, создавая видимость сходимости к
 SK> совершенно иному значению. Читал я где-то про еще один хитрый случай,
 SK> когда даже с ошибками сходимости может не быть, поищую, найду - скажу.

Ну, при особо ответственном случае придется повторять с несколькими начальными
приближениями. Все равно будет быстро...

 EM>> 3. Второй тяжелый случай - наличие нескольких собственных значений,
 EM>> равных по модулю. Для несимметричной матрицы это проблема серьезна, и
 EM>> лечится одновременными итерациями. Но все С.З. симметричной матрицы
 EM>> действительны (а для МНК неотрицательны), так что равные по модулю
 EM>> попросту равны, и сходимость на практике превосходна.

 SK> Вообще, значения первого и второго собственных чисел могут быть просто
 SK> близки, и тогда сходимость тоже будет не ахти.

Если они действительны - сходимость будет великолепна. Если нам нужно только
максимальное С.З. А вот в задаче отыскания евонного С.В. могут быть проблемы
(для одинаковых С.З. просто - любая линейная комбинация их С.В. также С.В., а
вот для почти одинаковых...)

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

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