Метод спуска математика кратко
Обновлено: 08.07.2024
Для решения задачи минимизации функционала наиболее часто применяются методы спуска. При заданном приближении определяется какое-либо направление, в котором функционал убывает, и производится перемещение приближения в этом направлении. Если величина перемещения взята не очень большой, то значение функционала обязательно уменьшится.
Рассмотрим примеры методов спуска.
При исследовании сходимости метода Зейделя в случае системы уравнений при мы описали циклический метод покоординатного спуска минимизации функции : при заданном приближении отыскивается значение , при котором достигается , затем отыскивается значение , при котором достигается , и т.д. Процесс циклически повторяется.
Обозначим через приближение, получаемое при спуске из по координате . Присваивая приближению, получающемуся при спуске по очередной координате, следующий номер, можно записать приближения метода циклического покоординатного спуска в виде
При практической реализации этого метода возникает проблема минимизации функций одной переменной. Рассмотрим отдельно задачу минимизации функций одной переменной при начальном приближении к точке минимума . Так как эта задача обычно не может быть решена точно, то часто поступают следующим образом: берут некоторые значения , и строят параболу , удовлетворяющую условиям
Абсциссу точки минимума принимают за следующее приближение . Уже в одномерном случае можно построить пример, когда последовательность точек, получаемых по описываемому методу, не обязательно сходится к искомой точке экстремума функции .
Даже если на каждом шаге отыскивается абсолютный экстремум функции по соответствующей координате, то уже при может случиться, что итерационный процесс сходится не к искомой точке абсолютного экстремума, а к некоторой точке локального экстремума. На рис. 7.3.1 изображены линии Уровня такой функции и получаемые приближения. Спуск в циклическом порядке необязателен. Если из рассмотрения проводившихся ранее вычислений видно, что спуск по каким-либо координатам обеспечивает наибольшее убывание , то иногда целесообразен более частый спуск по этим координатам.
В других случаях при каждом после получения приближения выбирается некоторая совокупность координат
производятся независимые спуски по координатам этой группы исходя из приближения , т.е. находят точки . Далее вычисляется
и соответствующая минимуму точка принимается за .
Иногда номер очередной координаты, по которой осуществляется спуск, выбирается недетерминированно. В этом случае говорят о случайном покоординатном спуске.
Другой вариант метода спуска — метод наискорейшего (градиентного) спуска. Следующее приближение отыскивается в виде
(рис. 7.3.2). Значение определяется из условия
т.е. этот алгоритм опять состоит в последовательной минимизации функции одной переменной .
Как и в методе покоординатного спуска, в методе наискорейшего спуска нет необходимости полного решения вспомогательной задачи минимизации функции одной переменной. В окрестности точки своего минимума эта функция меняется мало, и тщательное нахождение ее точки минимума не приводит к существенному эффекту. В Случае метода наискорейшего спуска вопрос об объеме вычислений при минимизации вспомогательных функций одной переменной должен решаться также с учетом относительной трудоемкости вычисления значений функции и ее градиента.
Для иллюстрации решения вопроса о выборе метода рассмотрим следующую типичную задачу: решается нелинейная краевая задача для системы обыкновенных дифференциальных уравнений. В гл. 9 будет показано, что эта задача сводится к решению нелинейной системы уравнений :
обладающей следующими свойствами.
Количество операций при отыскании одного значения и при одновременном отыскании всех значений , в той же точке одинаково; обозначим его через А. Количество операций при непосредственном отыскании значений и при одновременном отыскании всех значений , в той же точке одинаково. Обозначим его через обычно .
Тогда при решении задачи методом Ньютона целесообразно вычислять производные , пользуясь приближенной формулой
Область сходимости метода Ньютона обычно невелика, поэтому по крайней мере на начальном этапе итераций целесообразно свести решение этой задачи к минимизации некоторого функционала и применить какой-либо из методов спуска. Рассмотрим простейший случай функционала
множители называемые масштабными, подбираются из условий конкретной задачи.
Пусть - полученное приближение и решено сделать спуск в направлении . Вычисляют приближенные значения производных в этом направлении:
На прямой имеем
поэтому следующее приближение определяют из условия
Отметим, что в данном случае существен вопрос о разумном выборе в в формуле (2). (По этому поводу см. § 2.16.)
Задача минимизации функции при наличии ограничений, так называемая задача условной минимизации, формулируется следующим образом. Ищется величина
При решении этой задачи возникают дополнительные трудности по сравнению с решением задачи отыскания безусловного минимума, в которой ищется
— нижняя грань по всему пространству .
Непосредственное использование многих из описанных выше методов становится невозможным, и возникает необходимость в их модификации.
В то же время задача минимизации функции при ограничениях типа (4), (5) является весьма актуальной для приложений. Например, существует целый раздел математики — линейное программирование, — занимающийся решением задачи в случае, когда — линейные функции аргументов .
Среди других методов, связанных с решением задачи (3) (5), упомянем метод штрафа. Строится последовательность функций , удовлетворяющая следующим условиям:
1) определена при всех ;
3) если существуют точки такие, что
Вместо решения исходной задачи решается задача отыскания минимума при достаточно больших .
Часто вместо первого условия на функцию требуют выполнения более слабого условия. Функция определена в точках некоторой односвязной области при приближении точки к границе области или при (в случае, когда область неограниченная).
В отдельных случаях условие 3) также несколько модифицируется. Приведем пример построения такой функции . Для этого соотношения (4), (5) записываются в таком виде, что будут определены при всех (или при всех из ).
Вводится некоторая невозрастающая функция , определенная при , такая, что . Например, можно взять
В качестве берется функция
Наличие слагаемого заставляет смещаться точку экстремума в область, где в то время как наличие слагаемого заставляет смещаться точку экстремума в область, где .
Метод штрафа обладает следующим недостатком. Оказывается, что при больших структура линий уровня , как правило, такова, что сходимость методов минимизации существенно замедляется. Искусство применения метода штрафа при решении конкретных задач состоит в удачном выборе функции такой, что при заданной близости значений нижней грани замедление скорости сходимости применяемого итерационного метода будет минимальным.
В связи с отмеченными недостатками метода штрафа разработано большое число других методов решения задачи условной минимизации (3)-(5).
В методе наискорейшего спуска в качестве направления поиска выбирается вектор, направление которого противоположно направлению вектора градиента функции ▽f(x). Из математического анализа известно, что вектор grad f(x)=▽f(x) характеризует направление наиболее быстрого возрастания функции (см. градиент функции). Поэтому вектор - grad f (X) = -▽f(X) называется антиградиентом и является направлением наиболее быстрого ее убывания. Рекуррентное соотношение, с помощью которого реализуется метод наискорейшего спуска, имеет вид Xk+1=Xk - λk▽f(xk), k = 0,1.
где λk>0 - величина шага. В зависимости от выбора величины шага можно получить различные варианты градиентного метода. Если в процессе оптимизации величина шага λ фиксирована, то метод носит название градиентного метода с дискретным шагом. Процесс оптимизации на первых итерациях можно значительно ускорить, если λk выбирать из условия λk=min f(Xk + λSk) .
Для определения λk используется любой метод одномерной оптимизации. В этом случае метод называется методом наискорейшего спуска. Как правило, в общем случае недостаточно одного шага для достижения минимума функции, процесс повторяют до тех пор, пока последующие вычисления позволяют улучшать результат.
Если пространство очень вытянуто по некоторым переменным, то образуется “овраг”. Поиск может замедлиться и идти зигзагами поперек дна “оврага”. Иногда решение невозможно получить за приемлемое время.
Еще одним недостатком метода может быть критерий остановки |▽f(Xk)| , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Пример 1 . Начиная из точки xk=(-2, 3) определите точку xk+1 методом наискорейшего спуска для минимизации функции f(x)=3x1 2 +x2 2 -x1x2-4x1 → min .
В качестве направления поиска выберем вектор градиент в текущей точке
Проверим критерий остановки |▽f(X1)| . Имеем |▽f(X1)|=20.1>0.1.
Вычислим значение функции в начальной точке f(X1) = 35. Сделаем
шаг вдоль направления антиградиента
Вычислим значение функции в новой точке
f(X2) = 3(-2 + 19λ1) 2 + (3-8λ1) 2 - (-2 + 19λ1)(3-8λ1) - 4(-2 + 19λ1)
Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции
f’(X2) = 6(-2 + 19λ1) 19 + 2(3-8λ1)( -8) – (73 - 304 λ1) – 4*19
или f’(X2) = 2598 λ1 – 425 = 0.
Получим шаг λ1 = 0.164
Выполнение этого шага приведет в точку
в которой значение градиента |▽f(X2)|=2.02>0.1, значение функции f(X2) = 0.23. Точность не достигнута, из точки делаем шаг вдоль направления антиградиента ▽f(X2).
Пример №3 . Найти максимум функции f(x) методом Коши (методом наискорейшего спуска).
f(x) = 4x1 + 2x2 – x1 2 – x2 2 + 5 → max
x 0 =[4;5]
Разработал его всем известный француз Пьер Ферма прежде всего с целью решения диофантовых уравнений в целых числах. Метод опирается на фундаментальное свойство натуральных чисел - вполне упорядоченность. Давайте с ним познакомимся, а затем рассмотрим пример решения на конкретной задаче. Поехали!
Вполне упорядоченное множество
Итак, возьмем любую последовательность натуральных чисел. Например, такую:
Это может показаться тривиальным, но у каждого из конечных подмножеств натуральных чисел есть общее свойство - их всегда можно упорядочить от минимального элемента к максимальному. То же можно сказать и обо всём множестве натуральных чисел: очевидно, что его минимальным элементом является 1.
Как обратный пример множества не допускающего вполне упорядоченность можно привести множество целых чисел. Понятно, что среди целых чисел нет наименьшего отрицательного.
Тем не менее и целые и натуральные числа - линейно упорядоченные множества, т.к. для каждой пары их элементов сравнима: 1≥-1 , 3≤5, 4≤4 и т.д. Но это так, для справки. Едем дальше
Метод бесконечного спуска
Метод разработанный Пьером Ферма как раз отпирается на приведенные выше суждения. Общая схема доказательства такова:
- предполагается существование некоего решения или справедливость утверждения;
- показывается, что из первоначальных условий можно вывести и следующее, тем или иным образом связанное с убывающими натуральными числами (например, занумерованное);
- доказывается, что этот процесс можно продолжать бесконечно, что приводит в противоречие с вполне упорядоченностью множества натуральных чисел;
- исходное утверждение оказывается неверным или не существует.
Пример решения
Данный метод лучше всего используется для доказательства отсутствия решения. Допустим, докажем отсутствие решений в натуральных числах у такого уравнения:
Предположим, что у него есть такое решение, при чем, без потери общности, положим, что z в нём - минимальное:
Понятно, что левая часть уравнения должна делиться на 3. Так как речь идёт о сумме, то и каждое слагаемое должно так же делиться на 3:
Подставим x и y, выраженное через некоторые переменные a и b в исходное уравнение:
Понятно, что 3 должно делиться на z, а значит мы можем выразить z через произвольную переменную c:
Таким образом, мы показали, что если (x,y,z) - решение нашего уравнения в натуральных числах, то для него найдется решение (x/3,y/3,z/3) - меньшее его.
Так как мы получили после преобразований то же самое уравнение, это процесс можно продолжать бесконечно, что приводит к противоречию с вполне упорядоченностью множества натуральных чисел. Следовательно, наше уравнение не имеет решения! Спасибо за внимание!
В математике, метод бесконечного спуска — это метод доказательства от противного, основанный на том, что множество натуральных чисел вполне упорядочено.
Часто метод бесконечного спуска используется для доказательства того, что у некоторого уравнения нет решений по следующей схеме. Из предположения, что решение существует, вытекает существование другого решения, которое в некотором смысле меньше. Тогда можно построить бесконечную цепочку решений, каждое из которых меньше предыдущего. Это вызывает противоречие с тем что в любом подмножестве множества натуральных чисел есть минимальный элемент, значит предположение о существовании начального решения неверно.
Метод бесконечного спуска был существенно развит Пьером Ферма.
Содержание
Примеры
Доказательство иррациональности √2
— рациональное число. Это означает, что его можно записать в следующем виде:
для некоторых натуральных чисел и . Тогда
" width="" height="" />
Это означает, что — чётное число. Пусть и
Подставляем вместо :
Делим на 2 обе части:
значит, — чётное число. Таким образом, исходные числа и можно одновременно разделить на 2 и получить другое представление " width="" height="" />
. С полученными числами можно проделать ту же операцию, и так далее бесконечное число раз. Таким образом строится бесконечно убывающая последовательность натуральных чисел, что невозможно. Значит, " width="" height="" />
не является рациональным числом. Следовательно, " width="" height="" />
иррационален.
См. также
Ссылки
- Л. Курляндчик, Г. РозенблюмМетод бесконечного спуска // Квант. — 1978. — № 1. — С. 24-27.
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое "Метод бесконечного спуска" в других словарях:
Доказательство от противного — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
Ферма, Пьер — Пьер де Ферма Pierre de Fermat Дата рождения … Википедия
Пьер Ферма — Пьер де Ферма (фр. Pierre de Fermat, 1601 1665) французский математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел. По профессии юрист, с 1631 года советник парламента в Тулузе.… … Википедия
Ферма Пьер — Пьер Ферма Пьер де Ферма (фр. Pierre de Fermat, 1601 1665) французский математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел. По профессии юрист, с 1631 года советник парламента в… … Википедия
Ферма П. — Пьер Ферма Пьер де Ферма (фр. Pierre de Fermat, 1601 1665) французский математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел. По профессии юрист, с 1631 года советник парламента в… … Википедия
Галилей Галилео — Галилео Галилей: жизнь и творчество Галилео Галилей родился в Пизе 15 февраля 1564 г. Его родители Винченцо, музыкант и коммерсант, и Джулия Амманнати. К 1581 г. относятся письменные сведения о Галилее ученике пизанской школы. Он должен… … Западная философия от истоков до наших дней
Читайте также: