Журнал вычислительной математики и математической физики, 2022, T. 62, № 5, стр. 723-741

3.1. Существование, единственность, непрерывность

Приведем результаты о существовании, единственности и непрерывности решения задачи (4). Существование решения, т.е. такого $\hat {u} \in {{\mathbb{C}}^{r}}$, что

очевидно, поэтому перейдем сразу к вопросу о единственности решения. Здесь и далее будем обозначать нижним индексом столбец матрицы, а верхним индексом строку. Введем понятие чебышёвской системы векторов.

Определение 1. Столбцы матрицы $V \in {{\mathbb{C}}^{{n \times r}}}$ образуют чебышёвскую систему векторов, если любые r строк матрицы V линейно независимы.

Это понятие тесно связано с единственностью решения задачи наилучшего приближения. А именно, верна следующая

Теорема 2 (Хаар [10]). Пусть матрица $V \in {{\mathbb{C}}^{{n \times r}}}$ и $n > r$. Тогда для того, чтобы для любого вектора $a \in {{\mathbb{C}}^{n}}$ существовал единственный вектор $\hat {u} \in {{\mathbb{C}}^{r}}$ ее наилучшего равномерного приближения необходимо и достаточно, чтобы столбцы матрицы V образовывали чебышёвскую систему.

Также верно

Утверждение 2. Пусть столбцы матрицы $V \in {{\mathbb{C}}^{{n \times r}}}$, где $n > r$, образуют чебышёвскую систему и $V\widehat u$ — вектор наилучшего равномерного приближения. Тогда, по крайней мере, в r + 1 точке достигается максимальное значение, т.е. существуют ${{i}_{1}}, \ldots ,{{i}_{{r + 1}}}$, в которых выполняется равенство

Доказательство. Пусть точек, в которых достигается максимальное по модулю значение ${{r}_{1}} < r + 1$. Тогда решив систему с ${{r}_{1}}$ уравнениями и $r$ неизвестными, строки которой линейно независимы, мы можем получить вектор $p \in {{\mathbb{C}}^{r}}$ такой, что

Но тогда вектор $V(\widehat u + \delta p)$ при достаточно малом $\delta $ отклоняется от a меньше, чем $V\hat {u}$. Пришли к противоречию.

Рассмотрим вопрос о непрерывности решения.

Теорема 3 (Никольский [10]). Пусть система столбцов матрицы $V \in {{\mathbb{C}}^{{n \times r}}}$, где $n > r$, является чебышёвской. Тогда коэффициенты вектора наилучшего равномерного приближения $\widehat u$ непрерывно зависят от приближаемого вектора a, и системы столбцов V, т.е. $\forall \varepsilon > 0$ $\exists \delta = \delta (a,V,\varepsilon ) > 0$ такое, что если ${\text{||}}a - b{\text{|}}{{{\text{|}}}_{\infty }} + \,{\text{||}}V - W{\text{||}} < \delta $, то ${\text{||}}\hat {u}(a,V) - \hat {u}(b,W){\text{|}}{{{\text{|}}}_{\infty }} < \varepsilon $, где через $\widehat u(a,V)$ и $\widehat u(b,W)$ обозначены коэффициенты оптимального решения для векторов a по системе V и b по системе W соответственно.

3.2. Характеристические множества

Пусть J обозначает набор индексов $J = \left\{ {1,2, \ldots ,n} \right\},$ а $J{\kern 1pt} '$ и $J{\kern 1pt} ''$ – некоторые подмножества J. Пусть

