Основы математики и ее приложения в экономическом образовании (стр. 23 )

4. Рассмотрим теперь случай, когда r < п. Перенесем в правые части уравнений (15.7) все слагаемые, содержащие не­известные xr+1, xr+2, …, xп. Тогда система принимает вид

Неизвестным xr+1, ..., xп можно придавать любые значения, и потому они называются свободными. Неизвестные х1, x2, ..., xr соответствующие базисным столбцам, называются базисными. Из системы (15.8) легко найти выражения базисных неизвест­ных через свободные, согласно теореме Крамера, рассматри­вая правые части этих уравнений как элементы столбца сво­бодных членов, содержащие xr+1, xr+2,…, хп. Можно показать, что базисные неизвестные x1, х2, ..., xr линейно выражаются через свободные неизвестные. Поскольку свободные неизвест­ные могут принимать любые значения, то в случае когда ранг совместной системы меньше числа неизвестных, эта система является неопределенной: она имеет бесчисленное множество решений.

Метод Гаусса

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

Рассмотрим систему уравнений общего вида (15.1). Пусть для определенности a11 ≠ 0 (если a11 = 0, то можно переста­вить на первое место ненулевое слагаемое или начать с другого уравнения). Умножим первое уравнение системы (15.1) на чис­ло a21/a11 и затем вычтем его из второго уравнения этой системы. Умножим обе части первого уравнения на число a31/a11 и затем вычтем его из третьего уравнения и так далее, т. е. процесс заключается в последовательном вычитании первого уравнения, умножаемого на числа ai1/a11, из i-го уравнения (i = 2, 3, ... , m). Таким образом, в результате элементарных преобразований мы получим эквивалентную систему, в кото­рой начиная со второго уравнения отсутствуют слагаемые, со­держащие неизвестное x1:

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

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

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

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

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

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

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

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

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

1. Если r = n, то система (15.12) имеет вид

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

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

— из (r - 1)-го уравнения неизвестное xr-1 путем подста­новки в это уравнение уже найденного неизвестного xr;

— из i-го уравнения неизвестное xi при подстановке в него найденных величин xr, xr-1, ..., xi-1;

— и так далее до первого уравнения, из которого при под­становке в него уже найденных величин xr, xr-1 , ..., x2 находим х1.

2. Ранг системы уравнений (15.12) меньше n. В этом слу­чае, как и ранее, объявляем неизвестные xr+1, xr+2, …, xп, сво­бодными и формируем правые части уравнений (15.12), остав­ляя в левых частях слагаемые, содержащие базисные перемен­ные x1, x2, ..., xr:

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

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

Пример 2. Пример 1 п. 15.2.

Решение. Выпишем расширенную матрицу этой системы; справа в скобках укажем числа, на которые умножается соот­ветствующая строка матрицы для того, чтобы сложить ее с нижними строками. Горизонтальными стрелками показаны пе­реходы к расширенным матрицам эквивалентных систем. Пер­вую строку расширенной матрицы исходной системы умножа­ем последовательно на (-2) и (-1) и прибавляем ее соответ­ственно к 2-й и 3-й строкам этой матрицы. После первого шага, состоящего в "обнулении" первого столбца согласно формуле (15.9), получаем (номера шагов показаны перед стрелками пе­рехода)

Второй шаг прямого хода метода Гаусса состоит в операциях с преобразованной расширенной матрицей: прибавляем вторую строку, умноженную на (-3), к 3-й строке:

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

которая эквивалентна исходной системе. Отсюда последова­тельно находим: z = -1/2, у = 0,х = 1/2) = 3/2.

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

Решение. Составим расширенную матрицу этой системы, после чего выполним соответствующие шаги прямого хода ме­тода Гаусса. Имеем

Последняя нулевая строка в расширенной матрице, полученной после 3-го шага, появилась из-за того, что в исходной системе четвертое уравнение является суммой 1-го и 3-го уравнений. Система совместная, и после удаления нулевой строки заклю­чительный вид расширенной матрицы соответствует системе трех уравнений с четырьмя неизвестными (ранг системы мень­ше числа неизвестных). Полагая x4 свободной переменной, по­лучаем

Из этой системы обратным ходом метода Гаусса находим

Данная система уравнений имеет бесчисленное множество ре­шений, поскольку x4 может принимать любые значения.

15.3. Вычисление обратной матрицы методом Гаусса

Метод Гаусса является поистине универсальным в решении систем линейных алгебраических уравнений. Мы продемонст­рируем применение этого метода при вычислении обратных матриц.

Практически этот наиболее простой способ вычисления об­ратной матрицы состоит в следующих шагах.

1. К матрице А, по отношению к которой ищется обратная матрица, приписывается справа единичная матрица Е.

2. Путем преобразований методом Гаусса над строками рас­ширенной матрицы (А|Е) матрица А приводится к виду еди­ничной матрицы.

