Лабораторная работа 2 Приближение функций 2 Лабораторная работа 7 Интерполяция функций. 7 Лабораторная работа 9
 Скачать 0.93 Mb.
|
Лабораторная работа № 7.Численные методы решения обыкновенных дифференциальных уравнений.Цель работы: Изучить методы решения краевых задач для обыкновенных дифференциальных уравнений первого порядка, научиться программировать алгоритмы указанных методов. Общие сведения: Пусть требуется численно решить задачу Коши для дифференциального уравнения (1) при заданном начальном условии (2) Зададим некоторый достаточно малый шаг сетки вычислений . Тогда для каждого значение искомой функции (решения задачи (1)-(2)) можно последовательно вычислить по формуле Эйлера (3) Формула Эйлера является достаточно простой для программирования, однако, ее погрешность достаточно велика и сильно зависит от величины Более точной является неявная формула Адамса  , где значение вычисляется по формуле Эйлера (3). При использовании описанных формул следует учитывать, что погрешность увеличивается с каждым шагом вычислений. Варианты заданий: 1-8. Используя формулы Эйлера и Адамса решить краевую задачу, найти значение в точке при :
Лабораторная работа №8.Методы численной оптимизации.Цель работы: освоить методы численной оптимизации. а) градиентный метод с постоянным шагом; г) метод покоординатного спуска с постоянным шагом; 1. Краткие теоретические сведения. 1.1 О численных методах многомерной оптимизации. Задача многомерной безусловной оптимизации формулируется в виде: min f(x), xÎX где x={x(1), x(2),…, x(n)} — точка в n-мерном пространстве X=IRn, то есть целевая функция f(x)=f(x(1),…,f(x(n)) — функция n аргументов. Так же как и в первой лабораторной работе мы рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {xk}, удовлетворяющих условию f(x0)>f(x1)>…>f(xn)>… . Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {xk} вычисляются по формуле: хk+1 = xk + akpk, k=0,1,2,… , где pk — направление спуска, ak — длина шага в этом направлении. Различные методы спуска отличаются друг от друга способами выбора направления спуска pk и длины шага ak вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции, относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д. 1.2. Градиентные методы. 1.2.1. Общая схема градиентного спуска. Как известно, градиент функции в некоторой точке xk направлен в сторону наискорейшего локального возрастания функции и перпендикулярен линии уровня (поверхность постоянного значения функции f(x), проходящей через точку xk). Вектор, противоположный градиенту , называется антиградиентом, который направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска pk антиградиент - в точке xk, мы приходим к итерационному процессу вида: xk+1 = xk - ak f’(xk), ak>0, k=0,1,2,… .
В координатной форме этот процесс записывается следующим образом: Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом функции, называются градиентными методами. Они отличаются друг от друга только способом выбора шага ak. Существует много различных способов выбора ak, но наиболее распространены: метод с постоянным шагом, метод с дроблением шага и метод наискорейшего спуска. 1.2.2. Градиентный метод с постоянным шагом. Основная проблема в градиентных методах — это выбор шага ak. Достаточно малый шаг ak обеспечивает убывание функции, то есть выполнение неравенства: f(xk - ak( xk))) < f(xk), но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка условия убывания на каждой итерации является довольно трудоемкой, поэтому в методе градиентного спуска с постоянным шагом задают a=ak постоянным и достаточно малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим количеством итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент ). Схема алгоритма Шаг 1. Задаются начальное приближение х0, постоянный шаг a, условия останова алгоритма e3. Вычисляется значение градиента — направление поиска. Присваивается к=0. Шаг 2. Определяется точка очередного эксперимента: хк+1 = хк - af’(xk),
или, в координатной форме: Шаг 3. Вычисляется значение градиента в точке хк+1: ,
или, в координатной форме: Шаг 4. Если ||||£e3, то поиск заканчивается, при этом: Иначе к=к+1 и переходим к шагу 2. 1.2.3. Градиентный метод с дроблением шага. В методе градиентного спуска с дроблением шага величина шага aк выбирается так, чтобы было выполнено неравенство: f(xk-ak)-f(xk)£-dak||||2, где 0 Процесс выбора шага протекает следующим образом. Выбираем число a>0, одно и то же для всех итераций. На к-й итерации проверяем выполнение неравенства при aк=a. Если оно выполнено, полагаем aк=a и переходим к следующей итерации. Если нет, то шаг aк дробим, например уменьшаем каждый раз в два раза, до тех пор, пока оно не выполнится. Схема алгоритма Шаг 1. Задаются х0, e3, d и начальное значение шага a. Вычисляется значение градиента — направление поиска. Присваивается к=0. Шаг 2. Проверяется условие: f(xk-a)£-da||||2. Если выполняется, то переходим к шагу 3, иначе дробим значение a (a=a/2) и повторяем шаг 2. Шаг 3. Определяется точка очередного эксперимента: хк+1 = хк - a. Шаг 4. Вычисляется значение градиента в точке хк+1: . Шаг 5. Если ||||£e3, то поиск заканчивается, при этом:
Иначе к=к+1 и переходим к шагу 2. 1.2.4. Метод наискорейшего спуска.
В градиентном методе с постоянным шагом величина шага, обеспечивающая убывание функции f(x) от итерации к итерации, оказывается очень малой, что приводит к необходимости проводить большое количество итерации для достижения точки минимума. Поэтому методы спуска с переменным шагом являются более экономными. Алгоритм, на каждой итерации которого шаг aк выбирается из условия минимума функции f(x) в направлении движения, то есть: называется методом наискорейшего спуска. Разумеется, этот способ выбора aк сложнее ранее рассмотренных вариантов. Реализация метода наискорейшего спуска предполагает решение на каждой итерации довольно трудоемкой вспомогательной задачи одномерной минимизации. Как правило, метод наискорейшего спуска, тем не менее, дает выигрыш в числе машинных операций, поскольку обеспечивает движение с самым выгодным шагом, ибо решение задачи одномерной минимизации связано с дополнительными вычислениями только самой функции f(x), тогда как основное машинное время тратится на вычисление ее градиента . Следует иметь в виду, что одномерную минимизацию можно производить любым методом одномерной оптимизации, что порождает различные варианты метода наискорейшего спуска. Схема алгоритма Шаг 1. Задаются х0, e3. Вычисляется градиент , направление поиска. Присваивается к=0. Шаг 2. Определяется точка очередного эксперимента: хк+1 = хк - aк,
где aк — минимум задачи одномерной минимизации: Шаг 3. Вычисляется значение градиента в точке хк+1: . Шаг 4.
Если ||||£e3, то поиск точки минимума заканчивается и полагается: Иначе к=к+1 и переход к шагу 2. 1.3.Метод покоординатного спуска. Желание уменьшить объем вычислительной работы, требуемой для осуществления одной итерации метода наискорейшего спуска, привело к созданию методов покоординатного спуска.
Пусть - начальное приближение. Вычислим частную производную по первой координате и примем:
где е1={1,0,…,0}T — единичный вектор оси х(1). Следующая итерация состоит в вычислении точки х2 по формуле: где е2={0,1,0,…,0}T — единичный вектор оси х(2) и т. д. Таким образом, в методах координатного спуска мы спускаемся по ломанной, состоящей из отрезков прямых, параллельных координатным осям.
Спуск по всем координатам составляет одну «внешнюю» итерацию. Пусть к — номер очередной внешней итерации, а j — номер той координаты, по которой производится спуск. Тогда формула, определяющая следующее приближение к точке минимума, имеет вид:
где к=0,1,2,… ; j=1,2,…n.
В координатной форме формула выглядит так: После j=n счетчик числа внешних итераций к увеличивается на единицу, а j принимает значение равное единице. Величина шага aк выбирается на каждой итерации аналогично тому, как это делается в градиентных методах. Например, если aк=a постоянно, то имеем покоординатный спуск с постоянным шагом. Схема алгоритма покоординатного спуска с постоянным шагом Шаг 1. При к=0 вводятся исходные данные х0, e1, a. Шаг 2.
Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки хkn по формуле: Шаг 3.
Если ||x(k+1)n — xkn||£e1, то поиск минимума заканчивается, причем: Иначе к=к+1 и переходим к шагу 2.
Если же шаг aк выбирается из условия минимума функции: то мы получаем аналог метода наискорейшего спуска, называемый обычно методом Гаусса — Зейделя. Схема метода Гаусса — Зейделя Шаг 1. При к=0 вводятся исходные данные х0, e1. Шаг 2.
Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки хkn по формулам:
где akn+j-1 является решением задачи одномерной минимизации функции: Шаг 3.
Если ||x(k+1)n — xkn||£e1, то поиск минимума заканчивается, причем: Иначе к=к+1 и переходим к шагу 2. Список использованной литературы.Бахвалов Н.С. Численные методы. М.: Наука, 2006. 631 с. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. 3-е изд., перераб. и доп. М.: БИНОМ. Лаборатория знаний, 2009. 632 с. Воробьев Г. Н., Данилова А. Н. “Практикум по численным методам.” - М.:”Высш. шк.”, 2007 г. -184 с. Данко П.Е. Высшая математика в упражнениях и задачах: В 2т. учеб. пособ. – М.: Высш. шк., 2008. 3. Исаков В.Н. Элементы численных методов: учеб. пособ. – М.: Академия, 2008. Коварцев А.Н. Численные методы: Курс лекций / А.Н. Коварцев. Самар. Гос. Аэрокосм. Ун-т Самара. 2000. 177 с. Протасов И.Д. Лекции по вычислительной математике: учеб. пособ. – М.: Гелиос АРВ, 2009. |