где через $V(J{\kern 1pt} ')$ обозначена подматрица матрицы V, содержащая строки с номерами из множества $J{\kern 1pt} '$, а через $a(J{\kern 1pt} ')$ обозначен подвектор вектора a, содержащий элементы с номерами из $J{\kern 1pt} '$.

Определение 2. Множество $J{\kern 1pt} '$ называется характеристическим множеством, если $\mu (J) = \mu (J{\kern 1pt} ')$ и для любого подмножества $J{\kern 1pt} '' \subsetneq J{\kern 1pt} '$ $\mu (J{\kern 1pt} '') < \mu (J)$.

Далее мы докажем, что если система столбцов матрицы V линейно независима, то существует по крайней мере одно характеристическое множество, содержащее не более $2r + 1$ точек в комплексном и не более $r + 1$ точек в вещественном случае.

Для дальнейшего нам понадобятся следующие обозначения [10], [11]. Пусть $\lambda \geqslant 0$ и пусть

Утверждение 3. Верны следующие вложения

Лемма 1. Пусть столбцы матрицы V линейно независимы. Тогда множество $K(j,\lambda )$ выпукло и замкнуто, а множество $K(J,\lambda )$ ограничено для любых $\lambda \geqslant 0$.

Доказательство. Докажем замкнутость множеств $K(j,\lambda )$. Пусть u₁ – предельная точка множества $K(j,\lambda )$. Тогда в любой ее окрестности существуют точки $u \in K(j,\lambda )$

Так как $u \in K(j,\lambda )$, то $F(j,u) \leqslant \lambda $. Функция

очевидно непрерывна по u при любом фиксированном j. Тогда для любого $\varepsilon > 0$ существует $\delta > 0$ такая, что если ${\text{|}}u - {{u}_{1}}{\text{|}} < \delta $, то ${\text{|}}F(j,{{u}_{1}}) - F(j,u){\text{|}} < \varepsilon $. Таким образом, имеем для любого $\varepsilon > 0$, откуда ${{u}_{1}} \in K(j,\lambda )$. Замкнутость доказана.

Докажем ограниченность $K(J,\lambda )$. Рассмотрим вектор Vu при ${\text{||}}u{\text{|}}{{{\text{|}}}_{1}} = 1$. Величина ${\text{||}}Vu{\text{|}}{{{\text{|}}}_{\infty }}$ является непрерывной по u функцией на компактном множестве, поэтому достигает в некоторой точке своего минимального значения

Поскольку столбцы V линейно независимы, любая их нетривиальная линейная комбинация не равна 0 и $M > 0$.

Пусть ${\text{||}}u{\text{|}}{{{\text{|}}}_{1}} \geqslant \frac{{C + 1}}{M}$, где $C > 0$ — некоторая константа. Тогда

Тогда при ${\text{||}}u{\text{|}}{{{\text{|}}}_{1}} \geqslant \frac{{C + 1}}{M}$ не может быть выполнено условие $F(J,u) \leqslant \lambda = C\, - \,{\text{||}}a{\text{|}}{{{\text{|}}}_{\infty }}$, т.е. $u \notin K(j,\lambda )$ при $\lambda \leqslant C - \,{\text{||}}a{\text{|}}{{{\text{|}}}_{\infty }}$. В силу произвольности $C$ ограниченность доказана.

Докажем выпуклость множества $K(j,\lambda )$. Пусть ${{u}_{1}},{{u}_{2}} \in K(j,\lambda )$, т.е. $F(j,{{u}_{1}}) \leqslant \lambda $ и $F(j,{{u}_{2}}) \leqslant \lambda $. Нужно доказать, что $F(j,\tau {{u}_{1}} + (1 - \tau ){{u}_{2}}) \leqslant \lambda $ для любого $\tau \in (0,1)$:

Обозначим через M_k множество всевозможных упорядоченных подмножеств J_k, состоящих из k элементов ${{i}_{1}}, \ldots ,{{i}_{k}}$, взятых из множества J. Обозначим через ${{\mu }_{k}}(J)$ точную верхнюю грань наименьших отклонений от нуля функции $F(j,u)$ на всевозможных подмножествах ${{J}_{k}} \in {{M}_{k}}$:

Легко доказать

Утверждение 4. Верно неравенство ${{\mu }_{k}}(J) \leqslant {{\mu }_{{k + 1}}}(J) \leqslant \mu (J) \forall k$.

Для дальнейшего анализа понадобится следующая

Теорема 4 (Хелли). Если множество K замкнутых выпуклых множеств точек $x \in {{\mathbb{R}}^{r}}$ содержит не менее $r + 1$ множеств (среди которых могут быть одинаковые), пересечение любых $r + 1$ множеств из K не пусто и пересечение некоторого конечного числа множеств из K ограничено, то пересечение всех множеств из K не пусто.

Основываясь на теореме Хелли, докажем следующий результат.

Теорема 5 (Шнирельман [10]). Если существует такое ${{\lambda }_{0}} > {{\mu }_{{2r + 1}}}$ (${{\lambda }_{0}} > {{\mu }_{{r + 1}}}$ в вещественном случае), что для любого j и любом $\lambda $, ${{\mu }_{{2r + 1}}} < \lambda < {{\lambda }_{0}}$ (${{\mu }_{{r + 1}}} < \lambda < {{\lambda }_{0}}$ в вещественном случае), множество $K(j,\lambda )$ замкнуто и выпукло, и пересечение некоторого конечного числа множеств $K(j,\lambda )$ ограничено, то ${{\mu }_{{2r + 1}}}(J) = \mu (J)$ (${{\mu }_{{r + 1}}}(J) = \mu (J)$ в вещественном случае).

Доказательство. Пусть $k = r + 1$ в вещественном случае и $k = 2r + 1$ в комплексном. В силу конечности множеств J_k и M_k имеем, что максимумы и минимумы достигаются, поэтому при любом $\lambda > {{\mu }_{k}}(J)$ множество $K({{J}_{k}},\lambda )$ не пусто. Кроме того, так как $K(j,\lambda )$ по условию выпукло и замкнуто, то

не пусто и выпукло для любого ${{J}_{k}} \in {{M}_{k}}$.

Убедимся, что выполнены все условия теоремы Хелли. В качестве совокупности множеств K возьмем множества $K(j,\lambda )$, $j \in J$. По условию теоремы они замкнуты и выпуклы, и пересечение некоторого конечного числа этих множеств ограничено. В вещественном случае то, что пересечение любых $j + 1$ множеств не пусто, эквивалентно тому, что $K({{J}_{{r + 1}}},\lambda )$ не пусто, что было показано выше. В комплексном случае нам нужно работать с пространством ${{\mathbb{C}}^{r}}$, которое мы отождествим с ${{\mathbb{R}}^{{2r}}}$, поэтому нам требуется, чтобы пересечение любых $2r + 1$ множеств  было не пусто, что также было показано выше. Итак, все условия теоремы Хелли выполнены и мы имеем, что

не пусто, замкнуто, выпукло и ограничено.

Пусть последовательность $\{ {{\lambda }_{t}}\} $ убывающая, ${{\mu }_{k}} < {{\lambda }_{t}} < {{\lambda }_{0}}$ и стремится к ${{\mu }_{k}}$. При этом $K(J,{{\lambda }_{{t + 1}}}) \subset K(J,{{\lambda }_{t}})$ и пересечение

не пусто, замкнуто и ограничено. Пусть ${{u}_{0}} \in K$. Это значит, что ${{u}_{0}} \in K(J,{{\lambda }_{t}})$, что значит, что $F(j,{{u}_{0}}) \leqslant {{\lambda }_{t}}$ для любых $j \in J$ и любого t. В пределе при $t \to \infty $ получаем, что $F(j,{{u}_{0}}) \leqslant {{\mu }_{k}}(J)$ для любого $j \in J$, откуда

Но, как было отмечено выше, ${{\mu }_{k}}(J) \leqslant \mu (J)$.

Эта теорема позволяет сформулировать следующий результат.

Теорема 6. Пусть столбцы матрицы $V \in {{\mathbb{C}}^{{n \times r}}}$, где $n \geqslant r$ линейно независимы и вектор a не принадлежит образу матрицы V. Тогда существует по крайней мере одно характеристическое множество, состоящее не более чем из $2r + 1$ точек в комплексном случае и $r + 1$ точек в вещественном. Кроме того, если система столбцов матрицы V является чебышёвской, то любое характеристическое множество состоит не менее чем из $r + 1$ точек.

Доказательство. Результат для произвольной системы сразу следует из леммы 0 и теоремы 5. В случае чебышёвской системы на любом множестве из r и менее точек можно решить систему и точно приблизить вектор в этих точках, а поскольку множество является характеристическим, то это противоречит условию, что a не принадлежит образу V.

3.3. О задаче поиска равноудаленных точек

Введем понятие равноудаленной точки системы.

Определение 3. Пусть $V \in {{\mathbb{R}}^{{(r + 1) \times r}}}$ и $a \in {{\mathbb{R}}^{{r + 1}}}$. Пусть система

несовместна. Будем называть точку $u$ равноудаленной точкой системы, если

Будем называть точку $u$ наилучшей равноудаленной точкой системы, если она является равноудаленной и величина $\rho (u)$ минимальна.

Приведем результаты [12] о том, как устроено множество всех равноудаленных точек системы в вещественном случае.

Пусть

и ${{\hat {a}}_{j}} = ({{a}_{1}},{{a}_{2}}, \ldots ,{{a}_{{j - 1}}},{{a}_{{j + 1}}}, \ldots ,{{a}_{{r + 1}}}{{)}^{{\text{т}}}}$. Тогда обозначим через ${{D}_{j}} = \det {{\hat {V}}_{j}}$ и ${{\hat {u}}^{j}}$ решение системы ${{\hat {V}}_{j}}u = {{\hat {a}}_{j}}$. Верны следующие теоремы о множестве равноудаленных точек системы.

Теорема 7 (Дзядык [12]). Пусть задана несовместная система уравнений $Vu = a$, где $V \in {{\mathbb{R}}^{{(r + 1) \times r}}}$ и $a \in {{\mathbb{R}}^{{r + 1}}}$. Тогда верно следующее.

1) При каждом $j = 1, \ldots ,r + 1$ имеет место равенство