3. После окончания указанного вычислительного процесса, т. е. когда на месте исходной матрицы А будет сформирована единичная матрица, на месте приписанной справа единичной матрицы Е будет находиться обратная матрица А-1. Иными словами, вместо расширенной матрицы (А|Е) в итоге получaется расширенная матрица (E|A-1).

Продемонстрируем эту последовательность действий на не­сложном примере.

Пример 1. Найти обратную матрицу исходной матрицы

Решение. Выполняем последовательно шаги 1 — 3:

Схема вычислений по методу Гаусса пояснена здесь теми же обозначениями, что и в п. 15.2, при этом стрелками показано, к какой строке прибавляется измененная строка. Последний этап вычислений, показанный стрелкой (3), состоит в делении по­следней строки расширенной матрицы на -2. Итак, обратная матрица имеет вид

Нетрудно непосредственно проверить правильность прове­денных вычислений по определению обратной матрицы: АА-1 = А-1А.

15.4. Геометрическая интерпретация системы линейных уравнений

Как известно, уравнения с двумя переменными вида

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

Уравнение с тремя переменными вида

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

В случае системы уравнений с n неизвестными каждое ура­внение вида

можно интерпретировать как гиперплоскость в координатном пространстве An. Решение системы (15.1) — это множество точек пространства An, которые принадлежат одновременно всем m гиперплоскостям, соответствующим уравнениям этой системы.

15.5. Однородные системы линейных уравнений

Определение 1. Система линейных уравнений называется од­нородной, если во всех ее уравнениях свободные члены равны нулю.

В общем случае однородная система (или система однород­ных уравнений) имеет вид

Однородная система уравнений всегда совместна. Дейст­вительно, набор значений неизвестных xi = 0 (i = 1, 2,... , п) удовлетворяет всем уравнениям системы. Это решение одно­родной системы называется нулевым, или тривиальным.

Решение системы однородных уравнений

Вопрос о существовании ненулевого решения однородной системы линейных уравнений (15.14) разрешает следующая те­орема.

ТЕОРЕМА 3. Однородная система имеет ненулевое решение тогда и только тогда, когда ранг этой системы меньше чис­ла ее неизвестных.

Из этой теоремы вытекают два важных следствия.

Следствие 1. Если число уравнений однородной сис­темы меньше числа ее неизвестных, то эта система имеет ненулевое решение.

Следствие 2. Если в однородной системе число урав­нений равно числу неизвестных, то она имеет ненулевое ре­шение тогда и только тогда, когда определитель матрицы системы равен нулю.

Фундаментальная система решений

Решения однородной системы обладают следующими свой­ствами. Если вектор = (α1, α2,... ,αn) является решением системы (15.14), то и для любого числа k вектор k = (kα1, kα2,..., kαn) будет решением этой системы. Если решением сис­темы (15.14) является вектор = (γ1, γ2, ... ,γn), то сумма + также будет решением этой системы. Отсюда следует, что любая линейная комбинация решений однородной системы также является решением этой системы.

Как мы знаем из п. 12.2, всякая система n-мерных век­торов, состоящая более чем из п векторов, является линей­но зависимой. Таким образом, из множества векторов-решений однородной системы (15.14) можно выбрать базис, т. е. любой вектор-решение данной системы будет линейной комбинацией векторов этого базиса. Любой такой базис называется фунда­ментальной системой решений однородной системы линейных уравнений. Справедлива следующая теорема, которую мы при­водим без доказательства.

ТЕОРЕМА 4. Если ранг r системы однородных уравнений (15.14) меньше числа неизвестных п, то всякая фундамен­тальная система решений системы (15.14) состоит из п - r решений.

Укажем теперь способ нахождения фундаментальной сис­темы решений (ФСР). Пусть система однородных уравнений (15.14) имеет ранг r < п. Тогда, как следует из правил Краме­ра, базисные неизвестные этой системы x1, x2, … xr линейно выражаются через свободные переменные xr+1, xr+2 , ..., xп:

Выделим частные решения однородной системы (15.14) по сле­дующему принципу. Для нахождения первого вектора-решения 1 положим xr+1 = 1, xr+2 = xr+3 = ... = xn = 0. Затем на­ходим второе решение 2: принимаем xr+2 = 1, а остальные r - 1 свободных переменных положим нулями. Иными словами, мы последовательно присваиваем каждой свободной перемен­ной единичное значение, положив остальные нулями. Таким образом, фундаментальная система решений в векторной фор­ме с учетом первых r базисных переменных (15.15) имеет вид

ФСР (15.16) является одним из фундаментальных наборов решений однородной системы (15.14).

Пример 1. Найти решение и ФСР системы однородных урав­нений

Решение. Будем решать эту систему методом Гаусса. По­скольку число уравнений системы меньше числа неизвестных, считаем х1, x2, х3 базисными неизвестными, а x4, х5, x6 — сво­бодными переменными. Составим расширенную матрицу сис­темы и выполним действия, составляющие прямой ход метода:

Преобразованная расширенная матрица соответствует системе уравнений, которая эквивалентна исходной однородной системе: