Главная » Просмотр файлов » Н.Н. Калиткин - Численные методы

Н.Н. Калиткин - Численные методы (1133437), страница 46

Файл №1133437 Н.Н. Калиткин - Численные методы (Н.Н. Калиткин - Численные методы) 46 страницаН.Н. Калиткин - Численные методы (1133437) страница 462019-05-12СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 46)

е. в точках г„, убывают. В случае, когда Ф (г,,) > Ф (г„), процесс надо прекратить и значение г„, не испольэовать. Метод оврагов рассчитан на то, чтобы пройти вдоль оврага и выйти в котловину около минимума. В этой котловине значения минимума лучше уточнять другими методами. 210 1гл.

Уп ПОИСК МИНИМУМА Методом оврагов удается находить минимумы достатонио сложных функций от 5 — 10 переменных. Но этот метод довольно капризен. Для каждой функции приходится подбирать свой овражный шаг, визуально наблюдать эа ходом расдета и вносить коррективы. Программирование этого метода иа ЭВМ иесаожпо. 5. Сопряженные направления. Методы наискорейшего спуска или спуска по координатам даже для квадратичной функции требуют бесконечного числа итераций. Однако можно построить такие направления спуска, что для квадратичной функции Ф (г) = (г, Аг) -1- ((т, г) -(-с (30) (где г есть и-мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется точно к минимуму за конечное число шагов.

Положительно определенная матрица позволяет ввести норму вектора следующим образом: )х)~~~=(х, Ах))0 при хФО. (31) Нетрудно проверить, что все аксиомы нормы при этом выполнены. Определение (31) означает, что под скалярным произведением двух векторов х и у теперь подразумевается величина (х, Ау).

Векторы, ортогональные в смысле этого скалярного произведения (х, Ау) =О, (32) называют сопряженносми (по отношению к данной матрице А). Ниже мы увидим, что поочередный спуск по сопряженным направлениям особенно выгоден прн поиске минимума. На этом основана большая группа методов: сопряхгенных градиентов, сопряженных направлений, параллельных касательных и другие. Для квадратичной функции они применяются с одинаковым успехом. На произвольные функции наиболее хорошо обобщается метод сопряженных направлении, у которого детали алгоритма тщательно отработаны; этот метод излагается в данном пункте. а) Сначала рассмотрим, как применяется этот метод к квадратичной форме (30). Для этого нам потребуются некоторые свойства сопряженных векторов.

Пусть имеется некоторая система попарно сопряженных векторов хь Нормируем каждый из этих векторов в смысле нормы (31); тогда соотношения между ними примут вид (хн Аху) =бн. (33) Докажем, что взаимно сопряженные векторы линейно-независимы. Из равенства х,= ~ сс;хг следует (х,, Ахь) =- )~ ссз(х„Ах;)=О, с-а т а МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 21! $21 что противоречит положительной определенности матрицы, Это противоречие доказывает наше утверждение.

Значит, система п сопряженных векторов является базисом в и-мерном пространстве. Для данной матрицы имеется бесчисленное множество базисов, состоящих из взаимно сопряженных векторов. Пусть мы нашли некоторый сопряженный базис х2, 1 «! «и. Выберем произвольную точку г,. Любое движение из этой точки можно разложить по сопряженному базису г=г,+~ а!х!.

(34) Подставляя это выражение в правую часть формулы (30), преобразуем ее с учетом сопряженности базиса (33) к следующему виду: л Ф (г) = Ф (г) + ~ , '[а2+ 2а! (х2, А1,) + а! (хп Ь)1. (35) Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (34). Зто означает, что движение по одному из сопряженных направлений х! меняет только один член суммы (35), не затрагивая оогальных. Совершим из точки г, поочередные спуски до минимума по каждому из сопряженных направлений хи Каждый спуск минимизирует свой член суммы (35), так что минимум квадратичной функции точно досп!игается после выполнения одного цикла спусков, то есть за конечное число действий.

Поясним геометрический смысл сопряженного базиса. Если осями координат сделать главные оси эллипсоидов уровня квадратичной функции, то один цикл спусков по этим координатам приводит точно в минимум. Если перейти к некоторым аффинным координатам, то функция останется квадратичной, но коэффициенты квадратичной формы изменятся.

