Системы линейных уравнений: методы решения¶
Система уравнений — это совокупность двух или более уравнений с несколькими неизвестными, которые необходимо удовлетворить одновременно. Решением системы называется набор значений неизвестных, делающий все уравнения системы тождественно верными. Наиболее изучены системы линейных (алгебраических первого степени) уравнений; для них разработаны эффективные методы, применяемые в математике, физике, экономике и программировании.
¶Классификация систем уравнений
Системы уравнений разделяются по характеру уравнений:
- Линейные системы — каждое уравнение является линейной комбинацией неизвестных. Общая форма: $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n = b_i$.
- Нелинейные системы — содержат степени неизвестных выше первой, произведения неизвестных, тригонометрические или показательные функции.
- Однородные системы — свободные члены $b_i$ равны нулю.
- Квадратичные системы — содержат квадраты неизвестных.
По числу решений линейная система бывает совместной (имеет хотя бы одно решение) и несовместной (решений нет). Совместная система в свою очередь делится на определённую (единственное решение) и неопределённую (бесконечное семейство решений).
¶Метод克莱ramerа (определительный метод)
Для системы из $n$ линейных уравнений с $n$ неизвестными, коэффициенты которой образуют невырожденный определитель $\Delta \neq 0$, решение находится по формулам Крамера:
$$x_i = \frac{\Delta_i}{\Delta},$$
где $\Delta$ — определитель матрицы коэффициентов, а $\Delta_i$ — определитель, полученный заменой $i$-го столбца матрицы коэффициентов столбцом свободных членов.
Если $\Delta = 0$, а хотя бы один $\Delta_i \neq 0$, система несовместна. Если все определители равны нулю, система неопределённа.
¶Метод Гаусса
Наиболее универсальный и вычислительно устойчивый метод. Состоит в приведении расширенной матрицы системы к ступенчатому (треугольному) виду элементарными преобразованиями строк:
- Прямой ход — с помощью перестановки строк, умножения строки на ненулевое число и прибавления одной строки к другой обнуляются элементы под главной диагональю.
- Обратный ход — из треугольной системы вычисляются неизвестные, начиная с последнего уравнения.
Метод Гаусса применим к системам любого размера, включая неопределённые и несовместные, и требует примерно $2n^3/3$ арифметических операций для системы порядка $n$.
¶Матричный метод
Система линейных уравнений записывается в виде $AX = B$, где $A$ — матрица коэффициентов, $X$ — столбец неизвестных, $B$ — столбец свободных членов. Если $A$ обратима, решение имеет вид $X = A^{-1}B$.
На практике обращение матрицы выполняют методом Гаусса или с помощью LU-разложения. Матричный подход удобен при решении нескольких систем с одной матрицей коэффициентов и разными правыми частями.
¶Численные методы
Для систем высокого порядка (сотни и тысячи неизвестных) прямые методы уступают место итерационным:
- Метод Зейделя — последовательное уточнение компонент вектора решения.
- Метод простой итерации (Якоби) — обновление всех компонент одновременно по предыдущему приближению.
- Метод релаксации — ускоренная итерация с параметром релаксации.
- Метод наименьших квадратов — для переопределённых систем (число уравнений больше числа неизвестных) минимизируется сумма квадратов невязок.
Итерационные методы сходятся при выполнении условия диагонального преобладания или при положительной определённости матрицы.
¶Решение нелинейных систем
Для нелинейных систем применяются:
- Метод Ньютона — линеаризация системы в текущем приближении и решение вспомогательной линейной системы.
- Метод сопряжённых градиентов — для квадратичных функционалов.
- Графический метод — для двух уравнений с двумя неизвестными: решение — точки пересечения линий.
- Метод подстановки — выражение одной неизвестной из одного уравнения и подстановка в другое.
¶Применение
Системы линейных уравнений возникают при решении задач на смешивание, распределении ресурсов, нахождении токов в электрических цепях (законы Кирхгофа), построении интерполяционных многочленов, в методе конечных элементов. В компьютерной алгебре решения ищутся символьно, в численной линейной алгебре — с учётом ошибок округления и обусловленности матрицы.
¶Историческая справка
Метод Гаусса назван по имени Карла Фридриха Гаусса, опубликовавшего его в 1810 году, хотя элементы метода были известны ещё в Китае I века до н. э. («Девятиглавая книга»). Формулы Крамера выведены Габриэлем Крамером в 1750 году. Матричная теория систем была развита в трудах Германа Грассмана и Кэли в XIX веке.
¶Источники
- Кудрявцев Л. Д. «Курс математического анализа»
- Фаддеев Д. К., Соминский И. С. «Задачи по алгебре»
- Прасолов В. В. «Задачи и теоремы линейной алгебры»
- Гантмахер Ф. Р. «Теория матриц»