| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Корректная постановка задачи о решении систем линейных алгебраических уравнений Е. Е. Тыртышниковab a Институт вычислительной математики им. Г. И. Марчука Российской академии наук, г. Москва b Московский центр фундаментальной и прикладной математики
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 10, Pages DOI: https://doi.org/10.4213/sm9706e 
Реферативные базы данных:
    § 1. Введение и цели исследованияИзвестно, что для произвольной системы линейных алгебраических уравнений $Ax=b$ существует однозначно определенное нормальное псевдорешение. При использовании естественного скалярного произведения оно определяется по методу наименьших квадратов как вектор наименьшей длины среди всех векторов, минимизирующих длину невязки. Если матрица $A$ имеет неполный ранг, то задача о поиске нормального псевдорешения является некорректной, так как непрерывная зависимость от элементов матрицы $A$ отсутствует. Вполне типична ситуация, когда вместо системы $Ax=b$ для решения предлагается приближенная система $\widetilde{A} \widetilde{x}=\widetilde{b}$, где
$$
\begin{equation*}
\| \widetilde{A} - A \| \leqslant \mu, \qquad \| \widetilde{b} - b \| \leqslant \delta.
\end{equation*}
\notag
$$
При этом следует понимать, что малые значения погрешностей $\mu$ и $\delta$ не гарантируют какой-либо близости нормальных псевдорешений исходной и приближенной системы. В методе регуляризации А. Н. Тихонова (см. [1]–[4]) рассматриваются регуляризированные системы
$$
\begin{equation*}
(\widetilde{A}^* \widetilde{A} + \alpha I) x_\alpha=\widetilde{A}^* \widetilde{b}
\end{equation*}
\notag
$$
и утверждается, что при $\mu, \delta \to 0$ параметр можно выбрать таким образом, что вектор $x_\alpha$ будет сходиться к нормальному псевдорешению системы $Ax=b$. Тем не менее нельзя не задуматься о том, какой физический смысл вкладывается в поиск объекта, который может сколь угодно сильно измениться при малых возмущениях исходных данных. В задачах такого рода, по всей видимости, не учитывается какая-то важная дополнительная информация, которая могла бы помочь переформулировать саму задачу таким образом, чтобы она стала корректной, а методы решения предлагалось бы искать уже для задачи в новой постановке. Можно заметить, что обязательным атрибутом методов регуляризации является привлечение той или иной дополнительной информации. Однако в огромном множестве работ, посвященных развитию и применениям методов регуляризации, новая формулировка, использующая дополнительную информацию, обычно не предъявляется явным образом. В этом плане исключительный интерес представляет работа А. Н. Тихонова [5]. В ней предлагается включить в постановку задачи о решении систем линейных алгебраических уравнений указанные выше параметры точности $\mu$ и $\delta$. В качестве исходных данных в [5] предлагается рассмотреть целый класс систем, эквивалентных по точности. Отдельный класс определяется матрицей $A_0$, правой частью $b_0$ и двумя параметрами точности $\mu$ и $\delta$. Рассматриваются все системы вида $Ax=b$, где
$$
\begin{equation*}
\| A - A_0 \| \leqslant \mu, \qquad \| b - b_0 \| \leqslant \delta.
\end{equation*}
\notag
$$
В качестве нормального решения для класса $\Sigma$ предлагается взять вектор наименьшей длины среди всех решений всевозможных совместных систем в данном классе. Основной теоремой в [5] является утверждение о том, что при использовании фробениусовых (евклидовых) норм нормальное решение класса, содержащего хотя бы одну совместную систему, существует и единственно. Предлагается также метод его вычисления и обсуждается некоторая связь с идеей регуляризации. Теорема о корректности тихоновского нормального решения тем не менее в [5] не приводится. Цель настоящей работы – исследовать корректность тихоновской постановки. Основной новый результат – это теорема о непрерывной зависимости тихоновского нормального решения от исходных данных $A_0$, $b_0$, $\mu$, $\delta$. Кроме этого, изучаются возможности получения некоторых обобщений при использовании норм, отличных от фробениусовых. § 2. Единственность тихоновского решенияПусть на пространствах $\mathbb{C}^n$ и $\mathbb{C}^m$ заданы векторные нормы, а норма для $(m \times n)$-матриц подчиняется неравенству $\|Ax\| \leqslant \|A\| \,\|x\|$ при любом выборе вектора $x$ и матрицы $A$. Пространства $\mathbb{C}^n$ и $\mathbb{C}^m$ будем называть основным пространством и пространством образов соответственно. Класс систем
$$
\begin{equation*}
\Sigma=\Sigma (A_0, b_0, \mu, \delta ), \qquad A_0 \in \mathbb{C}^{m \times n}, \quad b_0 \in \mathbb{C}^m, \quad \mu, \nu > 0,
\end{equation*}
\notag
$$
состоит из всех систем вида $Ax=b$, где
$$
\begin{equation*}
\|A-A_0\| \leqslant \mu, \qquad \|b-b_0\| \leqslant \delta.
\end{equation*}
\notag
$$
Системы могут быть как совместными, так и несовместными. Совместность индивидуальной системы $A_0x=b_0$ не предполагается, но хотя бы одна система данного класса должна быть совместной. Среди векторов, которые являются решениями совместных систем класса $\Sigma$, выберем векторы наименьшей нормы. Условимся называть их тихоновскими решениями. Множество всех тихоновских решений обозначим
$$
\begin{equation*}
N_0=\bigl\{ \arg\min \|x\| \colon \|Ax-b_0\| \leqslant \delta, \, \|A-A_0\| \leqslant \mu \bigr\}.
\end{equation*}
\notag
$$
Из соображений компактности сразу следует, что $N_0 \ne \varnothing$. Следуя работе [5], введем также важные для нас множества
$$
\begin{equation*}
\begin{gathered} \, N_1=\bigl\{ \arg\min \|x\| \colon \|Ax-b_0\|=\delta, \, \|A-A_0\|=\mu \bigr\}, \\ N_2=\bigl\{ \arg\min \|x\| \colon \|A_0x-b_0\|=\mu \|x\| + \delta \bigr\}. \end{gathered}
\end{equation*}
\notag
$$
Доказательство. Пусть $z \in N_0$ и, от противного, $\|Az-b_0\| < \delta$. Положим $z_\varepsilon=(1-\varepsilon) z$. Тогда при всех малых $\varepsilon > 0$ получаем неравенства и приходим к противоречию с тем, что $z$ имеет минимальную норму среди решений совместных систем класса $\Sigma$. Таким образом, $\|Az-b_0\|=\delta$.
Теперь допустим, что $\|A - A_0\| < \mu$. При всех достаточно малых возмущениях $F$ матрицы $A$ это неравенство сохранится. Выберем возмущение так, чтобы выполнялось равенство Для этого достаточно взять любую матрицу $F_0$ такую, что и положить Здесь опять возникает противоречие с минимальностью нормы вектора $z$. Мы доказали, что для любого вектора $z \in N_0$ выполняются равенства Следовательно, $N_0=N_1$. Лемма доказана.Заметим, что лемма 2.1 не использует никаких ограничений на нормы и поэтому несколько обобщает аналогичный результат из [5], сформулированный там для фробениусовых (евклидовых) норм. Чтобы получить равенство нам уже придется ввести некоторые ограничения.Норму для $(m \times n)$-матриц будем называть суперсогласованной с векторными нормами в пространствах столбцов размера $m$ и $n$, если
Если в качестве векторных норм используются гёльдеровские 2-нормы, то свойством суперсогласованности обладают фробениусова (евклидова) норма и спектральная норма. При этом для заданных векторов $x$ и $y$ матрицу $A$ можно выбрать в виде
$$
\begin{equation*}
A=\frac{yx^*}{\|x\|_2^2}, \qquad \|A\|_2=\|A\|_F=\frac{\|y\|_2}{\|x\|_2}.
\end{equation*}
\notag
$$
Лемма 2.2. Если норма матриц суперсогласована с векторными нормами основного пространства и пространства образов, то $N_0=N_1=N_2$. Доказательство. Пусть $z \in N_0$. Положим $r_0=b_0 - A_0 z$. Тогда непременно $\|r_0\| - \mu \|z\| > 0$. От противного, допустим, что $z \ne 0$ и $\| r_0 \| / \|z\| \leqslant \mu$. Выберем матрицу $F$ из уравнения В силу суперсогласованности существует такая матрица $F$, для которой Получили противоречие с уже установленным равенством $N_0=N_1$.
Таким образом, величина $\alpha=\mu \|z\| / \|r_0\|$ принадлежит интервалу $0 < \alpha < 1$. Выберем матрицу $F$, удовлетворяющую уравнениям
$$
\begin{equation*}
Fz=\alpha r_0, \qquad \|F\|=\frac{\|\alpha r_0\|}{\|z\|}=\mu.
\end{equation*}
\notag
$$
Тогда
$$
\begin{equation*}
\|b_0-(A_0+F)z\|=\|(1-\alpha) r_0\|=\|r_0\| - \alpha \|r_0\|=\|r_0\| - \mu \|z\|.
\end{equation*}
\notag
$$
Согласно лемме 2.1 отсюда получаем Таким образом, тихоновское решение $z$ удовлетворяет уравнению
Остается заметить, что любой вектор $z$, удовлетворяющий данному уравнению, является решением некоторой совместной системы класса $\Sigma$. В самом деле, выбрав $F$ так, как это делалось выше, и положив $A=A_0 + F$, находим $\|b_0 - Az\|=\delta=\|b_0-A_0z\| - \mu \|z\|$. Лемма доказана. Очевидно, все тихоновские решения имеют одну и ту же (минимальную) норму. Обозначим ее через $\nu$. Тогда из леммы 2.2 вытекает, что тихоновские решения являются векторами минимальной нормы среди векторов $x$, удовлетворяющих уравнению
$$
\begin{equation*}
\|b_0 - A_0 x\|=\rho, \quad\text{где }\ \rho=\mu \nu + \delta.
\end{equation*}
\notag
$$
Они же, очевидно, являются векторами минимальной нормы среди векторов, принадлежащих замкнутому выпуклому множеству
$$
\begin{equation*}
M_\rho=\{ x \colon \|b_0 - A_0 x\| \leqslant \rho \}.
\end{equation*}
\notag
$$
Если норма $\|x\|$ строго выпукла, то такой вектор определяется однозначно. Таким образом, доказана следующая Теорема 2.1. Если норма матриц суперсогласована с векторными нормами, а векторная норма основного пространства строго выпукла, то тихоновское решение единственно. § 3. Непрерывность тихоновского решенияОбозначим через $R_0$ минимальное значение нормы невязки $b_0-A_0x$ на основном пространстве и при $\rho \geqslant R_0$ рассмотрим функцию
$$
\begin{equation*}
f(\rho) :=\min_{\|b_0-A_0x\| \leqslant \rho} \|x\|=\min_{\|b_0-A_0x\|=\rho} \|x\|.
\end{equation*}
\notag
$$
Очевидно, $f(\rho)=0$ при $\rho \geqslant R_1=\|b_0\|.$ Лемма 3.1. Функция $f(\rho)$ непрерывна и строго монотонно убывает на отрезке $R_0 \leqslant \rho \leqslant R_1$. Доказательство. Монотонность проверяется очевидным образом. Чтобы установить непрерывность справа, рассмотрим последовательность точек Пусть $f(\rho_k)=\|x_k\|$ и $\|b_0-A_0x_k\|=\rho_k$. Последовательность векторов $x_k$ принадлежит шару радиуса $f(\rho)$, поэтому из нее можно выделить сходящуюся подпоследовательность $x_{k_l} \to x$ $\Longrightarrow$ $\|x_{k_l}\| \to \|x\|$. Если $\rho_k \to \rho$, то находим $\|b_0 - A_0 x\|=\rho$ $\Longrightarrow$ $\lim_{k \to \infty} f(\rho_k)=\|x\|=f(\rho)$.
Чтобы доказать непрерывность слева, в силу монотонности достаточно построить некоторую специальную последовательность точек такую, что $\rho'_k \to \rho$ и $f(\rho'_k) \to f(\rho)$, $k\to\infty$. Пусть векторы $x$ и $x_0$ являются векторами наименьшей нормы на множествах $M_\rho$ и $M_{\rho'}$:
$$
\begin{equation*}
\|b_0-A_0x\|=\rho, \qquad \|x\|=f(\rho), \qquad \|b_0-A_0x_0\|=\rho_0, \qquad \|x_0\|=f(\rho_0).
\end{equation*}
\notag
$$
Для любой выпуклой комбинации $tx_0+(1-t)x$, где $0 < t < 1$, находим Отсюда следует, что в любой окрестности точки $x$ имеется точка $x'$, для которой Значит, мы можем подобрать последовательность векторов $x_k \to x$, $k\to\infty$, для которых числовая последовательность $\rho'_k :=\|b_0-A_0x_k\|$ является монотонно возрастающей и сходится к $\rho$. Ясно, что $f(\rho'_k) \leqslant \|x_k\| \to \|x\|=f(\rho)$. Пусть $f(\rho'_k)=\|x'_k\|$ и при этом $\|b_0-A_0x'_k\|=\rho'_k$. Если допустить, что то это бы означало, что вектор $x$ не является вектором наименьшей нормы на множестве $M_\rho$. Искомая специальная последовательность, таким образом, получена. Лемма доказана. Обозначим через $z(\rho)$ функцию, которая выбирает вектор наименьшей нормы на множестве $M_\rho$. Лемма 3.2. Если на каждом множестве $M_\rho$ существует только один вектор $z(\rho)$ наименьшей нормы, то функция $z(\rho)$ непрерывна по $\rho$. Доказательство. Рассмотрим произвольную последовательность $\rho_k \to \rho$, $k\to\infty$. Соответствующая ей последовательность точек $z_k=z(\rho_k)$ является ограниченной и поэтому содержит сходящиеся подпоследовательности. Пусть $z_{k_l}$ – любая из них и $z_{k_l} \to z'$, $l\to\infty$. Ясно, что $\|b_0-A_0z'\|=\rho$. При этом из уже установленной непрерывности функции $f(\rho)=\|z(\rho)\|$ следует, что $\|z_{k_l}\| \to \|z\|$, $l\to\infty$. Значит, $\|z'\|=\|z\|$ и в силу единственности $z'=z$.
Таким образом, любая сходящаяся подпоследовательность $z_{k_l}$ имеет один и тот же предел, равный $z$. Отсюда следует, что в ограниченной числовой последовательности $\|z_k-z\|$ любая сходящаяся подпоследовательность сходится к нулю. Значит, $\|z_k-z\| \to 0$, $k\to\infty$, $\Longrightarrow$ $z_k \to z$, $k\to\infty$. Лемма доказана. Величины $R_0$, $f(\rho)$ и множество $M_\rho$, согласно их определению, зависят от матрицы $A_0$ и вектора $b_0$. Поэтому будем писать
$$
\begin{equation*}
R_0=R_0(A_0,b_0), \qquad f(\rho)=f(\rho,A_0,b_0), \qquad M_\rho=M_\rho(A_0,b_0).
\end{equation*}
\notag
$$
В дальнейшем будем предполагать, что для любых $A_0$, $b_0$ и $\rho \geqslant R_0(A_0,b_0)$ на множестве $M_\rho(A_0,b_0)$ есть только один вектор наименьшей нормы. Обозначим его через $z(\rho,A_0,b_0)$. Лемма 3.3. При фиксированном $\rho > R_0(A_0, b_0)$ функция непрерывна по $A$, $b$ в некоторой окрестности $A_0$, $b_0$. Доказательство. Достаточно доказать непрерывность в точке $A_0$, $b_0$. Обозначим через $z_0$ нормальное псевдорешение системы $A_0x=b_0$. Очевидно, $z_0=z(\rho_0,A_0,b_0)$, где и, следовательно, $\|b-Az_0\| < \rho$ для всех $A$ и $b$, достаточно близких к $A_0$ и $b_0$. Таким образом, если $\|A-A_0\| \leqslant \varepsilon$, $\|b-b_0\| \leqslant \varepsilon$, то при достаточно малых $\varepsilon>0$ находим
$$
\begin{equation*}
\|z(\rho,A,b)\| \leqslant \|z_0\|, \qquad f(\rho,A,b)=\min_{ \stackrel{\|b-Ax\| \leqslant \rho}{\|x\| \leqslant \|z_0\|}} \|x\|.
\end{equation*}
\notag
$$
Положим $c=1+\|z_0\|$. Если $\|x\| \leqslant \|z_0\|$, то справедливы неравенства
$$
\begin{equation*}
\|b-Ax\| \leqslant\|b_0-A_0x\| + c \varepsilon, \qquad \|b_0-A_0x\| \leqslant \|b-Ax\| + c \varepsilon.
\end{equation*}
\notag
$$
Таким образом, если $\|b_0-A_0x\| \leqslant \rho-c\varepsilon$, то $\|b-Ax\| \leqslant \rho$. Следовательно,
$$
\begin{equation*}
\begin{aligned} \, &f(\rho+c\varepsilon,A_0,b_0) \leqslant f(\rho,A,b), \qquad f(\rho,A_0,b_0) \leqslant f(\rho-c\varepsilon,A_0,b_0) \\ & \qquad\Longrightarrow |f(\rho,A,b)-f(\rho,A_0,b_0)| \leqslant f(\rho-c\varepsilon,A_0,b_0) - f(\rho+c\varepsilon,A_0,b_0). \end{aligned}
\end{equation*}
\notag
$$
Лемма доказана. Теорема 3.1. В условиях теоремы 2.1 тихоновское решение $x(A_0,b_0,\mu,\delta)$ непрерывно зависит от $A_0$, $b_0$, $\mu$, $\delta$. Доказательство. Как мы уже знаем, $x(A_0,b_0,\mu,\delta)=z(\rho,A_0,b_0)$, а величина $\rho$ удовлетворяет уравнению где функция при $\rho > R_0(A_0,b_0)$ непрерывно зависит от $\rho$, $A_0$, $b_0$ и при любых фиксированных $A_0$, $b_0$ строго монотонно убывает по $\rho$ до тех пор, пока не станет равной нулю. Таким образом, функция $F(\rho)=\mu f(\rho,A_0,b_0) + \delta - \rho$ непрерывна и строго монотонно убывает. Поэтому существует единственное значение $\rho_*$ такое, что $F(\rho_*)=0$.
Докажем, что функция $\rho_*=\rho_*(\mu,\delta,A_0,b_0)$ непрерывно зависит от своих аргументов. Возьмем произвольное достаточно малое $\varepsilon > 0$. Тогда
$$
\begin{equation*}
F(\rho_*-\varepsilon) > 0, \qquad F(\rho_*+\varepsilon) < 0.
\end{equation*}
\notag
$$
При всех достаточно малых возмущениях $A_0$ и $b_0$ эти неравенства сохранятся, поэтому корень уравнения останется на отрезке $[\rho_*-\varepsilon, \rho_*+\varepsilon]$. Остается принять во внимание, что согласно лемме 3.2 вектор $z(\rho)$ непрерывно зависит от $\rho$, а значит, и от $A_0$, $b_0$. Теорема доказана. § 4. Заключительные замечанияДоказательство корректности тихоновского решения прямо связано с алгоритмом его вычисления, который состоит их двух этапов:
Подчеркнем, что индивидуальная система $A_0x=b_0$ не обязана иметь решение. Однако, если эта система совместна, то тихоновское решение можно рассматривать как двухпараметрический алгоритм регуляризации. Следующая теорема обобщает результат работы [5], сформулированный там для случая фробениусовых норм. Теорема 4.1. Пусть выполнены условия теоремы 2.1. Тогда если система $A_0x=b_0$ совместна, то при $\delta, \mu \to 0$ тихоновские решения $x(A_0,b_0,\mu,\delta)$ сходятся к ее решению минимальной нормы. Доказательство. Пусть $\widehat{x}$ – решение системы $A_0x\,{=}\,b_0$ с минимальной нормой. Тогда при заданных $A_0$, $b_0$, $\mu$, $\delta$ тихоновское решение $x$ равно $z(\rho,A_0,b_0)$ для значения $\rho \leqslant \delta + \mu \|\widehat{x}\|$. Поэтому при $\mu,\delta \to 0$ находим $\rho \to R_0=0$. Согласно лемме 3.2 $z(\rho,A_0,b_0) \to z(R_0,A_0,b_0)=\widehat{x}$. Теорема доказана. Насколько ограничительным является требование о том, чтобы класс $\Sigma$ содержал хотя бы одну совместную систему? Если $m \leqslant n$, то это требование заведомо выполнено – достаточно заметить, что в любой сколь угодно малой окрестности вырожденной матрицы найдется невырожденная матрица. Если $m > n$, то может случиться так, что при любых малых возмущениях матрицы и правой части системы будут несовместными. Однако от системы $A_0x=b_0$ можно перейти к расширенной системе с квадратной матрицей
$$
\begin{equation*}
\widetilde{A}_0 \widetilde{x}=b_0, \qquad \widetilde{A}_0=\begin{bmatrix} A_0, &0_{m \times (m-n)} \end{bmatrix}.
\end{equation*}
\notag
$$
Нормальное псевдорешение исходной системы, очевидно, совпадает с нормальным псевдорешением расширенной системы. В данном случае можно искать тихоновское решение $\widetilde{z}$ для класса $\Sigma=\{ \widetilde{A}_0, b_0, \mu, \delta \}$, а в качестве обобщенного решения исходной системы использовать вектор, составленный из первых $n$ элементов вектора $\widetilde{z}$. То, что при определении тихоновского решения рассматриваются только совместные системы, по-видимому, существенно. Даже в случае класса, содержащего совместные системы, можно было бы рассмотреть вектор наименьшей нормы среди всех нормальных псевдорешений систем, эквивалентных по точности, но такой вектор может и не совпадать с тихоновским решением. Введение каких-либо дополнительных ограничений на матрицы (например, симметрия, разреженность, тёплицевость и т.п.) при определении тихоновского решения требует тщательного анализа, так как возмущения, связанные со свойством суперсогласованности нормы матриц с векторными нормами, могут нарушать эти ограничения. 
Цитирование в формате AMSBIB
\RBibitem{Tyr22} |
|
||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|