Решение обыкновенного дифференциального уравнения. Формула Эйлера. Формула Рунге-Кута. Формула Адемса. Погрешность

1.  Решение ОДУ. Формула Эйлера. Формула Рунге-Кута. Формула Адемса. Погрешность.

Задача Коши:

у'=f(x,y)

y(x₀)= y_0.

Методы решения ОДУ: 2 класса: одно и многошаговые методы.

Рассмотрим одношаговые методы.

Метод Эйлера:

Пусть неизвестна т. (x_m,y_m) искомой кривой. Проведем прямую линию с tg угла наклона у'_m=f'(x_m,y_m) проходящею через точку (x_m,y_m). Уравнение этой прямой y=y _m= у'_m(x-x_m)= f(x_m,y_m)(x-x_m). Следующая точка приближения та, где прямая пересечет вертикаль проходящею через точку x_m+1=x_m+h.

                                 L

                    l                          у'(x)

 

у_m                                                                 у_m+1

 

             x_m                   x_m+1=x_m+h

y_m+1=y_m+ у_m'h

у_m'= f(x_m,y_m).     (1)

Решение по (1) согласуется с разложением в ряд Тейлора, вплоть до членов порядка h. Этот метод является методом Рунге-Кута 1-го порядка.

Погрешность. Ошибка ограничения e=kh2, k=const.  

Исправленный метод Эйлера:

В этом методе находится средний tg угла наклона касательной для 2-х точек (x_m,y_m) и Î (средний tg угла наклона)=(x_m+h, y_m+ hy'_m).

                                 Î

                                L1       L₂

                                 L

                    l                          у'(x)

 

у_m                                                                 у_m+1

 

             x_m                   x_m+1=x_m+h

Алгоритм:

1. с помощью метода Эйлера находим точку(x_m+h, y_m+ hy'_m), лежащую на L₁, с tg угла наклона у_m'= f(x_m,y_m).

2. в этой точке снова вычисляется tg угла наклона касательной f(x_m+h, y_m+ hy'_m) и проводится прямая L₁.

3. усреднение этих tg-ов дает Î, tg ее угла наклона= 1/2[f(x_m,y_m)+f(x_m+h, y_m+ hy'_m)]  (2)

4. через т. (x_m,y_m) проводим прямую // Î. Уравнение этой прямой: y- y_m= Ф(x_m,y_m,h) (x_m,y_m).

Точка в которой L пересечет вертикаль, проходит через точку x_m+1= x_mh, и будет искомой (x_m+1,y_m+1).

y_m+1= y_m+hФ(x_m,y_m,h). (3).

Формула Рунге-Кута.

y_m+1= y_m+hФ(x_m,y_m,h), где Ф(x_m,y_m,h)=а₁f (x_m,y_m)+ а₂f (x_m+b₂h, y_m+ b₂hy'_m).

y'_m= f(x_m,y_m).

a_m,b_m - const.

В частности, для исправленного метода Эйлера: a_m=1/2, b_m=1.

2.  Вариационное исчисление. Симплекс-метод - определение. Критерий оптимальности. Алгоритм.

Основной метод ЛП - СМ, разработанный для специальной задачи в канонической форме:

c'x→max, Ax=b, x≥0. (1)

ЦФ - maxимизируется, а все переменные имеют ограничения.

Введем обозначения:

J={1,…,n} - множество индексов переменной x_j.

I= {1,…,m} - множество #-ов основных ограничений.

a_j= Є R^m 

- j-ый столбец матрицы А. Вектор х Є R^m - базисный план (1), . если он удовлетворяет всем ограничениям задачи, и его переменные разбиты на 2 группы: 1. базисные: x_j1,… x_jm.; и 2. не базисные x_j, j Є J_h=J\J_Б. Причем: 1. x_j=0, j Є J_h.; 2. aj, jЄJ_Б - линейно независимы в R^m. 3. Если составить матрицу А_Б= (a_j, jЄJ_Б), то det А_Б≠0. Эта матрица называется базисной.

Критерий оптимальности: Пусть известен БП (x_j, J_Б), тогда: ∆н≥0 - достаточно, а для невыражденного БП необходимо для его оптимальности.

Достаточно: пусть ∆н= х_н - х_н ≥0., х_н ≥0, х_н =0. Тогда: с'х - c'x, для всех х _ЄХ, х - оптимум.

Необходимо: Пусть х -ОБ и невырожденный план → х_Б >0.

Предположим противное, т.е. существует j₀ЄJ_н: ∆j₀<0.

Построим вектор приращений ∆х с.о.: пусть ∆х_j=0, j Є J_h\r₀, а ∆х_j0= Θ≥0.

Базисные компоненты приращений подбирают т.о. что бы оставалось А∆х=0 и ∆х_Б= -А^-1_БА_н∆х_н.

При выполнении этих условий вектор ∆х будет удовлетворять основным ограничениям задачи (1). →

∆х_Б= - ΘА^-1_БА_нaj_0. Построим вектор х_н = х+∆х.

Θ можно подобрать т.о., ч.б. вектор х был планом задачи, т.е. х>0.

Тогда, план х лучше х, т.е. получаем противоречие с оптимальностью х.

Алгоритм:

Пусть имеется объект, поведение которого надо оптимизировать.

1.  изучение и описательное регулирование.

а) изучение структуры объекта.

б) изучение основных способов функционирования составных частей.

в) выясняют цель оптимизации.

г) собирают конкретную цифровую информацию о структуре функции и цели объекта.

2. Математическое моделирование.

а) построение неизвестных параметров х₁,…,х_n, которые однозначно описывают поведение объекта изменением которых можно выполнить достижение цели.

б) запись основных связей и закономерностей функционирования объекта с помощью введенных неизвестных х_j и мат. операций. В результате приходим к системе ограничений на х_j. В совокупности все эти ограничения и задают множество планов Х, а именно: вектор х т.т.т. является планом, есди он удовлетворяет всем ограничениям одновременно.

в) запись с помощью неизвестных и мат. операций ЦФ f(x).

После чего, мы приходим к задаче в форме (1).

3. Теоретическое исследование и выбор метода, вкл. в себя:

а) выяснение к какому классу задач оптимизации относится наша.

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

4. Построение ОП.

а) выясняем им-ся ли программа реализации нашего метода: Да- то используем; Нет- строим свою.

б) вводим в программу числовые параметры конкретной задачи.

5. Исследование. Сравнивается полученный ОП с реальным поведением объекта. Если есть возможность, то проводим эксперимент.

Если решение нас не удовлетворяет, то процесс решения задачи оптимизации может быть улучшен на всех этапах 1-4. При решении задачи оптимизации, возможны ошибки погрешности во всех 5 пунктах.

3. Принцип Лагранжа снятия ограничений для задач с ограниченными равенствами.

По параметрам задачи c'x→max, Ax=b, x≥0, вводим функцию Лагранжа.

F(x,λ)= λf(x)+ Σλ_ig_i(x)= λ₀f(x)- x₀λ(x) - обобщенная функция Лагранжа.

F(x,λ)= f(x)+ λ'g(x).

λ=λ_{i -} множители Лагранжа.

λ - обобщенный λ - классический вектор Лагранжа.

F(x,λ)_λ0=1 = F(x,λ).

Обобщенное правило Лагранжа: если Х⁰ - ЛОП, тогда существует такой обобщенный вектор Лагранжа λ⁰, λ⁰≠0. .

Из числа задач 1 можно выделить такой подкласс, который с одной стороны является достаточно широким, ему принадлежат практически все задачи возникающие в приложениях, а с другой стороны, для которых правило Лагранжа справедливо в классической форме (λ⁰₀=1).  

Обобщенное и классическое правило Лагранжа вместе образуют т.н. принцип Лагранжа снятия ограничений, согласно которого ОП и ЛОП задачи (1) следует искать среди решений системы  и системы .