Непосредственная аппроксимация задачи (10.1) на сеточной области
Примеры
Система дифференциальных уравнений
задает динамическую систему с непрерывным временем, называемую «гармоническим осциллятором». Её фазовым пространством является плоскость , где
— скорость точки
. Гармонический осциллятор моделирует разнообразные колебательные процессы — например, поведение груза на пружине. Его фазовыми кривыми являются эллипсы с центром в нуле.
Пусть — угол, задающий положение точки на единичной окружности. Отображение удвоения
, задаёт динамическую систему с дискретным временем, фазовым пространством которой является окружность.
Быстро-медленные системы описывают процессы, одновременно развивающиеся в нескольких масштабах времени.
Динамические системы, чьи уравнения могут быть получены посредством принципа наименьшего действия для удобно выбранной функции Лагранжа, известны как "лагранжевы динамические системы".
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.
Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.
Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый такжеполиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.
Последовательность вычислений симплекс-методом можно разделить на две основные фазы:
1. нахождение исходной вершины множества допустимых решений,
2. последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.
При этом в некоторых случаях исходное решение очевидно или его определение не требует сложных вычислений, например, когда все ограничения представлены неравенствами вида «меньше или равно» (тогда нулевой вектор совершенно точно является допустимым решением, хотя и, скорее всего, далеко не самым оптимальным). В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный.
Непосредственная аппроксимация задачи (10.1) на сеточной области
Сеточная область
t — шаг по времени, h — шаг по координате x;
— искомая сеточная функция; — значение сеточной функции, относящееся к узлу
Схема «Крест». Разностные уравнения для внутренних узлов сетки:
p = 1, 2, …, P – 1; m = 1, 2, …, M – 1. (10.2)
Аппроксимация краевых условий:
p = 1, 2, …, P.
Аппроксимация начальных условий:
m = 0, 1, …, M.
Во внутренних узлах уравнения (10.2) аппроксимируют исходное дифференциальное уравнение со вторым порядком точности. Однако в данном варианте схемы второе начальное условие аппроксимируется простейшим образом — с первым порядком точности (по t). Поэтому в целом это схема первого порядка.
Условие устойчивости численного решения — число Куранта (По поводу отмеченных фактов см. п. 10.4.–10.7). О проведении расчетов по этой схеме см. п. 10.8.
Явная схема. Шаблон схемы имеет вид:
Разностные уравнения для внутренних узлов сетки:
p = 1, 2, …, P – 1; m = 1, 2, …, M – 1. (10.3)
Начальные и краевые условия аппроксимируются как и в схеме «крест». Таким образом, данная схема состоит из уравнений (10.3) и начальных и краевых условий из схемы «крест».
Это схема первого порядка точности, но абсолютно неустойчива! Для решения конкретных задач она не используется и приводится здесь лишь как пример абсолютно неустойчивой разностной схемы.
Неявная схема (1). Шаблон схемы имеет вид:
Разностные уравнения для внутренних узлов сетки:
p = 1, 2, …, P – 1; m = 1, 2, …, M – 1. (10.4)
Начальные и краевые условия аппроксимируются также как в схеме «крест». Таким образом, данная схема состоит из приведенных здесь уравнений (10.4) и начальных и краевых условий из схемы «крест».
Это схема первого порядка точности абсолютно устойчива. Однако для решения конкретных задач она практически не используется, так как дает слишком плохие результаты. В этом можно убедиться на методических примерах этой лабораторной работы.
Неявная схема (2). Шаблон схемы имеет вид:
Разностные уравнения для внутренних узлов сетки:
(10.5)
p = 1, 2, …, P – 1; m = 1, 2, …, M – 1.
Начальные и краевые условия аппроксимируются как в схеме «крест». Таким образом, данная схема состоит из уравнений (10.5) и начальных и краевых условий из схемы «крест».
Это схема первого порядка точности по t (за счет грубой аппроксимации начальных данных, как и схема «крест»), абсолютно устойчива.