Системы линейных уравнений: теорема Кронекера–Капелли

Основная задача линейной алгебры

Система Ax = b (m уравнений, n неизвестных) — центральная задача вычислительной и теоретической математики. Когда система совместна? Сколько решений? Как их найти?

Метод Гаусса

Сводим расширенную матрицу [A|b] к ступенчатому виду элементарными преобразованиями строк. Ступенчатый вид: в каждой ненулевой строке ведущий элемент стоит правее, чем в предыдущей.

Приведённый ступенчатый вид (Гаусс–Жордан): ведущий элемент каждой строки = 1, в его столбце нули выше и ниже.

Теорема Кронекера–Капелли

Система Ax = b совместна (имеет хотя бы одно решение) тогда и только тогда, когда rank(A) = rank(A|b).

Три случая:

1. rank A = rank(A|b) = n: единственное решение
2. rank A = rank(A|b) = r < n: бесконечно много решений (n−r степеней свободы)
3. rank A < rank(A|b): несовместна (нет решений)

Структура общего решения

Если система совместна, общее решение: x = x* + xₒ, где x* — частное решение, xₒ — общее решение однородной системы Ax = 0.

Множество решений однородной системы — ядро (нуль-пространство) матрицы A, линейное подпространство размерности n − rank A.

Теорема о ранге: rank A + dim(ker A) = n (для A: m×n).

Метод LU-разложения

Эффективный алгоритм для вычислений: A = LU, где L — нижнетреугольная с единицами на диагонали, U — верхнетреугольная. Метод Гаусса — фактически LU-разложение.

Для решения Ax = b: Ly = b (прямая подстановка), Ux = y (обратная подстановка). Сложность O(n³) для нахождения разложения, O(n²) для решения при известном разложении.

LU-разложение с выбором ведущего элемента (partial pivoting) — стандарт вычислительной математики (библиотека LAPACK).