Как найти норму матрицы

Линейная алгебра для исследователей данных

Иллюстрация: UCI

«Наша [Ирвинга Капланского и Пола Халмоша] общая философия в отношении линейной алгебры такова: мы думаем в безбазисных терминах, пишем в безбазисных терминах, но когда доходит до серьезного дела, мы запираемся в офисе и вовсю считаем с помощью матриц».

Ирвинг Капланский

Для многих начинающих исследователей данных линейная алгебра становится камнем преткновения на пути к достижению мастерства в выбранной ими профессии.

kdnuggets

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

Произведения векторов

Для двух векторов x, y ∈ ℝⁿ их скалярным или внутренним произведением xᵀy

называется следующее вещественное число:

Как можно видеть, скалярное произведение является особым частным случаем произведения матриц. Также заметим, что всегда справедливо тождество

Для двух векторов x ∈ ℝᵐ, y ∈ ℝⁿ (не обязательно одной размерности) также можно определить внешнее произведение xyᵀ ∈ ℝᵐˣⁿ. Это матрица, значения элементов которой определяются следующим образом: (xyᵀ)ᵢⱼ = xᵢyⱼ, то есть

Следом квадратной матрицы A ∈ ℝⁿˣⁿ, обозначаемым tr(A) (или просто trA), называют сумму элементов на ее главной диагонали:

След обладает следующими свойствами:

Для любой матрицы A ∈ ℝⁿˣⁿ: trA = trAᵀ.

Для любой матрицы A ∈ ℝⁿˣⁿ и любого числа t ∈ ℝ: tr(tA) = t trA.

Для любых матриц A,B, таких, что их произведение AB является квадратной матрицей: trAB = trBA.

Для любых матриц A,B,C, таких, что их произведение ABC является квадратной матрицей: trABC = trBCA = trCAB (и так далее — данное свойство справедливо для любого числа матриц).

Нормы

Норму ∥x∥ вектора x можно неформально определить как меру «длины» вектора. Например, часто используется евклидова норма, или норма l₂:

Заметим, что ‖x‖₂²=xᵀx.

Более формальное определение таково: нормой называется любая функция f : ℝn → ℝ, удовлетворяющая четырем условиям:

Для всех векторов x ∈ ℝⁿ: f(x) ≥ 0 (неотрицательность).

f(x) = 0 тогда и только тогда, когда x = 0 (положительная определенность).

Для любых вектора x ∈ ℝⁿ и числа t ∈ ℝ: f(tx) = |t|f(x) (однородность).

Для любых векторов x, y ∈ ℝⁿ: f(x + y) ≤ f(x) + f(y) (неравенство треугольника)

Другими примерами норм являются норма l₁

Все три представленные выше нормы являются примерами норм семейства lp, параметризуемых вещественным числом p ≥ 1 и определяемых как

Нормы также могут быть определены для матриц, например норма Фробениуса:

Линейная независимость и ранг

Множество векторов <x₁, x₂, . xₙ> ⊂ ℝₘ называют линейно независимым, если никакой из этих векторов не может быть представлен в виде линейной комбинации других векторов этого множества. Если же такое представление какого-либо из векторов множества возможно, эти векторы называют линейно зависимыми. То есть, если выполняется равенство

для некоторых скалярных значений α₁,…, αₙ-₁ ∈ ℝ, то мы говорим, что векторы x₁, . x ₙ линейно зависимы; в противном случае они линейно независимы. Например, векторы

линейно зависимы, так как x₃ = −2xₙ + x₂.

Столбцовым рангом матрицы A ∈ ℝᵐˣⁿ называют число элементов в максимальном подмножестве ее столбцов, являющемся линейно независимым. Упрощая, говорят, что столбцовый ранг — это число линейно независимых столбцов A. Аналогично строчным рангом матрицы является число ее строк, составляющих максимальное линейно независимое множество.

Оказывается (здесь мы не будем это доказывать), что для любой матрицы A ∈ ℝᵐˣⁿ столбцовый ранг равен строчному, поэтому оба этих числа называют просто рангом A и обозначают rank(A) или rk(A); встречаются также обозначения rang(A), rg(A) и просто r(A). Вот некоторые основные свойства ранга:

