Ядерное оружие | Графика | Математика | Физика | Заказать курсовую | Информатика | ТКМ | Электротехника | Атомная энергетика | Лекции

Алгоритм нахождения решений произвольной системы линейных уравнений (метод Гаусса)

Пусть дана система $ m$ линейных уравнений с $ n$ неизвестными $ {Ax=b}$ . Требуется найти ее общее решение, если она совместна, или установить ее несовместность. Метод, который будет изложен в этом разделе, близок к методу вычисления определителя 5.1.с и к методу нахождения ранга матрицы (раздел 5.8). Предлагаемый алгоритм называется методом Гаусса или методом последовательного исключения неизвестных.

Выпишем расширенную матрицу системы

$\displaystyle A^*=\left(\begin{array}{ccccc}a_{11}&a_{12}&\dots&a_{1n}&b_1\\ ... ...{2n}&b_2\\ \hdotsfor{5}\\ a_{m1}&a_{m2}&\dots&a_{mn}&b_m\end{array}\right).$

Назовем элементарными операциями следующие действия с матрицами:

  1. перестановка строк;
  2. умножение строки на число, отличное от нуля;
  3. сложение строки с другой строкой, умноженной на число.

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

Читатель легко проверит, что если по матрице, полученной из $ A^*$ выполнением элементарной операции, восстановить систему уравнений, то новая система будет равносильна исходной.

Цель алгоритма -- с помощью применения последовательности элементарных операций к матрице $ A^*$ добиться, чтобы каждая строка, кроме, быть может, первой, начиналась с нулей, и число нулей до первого ненулевого элемента в каждой следующей строке было больше, чем в предыдущей.

Шаг алгоритма заключается в следующем. Находим первый ненулевой столбец в матрице $ A^*$ . Пусть это будет столбец с номером $ i$ . Находим в нем ненулевой элемент и строку с этим элементом меняем местами с первой строкой. Чтобы не нагромождать дополнительных обозначений, будем считать, что такая смена строк в матрице $ A^*$ уже произведена, то есть $ {a_{1i}\ne0}$ . Тогда ко второй строке прибавим первую, умноженную на число $ \left(-\dfrac{a_{2i}}{a_{1i}}\right)$ , к третьей строке прибавим первую, умноженную на число $ \left(-\dfrac{a_{3i}}{a_{1i}}\right)$ , и т.д. В результате получим матрицу

$\displaystyle A^*_1=\left(\begin{array}{cccccccc}0&\dots&0&a_{1i}&a_{1i+1}&\dot... ...\\ 0&\dots&0&0&a_{mi+1}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$
(Первые нулевые столбцы, как правило, отсутствуют.)

Если в матрице $ A^*_1$ встретилась строка с номером $ k$ , в которой все элементы $ a_{kj}^{(1)}$ равны нулю, а $ {b_k^{(1)}\ne0}$ , то выполнение алгоритма останавливаем и делаем вывод, что система несовместна. Действительно, восстанавливая систему уравнений по расширенной матрице, получим, что $ k$ -ое уравнение будет иметь вид

$\displaystyle 0\cdot x_1+0\cdot x_2+\ldots0\cdot x_n=b_k^{(1)}.$
Этому уравнению не удовлетворяет ни один набор чисел $ {x_1,x_2,\dots,x_k}$ .

Матрицу $ A^*_1$ можно записать в виде

$\displaystyle A^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar... ...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it B*}\end{array}\right),$
где
$\displaystyle B^*=\left(\begin{array}{ccccc} a_{2i+1}^{(1)}&a_{2i+2}^{(1)}&\do... ... a_{mi+1}^{(1)}&a_{mi+2}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$
По отношению к матрице $ B^*$ выполняем описанный шаг алгоритма. Получаем матрицу
$\displaystyle B_1^*=\left(\begin{array}{cccccccc} 0&\dots&0&a_{2j}^{(2)}&a_{2j... ...\\ 0&\dots&0&0&a_{mj+1}^{(2)}&\dots&a_{mn}^{(2)}&b_m^{(2)}\end{array}\right),$
где $ j>i$ , $ a_{2j}^{(2)}\ne0$ . Эту матрицу снова можно записать в виде
$\displaystyle B^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar... ...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it C*}\end{array}\right),$
и к матрице $ C^*$ снова применим описанный выше шаг алгоритма.

Процесс останавливается, если после выполнения очередного шага новая уменьшенная матрица состоит из одних нулей или если исчерпаны все строки. Заметим, что заключение о несовместности системы могло остановить процесс и ранее.

Если бы мы не уменьшали матрицу, то в итоге пришли бы к матрице вида

$\displaystyle \tilde A^*=\left(\begin{array}{ccccccccccccc} 0&\dots&0&a_{1i}^{... ... \hdotsfor{13}\\ 0&\dots&0&0&\dots&0&0&\dots&0&0&\dots&0&0\end{array}\right).$
Заказать перевод
Далее выполняется так называемый обратный ход метода Гаусса. По матрице $ \tilde A^*$ составляем систему уравнений. В левой части оставляем неизвестные с номерами, соответствующими первым ненулевым элементам в каждой строке, то есть $ {x_i,\,x_j,\,\dots,x_r}$ . Заметим, что $ {r={\rm Rg}A}$ . Остальные неизвестные переносим в правую часть. Считая неизвестные в правой части некоторыми фиксированными величинами, несложно выразить через них неизвестные левой части.

Теперь, придавая неизвестным в правой части произвольные значения и вычисляя значения переменных левой части, мы будем находить различные решения исходной системы $ {Ax=b}$ . Чтобы записать общее решение, нужно неизвестные в правой части обозначить в каком-либо порядке буквами $ {C_1,\,C_2,\dots,C_{n-r}}$ , включая и те неизвестные, которые явно не выписаны в правой части из-за нулевых коэффициентов, и тогда столбец неизвестных можно записать в виде столбца, где каждый элемент будет линейной комбинацией произвольных величин $ {C_1,\,C_2,\dots,C_{n-r}}$ (в частности, просто произвольной величиной $ C_k$ ). Эта запись и будет общим решением системы.

Если система была однородной, то получим общее решение однородной системы. Коэффициенты при $ C_1$ , взятые в каждом элементе столбца общего решения, составят первое решение из фундаментальной системы решений, коэффициенты при $ C_2$  -- второе решение и т.д.

Фундаментальную систему решений однородной системы можно получить и другим способом. Для этого одному переменному, перенесенному в правую часть, нужно присвоить значение 1, а остальным -- нули. Вычислив значения переменных в левой части, получим одно решение из фундаментальной системы. Присвоив другому переменному в правой части значение 1, а остальным -- нули, получим второе решение из фундаментальной системы и т.д.

        Замечание 15.4   У читателя может возникнуть вопрос: "Зачем рассматривать случай, когда некоторые столбцы матрицы $ A^*$ нулевые? Ведь в этом случае соответствующие им переменные в системе уравнений в явном виде отсутствуют." Но дело том, что в некоторых задачах, например, при нахождении собственных чисел матрицы, такие системы возникают, и игнорировать отсутствующие переменные нельзя, так как при этом происходит потеря важных для задачи решений.         
      

Главы учебника "Курс лекций высшей математики"

 

Платформу клиент-сервер | ActiveX-компоненты | Базы данных | Конструктор форм | Электро | ТОЭ | Linux | Интегралы | Лекции физика | Windows 2003 | Архитектура ЭВМ | Рисунок | Световые волны | Операционные системы
Pascal | Эксперт | Учебник Java | Кодирование | Пефирия ПК | Информатика | Сети | Моделирование | Язык SQL Расчет надежности | Задачи