1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 43
Текст из файла (страница 43)
Очевидно, при этом х""» Х,х". Процесс сходится линейно со знаменателем д — (А.,/Х, ~. Считается, что процесс практически сошелся, если отношения соответствующих коордийат векторов хм"» и х~о с требуемой точностью одинаковы и не меняются на последних итерациях. При этом для более точного получения собственного значения целесообразно положить хм.а ~ ., /(хоо~ хао ) (72) Отметим, что при расчетах на ЭВМ на каждой итерации после вычисления А, вектор хы-'~ надо нормировать, чтобы не получать переполнений или исчезновений чисел. $ я ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ 191 Формально при й,=О итерации сходятся к следующему собственному значению. Однако из-за ошибок округления й, не может быть точно нулем, а при малом $т процесс по-прежнему сходится к первому собственному значению, только за большее число итераций. Если наибольшее собственное значение кратное, но соответствующий элементарный делитель матрицы линеен, то итерации сходятся обычным образом. Но если Л, ~ Л„а их модули равны или если элементарный делитель матрицы нелинеен (жордаиова клетка), то процесс ие сходится.
Если (Л„~ — )Л,(, то сходимость очень медленная; этот случай нередко встречается в простейших итерационных методах решения разностных схем для эллиптических уравнений (глава Х11). Тогда сходимость можно ускорить процессом Эйткена (см. главу 1Ч, З 1). Одна итерация для матрицы общего вида требует 2а' арифметических действий, а для ленточной матрицы — 2та действий. Из-за медленной сходимости степенной метод применяют только к матрицам, содержащим очень много нулевых элементов (и даже к ним †доволь редко).
В математической литературе описана вариация степенною метода, имеюптая ивадратичную сходимость: хм'=Аэх'е', где А,=А,, А,, и Аэ=А. Од. пако если матрица А имеет мною нулевых элемейтов, то ее степени уже такими не будут. Поэтому этот вариант обычно не экономичен. 4. Обратные итерации со сдвигом. Напишем итерационный процесс, обратный по отношению к степенному процессу: хычм = А-'х"'. (?3) Очевидно, он сходится в указанном в и. 3 смысле к наибольшему по модулю собственному значению матрицы А-', т.
е. к наименьшему по модулю собственному значению матрицы А (ибо собственные значения матриц А и А' обратны друг другу). Все, что говорилось в предыдущем пункте о характере сходимости, разумеется, справедливо и в этом случае; сходимость будет довольно медленной. Однако здесь положение можно суц~ественно улучшить лгвто. дом сдвига, который заключается в следующем. Пусть нам приближенно известно некоторое, не обязательно наименьшее, собственное значение Ль Тогда так называемая сдвинутая матрица (А — Л,Е) будет иметь собственные значения Л вЂ” Ло У этой матрицы интересующее нас собственное значение Л; — Л, будет намного меньше по модулю, чем остальные.
Поэтому обратные итерации со сдвинутой матрицей (которые мы запишем в несколько иной форме) (А — ЛЕ) хь "м =х('>. (74а) >92 АЛГЕБРАИЧЕСКАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ (ГЛ. Ч! будут быстро сходиться и определят требуемое нам собственное значение Ц вЂ” )(. Напомним, что после каждой итерации надо нормировать вектор, чтобы избежать переполнений. С учетом этого вместо (74а) получим последовательность формул (А — ЦЕ)у(5) = Х(5>, (х(5)' у~5~ (74б) ((9(5>(5 (~~~Я ) Здесь индекс й относится к компонентам векторов, а скобки (...) означают некоторое усреднение по всем компонентам: например, среднеарифметическое. Если исходное приближение было хорошим, то иногда процесс сходится за несколько итераций; тогда выгодно непосредственно решать линейную систему (73). Если же требуемое число итераций велико, то лучше обратить матрицу (А — Х(Е).
Выгодней всего при решении линейной системы (74) методом исключения Гаусса использовать полученные на первой же итерации вспомогательные коэффициенты с „(см. главу т>, 9 1, п. 1) на каждой последующей итерации; но это не предусмотрено в обычных стандартных программах. Если сдвиг постоянный, то итерации сходятся линейно, Можно получить квадратичную сходимость, если уточнять сдвиг в ходе расчета следующим образом: (А — Л~'Е) у(5> = Х(5', (,> /Х~5>'1 Ч'5' (75) )) у|5) /! Для матриц, имеющих ортогональную систему собственных векторов (например, эрмитовых матриц), сходнмость вблизи корня будет даже кубической.
Заметим, что допускать слишком точное совпадение Ц с собственным значением нельзя, ибо мвтрица системы (75) становится плохо обусловленной; Об этом уже говорилось в 9 1, п. 6 в связи с нахождением собственных векторов. Поэтому, когда в ходе итераций у величины )(' устанавливаются (т.
е. перестают меняться) 5 — ? знаков, то итерации следует прекращать. Замечание 1. Переменный сдвиг собственного значения (75) нельзя включать с первой итерации; сначала надо получить грубую сходимость итераций с постоянным сдвигом. Замечание 2. Обратные итерации особенно удобны, если матрица заранее приведена преобразованием подобия к почти треугольной форме. Тогда одна обратная итерация выполняется 133 ЗАДАЧИ методом исключения с выбором главного элемента всего за 2из действий.
Теоретически для ленточных матриц возможна еще ббльшая экономия, но преобразование подобия почти треугольной матрицы к трехдиагональной форме не всегда устойчиво. Выводы. Обратные итерации с постоянным и особенно с переменным сдвигом — очень эффективный метод расчета. Для нахождения собственных векторов этот метод считается наиболее точным. Сходимость при хорошем подборе )ь настолько быстрая, что метод пригоден и для близких нли случайно равных по модулю собственных значений (ибо после сдвига они хорошо различаются), и даже при наличии у матрицы нелинейного элементарного делителя.
ЗАДАЧИ 1. Доказать, что если матрица и-го порядка имеет и собственных векторов ег=- (61ч), 1 =- и = л, то она диагональна. 2. Найти собственные векторы треугольной матрицы, считая все собственныс значения простыми. 3. Доказать, что нормальная матрица при унитарном преобразовании подобия остается нормальной. 4. Показать, что если матрица А ленточная, то преобразование подобия матрицами отражения (30) не сохраняет ее структуры, 5. Какие элементы необходимо вычислять в формулах (43) — (44) при преобразовании подобия матрицами вращения для зрмитовой матрицы А? 6. Доказать, что сферическая норма произвольной матрицы не меняется при умножении с любой стороны на унитарную матрицу. 7. В итерационном методе вращений вывести для определения параметров поворота комплексных матриц формулу, аналогичную (51). 3.
Показать, что в нтерациовном методе вращений формулы (54) определяют собственные векторы с точностью О (ез), где е — максимум модулей внедиагональных элементов; если же в этих формулах положить у;ь Нь то точность ухудшается до 0(е). 9. Получить все формулы расчета матричных элементов для второго хода метода элементарных преобразований.
16. 11аписать формулы восстановления собствениых векторов исходной матрицы по собственным векторам трехдиагональной матрицы в методе элементарных преобразований. 11. Показать, что если матрица А ленточная, то элементарное преобразование подобия (57) разрушает ее структуру. 12, а) Какой вид примут формулы метода линеаризапии (70), если недостающее уравнение получать из условия нормировки собственного вектора п ~~ (хг',з=1? 5) Как построить экономичный алгоритм решения полученной г=1 при этом линейной системы, если матрица А является трехдиагональной? 13.
Доказать, что метод обратных итераций с переменным сдвигом (75) сходится квадратичво вблизи простого собственного значения. ГЛАВА 7!1 ПОИСК МИНИМУМА В главе 711 рассмотрены способы нахождения такого значения аргумента, которое минимизирует некоторую зависящую от него скзлярную величину. В $1 изложена задача о минимуме функции одного переменного, лежащая в основе всех более сложных задач, В 5 2 рассмотрена задача о минимуме функции многих переменных в неограниченной области. В 4 3 область изменения переменных ограничена; наряду с общим случаем рассмотрена частная задача линейного программирования, важная в приложениях к кономике. В $ 4 разобрана задача о минимизации функционала, когда аргумент сам является функцией одного илн нескольких переменных.
В 1. Минимум функции одного переменного 1. Постановка задачи. Пусть имеется некоторое множество Х, состоящее из элементов х, принадлежащих какому-нибудь метрическому пространству, и на нем определена скалярная функция Ф(х). Говорят, что Ф(х) имеет локальный минимум на элеменаге х, если существует некоторая конечная е-окрестность этого элемента, в которой выполняется Ф (х) Ф (х), )) х — х () ~ е. (1) У функции может быть много локальных минимумов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
