%\input amsppt.sty
%\documentstyle{amsppt}
%\nopagenumbers
\magnification=\magstep2
%\pagewidth{17 true cm}
%\vcorrection{-.5 true cm}
%\hcorrection{-.5 true cm}
\TagsOnRight
\pretitle{ \centerline{\bf { Научные труды ИвГУ. Математика. Вып.~2}}
\centerline{\bf {Иваново, 1999}}

\noindent --------------------------------------------------------------------------------------------------
\vskip .1 cm
УДК   513.6}
\vskip .3 cm
\centerline {\bf С.~В.~Котвин, С.~И.~Хашин}
\vskip .3 cm
%\leftheadtext{\it С.~В.~Котвин, С.~И.~Хашин }
%\rightheadtext{\it Методы Рунге -- Кутта}

\topmatter
%\author
%С.В.Котвин, С.И.Хашин
%\endauthor
\title
\centerline{\bf Матричная запись условий порядка}
\centerline{\bf для методов Рунге -- Кутта}
\endtitle

\abstract \nofrills
\vskip .3cm\noindent
Предлагается унифицированный метод записи условий
порядка для методов Рунге -- Кутта. Выписываются новые виды уравнений, 
которым
должна удовлетворять матрица коэффициентов метода. Основным результатом
работы являются теоремы 2, 3.

%Библиогp.: 2 назв.
\endabstract
\endtopmatter
\document
\pageno=1
\vskip .5 cm

Методы Рунге -- Кутта (РК), используемые для численного решения
обыкновенных дифференциальных уравнений, характеризуются двумя
параметрами $(p,n)$ - порядком метода и количеством шагов
соответственно. Естественно, что при фиксированном порядке (точности)
метода количество шагов хотелось бы минимизировать. Классические
методы РК имеют параметры (4,4). К настоящему времени [1, 2]
известны методы с параметрами (5,6), (6,7), (7,9) (8,13) и некоторые
другие.

Каждый $n$-шаговый метод РК порядка $p$ задается с помощью
нижнетреугольной $n\times n$-матрицы $A$ вида:

$$ A =
          \left(\matrix{ 0      & 0       &\dots  & 0 \cr
                       a_{21}  & 0       &\dots  & 0 \cr
                               &         &\dots  &   \cr
                       a_{n1}  & a_{n2}  &\dots  & 0 \cr
                    } \right),
$$
\noindent и  вектора $b=(b_{1},\,\dots,\,b_{n})$  длины  n.
Их  можно  объединить  в  одну расширенную матрицу $\tilde{A}$
размера $(n+1)\times (n+1)$:
$$ \tilde{A} =
          \left(\matrix{ 0      & 0       &\dots  & 0 \cr
                       a_{21}  & 0       &\dots  & 0 \cr
                               &         &\dots  &   \cr
                       b_1     & b_2     &\dots  & 0 \cr
                    } \right).
$$

Для нахождения $n$-шагового метода РК требуется найти ${\Bbb R}\,$
-- матрицу $\tilde{A}$, коэффициенты которой удовлетворят некоторой
системе нелинейных (полиномиальных) уравнений. В практически важных
случаях $(p=7,\,\dots,\,10)$ мы получаем нелинейную систему от нескольких
десятков (или даже сотен) переменных и еще больше уравнений. В
настоящее время не существует общих способов ее решения. Нахождение
каждого отдельного решения является большой проблемой.

Для описания указанной системы уравнений применяется ``метод
деревьев" [2]: каждому дереву с не более чем $p$ вершинами
соответствует ровно одно уравнение. Опишем это соответствие более
подробно.

Матрицы $A$ и $\tilde{A}$ будем отождествлять с соответствующими линейными
операторами в пространствах ${\Bbb R}^{n}$ и ${\Bbb R}^{n+1}$.

Для двух векторов $x=(x_{1},\,\dots,\,x_{n})$ и $y=(y_{1},\,\dots,\,
y_{n})$ длины $n$ через $x*y$ будем обозначать вектор
$$
x*y = (x_{1}y_{1},\,\dots,\,x_{n}y_{n}),
$$
Через $e$ обозначим вектор $(1,\,\dots,\,1)$.


{\bf Определение 1}. a). Деревом  будем  называть  граф  без  циклов  с
отмеченной вершиной (корнем).  Будем  считать,  что  корень  дерева
расположен внизу.