2) Для любых действительных k_j, $j = 1, \ldots ,r + 1$, таких, что

точка u, определяемая по формулегдеявляется равноудаленной точкой системы $Vu = a$, при этом |ρ| выражает V-расстояние от точки $u$ до a.

3. Всякая V-равноудаленная точка u системы $Vu = a$ может быть при некоторых действительных k_j представлена по формуле выше. При этом k_j могут, в частности, быть выражены по формуле

Теорема 8 (Дзядык [12]). Пусть задана несовместная система уравнений $Vu = a$, где $V \in {{\mathbb{R}}^{{(r + 1) \times r}}}$ и $a \in {{\mathbb{R}}^{{r + 1}}}$. Тогда наилучшая равноудаленная от системы точка u определяется по формуле

где

Доказательство. Достаточно заметить, что величина

принимает наименьшее значение, когда все слагаемые сонаправлены, т.е. ${{e}^{{i{{k}_{1}}}}} = {{e}^{{i{{k}_{2}}}}} = \ldots = {{e}^{{i{{k}_{{r + 1}}}}}}$.

3.4. Критерии оптимальности

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

Теорема 9 (Колмогоров). Пусть заданы система векторов с матрицей $V \in {{\mathbb{C}}^{{n \times r}}}$ и вектор $a \in {{\mathbb{C}}^{n}}$, который следует приблизить линейной комбинацией столбцов V. Для того чтобы вектор $V\widehat u$ был для a вектором наилучшего равномерного приближения, необходимо и достаточно, чтобы на множестве $E = E(V\widehat u)$ всех точек, на которых для вектора $V\widehat u$ достигается максимальное по модулю значение разности, для всех векторов вида $Vu$ выполнялось

