Русская Википедия:Ядро (линейная алгебра)
Ядро линейного отображения — это такое линейное подпространство области определения отображения, каждый элемент которого отображается в нулевой вектор Шаблон:RШаблон:R. А именно: если задано линейное отображение <math>L\colon V\to W</math> между двумя векторными пространствами Шаблон:Mvar и Шаблон:Mvar, то ядро отображения Шаблон:Mvar — это векторное пространство всех элементов <math>\mathbf{v}</math> пространства Шаблон:Mvar, таких что <math>L(\mathbf{v}) = \mathbf{0}</math>, где <math>\mathbf{0}</math> обозначает нулевой вектор из Шаблон:MvarШаблон:R, или более формально:
- <math>\ker(L) = \left\{ \mathbf{v} \in V \mid L(\mathbf{v})=\mathbf{0} \right\} .</math>
Свойства
Ядро отображения Шаблон:Mvar — это линейное подпространство области определения Шаблон:MvarШаблон:R. В линейном отображении <math>L\colon V \to W</math> два элемента Шаблон:Mvar имеют один и тот же образ в Шаблон:Mvar тогда и только тогда, когда их разность лежит в ядре отображения Шаблон:Mvar:
- <math>L(\mathbf{v}_1) = L(\mathbf{v}_2) \iff L(\mathbf{v}_1-\mathbf{v}_2)=\mathbf{0}. </math>
Из этого следует, что образ Шаблон:Mvar изоморфен факторпространству пространства Шаблон:Mvar по ядру:
- <math>\operatorname{im}(L) \cong V / \ker(L).</math>
Шаблон:AnchorВ случае, когда Шаблон:Mvar конечномерно, из этого следует Шаблон:Не переведено 5:
- <math>\dim(\ker L) + \dim(\operatorname{im} L) = \dim(V),</math>
где под рангом мы понимаем размерность образа отображения Шаблон:Mvar, а под дефектом — размерность ядра отображения Шаблон:MvarШаблон:R.
Если Шаблон:Mvar является предгильбертовым пространством, факторпространство <math>V / ker(L)</math> можно отождествить с ортогональным дополнением к Шаблон:Mvar пространства <math>ker(L)</math>. Это является обобщением линейных операторов пространства строк или кообраза матрицы.
Приложение к модулям
Шаблон:Основная статья Понятие ядра также имеет смысл для гомоморфизмов модулей, которые являются обобщениями векторных пространств, где скаляры — элементы кольца, а не поля. Область определения отображения — это модуль с ядром, образующий подмодуль. Здесь концепции ранга и размерности ядра не обязательны.
В функциональном анализе
Шаблон:Основная статья Если <math>V</math> и <math>W</math> являются топологическими векторными пространствами, а <math>W</math> конечномерно, то линейный оператор <math>L\colon V\to W</math> непрерывен тогда и только тогда, когда ядро отображения <math>L</math> является замкнутым подпространством пространства <math>V</math>.
Представление в виде матричного умножения
Рассмотрим линейное отображение, представленное матрицей <math>A</math> размера <math>m \times n</math> с коэффициентами из поля <math>K</math> (обычно из <math>\mathbb{R}</math> или <math>\mathbb{C}</math>), то есть оперирующие с вектор-столбцами <math>\mathbf{x}</math> с <math>n</math> элементами из поля <math>K</math>. Ядро этого линейного отображения — это множество решений уравнения <math>A\mathbf{x}=\mathbf{0}</math>, где <math>\mathbf{0}</math> понимается как нулевой вектор. Размерность ядра матрицы <math>A</math> называется дефектом матрицы <math>A</math>. В виде операций на множествах,
- <math>\operatorname{N}(A)=\operatorname{Null}(A)=\operatorname{ker}(A) = \left\{ \mathbf{x}\in K^n | A\mathbf{x} = \mathbf{0} \right\}.</math>
Матричное уравнение эквивалентно однородной системе линейных уравнений:
- <math>A\mathbf{x}=\mathbf{0} \;\;\Leftrightarrow\;\;
\left\{\begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \;\cdots\; + \;&& a_{1n} x_n &&\; = \;&&& 0 \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \;\cdots\; + \;&& a_{2n} x_n &&\; = \;&&& 0 \\ \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \;\cdots\; + \;&& a_{mn} x_n &&\; = \;&&& 0\text{.} \\ \end{alignat}\right.</math> Тогда ядро матрицы <math>A</math> — это то же самое, что и решение набора приведённых выше однородных уравнений.
Свойства подпространства
Ядро <math>m \times n</math> матрицы <math>A</math> над полем <math>K</math> является линейным подпространством <math>K^n</math>. То есть ядро матрицы <math>A</math>, множество <math>\operatorname{Null}(A)</math>, имеет следующие три свойства:
- <math>\operatorname{Null}(A)</math> всегда содержит нулевой вектор, поскольку <math>A\mathbf{0}=\mathbf{0}</math>.
- Если <math>\mathbf{x} \in \operatorname{Null}(A)</math> и <math>\mathbf{y} \in \operatorname{Null}(A)</math>, то <math>\mathbf{x} + \mathbf{y} \in \operatorname{Null}(A)</math>. Это следует из свойства дистрибутивности матричного умножения.
- Если <math>\mathbf{x} \in \operatorname{Null}(A) </math>, а <math>c</math> является скаляром <math>c \in K</math>, то <math>c\mathbf{x}\in \operatorname{Null}(A) </math>, поскольку <math>A(c\mathbf{x}) = c(A\mathbf{x}) = c\mathbf{0} = \mathbf{0}</math>.
Пространство строк матрицы
Шаблон:Основная статья Произведение <math>A\mathbf{x}</math> может быть записано в терминах скалярного произведения векторов следующим образом:
- <math>A\mathbf{x} = \begin{bmatrix} \mathbf{a}_1 \cdot \mathbf{x} \\ \mathbf{a}_2 \cdot \mathbf{x} \\ \vdots \\ \mathbf{a}_m \cdot \mathbf{x} \end{bmatrix}.</math>
Здесь <math>\mathbf{a}_1, \dots, \mathbf{a}_m</math> означают строки матрицы <math>A</math>. Отсюда следует, что <math>\mathbf{x}</math> принадлежит ядру матрицы <math>A</math> тогда и только тогда, когда вектор <math>\mathbf{x}</math> ортогонален (перпендикулярен) каждой из вектор-строк матрицы <math>A</math> (поскольку ортогональность определяется как равенство нулю скалярного произведения).
Пространство строк, или кообраз матрицы <math>A</math>, — это линейная оболочка вектор-строк матрицы <math>A</math>. По указанным выше причинам ядро матрицы <math>A</math> является ортогональным дополнением пространству строк. То есть вектор <math>\mathbf{x}</math> лежит в ядре матрицы <math>A</math> тогда и только тогда, когда он перпендикулярен любому вектору из пространства строк матрицы <math>A</math>.
Размерность пространства строк матрицы <math>A</math> называется рангом матрицы <math>A</math>, а размерность ядра матрицы <math>A</math> называется дефектом матрицы <math>A</math>. Эти величины связаны Шаблон:Не переведено 5
- <math>\operatorname{rank}(A) + \operatorname{nullity}(A) = n.</math>Шаблон:R
Левое нуль-пространство (коядро)
Левое нуль-пространство или коядро матрицы <math>A</math> состоит из всех векторов <math>\mathbf{x}</math>, таких что <math>\mathbf{x}^TA=\mathbf{0}^T</math>, где <math>T</math> обозначает транспонирование матрицы. Левое нуль-пространство матрицы <math>A</math> — это то же самое, что и ядро матрицы <math>A^T</math>. Левое нуль-пространство матрицы <math>A</math> является ортогональным дополнением пространству столбцов матрицы <math>A</math> и двойственно коядру связанного линейного преобразования. Ядро, пространство строк, пространство столбцов и левое нуль-пространство матрицы <math>A</math> являются четырьмя фундаментальными подпространствами, ассоциированными с матрицей <math>A</math>.
Неоднородные системы линейных уравнений
Ядро играет также большую роль при решении неоднородных систем линейных уравнений:
- <math>A\mathbf{x}=\mathbf{b}\;\;\Leftrightarrow\;\;
\left\{\begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \;\cdots\; + \;&& a_{1n} x_n &&\; = \;&&& b_1 \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \;\cdots\; + \;&& a_{2n} x_n &&\; = \;&&& b_2 \\ \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \;\cdots\; + \;&& a_{mn} x_n &&\; = \;&&& b_m. \\ \end{alignat}\right.</math> Пусть векторы <math>\mathbf{u}</math> и <math>\mathbf{v}</math> являются решениями уравнения выше, тогда
- <math>A(\mathbf{u}-\mathbf{v}) = A\mathbf{u} - A\mathbf{v} = \mathbf{b} - \mathbf{b} = \mathbf{0}.</math>
Таким образом, разность любых двух решений системы <math>A\mathbb{x}=\mathbb{b}</math> лежит в ядре матрицы <math>A</math>.
Отсюда следует, что любое решение уравнения <math>A\mathbf{x}=\mathbf{b}</math> может быть выражено как сумма фиксированного решения <math>\mathbf{v}</math> и какого-либо элемента ядра. То есть множеством решений уравнения <math>A\mathbf{x}=\mathbf{b}</math> является
- <math>\left\{ \mathbf{v}+\mathbf{x} \mid A \mathbf{v}=\mathbf{b} \land \mathbf{x}\in\operatorname{Null}(A) \right\}.</math>
Геометрически это означает, что множество решений уравнения <math>A\mathbf{x}=\mathbf{b}</math> образовано параллельным переносом ядра матрицы <math>A</math> на вектор <math>\mathbf{v}</math>. См. также Альтернатива Фредгольма.
Иллюстрация
Ниже приведена простая иллюстрация вычисления ядра матрицы (см. Вычисление методом Гаусса ниже для метода, более подходящего для более сложных вычислений). Иллюстрация затрагивает также пространства строк и их связь с ядром.
Рассмотрим матрицу
- <math>A = \begin{bmatrix}2 & 3 & 5 \\ -4 & 2 & 3\end{bmatrix}.</math>
Ядро этой матрицы состоит из всех векторов <math>(x, y, z) \in \mathbb{R}^3</math>, для которых
- <math>\begin{bmatrix}2 & 3 & 5 \\ -4 & 2 & 3\end{bmatrix}\begin{bmatrix} x \\ y \\ z\end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix},</math>
что можно выразить в виде однородной системы линейных уравнений относительно <math>x</math>, <math>y</math> и <math>z</math>:
- <math>\begin{align}
2x + 3y + 5z &= 0, \\
-4x + 2y + 3z &= 0. \end{align}</math>
Те же самые равенства можно выписать в матричном виде:
- <math>
\left[\begin{array}{ccc|c}
2 & 3 & 5 & 0 \\
-4 & 2 & 3 & 0
\end{array}\right].
</math>
С помощью метода Гаусса матрица может быть сведена к:
- <math>
\left[\begin{array}{ccc|c}
1 & 0 & 1/16 & 0 \\
0 & 1 & 13/8 & 0
\end{array}\right].
</math>
Преобразование матрицы в уравнения даёт:
- <math>\begin{align}
x &= -\frac{1}{16}z \\ y &= -\frac{13}{8}z. \end{align}</math>
Элементы ядра можно выразить в параметрическом виде следующим образом:
- <math>\begin{bmatrix} x \\ y \\ z\end{bmatrix} = c \begin{bmatrix} -1/16 \\ -13/8 \\ 1\end{bmatrix}\quad (\text{где}\quad c \in \mathbb{R})</math>
Поскольку <math>c</math> является Шаблон:Не переведено 5, пробегающей по всем вещественным числам, это выражение можно эквивалентно переписать в виде:
- <math>
\begin{bmatrix} x\\ y\\ z \end{bmatrix} =
c \begin{bmatrix}
-1\\ -26\\ 16 \end{bmatrix}. </math> Ядро матрицы <math>A</math> — это в точности множество решений этих уравнений (в этом случае прямая через начало координат в <math>\mathbb{R}^3</math>). Здесь вектор (−1,−26,16)T образует базис ядра матрицы <math>A</math>. Дефект матрицы <math>A</math> равен 1.
Следующие скалярные произведения равны нулю:
- <math>
\begin{bmatrix} 2 & 3 & 5 \end{bmatrix}
\begin{bmatrix}
-1\\ -26\\ 16
\end{bmatrix}
= 0 \quad\text{ и }\quad
\begin{bmatrix} -4 & 2 & 3 \end{bmatrix}
\begin{bmatrix}
-1\\ -26\\ 16
\end{bmatrix}
= 0\mathrm{,} </math> что показывает, что вектора ядра матрицы <math>A</math> ортогональны каждой вектор-строке матрицы <math>A</math>.
Линейная оболочка этих двух (линейно независимых) вектор-строк — это плоскость, ортогональная вектору <math>(-1,-26,16)^T</math>.
Поскольку ранг матрицы <math>A</math> равен 2, размерность ядра матрицы <math>A</math> равна 1, а размерность матрицы <math>A</math> равна 3, мы имеем иллюстрацию теоремы о ранге и дефекте.
Примеры
- Если <math>L\colon\mathbb{R}^m\to\mathbb{R}^n </math>, то ядром отображения <math>L</math> является множество решений однородной системы линейных уравнений. Как в иллюстрации выше, если <math>L</math> является оператором:
- <math>L(x_1,x_2,x_3) = (2x_1 + 3x_2 + 5x_3,\; -4x_1 + 2x_2 + 3x_3)</math>,
- то ядром оператора L является множество решений системы
- <math>\begin{alignat}{7}
2x_1 &\;+\;& 3x_2 &\;+\;& 5x_3 &\;=\;& 0 \\ -4x_1 &\;+\;& 2x_2 &\;+\;& 3x_3 &\;=\;& 0
\end{alignat}</math>
- Пусть <math>C[0,1]</math> обозначает векторное пространство всех непрерывных вещественных функций на интервале [0,1]. Определим <math>L\colon C[0,1]\to\mathbb{R}</math> правилом
- <math>L(f) = f(0,3)\text{.}\,</math>
- Тогда ядро of L состоит из всех функций <math>f\in C[0,1]</math>, для которых<math>f(0,3)=0</math>.
- Пусть <math>C^\infty(\mathbb{R})</math> будет векторным пространством всех бесконечно дифференцируемых функций <math>\mathbb{R}\to\mathbb{R}</math> и пусть <math>D\colon C^\infty(\mathbb{R})\to C^\infty(\mathbb{R})</math> будет оператором дифференцирования:
- <math>D(f) = \frac{df}{dx}\text{.}</math>
- Тогда ядро of D состоит из всех функций в <math>C^\infty(\mathbb{R})</math>, производная которых равна нулю, то есть из всех постоянных функций.
- Пусть <math>\mathbb{R}^\infty</math> будет прямым произведением бесконечного числа копий <math>\mathbb{R}</math>, и пусть <math>s\colon \mathbb{R}^\infty\to\mathbb{R}^\infty</math> будет оператором сдвига
- <math>s(x_1,x_2,x_3,x_4,\ldots) = (x_2,x_3,x_4,\ldots)\text{.}</math>
- Тогда ядром оператора s будет одномерное подпространство, состоящее из всех векторов <math>(x_1,0,0,\dots)</math>.
- Если <math>V</math> является предгильбертовым пространством, а <math>W</math> — подпространством, ядром ортогональной проекции <math>V\to W</math> является ортогональным дополнением <math>W</math> в <math>V</math>.
Вычисления по методу Гаусса
Базис ядра матрицы можно вычислить с помощью метода Гаусса.
Для этой цели, если дана <math>m \times n</math> матрица <math>A</math>, мы строим сначала Шаблон:Не переведено 5 по строкам матрицу <math> \left[\begin{array}{c}A\\\hline E\end{array}\right],</math>, где <math>E</math> — это <math>n \times n</math> единичная матрица.
Если вычислим ступенчатый по столбцам вид матрицы методом Гаусса (или любым другим подходящим методом), мы получим матрицу <math> \left[\begin{array}{c}B\\\hline C\end{array}\right].</math> Базис ядра матрицы <math>A</math> состоит из ненулевых столбцов матрицы <math>C</math>, таких что соответствующие столбцы матрицы <math>B</math> a нулевые.
Фактически вычисление может быть остановлено, как только матрица принимает ступенчатый по столбцам вид — остальное вычисление состоит из изменения базиса векторного пространства, образованного столбцами, верхняя часть которых равна нулю.
Например, представим, что
- <math>A=\left[ \begin{array}{cccccc}
1 & 0 & -3 & 0 & 2 & -8 \\ 0 & 1 & 5 & 0 & -1 & 4 \\ 0 & 0 & 0 & 1 & 7 & -9 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \,\right]. </math> Тогда
- <math> \left[\begin{array}{c}A\\\hline E\end{array}\right]=
\left[\begin{array}{cccccc} 1 & 0 & -3 & 0 & 2 & -8 \\ 0 & 1 & 5 & 0 & -1 & 4 \\ 0 & 0 & 0 & 1 & 7 & -9 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right]. </math>
Если привести верхнюю часть с помощью операций над столбцами к ступенчатому виду, получим
- <math> \left[\begin{array}{c}B\\\hline C\end{array}\right]=
\left[\begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 3 & -2 & 8 \\ 0 & 1 & 0 & -5 & 1 & -4 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & -7 & 9 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right]. </math>
Последние три столбца матрицы <math>B</math> нулевые. Поэтому три последних вектора матрицы <math>C</math>,
- <math>\left[\!\! \begin{array}{r} 3 \\ -5 \\ 1 \\ 0 \\ 0 \\ 0 \end{array} \right],\;
\left[\!\! \begin{array}{r} -2 \\ 1 \\ 0 \\ -7 \\ 1 \\ 0 \end{array} \right],\; \left[\!\! \begin{array}{r} 8 \\ -4 \\ 0 \\ 9 \\ 0 \\ 1 \end{array} \right] </math> являются базисом ядра матрицы <math>A</math>.
Доказательство, что метод вычисляет ядро: поскольку операции над столбцами соответствуют умножению справа на обратимую матрицу, из факта, что <math>\left[\begin{array}{c}A\\\hline E\end{array}\right]</math> сводится к <math>\left[\begin{array}{c}B\\\hline C\end{array}\right]</math> вытекает, что существует обратимая матрица <math>P</math>, такая что <math> \left[\begin{array}{c}A\\\hline E\end{array}\right] P = \left[\begin{array}{c}B\\\hline C\end{array}\right], </math> где <math>B</math> имеет ступенчатый вид. Тогда <math>AP=B,</math> <math>EP=C, </math> и <math> AC=B. </math> Вектор-столбец <math>v</math> принадлежит ядру матрицы <math>A</math> (то есть <math>Av=0</math>) тогда и только тогда, когда <math>Bw=0,</math> где <math>w=P^{-1}v=C^{-1}v.</math> Так как <math>B</math> имеет ступенчатый вид, <math>Bw=0</math> тогда и только тогда, когда ненулевые элементы <math>w</math> соответствуют нулевым столбцам матрицы <math>B.</math> После умножения на <math>C</math> можно сделать вывод, что это случается тогда и только тогда, когда <math>v=Cw</math> является линейной комбинацией соответствующих столбцов матрицы <math>C.</math>
Численные вычисления
Задача вычисления ядра на компьютере зависит от природы коэффициентов.
Точные коэффициенты
Если коэффициенты матрицы заданы как точные числа, ступенчатый вид матрицы может быть вычислен алгоритмом Барейса, который более эффективен, чем метод Гаусса. Ещё более эффективно использование сравнения по модулю и китайской теоремы об остатках, которые сводят задачу к нескольким аналогичным задачам над конечными полями (что сокращает издержки, порождённые нелинейной вычислительной сложностью целочисленного умножения).
Для коэффициентов из конечного поля метод Гаусса работает хорошо, но для больших матриц, которые случаются в криптографии и при вычислении базиса Грёбнера, известны более эффективные алгоритмы, которые имеют почти ту же вычислительную сложность, но работают быстрее и более подходят для современных компьютерных устройств.
Вычисления с плавающей точкой
Для матриц, элементами которых служат числа с плавающей запятой, задача вычисления ядра имеет смысл только для матриц, число строк которых равно её рангу — ввиду Шаблон:Не переведено 5 матрицы с плавающими значениями почти всегда имеют полный ранг, даже когда они являются аппроксимацией матрицы много меньшего ранга. Даже для матрицы полного ранга можно вычислить её ядро только тогда, когда она хорошо обусловлена, то есть имеет низкое число обусловленностиШаблон:R.
И для хорошо обусловленной матрицы полного ранга метод Гаусса не ведёт себя корректно: ошибки округления слишком велики для получения значимого результата. Так как вычисление ядра матрицы является специальным случаем решения однородной системы линейных уравнений, ядро может быть вычислено любым алгоритмом, предназначенным для решения однородных систем. Передовым программным обеспечением для этих целей является библиотека Lapack.
См. также
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Ссылки
Шаблон:Векторы и матрицы Шаблон:Rq
