Журнал вычислительной математики и математической физики, 2023, T. 63, № 5, стр. 739-759

1. ВВЕДЕНИЕ И ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

2. ЗАДАЧА (5), АЛГОРИТМ И ПОГРЕШНОСТЬ

Дискретный вариант задачи (5) имеет вид

Легко видеть, что если система неравенств

Пусть ${{t}_{k}}$ – минимальное время из дискретного набора, для которого система (14) совместна, а ${{\hat {x}}_{0}}$ – некоторое решение системы (14).

Лемма 1. Пусть $\varepsilon > 0$ выбрано так, что $\varepsilon \geqslant h(\hat {M}({{t}_{k}}),M({{t}_{k}}))$ и $\int_{{{t}_{{k - 1}}}}^{{{t}_{k}}} {{{e}^{{As}}}U{\kern 1pt} ds} \subset {{B}_{\varepsilon }}(0)$, где ${{t}_{k}}$ – минимальное время, для которого система (14) разрешима. Тогда для любого решения ${{\hat {x}}_{0}}$ задачи (14) для $i = k$ истинное решение $T$ задачи (5) удовлетворяет включению

Доказательство. Пусть ${{\hat {x}}_{0}}$ – решение (14) для $i = k$. Тогда

Как было показано выше, $T > {{t}_{{k - 1}}}$. Если $T \in ({{t}_{{k - 1}}},{{t}_{k}}]$, то из включения (16) получаем

Если $T > {{t}_{k}}$, то $M({{t}_{k}}) \subset M(T)$ и

Объединяя формулы (17) и (18), получаем, что в любом случае выполнена формула (15). Лемма 1 доказана.

Включение $\int_{{{t}_{{k - 1}}}}^{{{t}_{k}}} {{{e}^{{As}}}U{\kern 1pt} ds} \subset {{B}_{\varepsilon }}(0)$ легко проверить. Для его справедливости надо, чтобы шаг по времени $\Delta {{t}_{k}} = {{t}_{k}} - {{t}_{{k - 1}}}$ удовлетворял условию $\Delta {{t}_{k}} \leqslant \frac{\varepsilon }{{\mu \left\| U \right\|}}$, где $\mu = \mathop {\max }\limits_{s \in [0,t]} \left\| {{{e}^{{As}}}} \right\|$, а $\left\| U \right\| = \mathop {\max }\limits_{u \in U} \left\| u \right\|$.

Теорема 1. Пусть $(T,{{x}_{0}})$ – решение задачи $(5)$ и $T < + \infty $. Пусть выполнены условия $\varepsilon \geqslant h(\hat {M}({{t}_{k}}),M({{t}_{k}}))$ и $\int_{{{t}_{{k - 1}}}}^{{{t}_{k}}} {{{e}^{{As}}}U{\kern 1pt} ds} \subset {{B}_{\varepsilon }}(0)$, где ${{t}_{k}}$ – наименьшее время из дискретного набора, при котором верно $(14)$.

1. Пусть множество $M(T)$ равномерно выпуклое с модулем ${{\delta }_{{M(T)}}}$. Тогда

2. Определим $D = ({{M}_{0}} - {{x}_{0}}) \cap \partial (M(T))$ и $P = \bigcup\nolimits_{x \in D} {{{N}_{1}}(M(T),x)} $. Пусть $\delta > 0$ и ${{B}_{\delta }}(0) \subset \operatorname{co} P$. Тогда $\left\| {{{x}_{0}} - {{{\hat {x}}}_{0}}} \right\| \leqslant \frac{{2\varepsilon }}{\delta }$.

Доказательство. Доказательство повторяет доказательство теорем 1 и 2 из [17].

Прежде всего покажем, что решение $(T,{{x}_{0}})$ единственно в условиях пунктов 1 и 2 теоремы.

Пусть множество $M(T)$ равномерно=строго выпукло. Если допустить, что есть две точки ${{x}_{1}}$ и ${{x}_{2}}$, для которых ${{x}_{i}} + M(T) \supset {{M}_{0}}$, $i = 1,2$, то в силу строгой выпуклости $M(T)$ выполнено включение $\frac{{{{x}_{1}} + {{x}_{2}}}}{2} + {\text{int}}{\kern 1pt} {\kern 1pt} M(T) \ni x$ для всякой точки $x \in {{M}_{0}}$. В силу компактности ${{M}_{0}}$ имеем $\frac{{{{x}_{1}} + {{x}_{2}}}}{2} + {\text{int}}{\kern 1pt} {\kern 1pt} M(T) \supset {{M}_{0}}$. Это противоречит минимальности $T$.

Пункт 2 теоремы также гарантирует единственность решения $(T,{{x}_{0}})$. Действительно, если вектор $v \ne 0$, то найдется вектор $p \in P$ такой, что $(p,v) > 0$. От противного, если для всех $p \in P$ верно $(p,v) \leqslant 0$, то для любой выпуклой комбинации $\sum\nolimits_{i = 1}^{n + 1} {{{\lambda }_{i}}{{p}_{i}}} $ для любых ${{p}_{i}} \in P$ выполнено $\left( {\sum\nolimits_{i = 1}^{n + 1} {{{\lambda }_{i}}{{p}_{i}},v} } \right) \leqslant 0$. Отсюда $\mathop {\sup }\limits_{p \in {\text{co}}{\kern 1pt} {\kern 1pt} P} (p,v) \leqslant 0$, т.е. $0$ – граничная точка ${\kern 1pt} {\text{co}}{\kern 1pt} {\kern 1pt} P$. Получили противоречие с условием ${{B}_{\delta }}(0) \subset {\text{co}}{\kern 1pt} {\kern 1pt} P$. Итак, пусть $p \in P$ и $(p,v) > 0$. Если $x \in D$ и $p \in N(M(T),x)$, то $(p,x + v) = (p,x) + (p,v) > s(p,M(T))$. Таким образом, сдвиг множества $M - {{x}_{0}}$ на любой вектор $v \ne 0$ выходит из $M(T)$, так как $x \in M - {{x}_{0}}$ и $x + v \notin M(T)$.

1. Без ограничения общности будем считать, что ${{x}_{0}} = 0$. Фиксируем произвольное решение ${{\hat {x}}_{0}} \in {{\mathbb{R}}^{n}}$ задачи (13), (14). По лемме 1 выполнено включение (15). Это означает, что для любого $x \in D = {{M}_{0}} \cap \partial (M(T))$ выполнено включение $x - {{\hat {x}}_{0}} \in M(T) + {{B}_{{2\varepsilon }}}(0)$.

В силу предложения 3 найдутся точки ${{x}_{i}} \in D$, векторы ${{p}_{i}} \in {{N}_{1}}(M(T),{{x}_{i}})$ и числа ${{\lambda }_{i}} > 0$, $1 \leqslant i \leqslant m \leqslant n + 1$ такие, что $\sum\nolimits_{i = 1}^m \,{{\lambda }_{i}} = 1$ и $\sum\nolimits_{i = 1}^m {{{\lambda }_{i}}{{p}_{i}}} = 0$. Отсюда $\sum\nolimits_{i = 1}^m {{{\lambda }_{i}}( - {{{\hat {x}}}_{0}},{{p}_{i}})} = 0$. Следовательно, найдется индекс $i \in \{ 1, \ldots ,m\} $ такой, что $({{p}_{i}}, - {{\hat {x}}_{0}}) \geqslant 0$, ${{p}_{i}} \in {{N}_{1}}(M(T),{{x}_{i}})$, ${{x}_{i}} \in D$. Зафиксируем данное $i$ и соответствующие ${{x}_{i}}$, ${{p}_{i}}$.

Пусть ${{H}^{ + }} = \{ x \in {{\mathbb{R}}^{n}}:({{p}_{i}},x) \geqslant ({{p}_{i}},{{x}_{i}})\} $. Тогда ${{x}_{i}} - {{\hat {x}}_{0}} \in {{H}^{ + }} \cap (M(T) + {{B}_{{2\varepsilon }}}(0)) = :S$, причем гиперплоскость $\partial {{H}^{ + }} + 2\varepsilon {{p}_{i}}$ опорная ко множеству $M(T) + {{B}_{{2\varepsilon }}}(0)$ в точке ${{x}_{i}} + 2\varepsilon {{p}_{i}}$.

Итак, вписанный шар максимального радиуса во множестве $M(T) + {{B}_{{2\varepsilon }}}(0)$ с центром в сегменте $S$ имеет радиус не более $2\varepsilon $ ($2\varepsilon $ – расстояние между параллельными гиперплоскостями $\partial {{H}^{ + }}$ и $\partial {{H}^{ + }} + 2\varepsilon {{p}_{i}}$). Поэтому расстояние от ${{x}_{i}}$ до ${{x}_{i}} - {{\hat {x}}_{0}}$, т.е. $\left\| {{{{\hat {x}}}_{0}}} \right\|$, оценивается из условия $2\varepsilon \geqslant {{\delta }_{{M(T) + {{B}_{{2\varepsilon }}}(0)}}}(\left\| {{{{\hat {x}}}_{0}} - 0} \right\|)$. Пункт 1 доказан.

2. Снова, не ограничивая общности, можно считать ${{x}_{0}} = 0$. Фиксируем $\tau \in (0,1)$. Пусть ${{P}_{1}} \subset P$ – такое конечное множество, что $h(P,{{P}_{1}}) < (1 - \tau )\delta $. Тогда ${{B}_{{\tau \delta }}}(0) \subset {\text{co}}{\kern 1pt} {\kern 1pt} {{P}_{1}}$.

Пусть $L$ – грань множества ${\text{co}}{\kern 1pt} {\kern 1pt} {{P}_{1}}$, $L = {\text{co}}{\kern 1pt} {\kern 1pt} \{ {{p}_{{{{i}_{j}}}}}\} _{{j = 1}}^{J}$, ${{p}_{{{{i}_{j}}}}} \in {{P}_{1}}$. Заметим, что ${\text{co}}{\kern 1pt} {\kern 1pt} (L \cup \{ 0\} )$ есть $n$-мерная пирамида с боковыми ребрами длины 1, вершиной $0$ и основанием $L$. Определим $e = {{P}_{{{\text{aff}}{\kern 1pt} {\kern 1pt} L}}}0$, $\left\| e \right\| \geqslant \tau \delta $ (${\kern 1pt} {\text{aff}}{\kern 1pt} {\kern 1pt} L$ – аффинная оболочка $L$).

Угол $\varphi $ между векторами $e$ и ${{p}_{{{{i}_{j}}}}}$ для всякого $j = 1, \ldots ,J$ можно оценить как $\cos \varphi = \frac{{\left\| e \right\|}}{{\left\| {{{p}_{{{{i}_{j}}}}}} \right\|}} = \left\| e \right\| \geqslant \tau \delta $. Через $\angle (a,b)$ будем обозначать угол между ненулевыми векторами $a,b \in {{\mathbb{R}}^{n}}$.

Если решение задачи (13), (14) ${{\hat {x}}_{0}} \in {{\mathbb{R}}^{n}}$ удовлетворяет включению $ - {{\hat {x}}_{0}} \in {\text{cone}}{\kern 1pt} {\kern 1pt} \{ {{p}_{{{{i}_{j}}}}}\} _{{j = 1}}^{J} = \operatorname{cone} L$, то найдется такой номер $j$, $1 \leqslant j \leqslant J$, что $\angle ( - {{\hat {x}}_{0}},{{p}_{{{{i}_{j}}}}}) \leqslant \varphi $. Покажем это. Пусть $w = \{ - t{{\hat {x}}_{0}}\,|\,t \geqslant 0\} \cap \operatorname{aff} L$ и $R = \sqrt {1 - {{{\left\| e \right\|}}^{2}}} = \left\| {{{p}_{{{{i}_{j}}}}} - e} \right\|$ для любого $j$. Пусть точка $w$ – относительно внутренняя точка симплекса ${\kern 1pt} {\text{co}}{\kern 1pt} {\kern 1pt} \{ {{p}_{{{{i}_{j}}}}}\} _{{j = 1}}^{m}$, $m \leqslant n$, и ${{a}_{j}} = {{p}_{{{{i}_{j}}}}} - w$, $1 \leqslant j \leqslant m$. Так как $w$ относительно внутренняя точка, то найдутся ${{\lambda }_{j}} > 0$, $\sum\nolimits_{j = 1}^m {{{\lambda }_{j}}} = 1$, для которых $\sum\nolimits_{j = 1}^m {{{\lambda }_{j}}{{p}_{{{{i}_{j}}}}}} = w$ или $\sum\nolimits_{j = 1}^m {{{\lambda }_{j}}{{a}_{j}}} = 0$. Отсюда $\sum\nolimits_{j = 1}^m {{{\lambda }_{j}}({{a}_{j}},w)} = 0$ и, значит, найдется номер $j$, для которого $({{a}_{j}},w) \geqslant 0$. Для этого номера $j$ в треугольнике ${{p}_{{{{i}_{j}}}}}0w$ $\angle ({{p}_{{{{i}_{j}}}}} - w, - w) \geqslant \frac{1}{2}\pi $ и тем самым ${{\left\| {{{p}_{{{{i}_{j}}}}} - w} \right\|}^{2}} + {{\left\| e \right\|}^{2}} \leqslant {{\left\| {{{p}_{{{{i}_{j}}}}} - w} \right\|}^{2}} + {{\left\| w \right\|}^{2}} \leqslant 1$, т.е. $r = \left\| {{{p}_{{{{i}_{j}}}}} - w} \right\| \leqslant R$.

По теореме косинусов из треугольника ${{p}_{{{{i}_{j}}}}}0w$ косинус угла $\gamma = \angle ( - {{\hat {x}}_{0}},{{p}_{{{{i}_{j}}}}}) = \angle (w,{{p}_{{{{i}_{j}}}}})$ равен

Рассмотрим соответствующую точку ${{x}_{{{{i}_{j}}}}} \in D = {{M}_{0}} \cap \partial (M(T))$, для которой ${{p}_{{{{i}_{j}}}}} \in {{N}_{1}}(M(T),{{x}_{{{{i}_{j}}}}})$. Для краткости обозначим ${{z}_{0}} = {{x}_{{{{i}_{j}}}}}$, ${{p}_{0}} = {{p}_{{{{i}_{j}}}}}$.

Пусть ${{H}^{ + }} = \{ x \in {{\mathbb{R}}^{n}}\,|\,({{p}_{0}},x - {{z}_{0}}) \geqslant 0\} $. В силу формулы (15) точка ${{z}_{0}} - {{\hat {x}}_{0}}$ лежит между плоскостями $\partial {{H}^{ + }}$ и $\partial {{H}^{ + }} + 2\varepsilon {{p}_{0}}$, и угол между $ - {{\hat {x}}_{0}}$ и ${{p}_{0}}$ не более $\varphi $. Отсюда

Опорную функцию множества достижимости $M(t)$ для любого единичного вектора $p \in {{\mathbb{R}}^{n}}$ легко вычислить по формуле (9). Если $U$ – любое компактное множество, для которого точно вычисляется опорная функция $s(p,U)$, то функция $s(p,{{e}^{{As}}}U) = s({{e}^{{{{A}^{T}}s}}}p,U)$ точно вычисляется для каждого $s$ и является липшицевой по $s$. Поэтому проблем с ее интегрированием по отрезку $[0,t]$ не возникает. В частности, в рассмотренных ниже примерах погрешность вычисления соответствующего интеграла может быть сделана сколь угодно малой.

Замечание 1. Напомним, что во введении мы предположили, что решение задачи (5) существует и реализуется за конечное время. Достаточно, чтобы нашлось $t > 0$, для которого $M(t)\;\mathop - \limits^* \;{{M}_{0}} \ne \emptyset $.

Для строгой=равномерной выпуклости $M(T)$ достаточно, чтобы множество $U$ удовлетворяло условию: для любого единичного вектора $p \in {{\mathbb{R}}^{n}}$ опорное подмножество $({{e}^{{As}}}U)(p)$ одноточечно для п.в. $s \in [0,T]$. При этом опорное множество $M(T)(p) = \int_0^T {({{e}^{{As}}}U)(p){\kern 1pt} ds} $ одноточечно для любого $\left\| p \right\| = 1$, и, значит, множество $M(T)$ строго выпукло. При этом множество $M(T)$ не обязательно сильно выпукло. Например, для системы с нулевой динамикой $x{\kern 1pt} ' \in 0 \cdot x + U = U$, $x(0) = 0$, $U$ – строго, но не сильно выпуклый компакт (например, $U$ – шар $\ell _{\alpha }^{n}$-нормы при $\alpha > 2$).

Вопрос о модуле равномерной выпуклости $M(T)$ для конкретных матриц $A$ и множеств $U$ должен решаться отдельно и в настоящей работе не рассматривается. Отметим, что если $M(T)$ сильно выпукло с радиусом $R$, оценка $\left\| {{{x}_{0}} - {{{\hat {x}}}_{0}}} \right\|$ в п. 1 имеет порядок $\sqrt {(R + \varepsilon )\varepsilon } \asymp R\Delta $ по радиусу и мелкости сетки.

Заметим, что и для нестрого выпуклого множества $U$ (например, отрезка) множество $M(T)$ может быть строго-равномерно, но не сильно выпуклым. Соответствующий пример будет рассмотрен в приложении $2$.