Для любой матрицы A ∈ ℝᵐˣⁿ: rank(A) ≤ min(m,n). Если rank(A) = min(m,n), то A называют матрицей полного ранга.

Для любой матрицы A ∈ ℝᵐˣⁿ: rank(A) = rank(Aᵀ).

Для любых матриц A ∈ ℝᵐˣⁿ, B ∈ ℝn×p: rank(AB) ≤ min(rank(A),rank(B)).

Ортогональные матрицы

Два вектора x, y ∈ ℝⁿ называются ортогональными, если xᵀy = 0. Вектор x ∈ ℝⁿ называется нормированным, если ||x||₂ = 1. Квадратная м

атрица U ∈ ℝⁿˣⁿ называется ортогональной, если все ее столбцы ортогональны друг другу и нормированы (в этом случае столбцы называют ортонормированными). Заметим, что понятие ортогональности имеет разный смысл для векторов и матриц.

Непосредственно из определений ортогональности и нормированности следует, что

Другими словами, результатом транспонирования ортогональной матрицы является матрица, обратная исходной. Заметим, что если U не является квадратной матрицей (U ∈ ℝᵐˣⁿ, n < m), но ее столбцы являются ортонормированными, то UᵀU = I, но UUᵀ ≠ I. Поэтому, говоря об ортогональных матрицах, мы будем по умолчанию подразумевать квадратные матрицы.

Еще одно удобное свойство ортогональных матриц состоит в том, что умножение вектора на ортогональную матрицу не меняет его евклидову норму, то есть

для любых вектора x ∈ ℝⁿ и ортогональной матрицы U ∈ ℝⁿˣⁿ.

TimoElliott

Область значений и нуль-пространство матрицы

Линейной оболочкой множества векторов <x₁, x₂, . xₙ> является множество всех векторов, которые могут быть представлены в виде линейной комбинации векторов <x₁, . xₙ>, то есть

Областью значений R(A) (или пространством столбцов) матрицы A ∈ ℝᵐˣⁿ называется линейная оболочка ее столбцов. Другими словами,

Нуль-пространством, или ядром матрицы A ∈ ℝᵐˣⁿ (обозначаемым N(A) или ker A), называют множество всех векторов, которые при умножении на A обращаются в нуль, то есть

Квадратичные формы и положительно полуопределенные матрицы

Для квадратной матрицы A ∈ ℝⁿˣⁿ и вектора x ∈ ℝⁿ квадратичной формой называется скалярное значение xᵀ Ax. Распишем это выражение подробно:

Симметричная матрица A ∈ ��ⁿ называется положительно определенной, если для всех ненулевых векторов x ∈ ℝⁿ справедливо неравенство xᵀAx > 0. Обычно это обозначается как

(или просто A > 0), а множество всех положительно определенных матриц часто обозначают

Симметричная матрица A ∈ ��ⁿ называется положительно полуопределенной, если для всех векторов справедливо неравенство xᵀ Ax ≥ 0. Это записывается как

(или просто A ≥ 0), а множество всех положительно полуопределенных матриц часто обозначают

Аналогично симметричная матрица A ∈ ��ⁿ называется отрицательно определенной

, если для всех ненулевых векторов x ∈ ℝⁿ справедливо неравенство xᵀAx < 0.

Далее, симметричная матрица A ∈ ��ⁿ называется отрицательно полуопределенной (

), если для всех ненулевых векторов x ∈ ℝⁿ справедливо неравенство xᵀAx ≤ 0.

Наконец, симметричная матрица A ∈ ��ⁿ называется неопределенной, если она не является ни положительно полуопределенной, ни отрицательно полуопределенной, то есть если существуют векторы x₁, x₂ ∈ ℝⁿ такие, что

Собственные значения и собственные векторы

Для квадратной матрицы A ∈ ℝⁿˣⁿ комплексное значение λ ∈ ℂ и вектор x ∈ ℂⁿ будут соответственно являться собственным значением и собственным вектором, если выполняется равенство

На интуитивном уровне это определение означает, что при умножении на матрицу A вектор x сохраняет направление, но масштабируется с коэффициентом λ. Заметим, что для любого собственного вектора x ∈ ℂⁿ и скалярного значения с ∈ ℂ справедливо равенство A(cx) = cAx = cλx = λ(cx). Таким образом, cx тоже является собственным вектором. Поэтому, говоря о собственном векторе, соответствующем собственному значению λ, мы обычно имеем в виду нормализованный вектор с длиной 1 (при таком определении все равно сохраняется некоторая неоднозначность, так как собственными векторами будут как x, так и –x, но тут уж ничего не поделаешь).

Перевод статьи был подготовлен в преддверии старта курса «Математика для Data Science». Также приглашаем всех желающих посетить бесплатный демоурок, в рамках которого рассмотрим понятие линейного пространства на примерах, поговорим о линейных отображениях, их роли в анализе данных и порешаем задачи.

учимся
программировать

Программированию нельзя научить, можно только научится

Главная » Уроки по Численным методам » Урок 12. Ранг матрицы. Вычисление ранга матрицы. Норма матриц

Урок №12. Ранг матрицы. Вычисление ранга матрицы. Норма матриц.

Если все миноры матрицы Aпорядка kравны нулю, то все миноры порядка k+1, если такие существуют, тоже равны нулю.
Рангом матрицы A называется наибольший из порядков миноров матрицы A, отличных от нуля.
Максимум ранг может быть равен минимальному числу из количества строк или столбцов матрицы, т.е. если матрица имеет размер 4х5, то максимум ранг будет 4.
Минимум ранг матрицы равен 1, если только вы не имеете дело с нулевой матрицей, там всегда ранг равен нулю.

Ранг невырожденной квадратной матрицы порядка n равен n, так как ее определитель является минором порядка n и у невырожденной матрицы отличен от нуля.
При транспонировании матрицы ее ранг не меняется.

Пусть ранг матрицы равен . Тогда любой минор порядка , отличный от нуля, называется базисным минором.
Пример. Дана матрица А.
$$ <A=\left(\begin<array><rrr>1&3&6\\ 2&1&2\\ 3&4&8\end<array>\right)>$» width=»134″ height=»65″ /> <br />Определитель матрицы <img loading=$ равен нулю.
Минор второго порядка . Следовательно, r(A)=2 и минор базисный.
Базисным минором является также минор .
Минор , т.к. =0, поэтому не будет базисным.
Задание: самостоятельно проверить, какие еще миноры второго порядка будут базисными, а какие нет.

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

Назовем элементарными преобразованиями матриц следующие действия над ними:
1) перестановка строк или столбцов;
2) умножение строки или столбца на число отличное от нуля;
3) добавление к одной из строк другой строки, умноженной на число или добавление к одному из столбцов другого столбца, умноженного на число.

При элементарных преобразованиях ранг матрицы не меняется.
Алгоритм вычисления ранга матрицы похож на алгоритм вычисления определителя и заключается в том, что с помощью элементарных преобразований матрица приводится к простому виду, для которого найти ранг не представляет труда. Так как при каждом преобразовании ранг не менялся, то, вычислив ранг преобразованной матрицы, мы тем самым находим ранг исходной матрицы.

Пусть требуется вычислить ранг матрицы размеров mxn.

С помощью перестановки строк и столбцов матрицы добиваемся того, чтобы в левом верхнем углу матрицы стоял ненулевой элемент. Итак, считаем, что . Первую строку оставляем без изменений.
Ко второй строке прибавляем первую, умноженную на число .
К третьей строке прибавляем первую строку, умноженную на число $$ \left(-\dfrac<a_<31>><a_<11>>\right)$» width=»66″ height=»46″ />.</li> <li>Процесс продолжаем до тех пор, пока не получим нуль на первом месте в последней строке. В результате получим матрицу А1, в которой в первом столбце все элементы равны 0, кроме элемента <img decoding=$ .

В результате расчетов матрица А1 имеет вид
$$\displaystyle A^<(1)>=\left(\begin<array><ccccc>a_<11>&a_<12>&a_<13>&\dots&a_<1. . ots&\dots\\ 0&a_<m2>^<(1)>&a_<m3>^<(1)>&\dots&a_<mn>^<(1)>\end<array>\right).$» width=»283″ height=»112″ /></p> <ol> <li>Если все строки, начиная со второй, в полученной матрице нулевые, то ее ранг равен 1, так как есть минор первого порядка, отличный от нуля <img decoding=$ . В противном случае перестановкой строк и столбцов матрицы с номерами, большими единицы, добиваемся, чтобы второй элемент второй строки был отличен от нуля. Итак, считаем, что .