б). Пусть $a$ - некоторая вершина в дереве $t$, через $t_a$  обозначим
дерево, состоящее из всех вершин дерева $t$, лежащих над  a.

в). Через $t_0$ обозначим дерево, состоящее из  одного  корня.

г). Для двух деревьев $t_{1}$ и $t_{2}$ через $t_{1}t_{2}$ обозначим
дерево, получающееся объединением корней деревьев $t_{1}$ и $t_{2}$.
Относительно этой операции множество всех деревьев является свободной
полугруппой бесконечного ранга, нейтральный элемент - $t_{0}$,
образующими являются все одноногие деревья (у которых из корня
выходит лишь одно ребро).

д). Для любого дерева $t$ через $\alpha t$ обозначим дерево, полученное
из $t$ добавлением еще одной вершины ``под" корнем. Дерево $\alpha t$ -
всегда одноногое. Любое дерево может быть получено из $t_0$
комбинацией операций $\alpha $ и умножения.

е). Для любого дерева $t$ через $w(t)$ обозначим  количество  вершин
дерева минус  1  (т.е. количество  ребер).  Число $w(t)$  будем
называть ``весом" дерева.

ж). Для любого дерева $t$ через $\delta (t)$ обозначим произведение по
всем вершинам $a$, кроме корня
$(w(t_{a})+1)$; $\gamma (t):=\delta(t)(w(t)+1)$.

\proclaim{\indent Предложение} а) $w(t_{1}t_{2}) = w(t_{1}) + w(t_{2})$,

б) $w(\alpha t) = w(t) + 1$,

в) $\delta (t_{1}t_{2}) = \delta (t_{1}) \delta (t_{2}),$

г) $\delta (\alpha t) = \delta (t) (w(t)+1)$.

Пусть $a_{n}, b_{n}$ - количество различных деревьев веса $n (\le n$).
Тогда (см.[1]):

$$\matrix{
n     &0  &1 &2 &3 &4  & 5 &6  &7   &8   &9     \cr
a_{n} &1  &1 &2 &4 &9  &20 &48 &115 &286 &719   \cr
b_{n} &1  &2 &4 &8 &17 &37 &85 &200 &486 &1205 .  \cr
} 
$$
\endproclaim
\proclaim{\indent Определение 2} Для любого дерева $t$ и квадратной матрицы $A$
определим вектор $\Phi _t(A)$ следующим образом. Для дерева $t_0$
положим $\Phi_{t_{0}}(A)=e$, где $e=(1,\ldots,1)$. Для дерева $\alpha
t$ положим 
$$\Phi _{\alpha t}(A)=A\cdot \Phi _{t}(A),$$ где
$A\cdot v$ --- произведение матрицы на вектор. Для двух деревьев $t_1$
и $t_2$ положим
$$
\Phi _{t_1 t_2}(A) = \Phi _{t_{1}}(A)*\Phi_{t_{2}}(A).
$$
\endproclaim
Так как с помощью операции $\alpha $ и умножения деревьев из
дерева $t_{0}$ можно получить все деревья, то этих правил достаточно
для полного задания оператора $\Phi$.

Сумму координат вектора $x$ обозначим через $\{x\}$.
\proclaim{\indent Теорема 1 {\rm [1]}} Нижнетреугольная матрица 
$A$ и вектор $b$ задают  метод
Рунге -- Кутта порядка точности $p \iff$ для каждого  дерева $t$  веса $<p$
выполнено равенство
$$
\{b*\Phi _{t}(A)\} = 1/\gamma (t).
$$
\noindent Напомним, что $\gamma (t)=\delta (t)(w(t)+1)$ и через
$\{x\}$ обозначена сумма координат вектора x.
\endproclaim
\proclaim{\indent Теорема 2} Расширенная матрица $\tilde{A}$ задает метод
Рунге -- Кутта порядка точности $p \iff$ для каждого дерева $t$ веса
$\le p$ выполнено равенство
$$
[\Phi _{t}(\tilde{A})] = 1/\delta (t),
$$
\noindent где через $[v]$ обозначена последняя, $(n+1)$-я координата
вектора v.
\endproclaim
\proclaim{\indent Замечание} Система уравнений из теоремы 2 не является точной
копией системы из теоремы 1. Уравнению для дерева $t$ из теоремы 1
соответствует уравнение для дерева $\alpha t$ из теоремы 2. При этом
уравнение из теоремы 2, соответствующее дереву $t_0$, является
тривиальным.
\endproclaim
Таким образом, система уравнений из теоремы 2 является еще более
громоздкой, чем система из теоремы 1. Однако новые уравнения обладают
важным свойством, которое позволяет надеяться, что новую систему
решать легче: и левая и правая часть уравнения для дерева $t_1 t_2$
являются произведением левых и правых частей соответствующих
уравнений для деревьев $t_1$ и $t_2$. Таким образом, в системе
уравнений теоремы 2 на самом деле можно оставить только уравнения для
одноногих деревьев.
\proclaim{\indent Определение 3} Пусть $\tilde{A}$ - матрица размера
$(n+1)\times (n+1)$ вида
$$ \tilde{A} =
          \left(\matrix{ 0        & 0         &\dots  & 0 \cr
                       a_{21}    & 0         &\dots  & 0 \cr
                                 &           &\dots  &   \cr
                       a_{n+1,1} & a_{n+1,2} &\dots  & 0 \cr
         } \right).