Доказательство. Необходимость. Пусть $V\widehat u$ является вектором наилучшего равномерного приближения для a. От противного, пусть

для некоторого вектора $u \in {{\mathbb{C}}^{r}}$. Пусть

Докажем, что тогда вектор $V(\widehat u + \lambda u)$ приближает вектор a лучше.

1. Пусть $j \in E$. Тогда

2. Пусть $j \notin E$. Тогда имеем

Отсюда следует, что вектор $V(\widehat u + \lambda u)$ приближает вектор a лучше. Получили противоречие.

Достаточность. Пусть выполнено условие критерия Колмогорова с вектором коэффициентов $\widehat u$ и пусть $u \in {{\mathbb{C}}^{r}}$ произвольный. Рассмотрим вектор $w = V(u - \hat {u})$. Выберем индекс ${{j}_{0}}$, для которого выполняется неравенство для вектора w:

Тогда имеем

Отсюда видно, что для любого вектора $u \in {{\mathbb{C}}^{r}}$, вектор $\widehat u$ дает приближение не хуже, т.е. является оптимальным.

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

Лемма 2. Пусть u_ij, $i = 1, \ldots ,m$, $j = 1, \ldots ,n$ – некоторые числа. Для того чтобы существовали числа ${{\delta }_{i}} \geqslant 0$, $i = 1, \ldots ,m$, не все равные нулю и такие, что

необходимо и достаточно, чтобы для любой системы чисел c_j, $j = 1, \ldots ,n$, неравенстване выполнялись одновременно.

Доказательство. Необходимость. Пусть при ${{\delta }_{i}} \geqslant 0$, $i = 1, \ldots ,m$, выполнено

Тогда имеем

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

Достаточность. Введем величину

Так как функция ${v}$ непрерывна на компактном множестве, то она принимает минимальное значение ${{{v}}_{0}}$ при ${{\delta }_{i}} = \delta _{i}^{0}$. Покажем, что условие леммы эквивалентно тому, что если неравенства $\operatorname{Re} \sum\limits_{j = 1}^n {{c}_{j}}{{u}_{{ij}}} > 0$ не могут быть выполнены одновременно, то ${{{v}}_{0}} = 0$.

Докажем это от противного. Пусть неравенства не могут быть выполнены одновременно ни при каком выборе c_j, но ${{{v}}_{0}} > 0$. Возьмем

и пусть при таком выборе c_j, не ограничивая общности, не выполнено неравенство при i = m:

Пусть

Выберем ${{\delta }_{i}}$ следующим образом:

и покажем, что ${v}({{\delta }_{1}}, \ldots ,{{\delta }_{m}}) < {{{v}}_{0}}$. Действительно,

Как было отмечено выше,

но $\lambda \geqslant 0$, $1 - \lambda > 0$, откуда

Пришли к противоречию с оптимальностью ${{{v}}_{0}}$, следовательно, ${{{v}}_{0}} = 0$.

Замечание 1. Если все ${{u}_{{ij}}} \in \mathbb{R}$, то c_j достаточно выбирать вещественными.

Используя эту лемму и критерий Колмогорова, докажем другой критерий оптимальности поэлементного приближения

Теорема 10 (Ремез). Пусть заданы система векторов с матрицей $V \in {{\mathbb{C}}^{{n \times r}}}$ и вектор $a \in {{\mathbb{C}}^{n}}$, который следует приблизить линейной комбинацией столбцов V. Пусть вектор $V\widehat u$ достигает максимальных по модулю значений разности в позициях $E = \{ {{i}_{1}}, \ldots ,{{i}_{t}}\} $. Тогда $V\widehat u$ является вектором наилучшего равномерного приближения для $a$, тогда и только тогда, когда существуют ${{\delta }_{k}} \geqslant 0$, $k = 1, \ldots ,t$, не все из которых равны нулю, такие, что

Доказательство. Достаточность. Пусть выполнены условия

Пусть ${{u}_{{ij}}} = \overline {({{a}_{k}} - {{{\widehat u}}^{{\text{т}}}}{{{v}}^{k}})} {v}_{j}^{k}$ в терминах предыдущей леммы. Тогда, согласно лемме, условия

не выполнены одновременно для любого выбора c_j. Принимая во внимание, что $\sum\limits_{j \in E} {{c}_{j}}{v}_{j}^{k}$ задает произвольный вектор вида Vc на строках из E, получаем, что выполнен критерий Колмогорова и $V\widehat u$ является оптимальным приближением.

Необходимость. Если $V\widehat u$ – оптимальный, то выполнен критерий Колмогорова:

следовательно, не выполнены одновременно и тогда по лемме существуют ${{\delta }_{k}} \geqslant 0$, удовлетворяющие условиям Ремеза.

Замечание 2. Всегда существует оптимальное решение, в котором максимальные значения достигаются в t точках, где $1 \leqslant t \leqslant 2r + 1$ в комплексном случае и $1 \leqslant t \leqslant r + 1$ в вещественном, причем условие критерия Ремеза выполняется с ${{\delta }_{k}} > 0$.

Замечание 3. Заметим, что условие Ремеза может быть переписано в виде

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

