Линейные уравнения

Вектора

Векторным пространством называется любая алгебраическая система \(V\) с двумя операциями: сложением типа \(V\times V\to V\) и растяжением вида \(R\times V\to V\) для некоторого кольца \(R\) (далее будем считать, что \(R\) — поле действительных чисел). Эти операции должны удовлетворять некоторому списку довольно естественных свойств. А именно, сложение должно иметь структуру коммутативной группы, а растяжение должно быть связано с ним следующими свойствами:

• \( (\alpha+\beta)(a+b) = \alpha a + \beta a + \alpha b + \beta b \)
• \( 1a = a \)
• \( (\alpha\beta)a = \alpha(\beta a) \)

Говоря проще, векторное пространство — то же самое, что и морфизм кольца \(R\) в кольцо эндоморфизмов коммутативной группы.

Чаще всего на практике встречаются пространства \(R^n\): последовательности чисел из \(R\) длины \(n\), сложение и растяжение которых определяется покомпонентно. Договоримся обозначать \(\delta_i\) такую последовательность (неважно для какого именно \(n\)), в которой только \(i\)-я компонента равна 1, а остальные — нулевые. Пространства \(R^n\) называются конечномерными.

Также часто встречаются пространства отображений типа \(X\to V\), где \(V\) является векторным пространством. Сложение и растяжение таких отображений определяется поточечно. В принципе, пространства \(R^n\) являются частным случаем таких пространств для множества \(X\) мощности \(n\).

Линейные отображения

Отображение векторных пространств называется линейным, если оно коммутирует со сложением и растяжением. Говоря проще, \(f\) линейно, если

\[ f(\alpha x + \beta y) = \alpha f(x) + \beta f(y) \]

Ну или, если быть совсем кратким:

\[ f\left( \sum_i \alpha_i x_i \right) = \alpha_i \sum_i f(x_i) \]

Линейные отображения конечномерных пространств имеют очень простое описание: любой вектор конечномерного пространства допускает однозначное представление в виде суммы \(\delta_i\). Поэтому если \(x = \sum_i \alpha_i \delta_i\), то

\[ f(x) = f\left( \sum_i \alpha_i \delta_i \right) = \alpha_i \sum_i f(\delta_i) \]

Заметим, что каждый из \(f(\delta_i)\) можно также разложить по дельтам. Введём обозначение \(f_{ji}\) для коэффициентов этого разложения:

\[ f(\delta_i) = \sum_i f_{ji} \delta_j \]

Такое соглашение (совокуплять индекс дельты здесь именно с первым индексом обозначения) приводит к удобным выражениям для координат образа вектора

\[ f(x)_{i} = \sum_j f_{ij} x_j \]

и для коэффициентов композиции линейных отображений

\[ (f\circ g)_{ij} = \sum_k f_{ik} g_{kj} \]

Набор коэффициентов линейного отображения называется его матрицей. Обычно её записывают в виде таблицы:

\[ \left( \begin{matrix} f_{11} & \ldots & f_{m1}\\ \vdots & & \vdots\\ f_{n1} & \ldots & f_{mn} \end{matrix} \right) \]

Вектора же часто записывают в виде матрицы-столбца: это связано с тем, что любому вектору \(x: R^m\) можно однозначно сопоставить линейное отображение \(\ulcorner x\urcorner: R\to R^m \) по правилу

\[ \ulcorner x\urcorner (r) = rx \]

Такое соглашение позволяет вообще избавиться от операции подстановки значения в отображение (она плоха тем, что неассоциативна, поэтому требует внимания к тому, как расставлены скобки) и писать все равенства в терминах композиции отображений (композиция ассоциативна). Далее мы будем придерживаться именно этого соглашения, считая, что в записи \(AB\) между \(A\) и \(B\) стоит композиция. Соответственно, числа мы будем также считать линейными отображениями \(R\to R\).

Линейные уравнения

Линейным уравнением называется уравнение вида

\[ Ax = a \]

где \(A:U\to V\) — линейное отображение, \(a:V\) — известный вектор (называемый правой частью), а \(x:U\) — неизвестный вектор, который требуется найти.

Если пространства \(U\) и \(V\) конечномерны, то можно применить метод Гаусса. С бесконечномерными такой фокус не пройдёт. Также не пройдёт он с пространствами большой размерности — алгоритмическая сложность метода Гаусса растёт как куб размерности пространства.

Поэтому мы рассмотрим так называемый итерационный способ решения линейных уравнений.

Итерация для чисел

Хорошо известно, что значение \( (1-\alpha)^{-1} \) при \( |\alpha| \lt 1 \) легко найти при помощи итерации схемы Горнера:

\[ x_0 = 0;\qquad x_{n+1} = 1 + \alpha x_n \]

Известно это из курса арифметики, в котором доказывается несложная теорема о том, что

\[ x_n = \frac{1-\alpha^n}{1-\alpha} \]

откуда следует, что при \( |\alpha| \lt 1 \) выполнено

\[ \lim_n x_n = (1-\alpha)^{-1} \]

В принципе, любое числовое уравнение вида

\[ kx = a \]

можно представить в таком виде, домножив на \( \alpha \) и сделав тривиальное преобразование

\[ (1 - (1 - \alpha k)) x = \alpha a \]

Очевидно, что выбором \( \alpha \) можно загнать \( \alpha k \) в интервал от 0 до 1.

Величина линейного отображения

С линейными отображениями всё хуже — у них нет адекватного аналога абсолютной величины числа. Самое лучшее, что есть — это точная нижняя грань множества тех чисел \(M\), для каждого из которых неравенство

\[ |Ax| \leqslant M |x| \]

выполнено для любого вектора \(x\). Она же совпадает с точной верхней гранью множества всевозможных чисел вида \(|Ax| / |x|\). Будем её в дальнейшем обозначать \( |A| \) и называть нормой отображения \( A \). Она удовлетворяет:

• неравенству треугольника \( |A+B| \leqslant |A| + |B| \)
• мультипликативному свойству \( |AB| \leqslant |A||B| \)

Именно эти свойства обеспечивают сходимость итерационного процесса, рассмотренного выше (конечно, при норме соответствующего отображения, меньшей 1).

Можно также сделать оценку снизу и рассмотреть точную верхнюю грань множества тех чисел \(N\), для каждого из которых для любого \(x\) имеет место неравенство

\[ N|x| \leqslant |Ax| \]

Эта точная грань обладает похожим мультипликавным свойством, но уже не удовлетворяет неравенству треугольника: в случае

\[ A = \left(\begin{matrix}1&0\\ 0&2\end{matrix}\right)\qquad B = \left(\begin{matrix}2&0\\ 0&1\end{matrix}\right) \]

эта величина у \(A\) и у \(B\) равна 1, а у их суммы она равна 3. Те отображения, у которых она положительна, будем называть положительными, а саму эту грань — коэффициентом положительности.

Всё плохо?

Посмотрим внимательно на уравнение

\[ (1 - (1 - \alpha A)) x = \alpha a \]

Пусть

\[ A = \left(\begin{matrix}1+a&0\\ 0&1-a\end{matrix}\right) \]

Нетрудно заметить, что как ни уменьшай \(\alpha\), норма \( (1 - \alpha A) \) всё равно равна \( 1 + |\alpha a| \), что больше единицы.

Также нетрудно заметить, что при \(U\ne V\) запись вида \(1 - \alpha A\) вообще смысла не имеет (при \(U=V\) же можно считать, что единица — это тождественное отображение).

На самом деле, всё хорошо (почти)

Вспомним, что в пространствах \( R^n \) есть стандартное скалярное произведение:

\[ x\cdot y = \sum_i x_i y_i \]

Пусть \(A: R^m\to R^n \) — линейное отображение с матрицей \( i,j\mapsto (A_{ij}) \). Отображение с матрицей \( i,j\mapsto (A_{ji}) \) будем называть транспонированным к \(A\) и обозначать \(A^*\).

Нетрудно проверить, что:

\[ x\cdot y = x^* y \]

а также, что:

\[ (AB)^* = B^* A^* \]

Отсюда (и из неравенства Коши-Буняковского) немедленно следует

\[ |Ax|^2 = x^{*} A^{*} A x = x\cdot (A^{*}A x) \leqslant |x| |A^{*}| |A| |x| = |A^{*}| |A| |x|^2 \]

Это означает, что \( |A|^2 \leqslant |A^{*}| |A| \), что эквивалентно \( |A| \leqslant |A^{*}| \). Меняя в этом рассуждении \(A\) на \(A^{*}\), получаем \( |A^{*}| \leqslant |A| \), откуда

\[ |A| = |A^{*}| \]

Использование транспонированного отображения позволяет построить сходящийся итерационный процесс для уравнения \(Ax = a\).

Что делать?

Банально перейти от уравнения

\[ Ax = a \]

к уравнению

\[ \alpha A^{*} A x = \alpha A^{*} a \]

и выбрать достаточно малый \(\alpha\). При этом итерационный процесс примет вид

\[ x_0 = b;\qquad x_{n+1} = b + Bx_n \]

где \(b = \alpha A^{*} a\) и \( B = 1 - \alpha A^{*} A \).

Скорость сходимости

У нас имеется точное равенство

\[ \alpha A^{*}A x_n = (1 - \left( \alpha A^{*} A\right)^n ) b \]

Пусть \(x\) — точное решение уравнения (если оно вообще есть). Тогда

\[ A^{*}A (x-x_n) = \alpha^n \left(A^{*} A\right)^n A^{*}a \]

Пусть \(N\) — коэффициент положительности для \(A^{*}A\). Если он не равен нулю, то

\[ |x-x_n| \leqslant \frac{|A^{*}a|}{N} \left( \alpha |A|^2 \right)^n \]

Отсюда видно, что если выбрать \( \alpha \lt |A|^{-2} \), то процесс сойдётся. Единственная проблема: непонятно, когда. Для этого нужно оценивать сверху \(N^{-1}\), что представляет собой нетривиальную задачу (по сложности сопоставимую с решением исходного уравнения). Впрочем, иногда эту оценку можно вытянуть из той модели, для исследования свойств которой это уравнение и решается.

А вот выбор \( \alpha \) осуществить легко: \( |A|^2 \) оценивается сверху суммой квадратов компонент матрицы \( A \). Таким образом получаем нижнюю оценку на \( |A|^{-2} \). Соответственно, \( \alpha \) можно выбрать, например, равным половине этой оценки.