$$

\noindent Будем отождествлять ее с соответствующим нильпотентным
оператором в пространстве ${\Bbb R}^{n+1}$. Через $L_{k}=L_{k}(A)$
обозначим подпространство в ${\Bbb R}^{n+1}$, порожденное векторами
$\Phi _{t}(A)$ для всех деревьев веса k. Через $L'_k$ обозначим
векторы из $L_{k}$ с нулевой последней координатой:
$$
L'_k= \{ v\in L_{k}: [v]=0 \}.
$$
\endproclaim
Любое дерево $t$ веса $k$ можно представить либо в виде $\alpha t_1$,
либо в виде $t_1 t_2$ для некоторых деревьев $t_1$, $t_2$, поэтому
$$
L_{k} = \tilde{A}(L_{k-1}) + \sum_{i+j=k}L_{i}*L_{j}.
$$
\proclaim{\indent Замечание} Если расширенная матрица $\tilde{A}$ 
задает метод
Рунге -- Кутта порядка точности $p$, то для всех $k \le p$:
$$
L_{k} = <\tilde{A}^{k}e> \oplus  L'_{k}.
$$
\endproclaim
\proclaim{\indent Теорема 3} Расширенная матрица $\tilde{A}$ задает метод
Рунге -- Кутта порядка точности $p \Leftrightarrow $ для всех $k<p$:
$$
\forall  v\in L_{k}: [\tilde{A}\cdot v] ={ [v]\over (k+1)},\eqno(*)
$$
\noindent где через $[v]$ обозначена последняя, $(n+1)$-я координата
вектора v.
\endproclaim
\underbar{Доказательство}. Пусть матрица $\tilde{A}$ задает метод
Рунге -- Кутта порядка точности $p$, т.е. выполнены соотношения
$$
[\Phi _{t}(\tilde{A})] = 1/\delta (t).
$$
\noindent Для доказательства равенства  (*)  достаточно  проверить,  что  для
каждого дерева $t$ веса $k$ выполнено
$$
[\tilde{A}\cdot \Phi _{t}(\tilde{A})] = [\Phi _{t}(\tilde{A})]/(k+1),
$$
\noindent что следует из $\delta (\alpha t) = \delta (t) (w(t)+1)$.

Обратно, пусть выполнены соотношения (*). При $k$=0 получим:
$[\tilde{A}e]=[e]=1,$ т.е. условия теоремы 2 выполнены для деревьев
веса 0. Если для некоторого дерева $t$
$$
[\Phi _{t}(\tilde{A})] = 1\hbox{/}\delta (t),
$$
\noindent то из соотношений (*) получим
$$
[\tilde{A}\cdot \Phi _{t}(\tilde{A})] = [\Phi _{t}(\tilde{A})]/(k+1) .
$$
\noindent что и дает нам индуктивное доказательство теоремы.

\vskip .5 cm
\centerline{\bf Список использованной литеpатуpы}
\vskip .3 cm
\noindent 
\hangindent 0.5cm
1. {\it Breman K.~E., Campbell S.~L., Petzold L.~R.} Numerical Solution
of Initial Problems in Differntial-algebraic Equations. N.Y., 1989. 320 p.

\noindent 
\hangindent 0.5cm
2. {\it Butcher J.~C.} Runge-Kutta and General Linear Methods// \hfill\break
The Numerical Analysis of Ordinary
Differential Equations. N.Y., 1987. P.~58 -- 83.

\end

