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

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

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

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

Если так сделать не удается, то выбирают несколько начальных приближений в разных участках отрезка 1а, Ь), и из каждого начального приближения проводят какой-нибудь итерационный процесс поиска минимума. Некоторые из этих итерационных процессов могут сходиться к одному и тому же локальному минимуму, а некоторые — к другим.

Остается сравнить найденные локальные минимумы между собой и выбрать наименьший (если это требуется по условиям задачи). Описанный способ не дает гарантии того, что будут найдены все минимумы (и тем самым, что будет найден абсолютный минимум). Но для недостаточно изученной функции такой гарантии не дают никакие способы. 4. Стохастические задачи. Опишем один алгоритм, рассчитанный на стохастические задачи. Он основан на предположении, что ошибки определения функции Ф (х) имеют статистическую природу, т.

е. они целиком случайны, а систематической погрешности нет. Тогда можно определить минимум со сколь угодно высокой точностью (фактически игнорируя область неопределенности дх 3 '6Ф), если воспользоваться таким итерационным 20! МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ » 2! процессом: х„„= х„— ф !Ф (хл + Ьл) — Ф (х„— Ьл)1, (16) где ал, Ьл — последовательности положительных чисел, удовлетво- ряющие следующим условиям: а„, Ь,— О, ~), а«=со, ~~ ~ — "") ~со. луп л=! (! 6) й 2.

Минимум функции многих переменных 1. Рельеф функции. Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных Ф (х, д). Она описывает некоторую поверхность в трехмерном пространстве с координатами х, у, Ф.

Задача Ф(х, у) =ш!п означает поиск низшей точки этой поверхности. Как в топографии, изобразим рельеф этой поверхности линиями уровня. Проведем равноотстоящие плоскости Ф=сопз! и найдем линни их пересечения с поверхностью Ф(х, у); проекции этих линий на плоскость х, у называют линиями уровня.

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

37, а). В малой окрестности невырожденного минимума рельеф функции котловинный. В самом деле, точка минимума гладкой функции определяется необходимыми условиями — = — =О, (17) и разложение функции по формуле Тейлора вблизи минимума При выполнении этих условий х„-»х с вероятностью единица при п- со (напомним, что стремление с вероятностью единица означает «почти всегда стремится», а не «обязательно стремится»). Условиям (16) удовлетворяют, например, а„=1!и и Ь,=п-". Этот алгоритм является обобщением алгоритма Роббинса— Монро, описанного в главе Ч, на задачи поиска минимума.

Он сходится весьма медленно, ибо изменение аргумента за шаг равно ~хл„— х„~ — 2ал!Ф'(хл)!, а величины ал убывают очень медленно, как видно из второго условия (16). Поэтому применять этот алгоритм к детерминированным задачам невыгодно. 202 поиск минимума )гл, пи имеет вид Ф (х, д) = Ф (л, и) + — „(Лх)а Ф „+ +сзхстУФ„а+ 2 (сту)а Фаз+..., (18) причем квадратичная форма (18) — положительно определенная*), иначе эта точна не была бы невырожденным минимумом.

А линии уровня знакоопределениой квадратичной формы — это эллипсы. д дт .)тг Т л г) Рис. 37. Случай, когда все вторые производные равны в этой точке нулю и минимум определяется более высокими производными, по существу ничего нового не дает, и мы не будем его специально рассматривать (линии уровня вместо эллипсов будут похожими на них кривыми четвертого порядка). Отметим, что условию (17) удовлетворяют также точки максимумов и седловые точки.

Но в точках максимумов квадратичная *) Квадратичная форма ~ ам а, ае назмвается положительно определена, а ной, если при любых га (за иснлюченнем обраптаюптихся одновременно в нуль) она положительна, МИНИМУМ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 203 форма (18) отрицательно определенная, а в седловинах она знакопеременна. Вблизи минимума функция мало меняется при заметных изменениях переменных. Поэтому даже если мы не очень точно определим те значения переменных, которые должны минимизировать функцию, то само значение функции при этом обычно будет мало отличаться от минимального. Рассмотрим овражный тип рельефа.

