Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
REAL X,R,A,B,E INTEGER N,I EXTERNAL F
DATA A,B,E,N/0., 1., 1 .E — 5,20/
С ОБРАЩЕНИЕ К ПРОГРАММЕ В4А0
CALL B4A0(X,R,F,A,B,E,N,I)
С ВЫВОД НА ТЕРМИНАЛ ПРИБЛИЖЕННОГО
С ЗНАЧЕНИЯ КОРНЯ И ИНДЕКСА ОШИБОК
WRITE (5,1) Х,1 1 FORMAT (2Х/Х = ',Е13.6/1 = ',12)
END
С ФУНКЦИЯ-ПОДПРОГРАММА, ВЫЧИСЛЯЮЩАЯ
С ЗНАЧЕНИЕ F(X)
FUNCTION F(X)
REAL X F=X—EXP( —X)
RETURN
END
# 9.5. Поиск минимума функции
Поиск оптимальных инженерно-технических, экономических и научных решений — основное поле деятельности инженера и ученого. Задачи минимизации функций одного или нескольких переменных принадлежат к этому важному направлению.
Функция Ф(хи ..., хп), подлежащая минимизации, называется целевой функцией.
Задача поиска максимума Ф(хи ..., *„) сводится к минимизации функции—Ф(хх, поэтому, не ограничивая общности, будем
рассматривать задачу поиска минимума.
Примерами целевых функций могут служить: расход топлива Ф, необходимый для вывода космического аппарата на орбиту (за счет выбора параметров аппарата и траектории д:= (x1? ..., хи)
363
стараются минимизировать величину Ф); вес Ф механической конструкции с заданной прочностью; стоимость Ф выпускаемой продукции предприятия и т. п.
Наибольшие трудности поиска минимума Ф(л:) возникают, когда размерность п вектора л: велика. Поэтому важнейшей является проблема уменьшения размерности вектора целевой функции на этапе построения математической модели технической задачи. В модели следует сохранить только те переменные хь которые сильнее других влияют на изменение целевой функции. Естественно, что такая информация обычно связана с опытом и знаниями в конкретных 1 предметных областях.
9.5.1. Решение уравнений и минимизация. Покажем, как поиск корня системы^ нелинейных уравнений можно свести к задаче минимизации и, наоборот, минимизацию—к решению системы уравнений.
Предположили, что в области В пространства Еп необходимо решить систему уравнений
/,.(*1, Х2, *и)=0,
/2(хи х2, ..., х„)=0,
/п(*ъ х2, ..., х„)=0.
Пусть известно, что в В существует решение (9.5.1). Определим целевую функцию Ф{х) формулой
?
Ф(*1> *„)+/2(*1, -, *„)+..•+/» (*1,
(9.5.2)
В области В целевая функция ф(д:)^0. Минимальное значение Ф(л:) достигает на корне (9.5.1) — векторе х = (х1, ..., х„), который обращает все /г(х) в нуль. Поэтому решение системы (9.5.1) эквивалентно поиску минимума Ф, определенной формулой (9.5.2): найти
пипФ(*). (9.5.3)
я
Если минимальное значение Ф(л:) в В строго больше нуля, то это свидетельствует, что в В система уравнений (9.5.1) не имеет решений.
Теперь рассмотрим задачу (9.5.3) как исходную с функцией ф(4 непрерывно дифференцируемой в открытой области В. Пусть известно, что в В существует л:, доставляющий минимум Ф(*), тогда в этой точке х = (д:1, ..., хп) с необходимостью должны выполняться соотношения
\
364
Система уравнений (9.5.4) имеет форму (9.5.1). Решение (9.5.4) позволяет определить неизвестные экстремальные точки. Затем, используя достаточные условия минимума, следует выделить точки, в которых достигается локальный минимум, затем, сравнив значение целевой функции в точках локального минимума, надо выбрать точку (одну или несколько) с минимальной величиной локального минимума, т. е. определить глобальный минимум Ф(х) в области И.
В качестве первого примера рассмотрим систему уравнений
Гл:1-0,05е_^1^2 = 0,
|л;2—0,05е~(*1+*2)=о
в области В = { 1*!—0,11<0,1, \х2—0,11<0,1}. Решение этой системы эквивалентно поиску минимума Ф(х1? х2):
1ШП Ф (хл)=[(*! - 0,05с-*1*2)2+(*2 - 0,05е-(*‘+*2>)2].
В качестве второго примера найдем в области /) = {|л:1|<1,
| х21 < 1} минимум Ф (хх, х2):
ттФ(ед) = Х1+4“^1-^2* в
Система уравнений (9.5.4) принимает вид
(2x1—хх =0,
(2x1—х2=0.
Отсюда получаем точки экстремума с координатами (х^1} = 0, х<12) = 1/^/2, *?>= — 1/ч/2)(*^1)=0, *^=1/^, х^-1/^2), всего девять точек. Из них четыре точки дают локальный и одновременно глобальный минимум, а именно: (1/л/2, 1/>/2); (—1/^/2, 1/л/2); (-1/^/2, —1/^/2); (11у/29 —1/^/2). Минимальное значение целевой функции в этих точках Ф = —1/2.
9.5.2. Поиск минимума функции перебором. Идея алгоритма перебора крайне проста. Вычислим в конечном числе точек х(к) области Е> значения Ф(х) и сравним их между собой. Точку х{*\ которая дает минимальное значение целевой функции, назовем приближенным элементом х, минимизирующим Ф(х).
Точность определения точки минимума, причем глобального, зависит от плотности заполнения области О дискретным множеством х{к).
Рис. 9.15
При большой размерности вектора п реализовать на ЭВМ алгоритм перебора невозможно из-за огромного объема вычислительной работы.
Пусть область D — гиперкуб
D = { 0<х*<1,
в котором ищется ттФ(х). Точность определения координат вектора, минимизирующего Ф, положим равной 0,1. Тогда интервалы 0<х^1 следует разбить на 10 частей с шагом h = 0,1 плоскостями, ортогональными х( (рис. 9.15), и вычислить во всех точках пересечения плоскостей значения Ф(х). Всего потребуется вычислить Ф(х) в 10" точках. Пусть для нахождения Ф в каждой точке требуется, например ~102и арифметических операций. Тогда общее число арифметических операций алгоритма перебора ~10"+2я и при я =10 на ЭВМ с быстродействием 106 оп/с требуется 107 с, т. е. ~4 месяца непрерывной работы ЭВМ.
