Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Метод Гаусса решения системы линейных уравнений
ОглавлениеЛинейная алгебра

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


Пусть дана система (5.3) [math]m[/math] линейных уравнений с [math]n[/math] неизвестными. Для ее решения нужно выполнить следующие действия.


1. Составить расширенную матрицу (5.7) системы:


[math]\begin{pmatrix}A\mid b\end{pmatrix}= \begin{pmatrix} a_{11}&\cdots&a_{1n}\!\!&\vline\!\!&b_1\\ \vdots&\ddots&\vdots\!\!&\vline\!\!& \vdots\\ a_{m1}&\cdots&a_{mn}\!\!&\vline\!\!&b_m\end{pmatrix}\!.[/math]

2. Используя элементарные преобразования над строками матрицы [math]\begin{pmatrix}A\mid b\end{pmatrix}[/math], привести ее к ступенчатому виду. Если базисный минор матрицы [math]A[/math] расположен в первых [math]r[/math] строках и [math]r[/math] столбцах, получится следующий вид:


[math]\begin{pmatrix} \widetilde{A}\mid \widetilde{b}\end{pmatrix}= \begin{pmatrix} 1&\widetilde{a}_{12}&\cdots&\widetilde{a}_{1r}&\cdots&\widetilde{a}_{1n}\!\!&\vline\!\!&\widetilde{b}_1\\ 0&1&\cdots&\widetilde{a}_{2r}&\cdots&\widetilde{a}_{2n}\!\!&\vline\!\!&\widetilde{b}_2\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\!\!&\vline\!\!&\vdots\\ 0&0&\cdots&1&\cdots& \widetilde{a}_{m}\!\!&\vline\!\!&\widetilde{b}_r\\ 0&0&\cdots&0&\cdots&0\!\!&\vline\!\!& \widetilde{b}_{r+1}\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\!\!&\vline\!\!&\vdots\\ 0&0&\cdots&0&\cdots&0\!\!&\vline\!\!&0 \end{pmatrix}\!.[/math]
(5.8)

3. Выяснить, совместна система или нет. Для этого определить ранги матриц [math]A[/math] и [math](A\mid b):[/math]


[math]\operatorname{rg}A=\operatorname{rg}\widetilde{A}=r[/math] — число ненулевых строк в матрице [math]\widetilde{A}[/math];


[math]\operatorname{rg}(A\mid b)= \operatorname{rg}(\widetilde{A}\mid \widetilde{b})= \begin{cases}r+1,&\text{if}\quad \widetilde{b}_{r+1}\ne0,\\ \phantom{r}r,&\text{if}\quad \widetilde{b}_{r+1}=0.\end{cases}[/math]


Если [math]\operatorname{rg}A\ne \operatorname{rg}(A\mid b)[/math] (при [math]\widetilde{b}_{r+1}\ne0[/math]), то система не имеет решений. Процесс решения завершен. Если [math]\operatorname{rg}A=\operatorname{rg}(A\mid b)[/math] (при [math]\widetilde{b}_{r+1}=0[/math]), то система совместна. Процесс решения продолжается.


4. Для совместной системы [math]\operatorname{rg}A=\operatorname{rg}(A\mid b)=r[/math] привести матрицу [math](\widetilde{A}\mid \widetilde{b})[/math] к упрощенному виду. Для этого при помощи элементарных преобразований над строками добиваемся того, чтобы в каждом столбце, входящем в базисный минор, все элементы были равны нулю, за исключением одного, равного единице. Если базисный минор матрицы [math]A[/math] расположен в первых [math]r[/math] строках и первых [math]r[/math] столбцах, то матрица приводится к упрощенному виду:


[math]\begin{pmatrix}A'\mid b'\end{pmatrix}= \begin{pmatrix} 1&0&\cdots&0&a'_{1\,r+1}&\cdots&a'_{1n}\!\!&\vline\!\!&b'_1\\ 0&1&\cdots&0&a'_{2\,r+1}&\cdots&a'_{2n}\!\!&\vline\!\!&b'_2\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\!\!&\vline\!\!&\vdots\\ 0&0&\cdots&1&a'_{r\,r+1}&\cdots&a'_{m}\!\!&\vline\!\!&b'_r\\ 0&0&\cdots&0&0&\cdots&0\!\!&\vline\!\!&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\!\!&\vline\!\!&\vdots\\ 0&0&\cdots&0&0&\cdots&0\!\!&\vline\!\!&0 \end{pmatrix}\!.[/math]
(5.9)

Первые четыре пункта составляют прямой ход метода Гаусса. В результате прямого хода исходная система существенно упрощается (имеет вид [math]A'x=b'[/math]):


[math]\begin{cases}x_1+a'_{1\,r+1}x_{r+1}+\ldots+a'_{1n}x_n=b'_1,\\ \cdots\cdots\cdots\cdots\cdots\\ x_r+a'_{r\,r+1}x_{r+1}+\ldots+a'_{rn}x_n=b'_r. \end{cases}[/math]
(5.10)

5. По упрощенному виду (5.9) разделяем все неизвестные [math]x_1,x_2,\ldots,x_n[/math] на базисные и свободные. Неизвестные, которым соответствуют столбцы, входящие в базисный минор, называются базисными переменными, остальные неизвестные — свободными переменными. Для системы (5.10) базисными переменными являются [math]x_1,x_2,\ldots,x_r[/math], свободными переменными[math]x_{r+1},x_{r+2},\ldots,x_n[/math] . Выражаем в (5.10) базисные переменные через свободные:


[math]\begin{cases}x_1=b'_1-a'_{1\,r+1}x_{r+1}-\ldots-a'_{1n}x_n,\\ \cdots\cdots\cdots\cdots\cdots\\ x_r=b'_r-a'_{r\,r+1}x_{r+1}-\ldots-a'_{rn}x_n.\end{cases}[/math]
(5.11)

Если ранг [math]r[/math] матрицы системы равен числу [math]n[/math] неизвестных [math](r=\operatorname{rg}A=n)[/math], то левый блок матрицы (5.9) будет представлен единичной матрицей [math]E_n:[/math]


[math]\begin{pmatrix}A'\mid b'\end{pmatrix}= \begin{pmatrix}1&0&\cdots&0\!\!&\vline\!\!&b'_1\\ 0&1&\cdots&0\!\!&\vline\!\!&b'_2\\ \vdots&\vdots&\ddots&\vdots\!\!&\vline\!\!&\vline\\ 0&0&\cdots&1\!\!&\vline\!\!&b'_n\end{pmatrix}\!.[/math]

Все неизвестные [math]x_1,x_2,\ldots,x_n[/math] будут базисными и формула (5.11) будет определять единственное решение системы


[math]\begin{cases}x_1=b'_1,\\x_2=b'_2,\\\vdots\\x_n=b'_n.\end{cases}[/math]
(5.12)

Если ранг матрицы системы меньше числа неизвестных [math](\operatorname{rg}A<n)[/math], то система имеет бесконечно много решений, задаваемых формулой (5.11), которая обладает следующими свойствами:


– при любых значениях свободных переменных [math]x_{r+1},x_{r+2},\ldots,x_n[/math] по формуле (5.11) получаются такие значения базисных переменных, что упорядоченный набор чисел [math]x_1,x_2,\ldots,x_n[/math] является решением системы (5.3);


– любое решение [math]x_1,x_2,\ldots,x_n[/math] системы (5.3) удовлетворяет равенствам (5.11).


Равенства (5.11), выражающие базисные переменные через свободные, называются общим решением системы (5.3). Решение системы, получающееся по формуле (5.11) при задании конкретных значений свободных переменных, называется частным решением системы (5.3).


Процесс решения совместной системы (5-3) заканчивается получением формулы (5.11) общего решения (в частности, определением единственного решения (5.12)).


Содержание п.5 алгоритма составляет обратный ход метода Гаусса.




Пример 5.3. Решить систему линейных уравнений


[math]\begin{cases}x_1+x_2+2x_3+x_4=1,\\2x_1+3x_2+x_4=0,\\3x_1+4x_2+2x_3+2x_4=1.\end{cases}[/math]

Решение. 1. Составим расширенную матрицу системы


[math]\begin{pmatrix}A\mid B\end{pmatrix}= \begin{pmatrix}1&1&2&1\!\!&\vline&\!\!1\\ 2&3&0&1\!\!&\vline&\!\!0\\ 3&4&2&2\!\!&\vline&\!\!1\end{pmatrix}\!.[/math]

2. Используя элементарные преобразования над строками матрицы [math]\begin{pmatrix}A\mid b\end{pmatrix}[/math], приводим ее к ступенчатому виду. Берем в качестве ведущего элемента [math]a_{11}=1\ne0[/math]. Ко второй строке прибавим первую, умноженную на (-2), а к третьей — первую, умноженную на (-3):


[math]\begin{pmatrix}A\mid B\end{pmatrix}= \begin{pmatrix}1&1&2&1\!\!&\vline&\!\!1\\ 2&3&0&1\!\!&\vline&\!\!0\\ 3&4&2&2\!\!&\vline&\!\!1\end{pmatrix}\sim \begin{pmatrix}1&1&2&1\!\!&\vline&\!\!1\\ 0&1&-4&-1\!\!&\vline&\!\!-2\\ 0&1&-4&-1\!\!&\vline&\!\!-2\end{pmatrix}\!.[/math]

Ведущий элемент [math]a_{22}=1\ne0[/math]. К третьей строке прибавим вторую, умноженную на (-1):


[math]\begin{pmatrix}A\mid B\end{pmatrix}\sim \begin{pmatrix}1&1&2&1\!\!&\vline&\!\!1\\ 0&1&-4&-1\!\!&\vline&\!\!-2\\ 0&1&-4&-1\!\!&\vline&\!\!-2\end{pmatrix}\sim \begin{pmatrix}1&1&2&1\!\!&\vline&\!\!1\\ 0&1&-4&-1\!\!&\vline&\!\!-2\\ 0&0&0&0\!\!&\vline&\!\!0\end{pmatrix}= \begin{pmatrix}\widetilde{A}\mid \widetilde{B}\end{pmatrix}\!.[/math]

Расширенная матрица системы приведена к ступенчатому виду.


3. Определяем ранги матриц: [math]\operatorname{rg}A= \operatorname{rg}(A\mid b)=2[/math]. Согласно теореме 5.2, система совместна.


4. Приводим матрицу к упрощенному виду. Выбираем в качестве базисного минора [math]M_{{}_{1\,2}}^{{}^{1\,2}}[/math]. К первой строке прибавляем вторую, умноженную на (-1):


[math]\begin{pmatrix}\widetilde{A}\mid \widetilde{B}\end{pmatrix}= \begin{pmatrix} 1&1&2&1\!\!&\vline&\!\!1\\ 0&1&-4&-1\!\!&\vline&\!\!-2\\ 0&0&0&0\!\!&\vline&\!\!0\end{pmatrix}\sim \begin{pmatrix}1&0&6&2\!\!&\vline&\!\!3\\ 0&1&-4&-1\!\!&\vline&\!\!-2\\ 0&0&0&0\!\!&\vline&\!\!0\end{pmatrix}= \begin{pmatrix}A'\mid b'\end{pmatrix}\!.[/math]

5. Переменные [math]x_1,\,x_2[/math] — базисные, а [math]x_2,\,x_4[/math] — свободные. Записываем общее решение системы, используя (5.11):


[math]\begin{cases}x_1=3-6x_3-2x_4,\\ x_2=-2+4x_3+x_4.\end{cases}[/math]

Система имеет бесконечно много решений. Найдем частное решение. Например, для [math]x_3=x_4=0[/math] получаем [math]x_1=3,~x_2=-2[/math]. Следовательно, столбец [math]x=\begin{pmatrix}3&-2&0&0\end{pmatrix}^T[/math] — частное решение системы.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved