Система линейных уравнений: методы решения¶
Система уравнений — это совокупность двух или более уравнений с общими неизвестными, которые необходимо удовлетворить одновременно. Решением такой системы называется набор значений неизвестных, делающий все уравнения системы тождественно верными. Наиболее изучены и распространены линейные системы уравнений — системы, в которых неизвестные входят в уравнения только в первой степени и не перемножаются между собой.
¶Виды систем уравнений
Системы уравнений классифицируются по нескольким признакам.
По типу уравнений различают:
- Линейные системы — неизвестные входят линейно (степень 1). Наиболее простой и изученный случай.
- Нелинейные системы — содержат степени, показательные, логарифмические или тригонометрические функции от неизвестных.
- Смешанные системы — сочетают линейные и нелинейные уравнения.
По числу уравнений и неизвестных системы делятся на квадратные (число уравнений равно числу неизвестных), вырожденные (уравнений меньше, чем неизвестных) и переопределённые (уравнений больше, чем неизвестных).
¶Методы решения линейных систем
¶Метод подстановки
Простейший метод. Одно из уравнений решается относительно одного неизвестного, после чего полученное выражение подставляется в остальные уравнения. В результате число неизвестных уменьшается на единицу. Процесс повторяется до тех пор, пока не останется уравнение с одним неизвестным.
Пример для системы: `` x + y = 10 2x − y = 5 `` Из первого уравнения: x = 10 − y. Подставляя во второе: 2(10 − y) − y = 5, откуда 20 − 3y = 5, y = 5, x = 5.
¶Метод сложения (вычитания)
Уравнения системы складывают или вычитают друг от друга так, чтобы одно из неизвестных сократилось. Для приведённого примера достаточно сложить оба уравнения: 3x = 15, откуда x = 5, а затем найти y = 5.
¶Метод Крамера
Применяется к квадратной линейной системе. Основан на вычислении определителей. Для системы: `` a₁x + b₁y = c₁ a₂x + b₂y = c₂ `` Главный определитель Δ = a₁b₂ − a₂b₁. Если Δ ≠ 0, система имеет единственное решение:
- x = Δ₁ / Δ, где Δ₁ получается заменой первого столбца на столбец свободных членов;
- y = Δ₂ / Δ, где Δ₂ получается заменой второго столбца на столбец свободных членов.
Если Δ = 0, но хотя бы один из Δ₁, Δ₂ не равен нулю, системы несовместимы (решений нет). Если все три определителя равны нулю, система имеет бесконечно много решений либо несовместима — требуется дополнительный анализ.
¶Метод Гаусса
Наиболее общий и эффективный алгоритм для систем любой размерности. Состоит из двух этапов:
- Прямой ход — элементарными преобразованиями строк приведение системы к ступенчатой (треугольной) форме, при которой в каждом следующем уравнении число неизвестных меньше, чем в предыдущем.
- Обратный ход — решение уравнений снизу вверх методом подстановки.
Для системы трёх уравнений с тремя неизвестными прямой ход выглядит так: первое уравнение используется для исключения первого неизвестного из второго и третьего, затем второе — для исключения второго неизвестного из третьего. В результате третье уравнение содержит одно неизвестное.
¶Матричный метод
Линейная система записывается в виде AX = B, где A — матрица коэффициентов, X — столбец неизвестных, B — столбец свободных членов. Если определитель матрицы A не равен нулю, решение имеет вид X = A⁻¹B, где A⁻¹ — обратная матрица. На практике обратная матрица вычисляется через алгебраические дополнения.
¶Численные методы
Для систем большой размерности (сотни и тысячи уравнений) прямые методы (Гаусса, Крамера) вычислительно дороги. Применяют итерационные методы:
- Метод простых итераций — последовательное приближение к решению через повторное применение итерационной формулы.
- Метод Зейделя — улучшение простых итераций, при котором уже вычисленные новые значения компонент используются немедленно.
- Метод релаксации — взвешенное сочетание предыдущего и нового приближений.
Итерационные методы сходятся при выполнении условия диагонального преобладания матрицы коэффициентов.
¶Решение нелинейных систем
Для нелинейных систем прямых общих методов не существует. Применяют:
- Графический метод — построение графиков уравнений системы; решение соответствует точкам пересечения.
- Метод Ньютона — линеаризация системы вблизи начального приближения и решение вспомогательной линейной системы.
- Численные методы — методы Ньютона, простых итераций, метод секущих, адаптированные для многомерного случая.
¶Применение
Системы уравнений находят применение в физике (законы Кирхгофа в электротехнике, задачи механики), химии (расчёт состава смесей), экономике (модели равновесия Лежандра и Вальраса), компьютерной графике (решение уравнений пересечения лучей и поверхностей), криптографии (линейные системы над конечными полями лежат в основе атак на некоторые шифры). В инженерных расчётах линейные системы размерностью в тысячи и десятки тысяч неизвестных решаются на ЭВМ методами Гаусса, Холецкого и итерационными методами.
¶Историческая справка
Системы линейных уравнений изучались ещё в Древнем Китае: в трактате «Девять глав о математическом искусстве» (около I века н. э.) описан метод, эквивалентный прямому ходу метода Гаусса. В Европе метод Гаусса был опубликован Карлом Фридрихом Гауссом в 1801 году, хотя аналогичные приёмы использовались и ранее. Метод Крамера назван в честь швейцарского математика Габриэля Крамера, опубликовавшего его в 1750 году.