Примеры

Система дифференциальных уравнений

задает динамическую систему с непрерывным временем, называемую «гармоническим осциллятором». Её фазовым пространством является плоскость , где - скорость точки . Гармонический осциллятор моделирует разнообразные колебательные процессы - например, поведение груза на пружине. Его фазовыми кривыми являются эллипсы с центром в нуле.

Пусть - угол, задающий положение точки на единичной окружности. Отображение удвоения , задаёт динамическую систему с дискретным временем, фазовым пространством которой является окружность.

Быстро-медленные системы описывают процессы, одновременно развивающиеся в нескольких масштабах времени.

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

Симплекс-метод - алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 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) и начальных и краевых условий из схемы «крест».

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

Запишем дифференциальную задачу в операторной форме

LU = f , где L - один из дифференциальных операторов

U(x,y) - искомая функция удовлетворяющая дифференциальной задаче; f - входные данные (т.е. начальные и краевые условия, правые части и т.п.). Операторная форма описывает дифференциальную задачу в узлах сетки, а операторная форма описывает конечно-разностную схему на точном решении U(x,t),т.е. в конечно-разностной схеме вместо сеточных значений сеточной функции подставлены точные (неизвестные) значения искомой функции. Операторная форма конечно-разностной схемы имеет вид.

Введём норму сеточной функции, например, с помощью выражения

Определение. Конечно-разностная схема аппроксимирует дифференциальную задачу на точном решении, если какая-либо норма разности? стремится к нулю при

Определение. Конечно-разностная схема аппроксимирует дифференциальную задачу на точном решении с порядком p по времени и порядком q по пространственной переменной, если какая-либо норма разности удовлетворяет равенству

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

Устойчивость

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

Определение. Конечно-разностная схема устойчива по входным данным, если найдется такая ограниченная константа K , не зависящая от сеточных характеристик и входных данных, что выполняется неравенство (4)

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

Если во входные данные входят только начальные условия или только краевые условия, или только правые части, то говорят об устойчивости соответственно по начальным условиям, по краевым условиям или по правым частям

Определение. Конечно-разностная схема абсолютно (безусловно) устойчива, если неравенство (4) выполняется при любых значениях сеточных характеристик ф и h, т.е. на шаги сетки не накладывается никаких ограничений.

Определение. Конечно-разностная схема условно устойчива, если неравенство (4) выполняется для сеточных характеристик ф и h, на которые накладываются определённые ограничения.

Явные схемы

Рассмотрим первую начально-краевую задачу для волнового уравнения. На пространственно-временной сетке будем аппроксимировать дифференциальное уравнение одной из следующих конечно-разностных схем:

с шаблоном на рисунке 1 и

с шаблоном на рисунке 2

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

Неявные схемы

Схема (2) является неявной схемой и обладает абсолютной устойчивостью. Ее можно свести к СЛАУ с трехдиагональной матрицей, решаемой методом прогонки.

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

Откуда для искомых значений получаем следующее выражение:

Неявные схемы обычно являются устойчивыми.

1. Примеры разностных аппроксимаций.

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

w h ={x i =ih, i=0, ± 1, ± 2,…}.

Пусть u(x) – достаточно гладкая функция, заданная на отрезке . Обозначим

Разностные отношения

называются соответственно правой, левой и центральной разностными производными функции u(x) в точке x i , т.е. при фиксированном x i и при h®0 (тем самым при i®¥) пределом этих отношений является u’(x i) . Проводя разложение по формуле Тейлора, получим

u x,i – u’(x i) = 0,5hu’’(x i) + O(h 2),

u x,i – u’(x i) = -0,5hu’’(x i) + O(h 2),

u x,i – u’(x i) = O(h 2),

Отсюда видно, что левая и правая разностные производные аппроксимируют u’(x) с первым порядком по h , а центральная разностная производная – со вторым порядком. Нетрудно показать, что вторая разностная производная

аппроксимирует u’’(x i) со вторым порядком по h , причем справедливо разложение

Рассмотрим дифференциальное выражение

с переменным коэффициентом k(x) . Заменим выражение (1) разностным отношением

где a=a(x) – функция, определенная на сетке w h . Найдем условия, которым должна удовлетворять функция a(x) для того, чтобы отношение (au x) x,i аппроксимировало (ku’)’ в точке x i со вторым порядком по h . Подставляя в (2) разложения

где u i ’ = u’(x i) , получим

С другой стороны, Lu = (ku’)’ = ku’’ + k’u’,

т.е.

Отсюда видно, что L h u–Lu = O(h 2) , если выполнены условия

Условия (3) называются достаточными условиями второго порядка аппроксимации . При их выводе предполагалось, что функция u(x) имеет непрерывную четвертую производную и k(x) – дифференцируемая функция. Нетрудно показать, что условиям (3) удовлетворяют, например, следующие функции:

Заметим, что если положить a i = k(x i), то получим только первый порядок аппроксимации.

В качестве следующего примера рассмотрим разностную аппроксимацию оператора Лапласа

Введем на плоскости (x 1 , x 2) прямоугольную сетку с шагом h 1 по направлению x 1 и с шагом h 2 по направлению x 2 , т.е. множество точек

w h = {(x i 1 , x j 2) | x i 1 = ih 1 , x j 2 = jh 2 ; i, j = 0, ± 1, ± 2,…},

и обозначим

Из предыдущих рассуждений следует, что разностное выражение

аппроксимирует дифференциальное выражение (4) со вторым порядком, т.е. L h u ij – Lu(x i 1 , x j 2) = O(h 2 1) + O(h 2 2). Более того, для функций u(x 1 , x 2), обладающих непрерывными шестыми производными, справедливо разложение

Разностное выражение (5) называется пятиточечным разностным оператором Лапласа , так как оно содержит значения функции u(x 1 , x 2) в пяти точках сетки, а именно в точках (x 1 i , x 2 j), (x 1 i ± 1 , x 2 j), (x 1 i , x 2 j ± 1). Указанное множество точек называется шаблоном разностного оператора. Возможны разностные аппроксимации оператора Лапласа и на шаблонах, содержащих большее число точек.

2. Исследование аппроксимации и сходимости

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

(k(x) u’(x))’ – q(x) u(x) + f(x) = 0, 0 < x < l, (1)

– k(0) u’(0) + b u(0) = m 1 , u(l) = m 2 , (2)

k(x) ³ c 1 > 0, b ³ 0,

для которой интегро-интерполяционным методом была построена разностная схема

Обозначим через Lu(x) левую часть уравнения (1) и через L h y i – левую часть уравнения (3), т.е.

Пусть u (x) – достаточно гладкая функция и u (x i) – ее значение в точке x i сетки

w h = {x i = ih, i = 0, 1, …,N, hN = l} (7)

Говорят, что разностный оператор L h аппроксимирует дифференциальный оператор L в точке x=x i , если разность L h u i – L h u (x i) стремится к нулю при h®0. В этом случае говорят также, что разностное уравнение (3) аппроксимирует дифференциальное уравнение (1).

Чтобы установить наличие аппроксимации, достаточно разложить по формуле Тейлора в точке x=x i значения u i ± 1 = u (x i ± h) , входящие в разностное выражение L h u i . Большая часть этой работы проделана в предыдущей главе, где показано, что при условиях

(8)

выполняется соотношение

Рассмотрим дифференциальную задачу в операторной форме (2.1) и операторную форму конечно-разностной схемы (2.3).

Введем норму сеточной функции с помощью выражения

Определение 3. Конечно-разностная схема (2.3) аппроксимирует дифференциальную задачу на точном решении, если какая-либо норма разности (не обязательно в виде (2.9)) стремится к нули при:

Определение 4. Конечно-разностная схема (2.3) аппроксимирует дифференциальную задачу на точном решении с порядком p по времени и порядком q по пространственной переменной, если какая-либо норма разности удовлетворяет равенству

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

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

Для нахождения порядка аппроксимации используется аппарат разложения в ряды Тейлора точных (неизвестных, но дифференцируемых) решений дифференциальной задачи в узлах сетки (подчеркнем: значения сеточной функции дискретны, следовательно, не дифференцируемы и поэтому не разлагаются в ряды Тейлора).

В соответствии с определением порядка аппроксимации проанализируем порядок аппроксимации конечно-разностной схемы (2.6), для чего эту схему запишем на точном решении :

(2.12)

Разложим в ряды Тейлора по переменной х значения ,в окрестности узладо четвертой производной включительно, а значение– в Тейлора по переменной t в окрестности узладо второй производной включительно, получим

(2.15)

Подставляя (2.13)-(2.15) в (2.12), находим

Таким образом,

