Green-sell.info

Новые технологии
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Методы оптимизации метод половинного деления

Методы одномерной оптимизации;

Эти методы строятся в предположении унимодальности функции F(x) на заданном интервале [a, b]. К функции не предъявляются требования непрерывности или дифференцируемости, предполагается лишь, что для любого x Î [a, b] значение F(x) может быть вычислено.

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

ü Методы последовательного поиска (методы сокращения интервалов, методы исключения интервалов)

Методы этой группы нацелены на построение такой стратегии поиска x*, при которой любая пара вычислений F(x) позволяет сузить область поиска (или интервал неопределенности). Вычисляя F(x) в точках x1 и x2 таких, что a

Основное различие между методами последовательного поиска состоит в стратегиях выбора значений x1 и x2.

· Метод дихотомии (половинного деления) – один из самых простых методов последовательного поиска.

Метод половинного деления (метод дихотомии) проиллюстрирован ниже.

· Метод золотого сечения предполагает такое сокращение интервала на каждом шаге, что отношение целого к большей части было равно отношению большей части к меньшей. Это отношение, равное 1.618, и называют «золотым сечением». (1 : 0,618 = 1,618; 0.618 : 0,382 = 1,618)

Значение коэффициента К (0,382) подобрано так, что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточной точкой от предыдущего шага. Это позволяет сократить число вычислений целевой функции на всех шагах (кроме первого) в 2 раза.

Таким образом, требуется не более N шагов и N+1 вычисление целевой функции, где N можно рассчитать, используя соотношение (b–a)/ε = (1–a)N при заданной погрешности ε определения экстремума.

· Метод чисел Фибоначчи

Стратегия поиска связана с использованием чисел Фибоначчи, которые можно получить из рекуррентного соотношения Rk = Rk-1 + Rk-2 , k = 2, 3, …, R = R1 = 1. В отличие от метода золотого сечения, здесь коэффициент сокращения интервала изменяется от итерации к итерации, хотя он также близок к значению 0.382.

Норенков-2000: Согласно методу чисел Фибоначчи, используют числа Фибоначчи Ri, последовательность которых образуется по правилу Ri+2 = Ri+1 + Ri при R = R1 = 1, т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, . Метод аналогичен методу золотого сечения с тем отличием, что коэффициент K равен отношению Ri-2 /Ri, начальное значение i определяется из условия, что Ri должно быть наименьшим числом Фибоначчи, превышающим величину (b–a)/ε, где ε — заданная допустимая погрешность определения экстремума. Так, если (b–a)/ε = 100, то начальное значение i = 12, поскольку R12 = 144, и K = 55/144 = 0,3819, на следующем шаге будет K = 34/89 = 0,3820 и т.д.

Основной недостаток метода – необходимость задания числа шагов. Основное преимущество – быстрое сужение интервала неопределенности: при числе шагов n = 14 интервал неопределенности примерно в 5 раз меньше, чем получаемый по методу половинного деления. В то же время по сравнению с методом золотого сечения метод Фибоначчи позволяет получить интервал только на 17% меньше, и при большом числе шагов оба эти метода практически идентичны.

ü Методы полиномиальной аппроксимации

Общая идея методов, использующих аппроксимацию функции, основана на приближении функции гладким полиномом и использовании этого полинома для оценки координаты минимума.

· Метод квадратичной интерполяции – один из популярных методов этой группы.

Метод заключается в замене нелинейной функции F(x) квадратичной параболой F2(x), построенной по трем точкам, принадлежащим F(x), так, чтобы значения аппроксимирующей функции F2(x) совпали со значениями F(x) в этих трех точках. Минимум квадратичной функции находится с использованием аналитического условия оптимальности: df/dx = 0.

На первом этапе в качестве исходных трех точек используются

В этих точках вычисляется f(x) и по полученным точкам f(x1), f(x2), f(x3) строится парабола

коэффициенты которой находятся из решения соответствующей системы уравнений:

Условие оптимальности приводит к уравнению x4 = – C1 / 2C2 , где х4 – точка минимума параболы f2(x).

Далее выбирается новый отрезок, внутри которого находится точка х4, и c использованием х3, х4 строится новая парабола, по которой уточняется положение минимума f(x), и т. д. до тех пор, пока величина отрезка, внутри которого находится оптимум, не станет меньше заданной погрешности e. Таким образом, метод имеет итерационный характер.

К достоинствам метода относится высокая скорость сходимости, хотя метод может не всегда сходиться.

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

Пример. Найти максимум функции f(x) = sin (x + 1)на интервале [-1; 2], точность e = 0,01.

Решение. Для построения аппроксимирующей параболы находим точки

Система уравнений для нахождения коэффициентов параболы примет вид:

Решение системы можно найти любым из известных способов, например, по формулам Крамера. На первом шаге получаем = 0,5571, f( ) = 0.9999. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола.

Метод половинного деления

Домашняя лабораторная работа по теме «Приближенное решение уравнений с одной переменной»

Задание. Найти один из корней уравнения методом деления отрезка пополам (методом Фибоначчи, «золотого сечения», рандомизации) с точностью до : 1) отделить корень на отрезке , проверить его единственность; 2) реализовать один из методов деления отрезка в заданном отношении (использовать ЭВМ или калькулятор); 3) сделать проверку точности найденного решения подстановкой его в исходное уравнение.

Порядок выполнения работы

1) Графическое отделение корня в случае достаточно сложного выражения y=f(х) можно производить следующим образом. Допустим, что уравнение можно представить в виде f1(x) = f2(x). В этом случае строим графики функций у=f1(x) и y=f2(x); абсциссы точек пересечения кривых будут действительными корнями уравнения. Найдем, например, приближенно корни уравнения x-sin x-1 = 0, записав это уравнение в виде x-1 = sin x. Построим графики функций y = sin x и у = х-1 (рис.2). Точка пересечения этих линий имеет абсциссу х ≈ 1,9, что можно считать грубым приближением значения корня.

Интервал [а;b] является интервалом изоляции корня, если его можно считать настолько малым, что на нем лежит точно один корень исходного уравнения. Выбор этого интервала производится на основании свойства непрерывных функций: если функция у=f(x) непрерывна на отрезке [а;b] и на концах отрезка принимает значения разных знаков (f(a)f(b)

Читать еще:  Какая версия linux лучше

Найдем интервал изоляции корня уравнения: х 3 +x 2 -1=0. Для этого представим уравнение в виде: х 3 =1-x 2 , т. е. f(x)=x 3 и g(x)=1-x 2 . Построим приближенно графики функций y=f(x) и y=g(x) (рис 4). Точка пересечения графиков двух функций, а значит, и корень уравнения находится на отрезке [0;1]. Проверим аналитические условия: f(0)=0 3 +0 2 -1=-1 3 +1 2 -1=1>0, и f'(х)=3х²+2x>0 на отрезке [0;1]. Таким образом, мы определили интервал изоляции корня, для нахождения которого достаточно применить любой из аналитических методов численного решения уравнений.

Задача отыскания корней уравнений может считаться практически решенной, если удалось определить корни с нужной степенью точности и указать пределы возможной погрешности.

Метод половинного деления

Рассмотрим один из самых простых численных методов решения уравнений – метод половинного деления. Пусть для уравнения найден интервал изоляции корня – отрезок [а;b]. Для уточнения искомого корня отрезок [а;b] делим пополам и из двух, полученных в результате этого деления отрезков выбираем тот, для которого выполняются условия существования и единственности корня (на концах отрезка функция принимает значения разных знаков). Середину отрезка находим по формуле хi=(a+b)/2, i=1,2,3…, и продолжаем данный процесс пока не достигнем необходимой точности (рис.5).

Рассмотрим применение метода половинного деления на примере решения уравнения х 3 +x 2 -1 = 0 на отрезке [0;1]. Разделим интервал изоляции пополам – это точка х=0,5. Получим два подотрезка – [0;0,5] и [0,5;1]. Вычислим значения функции на концах отрезков, f(0)=-1 3 +0,5 2 -1=0,125+0,25-1=-0,625 3 +1 2 -1=1+1—1=1>0, т. е. на концах отрезка [0,5;1] функция имеет значения разных знаков, следовательно, корень уравнения принадлежит отрезку [0,5;1]. Выбираем этот отрезок для дальнейшего рассмотрения.

Повторяем метод половинного деления уже для нового отрезка. Середина отрезка x=(0,5+1)/2=0,75, и из двух полученных отрезков выбираем правый отрезок [0,75;1], т.к. f(0,75) = -0,015625 0. Процесс продолжается до получения корня с заданной степенью точности.

Если делить отрезок [a;b] сразу на десять частей, то на следующем шаге можно получить отрезок в десять раз меньший, чем [a;b].

2. Метод Фибоначчи

Рассмотрим одну из разновидностей метода половинного деления – метод Фибоначчи.

Пусть дано уравнение , где функция у= непрерывна на и . Для уточнения корня данного уравнения введем последовательность чисел Фибоначчи: , , , это будут числа 1,1,2,3,5,8,13,21 и т.д. Согласно данному методу, на каждом ом этапе отрезок делят в отношении , где и соответственно е и е число из последовательности Фибоначчи. Так на первом шаге отрезок делят в отношении (пополам) и выбирают тот из них, на концах которого функция имеет разные знаки. На втором этапе выбранный суженный отрезок делят в отношении , следующие в отношениях , , В результате получаем на некотором этапе точный корень уравнения, или же бесконечную последовательность отрезков таких, что (n=1,2,…). Формула для вычисления имеет вид: В качестве корня можем принять .

Методы дихотомии

Материал из MachineLearning.

Содержание

Введение

Существует довольно очевидная теорема: «Если непрерывная функция на концах некоторого интервала имеет значения разных знаков, то внутри этого интервала у нее есть корень (как минимум, один, но м.б. и несколько)». На базе этой теоремы построено численное нахождение приближенного значения корня функции. Обобщенно этот метод называется дихотомией, т.е. делением отрезка на две части. Обобщенный алгоритм выглядит так:

  1. Задать начальный интервал ;
  2. Убедиться, что на концах функция имеет разный знак;
  3. Повторять
    • выбрать внутри интервала точку ;
    • сравнить знак функции в точке со знаком функции в одном из концов;
      • если совпадает, то переместить этот конец интервала в точку ,
      • иначе переместить в точку другой конец интервала;

пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд.

Метод половинного деления

Метод половинного деления известен также как метод бисекции. В данном методе интервал делится ровно пополам.

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

Метод половинного деления:

  1. Один из простых способов поиска корней функции одного аргумента.
  2. Применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).

Метод половинного деления как метод поиска корней функции

Изложение метода

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

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

Пусть функция непрерывна на отрезке ,

и — единственный корень уравнения .

(Мы не рассматриваем случай, когда корней на отрезке несколько, то есть более одного. В качестве можно взять и другое достаточно малое положительное число, например, .)

Поделим отрезок пополам. Получим точку и два отрезка .

  • Если , то корень найден ( ).
  • Если нет, то из двух полученных отрезков и надо выбрать один такой, что , то есть
    • , если или
    • , если .

Новый отрезок делим пополам. Получаем середину этого отрезка и так далее.

Для того, чтобы найти приближённое значение корня с точностью до 0″ alt= » eps >0″ />, необходимо остановить процесс половинного деления на таком шаге , на котором

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

Рассмотрим метод половинного деления как простейший однопараметрический метод безусловной оптимизации. Данный метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

Запишем словесный алгоритм метода.

  1. На каждом шаге процесса поиска делим отрезок пополам, — координата середины отрезка .
  2. Вычисляем значение функции в окрестности вычисленной точки , т.е.
    .
  3. Сравниваем и и отбрасываем одну из половинок отрезка (рис. 1).
    • При поиске минимума:
      • Если , то отбрасываем отрезок , тогда . (рис. 1.а)
      • Иначе отбрасываем отрезок , тогда . (рис. 1.б)
    • При поиске максимума:
      • Если , то отбрасываем отрезок , тогда .
      • Иначе отбрасываем отрезок , тогда .
  4. Деление отрезка продолжается, пока его длина не станет меньше заданной точности , т.е. .
Читать еще:  Анализ методов решения комбинаторных оптимизационных задач

Схема алгоритма метода представлена на рис 2.

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

Метод хорд

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

Изложение метода

Метод основан на замене функции на каждом шаге поиска хордой, пересечение которой с осью дает приближение корня.

При этом в процессе поиска семейство хорд может строиться:

  1. при фиксированном левом конце хорд, т.е. , тогда начальная точка (рис. 3а);
  2. при фиксированном правом конце хорд, т.е. , тогда начальная точка (рис. 3б);

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

Процесс поиска продолжается до тех пор, пока не выполнится условие или .

Метод обеспечивает быструю сходимость, если 0″ alt= «f(z)cdot f»(z) > 0″ />, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.

Комбинация метода хорд и метода половинного деления

Метод хорд можно применить в качестве «последнего штриха» после того, как метод половинного деления гарантирует требуемую точность — это не улучшит существенно гарантируемой точности, но, скорее всего, на несколько порядков повысит точность решения.

Если применять аналогичное уточнение к интервалу, полученному методом хорд, то эффект будет значительно слабее. Это ещё раз иллюстрирует тот факт, что метод хорд очень хорошо работает в условиях малого интервала (близости обеих границ интервала к корню), но неспособен сам создать себе эти условия (приблизить обе границы к корню).

На вопрос о том, стоит ли использовать попеременное применение метода половинного деления и метода хорд, ответ отрицателен. После того, как метод хорд приближает одну из границ почти вплотную к корню, методу половинного деления придётся долго работать, чтобы гарантировать заданную точность, т.к. метод хорд ее гарантировать не может.

Поэтому лучше использовать в качестве точки деления что-то среднее: если метод половинного деления предлагает использовать , а метод хорд — , то возьмем . Коэффициент .

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

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

Метод дихотомии (половинного деления).

ЗАДАНИЕ

на курсовую работу студента

Матушкина Михаила Николаевича

1 Дисциплина (специализация) «Вычислительная математика»

2 Тема работы: Выполнить минимизацию целевой функции методом дихотомииF(x)= .

3 Срок сдачи студентом законченной работы ___________________2018г.

4 Пояснительная записка должна содержать.:

1) Анализ численных методов одномерной оптимизации.

2) Математическое описание заданного метода

3) Подробный ход решения

Руководитель проекта_____________________________/Чернецкий В.О.

Студент _____________________________/Матушкин М.Н.

АННОТАЦИЯ

В ходе работы над курсовым проектом выполнен анализ численных методов одномерной оптимизации: Методы дихотомии, хорд, касательных, золотого сечения, метод Ньютона. Математическое описание метода дихотомия или половинного сечения. Также подробный ход решения методом дихотомии.

ОГЛАВЛЕНИЕ

1. Анализ численных методов одномерной оптимизации. 7

1.1 Метод дихотомии (половинного деления). 7

1.2 Метод хорд. 7

1.4 Метод золотого сечения. 8

1.5 Метод Ньютона. 8

2.Математическое описание заданного метода. 9

3.Подробный ход решения. 10

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 14

ВВЕДЕНИЕ

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

Для выполнения минимизации целевой функции используются различные методы, один из которых – метод дихотомии.

Метод дихотомии(метод половинного сечения) — метод является методом прямого поиска. В нем при поиске экстремума целевой функции используются только вычисленные значения целевой функции.

Для решения целевой функции и поиска экстремума часто используются программы, написанные на различных языках программирования, что позволяет облегчить решение.

Анализ численных методов одномерной оптимизации.

Метод дихотомии (половинного деления).

Метод основан на делении текущего отрезка [а, b],где содер­жится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется минимум (максимум) в качестве следующего текущего отрезка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на ε/2, где ε –погрешность решения задачи оптимизации.

Метод дихотомии (половинного деления):

1. Один из простых способов поиска корней функции одного аргумента.

2. Применяется для нахождения значений действительно-значной функции, определяемому по какому-либо критерию (это может быть сравнение на минимум, максимум или конкретное число).

К недостаткам метода относится его работоспособность только для одноэкстремальных функций R(x) (т.е. таких, которые содержат один экстремум того типа, который мы ищем в задаче), так как в других случаях при сравнении двух критериев в соседних точках невозможно правильно выбрать следующий интервал, где находится минимум (максимум).

Метод хорд

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

Читать еще:  Решение задач оптимизации в mathcad

Метод секущих.

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

Методы одномерной оптимизации;

Эти методы строятся в предположении унимодальности функции F(x) на заданном интервале [a, b]. К функции не предъявляются требования непрерывности или дифференцируемости, предполагается лишь, что для любого x Î [a, b] значение F(x) может быть вычислено.

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

ü Методы последовательного поиска (методы сокращения интервалов, методы исключения интервалов)