В п. 2 теоремы 1 требуется выполнение включения ${{B}_{\delta }}(0) \subset \operatorname{co} P$, которое априори бывает трудно проверить. Тем не менее, если из каких-то соображений это включение установлено, то, как показано в примерах, возможно оценить погрешность алгоритма. Иногда проверить указанное условие можно после решения на сетке задачи-аппроксимации. Ниже приводится такой пример.

Пример 1. Рассмотрим пример, в котором обсудим ряд условий, позволяющих установить включение $0 \in \operatorname{int} \operatorname{co} P$ в теореме 1 по решению задачи (13). Пусть $D = \{ {{d}_{i}}\} _{{i = 1}}^{{n + 1}} \subset {{\mathbb{R}}^{n}}$ и ${{M}_{0}} = {\text{co}}D$ – полноразмерный симплекс. Допустим, что сетка $\mathbb{G}$ выбирается так, что ${{\hat {M}}_{0}} = {{M}_{0}}$. Предположим, что некоторое решение ${{\hat {x}}_{0}}$, ${{t}_{k}}$ задачи (13) удовлетворяет условиям ${{\hat {x}}_{0}} = 0$, ${{M}_{0}} \cap \partial{ \hat {M}}({{t}_{k}}) = D$. Предположим, что внутренность $M({{t}_{k}})$ содержит шар радиуса $r > 0$ и $r > 10\varepsilon $. Потребуем строгую выпуклость $M(T)$.

Определим грани ${{S}_{i}} = {\text{co}}{\kern 1pt} {\kern 1pt} (D{{\backslash }}\{ {{d}_{i}}\} )$ для всех $1 \leqslant i \leqslant n + 1$.

Тогда в обозначениях теоремы 1 по лемме 1

Действительно, найдется вектор $x \in {{\mathbb{R}}^{n}}$ такой, что выполнено включение $x + {{M}_{0}} \subset M(T)$, а значит, для всякого $i$ имеют место включения $x + {{S}_{i}} \subset M(T)$, ${{S}_{i}} + {{v}_{i}} \subset M_{k}^{'}\;\mathop - \limits^* \;{{B}_{{2\varepsilon }}}(0) \subset $ $ \subset M(T)\;\mathop - \limits^* \;{{B}_{{2\varepsilon }}}(0) \subset \operatorname{int} M(T)$. При этом, в силу непрерывности операции сложения векторов, можно выбрать ${{v}_{i}} \ne x$ и сохранить включение ${{S}_{i}} + {{v}_{i}} \subset M_{k}^{'}\;\mathop - \limits^* \;{{B}_{\varepsilon }}(0) \subset \operatorname{int} M(T)$. Следовательно, ${{S}_{i}} + (x,{{v}_{i}}] \subset \operatorname{int} M(T)$ для всех $1 \leqslant i \leqslant n + 1$. Если для некоторого $i$ точка $x + {{d}_{i}}$ является внутренней для множества $M(T)$, то найдется $\lambda \in (0,1)$ такое, что $({{S}_{i}} + \lambda {{v}_{i}} + (1 - \lambda )x) \cup $ $ \cup \;({{d}_{i}} + \lambda {{v}_{i}} + (1 - \lambda )x) \subset \operatorname{int} M(T)$. Это противоречит минимальности $T$. Утверждение $(x + {{M}_{0}}) \cap $ $ \cap \;\partial M(T) = D$ доказано. Также из строгой выпуклости $M(T)$ и замечания 1 вытекает, что $M(T)\;\mathop - \limits^* \;{{M}_{0}} = \{ x\} $. Далее можно считать $x = 0$, заменив ${{M}_{0}}$ на ${{M}_{0}} + x$.

Проанализируем множество $P = \bigcup\nolimits_{1 \leqslant i \leqslant n + 1} {{{N}_{1}}(M(T),{{d}_{i}})} $ и установим выполнение условия $0 \in \operatorname{int} \operatorname{co} P$.

В силу предложения 3 $0 \in \operatorname{co} P$. Предположим, что $0 \in \partial {\text{co}}P$. Тогда по теореме Каратеодори найдутся $n$ векторов ${{p}_{i}} \in {{N}_{1}}(M(T),{{d}_{i}})$ (без ограничения общности с номерами $1 \leqslant i \leqslant n$) таких, что $0 \in {\text{co}}\{ {{p}_{i}}\} _{{i = 1}}^{n}$. Рассмотрим ${{S}_{{n + 1}}}$. Как показано выше, это множество можно сдвинуть на вектор $v = {{v}_{{n + 1}}} \ne 0$: ${{S}_{{n + 1}}} + v \subset \operatorname{int} M(T)$. Значит, ${{S}_{{n + 1}}} + (0,v] \subset \operatorname{int} M(T)$. Так как для всякого $1 \leqslant i \leqslant n$ точка ${{d}_{i}} + v \in \operatorname{int} M(T)$, то $({{p}_{i}},v) < 0$. Тем самым для любой нетривиальной выпуклой комбинации $\sum\nolimits_{i = 1}^n {{{\lambda }_{i}}{{p}_{i}}} $ вектров $\{ {{p}_{i}}\} _{{i = 1}}^{n}$ (где ${{\lambda }_{i}} \geqslant 0$, $\sum\nolimits_{i = 1}^n {{{\lambda }_{i}} > 0} $) имеем $(\sum\nolimits_{i = 1}^n {{{\lambda }_{i}}{{p}_{i}},v} ) < 0$. Значит, выпуклая комбинация $\sum\nolimits_{i = 1}^n {{{\lambda }_{i}}{{p}_{i}}} $ не может равняться нулю. Противоречие показывает, что $0 \in {\text{int}}\,{\text{co}}P$.

Оценим теперь $\left| {T - {{t}_{k}}} \right|$. С одной стороны, $T > {{t}_{{k - 1}}}$. Для оценки $T$ сверху предположим, что $T > {{t}_{k}}$. Тогда

Условие (20) достаточно трудно для проверки и, в частности, оно может не выполняться. В реальных задачах это условие может проверяться численно. В случае $0 \in {\text{int}}U$ можно дать оценку сверху на $T$ через $\varepsilon $.

Лемма 2. Пусть $\mu = \mathop {\min }\limits_{\left\| h \right\| = 1,\;t \in [0,{{T}_{0}}]} \left\| {{{e}^{{At}}}h} \right\|$ и ${{B}_{d}}(0) \subset U$ для некоторого $d > 0$. Тогда если ${{t}_{k}} + \frac{\varepsilon }{{\mu d}} \leqslant {{T}_{0}}$, то ${{t}_{{k - 1}}} < T \leqslant {{t}_{k}} + \frac{\varepsilon }{{\mu d}}$.

Доказательство. Из определения $\mu $ получаем

Некоторые оценки типа (20) для плоского случая содержатся в приложении 1.

3. ЗАДАЧА (6), АЛГОРИТМ И ПОГРЕШНОСТЬ. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ

Рассмотрим теперь задачу (6). Напомним, что мы ищем решение $t$ на отрезке $[0,{{T}_{0}}]$. Дискретный вариант задачи (6) имеет вид

Лемма 3. Пусть ${{t}_{k}}$ – решение $(21)$, и ${{\hat {x}}_{0}}$ – некоторое решение системы $(22)$. Определим $\varepsilon > 0$ так, что $\varepsilon \geqslant h({{M}_{0}},{{\hat {M}}_{0}})$ и $\int_{{{t}_{k}}}^{{{t}_{{k + 1}}}} {{{e}^{{As}}}U{\kern 1pt} ds} \subset {{B}_{\varepsilon }}(0)$. Тогда для $i = k$ и для истинного решения $T$ задачи $(6)$ выполнено включение

Доказательство. Пусть ${{\hat {x}}_{0}}$ – решение (21) для $i = k$. С учетом равенства $M({{t}_{{k + 1}}}) = M({{t}_{k}}) + $ $ + \;\int_{{{t}_{k}}}^{{{t}_{{k + 1}}}} {{{e}^{{As}}}U{\kern 1pt} ds} \subset M({{t}_{k}}) + {{B}_{\varepsilon }}(0)$ имеем

Используя формулу (23), получаем аналогично разд. 2 следующий результат относительно погрешности $\left\| {{{x}_{0}} - {{{\hat {x}}}_{0}}} \right\|$ при условии, что ${{t}_{k}}$ – решение (21).

Теорема 2. Пусть $(T,{{x}_{0}})$ – решение задачи $(6)$ и $T < + \infty $. Пусть $\varepsilon \geqslant h({{M}_{0}},{{\hat {M}}_{0}})$ и $\int_{{{t}_{k}}}^{{{t}_{{k + 1}}}} {{{e}^{{As}}}U{\kern 1pt} ds} \subset {{B}_{\varepsilon }}(0)$, где ${{t}_{k}}$ – наибольшее время из дискретного набора, при котором верно $(22)$.

1. Пусть множество ${{M}_{0}}$ равномерно выпуклое с модулем ${{\delta }_{{{{M}_{0}}}}}$. Тогда

2. Определим $D = (M(T) + {{x}_{0}}) \cap \partial {{M}_{0}}$ и $P = \bigcup\nolimits_{x \in D} {{{N}_{1}}({{M}_{0}},x)} $. Пусть $\delta > 0$ и ${{B}_{\delta }}(0) \subset \operatorname{co} P$. Тогда $\left\| {{{x}_{0}} - {{{\hat {x}}}_{0}}} \right\| \leqslant 2\varepsilon {\text{/}}\delta $.

Замечание 2. Как и в теореме 1, решение $(T,{{x}_{0}})$ единственно. Замечание, аналогичное замечанию 1, имеет место и для теоремы 2.

Предположим, $T < {{t}_{k}}$. Тогда из включения

Лемма 4. Пусть $\mu = \mathop {\min }\limits_{\left\| h \right\| = 1,\;t \in [0,{{T}_{0}}]} \left\| {{{e}^{{At}}}h} \right\|$ и ${{B}_{d}}(0) \subset U$ для некоторого $d > 0$. Тогда ${{t}_{k}} - \frac{\varepsilon }{{\mu d}} \leqslant T < {{t}_{{k + 1}}}$.

Доказательство. Повторяет доказательство леммы 2.

Заметим, что если ${{t}_{k}} - \frac{\varepsilon }{{\mu d}} \leqslant 0$, то оценка леммы 4 не информативна, так как утверждает, что $0 \leqslant T < {{t}_{{k + 1}}}$.

Доказательство лемм 2 и 4 основано на включении (20) или (24), они доказываются при условии, что $0$ – внутренняя точка множества $U$. Однако может выполняться включение $0 \in \partial U$. В этом случае удается доказать включение (20) или (24) для некоторых конкретных видов матрицы $A$ и множества $U$. Этим вопросам посвящено приложение 1, где рассматривается ряд примеров в плоском случае.

В заключение рассмотрим, как меняется множество достижимости при изменении начальной точки и времени на их приближенные значения. Пусть $(T,{{x}_{0}})$ – истинное решение задачи (5) или (6), а $(\hat {T},{{\hat {x}}_{0}})$ – некоторое их приближение. Без ограничения общности считаем, что $T \leqslant \hat {T}$. Тогда отличие множеств достижимости системы (1) с начальными условиями $x(0) = {{e}^{{ - AT}}}{{x}_{0}}$ и $x(0) = {{e}^{{ - A\hat {T}}}}{{\hat {x}}_{0}}$ и временами $T$ и $\hat {T}$ соответственно есть (см. (4))

Таким образом, основной вклад в погрешность вносит погрешность по времени $\left| {T - \hat {T}} \right|$.

Для сильно выпуклого множества достижимости с радиусом $R$ погрешность $\left\| {{{x}_{0}} - {{{\hat {x}}}_{0}}} \right\|$ решения задач (13) и (21) имеет порядок $\sqrt {(R + \varepsilon )\varepsilon } $. В случае условия непустой внутренности (пункт 2 в теоремах 1 и 2) указанная погрешность имеет порядок $\varepsilon $.

Величина $\left| {T - \hat {T}} \right|$ в силу лемм 2 и 4 оценивается $\varepsilon {\text{/}}(\mu d)$ в обозначениях этих лемм. В случае, если точка $0$ – граничная точка множества $U \subset {{\mathbb{R}}^{2}}$ и спектр матрицы $A \in {{\mathbb{R}}^{{2 \times 2}}}$ не вещественный, получаем, что $\left| {T - \hat {T}} \right|$ имеет порядок ${{\varepsilon }^{{1/3}}}$ в случае гладкой границы $U$, когда возможно касание $0$ шаром, целиком содержащимся в $U$. В случае, когда $0$ лежит на отрезке, являющемся частью границы $\partial U$, $U \subset {{\mathbb{R}}^{2}}$, получаем, что ${\text{|}}T - \hat {T}{\text{|}}$ имеет порядок ${{\varepsilon }^{{1/2}}}$. Эти плоские случаи рассмотрены в приложении 1.

4. ПРИМЕРЫ

В примерах используется равномерная сетка в ${{\mathbb{R}}^{2}}$ вида $\left\{ {\left( {\cos \frac{{2\pi k}}{I},\sin \frac{{2\pi k}}{I}} \right)} \right\}_{{k = 0}}^{{I - 1}}$, где $I$ – число элементов сетки. Мелкость сетки имеет порядок $1{\text{/}}I$. Все картинки нарисованы для $I = 100$. Во всех примерах для всех $i$ шаг по времени ${{t}_{{i + 1}}} - {{t}_{i}}{{ = 10}^{{ - 7}}}$ (избыточно малый). Мы старались подобрать условия примеров так, чтобы читатель мог их максимально просто интерпретировать.

Пример 2. Рассмотрим матрицу $A \in {{\mathbb{R}}^{{2 \times 2}}}$,

Решается задача (5) (см. фиг. 1). В табл. 1 приведены результаты численного моделирования для данного примера. Все обозначения соответствуют ранее описанным, и их значения были получены с помощью алгоритмов, описанных выше. Радиус сильной выпуклости множеств $M({{t}_{k}})$ равен примерно $R = 2.81$ и вычисляется численно, его можно также оценить чисто теоретически (см. следствие теоремы 1 из [24]). В условиях п. 2 теоремы 2 значение $\delta = 0.5$. Истинное время оценивается из условия ${{t}_{k}} - {{10}^{{ - 7}}} \leqslant T \leqslant \tau $. Последняя строка данной таблицы подтверждает оценку $\left\| {{{x}_{0}} - {{{\hat {x}}}_{0}}} \right\|$, полученную в п. 2 теоремы 2. Скорость сходимости алгоритма по пространственной переменной является квадратичной по мелкости сетки и соответственно линейной по $\varepsilon = h(\hat {M}({{t}_{k}}),M({{t}_{k}}))$ в силу неравенства $\delta > 0$.

Фиг. 1.

Пример 1.

Пример 3. Снова матрица $A \in {{\mathbb{R}}^{{2 \times 2}}}$ имеет вид

По теореме 3 (см. [12]) множество ${{M}_{0}}$ является сильно выпуклым с радиусом $R = 3{\text{/}}4$.

Решается задача (6) (см. фиг. 2). В условиях п. 2 теоремы 2 значение $\delta = 0.11$. Истинное вре-мя $T$ оценивается из условия $\tau \leqslant T \leqslant {{t}_{k}} + {{10}^{{ - 7}}}$. В табл. 2 приводятся результаты численного моделирования для данного примера.

Фиг. 2.

Пример 2.

Пример 4. Пусть матрица $A \in {{\mathbb{R}}^{{2 \times 2}}}$ задана следующим образом:

На фиг. 3 изображено решение задачи (6). В отличие от предыдущего примера здесь не реализуется случай п. 2 теоремы 2 ($\delta = 0$). При этом $0$ – внутренняя точка множества $U$, а именно, ${{B}_{{1/\sqrt 5 }}}(0) \subset U$. Истинное время $T$ оценивается из условия $\tau \leqslant T \leqslant {{t}_{k}} + {{10}^{{ - 7}}}$. В табл. 3 приведены результаты численного моделирования для данного примера.

Фиг. 3.

Пример 3.

Пример 5. Пусть матрица $A \in {{\mathbb{R}}^{{2 \times 2}}}$ задана следующим образом:

Фиг. 4.

Пример 4.

Решается задача (5). В табл. 4 приведены результаты численного моделирования для данного примера. Радиус сильной выпуклости множества $M({{t}_{k}})$ примерно равен $64.76$ и может быть вычислен по формуле $\int_0^{{{t}_{k}}} {R(s){\kern 1pt} ds} $ (см. [19]), где $R(s) = \lambda _{1}^{2}(s){\text{/}}{{\lambda }_{2}}(s) = \frac{3}{2}{{e}^{{ - 2s}}}$ – радиус сильной выпуклости эллипса ${{e}^{{As}}}{{B}_{{3/2}}}(0)$ с максимальной полуосью ${{\lambda }_{1}}(s) = \frac{3}{2}{{e}^{{ - 0.5s}}}$ и минимальной полуосью ${{\lambda }_{2}}(s) = \frac{3}{2}{{e}^{{ - 3s}}}$. Для $I = 3000$ векторов в сетке время $\tau $, полученное из включения (20), равно $\tau = 2.44260$. При меньшем $I$ получается $\tau = 0$ в силу малости параметра $\mu = {{e}^{{ - 3{{t}_{k}}}}}$ из леммы 2. Скорость сходимости алгоритма по фазовой переменной является линейной по мелкости сетки, что обусловлено равенством $\delta = 0$.