k номер итерации
|
|
|
1
|
-0,497419
|
0,116021
|
2
|
-0,451529
|
-0,003278
|
-0,450185
|
-0,000003
|
Таблица 3. Пример 3
Так как < , следовательно минимум x = -0,450185.
Рисунок 3. Функция
2 Математические и
алгоритмические основы решения задачи
Пусть имеет первую и вторую производную. Разложим в ряд Тейлора в некоторой точке , ограничиваясь при этом тремя членами
разложения:
. (3)
Иными словами,
аппроксимируем нашу функцию в точке , параболой (рисунок 1).
Для этой параболы можно аналитически вычислить положение экстремума как корень
уравнения первой производной от (3):
.
Пусть минимум
аппроксимирующей параболы находится в точке . Тогда
вычислив значение функции , мы получаем новую точку
приближения к минимуму.
Рисунок 4. Поиск минимума
функции методом парабол
Обычно в практических
реализациях данного метода не используют аналитический вид первой и второй
производных . Их заменяют конечно-разностными
аппроксимациями. Наиболее часто берут симметричные разности с постоянным шагом h:
Это эквивалентно
аппроксимации функции параболой, проходящей через три близкие точки
,
, .
Окончательное выражение,
по которому можно строить итерационный процесс, таково:
(4)
Данный метод отличается
от других методом поиска минимума высокой скоростью сходимости. Вблизи
экстремума, вплоть до расстояний ~, сходимость практически не
отличается от квадратичной. Однако алгоритм требует постоянного контроля
сходимости. Например, итерационный процесс будет сходиться к минимуму, если:
1) знаменатель формулы
должен быть > 0. Если
это не так, нужно сделать шаг в обратном направлении, причем достаточно
большой. Обычно в итерационном процессе полагают
.
Иногда ради упрощения
расчетов полагают
,
однако это существенно
уменьшает скорость сходимости.
2) если это не так, то от следует сделать шаг
,
с .
Если и при этом условие
убывания не выполнено, уменьшают τ и вновь делают шаг.
3 Функциональные модели
и блок-схемы решения задачи
Функциональные модели и блок-схемы
решения задачи представлены на рисунке 5, 6.
Используемые обозначения:
· X0, MIN_VAL –
начальная точка;
· H, MAX_VAL –
конечная точка;
· EPS – требуемая точность;
· FN – функция для вычисления минимума;
· X1 – вспомогательная точка;
· X2 – вспомогательная точка;
· XN – вспомогательная точка;
· F_X0 – функция от начальной точки X0;
· F_X1 – функция от вспомогательной точки X1;
· F_X2 – функция от вспомогательной точки X2;
· F_XN – функция от вспомогательной точки XN;
· Q – рабочая переменная;
· A – рабочая переменная;
· B – рабочая переменная;
· C – рабочая переменная;
· D – рабочая переменная;
· Z – рабочая переменная;
· K – рабочая переменная.
Рисунок 5 – Блок-схема
решения задачи для функции PARABL_METHOD
Рисунок 6 –
Функциональная модель решения задачи для поиска минимума
4 Программная
реализация решения задачи
;ЗАГРУЖАЕМ
ФУНКЦИЮ, МИНИМАЛЬНОЕ И МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ,
;ТРЕБУЕМУЮ
ТОЧНОСТЬ ИЗ ФАЙЛА
(LOAD
"D:\\FUNCTION.TXT")
;ОЪЯВЛЯЕМ
ФУНКЦИЮ PARABL_METHOD ДЛЯ ПОИСКА МИНИМУМА ФУНКЦИИ
;X0 - НАЧАЛЬНАЯ ТОЧКА
;H - КОНЕЧНАЯ ТОЧКА
;EPS - ТОЧНОСТЬ ВЫЧИСЛЕНИЯ
;FN - ФУНКЦИЯ ДЛЯ ВЫЧИСЛЕНИЯ МИМИМУМА
(DEFUN PARABL_METHOD (X0 H EPS FN)
;ОБЪЯВЛЯЕМ
ПЕРЕМЕННЫЕ
;---------------------
(DECLARE
(SPECIAL X1))
(DECLARE (SPECIAL X2))
(DECLARE (SPECIAL XN))
;ФУНКЦИИ ОТ ТОЧЕК
(DECLARE (SPECIAL F_X0))
(DECLARE (SPECIAL F_X1))
(DECLARE (SPECIAL F_X2))
(DECLARE (SPECIAL F_XN))
;ВСПОМОГАТЕЛЬНЫЕ
ПЕРЕМЕННЫЕ
(DECLARE
(SPECIAL Q))
(DECLARE (SPECIAL A))
(DECLARE (SPECIAL B))
(DECLARE (SPECIAL C))
(DECLARE (SPECIAL D))
(DECLARE (SPECIAL Z))
;---------------------
;УСТАНАВЛИВАЕМ
ПЕРВУЮ ТОЧКУ
(SETQ
X1 (+ X0 H))
;УСТАНАВЛИВАЕМ
ВТОРУЮ ТОЧКУ
(SETQ
X2 (+ X0 (* 2 H)))
;ВЫЗЫВАЕМ
ФУНКЦИЮ FN
;ВЫЧИСЛЯЕМ
ЗНАЧЕНИЯ ФУНКЦИИ В ВЫБРАННЫХ ТОЧКАХ
(SETQ F_X0 (FUNCALL FN
X0))
(SETQ F_X1 (FUNCALL FN X1))
(SETQ F_X2 (FUNCALL FN X2))
(DO
((K
0))
;МАКСИМАЛЬНОЕ
КОЛИЧЕСТВО ШАГОВ 10000 (>= K 10000)
((>=
K 10000))
;ВЫПОЛНЯЕМ
ДЕЙСТВИЯ СОГЛАСНО АЛГОРИТМУ ПОИСКА МИНИМУМА МЕТОДОМ ПАРАБОЛ
(SETQ Q (/ (- X0 X1) (- X1 X2)))
(SETQ A (+ (- (* Q F_X0) (* (* Q (+ 1 Q)) F_X1)) (* Q Q F_X2)))
(SETQ B (+ (- (* (+ (* 2 Q) 1) F_X0) (* (+ 1 Q) (+ 1 Q) F_X1)) (* Q Q
F_X2)))
(SETQ C (* (+ 1 Q) F_X0))
(SETQ D (SQRT (- (* B B)(* 4 A C))))
(IF (> (ABS (+ B D)) (ABS (- B D)))
(SETQ Z (+ B D))
(SETQ Z (- B D))
)
(SETQ XN (- X0 (/ (* (- X0 X1) 2 C) Z)))
(SETQ F_XN (FUNCALL FN XN))
;ПРОВЕРЯЕМ
ДОСТИГЛИ ЛИ МЫ ТРЕБУЕМОЙ ТОЧНОСТИ
(IF (< (ABS F_XN) EPS) (SETQ K 10000))
;ЗАДАЕМ
НОВЫЕ ЗНАЧЕНИЯ ТОЧКАМ
(SETQ X2 X1)
(SETQ X1 X0)
(SETQ X0 XN)
;ВЫЧИСЛЯЕМ
ЗНАЧЕНИЯ ФУНКЦИЙ В ТОЧКАХ
(SETQ F_X2 F_X1)
(SETQ F_X1 F_X0)
(SETQ F_X0 F_XN)
;УВЕЛИЧИВАЕМ
СЧЕТЧИК
(SETQ
K (+ K 1))
)
;ВОЗВРАЩАЕМ
МИНИМУМ ФУНКЦИИ
XN
)
;ВЫЗЫВАЕМ
ФУНКЦИЮ PARABL_METHOD
(SETQ MIMIMUM (PARABL_METHOD MIN_VAL MAX_VAL EPS (FUNCTION FUNC)))
;ЗАПИСЫВАЕМ РЕЗУЛЬТАТ
(SETQ OUTPUT_STREAM (OPEN " D:\MINIMUM.TXT" :DIRECTION
:OUTPUT))
;ЗАПИСЫВАЕМ МИНИМУМ
(PRINT 'MIMIMUM OUTPUT_STREAM)
(PRINT MIMIMUM OUTPUT_STREAM)
;ЗАКРЫВАЕМ ФАЙЛ
(TERPRI OUTPUT_STREAM)
(CLOSE OUTPUT_STREAM)
5 Пример выполнения
программы
Рисунок 7 – Входные
данные
Рисунок 8 – Выходные
данные
Пример 2.
Рисунок 9 – Входные
данные
Рисунок 10 – Выходные
данные
Пример 3.
Рисунок 11 – Входные
данные
Рисунок 12 – Выходные
данные
ЗАКЛЮЧЕНИЕ
Проблема
повышения качества вычислений, как несоответствие между желаемым и
действительным, существует и будет существовать в дальнейшем. Ее решению будет
содействовать развитие информационных технологий, которое заключается как в
совершенствовании методов организации информационных процессов, так и их
реализации с помощью конкретных инструментов – сред и языков программирования.
Итогом
работы можно считать созданную функциональную модель вычисления минимума заданной функции
методом парабол. Данная модель применима к
детерминированным задачам, т.е. погрешностью экспериментального вычисления
функции f(x) можно пренебречь. Созданная
функциональная модель вычисления
минимума заданной функции методом парабол и
ее программная реализация могут служить органической частью решения более
сложных задач.
СПИСОК
ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ и литературы
1. Бронштейн, И.Н.
Справочник по математике для инженеров и учащихся втузов [Текст] /
И.Н. Бронштейн, К.А. Семендяев. – М.: Наука, 2007. – 708 с.
2. Кремер, Н.Ш. Высшая математика для
экономистов: учебник для студентов вузов. [Текст] / Н.Ш.Кремер, 3-е издание –
М.:ЮНИТИ-ДАНА, 2006. C. 412.
3. Калиткин, Н.Н. Численные методы.
[Электронный ресурс] / Н.Н. Калиткин. – М.: Питер, 2001. С. 504.
4. Поиск минимума функции [Электронный
ресурс] – Режим доступа: http://solidbase.karelia.ru/edu/meth_calc/files/12.shtm
5. Семакин, И.Г. Основы
программирования. [Текст] / И.Г.Семакин, А.П.Шестаков. – М.: Мир, 2006. C. 346.
6. Симанков, В.С. Основы функционального
программирования [Текст] / В.С. Симанков, Т.Т. Зангиев,
И.В. Зайцев. – Краснодар: КубГТУ, 2002. – 160 с.
7. Степанов, П.А. Функциональное
программирование на языке Lisp. [Электронный ресурс] / П.А.Степанов, А.В.
Бржезовский. – М.: ГУАП, 2003. С. 79.
8. Хювенен Э. Мир
Лиспа [Текст] / Э. Хювенен, Й. Сеппянен. – М.: Мир, 1990. – 460 с.