Краткое введение в линейную алгебру: исключение Гаусса, обратная матрица, разложение LU и т. д.

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

Эта статья — только первая из многих, которые я планирую выпустить по мере прохождения Линейной алгебры 18.06 в MIT OpenCourseWare и книги профессора Гилберта Стрэнга Линейная алгебра и ее приложения, 4-е издание.

В этой статье затронуто несколько тем:

  • Решение систем линейных уравнений
  • Геометрия линейных уравнений
  • Краткий обзор исключения Гаусса
  • Матричное уравнение
  • Исключение в матричной форме
  • Обратная матрица
  • Исключение Гаусса-Джордана
  • Факторизация в A=LU

Решение систем линейных уравнений

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

Чтобы освежить память, давайте рассмотрим пример системы в 2-х измерениях — с равным количеством неизвестных и уравнений:

Мы определяем неизвестные — правильную пару чисел, которая решает систему — сначала применяя исключение:

Мы исключаем x из второго уравнения, чтобы получить значение y. Последний шаг — подставить значение y обратно в первое уравнение, чтобы определить значение x:

Система решается!

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

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

На этом этапе необходимо хорошее понимание векторов, и я настоятельно рекомендую это видео Грант Сандерсон (3Blue1Brown), чтобы закрепить ваше понимание векторов:

Геометрия линейных уравнений

Вы можете рассматривать систему с точки зрения «строк» ​​или «столбцов». Мы называем каждое уравнение в системе строкой и представляем столбцы как векторы-столбцы в векторном уравнении. . Рассмотрим следующие геометрические интерпретации нашей системы:

На изображении строки прямая линия представляет уравнение (строку). Обе линии пересекаются в точке (4;5), что является единственным решением обоих уравнений.

Системы в более высоких измерениях немного сложнее.

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

Краткий обзор исключения Гаусса

Названный в честь одного из величайших математиков всех времен, Иоганна Карла Фридриха Гаусса, алгоритм устранения Гаусса представляет собой сокращение строк для решения систем линейные уравнения.

Уменьшение количества строк достигается путем применения последовательности из трех элементарных операций со строками:

  • Добавление или вычитание кратного одной строки из другой
  • Замена двух строк
  • Умножение строки на любое ненулевое число

Давайте теперь посмотрим на систему в трех измерениях:

Задача состоит в том, чтобы найти комбинацию столбцов в левой части, которая дает столбец в правой части.

Мы копируем коэффициенты слева и константы справа, чтобы сформировать расширенную матрицу:

Мы хотим выполнить удаление вперед, чтобы свестисистему к верхнетреугольной матрице, где все элементы ниже диагональ равны нулю. Это можно сделать, исключив u из второго уравнения, а также uи v из последнего уравнения.

Мы используем начальную записьпервой строки, также называемую основной, чтобы исключить все записи ниже нее. Для этого мы вычитаем 2 раза первую строку из второй строки:

Затем мы вычитаем первую строку из третьей строки. Этот шаг создает нули ниже первой поворотной точки:

Последним шагом в процессе прямого исключения является удаление v из третьей строки. Обычно для этого мы используем запись во второй основной позиции, но проблема в том, что у нас есть нулевая запись в основной позиции. . Если в основной позиции есть ноль, вы можете поменять местами строки:

Конечным результатом прямого исключения является эквивалентная система в верхнетреугольной форме.

Хотя система кажется другой, решение для нее такое же, как и для исходной системы. Система должна быть решена в обратном порядке, чтобы получить u=3, v=−4 и w =2.

Матричное уравнение

Мы описываем исходную систему как матричное уравнение: Ax=b:

A – это матрица коэффициентов. x — вектор неизвестных, а b — вектор, содержащий правую часть нашей системы. Ключевая идея здесь заключается в том, что умножение матриц описывает операции, выполняемые в процессе удаления вперед.

Исключение в матричной форме

Результатом сокращения строк является верхнетреугольная матрица (U). Следовательно, эквивалентная система (U) не может быть описана Ax=b. Он должен быть описан новой модельной системой:

Всегда помните, что умножение матрицописывает операции, выполняемые в процессе прямого исключения. Следовательно, мы можем выразить каждый шаг исключения как произведение элементарной матрицы (E) и матрицы коэффициентов. Операции, связанные с обменом строками, описываются матрицами перестановки.

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

Матрица перестановок (P) – это квадратная матрица, полученная в результате выполнения перестановки строк в единичной матрице.

Единичная матрица — это линейная алгебраическая эквивалентность 1. Это квадратная матрица с единицами только на главной диагонали и нулями везде:

Давайте обратим внимание на нашу последовательность элементарных операций со строками. Наша последовательность состоит из трех шагов:

  • Вычтите два раза первую строку из второй строки

  • Вычесть первую строку из третьей строки

  • Поменяйте местами второй и третий ряды

Всегда не забывайте вносить те же изменения с правой стороны.

Результатом всех трех шагов процесса прямого исключения является верхнетреугольная матрица (U):

Поскольку умножение матриц является ассоциативным, способ группировки матриц скобками не влияет на конечный результат: (AB)C = A(BC). С другой стороны, умножение матриц не коммутативно: AB≠BA. Матричные операции являются дистрибутивными: A(B + C)=AB + AC и (B + C)A = BA + CA.

Обратная матрица

Обратное мультипликативное натуральное число (n) является его обратным:

Произведение натурального числа (n) и обратного ему мультипликативного равно 1 — мультипликативное тождество.

Точно так же матрица имеет обратную. Произведение матрицы и ее обратной является единичной матрицей:

Не все матрицы обратимы! На самом деле, если Ax=0 для ненулевого вектора можно найти, то A не имеет обратного. Также легко видеть, что матрица не имеет обратной, если ее определитель равен нулю:

Предположим, что матрицы A, B и C являются обратимыми. Обратноепроизведение выглядит следующим образом:

Исключение Гаусса-Джордана

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

Конечным результатом исключения Гаусса-Жордана является матрица в форме уменьшенного эшелона строк, где все элементы выше и ниже опорных точек равны нулю.

Рассмотрим следующую матрицу:

Используя Исключение Гаусса-Жордана, наша цель — найти обратную матрицу A. Идентификационная матрица и матрица A объединены в расширенную матрицу:

Мы выполняем последовательность операций с элементарными строками, чтобы преобразовать матрицу A в эшелонированную форму с уменьшенными строками:

  • Вычтите два раза первую строку из второй строки

  • Трижды прибавляем второй ряд к первому ряду

  • Умножьте вторую строку на −1.

Факторизация в A=LU

Разложение нижней-верхней (LU) – это разложение заданной матрицы на произведение нижнетреугольной матрицы и >верхнетреугольная матрица.

По вычислительным причинам лучше использовать метод разложения LU для решения Ax=b, если A остается фиксированным, а b продолжает меняться.

Чтобы понять эту концепцию, давайте посмотрим на следующую систему:

Мы уменьшаем матрицу A, применяя последовательность из 3 элементарных операций со строками.

  • Вычесть строку 1 из строки 2

  • Вычтите два раза строку 1 из строки 3

  • Вычесть два раза строку 2 из строки 3

В итоге мы получаем верхнетреугольную матрицу, в которой все элементы ниже диагонали равны нулю. Чтобы перейти от A к U, мы применили 3 операции, которые можно просто представить в матричной форме. :

Обратите внимание, как умножение матриц описывает операции, выполняемые в процессе удаления:

Вычисляя произведение всех трех матриц исключения, мы получаем единую матрицу, которая выполняет все три шага исключения:

Если мы инвертируем каждый шаг исключения, мы вернем Uобратно к A:

Произведение всех трех обратных матриц представляет собой одну матрицу в нижнетреугольной форме:

На этом шаге завершается разложение матрицы A на две треугольные матрицы — L и Вы:

Если вы нашли эту статью полезной, не забудьте подписаться, чтобы получать электронные письма всякий раз, когда я публикую. Кроме того, вы можете подписаться на меня в LinkedIn, Twitter и Instagram.