Можно формально рассмотреть нашу квадратичную функцшо с измененными коэффициентами как некоторую новую квадратичную форму в декартовых координатах и найти главные оси ее эллипсоидов. Положение этих главных осей в исходных аффинных координатах будет некоторой системой сопряженных направлений. Разный выбор аффинных координат естественно приводит к разным сопряженным базисам. б) Сопряженный базис можно построить способом параллельных касательных плоскостей. Пусть некоторая прямая параллельна вектору х, а квадратичная функция достигает на этой прямой минимального значения в точке г,. Подставим уравнение этой прямой г=гл+ах в выражение (30) и потребуем выполнения условия минимума 2!2 ПОИСК МИНИМУМА 1гл.

Уп функции >р(сс) = Ф(г',+ах) в точке г"=1',, т. е, при а=О. Для этого воспользуемся выражением (35), где в сумме оставим только один член: Ч Ох) = Ф(Р'ч)+сс'+се (х, 2ЛА;+ Ь), и положим (>(ч>.,>>(а)„,=0. Отсюда следует уравнение, которому удовлетворяет точка минимума: (х, 2Аг»+Ь) =О. (36) Пусть на какой-нибудь другой прямой, параллельной первой, функция принимает минимальное значение в точке >,; тогда аналогично найдем (х, 2Лг; + Ь) = О. Вычитая это равенство из (36), получим (х, А (т 1 — т;)) = О. (37) Следовательно, направление, соединя>ощее точки минимума на двух параллельных прямых, сопряжено направленгио этих прямых.

Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору х. Для этого достаточно провести две прямые, параллельные эс, и найти на каждой прямой минимум квадратичной формы (30). Вектор е1 — т„соединяющий эти минимумы, сопряжен х. Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа. Пусть имеются две параллельные т-мерные плоскости, порожденные системой сопряженных векторов эс„ 1 == 1:- т (и.

Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках е; и гт. Аналогичными рассуждениями можно доказать, что вектор г; — г„, соединяющий точки минимума, сопряжен всем векторам х>. Следовательно, Если задана неполная система сопряженных векторов эс>, то этим способом всегда можно построить вектор г',— г', сопряженный всем векторам этой системы. Р а с с м о т р и м од и н ц и к л процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние т векторов взаимно сопряжены, а первые и — т векторов не сопряжены последним.

Найдем минимум квадратичной функции (30) в какой-нибудь т-мерной плоскости, порожденной последними т векторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку т; и сделать из нее спуск поочередно по каждому из этих направлений (до минимума!). Точку минимума в этой плоскости обозначим че- РЕЗ г'1. Теперь из точки г1 сделаем поочередный спуск по первым и — т векторам базиса.

Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку т,. Из точки гз МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМеННЫХ 2!3 снова совершим по последним и направлениям спуск, который приведет в точку г'„. Этот спуск означает точное нахожденне минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление г,— г, сопряжено последним т векторам базиса. Если одно из несопряженных направлений в базисе заменить направлением ге — вм то в новом базисе уже и + 1 направление будет взаимно сопряжено.

Начнем расчет циклов с произвольного базиса; для него можно считать, что т = 1. Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за п — 1 цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (30). в) Хотя понятие сопряженного базиса определено только для квадратичной функции, описанный выше процесс построен так, что его можно формально применять для произвольной функции.

Разумеется, что при этом находить минимум вдоль направления надо методом парабол, не используя нигде формул, связанных с конкретным видом квадратичной функции (30). В малой окрестности минимума приращение достаточно гладкой функции обычно представимо в виде симметричной положительно определенной квадратичной формы типа (18). Если бы это представление было точным, то метод сопряженных направлений сходился бы за конечное число шагов.

Но представление приближенно, поэтому число шагов будет бесконечным; зато сходимость этого метода вблизи минимума будет квадратичной. Благодаря квадратичной сходимости метод сопряженных направлений позволяет находить минимум с высокой точностью. Методы с линейной сходнмостью обычно определяют экстремальные значения координат менее точно. Замечание 1. Реально даже для квадратичной функции процесс не всегда укладывается в и циклов.

Характеристики

Тип файла
PDF-файл
Размер
21,94 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее