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

Рассмотрим систему из n линейных уравнений с n неизвестными:

(6.8)

В матричном виде эта система записывается намного элегантнее:

(6.9)

Здесь вектор неизвестных x рассматривается как столбец - прямоугольная матрица размерности n*1. Аналогичный вид имеет вектор правых частей b системы уравнений. В матричном виде условие существования решения системы линейных уравнений 6.8 и нахождение самого решения формулируется совсем просто. Для существования решения необходимо и достаточно, чтобы определитель матрицы A был отличен от нуля. Тогда у матрицы A существует обратная матрица . Для нахождения решения системы умножим обе части уравнения 6.9 на . Тогда получим:

(6.10)

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

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

задается соотношением:

Здесь - прямоугольная матрица размерности , каждый столбец которой представляет вектор правых частей одной системы уравнений. Соответствующий столбец матрицы дает решение этой системы. Что произойдет, если в качестве матрицы рассмотреть единичную матрицу? Очевидно, что тогда матрица будет представлять собой обратную матрицу . Несмотря на кажущуюся очевидность соотношения , в нем есть определенный смысл, который постараюсь сейчас прояснить. Три задачи - вычисление определителя, решение системы линейных уравнений, нахождение обратной матрицы - имеют одинаковую вычислительную сложность и требуют, если не применять специальные алгоритмы, выполнения порядка операций умножения и сложения. Если посмотреть на соотношение 6.10, то кажется, что решить систему уравнений несколько сложнее, чем вычислить обратную матрицу, поскольку нужно вначале найти обратную матрицу, а затем умножить ее на вектор правых частей . Однако реальный алгоритм, рассматриваемый ниже и находящий решение системы, вычислительно проще, чем тот же алгоритм, находящий обратную матрицу. Для такого алгоритма найти обратную матрицу - это все равно, что решить n систем линейных уравнений с одной и той же матрицей в левой части, используя матрицу в качестве правых частей.