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

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

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

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

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

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

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

Построим итерационный процесс, сходящийся к этому минимуму. Вычислим функцию на концах отрезка, а также в двух внутренних точках х„х, сравним все четыре значения функции между собой и выберем среди них наименьшее. Пусть наименьшим оказалось Ф(х,). Очевидно, минимум расположен в одном из прилегающих к нему отрезков (рис. Зб). Поэтому отрезок 1х„(1) можно отбросить н оставить отрезок [а, х.,). Первый шаг процесса сделан. На отрезке 1а, хД снова надо выбрать две внутренние точки, вычислить в них и на концах отрезка значения функции, и сделать следующий шаг процесса.

Но иа предыдущем шаге вычислений мы уже нашли Ф (х) на концах нового отрезка а, кз и в одной его внутренней точке х,. Поэтому достаточно выбрать внутри 1а, хи1 еще одну точку х„определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса. 197 5 и МИНИМУМ ФУНКЦИИ ОДНОГО ПЕРЕМЕННОГО Как выгодно размещать точки? Всякий раз мы делим оставшийся отрезок на три части (причем одна из точек деления уже определена предыдущими вычислениями) и затем Отбрасываем один из крайних отрезков. Очевидно, надо, чтобы следующий отрезок был поделен подобно предыдущему. Для этого должны выполняться соотношения х,— а хэ — хт Ь вЂ” а х,— а Ь вЂ” хв=х,— а, Решение этих уравнений дает $==-0,38.

2 3+у'в Ь вЂ” хэ хт — а Ь вЂ” а Ь вЂ” а (4) а=х„Ь=х„ а поочередно вводимые внутренние точки будут х„х„... На первом шаге полагаем согласно (4) хв хо+ ь (хт хе) р хэ хт ь (хт хо) (5) После сравнения может быть отброшена точка с любым номером, так что на следующих шагах оставшиеся точки будут перенумерованы беспорядочно. Пусть на данном отрезке есть четыре точки хь х,, х„, х„из которых какие-то две являются концами отрезка. Выберем ту точку, в которой функция принимает наименьшее значение; пусть это оказалось х;: Ф (х;) ( Ф (х)), Ф (хе), Ф (х~). (6) Затем отбрасываем ту точку, которая более всего удалена е) от х,; пусть этой точкой оказалась х,: ~ х, — х; ) > ( х) — х~ '„~ хе — х~ ~.

(7) Определим порядок расположения оставшихся трех точек на числовой оси; пусть, для определенности, х.<х; Сх,. (8) *) Это верно не при всяких делениях отреэкв, но для деления в соответствии (4) это справедливо. После проведения очередного вычисления отрезок сокращается в 1 — 5 0,62 раза; после и вычислений функции он составляет (1 — 9)э ' долю первоначальной величины (три первых вычисления в точках а, Ь, х, еще не сокращают отрезок), Следовательно, при и-~ оо длина оставшегося отрезка стремится к нулю как геометрическая прогрессия со знаменателем 1 — $ = 0,62, т. е. метод золотого сечения всегда сходится, причем линейно.

Запишем алгоритм вычисления. Для единообразия записи обозначим 198 ПОИСК МИНИМУМА [Гл. уп Тогда новую внутреннюю точку введем таким соотношением'): Х = ХУ+ ХА — ХЬ (9) и присвоим ей очередной номер. Минимум находится где-то внутри последнего отрезка, хк ~ х ~ ху, Поэтому итерации прекращаем, когда длина этого отрезка станет меньше заданной погрешности б: хг — хх <б. (10) Ф' (х,) Хмг «» Ф" (х,) (11) в простейших задачах нулевое приближение можно выбрать графически. Формулу (11) можно получить несколько иным способом. Разложим Ф(х) в точке х, по формуле Тейлора, ограничившись *) См.

предыдущую сноску. Метод золотого сечения является наиболее экономичным аналогом метода дихотомии применительно к задачам на минимум. Он применим даже к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке (а, Ь1 функция имеет несколько локальных минимумов, то процесс сойдется к одному из них (но не обязательно н наименьшему). Этот метод нередко применяют в технических или экономических задачах оптимизации, когда минимизируемая функция неднфференцируема, а каждое вычисление функции — это дорогой эксперимент. Метод золотого сечения рассчитан на детерминированные задачи. В стохастических задачах из-за ошибок эксперимента можно неправильно определить соотношения между значениями функций в точках; тогда дальнейшие итерации пойдут по ложному пути. Поэтому если различия функций в выбранных точках стали того же порядка, что и ошибки эксперимента, то итерации надо прекращать.

Поскольку вблизи минимума чаще всего бФ (бх)', то небольшая погрешность функции приводит к появлению довольно большой области неопределенности бх у' бФ. 3. Метод парабол. Метод золотого сечения надежный, но медленный. Если Ф(х) дифференцируема, то можно построить гораздо более быстрые методы, основанные на решении уравнения Ф'(х)=0. Напомним, что корень х этого уравнения является точкой минимума, если Ф" (х) ) О, и точкой максимума при Ф" (х) <О. На практике часто Ф(х) имеет и первую производную и вторую. Поэтому.для нахождения нулей первой производной применяют метод линеаризации, что приводит к такому итерационному процессу: МИНИМРМ ЮУНКЦИИ ОДНОГО ПЕРЕМЕННОГО тремя членами, т.

е. аппраксимируем кривую параболой Ф (х) Ф (х,) + (х — х,) Ф' (х,) + — (х — х,)' Ф" (х,); 1 Ь Ф (х,+51) — Ф (х,— Ь) 2 Ф (х, + Л) — 2Ф (х,) + Ф (х, — Ь) (12) Это эквивалентно замене кривой на интерполяционную параболу, построенную по трем точкам х, — Ь, х„ хх+ Ь. Обычно выбирают вспомогательный шаг Ь вЂ” 0,1 — 0,01 при ручных расчетах с небольшим числом знаков и Ь 0,01 — 0,001 при расчетах на ЭВМ; то~да характер сходимости вблизи экстремума вплоть до расстояний Ьз практически не отличается от квадратичного.

Формула (12) наиболее, часто употребляется в практических расчетах. Этот способ кажется неэкономным, нбо на каждой итерации надо вычнслять трн значения функцнн. Построейне параболы по трем последовательным итерациям, как это делалось в методе парабол прн нахождении корней много- члена, дает Ф (Х5 «5-1) 2х „т=хх+х ч (х5 хх 1, хз й (16) н требует только одного вычисления функцнн за итерацию.

Однако ранее уже отмечалось, что такая замена производных разделенпымн разностямя уменьшаег скорость сходнмостн. Можно показать, используя опнсанную в главе Ъ', 4 2, и. 7 технику, что вблвзн невырождсннога минимума ~ Ф" (х) 1о,заз ) х ., — е, = ! . †, †, ~ 1 х — х /1,ЗЗЗ. 1 6Ф" (х) (14) Во-первых, отсюда видно, что ) хх„,— Е ~ ( ~х,— х 1„только если выполнено условие ~ х,— х ~ ( 6Ф"(Ф5 1; это приблизительно показывает размеры окрестностн корйя, в которой Итерации сходятся. Эта окрестность может быть небольшой, если Ф" (х) неявка.

Во-вторых, аснмптотнческая скорость сходнмостн определяется показателем степенн прн ! х, †х , 'в правой части соотношения (14). Этот показатель невелик; позтол1у сходнмость настолько медленна, что трн итерации по этой формуле только немного сильней уменьшают погрешность, чем одна итерация по формуле (12).

А поскольку формула (13) ьедостаточно нспытана на пррктике, то нет уверенности, что ова окажется лучше. минимум этой параболы достигается в точке, определяемой формулой (!1). Итерационный процесс (11) является ньютоновским; вблизи простого корня уравнения Ф'(х) =О, т. е. вблизи экстремума с ненулевой второй производной, он сходится квадратично. Если же Ф" (х) = О, то сходимость в достаточно малой окрестности экстремума есть, но она1 более.

медленная — линейная. Обычно для первой и тем более второй производной получаются очень громоздкие выражения. Поэтому выгоднее заменить их конечно-разностными аппроксимациями. Наиболее часто берут. симметричные разности (З.б) — (3.7) с постоянным шагом, что приводит к формуле ПОИСК МИНИ»1УМА 1гл, чп Заметим, что во всех вариантах метода парабол для успешной работы необходимы «кухонные» поправки к алгоритму. В ходе вычислений надо проверять, движемся ли мы к минимуму: вторая разность, стоящая в знаменателе формулы (!2), или вторая производная в знаменателе формулы (11) должна быть положительной.

Если она отрицательна, то итерации сходятся к максимуму, и надо сделать какой-то шаг в обратном направлении, причем достаточно большой. Вычислив новое приближение, надо обязательно проверить, уменьшилась ли функция. Если оказалось, что Ф (х,ы) ) Ф (х,), то значение х,ы нельзя использовать и надо просто сделать от точки х, какой-то шаг в сторону убывания функции. Обычно делают шаг величиной т(х„,— х,) с т='/» и проверяют условие убывания функции; если оно снова не выполнено, то уменьшают т вдвое и делают шаг опять из точки х„и так до тех пор, пока не добьются убывания функции. Фактическая скорость работы программы очень сильно зависит от того, насколько тщательно обдуманы эти поправки к алгоритму.

Если функция имеет несколько локальных минимумов, то итерационный метод может сойтись к любому из них. Удалять найденные минимумы можно только в том случае, когда мы располагаем явным выражением. для Ф'(х) и решаем не исходную задачу (1), а уравнение Ф'(х) = 0; тогда удаляют уже найденные корни этого уравнения при помощи техники, описанной в главе Ч.

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

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

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

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