т. е. явная схема (2.6) для уравнения теплопроводности имеет первый порядок аппроксимации по времени и второй - по пространственной переменной. Аналогично, тот же порядок аппроксимации можно получить и для неявной схемы (2.8).

Определение 5. Решение , полученное с помощью конечно-разностной схемы (2.3), сходится к точному решению U, если какая-либо норма разностистремится к нулю при стремлении к нулю сеточных характеристик:

Определение 6. Конечно-разностная схема (2.3) имеет p-й порядок сходимости (порядок точности) по времени и q-й порядок сходимости по пространственной переменной, если какая-либо норма разности удовлетворяет равенству

Таким образом, порядок сходимости (порядок точности) характеризует близость конечно-разностного и точного (неизвестного) решения.

2.1.3 Исследование устойчивости конечно-разностных схем

Пусть в конечно-разностной схеме (2.3) входные данные получили возмущения и приняли значения. Тогда сеточная функциятакже получит возмущение и примет значение

Определение 7. Конечно-разностная схема (2.3) устойчива по входным данным, если найдется такая ограниченная константа не зависящая от сеточных характеристики входные данные, что выполняется неравенство

Таким образом, понятие устойчивости интерпритируется следующим образом: конечно-разностная схема устойчива, если для малых возмущений входных данных (начально-краевых условий и правых частей) конечно-разностная схема (2.3) обеспечивает малые возмущения сеточной функции , т.е. решение с помощью конечно-разностной схемы находится под контролем входных данных.

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

Определение 8. Конечно-разностная схема (2.3) называется абсолютно устойчивой, если неравенство (2.17) выполняется при любом соотношении шагов и.

Определение 9. Конечно-разностная схема (2.3), неустойчивые при любом соотношении шагов иназываются абсолютно неустойчивыми.

Определение 10. Конечно-разностная схема (2.3) называется условно устойчивой, если неравенство (2.17) выполняется для сеточных характеристик и, на которые накладываются определенные ограничения.

Поскольку устойчивость является одной из основных характеристик конечно-разностных схем, то в данном параграфе рассматриваются различные методы исследования устойчивости конечно-разностных схем по начальным условиям. Наиболее распространенными методами исследования устойчивости являются следующие:

Метод гармонического анализа (Фурье);

Принцип максимума;

Спектральный метод;

Энергетический метод.

Каждый из этих методов имеет достоинства и недостатки.

Метод гармонического анализа. Из математической физики известно, что решение начально-краевых задач представляется в виде следующего ряда:

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

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

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

Если разложить значение сеточной функции в ряд Фурье по собственным функциям:

где амплитудная часть может быть представлена в виде произведения

Un - размерный и постоянный сомножитель амплитудной части, а k - показатель степени (соответствующий номеру временного слоя) сомножителя, зависящего от времени, то, подставив (2.18) в конечно-разностную схему, можно по модулю оценить отношение амплитудных частей на соседних временных слоях.

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

Таким образом, если конечно-разностная схема устойчива по начальным данным, то

т. е. условие (2.21) является необходимым условием устойчивости.

Исследование устойчивости методом гармонического анализа явной и неявной схем для уравнения теплопроводности. Подставим выражения (2.20) в явную конечно-разносную схему (2.6) для уравнения теплопроводности, получим

Здесь использована формула, вытекающая из формулы Эйлера:

и формула , причем, посколькуи.

В соответствии с (2.22) получаем выражение

, ,

или, с учетом (2.21), неравенство

Отсюда получаем следующие два неравенства:

из которых правое выполнено всегда, а из левого следует знаменитое условие устойчивости Куранта:, или более жесткое дляусловие

Из (2.23) следует, что явная схема для уравнения теплопроводности условно устойчива с условием (2.23), накладываемым на сеточные характеристики и h.

Подставим теперь гармоники (2.20) в неявную конечно-разностную схему (2.8) для уравнения теплопроводности, получим

,

всегда, так как а и квадрат синуса больше нуля.

Следовательно, неявная схема для уравнения теплопроводности абсолютно устойчива, так как для выполнения неравенства на сеточные характеристикии h не накладывалось никаких ограничений.

Комплекс называют числом Куранта для уравнения теплопроводности.

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

Для его использования рассмотрим явную конечно-разностную схему (2.6) для уравнения теплопроводности в форме

и введем норму сеточной функции в виде.

Тогда из (2.24) получим

то из (2.25) имеем неравенство

откуда, продолжая цепочку неравенств вплоть до начального условия, получим

где - начальное условие из (1.18).

Неравенства (2.27) в вычислительной математике называют принципом максимума. Он является достаточным условием устойчивости явной схемы (2.24) для уравнения теплопроводности.

Таким образом, если выполнено условие Куранта (2.26), то из цепочки (2.27) видно, что значение сеточной функции на любом временном слое по норме не превысит начального условия, т. е. рассматриваемая схема устойчива по начальному условию, причем условие (2.26) является теперь не только необходимым в соответствии с методом гармонического анализа, но и достаточным.

Спектральный метод исследования устойчивости. Рассмотрим сеточные функции и,, на двух временных слояхии представим конечно-разностную схему в следующей операторной форме:

где S - оператор перехода от слоя tk к слою tk+1. Такой оператор можно построить не для всякой конечно-разностной схемы

(например, метод прогонки нельзя представить в форме (6.64)). Для явных конечно-разностных схем (2.6) оператор S представляется следующей матрицей перехода:

.

Составим от левой и правой частей равенства (2.28) операцию нормы и используем свойство нормы: норма произведения операторов не превышает произведения норм, получим

Если выполнено неравенство вида

то из условий (2.29) и (2.30) следует принцип максимума

Таким образом, если схема устойчива, то норма оператора перехода S не превышает единицы и, следовательно, условие (2.30) является необходимым условием устойчивости конечно-разностных схем.

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

Для понимания энергетического метода рассмотрим применение его с целью исследования устойчивости конечно-разностных схем при численном решении следующей первой начально-краевой задачи для уравнения теплопроводности с однородными краевыми условиями:

T > 0; (2.31)

X = 0, t > 0; (2.32)

X = 1, t > 0; (2.33)

T = 0; (2.34)

На сетке (2.2) будем аппроксимировать эту задачу с помощью явной (2.6) и неявной (2.8) конечно-разностных схем, записанных в векторно-операторной форме следующим образом:

где конечно-разностный оператор аппроксимирует дифференциальный оператор по пространственной переменной x, т.е.

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

, (2.37)

и, следовательно, с нормой

. (2.38)

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

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

Для двух сеточных функций и(двух элементов гильбертова пространства HA) на различных сетках с шагами hn и hm понятие полноты означает, что при измельчении сетки, т. е. при(или) последовательностиисходятся к одному и тому же пределу, т. е. выполняется (2.39).

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

Определение 11. Конечно-разностный оператор А* называется сопряженным оператору А, если выполняется равенство

Например, если оператор А - симметрическая матрица с действительными элементами (А = АТ), то А - сопряженный оператор (это можно проверить непосредственно).

Определение. Конечно-разностный оператор А называется самосопряженным, если выполняется равенство

Определение 12. Конечно-разностный оператор А называется положительно определенным или положительно полуопределенным

на гильбертовом пространстве сеточных функций , если

Можно показать, что разностный оператор является самосопряженным, т. е.

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

Собственные функции должны удовлетворять следующим условиям:

быть ортогональными на отрезке при, т. е.напри;

удовлетворять однородным краевым уравнениям (2.32), (2.33);

их число должно совпадать с числом собственных значений .

Таким условиям удовлетворяют функции:

Для нахождения собственных значений подставим (2.44) в (2.43), получим

Из (2.45) видно, что все собственные значения оператора А отрицательны, а собственные значения оператора положительны, т. е. операторположительно определен.

При исследовании устойчивости явной конечно-разностной схемы (2.35) энергетическим методом воспользуемся следующими тождествами:

Умножим скалярно явную схему (2.35) на вектор , получим

или, после подстановки сюда тождеств (2.46),

В силу самосопряженности оператора А и коммутативности скалярного произведения, последние два слагаемых сокращаются, после чего получим следующее энергетическое тождество:

Если оператор

то из (2.47) получаем следующее энергетическое неравенство:

откуда сразу следует принцип максимума

являющийся достаточным условием устойчивости.

Если теперь от неравенства (2.48) вычислить любую норму , например норму, которая равна максимальному по модулю собственному значению оператора А, то с использованием выражения (2.45) получим

Таким образом, условие устойчивости Куранта (2.33) явной конечно-разностной схемы для уравнения теплопроводности, выведенное с помощью метода гармонического анализа, является и достаточным условием.

Исследуем теперь устойчивость неявной конечно-разностной схемы (2.36) энергетическим методом, для чего к тождествам (2.46) добавим тождество

(2.51)

Умножим скалярно схему (2.36) на вектор , получим

Таким образом, для неявной схемы энергетическое тождество имеет вид

Здесь первое слагаемое всегда положительно определено, поэтому энергетическое неравенство имеет вид

откуда следует принцип максимума

Таким образом, неявная схема (2.36) безусловно устойчива, так как оператор всегда положительно определен.

УДК 519.248:

МЕТОДЫ СЕТОЧНОЙ АППРОКСИМАЦИИ СЛОЖНЫХ СИСТЕМ СОБЫТИЙ

О.Ю. Воробьев, О.Ю. Тарасова, А.Н. Овсянникова

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

Введение

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

Постановка задачи

Существо сеточного метода состоит в следующем: вместо исходного пространства элементарных событий вводится его сеточный аналог. Эта сеточная модель описывается вероятностями, которые определены только на событиях сетки. Неизвестные распределения, т.е. законы, в соответствии с которыми эволюционирует пространство элементарных событий, заменяется соответствующими сеточными аналогами. В итоге исходная задача заменяется, или, как говорят, аппроксимируется системой сеточных распределений - сеточной схемой. Другими словами, на аппроксимируемое множество событий «набрасывается сетка» с целью попытаться представить, как ведут себя «неизвестные» события из аппроксимируемого множества в пределах «известных ячеек», роль которых будет предоставлено исполнять событиям-терраскам, образующим сетку.

Основные понятия эвентологии и теории вероятностей

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

Определение 1.1. Вероятностным пространством называется тройка (С1, 7% Р), где О -пространство элементарных событий, Т7 - алгебра событий и Р - вероятность, определенная на элементах алгебры Р - случайных событиях х,у,...еР.

Определение 1.2. Конечное множество избранных событий ЛгeF, выбранных из алгебры вероятностного пространства (О, Р, Р) и состоящее из ^У = |х| событий, называется множеством случайных событий.

Определение 1.3. Множество случайных событий X порождает различные наборы так называемых событий-террасок, среди которых есть события-терраски для 1сХ в форме пересечения: 1ег(Х)= Р|х Р)*с.

Определение 1.4. Два случайных события х, у е X (х Ф 0, у ф 0) называются вложенными, если между ними возможны только два отношения

то есть одно из этих событий вложено в другое: X С у ИЛИ V С Л".

Сетка событий, или эвентологическая сетка (Э-сетка)

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

Определение 2.1. Эвентологическая сетка (Э-сетка) - это множество 5 с/7 непересекаю-щихся случайных событий, выбранных из алгебры Р вероятностного пространства (О, Р, Р) и образующих разбиение пространства элементарных событий О..

Э-сетка 5 (сеточное множество случайных событий 5, сеточное эвентологическое распределение множества 5) определена тогда и только тогда, когда:

1) выбрано множество БаР непересекакмцихся случайных событий, образующих разбие-

2) задан набор вероятностей <7(5) = Р(«), 5 е

Для «одномерной» задачи простейшим примером Э-сетки является равновероятное разбиение пространства элементарных событий на N равновероятных событий, вероятность которых равна МЫ (равновероятная Э-сетка). Равновероятные события Э-сетки называются Э-террасками сетки (Э-узлами сетки), а их вероятности называют также Э-шагами сетки. Совокупность Э-террасок образует множество событий, где определены Э-сеточные распределения.

Определение 2.2. Эвентологической сеткой п-го порядка 8" пространства элементарных событий О называется пересечение по Минковскому разбиений А1,..., Ап с Р:

Несмотря на кажущуюся простоту, вопрос о выборе Э-сетки заслуживает внимания. С одной стороны, количество событий-террасок желательно брать большим, т.е. пользоваться мелкими, подробными Э-сетками. Точнее передавая при этом область изменения Э-аргумента, мы интуитивно рассчитываем лучше аппроксимировать искомое Э-распределение сеточными распределениями. С другой стороны, практические соображения, и в первую очередь ограниченность быстродействия и объема памяти компьютеров, заставляет обращаться к Э-сеткам со сравнительно небольшим числом Э-террасок. Решением этой проблемы часто служат неравновероятные Э-сетки. Если имеется информация об Э-распределении, например, известно «расположение» в пространстве элементарных событий некоторых его особенностей, для «разрешения» которых необходима мелкая Э-сетка, то можно, не увеличивая общего числа террасок, сгустить сетку в «окрестности» этих особенностей, а в «гладкой» области распределения сетку сделать редкой.

Определение 2.З.. X - аппроксимирующим 5” -сеточным отображением называется отображение ср: Б" -» 2х, которое на Э-ячейке

Определение 2.4. - аппроксимацией множества событий X называется множество со-

Элементы Э-сетки - события-терраски вида

Называются Э-ячейками Э-сетки б1”. Ясно, что

Э-ячейки образуют разбиение пространства элементарных событий О. Таким образом, Э-сетка имеет вид:

<Р(-ІСГ{а".а"]^(ХЄХ: *П%>..а«}*0Ь

которое сокращенно обозначается

где каждое событие

Xф ={хф:1б!}

называется 5” -аппроксимацией события хе X . Событие-терраску будем обозначать

и!Г*(Л")= ГК П(^)С’ Х^Х

Приведем примеры X -аппроксимирующего 5 отображения с различной степенью ошибки: а

У х, у «Л X X

Г У У> 7~ х,у,г х, г X

У У> 2 г <т 0

Рис. 1. Эвентологическая сетка второго порядка V2 = {а.Ь.с,с!,г)(п)>а,[),у,д,с), аппроксимирующая исходное Э-распределение триплета событий А" = {х,у,г} с нулевой ошибкой (слева). Э-сеточная аппроксимация

Х<р -{хР"уф"г^} на э-ячейках (справа)

Рис. 2. Эвентологическая сетка второго порядка 5 = {а, Ь, с, с/, е}(п){а, /?, у, 5, е}, аппроксимирующая исходное Э-распределение триплета событий X = {х,у,г} с некоторой ошибкой (слева). Э-сеточная аппроксимация Х"г = {х‘г ^ ,х1’) на Э-ячейках (справа)

Виды Э-сеточной аппроксимации

Точность Э-сеточной аппроксимации Э-распределений определяется структурой локальной зависимости аппроксимируемого множества событий, которая характеризуется отношением структур зависимостейдвух множеств событий, участвующих в Э-сеточной аппроксимации: Э-сетки 51" и аппроксимируемого множества X .

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

Рис. 3. Эвентологическая сетка второго порядка S = {а, Ь, с, d, e}(n){a, Р, у, S, е}, аппроксимирующая исходное Э-распределение триплета событий X -{x,y,z} с наибольшей ошибкой (слева).

Э-сеточная аппроксимация X9 = {Q,Q,Q} на Э-ячейках (справа)

Определение 3.1. Множество событий X имеет локально вложенную структуру относи-

телъно Э-сетки Sn, если для любой Э-ячейки ter, - С] а" е Sn и любого события

xnter, „ =<,

{а"а) lteV..vv

т.е. либо ter | а„, содержится в л, либо не пересекается с ним.

Из этого определения следуют два свойства:

U (*ntev..v>J=teV..vv

2) события xn ter, „ _, где xe X , „равновероятны.

{a ...a } a ... a 1 1

Определение 3.2. Множество событий X имеет локально наименее пересекающуюся структуру относительно Э-сетки Sn , если для любой Э-ячейки ter , „ eSn и любого мно-

жества событий X , „ с X:

I) X (*nte^.aJ=teVv)’

2) события xn ter, „ 1, где.г е X , „равновероятны.

" {а... а } а... а 1

Определение 3.3. Множество событий X имеет локально независимую структуру относительно Э-сетки Sn, если для любой Э-ячейки ter, „ i е S" и любого множества событий

і „I „nil 1 Л()

{а...а } / {а...а }

2) события хгМег, „, где хеХ, „равновероятны,

7 {а...а) а...а 1

3) события х п 1ег{а, а„ , где х е X^ а„, независимы в совокупности.

Теорема 3.1. Эвентологическое распределение 5 й -аппроксимации множества событий X

р"р(Х)^РЦегф(Х)), ХаХ

принимает один из следующих видов:

1) для локально вложенной структуры множества событий X:

р*{х)= X р(4ег{в"...*»}>’

ХШ*г{а> а„})

2) для локально наименее пересекающейся структуры множества событий X: рф(Х)= £ ::.....Р^ег{а1„.а"}Х Х^Х\

XZ

3) для локально независимой структуры множества событий X:

