Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 45
Текст из файла (страница 45)
2. Ускорение ЯЯ-алгоритма. Приведенный выше вариант ЯЯ-алгоритма очень неэффективен по двум основным причинам. Первая из них состоит в том, что для реализации только лишь одной итерации этого метода требуется выполнить порядка тз арифметических операций, если А — матрица общего вида.
Вторая причина заключается в том, что при наличии двух близких собственных значений Л; м Л;1 метод сходится очень медленно, так как, например, элемент а~.">., + 1 (т.е. все элементы, расположенные ниже диагонали, непосредственно примыкающей к главной диагонали), называется иатрицей Хессен— берга. Существуют эффективные стандартные процедуры преобразования матрицы А к виду (8.35), поэтому мы не будем останавливаться подробно на этом преобразовании.
Для дальнейшего важно то, что матрицы А и Н подобны и обладают общим набором собственных значений, а матрица подобия Р, для которой выполняется равенство Н= Р1АР, (8.36) Нг 1$1 = Н1 1$> — Л *.Ю являются Л = Л вЂ” Л ', $' = 1, 2, ..., т. В этом слу- $ 1 г л; чае вместо отношения — и 1 скорость убывания поддиагонального л;, Л; — Л,*. элемента п1.$$1. определяет величина — ' =, я О. После $, $1 Л,,-Л,' нескольких итераций ЯВ-алгоритма, которые практически сделают элемент йг.">,, равным нулю, следует выполнить обратный сдвиг, пола- Ф 233 ортогональна. После преобразования матрицы А к виду (8.35) к матрице Н применяют ЯЯ-алгоритм.
Эффективность такого подхода обусловлена наличием следующих двух замечательных свойств матриц Хессенберга. 1в. Матрицы Н' "', порождаемые ДН-алгоригплол из матрицы Н'в1 = Н$ сали являются матрицали Хессенберга, т.е. для них Ьг =Оприг>г+1. 2в. Для выполнения одной итерации ЯК-алгоритма для латрицьг Хессенберга требуется число арифлетичесггих операций, пропорциональное т2. Однако, как уже было отмечено, даже достигнутая благодаря пред— варительному преобразованию матрицы А к виду (8.35) существенная экономия числа арифметических операций недостаточна для практического использования ф~-алгоритма.
Дело в том, что при наличии близких соседних собственных значений Л, в Л,1 элемент йг "1,. убываЛ; ет очень медленно пропорционально у" где $$ = ! — ~ и 1. Для реше— $$л,, ния этой проблемы используют различньге варианты ЧИ-а ггоритла со сдвигали. Поясним суть этого подхода. Допустим, что для Л, известно хорошее приближение Л*, Тогда собственными значениями матрицы тая Л'"' = Й< Ь~ + Л,.Ж После выполнения этой операции матрицы А и Н~~' снова имеют общий набор собственных значений. Последовательное осуществление сдвигов для г = т, т — 1, ..., 1, сопровождаемых итерациями по Щ-алгоритму, дает возможность быстро привести матрицу А к виду (8.33).
Остающийся невыясненным вопрос о том, как получить приближенные значения Л,*. ~ Ль снимает- ся, если учесть, что в ходе дВ-алгоритма диагональные элементы Ь<.",.~ сходятся к Л, при х -~ м. Следовательно, в качестве Л,*. можно, например, брать элементы1 Ь< ~'. Итак, прежде чем применять ДЯ вЂ” алгоритм, следует преобразовать исходную матрицу А к форме Хессенберга. Без такого преобразования ф2-алгоритм практически не применяется. Затем целесообразно использовать один из вариантов ЯЯ-алгоритма со сдвигами. Пусть теперь собственные значения найдены и требуется найти один собственный вектор с матрицы А, отвечающий собственному значению Л, или несколько собственных векторов.
Тогда целесообразно сначала найти соответствующий собственный вектор в матрицы Н (например, методом обратных итераций), а затем вычислить с по формуле су — — Р. в~, где Р— матрица подобия из (8.36). 3 а м е ч а н и е 1. Вычисление собственного вектора е непосредственным применением метода обратных итераций к матрице А возможно, но потребует большего числа арифметических операций по сравнению с указанным выше подходом. 3 а м е ч а н и е 2.
Проведенное в этом параграфе обсуждение алгоритма носило в значительной степени ознакомительный характер. Практически не был затронут случай, когда матрица имеет кратные или комплексные собственные значения. Не рассматривались и особенности применения ЯА-алгоритма для комплексных матриц. 3 а м е ч а н и е 3. ЧЯ-алгоритм обладает хорошей обусловленностью. Например, как показано в (19], в одном из его вариантов после числа итераций, не превосходящего 5, для каждого собственного значения получаются приближения Л*, Л ', ..., Л *, являющи- Чаще всего в библиотечных программах используется либо указанная стратегия сдвигов (сдвигов во Рэлею), либо стратегия сдвигов во Уилжинсону (84].
234 еся точными собственными значениями некоторой матрицы А, такой, что ]А — А,]к < 30 тге 1(А]]е (это Утверждение сфоРмУлировано в терминах обратного а ошибок). $8 5. Дополнительные замечания 1. В данной книге не рассмотрены некоторые весьма популярные методы решения проблемы собственных значений. Изложение лето да бисеат1ий, метода враш,ений Якоби, Яй-аторитла (являющегося вариантом Ядалгоритма), ЬВ-ал1оритла и других методов можно найти, например в [19], [20], [62], [83], [84].
Авторы советуют обратить внимание на книгу [41], содержащую изложение современных численных методов решения проблемы собственных значений, вполне доступное для студента или выпускника технического вуза. 2. Если А — заполненная матрица общего вида умеренного порядка, то лучшим выбором для вычисления всех собственных значений служит один из вариантов ЯВ-алгоритма со сдвигами. Необходимо только предварительно преобразовать матрицу к форме Хессенберга. 3.
В случае, когда А — симметричная матрица умеренного порядка, ее обычно приводят сначала с помощью последовательных преобразований Хаусхолдера к трехдиагональному виду. Для вычисления собственных значений полученной трехдиагональной матрицы можно использовать ЯЛ вЂ” алгоритм, но по-видимому, чаще более предпочтительным является метод бисекций. Одно из достоинств этого алгоритма состоит в том, что он позволяет находить не все собственные значения, а одно или группу нужных собственных значений. 4.
Если приближенное значение собственного числа найдено, то подходящим методом вычисления соответствующего собственного вектора является метод обратных итераций. 5. Методы, которые используются в настоящее время для решения пробл~ мы собственных значений в случае, когда А — разреженная матрица большой размерности, можно разделить на две основные группы: методы одновреленных итераций (или итерирования подпространства) и методы тина Ланц<~ ~аа..
Их обсуждение можно найти, например, в [41]. Один из простейших возможных подходов — степенной метод — был рассмотрен в г 8.2. Глава У МЕТОДЫ ОДНо~йЕРНОИ МИНИМИЗ.йЦИИ Одно из важнейших направлений в конструировании изделий, а также проектировании и эксплуатации технологических процессов состоит в оптимизации (минимизации или максимизации) некоторой характеристики ~(х). Функцию ~(х) часто называют целевой функцией. Заметим, что основное внимание может быть уделено минимизации целевой функции, так как максимизация сводится к минимизации с помощью введения новой целевой функции ~ (х) = — ~(х).
В случае, когда варьируется один скалярный параметр х, возникает задача одномерной лгинилгиэации. Необходимость изучения методов ре~шения задачи одномерной минимизации определяется не только тем, что задача может иметь самостоятельное значение, но и в значительной мере тем, что алгоритмы минимизации являются существенной составной частью алгоритмов решения задач многомерной минимизации (см. гл. 10), а также других вычислительных задач. 1 9.1.
Задача одномерной минимизации 1. Постановка задачи. Определения. Пусть ~ (х) — действительная функция одной переменной, определенная на множестве Х С ( », м). Напомним, что точка х Е Х называется гпочкой глобалъного минимума функции ~на множестве Х, если для всех х Е Х выполняется неравенство ~(х) ч ~(х). В этом случае значение Х(х) называется лгинилгалънъг и эначениелг функции ~на Х. Точка х Е Х называется гпочкой локалъного лгинииулга функции ~ если существует такая 6-окрестность этой точки, что для всех х из меножества Х, содержащихся в указанной 6 окрестности, выполняется неравенство ~(х) ~ ~(х). Если же для всех таких х, не совпадающих с 236 х, выполняется неравенство ~(х) ( ~(х), то х называется точкой стпро~о10 лохальноюо кинилли. Пример 9.1. Для функции, график которой изображен на рис.
9.1, точки и х~ являются точками строго локального минимума, а в точках х, удовлет— воряющих неравенству х1 ~ х ь хх, реализуется нестрогий локальный минимум. Рис. 0.1 Известно, что необходимым условием того, чтобы внутренняя для множества Х точка х была точкой локального минимума дифференцируемой функции ~ является выполнение равенства Дх) = О. (Я 1) Число х, удовлетворяющее этому равенству, называется стаЧиокаркой точкой фукхции ~ Конечно, не всякая стационарная точка х обязана быть точкой локального минимума. Для дважды непрерывно дифференцируемой функции достаточным условием того, чтобы стационарная точка х была точкой строгого локального минимума, является выполнение неравенства ~ (х) > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
