Реферат: Методы спуска - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Методы спуска

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 142 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы




Методы спуска

Общая схема.

Все методы спуска решения задачи безусловной минимизации различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Это позволяет написать общую схему методов спуска.

Решается задача минимизации функции (x) на всём пространстве En. Методы спуска состоят в следующей процедуре построения последовательности {xk}. ? качестве начального приближения выбирается любая точка x0En. Последовательные приближения x1, x2, … строятся по следующей схеме:

  1. в точке xk выбирают направление спуска - Sk;

  2. находят (k+1)-е приближение по формуле xk+1=xk-pkSk.

Направление Sk выбирают таким образом, чтобы обеспечить неравенство (xk+1)<(xk) по крайней мере для малых значений величины pk. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

Число pk определяет расстояние от точки xk до точки хk+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины k - это обеспечить выполнение неравенства (xk+1)<(xk). Одним из элементарных способов выбора шага является способ удвоения шага.

Выбирают k=k-1. Если при этом (xk+1)<(xk), то либо переходят к следующей (k+2)-й итерации, либо выбирают k=2k-1. Если значение (х) меньше его предыдущего значения, то процесс удвоения можно продолжать до тех пор, пока убывание не прекратится. Если (xk+1)(xk), то выбирают k=0.5k-1. Если (xk-0.5k-1Sk)<(xk), то полагают xk+1=xk-0.5k-1Sk и переходят к следующей (k+2)-й итерации. Если же (xk-0.5k-1Sk)(xk), то выбирают k=0.25k-1 и т.д.

Метод градиентного спуска.

Одним из самых распространённых методов минимизации, связанных с вычислением градиента, является метод спуска по направлению антиградиента минимизируемой функции. В пользу такого выбора направления спуска можно привести следующие соображения. Поскольку антиградиент, то есть ’(xk) в точке xk указывает направление наискорейшего убывания функции, то естественным представляется сместиться из точки xk по этому направлению.

Метод спуска, в котором Sk=’(xk), называется методом градиентного спуска.

Величина k в методе градиентного спуска традиционно вычисляется путём применения одного из методов одномерной минимизации функции ()=(xk-’(xk)), что не исключает применение и других способов отыскания k.

Если в качестве k выбирают точку одномерного минимума функции ()=(xk-Sk) релаксационный процесс называется методом наискорейшего спуска: xk+1=xk-k’(xk), k=arg min {()=(xk-Sk) | 0}.

Метод покоординатного спуска.

Одним из наиболее простых способов определения направления спуска является выбор в качестве Sk одного из координатных векторов e1, e2, …, en, вследствие чего у xk на каждой итерации изменяется лишь одна из компонент.

Существуют многочисленные варианты покоординатного спуска. Но в любом из этих методов выбирают в качестве -Sk то из двух направлений, +ej, -ej, которому соответствует неравенство

[’(xk), Sk] > 0.

В случае, если =0, полагают xk+1=xk и переходят к следующей итерации.

Опишем первый цикл метода, состоящий из n итераций. В произвольной точке x0 выбирают S0=e, и определяет величину 0 способом удвоения так, чтобы было (x1)=(x0-0S0)<(x0). Затем выбирают S1=e2 и, полагая =0, удвоением вычисляют 1 и так далее. При этом на каждой итерации стремятся определение величины шага методом удвоения осуществлять с наименьшим числом вычислений значений функции (х). Цикл заканчивается при k=n-1, после чего начинают следующий цикл, полагая Sn=e1 и т.д.


Практическое задание

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

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

Для нахождения минимума моей функции с помощью метода покоординатного спуска я использовал программу, представленную ниже. Входными параметрами этой программы являются координаты начальной точки (я взял х=10, y=10), начальный шаг по х и по y (я взял х=0.5 и y=0.5), а так же точность (=10-5; большую точность брать не имеет смысла, поскольку во время выполнения программы накапливается ошибка и искажает данные такой точности). Итак, взяв в качестве начальных условий эти значения я получил координаты точки минимума:

х= 1,00000977

y= 1,99999931

z=-3,00000142

Для получения результата программой было выполнено 24 итерации.


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

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

Поскольку входные параметры этой программы совпадают со входными параметрами задачи №1, то я взял их такие же, что и для первой задачи, чтобы, сравнив полученные результаты и количество итераций, необходимых для поиска минимума, я смог сделать какие-либо выводы о преимуществах и недостатках обеих задач из практики.

Итак, взяв те же начальные условия я получил следующие результаты:

x= 1,00000234

y= 2,00000119

z=-3,00000094

Количество итераций, которое потребовалось для нахождения точки минимума равно 20. Видно, что количество итераций, потребовавшееся первой программе больше, чем количество итераций, необходимых второй программе. Это следует из того, что антиградиент указывает направление наискорейшего убывания функции.

Ниже также представлен график сходимости вышеописанного процесса для моей функции и моих начальных условий.

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


1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Шел спать - прошел мимо.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по математике "Методы спуска", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru