Метод Эйлера. Пусть на отрезке [a; b] выбрано разбиение точками x j с шагом h:

Пусть на отрезке [ a; b ] выбрано разбиение точками x _j с шагом h:

x _j = a + jh, где h = (b-a)/N.

Рассмотрим дифференциальное уравнение первого порядка с заданным начальным условием

y^/ = f(x, y), y(a) = u ₀ (6.5)

и составим для него разностную схему (6.2)

.

Тогда

, j = 1, 2,..., N. (6.6)

Используя начальное условие (6.5), последовательно вычисляем значения неизвестной функции у в узлах x_j.

Геометрически замена производной на правую разность означает переход из точки с координатой x_j в точку, принадлежащую другой кривой из семейства решений данного дифференциального уравнения. Таким образом, по мере удаления от точки х ₀ погрешность решения увеличивается.

Для оценки погрешности докажем следующую лемму.

Лемма 6.1. Пусть задана последовательность чисел , обладающая следующими свойствами:

e ₀ =0, , i = 0, 1,..., N -1

для некоторых a> 0, b> 0. Тогда для всех k = 0, 1,..., N выполняется неравенство

. (6.7)

Доказательство. Проведем доказательство методом математической индукции.

1) Пусть k= 1. Тогда 0 = .

2) Пусть при всех k = m неравенство (6.7) справедливо. Рассмотрим k = m+ 1:

Поскольку - разложение экспоненты в ряд Тейлора, то и, заменяя (1+ a) на e ^a, получаем:

Оценим погрешность метода Эйлера. Обозначим точное решение задачи Коши через U = U(x), при этом U(a)=U₀. Тогда для него справедлива формула Тейлора:

(6.8).

Так как U ^/ – решение дифференциального уравнения, то для него справедливо равенство:

. (6.9)

Подставляя (6.9) в (6.8), получаем:

(6.10).

Найдем приближенное решение дифференциального уравнения по формуле (6.6). Обозначим погрешность решения в j -той точке через e _j = U _j - y _j. Вычтем из (6.10) (6.6):

;

.

При фиксированном j функция f является функцией одной переменной U_j, следовательно, для нее можно записать формулу конечных приращений Лагранжа:

, .

Учитывая определение e _j, получаем:

. (6.11)

Используя равенство , найдем вторую производную:

. (6.12)

Введем следующие обозначения:

; ; .

Тогда (6.12) имеет следующий вид:

.

Учитывая это обстоятельство, (6.11) можно переписать в виде:

.

Из совпадения начальных условий для точного и приближенного решений следует, что e ₀ = 0. Таким образом, последовательность e _j удовлетворяет условиям леммы 6.1 и из неравенства (6.7) следует, что

, k = 0, 1,..., N. (6.13)

Учитывая, что максимального значения (6.13) достигает при k=N и , заключаем, что погрешность метода Эйлера имеет порядок h:

.

Метод Эйлера имеет низкий порядок точности. Класс простых методов более высокого порядка можно получить из разложения y_j+1 вблизи y_j в ряд Тейлора:

Поскольку

и

,

получим

(6.14)

Точность полученной формулы на порядок превышает точность формулы Эйлера.

Для увеличения порядка точности метода Эйлера можно также использовать следующие методы.

1. Предиктор–корректор (метод 2-го порядка точности).

В каждой точке находится сначала первое приближение по методу Эйлера:

,

а затем оно уточняется:

. (6.15)

2. Усовершенствованный метод Эйлера (2-го порядка точности).

Вычисляется приближенное значение в средней точке отрезка [ x_j; x_{j+ 1}]:

,

а затем находится значение

. (6.16)

Методы одномерной минимизации

1. Метод равномерного поиска. Отрезок делится на равных частей и находится точка , в которой значение функции наименьшее

2. Метод деления интервала пополам. На каждой итерации исключается половина интервала неопределенности

3. Метод дихотомии. Интервал неопределенности делится пополам и в обе стороны от середины откладывается по .

4. Метод золотого сечения. Точка производит «золотое сечение» отрезка, если отношение длины всего отрезка к большей части, равно отношению большей части к меньшей ().

Алгоритм: 0 – положить , , вычислить . Положить k=1.

1 – если , то остановиться. Если , то перейти к 2, если , то к 3.

2 – положить . Вычислить и перейти к 4.

3 − положить . Вычислить и перейти к 4.

4 – заменить k на k+1 и перейти к 1.

5. Метод Фибоначчи. Числа Фибоначчи: Последовательность имеет вид 1, 1, 2, 3, 5, 8, 13, 21, …

Задается начальный интервал неопределенности длины и допустимая длина конечного интервала l. Находится количество вычислений N: .

,

,

.

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

7. Сравнение по скорости сокращение интервала неопределенности. Пусть длина исходного интервала равна , а – длина конечного интервала неопределенности. При заданной величине интервала , которая удовлетворяет требуемой степени точности, необходимое число вычислений функции n может быть определено, как наименьшее положительное целое, удовлетворяющее следующим соотношениям:

· метод дихотомии: ;

· метод золотого сечения: ;

· метод Фибоначчи: .

Для фиксированного значения наименьшее число вычислений целевой функции отвечает более эффективному алгоритму. С этой точки зрения наиболее эффективным является метод Фибоначчи, далее – метод золотого сечения, затем – метод дихотомии. При достаточно больших n значение , поэтому методы Фибоначчи и золотого сечения асимптотически эквивалентны.

МЕТОД ЛОМАНЫХ

Однако данный метод так же имеет ограничение, он применим для минимизации функций, удовлетворяющих условию Липшица на отрезке.

Для построения метода ломанных используются свойства липшицевых функций (см. определение 2.8 и свойства 1-5 там же).

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