Методы этой группы нацелены на построение такой стратегии поиска x*, при которой любая пара вычислений F(x) позволяет сузить область поиска (или интервал неопределенности). Вычисляя F(x) в точках x1 и x2 таких, что a

Основное различие между методами последовательного поиска состоит в стратегиях выбора значений x1 и x2.

· Метод дихотомии (половинного деления) – один из самых простых методов последовательного поиска.

Метод половинного деления (метод дихотомии) проиллюстрирован ниже.

· Метод золотого сечения предполагает такое сокращение интервала на каждом шаге, что отношение целого к большей части было равно отношению большей части к меньшей. Это отношение, равное 1.618, и называют «золотым сечением». (1 : 0,618 = 1,618; 0.618 : 0,382 = 1,618)

Значение коэффициента К (0,382) подобрано так, что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточной точкой от предыдущего шага. Это позволяет сократить число вычислений целевой функции на всех шагах (кроме первого) в 2 раза.

Таким образом, требуется не более N шагов и N+1 вычисление целевой функции, где N можно рассчитать, используя соотношение (b–a)/ε = (1–a)N при заданной погрешности ε определения экстремума.

· Метод чисел Фибоначчи

Стратегия поиска связана с использованием чисел Фибоначчи, которые можно получить из рекуррентного соотношения Rk = Rk-1 + Rk-2 , k = 2, 3, …, R = R1 = 1. В отличие от метода золотого сечения, здесь коэффициент сокращения интервала изменяется от итерации к итерации, хотя он также близок к значению 0.382.

Норенков-2000: Согласно методу чисел Фибоначчи, используют числа Фибоначчи Ri, последовательность которых образуется по правилу Ri+2 = Ri+1 + Ri при R = R1 = 1, т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, . Метод аналогичен методу золотого сечения с тем отличием, что коэффициент K равен отношению Ri-2 /Ri, начальное значение i определяется из условия, что Ri должно быть наименьшим числом Фибоначчи, превышающим величину (b–a)/ε, где ε — заданная допустимая погрешность определения экстремума. Так, если (b–a)/ε = 100, то начальное значение i = 12, поскольку R12 = 144, и K = 55/144 = 0,3819, на следующем шаге будет K = 34/89 = 0,3820 и т.д.

Основной недостаток метода – необходимость задания числа шагов. Основное преимущество – быстрое сужение интервала неопределенности: при числе шагов n = 14 интервал неопределенности примерно в 5 раз меньше, чем получаемый по методу половинного деления. В то же время по сравнению с методом золотого сечения метод Фибоначчи позволяет получить интервал только на 17% меньше, и при большом числе шагов оба эти метода практически идентичны.

ü Методы полиномиальной аппроксимации

Общая идея методов, использующих аппроксимацию функции, основана на приближении функции гладким полиномом и использовании этого полинома для оценки координаты минимума.

· Метод квадратичной интерполяции – один из популярных методов этой группы.

Метод заключается в замене нелинейной функции F(x) квадратичной параболой F2(x), построенной по трем точкам, принадлежащим F(x), так, чтобы значения аппроксимирующей функции F2(x) совпали со значениями F(x) в этих трех точках. Минимум квадратичной функции находится с использованием аналитического условия оптимальности: df/dx = 0.

На первом этапе в качестве исходных трех точек используются

В этих точках вычисляется f(x) и по полученным точкам f(x1), f(x2), f(x3) строится парабола

коэффициенты которой находятся из решения соответствующей системы уравнений:

Условие оптимальности приводит к уравнению x4 = – C1 / 2C2 , где х4 – точка минимума параболы f2(x).

Далее выбирается новый отрезок, внутри которого находится точка х4, и c использованием х3, х4 строится новая парабола, по которой уточняется положение минимума f(x), и т. д. до тех пор, пока величина отрезка, внутри которого находится оптимум, не станет меньше заданной погрешности e. Таким образом, метод имеет итерационный характер.

К достоинствам метода относится высокая скорость сходимости, хотя метод может не всегда сходиться.

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

Пример. Найти максимум функции f(x) = sin (x + 1)на интервале [-1; 2], точность e = 0,01.

Решение. Для построения аппроксимирующей параболы находим точки

Система уравнений для нахождения коэффициентов параболы примет вид:

Решение системы можно найти любым из известных способов, например, по формулам Крамера. На первом шаге получаем = 0,5571, f( ) = 0.9999. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола.

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×