Это система с $r + 1$ переменной и $r$ уравнениями, которая имеет нетривиальное решение. Найдем это решение. Тогда

Поскольку чебышёвская система векторов всегда имеет характеристическое множество, состоящее ровно из $r + 1$ элементов, для чебышёвской системы из $r + 1$ уравнений и $r$ неизвестных, уравнение (5) задает знаки величин $\overline {({{a}_{k}} - {{{\hat {u}}}^{{\text{т}}}}{{{v}}^{k}})} $ для наилучшей равноудаленной точки. Кроме того, модули ${\text{|}}{{a}_{k}} - {{\hat {u}}^{{\text{т}}}}{{{v}}^{k}}{\text{|}}$ равны, что позволяет в вещественном случае выписать систему из $r$ с $r$ неизвестными, решением которой будет наилучшая равноудаленная точка. Таким образом, наилучшая равноудаленная точка чебышёвской системы $(r + 1) \times r$ может быть найдена за $O({{r}^{3}})$ операций с помощью двух решений систем линейных уравнений.

4.1. Комбинаторная формула решения

Пусть решается задача приближения вектора $a \in {{\mathbb{R}}^{n}}$ по системе векторов $V \in {{\mathbb{R}}^{{n \times r}}}$. Пусть $\widetilde V \in {{\mathbb{R}}^{{(r + 1) \times r}}}$ и $\tilde {a} \in {{\mathbb{R}}^{{r + 1}}}$. Тогда через $\left[ {\begin{array}{*{20}{c}} {\widetilde V}&{\widetilde a} \end{array}} \right] \in {{\mathbb{R}}^{{(r + 1) \times (r + 1)}}}$ мы обозначим матрицу, первые $r$ столбцов которой являются столбцами матрицы $\widetilde V$, а последний столбец $\tilde {a}$. Обозначим через $V({{i}_{1}}, \ldots ,{{i}_{k}})$ подматрицу матрицы V, содержащую строки ${{i}_{1}}, \ldots ,{{i}_{k}}$. Аналогично обозначим через $a({{i}_{1}}, \ldots ,{{i}_{k}})$ подвектор вектора a, содержащий элементы ${{i}_{1}}, \ldots ,{{i}_{k}}$. Кроме того, обозначим через ${{\widetilde V}_{{\backslash k}}}$ подматрицу матрицы $\widetilde V$, в которой удалена k-я строка.

Теорема 11. Пусть решается задача наилучшего равномерного приближения вектора $a \in {{\mathbb{R}}^{n}}$ по чебышёвской системе векторов $V \in {{\mathbb{R}}^{{n \times r}}}$. Пусть

Тогда получаем

Доказательство. По теореме 5 имеем, что

а согласно определению верно

Остается применить теорему 8 для получения явного вида $\mu ({{J}_{{r + 1}}})$.

4.2. Аналог теоремы о чебышёвском альтернансе

В утверждении 2 было показано, что для оптимального решения в векторе невязки достигаются максимальные по модулю значения по крайней мере в $r + 1$ позициях. Широко известен результат о чебышёвском альтернансе для непрерывных функций. В этом случае помимо того, что в векторе невязки достигаются максимальные по модулю значения, имеет место чередование знаков. Аналогичный результат может быть доказан и в матричном случае.

Лемма 3. Пусть решается задача наилучшего равномерного приближения вектора $a \in {{\mathbb{R}}^{{n + 1}}}$ по чебышёвской системе векторов $V \in {{\mathbb{R}}^{{(n + 1) \times n}}}$ и вектор z* является вектором наилучшего равномерного приближения (наилучшей равноудаленной точкой системы). Обозначим через $w = a - Vz{\text{*}}$ вектор невязки. Тогда знаки величин

чередуются.

Доказательство. В обозначениях теорем 7 и 8 имеем

Кроме того, из теоремы 7 имеем

где не зависит от j. Согласно определению ${{z}^{j}}$ получаем где ${{\widetilde a}_{j}} = ({{{v}}^{j}},{{z}^{j}})$. Тогда имеем

Отсюда

поскольку

Обозначая через

получаем, что

А тогда верно

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