Следующая точка определяется из условия . В силу линейности функции очевидно или . Далее берется новая вспомогательная функция и строится аппроксимирующая функция . Очередная точка находится из условия . Далее строятся новые функции и и точка такая, что . Итак далее (см. рис. 3.4)

Пуст точки , уже известны. Тогда составляется следующая функция и следующая точка определяется из условия

. (3.9)

Если минимум на достигается в нескольких точках, то в качестве можно взять любую из них. Метод ломаных описан.

Рис. 3.4. - график , - график , - график , - график , - график , - график , - график

Очевидно, что есть кусочно-линейная функция, график которой представляет собой непрерывную линию, состоящую из отрезков прямых с угловыми коэффициентами + L и – L.

Таким образом, на каждом шаге метода ломанных задача минимизации функции заменяется более простой задачей минимизации кусочно-линейной функции , которая приближает функцию снизу, причем монотонно возрастают.

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

Отметим, что метод ломаных не возможно реализовать без знания константы Липшица . При определении константы Липшица можно непосредственно использовать определение 2.8 и замечания 1-5, приведенные вслед за этим определением. На практике, часто для оценки минимальной константы вычисляют угловые коэффициенты некоторого числа хорд, соединяющих точки графика минимизируемой функции. Максимальный из модулей этих коэффициентов является приближением снизу к , причем тем лучшим, чем меньше эти хорды.

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

ВЫПУКЛЫЕ МНОЖЕСТВА

Пусть x, yЄЕn. Множество {z}ЄЕn точек

вида z= x+(1- )y, Є[0, 1] (1)

называется отрезком, соединяющим точки x и y.

В пространстве Еn, n 3 соотношение (1) определяет обычный отрезок, соединяющий точки х и у. Для точки z, прямой, проходящей через точки х и у, справедливо представление: z=y+ (x-y), которое отличается от (1) лишь формой записи. При =0 точки z совпадает с одним из концов отрезка (z=y), а при =1 с другим (z=x). При изменении от 0 до 1 точка z пробегает отрезок от точки у до точки х.

Определение 2:

Множество UЄEn называется вынужденным, если вместе с любыми точками ХиY Є U оно содержит и весь отрезок (1).

Очевидно, Еn – выпуклое множество.

Теорема 1: Пересечение выпуклых множествU , i=1, …, m, есть выпуклое множество, если оно содержит более одной точки.

Определение 3:

f(x), заданная на выпуклом множестве UЄEn, называется выпуклой, если для точек ХиYЄU и Є[0, 1] выполняется неравенство:

f[ х+(1- )у] f(x)+(1- )f(y) (2)

Функция f(x) называется строго выпуклой, если для всех Є(0, 1) неравенство (2) выполняется как строгое.

Теорема 2: Линейная комбинация выпуклых на выпуклом множестве U функций f (x), i= с неотрицательными коэффициентами , т.е. f(x)= , , есть выпуклая на множестве U функция.

Теорема 3: Пусть g(х) – выпуклая функция, заданная в пространстве Еn. Тогда множество U точек Х, удовлетворяющих неравенству g(х) в, выпукло.

Приведем свойства выпуклых функций, играющие важную роль в вопросах min-ии:

Теорема 1: Пусть f(x) – выпуклая на выпуклом множестве U функция. Тогда любой ее локальный минимум на множестве U является одновременно и глобальным.

Теорема 2: Глобальный min-м строго выпуклой функции f(x) на выпуклом множестве U может достигаться в единственной точке.

Наличие локальных min-ов функции f(x), не совпадающих с глобальным, сильно затрудняет поиск точки глобального min-ма f(x). Поэтому применение многих методов min-ции обосновано только для функции, не имеющих точек локального min-ма, отличных от глобального. Этим объясняется особая роль свойства выпуклости функции во многих вопросах оптимизации.

Замечание: Отметим, что не всякая выпуклая в Еn функция достигает min-го значения, даже если она ограничена снизу.

Введем класс функций, для которых min-м в Еn обязательно существует.

Определение:

Функция f(x), заданная в Еn, называется сильно выпуклой, если существует такое число > 0 ( - это константа сильной выпуклости), что для всех ХиYЄЕn и любого Є[0, 1] выполняется неравенство:

f[ x+(1- )y] f(x)+(1- )f(y)- (1- ) ||x-y||

Очевидно, сильно выпуклая функция является выпуклой и строго выпуклой.

Замечание: Можно показать, что у сильно выпуклой функции точка глобального min-ма существует и единственна.

- скалярное произведение

Для дифференцированных в Еn функций f(x) выпуклость эквивалентна выполнению неравенства

f(x) f(x ), x-x >, (1) – нестрогая выпуклость

f(x)> f(x )+< f (х ), x-x >, (2) – строгая выпуклость

f(x) f(x )+< f (х ), x-x > + ||x-х || (3) – сильная выпуклость

для любых x, x ЄЕn.

Рассмотрим графики этих функций:

а) График функции f(x) не ниже касательной плоскости z=f(x )+< f (х ), x-x >, проходящей через произвольную точку поверхности (x , f(x ))

б) График функции имеет единственную общую точку с плоскостью z

в) Предположим, что f(x) сильно выпуклая и Х* - точка ее глобального min-а. Тогда f (х*)=0 и неравенство (3) принимает вид f(x) f(x*)+ ||x-х*||

Поверхность z= f(x*)+ ||x-х*|| представляет собой параболоид вращения с вершиной в точке (x*, f(x*)). Поэтому график сильно выпуклой функции расположен внутри некоторого параболоида вращения.

Замечание:

Из неравенства (1) для выпуклой дифференциальной функции f(х) следует, что условие f (х*)=0 является не только необходимым, но и достаточным для того, чтобы х* была точкой глобального min-ма функции f(х).