Первую и вторую строки оставляем без изменений.

К третьей строке прибавляем вторую, умноженную на число

. В результате получим, что второй элемент третьей строки равен нулю.

Затем к четвертой строке прибавляем вторую, умноженную на число

, и т.д. В результате получаем матрицу

$$\displaystyle A^<(2)>=\left(\begin<array><ccccc>a_<11>&a_<12>&a_<13>&\dots&a_<1. . ts&\dots&\dots&\dots\\ 0&0&a_<m3>^<(2)>&\dots&a_<mn>^<(2)>\end<array>\right).$» width=»282″ height=»123″ /> <br />Если все строки, начиная с третьей, нулевые, то <img decoding=$ , так как минор $$ <\left\vert\begin<array><cc>a_<11>&a_<12>\\ 0&a_<22>^<(1)>\end<array>\right\vert=a_<11>a_<22>^<(1)>\ne0>$» width=»187″ height=»46″ />. Иначе перестановкой строк и столбцов с номерами, большими двух, добиваемся, чтобы третий элемент третьей строки был отличен от нуля. Далее, добавлением третьей строки, умноженной на соответствующие числа, к строкам с большими номерами получаем нули в третьем столбце, начиная с четвертого элемента, и т.д. <br />На каком-то этапе мы придем к матрице, у которой все строки, начиная с (r+1)-ой , равны нулю (или отсутствуют при <img decoding=$ ), а минор в первых строках и первых столбцах является определителем треугольной матрицы с ненулевыми элементами на диагонали. Ранг такой матрицы равен . Следовательно, Rang(A)=r.

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

В лабораторно-практической работе рассмотрим пример нахождения ранга матрицы.

АЛГОРИТМ НАХОЖДЕНИЯ НОРМЫ МАТРИЦЫ.
Выделяют всего три нормы матрицы.
Первая норма матрицы = максимальному из чисел, полученных при сложении всех элементов каждого столбца, взятых по модулю.
Пример: пусть дана матрица А размера 3х2 (рис.10). В первом столбце стоят элементы: 8, 3, 8. Все элементы положительные. Найдем их сумму: 8+3+8=19. Во втором столбце стоят элементы: 8, -2, -8. Два элемента — отрицательные, поэтому при сложении этих чисел, необходимо подставлять модуль этих чисел (т.е. без знаков "минус"). Найдем их сумму: 8+2+8=18. Максимальное из этих двух чисел — это 19. Значит первая норма матрицы равна 19.

Нормы матрицы

Рисунок 10.

Вторая норма матрицы представляет из себя квадратный корень из суммы квадратов всех элементов матрицы. А это значит мы возводим в квадрат все элементы матрицы, затем складываем полученные значения и из результата извлекаем квадратный корень.
В нашем случае, 2 норма матрицы получилась равна квадратному корню из 269. На схеме, я приближенно извлекла квадратный корень из 269 и в результате получила приблизительно около 16,401. Хотя более правильно не извлекать корень.
Норма матрицы

Третья норма матрицы представляет из себя максимальное из чисел, полученных при сложении всех элементов каждой строки, взятых по модулю.
В нашем примере: в первой строке стоят элементы: 8, 8. Все элементы положительные. Найдем их сумму: 8+8=16. В второй строке стоят элементы: 3, -2. Один из элементов отрицательный, поэтому при сложении этих чисел, необходимо подставлять модуль этого числа. Найдем их сумму: 3+2=5. В третьей строке стоят элементы 8, и -8. Один из элементов отрицательный, поэтому при сложении этих чисел, необходимо подставлять модуль этого числа. Найдем их сумму: 8+8=16. Максимальное из этих трех чисел — это 16. Значит третья норма матрицы равна 16.
Нормы матрицы

Нормы матриц

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

Как правило, используются нормы трех видов.

1) M-норма. Вычисляется по формуле

, где i – номер строки, j – номер столбца.