4.3. Обобщенный алгоритм Ремеза для матриц

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

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

Заметим, что теорема 11 уже позволяет решать задачу (4) за конечное число операций. Для этого достаточно перебрать всевозможные варианты характеристических множеств (все $r + 1$-элементные подмножества строк) и решить для каждого из них задачу о поиске наилучшей равноудаленной точки. Однако находить характеристическое множество можно намного быстрее.

Приведем алгоритм решения задачи о наилучшем равномерном приближении в вещественном случае. Пусть имеются матрица $V \in {{\mathbb{R}}^{{n \times r}}}$ и вектор $a \in {{\mathbb{R}}^{n}}$.

1. Выберем произвольное множество из $r + 1$ индексов строк матрицы V. Обозначим это множество через ${{I}_{1}}$ и возьмем $t = 1$.

2. Решим задачу о наилучшем равномерном приближении для матрицы $V({{I}_{t}})$ и вектора $a({{I}_{t}})$. Эта задача может быть решена за $O({{r}^{3}})$ операций для чебышёвской системы векторов. Получим решение ${{u}_{t}}$.

3. Вычислим невязку ${{w}_{t}} = V{{u}_{t}} - a$ и найдем в векторе ${{w}_{t}}$ максимальный по модулю элемент. Эта операция требует $O(nr)$ операций. Обозначим позицию максимального по модулю элемента ${{j}_{t}}$. Если ${{j}_{t}} \in {{I}_{t}}$, то согласно замечанию к критерию Ремеза, множество ${{I}_{t}}$ является характеристическим и ${{u}_{t}}$ является решением задачи наилучшего равномерного приближения.

4. Если ${{j}_{t}} \notin {{I}_{t}}$, то попробуем заменить каждый из элементов множества ${{I}_{t}}$ на ${{j}_{t}}$. Пусть ${{I}_{t}} = \{ i_{1}^{{\text{т}}},i_{2}^{t}, \ldots ,i_{{r + 1}}^{t}\} $ и пусть $I_{t}^{k} = {{I}_{t}}{{\backslash }}\{ i_{k}^{t}\} \cup {{j}_{t}}$. Решим задачу с матрицей $V(I_{t}^{k})$ и вектором $a(I_{t}^{k})$ и найдем максимум модуля невязки на множестве $I_{t}^{k}$, $w_{t}^{k} = V(I_{t}^{k})u_{t}^{k} - a(I_{t}^{k})$. Пусть $l = \mathop {\arg \max }\limits_k {\text{||}}w_{t}^{k}{\text{|}}{{{\text{|}}}_{\infty }}$. Это шаг требует $O({{r}^{4}})$ операций.

5. ${{I}_{{t + 1}}} = I_{t}^{l}$, $t = t + 1$, и перейдем к шагу 2.

Теорема 12. Пусть система векторов $V \in {{\mathbb{R}}^{{n \times r}}}$ является чебышёвской и вектор $a \in {{\mathbb{R}}^{n}}$. Тогда обобщенный алгоритм Ремеза находит решение задачи о наилучшем равномерном приближении за конечное число операций.

Доказательство. Пусть ${{I}_{t}}$ – текущее множество индексов и ${{w}_{t}} = V{{u}_{t}} - a$. Пусть

Пусть в векторе ${{w}_{t}}$ максимальный по модулю элемент достигается в позиции ${{j}_{t}}$. Тогда рассмотрим задачу о наилучшем равномерном приближении для подматрицы, взятой на множестве строк с номерами ${{I}_{t}} \cup \{ {{j}_{t}}\} $. Для этой задачи существует характеристическое множество из $r + 1$ элементов. Заметим, что оно не может целиком состоять из элементов множества ${{I}_{t}}$, поскольку для оптимального решения на этом множестве в позиции ${{j}_{t}}$ достигается строго большее значение элемента невязки. Это означает, что характеристическое множество содержит ${{j}_{t}}$ и r элементов из множества ${{I}_{t}}$, т.е. получается заменой в ${{I}_{t}}$ одного из элементов на ${{j}_{t}}$. Обозначим это множество через ${{\hat {I}}_{t}}$. Покажем, что при этом ошибка оптимального приближения на новом множестве ${{\hat {I}}_{t}}$ строго больше, чем на множестве ${{I}_{t}}$. Действительно, пусть при оптимальном приближении на множестве ${{I}_{t}}$ получается ошибка $\delta $, а на элементе в позиции ${{j}_{t}}$ соответствующее решение дает ошибку $\varepsilon $. Заметим, что $\varepsilon > \delta $. Аналогично, пусть при оптимальном приближении на множестве ${{\hat {I}}_{t}}$ на самом множестве получается ошибка ${{\delta }_{1}}$, а на удаленном из ${{I}_{t}}$ элементе ошибка ${{\varepsilon }_{1}}$. Заметим, что поскольку ${{\hat {I}}_{t}}$ — характеристическое множество, то $\varepsilon \leqslant {{\delta }_{1}}$. Тогда получаем

