Подобные документы
Рассмотрение эффективности применения методов штрафов, безусловной оптимизации, сопряженных направлений и наискорейшего градиентного спуска для решения задачи поиска экстремума (максимума) функции нескольких переменных при наличии ограничения равенства.
контрольная работа , добавлен 16.08.2010
Анализ теорем сопряженных функторов. Естественное преобразование как семейство морфизмов. Характеристика свойств рефлективных подкатегорий. Знакомство с универсальными стрелками. Рассмотрение особенностей метода построения сопряженных функторов.
курсовая работа , добавлен 27.01.2013
Методика преобразования вращения и ее значение в решении алгебраических систем уравнений. Получение результирующей матрицы. Ортогональные преобразования отражением. Итерационные методы с минимизацией невязки. Решение методом сопряженных направлений.
реферат , добавлен 14.08.2009
Методы решения систем линейных алгебраических уравнений, их характеристика и отличительные черты, особенности и сферы применения. Структура метода ортогонализации и метода сопряженных градиентов, их разновидности и условия, этапы практической реализации.
курсовая работа , добавлен 01.10.2009
Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа , добавлен 30.04.2011
Формирование функции Лагранжа, условия Куна и Таккера. Численные методы оптимизации и блок-схемы. Применение методов штрафных функций, внешней точки, покоординатного спуска, сопряженных градиентов для сведения задач условной оптимизации к безусловной.
курсовая работа , добавлен 27.11.2012
Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа , добавлен 12.06.2011
Методы нахождения минимума функции одной переменной и функции многих переменных. Разработка программного обеспечения вычисления локального минимума функции Химмельблау методом покоординатного спуска. Поиск минимума функции методом золотого сечения.
курсовая работа , добавлен 12.10.2009
Решение систем линейных алгебраических уравнений методом простой итерации. Полиномиальная интерполяция функции методом Ньютона с разделенными разностями. Среднеквадратическое приближение функции. Численное интегрирование функций методом Гаусса.
курсовая работа , добавлен 14.04.2009
Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
Методы наискорейшего спуска или спуска по координатам даже для квадратичной функции требуют бесконечного числа итераций. Однако можно построить такие направления спуска, что для квадратичной функции
(где есть -мерный вектор) с симметричной положительно определенной матрицей А процесс спуска сойдется точно к минимуму за конечное число шагов.
Положительно определенная матрица позволяет ввести норму вектора следующим образом:
Нетрудно проверить, что все аксиомы нормы при этом выполнены. Определение (31) означает, что под скалярным произведением двух векторов х и у теперь подразумевается величина Векторы, ортогональные в смысле этого скалярного произведения
называют сопряженными (по отношению к данной матрице А). Ниже мы увидим, что поочередный спуск по сопряженным направлениям особенно выгоден при поиске минимума.
На этом основана большая группа методов: сопряженных градиентов, сопряженных направлений, параллельных касательных и другие. Для квадратичной функции они применяются с одинаковым успехом. На произвольные функции наиболее хорошо обобщается метод сопряженных направлений, у которого детали алгоритма тщательно отработаны; этот метод излагается в данном пункте.
а) Сначала рассмотрим, как применяется этот метод к квадратичной форме (30). Для этого нам потребуются некоторые свойства сопряженных векторов. Пусть имеется некоторая система попарно сопряженных векторов . Нормируем каждый из этих векторов в смысле нормы (31); тогда соотношения между ними примут вид
Докажем, что взаимно сопряженные векторы линейно-независимы.
Из равенства следует , что противоречит положительной определенности матрицы.
Это противоречие доказывает наше утверждение. Значит, система сопряженных векторов является базисом в -мерном пространстве. Для данной матрицы имеется бесчисленное множество базисов, состоящих из взаимно сопряженных векторов.
Пусть мы нашли некоторый сопряженный базис Выберем произвольную точку . Любое движение из этой точки можно разложить по сопряженному базису
Подставляя это выражение в правую часть формулы (30), преобразуем ее с учетом сопряженности базиса (33) к следующему виду:
Последняя сумма состоит из членов, каждый из которых соответствует только одной компоненте суммы (34). Это означает, что движение по одному из сопряженных направлений меняет только один член суммы (35), не затрагивая остальных.
Совершим из точки поочередные спуски до минимума по каждому из сопряженных направлений Каждый спуск минимизирует свой член суммы (35), так что минимум квадратичной функции точно достигается после выполнения одного цикла спусков, то есть за конечное число действий.
Поясним геометрический смысл сопряженного базиса. Если осями координат сделать главные оси эллипсоидов уровня квадратичной функции, то один цикл спусков по этим координатам приводит точно в минимум. Если перейти к некоторым аффинным координатам, то функция останется квадратичной, но коэффициенты квадратичной формы изменятся. Можно формально рассмотреть нашу квадратичную функцию с измененными коэффициентами как некоторую новую квадратичную форму в декартовых координатах и найти главные оси ее эллипсоидов. Положение этих главных осей в исходных аффинных координатах будет некоторой системой сопряженных направлений. Разный выбор аффинных координат естественно приводит к разным сопряженным базисам.
б) Сопряженный базис можно построить способом параллельных касательных плоскостей.
Пусть некоторая прямая параллельна вектору а квадратичная функция достигает на этой прямой минимального значения в точке . Подставим уравнение этой прямой в выражение (30) и потребуем выполнения условия минимума функции в точке т. е. при
Для этого воспользуемся выражением (35), где в сумме оставим только один член:
и положим . Отсюда следует уравнение, которому удовлетворяет точка минимума:
Пусть на какой-нибудь другой прямой, параллельной первой, функция принимает минимальное значение в точке гг; тогда аналогично найдем Вычитая это равенство из (36), получим
Следовательно, направление, соединяющее точки минимума на двух параллельных прямых, сопряжено направлению этих прямых.
Таким образом, всегда можно построить вектор, сопряженный произвольному заданному вектору . Для этого достаточно провести две прямые, параллельные и найти на каждой прямой минимум квадратичной формы (30). Вектор соединяющий эти минимумы, сопряжен Заметим, что прямая касается линии уровня в той точке, где функция на данной прямой принимает минимальное значение; с этим связано название способа.
Пусть имеются две параллельные -мерные плоскости, порожденные системой сопряженных векторов . Пусть квадратичная функция достигает своего минимального значения на этих плоскостях соответственно в точках . Аналогичными рассуждениями можно доказать, что вектор соединяющий точки минимума, сопряжен всем векторам . Следовательно, задана неполная система сопряженных векторов то этим способом всегда можно построить вектор сопряженный всем векторам этой системы.
Рассмотрим один цикл процесса построения сопряженного базиса. Пусть уже построен базис, в котором последние векторов взаимно сопряжены, а первые векторов не сопряжены последним. Найдем минимум квадратичной функции (30) в какой-нибудь -мерной плоскости, порожденной последними векторами базиса. Поскольку эти векторы взаимно сопряжены, то для этого достаточно произвольно выбрать точку и сделать из нее спуск поочередно по каждому из этих направлений (до минимума!). Точку минимума в этой плоскости обозначим через .
Теперь из точки сделаем поочередный спуск по первым векторам базиса. Этот спуск выведет траекторию из первой плоскости и приведет ее в некоторую точку
Из точки снова совершим по последним направлениям спуск, который приведет в точку Этот спуск означает точное нахождение минимума во второй плоскости, параллельной первой плоскости. Следовательно, направление сопряжено последним векторам базиса.
Если одно из несопряженных направлений в базисе заменить направлением то в новом базисе уже направление будет взаимно сопряжено.
Начнем расчет циклов с произвольного базиса; для него можно считать, что . Описанный процесс за один цикл увеличивает на единицу число сопряженных векторов в базисе. Значит, за цикл все векторы базиса станут сопряженными, и следующий цикл приведет траекторию в точку минимума квадратичной функции (30).
в) Хотя понятие сопряженного базиса определено только для квадратичной функции, описанный выше процесс построен так, что его можно формально применять для произвольной функции. Разумеется, что при этом находить минимум вдоль направления надо методом парабол, не используя нигде формул, связанных с конкретным видом квадратичной функции (30).
В малой окрестности минимума приращение достаточно гладкой функции обычно представимо в виде симметричной положительно определенной квадратичной формы типа (18). Если бы это представление было точным, то метод сопряженных направлений сходился бы за конечное число шагов. Но представление приближенно, поэтому число шагов будет бесконечным; зато сходимость этого метода вблизи минимума будет квадратичной.
Благодаря квадратичной сходимости метод сопряженных направлений позволяет находить минимум с высокой точностью. Методы с линейной сходимостью обычно определяют экстремальные значения координат менее точно.
Замечание 1. Реально даже для квадратичной функции процесс не всегда укладывается в циклов. Построение сопряженного базиса означает ортогонализацию в метрике, порожденной матрицей А. Ранее отмечалось, что в процессе ортогонализации теряется точность; при большом числе переменных погрешность настолько возрастает, что процесс приходится повторять.
Замечание 2. Теоретически безразлично, какое из несопряженных направлений выкинуть из базиса в конце цикла. Обычно выкидывают то направление, при спуске по которому на данном цикле функция изменилась менее всего. Поскольку для произвольной функции понятие сопряженности ввести нельзя, то направление наиболее слабого убывания выкидывают независимо от того, под каким номером оно стоит в базисе. Любопытно, что это оказывается выгодным даже для квадратичной функции, хотя на основании этого критерия иногда можно выкинуть сопряженное направление, оставив несопряженные; зато уменьшается потеря точности при ортогонализации.
Замечание 3. Описанный выше цикл метода включает два спуска по сопряженным направлениям и один - по несопряженным. Более выгоден цикл, при котором сразу после нахождения нового сопряженного направления по нему делают спуск из точки приходя в некоторую точку Тогда спуск из будет спуском в плоскости всех новых сопряженных направлений, т. е. его можно считать первой группой нового цикла спусков. Поэтому из точки сразу можно спускаться по несопряженным направлениям.
При этом новое направление ставят в базис на последнее место и выкидывают то направление, на котором функция слабее всего уменьшилась при спусках от точки до точки Наименее выгодным может оказаться и новое направление; тогда следующий цикл спусков будет сделан со старым базисом.
Метод сопряженных направлений является, по-видимому, наиболее эффективным методом спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа - «плато»-, и при большом числе переменных - до двух десятков.
Определение . Направление, определяемое ненулевым вектором называется асимптотическимнаправлением относительно линии второго порядка, если любая прямая этого направления (то есть параллельная вектору ) либо имеет с линией не более одной общей точки, либо содержится в этой линии.
? Сколько общих точек может быть у линии второго порядка и прямой асимптотического направления относительно этой линии?
В общей теории линий второго порядка доказывается, что если
То ненулевой вектор ( задаёт асимптотическое направление относительно линии
(общий критерий асимптотического направления ).
Для линий второго порядка
если , то нет асимптотических направлений,
если то существует два асимптотических направления,
если то существует только одно асимптотическое направление.
Полезной оказывается следующая лемма (критерий асимптотического направления линии параболического типа ).
Лемма . Пусть - линия параболического типа.
Ненулевой вектор имеет асимптотическое направление
относительно 
. (5)
(Задача. Доказать лемму.)
Определение . Прямая асимптотического направления называется асимптотой линии второго порядка, если эта прямая либо не пересекается с , либо содержится в ней.
Теорема . Если имеет асимптотическое направление относительно , то асимптота, параллельная вектору , определяется уравнением
Заполняем таблицу.
ЗАДАЧИ .
1. Найти векторы асимптотических направлений для следующих линий второго поря дка:
4 
- гиперболического типа два асимптотических направления.
Воспользуемся критерием асимптотического направления:
Имеет асимптотическое направление относительно данной линии 4 .
Если =0, то =0, то есть - нулевой. Тогда Поделим на Получаем квадратное уравнение: 
, где t = . Решаем это квадратное уравнение и находим два решения: t = 4 и t = 1. Тогда асимптотические направления линии .
(Можно рассмотреть два способа, так как линия – параболического типа.)
2. Выясните, имеют ли оси координат асимптотические направления относительно линий второго порядка:
3. Напишите общее уравнение линии второго порядка, для которой
а) ось абсцисс имеет асимптотическое направление;
б) Обе оси координат имеют асимптотические направления;
в) оси координат имеют асимптотические направления и О – центр линии.
4. Напишите уравнения асимптот для линий:
а) ng w:val="EN-US"/>
5. Докажите, что если линия второго порядка имеет две непараллельные асимптоты, то их точка пересечения является центром данной линии.
Указание: Так как есть две непараллельные асимптоты, то существует два асимптотических направления, тогда , а, значит, линия – центральная.
Запишите уравнения асимптот в общем виде и систему для нахождения центра. Всё очевидно.
6.(№920) Напишите уравнение гиперболы, проходящей через точку А(0, -5) и имеющей асимптоты х – 1 = 0 и 2х – y + 1 = 0.
Указание . Воспользуйтесь утверждением предыдущей задачи.
Домашнее задание . , №915(в,д,е), №916 (в,г,д), №920 (если не успели);
Шпаргалки;
Силаев, Тимошенко. Практические задания по геометрии,
1 семестр. С.67, вопросы 1-8, с.70, вопросы 1-3 (устно).
ДИАМЕТРЫ ЛИНИИ ВТОРОГО ПОРЯДКА.
СОПРЯЖЕННЫЕ ДИАМЕТРЫ.
Дана аффинная система координат .
Определение. Диаметром линии второго порядка, сопряженным вектору не асимптотического направления относительно , называется множество середин всех хорд линии , параллельных вектору .
На лекции доказано, что диаметр – это прямая и получено её уравнение
Рекомендации : Показать (на эллипсе), как строится (задаём не асимптотическое направление; проводим [две] прямые этого направления, пересекающие линию; находим середины отсекаемых хорд; проводим через середины прямую – это и есть диаметр).
Обсудить:
1. Почему в определении диаметра берётся вектор не асимптотического направления. Если не могут ответить, то попросите построить диаметр, например, для параболы.
2. Любая ли линия второго порядка имеет хотя бы один диаметр? Почему?
3. На лекции доказано, что диаметр – это прямая. Серединой какой хорды является точка М на рисунке?
4. Посмотрите на скобки в уравнении (7). Что они напоминают?
Вывод: 1) каждый центр принадлежит каждому диаметру;
2) если существует прямая центров, то существует единственный диаметр.
5. Какое направление имеют диаметры линии параболического типа? (Асимптотическое)
Доказательство (наверно, на лекции).
Пусть диаметр d, заданный уравнением (7`) сопряжен вектору не асимптотического направления. Тогда его направляющий вектор
(-(
), 
). Покажем, что этот вектор имеет асимптотическое направление. Воспользуемся критерием вектора асимптотического направления для линии параболического типа (см.(5)). Подставляем и убеждаемся (не забываем, что .
6. Сколько диаметров у параболы? Их взаимное расположение? Сколько диаметров у остальных линий параболического типа? Почему?
7. Как построить общий диаметр некоторых пар линий второго порядка (см. вопросы 30, 31 далее).
8. Заполняем таблицу, обязательно делаем рисунки.
1. . Напишите уравнение множества середин всех хорд, параллельных вектору
2. Напишите уравнение диаметра d, проходящего через точку К(1,-2) для линии .
Этапы решения :
1-й способ .
1. Определяем тип (чтобы знать, как ведут себя диаметры этой линии).
В данном случае линия центральная, тогда все диаметры проходят через центр С.
2. Составляем уравнение прямой, проходящей через две точки К и С. Это и есть искомый диаметр.
2-й способ .
1. Записываем уравнение диаметра d в виде (7`).
2. Подставив в это уравнение координаты точки К, находим зависимость между координатами вектора, сопряженного диаметру d.
3. Задаём этот вектор, учитывая найденную зависимость, и составляем уравнение диаметра d.
В данной задаче вычислять проще вторым способом.
3. . Напишите уравнение диаметра, параллельного оси абсцисс.
4. Найдите середину хорды, отсекаемой линией
на прямой x + 3y – 12 =0.
Указание к решению : Конечно, можно найти точки пересечения данных прямой и линии , а затем – середину полученного отрезка. Желание сделать так отпадает, если взять, к примеру, прямую с уравнением х +3у – 2009 =0.
Назначение сервиса . Онлайн-калькулятор предназначен для нахождения минимума функции методом Пауэлла . Решение оформляется в формате Word .Правила ввода функций:
- Все переменные выражаются через x 1 ,x 2
- Все математические операции выражаются через общепринятые символы (+,-,*,/,^). Например, x 1 2 +x 1 x 2 , записываем как x1^2+x1*x2 .
Метод Пауэлла
относится к прямым методам (методам нулевого порядка). Этим методом наиболее эффективно осуществляется минимизация функций, близких к квадратичным. На каждой итерации алгоритма поиск осуществляется вдоль системы сопряженных направлений.
Два направления поиска S
i , S
j называются сопряженными
, если S
j T ·H·S
j =0, i≠j, S
i T ·H·S
i =0, i=j.
где H - положительно определенная квадратная матрица.
Обоснование применения сопряженных направлений в алгоритмах оптимизации
. В методе Пауэлла H=▽²f(x
k) - матрица вторых частных производных. Идеи метода Пауэлла относятся к квадратичной функции f(x
).
Основная идея заключается в том, что если на каждом этапе поиска определяется минимум квадратичной функции f(x
) вдоль каждого из p (p < n) - сопряженных направлений и если затем в каждом из направлений делается шаг до минимальной точки, то полное перемещение от начала до шага с номером p сопряжено ко всем поднаправлениям поиска.
Идея использования сопряженных направлений лежит в основе ряда алгоритмов.
Пусть f(x
) - квадратичная функция и процесс минимизации начинается в точке x
0 с начальным направлением S
1 . Для удобства возьмем этот вектор единичным, т.е. (S
1) T ·S
1 =1. Тогда вектор x
1 =x
0 +λ 1 ·S
1 и длина шага λ 1 определяется из условия минимальности функции в данном направлении т.е.
.
Для квадратичной функции
, (1)
и, таким образом, оптимальное значение λ на первом шаге определяется в соответствии с соотношением
, (2)
где H=▽²f(x
k).
Из точки x
1 процесс минимизации должен осуществляться в другом сопряженном направлении S
2 и при этом
(S
2) T ·H·).
В общем случае система n линейно независимых направлений поиска S
1 , S
2 ,..., S
n называется сопряженной
по отношению к некоторой положительно определенной матрице H , если (S
i) T ·H·S
j =0, 0 ≤ i ≠ j ≤ n.
Так как сопряженные направления линейно независимы, то любой вектор в пространстве E n можно выразить через S
1 , S
2 ,..., S
n следующим образом:
где 
. (3)
Для некоторой матрицы H всегда существует, по крайней мере, одна система из n взаимно сопряженных направлений, так как сами собственные векторы матрицы H представляют собой такую систему.
Отметим, что для квадратичной функции справедливо следующее соотношение, которое потребуется в дальнейшем:
. (4)
Чтобы убедиться в его справедливости, рассмотрим матрицу 
. Умножение ее справа на H·S
k дает
,
если положить 
.
Вообще говоря, справедливо общее правило, заключающееся в том, что если используются сопряженные направления для поиска минимума квадратичной функции f(x
), то эта функция может быть минимизирована за n шагов по одному в каждом из сопряженных направлений. Более того, порядок использования сопряженных направлений несущественен.
Покажем, что это действительно так. Пусть f()=b
+H·x
.
В точке минимума ▽f(x
*), и эта точка x
*=-H T ·b
.
Заметим, что ▽ T f(x
k)·S
k =(S
k) T ·▽f(x
k).
Так как x
1 =x
0 +λ 1 ·S
1 , (5)
где λ 1 определяется в соответствии с соотношением (2):
,
затем минимум находится в следующем сопряженном направлении по аналогичным формулам i-1 +λ i ·S
i) в направлении S
i , чтобы получить λ i , что приводит к следующему выражению (на основании (2))
. (7)
Кроме того,
и (S
i) T ·▽f(x
i-1)=(S
i) T ·,
так как все (S
i) T ·H·S
k =0, ∀i≠k, 0 и H -1 ·b
через систему сопряженных векторов S
i следующим образом (по аналогии с (3)):
,
.
Подставив эти выражения в (7), получим
x
n =x
0 -x
0 +H -1 ·b
=H -1 ·b
. (9)
Таким образом, точка x
n , полученная в результате минимизации квадратичной функции на n -м шаге, совпадает с точкой минимума квадратичной функции f(x
).
Покажем, что для сопряженных направлений, если f(x
) каждый раз минимизируется в сопряженном направлении S
j в соответствии с формулой (2), то при этом выполняется следующее равенство:
(x
j) T ·▽f(x
l), 1 ≤ j ≤ l-1 ,
при использовании не более чем n направлений, то есть ▽f(x
l) ортогонален использованным сопряженным направлениям.
Для квадратичной функции ▽f( k - произвольная точка, из которой начинается поиск по сопряженным направлениям. Поскольку ▽f( k-1) T дает
.
Первый член в правой части (S
k-1) T ·▽f(x
k)=0, так как градиент в точке x
k ортогонален направлению предыдущего спуска, если точка получена в результате минимизации функции в этом направлении. Кроме того, все остальные слагаемые под знаком суммы исчезают вследствие сопряженности направлений S
k-1 и S
j , и таким образом
(S
j) T ·▽f(x
l)=0, 1≤j≤l-1 . (10)
Алгоритм Пауэлла
Переход из точки x k 0 в точку x k n на k -м шаге алгоритма Пауэлла осуществляется в соответствии с формулой:
.
При этом последовательно осуществляется минимизация исходной функции по сопряженным направлениям S k 1 , ... ,S k n . Результатом минимизации по каждому из сопряженных направлений является система параметров λ 1 k ,...,λ n k , при которых функция минимальна в каждом из сопряженных направлений:
, 
.
Начальную систему сопряженных направлений можно выбрать параллельной осям системы координат. В конце каждой итерации алгоритма Пауэлла необходимо выбрать новую систему сопряженных направлений, так как если этого не сделать, то получим простой покоординатный поиск. В основе построения новой системы лежит следующая теорема.
Теорема:
Если при начальной точке x
0 поиска в направлении вектора S
минимум функции f(x
) находится к точке x
a , а при начальной точке x
1 ≠x
0 поиск минимума функции f(x
) в том же направлении S
приводит к точке x
b , то при f(x
b) Доказательство
. Используя ранее полученные результаты (10), можно записать, что в первом случае
Второй этап начинается с минимизации вдоль направления S
1 2 , затем, если необходимо, перемещение в направлении S
1 1 . Но в случае квадратичной функции двух переменных после минимизации по двум сопряженным направлениям будет достигнута точка минимума.
Пример №1
. Методом Пауэлла найти точку минимума функции 4(x 1 -5) 2 +(x 2 -6) 2 , если задана начальная точка х (0) = (8, 9) Т.
Итерация №0
.
Шаг №1. Сделаем шаг вдоль направления поиска p 2 = T
Шаг №2. Сделаем шаг вдоль другого направления поиска p 1 = T
Шаг №3. Повторно сделаем шаг вдоль направления поиска p 2 = T Шаг №4. Выбираем сопряженное направление: p 2 = x 3 - x 1 Итерация №1
.
Пример №2
. Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при |d(x)/dx| < 10 -3 , i=1,2,..,n.
Итерация №2
. СОПРЯЖЕННЫЕ НАПРАВЛЕНИЯ
Пара направлений, исходящих из точки Рповерхности Sи таких, что содержащие их прямые являются сопряженными диаметрами индикатрисы Дюпена поверхности Sвточке Р.
Для того чтобы направления (du
: dv
),
вточке Рповерхности Sбыли С. н., необходимо и достаточно выполнения условия где L, М
и N -
коэффициенты второй квадратичной формы поверхности S,
вычисленные в точке Р.
Примеры: асимптотические направления, главные направления.
Лит.
: Погорелов А. В., Дифференциальная , 5 изд., М., 1969. Математическая энциклопедия. - М.: Советская энциклопедия
.
И. М. Виноградов
.
1977-1985
.
Раздел геометрии, в к ром изучаются геометрич. образы, в первую очередь кривые и поверхности, методами математич. анализа. Обычно в Д. г. изучаются свойства кривых и поверхностей в малом, т. е. свойства сколь угодно малых их кусков. Кроме того, в … Математическая энциклопедия
1) Сумма квадратов длин сопряженных полудиаметров эллипса есть величина постоянная, равная сумме квадратов длин его полуосей. 2) Площадь описанного вокруг эллипса параллелограмма, стороны к рого имеют сопряженные направления, постоянна и равна… … Математическая энциклопедия
Направ ление на регулярной поверхности, в к ром кривизна нормального сечения поверхности равна нулю. Для того чтобы направление в точке Рбыло А. н., необходимо и достаточно выполнение условия: где внутренние координаты на поверхности, а L, М и N… … Математическая энциклопедия
Численные методы раздел вычислительной математики, посвященный математич. описанию и исследованию процессов численного решения задач линейной алгебры. Среди задач Л. а. наибольшее значение имеют две: решение системы линейных алгебраич. уравнений… … Математическая энциклопедия
Сеть линий на поверхности, образованная двумя семействами линий такими, что в каждой точке поверхности линии сети различных семейств имеют сопряженные направления. Если координатная сеть является С. с., то коэффициент М второй квадратичной формы… … Математическая энциклопедия
СО 34.21.308-2005: Гидротехника. Основные понятия. Термины и определения
- Терминология СО 34.21.308 2005: Гидротехника. Основные понятия. Термины и определения: 3.10.28 аванпорт: Ограниченная волнозащитными дамбами акватория в верхнем бьефе гидроузла, снабженная причальными устройствами и предназначенная для размещения … Словарь-справочник терминов нормативно-технической документации
I I. История развития железных дорог. Ж. дорога, в том виде, в каком она существует теперь, изобретена не сразу. Три элемента, ее составляющие, рельсовый путь, перевозочные средства и двигательная сила прошли каждый отдельную стадию развития,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Заработная плата
- (Wages) Важнейшее средство повышения заинтересованности работников Участие трудящихся в доле вновь созданных материальных и духовных благ Содержание Содержание. > заработная плата - это важнейшее средство повышения заинтересованности… … Энциклопедия инвестора
Диверсификация
- (Diversification) Диверсификация это инвестиционный подход направленный на снижение финансовых рынков Понятие, основные методы и цели диверсификации производства, бизнеса и финансовых рисков на валютных, фондовых и сырьевых рынках Содержание… … Энциклопедия инвестора
XIII. Дела внутренние (1866—1871). 4 го апреля 1866 года, в четвертом часу дня, Император Александр, после обычной прогулки в Летнем саду, садился в коляску, когда неизвестный человек выстрелил в него из пистолета. В эту минуту, стоявший в… … Большая биографическая энциклопедия
S
T ·▽f(x
a)=S
T ·(H·x
a +b
)=0,
аналогично, во втором случае можно записать
S
T ·▽f(x
b)=S
T ·(H·x
b +b
)=0,
Вычитая из первого выражения второе получим, что
S
T ·H·(x
b -x
a)=0,
Следовательно, векторы S
и (x
b -x
a) являются сопряженными.
Эта теорема непосредственно может быть распространена на случай нескольких сопряженных направлений следующим образом. Если, начиная из точки x
0 , точка x
a определяется после использования при минимизации нескольких сопряженных направлений p (p
Рисунок.
Пусть в начальный момент для двумерной задачи поиск осуществляется из точки x
0 вдоль направлений, параллельных осям координат: S
0 1 и S
0 2 . Последовательно были найдены точки x
0 1 , x
0 2 , x
0 3 (см. рис.).
Таким образом, определили 2 сопряженных направления, в которых следует вести поиск: S
0 2 и (x
0 3 -x
0 1). В системе исходных направлений S
0 1 должно быть заменено на (x
0 3 -x
0 1), представляющее собой полное перемещение из первого минимума. Направления поиска на следующем этапе:
S
1 1 =S
0 2 ,
S
1 2 =x
0 3 -x
0 1 .
В общем случае, на k -м шаге алгоритма Пауэлла используется n линейно независимых направлений поиска. Поиск начинается с точки x
k 0 и осуществляется по следующему алгоритму:
1. Начиная с точки , в направлениях S
k 1 , ... , S
k n . При этом находятся точки x
k 1 , ... , x
k n , которые минимизируют исходную функцию в заданных направлениях, причем x
k 1 =x
k 0 +λ 1 ·S
k 1 = x
k 1 +λ 2 ·S
k 2 , ..., x
k n =x
k n-1 +λ n ·S
k n .
2. Поиск, осуществляемый на первом этапе, может привести к линейно зависимым направлениям, если, например, в одном из направлений S
i не удается найти меньшего значения функции. Поэтому 2 направления могут стать коллинеарными. Поэтому в системе сопряженных направлений не следует заменять старое направление на новое, если после такой замены направления нового набора становятся линейно зависимыми.
На примере квадратичной функции Пауэллом было показано, что при нормировании направлений поиска в соответствии с соотношением:
(S
k i)·H·S
k i =1, i=1,n
,
определитель матрицы, столбцы которой представляют собой направления поиска, принимает максимальное значение тогда и только тогда, когда S
k i взаимно сопряжены относительно матрицы H . Он пришел к выводу, что направление полного перемещения на k -м шаге должно заменять предыдущее направление только в том случае, когда заменяющий вектор увеличивает определитель матрицы направлений поиска. Так как только тогда новый набор направлений будет более эффективным.
Для такой проверки из точки x
k n делается дополнительный шаг в направлении (x
k n -x
k 0), соответствующий полному перемещению на k -м этапе и получают точку (2x
k n -x
k 0). Для проверки того, что определитель матрицы направлений поиска увеличивается при включении нового направления, делается шаг 3.
3. Обозначим наибольшее уменьшение f( k m .
Обозначим:
f 1 =f(x
k 0), f 2 =f(x
k n), f 3 =f(2x
k n -f 1 =f(x
k 0),
где x
k 0 =x
k-1 n , 
.
Тогда, если f 3 ≥f 1 и (или) (f 1 -2f 2 +f 3)(f 1 -f 2 -Δ k) 2 ≥0.5*Δ k (f 1 -f 3) 2 , то следует использовать на (k+1) -м этапе те же направления S
k 1 , ... , S
k n , что и на k -м этапе, то есть S
k+1 i =S
k i , i=1,n
, и начать поиск из точки x
k+1 0 =x
k n или из точки x
k+1 0 =2x
k n -x
k 0 =x
k n+1 , в зависимости от того, в какой точке функция принимает минимальное значение.
4. Если тест на шаге 3 не прошел, то ищется минимум f(x
) в направлении вектора S
k n+1 , проведенного из x
k 0 в x
k n: S
k n+1 =(x
k n -x
k 0). Точка этого минимума берется в качестве начальной точки на (k+1) -м этапе. А в системе сопряженных направлений сохраняются все, кроме направления S
k m , которое заменяется на новое направление S
k n+1 , но новое направление помещается в последний столбец матрицы направлений. На (k+1) -м этапе будут использоваться направления
= .
5. Критерий останова. Алгоритм прерывается, если изменение по каждой переменной оказывается меньше заданной точности по соответствующей переменной или ||x
k n -x
k 0 ||≤ε.
Решение
:
Градиент функции: 
Проверим критерий остановки: |▽f(X 0)| < ε
Вычислим значение функции в начальной точке f(X 0) = 45.
Направление поиска:
p 1 = T
p 2 = T
f(X 1) = 4(8-5) 2 +((h+9)-6) 2 → min
f(X 1) = h 2 +6h+45 → min
Найдем такой шаг h, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f"(x 1)=0):
2h+6 = 0. Получим шаг: h = -3
f(X 2) = 4((h+8)-5) 2 +((6)-6) 2 → min
f(X 2) = 4h 2 +24h+36 → min
Найдем такой шаг h, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f"(x 2)=0):
8h+24 = 0. Получим шаг: h = -3
Выполнение этого шага приведет в точку:
f(X 3) = 4(5-5) 2 +((h+6)-6) 2 → min
f(X 3) = h 2 → min
Найдем такой шаг h, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f"(x 3)=0):
2h = 0. Получим шаг: h = 0
Выполнение этого шага приведет в точку:
p 2 = T - T = [-3;0] T
Проверим критерий остановки:
|▽f(X 3)| < ε
Вычислим значение функции в начальной точке f(X 3) = 0.
Ответ: X = T
x 1 4 +2*x 2 4 +x 1 2 *x 2 2 +2*x 1 +x 2
Градиент функции
+ h
-0.5
+ h
-0.7413
+ h
+ 0.09038
+ h
+ 0.02394
+ h
+ 0.000178
+ h
+ 0.000243
-0.741
0.0904
=
-0.759
-0.4074
Ответ: X = [-0.759;-0.4074] T
▽ f(X 6) =
-0.00093
-0.0103
Проверим критерий остановки:
|▽f(X 6)|
Вычислим значение функции в новой точке f(X 6) = -1.443.
Направление поиска: p 1 = T , p 2 = T
Одно из направлений поиска p 2 = T . Заканчиваем процесс итераций.
Ответ: X = [-0.759;-0.4074] T
Е. В. Шикин.
Смотреть что такое "СОПРЯЖЕННЫЕ НАПРАВЛЕНИЯ" в других словарях:
