Навигация
3.2.1 Постановка задачи
Необходимо численным методом найти минимум функции F(x)=L(x1)x2-2.5L(x2)x-3
на отрезке [a;b] с точностью ε, при том, что L(x1) и L(x2) – коэффициенты, полученные вычислением полинома Лагранжа в точках x1, x2. Это задача одномерной оптимизации.
Выбор метода: Для решения задачи одномерной оптимизации существует множество методов, среди которых:
1) метод прямого перебора
2) метод дихотомии
3) метод золотого сечения
4) метод Фибоначчи
5) метод касательных
6) метод Ньютона
оптимизация методом квадратичной интерполяции Выберем метод дихотомии, т.к. он прост в алгоритмизации, обеспечивает быструю сходимость (на каждой итерации отрезок неопределённости сужается почти вдвое). Его недостаток в виде необходимости многократного вычисления F(x) не играет особой роли, т.к. F(x) – обыкновенный полином и расчёт его значений не затратит много ресурсов ПК.
Описание метода:
Пусть f(x)- унимодальная на [a;b] и требуется найти минимум f(x) с абсолютной погрешностью Е. Идея метода дихотомии состоит в проведении на каждой итерации двух отсчётов (вычислений значений функции), отстоящих от середины отрезке неопределённости [а;b] на величину de[0;2E] и сравнения значения исследуемой функции в двух точках х(n-1) и
x(n-1). определяемых рекуррентными формулами:
|
|
|
|
Если
, то 
Иначе
N = 1,2,...- номер итерации, а0=а , b0 = b .
Вычисления проводятся до тех пор, пока b-а >Е.
Тогда с абсолютной погрешностью, не превосходящей Е, полагают
x*=(aN+bN)/2
Длина конечного отрезка неопределённости:
L0=b-a – длина начального отрезка
На каждой итерации отрезок неопределённости [aN;bN] уменьшается примерно вдвое. Число отсчётов функции n и число итераций N связаны соотношением N=n/2
Практически величина d выбирается из условий различимости двух отсчётов функции
Процедура поиска минимума методом дихотомии использует большее количество отсчётов функции для локализации точки минимума на отрезке заданной длины.
Геометрическая иллюстрация метода дихотомии
4. Проверка условий сходимости методов. Поиск значений интерполяционного многочлена в точках x1 и x2
Для правильной работы этого метода необходимо, чтобы функция была ограничена на отрезке интерполирования. Выполнение этого условия очевидно по заданию.
Условия унимодальности на отрезке [a;b] (первая производная возрастает, вторая больше нуля) выполняются, следовательно, отрезок [a;b] остаётся таким же как по заданию [0;2]
5. Тестирование программных модулей
5.1 Тестирование модуля поиска значений интерполяционного многочлена в точках x1 и x2
Рассчитаем значения функции f(x)=x2, заданной в виде таблицы
в точках x1=-1, x2=0.5. Т.к. исходная функция – полином, то интерполирующая будет ей в точности соответствовать и f(x.1)=L(x1)=1, f(x2)=L(x2)=0.25
Схема алгоритма управляющей программы
Схема алгоритма модуля поиска значений интерполяционного многочлена в точкe xl
Похожие работы
... , так и их реализации с помощью конкретных инструментов – сред и языков программирования. Итогом работы можно считать созданную функциональную модель вычисления минимума заданной функции методом парабол. Данная модель применима к детерминированным задачам, т.е. погрешностью экспериментального вычисления функции f(x) можно пренебречь. Созданная функциональная модель вычисления минимума заданной ...
... исследованных функций. Так же необходимо изучить работу встроенных в MatLab функций. Протестировать программу на серии тестов. Теоретическое описание Одномерная оптимизация функций методом золотого сечения Метод золотого сечения состоит в построении последовательности отрезков [a0, b0], [a1, b1], …,стягивающихся к точке минимума функции f(x). На каждом шаге, за исключением первого, вычисление ...
... все многообразие факторов, имеющих место в реальных системах, т. е. использованию моделей, более адекватных исследуемым явлениям. Библиографический список 1 Лященко И.Н. Линейное и нелинейное программирования / И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова, Н.З.Шор. – К.: «Высшая школа», 1975, 372 с. 2 Методические указания для выполнения курсового проекта по дисциплине «Прикладная ...
... диаграммы. С этой целью строки и столбцы таблицы переставляются до тех пор, пока не получится упорядоченная диаграмма. Поиск сегментов рынка для программы установки защищенных сетевых соединений с помощью протокола ISAKMP Взрывной характер развития компьютерных технологий и резко возросшее количество действий совершаемых с помощью глобальной сети Internet (развитие электронной торговли, ...
0 комментариев