откуда следует, что ошибка оптимального приближения на новом множестве ${{\hat {I}}_{t}}$ строго больше, чем ошибка оптимального приближения на множестве ${{I}_{t}}$. Откуда следует, что

Но поскольку существует конечное число $r + 1$–элементных подмножеств, последовательность $\{ {{E}_{t}}\} $ не может быть бесконечной и достигает своего максимального значения на некотором множестве, что согласно рассуждениям теоремы 11 говорит о том, что найденное множество является характеристическим и было построено оптимальное решение.

5.1. Необходимое условие оптимальности

В [9] было доказано необходимое условие оптимальности решения задачи (7). В свете полученных выше результатов мы можем легко получить это условие, а также обобщить его на случай произвольного ранга. Пусть пара $(\widehat U,\widehat V)$ является решением задачи (7). Тогда матрица $\widehat U$ является решением задачи

В матрице $A - \widehat U{{\widehat V}^{{\text{т}}}}$ в некоторой позиции $(i,j)$ достигается максимальный по модулю элемент. Рассмотрим задачу для i-й строки матрицы

Ясно, что ${{\widehat u}^{i}}$ является оптимальным решением задачи (8), в противном случае можно было бы заменить i-ю строку матрицы $\widehat U$ на оптимальное решение и получить лучший результат в задаче (7). В силу оптимальности решения мы имеем, что в векторе ${{a}^{i}} - {{\widehat u}^{i}}{{\widehat V}^{{\text{т}}}}$ максимальное по модулю значение достигается в $r + 1$ позиции и знаки невязки и определителей матрицы $\widehat V$ в этих позициях чередуются (см. лемму 3). Для получения необходимого условия из [9] достаточно заметить, что при $r = 1$ определителями являются элементы вектора $\widehat V$, а знак ${{\widehat u}^{i}}$, очевидно, не меняется в пределах одного столбца, откуда следует утверждение 1. В случае произвольного ранга в каждом столбце и каждой строке, в которых достигается максимальный по модулю элемент, максимальное по модулю значение достигается в $r + 1$ позиции и знаки невязки и определителей чередуются согласно лемме 3.

5.2. Метод решения

Построим итерационный процесс решения задачи (7). Пусть задана некоторая матрица $A \in {{\mathbb{R}}^{{m \times n}}}$. Пусть также задана некоторая чебышёвская матрица ${{U}_{0}}$. Найдем оптимальное чебышёвское приближение $A = {{U}_{0}}{{V}^{{\text{т}}}}$ и обозначим результат ${{V}_{1}}$. Предположим, что система векторов ${{V}_{1}}$ чебышёвская. Затем найдем оптимальное чебышёвское приближение $A = UV_{1}^{{\text{т}}}$ и обозначим результат через ${{U}_{1}}$, снова предполагая, что система ${{U}_{1}}$ чебышёвская. Найдем оптимальное чебышёвское приближение $A = {{U}_{1}}{{V}^{{\text{т}}}}$ и обозначим результат через ${{V}_{2}}$. Продолжая по описанной схеме, заметим, что при этом величина ${{\rho }_{k}} = {\text{||}}A - {{U}_{k}}V_{k}^{{\text{т}}}{\text{|}}{{{\text{|}}}_{C}}$ не возрастает и ограничена снизу и, следовательно, сходится.