р1р(Х) = £ (Р(х n ter{a, (P(ter{a, - Р(х п ter!a, дЯ)))1А"11сХ,

Х<^<р{\ег, „)

где(р(хп 1ег{£)1 вИ,)) = 1 -(1 -Р(1ег{а, аП])\1п. Доказательство. Очевидно, что

X (ter^ (X) n ter

ter . п eS V {0х ап}-

Подставляя (1) в (2), получаем

ter-(T)= IV П<^)“ =

ХЄ(р\ ter і ^ ^ а1...а"

У (xnteral v) n X У ntera\..a")

xeg>\ ter , „ хєХс XH(p\ ter 1 я

V V a ■ a) J V ° a) у

Используя полученное выражение для Хъх9 (X), получаем

1еггттег|а, ^ = п„в-,)Л 1*сп%>..«»,)

хеХ х<Ехс

или в других обозначениях

1ег"(ДГ)пкг{а, ^ = Г) (*шег{а, ^П1ег1о, ^ ,

где X = ter ,

\ х n ter, „ I - дополнение х до ter, | е S’1, а хс = Q \ .

о 1 v {а...а [ / {а...а! V

{а" . ап}! "............"V

дополнение X до П.

Таким образом, выражение под знаком суммы в (3) можно записать в виде

а саму формулу (3)

fl^ntev...."}) П (*ntev v/

рф(Х)= £ p(ter^(X)nter , a)=

I P П (^nter!a>..о»,) П (JCnteV..V>>C"

Формула (4) - эвентологическое распределение Sn -аппроксимации множества событий X , имеющего произвольную локальную структуру. Используя формулу (4), можно записать формулы для эвентологического распределения S" -аппроксимации множества событий X, имеющего локально вложенную, локально наименее пресекающуюся и локально независимую структуру.

Например, рассмотрим множество X, имеющего локально наименее пересекающуюся структуру. По определению локально наименее пересекающейся структуры, события д:пter , „ , где хеf/?(ter. , и,) не пересекаются и имеют одинаковую вероятность. Поэтому

\0 ... О (\С1 ... (I)

эвентологическое распределение S" -аппроксимации множества событий X с локально наименее пересекающейся структурой можно записать в виде:

В качестве аппроксимируемого множества X рассмотрим множество стратегий, предлагаемых компанией Артур Д. Литтл . Распределение множества стратегий неизвестно, поэтому будем использовать метод сеточной аппроксимации для нахождения этого распределения.

В классическом изложении маркетинговой модели АОЬ/ЬС принцип построения матрицы АЭЬ подсказывает вид эвентологической сетки. Пересечение двух множеств событий - четырех событий жизненного цикла отрасли и пяти событий его конкурентного положения образуют

эвентологическую сетку второго порядка.V2 = {а, Ъ, с, с1)(и){а, /3, у, 3, е}. Каждой ячейке сетки соответствует набор стратегий из множества базовых стратегий, предлагаемых специалистами АОЬ в качестве руководства к действию. Сделав предположения о локальной структуре зависимости аппроксимируемого множества стратегий А" (например, на основе анализа этих стратегий

специалистами маркетинга), получим эвентологическое распределение 52-аппроксимации множества событий X .

В работе получены следующие результаты:

1. Определены понятия эвентологической теории сеточных методов: Э-сетки, X -аппроксимирующего $п сеточного отображения, 8П -аппроксимации множества событий.

2. Определены три вида локальных структур зависимости.

3. Сформулирована и доказана теорема об эвентологическом распределении 5" -аппроксимации множества событий X для различных локальных структур зависимости этого множества.

1. Ефремов, B.C. Классические модели стратегического анализа и планирования: модель ADL/LC / B.C. Ефремов // Менеджмент в России и за рубежом. М.: Финпресс. - 1998. - № 1 (http://www.cfm.ru/press/rnanagment/1998-l/09.shtml).

2. Воробьев, О.Ю. Введение в эвентологию / О.Ю. Воробьев - Красноярск: КрасГУ, ИВМ СО РАН, 2005.-512 с.

3. http://www.r-events.narod.ru

Хс<р(\£Х - „) X ,

(а -а > а...а

где суммирование ведется по всем ter , „ <= 5”, содержащим X с X .

Применение полученных результатов

Заключение

Литература