\documentclass{article}[14pt] \usepackage[LCY]{fontenc} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{amsmath} \usepackage{delarray} \fontencoding{LCY}\selectfont \DeclareMathOperator{\minim}{inf} \DeclareMathOperator{\mini}{min} \DeclareMathOperator{\maxi}{sup} \DeclareMathOperator{\maxim}{max} \renewcommand{\contentsname}{Содержание} \renewcommand{\tablename}{Рис.} \unitlength=1mm \textwidth=14.5cm \textheight=25cm \topmargin=-5.5mm \hoffset=-17mm \voffset=-2cm \binoppenalty=10000 \relpenalty=10000 %\documentstyle{amsppt} %\document %\tenpoint %\input nologo.sty %\hsize=10.5cm %\vsize=16.5cm %\parindent=1cm %\pageno=1 %\TagsOnRight \begin{document} \leftline{\it В.\,А.\,Даугавет, Н.\,А.\,Таныгина} \bigskip \noindent {\bf БЫСТРОТА СХОДИМОСТИ МЕТОДА \noindent ВЫРАВНИВАНИЯ В РАВНОМЕРНОЙ \noindent $\Sigma$-АППРОКСИМАЦИИ\footnote{Работа выполнена при финансовой поддержке РФФИ (проект N 01-0100231).} } \bigskip {\bf 1.} Под $\Sigma$-аппроксимацией понимается аппроксимация фун\-кции двух переменных $f(u,v)$ суммой функций одной переменной $\,x(u)+y(v).$ В данной статье рассматривается дискретный вариант такой аппроксимации, который описывается следующим образом. Пусть $F[M,N]$ приближаемая матрица (таблица функции от двух переменных), где $M=\{1,2,\dots,m\},$ $N=\{1,2,\dots,n\},$ а $x[M]$ и $y[N]$ искомые векторы (таблицы функций одной переменной). Равномерная дискретная задача $\Sigma$-аппрокси\-мации имеет вид $$\varphi(x,y):=\max_{i\in M,j\in N} \bigm |F[i,j]-x[i]-y[j] \bigm | \to \inf_{x[M],y[N]}.\eqno (1)$$ Эта задача сводится к задаче линейного программирования, но применение традиционного симплекс-метода для ее решения не эффективно. Для этой задачи обычно используется итеративный метод {\it выравнивания} (см. $[1,2]$). В данной работе рассматривается вопрос о быстроте сходимости метода выравнивания. Вводится определение альтернанса для матрицы $F$ и показывается, что метод выравнивания сходится с быстротой геометрической прогрессии со знаменателем, зависящим от длины альтернанса. \bigskip {\bf 2.} Приведем необходимые и достаточные признаки решения для задачи (1).\\ Обозначим ${\cal P}:=\{[i,j]\,\Big |\,i\in M,\, j\in N\}.$ {\bf Определение 1.} {\it Ступенчатым циклом} $C_q$ называется множество $2q$ различных пар индексов из ${\cal P}$ следующего вида $$C_q=\bigl\{[i_1,j_1],[i_1,j_2],[i_2,j_2],[i_2,j_3], \dots,[i_q,j_q],[i_q,j_1]\bigr\},$$ где $ q\in [2, \min\{m,n\}].$ Число $q$ называется длиной ступенчатого цикла. {\bf Определение 2.} Пара векторов $\{x,y\}$ об\-ладает {\it альтернансом} относительно матрицы $F[M,N],$ если в ${\cal P}$ существует ступенчатый цикл $C_q,$ на котором при всех $k\in 1:q$ выполняются равенства: $$\begin{matrix} F[i_k,j_k]-x[i_k]-y[j_k]&= \mu,\\ F[i_k,j_{k+1}]-x[i_k]-y[j_{k+1}] &=- \mu, \\ j_{q+1}=j_1, \ \ |\mu|=\varphi(x,y).&\end{matrix}$$ На рис. 1 приведена схема расположения альтернансных точек при $q=4.$ $$\begin{matrix} &j_1&j_2& j_3 & j_4\\ ---&---&---&---&---\\ i_1& \ \ \mu &-\mu & & \\ i_2& & \ \ \mu & -\mu & \\ i_3& & &\ \ \mu & -\mu \\ i_4&-\mu & & & \ \ \mu \end{matrix}$$ \centerline{рис. 1.} Известный признак оптимальности для непрерывной задачи $\Sigma$-аппроксимации (см. $[3]$) в дискретном случае формулируется следующим образом. \smallskip {\bf Теорема 1.} {\it Пара векторов $\{x_*,y_*\}$ является решением задачи} (1) {\it тогда и только тогда, когда она обладает альтернансом.} Заметим, что в дискретном случае доказательство этой теоремы становится очень простым. Действительно, задача (1) сводится к задаче линейного программирования, и результаты теоремы легко вытекают из известных теорем двойственности. \bigskip {\bf 3.} Для заданной матрицы $F[M,N]$ возьмем произвольный ступенчатый цикл\\ $C_q=\bigl\{ [i_1,j_1],[i_1,j_2],\dots,[i_q,j_q],[i_q,j_1]\bigr\}$ и обозначим $$\rho(C_q):={1\over 2q}\sum_{k\in 1:q} (F[i_k,j_k]-F[i_k,j_{k+1}]).$$ Решим задачу аппроксимации только на этом ступенчатом цикле. Положим $$\varphi_c(u,v):=\max_{k\in 1:q}\bigl\{\bigm |F[i_k,j_k]-u[k]-v[k] \bigm |,\bigm |F[i_k,j_{k+1}]-u[k]-v[k+1] \bigm | \bigr\},$$ где $j_{q+1}=j_1,$ $v[q+1]=v[1],$ и рассмотрим задачу $$\varphi_c(u,v)\to \min_{u,v\in \Bbb R^q}.$$ Она сводится к следующей задаче линейного программирования $$g\to \min,$$ $$ \begin{matrix} g+u[k]+v[k]& \ge F[i_k,j_k],\\ g-u[k]-v[k]& \ge -F[i_k,j_k],\\ g+u[k]+v[k+1]& \ge F[i_k,j_{k+1}],\\ g-u[k]-v[k+1]& \ge -F[i_k,j_{k+1}]\\ & \forall\ k\in 1:q. \end{matrix} \eqno(2)$$ Покажем, что $$\min_{u,v}\varphi_c(u,v)=|\rho(C_q)|.\eqno(3)$$ Действительно, сложив первое неравенство с последним и просуммировав по $k\in 1:q,$ получим неравенство $g\geq\rho(C_q).$ Аналогичным образом из второго и третьего неравенства получаем $g\geq -\rho(C_q).$ Значит, $g\geq |\rho(C_q)|.$ Подберем теперь $u,v$, на которых эта оценка реализуется. Возьмем произвольное число $\gamma$ и положим $v[1]=\gamma.$ Остальные компоненты $v$ и $u$ найдем из следующих рекуррентных соотношений для $k=1,2,...,q$: $$ u[k]=F[i_k,j_k]-v[k]-\rho(C_q),\ \ v[k+1]=F[i_k,j_{k+1}]-u[k]+\rho(C_q).$$ Легко видеть, что полученная пара векторов $u,v \in \Bbb R^q$ является планом задачи (2) и значение целевой функции на этом плане равно $|\rho(C_q)|.$ Значит, равенство (3) доказано. \smallskip {\bf Замечание.} Возьмем произвольные векторы $x[M]$ и $y[N]$ и рассмотрим матрицу $H[i,j]=F[i,j]-x[i]-y[j].$ Для любого ступенчатого цикла $C_q$ справедливо равенство $$\frac1{2q}\sum_{k\in 1:q}(H[i_k,j_k]-H[i_k,j_{k+1}])=\rho(C_q). \eqno(4)$$ Действительно, при вычислении левой суммы все $x[i_k]$ и $y[j_k]$ сократятся и останется только $\rho(C_q).$ \smallskip Вернемся к задаче (1). В силу (3) для любого ступенчатого цикла $C_q$ и любой пары векторов $\{x[M],y[N]\}$ справедливо неравенство $ \varphi(x,y)\geq |\rho(C_q)|.$ Значит, $\mu_*:=\inf\limits_{x,y}\varphi(x,y)\geq$ $\geq |\rho(C_q)|.$ Так как оптимальная пара векторов задачи (1) обладает альтернансом, то $$\mu_*=\max_{C_q} {1\over 2q} \Bigg | \sum_{k=1}^q\left( F[i_k,j_k]-F[i_k,j_{k+1}]\right)\Bigg | .$$ Пользуясь (4) легко показать, что если $|\rho(C_q)|=\mu_*,$ то ступенчатый цикл $C_q$ является альтернансом для любого решения $\{x,y\}$ задачи (1), поэтому далее будем называть его просто {\it альтернансом } матрицы $F.$ Нетрудно построить матрицы $F,$ у которых несколько альтернансов, при этом они могут и пересекаться. Тем не менее, практически чаcто встречаются матрицы $F,$ которые имеют единственный альтернанс с $q=2.$ \bigskip {\bf 4.} Метод выравнивания в дискретной равномерной $\Sigma$-ап\-проксимации заключается в следующем. Выберем $x_0[M]$ и затем на каждом $p$-м шаге ($p=1,2,\dots $) производим следующие операции. Зафиксировав вектор $x_{p-1}[M]$, построим \lq\lq наилучший\rq\rq для него вектор $y_p[N]$, решив задачу $$ \varphi(x_{p-1},y):= \max_{[i,j]\in {\cal P}}|F[i,j]-x_{p-1}[i]-y[j]|\to \inf_{y[N]}.\eqno(5)$$ Затем, зафиксировав вектор $y_p$, построим \lq\lq наилучший\rq\rq для него вектор $x_p[M],$ решив задачу $$\varphi(x,y_p)= \max_{[i,j]\in {\cal P}}|F[i,j]-x[i]-y_p[j]|\to \inf_{x[M]}.\eqno (6) $$ Процесс закончится, когда $x_p$ совпадет с $x_{p-1}.$ Опишем этот процесс подробнее. Ясно, что задача (5) распадается на $n$ самостоятельных задач при каждом $j\in N$: $$\max_{i\in M}|F[i,j]-x_{p-1}[i]-t|\to \inf_t.$$ Очевидно, что решение $j$-й задачи, которое обозначим $y_p[j],$ находится по формуле $$y_p[j]={1\over 2}\left( \max_{i\in M}(F[i,j]-x_{p-1}[i])+ \min_{i\in M}(F[i,j]-x_{p-1}[i])\right). \eqno(7)$$ Введем в рассмотрение матрицу невязок $H_{p-1,p-1}[M,N]$ с компонентами\\ $H_{p-1,p-1}[i,j]=F[i,j]-x_{p-1}[i]-y_{p-1}[j]$ и вектор $\Delta\,y_p$ с компонентами $\Delta\,y_p[j]:=y_p[j]-y_{p-1}[j].$ Тогда из (7) следует, что $$\Delta\,y_p[j]={1\over 2}\Big (\max_{i\in M}H_{p-1,p-1}[i,j]+\min_{i\in M}H_{p-1,p-1}[i,j]\Big ),$$ а новая матрица $H_{p-1,p}$ получается из $H_{p-1,p-1}$ вычитанием из каждого элемента $j$-го столбца одного и того же числа $\Delta\,y_p[j].$ Аналогично решается задача (6), т.~е. находится вектор $\Delta x_p:=x_p-x_{p-1},$ и строится новая матрица $H_{p,p}.$ Таким образом, $p$-й шаг метода выравнивания (построение $x_p$ по известному $x_{p-1}$) заключается в построении следующих векторов и матриц: $$\begin{matrix} \Delta\,y_p[j]={1\over 2}\Big (\max\limits_{i\in M}H_{p-1,p-1}[i,j]+ \min\limits_{i\in M} H_{p-1,p-1}[i,j]\Big ),\ j\in N;\\ H_{p-1,p}[i,j]=H_{p-1,p-1}[i,j]-\Delta\,y_p[j], \ \ \ i\in M,\ \ j\in N;\end{matrix}$$ $$ \begin{matrix} \Delta\,x_{p}[i] ={1\over 2}\Big (\max\limits_{j\in N}H_{p-1,p}[i,j]+ \min\limits_{j\in N}H_{p-1,p}[i,j] \Big ),\ i\in M;\\ H_{p,p}[i,j]=H_{p-1,p}[i,j]- \Delta\,x_{p}[i], \ i\in M,\ j\in N.\end{matrix}$$ Вычисления заканчиваются, когда вектор $ \Delta\,x_{p}[M]$ станет нулевым. Ясно, что $ \varphi(x_p,y_p)\leq \varphi(x_{p-1},y_p)\leq \varphi(x_{p-1},y_{p-1}),$ поэтому при $p\to \infty\ $ имеем $\varphi(x_p,y_p) \to \mu_*.$ В работах $[1,2]$ доказано, что $$\mu_*=\min_{x,y}\varphi(x,y).$$ Значит, всякая предельная пара последовательности $\{x_p,y_p\}$ яв\-ляется решением задачи (1). Перейдем к основному результату данной работы --- установлению быстроты сходимости метода выравнивания. Предварительно докажем некоторые вспомогательные утверждения. \bigskip {\bf 5.} Если процесс выравнивания сходится, то согласно алгоритму в пределе получим матрицу невязок $H_*$ с компонентами $H_*[i,j]=F[i,j]-x_*[i]-y_*[j],$ которая обладает свойством $$\begin{matrix} \max\limits_{j\in N}H_*[i,j]=-\min\limits_{j\in N}H_*[i,j],\ \ i\in M;\\ \max\limits_{i\in M}H_*[i,j]=-\min\limits_{i\in M}H_*[i,j],\ \ j\in N. \end{matrix} $$ Матрицу невязок $H_*$ с таким свойством назовем {\it выравненной.} \bigskip {\bf Теорема~2.} {\it Пусть исходная матрица $F$ имеет един\-ст\-вен\-ный альтернанс и решение задачи} (1) $\{x_*,y_*\}$ {\it таково, что матрица $H_*[i,j]=F[i,j]-x_*[i]-y_*[j]$ выравнена. Тогда каждая пара индексов $[i,j],$ на которой $|H_*[i,j]|=\varphi(x_*,y_*),$ принадлежит альтернансу.} Д\,о\,к\,а\,з\,а\,т\,е\,л\,ь\,с\,т\,в\,о. Введем обозначения $$\begin{matrix} C_q^*=\bigl\{ [i_1,j_1],[i_1,j_2],\dots,[i_q,j_q],[i_q,j_1]\bigr\}\ - \ \text{альтернанс},\\ c_i^*=\bigl\{i_1,i_2,...,i_q\bigr\},\ \ c_j^*=\bigl\{j_1,j_2,...,j_q\bigr\}.\end{matrix}$$ Пусть для определенности $H_*[i_k,j_k]=\varphi_*,$ $k=1:q,$ что соответствует рис. 1 с $\mu=\varphi_*.$ Допустим, что $|H_*[r_1,s_1]|=\varphi_*$ и пара $[r_1,s_1]$ не принадлежит $C_q^*.$ Рассмотрим четыре случая. а) $r_1=i_p\in c_i^*,\ s_1=j_l\in c_j^*.$ Если $H_*[r_1,s_1]=-\varphi_*,$ то цепочка $$[i_p,j_l],[i_l,j_l],[i_l,j_{l+1}],...,[i_p,j_p]$$ образует другой альтернанс, что противоречит предположению теоремы. Аналогичным образом можно построить другой альтернанс, если $H_*[r_1,s_1]$ $=\varphi_*.$ б) $r_1=i_p\in c_i^*,\ s_1\notin c_j^*$ (или $r_1\notin c_i^*,$ $\ s_1=j_l\in c_j^*$). Не умаляя общности считаем, что $H_*[r_1,s_1]=\varphi_*.$ Так как матрица $H_*$ выравнена, то найдется $H_*[r_2,s_1]=-\varphi_*. $ Далее, если $r_2\notin c_i^*,$ то находим $H_*[r_2,s_2]=\varphi_*$ и т.д. Таким образом строим цепочку из точек, не принадлежащих $C_q^*,$ пока это возможно. Если цепочка замкнулась, то получился новый альтернанс, что недопустимо. Если цепочка сама не замкнулась, а вышла на точку из $C_q^*,$ то, как в случае а), ее можно замкнуть точками из $C_q^*$ и снова получить другой альтернанс. в) $r_1\notin c_i^*,\ s_1\notin c_j^*$. Опять сначала строим цепочку из точек, не принадлежащих $C_q^*,$ пока это возможно. Либо она сама замкнется, либо выйдет своими концами в $C_q^*.$ В обоих случаях образуется новый альтернанс, что противоречит предположению теоремы. $\ \ \ \blacksquare$ \bigskip {\bf 6.} Исследовать скорость сходимости будем для матрицы $F,$ которая имеет {\bf единствен\-ный} альтернанс $$C_q=\bigl\{[i_1,j_1],[i_1,j_2],\dots,[i_q,j_q],[i_q,j_1]\bigr\},$$ и для которой $\inf\limits_{x,y}\varphi(x,y)=\mu_*>0.$ Для определенности будем считать, что $H_*[i_k,j_k]=\mu_*$ и $H_*[i_k,j_{k+1}]=-\mu_*$ при всех $k\in 1:q$ (см. рис. 1), так что $\rho(C_q)=\mu_*.$ Пусть для такой матрицы $F$ метод выравнивания сходится к паре векторов $\{x_*,y_*\}$ с какого-либо начального вектора $x_0.$ Согласно алгоритму предельная матрица невязок $H_*$ выравнена и по теореме 2 у матрицы $H_*$ нет других компонент максимального уклонения, кроме тех, которые входят в $C_q.$ Пусть пара $\{x_p,y_p\},$ построенная методом выравнивания, нас\-толь\-ко близка к предельной паре $\{x_*,y_*\},$ что для нее и для пар на всех следующих итерациях выполнено неравенство: $$\begin{matrix} \max\limits_{[i,j]\in {\cal P}\setminus C_q}|H_{p,p}[i,j]|< \min\limits_{[i,j]\in C_q}|H_{p,p}[i,j]|,\\ H_{p,p}[i_k,j_k]>0,\ \ H_{p,p}[i_k,j_{k+1}]<0, \ k\in 1:q.\end{matrix}\eqno(8)$$ Установим скорость сходимости пар $\{x_p,y_p\}$ к предельной паре $\{x_*,y_*\}.$ Напомним, что на каждой итерации метода матрица невязок $H_{p,p}$ выравнена по строкам, матрица $H_{p,p+1}$ выравнена по столбцам. Введем в рассмотрение $q$-мерные векторы $\Delta^{(p)}$ и $\delta^{(p)}$ с компонентами $$ \begin{matrix} \Delta^{(p)}[k]:=H_{p,p}[i_k,j_k]-\mu_*=-H_{p,p}[i_k,j_{k+1}]-\mu_*,\\ \delta^{(p)}[k]:=H_{p,p+1}[i_k,j_k]-\mu_*=-H_{p,p+1}[i_{k-1},j_k]-\mu_*,\\ \ \ k\in 1:q,\ \ i_0=i_q,\ j_{q+1}=j_1.\end{matrix}$$ Быстрота сходимости рассматриваемого процесса зависит от $q$ --- длины альтернанса ($q\geq 2$), и определяется следующей оценкой. \bigskip {\bf Теорема ~3.} {\it Справедливы неравенства $$ \|\Delta^{(p+1)}\|_\infty\leq \|\delta^{(p)}\|_\infty\leq \|\Delta^{(p)}\|_\infty.$$ Более того, полагая $\xi(q)=(1-\frac{q}{2^{q-1}}),$ имеем} $$\begin{matrix} \|\Delta^{(p+r)}\|_{\infty} \leq \xi(q) \cdot \|\Delta^{(p)}\|_{\infty}& \text{\it для нечетного}\ q=2r+1,\\ \|\Delta^{(p+r)}\|_{\infty} \leq \xi(q) \cdot \|\delta^{(p)}\|_{\infty}& \text{\it для четного}\ q=2r. \end{matrix} \eqno(9)$$ Д\,о\,к\,а\,з\,а\,т\,е\,л\,ь\,с\,т\,в\,о. Согласно алгоритму $$H_{p,p+1}[i,j]=H_{p,p}[i,j]- {1\over 2}\Big (\max\limits_{l\in M}H_{p,p}[l,j]+ \min\limits_{l\in M}H_{p,p}[l,j]\Big ).$$ В силу (8) минимальное и максимальное значения $H_{p,p}[i,j]$ в стол\-бце $j_k$ известны. Пользуясь выравненностью матрицы $H_{p,p}$ по строкам, имеем: $$ \begin{matrix} \min\limits_{l\in M}H_{p,p}[l,j_k]=H_{p,p}[i_{k-1},j_k]= -H_{p,p}[i_{k-1},j_{k-1}],\\ \max\limits_{l\in M}H_{p,p}[l,j_k]=H_{p,p}[i_{k},j_k]=-H_{p,p} [i_k,j_{k+1}]. \end{matrix}$$ Значит, на альтернансных индексах ($k\in 1:q$) $$ \begin{matrix} H_{p,p+1}[i_k,j_k]={1\over 2} \Big (H_{p,p}[i_k,j_k]+H_{p,p}[i_{k-1},j_{k-1}]\Big ),\\ -H_{p,p+1}[i_k,j_{k+1}]={1\over 2} \Big (H_{p,p}[i_k,j_k]+H_{p,p}[i_{k+1},j_{k+1}]\Big )=\\ =H_{p,p+1}[i_{k+1},j_{k+1}].\end{matrix}$$ Вычитая из обеих частей первого равенства $\mu_*,$ получим $$\delta^{(p)}[k]= {1\over 2}(\Delta^{(p)}[k-1]+\Delta^{(p)}[k]),\ \ k\in 1:q.\eqno(10)$$ Здесь $\Delta^{(p)}[0]=\Delta{(p)}[q].$ Далее, по алгоритму $$H_{p+1,p+1}[i,j]=H_{p,p+1}[i,j]- {1\over 2}\Big (\max\limits_{l\in N}H_{p,p+1}[i,l]+ \min\limits_{l\in N}H_{p,p+1}[i,l]\Big ).$$ Поступая аналогичным образом с учетом, что матрица $H_{p,p+1}$ выравнена по столбцам, получим $$\Delta^{(p+1)}[k]={1\over 2}(\delta^{(p)}[k+1]+\delta^{(p)}[k]), \ \ k\in 1:q.\eqno(11)$$ Здесь $\delta^{(p)}[q+1]=\delta^{(p)}[1].$ Из (11) и (10) теперь следует первая оценка теоремы: $$\|\Delta^{(p+1)}\|_\infty\leq \|\delta^{(p)}\|_\infty\leq \|\Delta^{(p)}\|_\infty.$$ Далее, подставляя (10) в (11), получим $$\Delta^{(p+1)}[k]= {1\over 4} (\Delta^{(p)}[k-1]+2 \Delta^{(p)}[k] +\Delta^{(p)}[k+1]),\ \ k\in 1:q.\eqno(12)$$ Аналогичным образом, вычисляя матрицу $H_{p+1,p+2},$ получим $$\delta^{(p+1)}[k]= {1\over 4} (\delta^{(p)}[k-1]+2 \delta^{(p)}[k] +\delta^{(p)}[k+1]), \ \ k\in 1:q. \eqno(13)$$ Напомним (см. (4)), что на всех итерациях для матриц $H_{p,p}$ и $H_{p,p+1}$ выполнено равенство $$\frac1{2q}\sum_{k\in 1:q}(H_{p,p}[i_k,j_k]-H_{p,p}[i_k,j_{k+1}])=\rho(C_q)=\mu_*,$$ откуда при любых $p$ имеем $$\sum_{k\in 1:q}\Delta^{(p)}[k]=0,\ \ \sum_{k\in 1:q}\delta^{(p)}[k]= 0.\eqno(14)$$ Чтобы воспользоваться этими равенствами, найдем выражение $\Delta^{(p+r)}[k]$ через $\Delta^{(p)}[k],$ подбирая $r$ таким, чтобы в выражении для $\Delta^{(p+r)}[k]$ содержалось ровно $q$ различных компонент вектора $\Delta^{(p)}$ или $\delta^{(p)}.$ Рассмотрим два случая. Пусть $q$ --- нечетное, $q=2r+1.$ Применим формулу (12) $r$ раз к $\Delta^{(p+r)}[k]$. Каждое $i$-е применение формулы добавляет две различные новые компоненты вектора $\Delta^{(p+r-i)}$ и уменьшает общий множитель в четыре раза. Значит, за $r$ шагов получим $$\Delta^{(p+r)}[k]={1\over 2^{2r}}\sum_{i=1}^q\,a_i^{(r)} \Delta^{(p)}[i].$$ Нетрудно заметить, что $\sum_{i=1}^q\,a_i^{(r)}= 2^{2r}.$ Пользуясь формулой (14), получим $$\Big|\Delta^{(p+r)}[k]\Big|={1\over 2^{2r}}\Big|\sum_{i=1}^q\,(a_i^{(r)}-1) \Delta^{(p)}[i]\Big|\leq \xi(q)\|\Delta^{(p)}\|_\infty, \ \ k\in 1:q,$$ откуда следует требуемая оценка для нечетного $q.$ Пусть $q$ --- четное, $q=2r.$ Найдем выражение $\Delta^{(p+r)}[k]$ через $\delta^{(p)}[k].$ Воспользуемся один раз формулой (11), а затем $r-1$ раз формулой (13). Тогда получим $$\Delta^{(p+r)}[k]={1\over 2^{2r-1}}\sum_{i=1}^q\,b_i^{(r)} \delta^{(p)}[i].$$ Так как $\sum_{i=1}^q\,b_i^{(r)}= 2^{2r-1},$ то в силу (14) получим $$\Big|\Delta^{(p+r)}[k]\Big|={1\over 2^{2r-1}}\Big|\sum_{i=1}^q\,(b_i^{(r)}-1) \delta^{(p)}[i]\Big|\leq \xi(q)\|\delta^{(p)}\|_\infty,\ \ k\in 1:q,$$ откуда следует оценка для четного $q.$ $\ \ \ \blacksquare$ \bigskip {\bf Следствие.} {\it При $q=2$ метод выравнивания конечен. При $q=3$ оценка } (9) {\it точна. При $q=4$ справедливо равенство} $$\| \Delta^{(p+2)}\|_\infty = \frac{1}{2}\|\Delta^{(p+1)}\|_\infty.$$ Д\,о\,к\,а\,з\,а\,т\,е\,л\,ь\,с\,т\,в\,о. Очевидно, что $\xi(q)=0$ при $q=2,$ так что $\Delta^{(p+1)}=\Bbb O.$ При $q=3$ имеем $\xi(3)=\frac{1}{4},$ а из формулы (12) для всех $k\in 1:3$ следует $$\Delta^{(p+1)}[k] =\frac{1}{4} \cdot \Delta^{(p)}[k]+ \frac{1}{4} (\Delta^{(p)}[k-1] + \Delta^{(p)}[k] + \Delta^{(p)}[k+1]).$$ Теперь в силу (14) получаем $\Delta^{(p+1)}[k] = \frac{1}{4} \Delta^{(p)}[k].$ Аналогичная формула справедлива и для $\delta^{(p+1)}[k]$. При $q=4$ применим к $\Delta^{(p+2)}[k]$ сначала формулу (11), потом (13), а затем воспользуемся (14). Тогда получим $$\Delta^{(p+2)}[k]=\frac{1}{4}(\delta^{(p)}[k+1]+\delta^{(p)}[k]).$$ Теперь из (11) следует равенство $\Delta^{(p+2)}[k] = \frac{1}{2} \Delta^{(p+1)}[k]$ для всех $k\in 1:q.$ $\ \ \ \blacksquare$ Таким образом, если матрица $F$ обладает единственным альтернансом, то метод вы\-рав\-ни\-ва\-ния, описанный в п. 4, сходится с быстротой геометрической прогрессии, знаменатель которой равен $\xi(q)=(1-\frac{q}{2^{q-1}}),$ где $q$ --- длина альтернанса ($q\geq 2$). %\bigskip % %Работа выполнена при финансовой поддержке РФФИ (проект N 01-0100231). \bigskip \noindent {\bf Литература} 1. {\it Diliberto S. P. and Straus E. G.} On the approximation of a function of several variables by the sum of functions of fewer variables // Pacif. J. Mathem. 1951, v.1, p.195-210. 2. {\it Аникеич А. А., Грибов А. Б.} Приближение элементов матрицы суммой соответствую\-щих компонент двух векторов// Сб. Исследование операций и статистическое моделирова\-ние. Изд-во ЛГУ, вып.1, 1972, с. 3 - 9. 3. {\it Хавинсон С. Я.} Чебышевская теорема для приближения фу\-нкции двух переменных суммами// Изв. АН СССР, сер. мат., т.33, N 3.1969 г. с. 650-666. \end{document}