next up previous
Next: 7 Примеры Up: GRIGOR Previous: 5 Аппроксимационные схемы и

6. Некоторые типы КРО

Выше приведена АС построения обобщенного решения задачи (2.1). При этом использован ОСП, известный в теории дифференциальных игр и примененный здесь к решению задачи 1 - задачи о построении надграфика обобщенного решения. Аналогичным образом ОСП используется при решении задачи 2 - задачи о построении подграфика $w$. При этом получаем КРО $G_2$, двойственный по отношению к КРО $G_1$ и определяемый по формуле


\begin{displaymath}
G_2(t,\Delta,\xi) (x) = \min_{s \in S_n} \max_{f \in F_2(t,x,s)}
\mathrm{conc\,}\xi(x+ \Delta f).
\end{displaymath} (6.1)

Здесь $\xi$ - функция, определенная на $\bar{D}(t+ \Delta)$, $t_0 \leq t < \vartheta$, $\Delta > 0$, $t+ \Delta \leq \vartheta;$ $ \ \mathrm{conc\,}\xi = -\mathrm{co\,}\{- \xi \}$ - локально-вогнутая оболочка (ЛВГО) сужения функции $\xi$ на шар $O(x,K \Delta), \ x \in \bar{D}(t)$; множество $F_2(t,x,s) = \{ f \in R^n:$ $\l s,f \r\leq H(t,x,s)$, $\Vert f\Vert \leq K \}$ - замыкание дополнения до $F$ множества
$F_1(t,x,s)$.

Отметим, что оператор $G_2$ допускает следующее представление

