Подобные работы

Интерполяция многочленами

echo "Функция у( х ) может участвовать в каких-либо физико-технических или чисто математических расчётах, где её приходится многократно вычислять. В этом случае выгодно заменить функцию у( х ) приближ

Геометрия

echo "Например, выражение: «В D ABC сторона BC равна a , а в вершине A мы помещаем массу a » означает: «Длина стороны BC равна a , , я в вершине A , равна a грамм». Если в точке A помещена масса m , т

Решение задач - методы спуска

echo "Основная задача при выборе величины b k - это обеспечить выполнение неравенства j ( x k+1 ) j (x k ) . Одним из элементарных способов выбора шага является способ удвоения шага. Выбирают b k = b

Типичные дефекты в криптографических протоколах

echo "Однако стандарты быстро устаревают, а в протоколах обнаруживаются дефекты разной степени тяжести, начиная от недостатков типа необоснованной сложности протокола и до катастрофических недостатков

Ряд Фурье

echo "Подобное колебание, называемое меандром, находит широкое применение в технике. Итак, "; echo ''; echo " Так как на практике мы не можем вычислить бесконечную сумму, проанализируем, как увеличени

Приближенное вычисление определенного интеграла при помощи квадратурной формулы Чебышева

echo "Требуется найти определенный интеграл I = "; echo ''; echo " по квадратурной формуле Чебышева. Рассмотрим, что представляет из себя вообще квадратурная формула, и как можно с ее помощью вычисли

Теория вероятностей и математическая статистика

echo "Случайные числа, распределенные по закону Стьюдента с 10 степенями свободы: "; echo ''; echo " , где x – нормальная случайная величина, а c 2 – независимая от x величина, которая распределена по

Математика

echo "Матричная запись линейной ситемы А=( Кооф .), Х=( неизв .), В=(св. чл.), =( кооф и св. члены) Невыражд . сист . |a11 a12 .. b1 .. a1m| = | кооф.| , k=| a21 a22 .. b2 .. a2m| |………………………………..| | a

Решение задач - методы спуска

Решение задач - методы спуска

Основная задача при выборе величины b k - это обеспечить выполнение неравенства j ( x k+1 ) j (x k ) . Одним из элементарных способов выбора шага является способ удвоения шага.

Выбирают b k = b k-1 . Если при этом j ( x k+1 ) j (x k ) , то либо переходят к следующей ( k+2)- й итерации, либо выбирают b k =2 b k-1 . Если значение j (х) меньше его предыдущего значения, то процесс удвоения можно продолжать до тех пор, пока убывание не прекратится. Если j ( x k+1 ) ³ j (x k ) , то выбирают b k =0.5 b k-1 . Если j ( x k -0.5 b k-1 S k ) j (x k ) , то полагают x k+1 =x k -0.5 b k-1 S k и переходят к следующей ( k+2) -й итерации. Если же j ( x k -0.5 b k-1 S k ) ³ j (x k ) , то выбирают b k =0.25 b k-1 и т.д. Метод градиентного спуска. Одним из самых распространённых методов минимизации, связанных с вычислением градиента, является метод спуска по направлению антиградиента минимизируемой функции. В пользу такого выбора направления спуска можно привести следующие соображения.

Поскольку антиградиент, то есть j ’(x k ) в точке x k указывает направление наискорейшего убывания функции, то естественным представляется сместиться из точки x k по этому направлению. Метод спуска, в котором S k = j ’(x k ) , называется методом градиентного спуска.

Величина b k в методе градиентного спуска традиционно вычисляется путём применения одного из методов одномерной минимизации функции y ( b )= j ( x k - b j ’(x k )) , что не исключает применение и других способов отыскания b k . Если в качестве b k выбирают точку одномерного минимума функции y ( b )= j ( x k - b S k ) релаксационный процесс называется методом наискорейшего спуска: x k+1 =x k - b k j ’(x k ) , b k =arg min { y ( b )= j ( x k - b S k ) | b ³ 0}. Метод покоординатного спуска . Одним из наиболее простых способов определения направления спуска является выбор в качестве S k одного из координатных векторов ± e 1 , ± e 2 , …, ± e n , вследствие чего у x k на каждой итерации изменяется лишь одна из компонент.

Существуют многочисленные варианты покоординатного спуска. Но в любом из этих методов выбирают в качестве - S k то из двух направлений, + e j , -e j , которому соответствует неравенство [ j ’(x k ), S k ] > 0. В случае, если x k+1 =x k и переходят к следующей итерации.

Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x 0 выбирают S 0 = ± e , и определяет величину b 0 способом удвоения так, чтобы было j ( x 1 )= j (x 0 - b 0 S 0 ) j (x 0 ) . Затем выбирают S 1 = ± e 2 и, полагая b = b 0 , удвоением вычисляют b 1 и так далее. При этом на каждой итерации стремятся определение величины шага методом удвоения осуществлять с наименьшим числом вычислений значений функции j (х). Цикл заканчивается при k=n-1 , после чего начинают следующий цикл, полагая S n = ± e 1 и т.д.

Практическое задание На практике нам нужно было найти минимум функции z(x)=x 2 +y 2 -xy-3y c точностью e , используя описанные выше методы.

Нахождение минимума моей функции с помощью метода покоординатного спуска. Для нахождения минимума моей функции с помощью метода покоординатного спуска я использовал программу, представленную ниже.

Входными параметрами этой программы являются координаты начальной точки (я взял х=10, y =10), начальный шаг по х и по y (я взял D х=0.5 и D y =0.5), а так же точность ( e =10 -5 ; большую точность брать не имеет смысла, поскольку во время выполнения программы накапливается ошибка и искажает данные такой точности). Итак, взяв в качестве начальных условий эти значения я получил координаты точки минимума: х= 1,00000977 y= 1,99999931 z=-3,00000 142 Для получения результата программой было выполнено 24 итерации.

Нахождение минимума с помощью метода градиентного спуска.

Программа, использованная мной для выполнения этой задачи представлена ниже.

Поскольку входные параметры этой программы совпадают со входными параметрами задачи №1, то я взял их такие же, что и для первой задачи, чтобы, сравнив полученные результаты и количество итераций, необходимых для поиска минимума, я смог сделать какие-либо выводы о преимуществах и недостатках обеих задач из практики. Итак, взяв те же начальные условия я получил следующие результаты: x= 1,00000234 y= 2,00000119 z=-3,00000094 Количество итераций, которое потребовалось для нахождения точки минимума равно 20. Видно, что количество итераций, потребовавшееся первой программе больше, чем количество итераций, необходимых второй программе. Это следует из того, что антиградиент указывает направление наискорейшего убывания функции. Ниже также представлен график сходимости вышеописанного процесса для моей функции и моих начальных условий.