Если линии уровня кусочно-гладкие, то выделим на каждой нз них точку излома. Геометрическое место точек излома назовем истинным оврагом, если угол направлен в сторону возрастания функции, и гребнем— если в сторону убывания (рис. 37, б). Чаще линии уровня всюду гладкие, но на них имеются участки с большой кривизнои; геометрические места точек с наибольшей кривизной назовем разрешимыми оврагами или гребнями (рис.

37, в). Например, рельеф функции Ф(х, у) = 10(у — з(ох)'+0,1х>, (19) изображенный на этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, «дно> которого — синусоида, а низшая точка — начало координат. В физических задачах овражный рельеф указывает на то, что вычислитель не учел какую-то закономерность, имеющую вид связи между переменными. Обнаружение и явный.

учет этой закономерности облегчают решение математической задачи. Так, если в примере (19) ввести новые переменные ~=х, «1=у — з(их, то рельеф становится котловинным. Неупорядоченный тип рельефа (рис. 37, г) характеризуется наличием многих максимумов, минимумов и седловин. Примером может служить функция Ф (х, у) = (1+ з 1п> х) (1+ з 1п' у), (20) рельеф которой изображен на этом рисунке; она имеет минимумы в точках с координатами х„=пй, у,=п( и максимумы в точках, сдвинутых относительно минимумов на и/2 по каждой координате. Все эффективные методы поиска минимума сводятся к построению траекторий, вдоль которых функция убывает; разные методы отличаются способами построения таких траекторий Метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа.

2. Спуск по координатам. Казалось бы, для нахождения минимума достаточно решить систему уравнений типа (17) методом линеаризацни или простых итераций и отбросить те решения, которые являются седловинами или максимумами. Однако в реальных задачах минимизации эти методы обычно сходятся в настолько малой окрестности минимума, что выбрать подходящее пОиск минимумА [Гл. чи нулевое приближение далеко не всегда удается. Проще и эффективнее провести спуск по координатам.

Изложим этот метод на примере функции трех переменных Ф(х, у, г). Выберем нулевое приближение х„у„, г,. Фиксируем значения двух координат у=у,„г=г,. Тогда функция будет зависеть только от одной переменной х; обозначим ее через ~, (х) = .=- Ф(х, у„г,). Используя описанные в 8 1 методы, найдем минимум функции одной переменной ~,(х) и обозначим его через х,. Мы сделали шаг из точки (х„, у„г,) в точку (х„у„г„) по направлению, параллельному оси х; на этом шаге значение функции уменьшилось.

а) Рис. 38. Затем из новой точки сделаем спуск по направлению, параллельному осн у, т. е. рассмотоим )з(у) =Ф (х„ у, г„), найдем ее минимум и обозначим его через у,. Второй шаг приводит нас в точку (х„ у„ г„). Из этой точки делаем третий шаг — спуск параллельно оси г и находим минимум функции ), (г) = — Ф (х„у„г). Приход в точку (х„у,, г,) завершает цикл спусков. Будем повторять циклы.

На каждом спуске функция не возрастает, и при этом значения функции ограничены снизу ее значением в минимуме Ф=Ф(х, у, г), Следовательно, итерации сходятся к некоторому пределу Ф- Ф. Будет ли здесь иметь место равенство, т. е. сойдутся ли спуски к минимуму и как быстрог Это зависит от функции и выбора нулевого приближения. На примере функции двух переменных легко убедиться, что существуют случаи сходимости спуска по координатам к искомому минимуму и случаи, когда этот спуск к минимуму не сходится. В самом деле, рассмотрим геометрическую трактовку спуска по координатам (рис.

38). Будем двигаться по выбранному направлению, т. е. по некоторой прямой в плоскости х, у. минимум Функции многих пегеменных В тех участках, где прямая пересекает линии уровня, мы при движении переходим от одной линии уровня к другой, так что при этом движении функция меняется (возрастает или убывает, в зависимости от направления движения). Толы<о в той точке, где данная прямая касается линии уровня (рис. 38, а), функция имеет экстремум вдоль этого направления. 1Чайдя такую точку, мы завершаем в ней спуск по первому направлению, и должны начать спуск по второму направлению (поскольку направления мы сейчас выбираем параллельно координатным осям, то второе направление перпендикулярно первому).

Пусть линии уровня образуют истинный овраг. Тогда возможен случай (рис. 38, б), когда спуск по одной координате приводит нас на «дно» оврага, а любое движение по следующей координате (пунктирная линия) ведет нас на подъем. Никакой дальнейший спуск по координатам невозможен, хотя минимум еще не достигнут; процесс спуска по координатам в данном случае не сходится к минимуму. Наоборот, если функция достаточно гладкая, то в некоторой окрестности минимума процесс спуска <ю координатам сходится к этому минимуму.

Пусть функция имеет непрерывные вторые производные, а ее минимум не вырожден. Для простоты опять рассмотрим функцию двух переменных Ф(х, у). Выберем некоторое нулевое приближение х„у„и проведем линию уровня через эту точку. Пусть в области 6, ограниченной'этой линией уровня, выполняются неравенства, означающие положительную определенность квадратичной формы (18): Ф» = а)0, ФУУ)Ь)0, ~Ф,У~.=С, аЬ)с».

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

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

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

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