\begin{displaymath}
G_2(t,\Delta,\xi) (x) = \min_{y \in O(x,K_0 \Delta)} \min_{s...
... \{ \Delta H(t,x,s) + \l s,x-y \r + \mathrm{conc\,}\xi (y)
\},
\end{displaymath}

где $\partial \, \mathrm{conc\,}\xi(y)= \{ s \in R^n: \mathrm{conc\,}
\xi(y^*) - \mathrm{conc\,}\xi(y) \leq \l s, y^*-y \r $
$\forall\, \ y^* \in O(x,K \Delta) \}$ - супердифференциал ЛВГО функции $\xi$, вычисленный в точке $y \in O(x, K_0 \Delta)$. Константа $K_0$ выбрана из условия

\begin{displaymath}
\max_{(t,u,v) \in [t_0, \vartheta] \times P
\times Q} \Vert f(t,x,u,v)\Vert \leq K_0 < {K\over 2}.
\end{displaymath}

З а м е ч а н и е. Формулы (5.2) и (6.1) для операторов $G_1$ и $G_2$, соответственно, можно интерпретировать как обобщение формул Хопфа [23] на ЛВО (ЛВГО) функций. Более точно, справедливы равенства

\begin{displaymath}
G_1(t,\Delta,\xi) (x) = H G_1(t,\Delta,\xi) (x),
\end{displaymath}


\begin{displaymath}
H G_1(t,\Delta,\xi) (x) = \sup_{s \in R^n} \{ \l s,x \r + \Delta H(t,x,s)
- \rho_1(s,x,\Delta,\xi) \},
\end{displaymath}


\begin{displaymath}
\rho_1(s,x,\Delta,\xi) = \max_{y \in O(x,K \Delta)} \{ \l s,y \r - \xi
(y) \},
\end{displaymath}


\begin{displaymath}
G_2(t,\Delta,\xi) (x) = H G_2(t,\Delta,\xi) (x),
\end{displaymath}


\begin{displaymath}
H G_2(t,\Delta,\xi) (x) = \inf_{s \in R^n} \{ \l s,x \r + \Delta H(t,x,s)
- \rho_2(s,x,\Delta,\xi) \},
\end{displaymath}


\begin{displaymath}
\rho_2(s,x,\Delta,\xi) = \min_{y \in O(x,K \Delta)} \{ \l s,y \r - \xi
(y) \}.
\end{displaymath}

Оператор $G_2$, как и оператор $G_1$, удовлетворяет условиям (G1)-(G8), следовательно, порожденная им АС сходится к обобщенному решению $w$ задачи Коши (2.1) со скоростью, пропорциональной $\Delta^{1/2}$. Поэтому любая выпуклая комбинация операторов $G_1$ и $G_2$, определяемая формулой

\begin{displaymath}
G_3(t,\Delta,\xi) (x) = \alpha_1(x) G_1(t,\Delta,\xi) (x) +
\alpha_2(x) G_2(t,\Delta,\xi) (x)
\end{displaymath} (6.2)

также сходится с той же скоростью. Здесь $\alpha_1(x)$ и $\alpha_2(x)$ - любые (необязательно непрерывные) весовые функции, удовлетворяющие ограничениям $\alpha_1(x) \geq 0$, $\alpha_2(x) \geq 0$, $\alpha_1(x) + \alpha_2(x) =1$.

Отметим, что среди КРО вида (6.2) существует оператор, определяющий квазидифференцируемую (в смысле Демьянова [24]) функцию, аппроксимирующую обобщенное решение задачи (2.1).

Рассмотрим КРО на множестве таблично заданных функций. Пусть $h_i = \gamma_i \Delta >0$ (i=1, ...,n) - шаги дискретизации фазового пространства. Совокупность точек $\{ y= \hat{x} + \Sigma(m_1 h_1 e_1 + \cdots + m_n h_n e_n) \}$ таких, что $(\tau,y) \in \bar{D}$ $(m_i = 0,\pm1, \pm2, \ldots, \ i=1, \ldots, n)$, назовем сеткой и будем обозначать $\bar{D}R(\tau)$. Здесь $e_i \ (i=1, \ldots, n)$ - орты в $R^n$. Пусть $D^*(\tau)$ - выпуклая оболочка сетки $\bar{D}R(\tau)$:

\begin{displaymath}
D^*(\tau) = \left\{ y \in R^n: \ y= \sum_{i=0}^n \alpha_j y_j, \ y_j
\in \bar{D}R(\tau),\right.
\end{displaymath}


\begin{displaymath}
\left. \alpha_j \geq 0, \ j=0, \ldots,n, \ \sum_{j=0}^n \alpha_j =1 \right\}.
\end{displaymath}

Полагаем, что $t \in [t_0, \vartheta), t+ \Delta \in (t_0, \vartheta]$ и $\xi: D^*(t+ \Delta) \rightarrow R$ - функция, удовлетворяющая условию Липшица. Пусть $\Omega$ - некоторое фиксированное разбиение n-мерного куба на симплексы.

Определим значение оператора $G_4(t, \Delta, \xi)(y): D^*(t) \rightarrow R$ в точке $y \in D^*(t)$ соотношением

\begin{displaymath}
G_4(t,\Delta,\xi)(y) = \sum_{j=0}^n \alpha_j F(t,\Delta, \xi)
(y_j),
\end{displaymath} (6.3)


\begin{displaymath}
y \in D^*(t), \quad y_j \in \bar{D}R(t), \quad \alpha_j \geq 0, \quad
j=0, \ldots, n,
\end{displaymath}


\begin{displaymath}
\sum_{j=0}^n \alpha_j =1, \quad y= \sum_{j=0}^n \alpha_j y_j,
\end{displaymath}


\begin{displaymath}
y_0 = \hat{x} + \Sigma (m_1 h_1 e_1 + \cdots + m_n h_n e_n),
\end{displaymath}


\begin{displaymath}
y_j= y_0 + \Sigma (k_1 h_1 e_1 + \cdots + k_n h_n e_n), \quad
j=1, \ldots, n, \quad k_j =0, \pm1,
\end{displaymath}

Здесь $F=F_1$ (или $F_2$). Коэффициенты $\alpha_j = \alpha_j (\Omega)$ и точки $y_j =y_j (\Omega) \ (j=0, \ldots, n)$ здесь и далее задаются однозначно в соответствии с разби-
ением $\Omega$.

АС с КРО $G_4$ также сходится [18] со скоростью, пропорциональной шагу $\Delta$ разбиения отрезка $[t_0, \vartheta]$. Здесь подчеркнем, что оператор $G_4$ может быть использован для реального (численного) построения аппроксимации решения задачи (2.1).

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

Пусть

\begin{displaymath}
r = 3Kn,
\end{displaymath}

где $K= \sup\{\Vert f(t,x,u,v) \Vert:(t,x,u,v) \in \hat{D} \times P \times Q\},$

\begin{displaymath}
y_l \in B(t,x,r \Delta) = w(x,r \Delta) \bigcap \bar{D}R(t),
\end{displaymath}


\begin{displaymath}
l=1, \ldots, m, \quad m=(2k+1)^n, \ \ \ k \geq 1,
\end{displaymath}


\begin{displaymath}
B(t,x,r \Delta) = O(x, r \Delta) \bigcap \bar{D}R(t),
\end{displaymath}


\begin{displaymath}
w(x,r \Delta) = \{d \in R^n: \ \max_i \vert d_i-x_i\vert \leq r \Delta, \ i=1,
\ldots, n \}.
\end{displaymath}

Пусть $L(y) = \l a,y \r + b$ - линейная функция, наиболее близкая в смысле квадратичного отклонения к табличной функции $\{ (y_l, \xi(y_l)): l = 1, \ldots,m \}$, т.е. параметры $a \in R^n, \ b \in R$ определяются из условия минимума квадратичного отклонения

\begin{displaymath}
\sum_{l=1}^m [\xi(y_l) - (\l a,y_l \r +b)]^2.
\end{displaymath}

Это условие приводит к системе линейных уравнений
\begin{displaymath}
b=-\l a,x \r + \xi_0, \quad x=\frac{1}{m} \sum_{l=1}^m y_l, \quad \xi_0
= \frac{1}{m} \sum_{l=1}^m \xi(y_l),
\end{displaymath} (6.4)


\begin{displaymath}
\sum_{l=1}^m \l a,p_l \r p_l = \sum_{l=1}^m \xi (y_l)p_l, \quad p_l=y_l-x, \quad
l=1, \ldots, m.
\end{displaymath}

Система (6.4) является симметрической и может быть записана в виде

\begin{displaymath}
\Phi a =\psi, \quad
\Phi = \{ \phi_{ij}\}, \quad
\phi_{ij} =...
...\quad
\psi = \sum_{l=1}^m \xi (y_l)p_l, \quad
i,j=1, \ldots,n.
\end{displaymath} (6.5)

Симметрия множества $B(t,x, r \Delta)$ относительно координатных плоскостей обеспечивает диагональность системы (6.5)

\begin{displaymath}
\phi_{ii}= 2(1^2+ \cdots +k^2) (2k+1)^{n-1} \ h^2_i= \frac{1}{3}k
(k+1) (2k+1)^n h^2_i,
\end{displaymath}


\begin{displaymath}
\phi_{ij}=0, \quad i \neq j, \quad i,j =1, \ldots, n,
\end{displaymath}


\begin{displaymath}
\psi_i = h_i \sum_{\eta} \sum_{s=1}^k s(\xi (x+sh_i e_i + \eta) -
\xi(x-sh_i e_i +\eta)),
\end{displaymath}


\begin{displaymath}
\eta = \sum_{j} \sum_{s_j} s_j h_j e_j, \quad s_j= 0, \pm{1}, \ldots, \pm{k},
\quad j=1, \ldots, n, \quad j \neq i,
\end{displaymath}


\begin{displaymath}
a=(a_1, \ldots, a_n), \quad a_i= {\psi_i \over \psi_{ii}}, \quad
i=1, \ldots, n.
\end{displaymath}

Можно проверить, что линейная функция $L(y)$, рассмотренная на шаре $O(x, K \Delta)$, расположена между ЛВО и ЛВГО функции $\xi$, построенными на шаре $O(x,r \Delta)$, $r=3Kn$

\begin{displaymath}
\mathrm{co\,}\xi (y) \leq L(y) \leq \mathrm{conc\,}\xi(y),\ \ \ \ y \in O(x,K
\Delta).
\end{displaymath}

Следовательно, справедливы соотношения
\begin{displaymath}
\begin{array}{c} G_1(t, \Delta, \xi)(x) \leq
G_5(t, \Delta,\...
... \Delta, L)(x)= \\ [2ex]
= \xi_0 + \Delta H(t,x,a),
\end{array}\end{displaymath} (6.6)

где $x \in \bar{D}(t)$. Поэтому АС с оператором $G_5$ сходится.

Отметим следующий факт. Пусть $\gamma_i =\gamma, \ i=1, \ldots,n, \ 3Kn^{1/2} < \gamma$. Тогда КРО $G_5$ обращается в оператор Лакса-Фридрихса [17].

\begin{displaymath}
F_5(t, \Delta, \xi) = \xi_0 + \Delta H(t,x,c),
\end{displaymath}

где компоненты $c_i$ вектора $c$ находятся по формулам

\begin{displaymath}
c_i= (\xi(x+ \Delta \gamma_i e_i)- \xi(x- \Delta \gamma_i e_i))
(2 \Delta \gamma_i)^{-1}, \quad i-1, \ldots, n,
\end{displaymath}


\begin{displaymath}
\xi_0= \frac{1}{2n+1} [\xi (x) + \sum_{i=1}^n (\xi(x+ \Delta
\gamma_i e_i)+ \xi(x- \Delta \gamma_i e_i))].
\end{displaymath}

В заключение укажем на возможность синтеза оптмального управления при пространственно-временной дискретизации динамических игровых задач. Решение проблемы корректной интерполяции узловых значений оптимального управления обеспечивается в общем случае более высоким порядком малости шага аппроксимации по пространственным переменным в сравнении с шагом по времени [25].


next up previous
Next: 7 Примеры Up: GRIGOR Previous: 5 Аппроксимационные схемы и
2003-08-19