|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 11 Jun 2002 11:53:12
To : Sergei Katkovsky
Subject : Re: Метод итераций для ЛС
--------------------------------------------------------------------------------
Sat Jun 08 2002 01:51, Sergei Katkovsky wrote to Evgenij Masherov:
SK>>> Вообще, значения первого и второго собственных чисел могут быть просто
SK>>> близки, и тогда сходимость тоже будет не ахти.
EM>> Если они действительны - сходимость будет великолепна.
SK> Чтобы не быть голословным. С Матлабом знаком, наверное? Врочем, тут все
SK> прозрачно.
SK> clear;
SK> A=diag([100 90 40 30 20 15 10 5 3 1]);
SK> x=ones(10);
SK> n=0;
SK> while( abs(norm(x) - 100) > 1e-6)
SK> x=x/norm(x);
SK> x=A*x;
SK> n=n+1;
SK> end
SK> norm(x)
SK> n
SK> Потребовалось 78 итераций. Меняем второе собственное значение на 99, 99.9
SK> и 99.99 требуется, соответственно, 689, 5755 и 46050 итераций. Для
SK> матрицы
SK> 10х10 последнее многовато, не так ли?
Контрпример хорош, но после некоторых экспериментов+скромной теории
обнаружено:
1. При наличии двух близких максимальных С.З. очень быстро попадаем в интервал
между ними, после чего существенно медленнее движемся с максимальному.
2. Собственные вектора при этом прыгают.
3. При снижении требований к относительной ошибке с 10(-8) до более скромных
скорость работы возрастает изрядно...
Рекомендации:
1. В задаче грубой оценки С.З. (что первоначально требовалось) вполне
адекватен.
2. При необходимости получения точных значений требуется дополнительная
проверка схождения к С.З., стабилизация значений может наступить до достижения
максимального С.З.
3. При подозрении на наличие нескольких близких С.З. возможно использование
одновременных итераций (для 2-х - не столь дорого).
4. Экономически степенной метод (и одновременные итерации) особенно выгодны
для разреженных или алгоритмически заданных матриц.
Примечание к Р.1
Существуют оценки максимального и минимального С.З. (Лагерра). Вполне себе
прямые.
ЗЫ.
Фадеева и Фадееву переиздали... Хорошо...
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
