Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 6.4. МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВПредшествующая процедура, когда в качестве расширяющего шага используется метод циклического координатного спуска, не использует производные. Однако, когда производные вычисляются сравнительно легко, может оказаться полезным алгоритм, рассматриваемый в настоящем параграфе. Несмотря на то, что ниже приводится подробное изложение алгоритма, отметим, что он вырабатывает сопряженные направления при помощи рекурсии
в которой Этот алгоритм ценен не только в вычислительном отношении, его теоретическое обоснование также является весьма интересным. В частности, требуется теоретически рассмотреть два вопроса: как из линейно независимых направлений строить сопряженные направления и как строить ортогональные направления. Комбинация этих двух элементов дает алгоритм. Мы предполагаем, что матрица Построение сопряженных направлений из линейно независимых направлений. Пусть нам даны Пусть
Тогда
Для применений, которые мы будем рассматривать, Переписывая (6.11), получаем
а из того, что
Ортогональность эквивалентна Если Таким образом, используя (6.10) и (6.11) и заменяя Построение ортогональных направлений. Пусть даны
Для наших целей более удобно определять ортогональные векторы
Ясно, что сопряженного метода, который будет разработан, выражение Точно так же, как (6.12) было получено из (6.11), получим
Одновременная выработка ортогональных и сопряженных направлений. Теперь линейно независимые направления и сопряженные направления Используя В общем случае даны
Упрощения. Вследствие ортогональности
так что (6.11) принимает вид
Аналогично из (6.12) получаем
Тк что (6.13) принимает вид
где
Между выражениями (6.16) и (6.17) существует много важных зависимостей. Из ортогональности
Воспользовавшись уравнением (6.16) и сопряженностью
Далее уравнения (6.19) и (6.20) дают
Теперь будет показано, что
Так как
так что Теперь, предполагая, что и применяя (6.16), получаем
Тогда из выражений (6.17), (6.21) и (6.23) получаем
что подтверждает справедливость выражения (6.22) для всех
для всех Основные соотношения алгоритма. Используя выведенные соотношения, можно представить (6.16) и (6.17) в их окончательной форме. Если подставим (6.18) и (6.21) в (6.16), то получим
Перепишем также (6.17) в виде
где согласно (6.24) и (6.20)
Уравнения (6.25) и (6.26) составляют основу процедуры сопряженных градиентов для максимизации Алгоритм сопряженных градиентов. В используемом далее отображении Исходный шаг. Выберем Шаг
Вычисляется Доказательство сходимости. Теперь следует показать, что процедура сопряженных градиентов ведет себя согласно уравнениям (6.25) и (6.26). Если это так, то построенные Прежде всего необходимо обратить внимание на некоторые особенности. Если даны произвольные точка х и направление
Предположим, что
Следовательно, в точке
и из (6.29) получаем
Решая это уравнение относительно
Итак, максимум квадратичной функции Теперь мы установим, что эта процедура вырабатывает направления
то благодаря (6.28) уравнение (6.25) удовлетворяется. Поэтому необходимо лишь доказать, что получаемые по (6.26), такие же, как и в (6.31). Очевидно, Так как процедура вычисляет
По предположению индукции отсюда имеем
или согласно
и справедливость уравнения (6.31) подтверждается, так как, рассматривая (6.26), видим, что Таким образом, процедура сопряженных градиентов в точности такая же, как и рекурсия, представленная соотношениями (6.25) и (6.26). Очевидно, что процедура сопряженных градиентов вырабатывает направления Применение в качестве смешанного алгоритма. Включение метода сопряженных градиентов в смешанный алгоритм для максимизации произвольной функции Упражнения(см. скан) (кликните для просмотра скана) (см. скан) Дополнительные замечанияСопряженные направления были предложены в 1952 г. для решения линейных уравнений Хестенесом и Стифелом (см. упр. 6.7). Другие методы сопряженных направлений содержатся в работе Розенброка и в связанной с этой работой статье Флетчера и Пауэлла (см. также Флетчер, 1964; Пауэлл, 1962; Стифель; Мартин и Ти, а для обзора Флетчер, 1965). Другие подходы включают методы Коллатца; Недлера и Мида; Химсворса и других, метод параллельных касательных Шаха и др. (1961, 1964 г.). Сравнение методов для решения задачи без ограничений может быть найдено у Брукса. Необходимые сведения о многообразиях можно почерпнуть из стандартных курсов по линейной алгебре.
|
1 |
Оглавление
|