Решение системы общего вида

Пусть задана система линейных уравнений общего вида (16.1), где , т. е. число неизвестных не меньше числа уравнений. Представим общий порядок решения этой системы.

Необходимо определить совместность системы, т.е. определить сначала ранги матрицы системы А и расширенной матрицы А_В. По теореме Кронекера-Капелли, если ранги этих матриц не совпадают, то система несовместна, и тогда нет смысла ее решать. Если же ранги матриц А и А_В равны, то система (16.1) совместна.

Определение. Рангом совместной системы линейных алгебраических уравнений называется ранг ее матрицы.

Пусть система (16.1) совместна и ранг ее равен k. Выделим в матрице системы (16.2) некоторый базисный минор; предположим, что именно первые г строк матриц А и А_В являются базисными. Тогда по теореме о базисном миноре остальные строки матрицы являются линейными комбинациями остальных строк. В свою очередь, это означает, что в системе (16.1) первые r уравнений, соответствующие базисным строкам матрицы А, являются базисными, а остальные — их линейными комбинациями. Тогда эти (m — r) уравнений можно удалить из системы, причем в результате указанных элементарных преобразований мы получаем эквивалентную систему:

(16.13)

Система (16.13) характерна тем, что ее ранг равен числу уравнений в ней, причем , т. е. ранг не превосходит число неизвестных. Поэтому возможны два случая: либо , либо .

В первом случае система (16.13) имеет квадратную невырожденную матрицу порядка r и, согласно теореме Крамера (теорема 16.2), существует единственное решение этой системы. Иными словами, если ранг системы равен числу неизвестных, то система имеет единственное решение, т. е. она является определенной.

Рассмотрим теперь случай, когда . Перенесем в правые части уравнений (16.13) все слагаемые, содержащие неизвестные х_{r+ 1}, х_{r+ 2}, …, x_n. Тогда система принимает вид

(16.14)

Неизвестным х_{r+ 1}, х_{r+ 2}, …, x_n можно придавать любые значения, и потому они называются свободными. Неизвестные х ₁, х ₂, …, x_r соответствующие базисным столбцам, называются базисными. Из системы (16.14) легко найти выражения базисных неизвестных через свободные, согласно теореме Крамера, рассматривая правые части этих уравнений как элементы столбца свободных членов, содержащие х_{r+ 1}, х_{r+ 2}, …, x_n. Можно показать, что базисные неизвестные х ₁, х ₂, …, x_r линейно выражаются через свободные неизвестные. Поскольку свободные неизвестные могут принимать любые значения, то в случае, когда ранг совместной системы меньше числа неизвестных, эта система является неопределенной: она имеет бесчисленное множество решений.

Метод Гаусса

Следует заметить, что вычисления как по методу обратной матрицы, так и по методу Крамера являются очень трудоемкими. Оба они требуют порядка п ² п!арифметических действий для нахождения решения системы линейных уравнений. При п = 5 это составит около 3000 действий, при п = 10 — около 3, 6 · 10⁸ действий. При решении серьезных задач приходится иметь дело с системами уравнений порядка п = 100 и более. При таких масштабах даже суперкомпьютерам потребуется долгое время для вычисления решения. Кроме того, погрешности компьютерного округления чисел приводят к большим ошибкам в численных расчетах решения систем уравнений большого порядка. Между тем существуют более экономичные методы решения систем линейных уравнений, основанные на предварительном преобразовании расширенной матрицы системы к специальному виду, в частности метод Гаусса. Рассмотрим его практическую реализацию.

Пусть для определенности в системе уравнений общего вида (16.1) (если а₁₁ = 0, то можно переставить на первое место ненулевое слагаемое или начать с другого уравнения). Умножим первое уравнение системы (16.1) на число a ₂₁/ a ₁₁ и вычтем его из второго уравнения этой системы. Затем умножим обе части первого уравнения на число a ₃₁/ a ₁₁ и вычтем его из третьего уравнения и так далее, т. е. процесс заключается в последовательном вычитании первого уравнения, умножаемого на числа a_{i 1}/ a ₁₁, из i -го уравнения (i = 2, 3,..., т).Таким образом, в результате элементарных преобразований мы получим эквивалентную систему, в которой, начиная со второго уравнения, отсутствуют слагаемые, содержащие неизвестную х ₁:

