Метод Гаусса для решения систем линейных уравнений
Метод Гаусса — это алгоритм решения систем линейных уравнений с квадратной матрицей. Он основан на приведении системы к эквивалентному виду с треугольной матрицей, что значительно упрощает нахождение решения. Метод также позволяет вычислять определитель матрицы и находить обратную матрицу.
Основные понятия и критерии
Для применения метода Гаусса система уравнений должна быть регулярной (невырожденной), то есть иметь единственное решение. Критерии регулярности квадратной матрицы A:
- Её определитель не равен нулю.
- Однородная система уравнений Ax = 0 имеет только тривиальное решение (нулевой вектор).
- Для любого вектора правой части b система Ax = b имеет единственное решение.
Если определитель матрицы не равен нулю, существует обратная матрица A⁻¹.
Суть метода исключения (прямой ход)
Цель прямого хода — преобразовать исходную систему к виду с верхней треугольной матрицей. Это достигается с помощью элементарных преобразований строк, которые не меняют решения системы:
- Перестановка двух уравнений (строк).
- Умножение уравнения на ненулевое число.
- Прибавление к одному уравнению другого, умноженного на число.
Алгоритм прямого хода:
- На первом шаге с помощью первого уравнения исключается переменная x₁ из всех последующих уравнений. Для этого из i-й строки вычитается первая строка, умноженная на коэффициент
a_i1 / a_11. - Первая строка далее остаётся без изменений. Процедура повторяется для уменьшенной подсистемы со второй строки, чтобы исключить x₂ из строк ниже, и так далее.
- Если на каком-то шаге в ведущем столбце оказывается ноль, производится перестановка строк.
В результате получается система с верхней треугольной матрицей. Число арифметических операций имеет порядок n³.
Обратный ход
После приведения системы к треугольному виду решение находится обратным ходом — снизу вверх:
- Из последнего уравнения сразу находится значение последней переменной x_n.
- Это значение подставляется в предпоследнее уравнение, чтобы найти x_{n-1}.
- Процесс продолжается до нахождения всех переменных.
Вычисление определителя
При элементарных преобразованиях определитель матрицы изменяется предсказуемо:
- Перестановка строк меняет знак определителя.
- Умножение строки на число k умножает определитель на k.
- Прибавление к одной строке другой не меняет определитель.
Если в процессе прямого хода методом Гаусса (с учётом перестановок) матрица приведена к треугольной, её определитель равен произведению элементов на главной диагонали. Все выполненные операции (перестановки, умножения строк) необходимо отслеживать, чтобы скорректировать итоговое значение.
Матричная интерпретация
Прямой ход метода Гаусса с точки зрения матричных операций равносилен умножению исходной системы слева на последовательность матриц элементарных преобразований (L-матрицы). В итоге это приводит к разложению исходной матрицы A в произведение нижней (L) и верхней треугольной (U) матриц: A = L * U.
Метод Гаусса-Жордана для нахождения обратной матрицы
Это модификация, которая позволяет сразу получить обратную матрицу. Алгоритм продолжает идею метода Гаусса:
- К исходной матрице A справа приписывается единичная матрица I того же размера: [ A | I ].
- Методом Гаусса-Жордана левую часть (блок A) приводят не к треугольному, а к единичному виду с помощью тех же элементарных преобразований строк, применяемых ко всей расширенной матрице.
- Когда левая часть становится единичной матрицей I, правая часть преобразованной матрицы будет искомой обратной матрицей A⁻¹: [ I | A⁻¹ ].
Это равносильно подбору такой матрицы M, что M * A = I. По определению, матрица M и есть A⁻¹. Данный метод требует примерно в три раза больше операций, чем просто решение системы, но он систематичен и эффективен для ручных и машинных вычислений.