(16.15)

где верхний индекс в скобках означает новые коэффициенты полученные после первого шага. Для уменьшения громоздкости записи удобнее оперировать расширенной матрицей системы, отделяя в ней вертикальной чертой столбец свободных членов. Итак, после первого шага, содержащего (m —1) элементарных преобразований системы, мы переходим от расширенной матрицы (16.5) исходной системы к расширенной матрице

(16.16)

Второй шаг заключается в том, что теперь второе уравнение системы (16.13), или вторая строка матрицы (16.14), используется для аналогичных элементарных преобразований строк с третьей по m -ю: эта строка последовательно умножается на число и вычитается из i -й строки (r = 3, 4,..., m). В результате этих (m-2) элементарных преобразований получаем новую расширенную матрицу, соответствующую новой эквивалентной системе уравнений. Эта матрица имеет вид

(16.17)

где верхний индекс означает новые коэффициенты. В случае если элемент , второе уравнение можно поменять местами с другим уравнением, у которого элемент .

Продолжим этот процесс аналогичным образом (т.е. на третьем шаге преобразуются строки с 4-й по m -ю, на четвертом шаге — строки с 5-й по m -ю и т.д.) до тех пор, пока не пойдем до последней m -й строки. После (r –1)-ro шага процесса последовательного исключения неизвестных мы получим следующую расширенную матрицу:

(16.18)

Последние (m-r) строк этой матрицы соответствуют уравнениям эквивалентной системы уравнений

(16.19)

Эти уравнения могут появиться, если соответствующие уравнения исходной системы (16.1) представляют собой линейные комбинации других уравнений этой системы. Здесь мы не исследовали заранее систему (16.1) на совместность; поэтому если эта система несовместна, то хотя бы одно из чисел не равно нулю. Таким образом, метод Гаусса позволяет на определенном шаге установить возможную несовместность исходной системы линейных уравнений или выявить и удалить уравнения, являющиеся линейными комбинациями других уравнений системы (16.1), если она совместна.

Пусть система (16.1) совместна, тогда все правые части Уравнений (16.19) равны нулю, и после удаления нулевых уравнений в эквивалентной системе и нулевых строк в расширенной матрице получаем матрицу специфического ступенчатого вида, ранг которой равен r. Все элементы этой матрицы, стоящие слева или ниже элементов а_ii равны нулю:

(16.20)

Эта расширенная матрица соответствует системе уравнений ранга r, которая имеет вид

(16.21)

Полученная система уравнений (16.21) позволяет найти решение, осуществляя процесс снизу вверх, т.е. от последнего уравнения к первому. Переход от системы (16.1) к эквивалентной ей системе (16.21) называется прямым ходом, а нахождение неизвестных из системы (16.21) — обратным ходом метода Гаусса. Далее последовательность действий аналогична последовательности для решения системы линейных уравнений общего вида.

Если r = п, то система (16.21) имеет вид

(16.22)

Поднимаясь снизу вверх, последовательно находим (обратный ход метода Гаусса):

· из последнего r -го уравнения неизвестное ;

· из (r –1)-го уравнения неизвестное х_{r- 1}путем подстановки в это уравнение уже найденного неизвестного х_r;

· из i -го уравнения неизвестное х_i при подстановке в него найденных величин х_r, x_{r- 1}, …, x_{i +1};

· и так далее до первого уравнения, из которого при подстановке в него уже найденных величин х_r, x_{r- 1}, …, x ₂ находим x₁.

Если ранг системы уравнений (16.21) r < п, объявляем неизвестные х_r+1, x_r+2, …, х_п свободными и формируем правые части уравнений (16.21), оставляя в левых частях слагаемые, содержащие базисные переменные х ₁, x ₂, …, x_r:

(16.23)

Решение этой системы находится обратным ходом метода; теперь базисные неизвестные зависят от свободных неизвестных, которые могут принимать любые значения, а потому система (16.1) имеет бесчисленное множество решений.

Рассмотрим примеры решения систем линейных уравнений методом Гаусса.

Не нашли, что искали? Воспользуйтесь поиском: