Решить методом Гаусса систему уравнений:

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

Поменяем местами первую и третью строки

Мы получили единицу в верхнем углу. Теперь нужно получить нули в первом столбце 2-ой и 3-ей строки. Для этого ко второй строке прибавим первую строку, умноженную на -2:

К третьей строке прибавим первую, умноженную на 3:

Вторую строку умножим на -1/5, а третью строку на -1/2

К третьей строке прибавим вторую строку, умноженную на -2

Из последней строчки находим, что .

Из второй строки находим y:

И из первой строки найдем x:

Таким образом, мы нашли решение системы:

Решить методом Гаусса следующие системы уравнений:

1 2 3 4

5 6 7 8

9 10 11

12 13 14

15 16

17 18

19 20

Шатных Олеся Николаевна

АЛГЕБРА

(ЧАСТЬ 1)

Материалы для практических занятий

и самостоятельной работы

для студентов факультета М и ИТ

Редактор

____________________________________________________________________

Подписано к печати Формат бумаги 60 84 1/16 Бумага тип № 1

Печать цифровая Усл. печ.л. 2,25 Уч.-изд.л.

Заказ Тираж 30 Не для продажи

____________________________________________________________________

РИЦ Курганского государственного университета.

640669, г. Курган, ул. Гоголя, 25.

Курганский государственный университет.

poisk-ru.ru

Метод Гаусса. Метод последовательного исключения неизвестных

Историческая справка

Метод Гаусса был предложен известнейшим немецким математиком Карлом Фридрихом Гауссом (1777 – 1855) и является одним из наиболее универсальных методов решения СЛАУ. Сущность этого метода состоит в том, что посредством последовательных исключений неизвестных данная система превращается в ступенчатую (в частности, треугольную) систему, равносильную данной. При практическом решении задачи, расширенная матрица системы с помощью элементарных преобразований над ее строками приводится к ступенчатому виду. Далее последовательно находятся все неизвестные, начиная снизу вверх.

Принцип метода Гаусса

Метод Гаусса включает в себя прямой (приведение расширенной матрицы к ступенчатому виду, то есть получение нулей под главной диагональю) и обратный (получение нулей над главной диагональю расширенной матрицы) ходы. Прямой ход и называется методом Гаусса, обратный – методом Гаусса-Жордана, который отличается от первого только последовательностью исключения переменных.

Метод Гаусса идеально подходит для решения систем содержащих больше трех линейных уравнений, для решения систем уравнений, которые не являются квадратными (чего не скажешь про метод Крамера и матричный метод). То есть метод Гаусса – наиболее универсальный метод для нахождения решения любой системы линейных уравнений, он работает в случае, когда система имеет бесконечно много решений или несовместна.

Примеры решения систем уравнений

Пример

Задание. Решить СЛАУ методом Гаусса.

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

Далее делаем нули под главной диагональю в первом столбце. Для этого от второй строки отнимаем две первых, от третьей – три первых:

Все элементы третьей строки делим на два (или, что тоже самое, умножаем на ):

Далее делаем нули во втором столбце под главной диагональю, для удобства вычислений поменяем местами вторую и третью строки, чтобы диагональный элемент равнялся 1:

От третьей строки отнимаем вторую, умноженную на 3:

Умножив третью строку на , получаем:

Проведем теперь обратный ход метода Гаусса (метод Гассу-Жордана), то есть сделаем нули над главной диагональю. Начнем с элементов третьего столбца. Надо обнулить элемент , для этого от второй строки отнимем третью:

Далее обнуляем недиагональные элементы второго столбца, к первой строке прибавляем вторую:

Полученной матрице соответствует система

или

Ответ.

mykonspekts.ru

3.2 Метод исключения Гаусса. Схема единственного деления

Основная идея метода исключений Гаусса состоит в том, что система уравнений (3.1) приводится к эквивалентной ей системе с верхней треугольной матрицей (прямой ход исключений), а затем неизвестные вычисляются последовательной подстановкой (обратный ход исключений).

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

Прямой ход состоит из n – 1 шагов. На первом шаге исключается переменная x₁ из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n-го уравнений вычесть первое, умноженное на величину

m = , i = 2, 3, …, n. (3.4)

При этом коэффициенты при x₁ обратятся в нуль во всех уравнениях, кроме первого.

Введем обозначения:

a = a_ij – ma_1j , b= b_i – mb₁. (3.5)

Легко убедиться, что для всех уравнений, начиная со второго, a= 0, i = 2, 3, …, n. Преобразованная система запишется в виде:

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

ax₂ + ax₃ + … + ax_n = b

a x₂ + ax₃ + … + ax_n = b (3.6)

ax₂ + ax₃ + … + ax_n = b

Все уравнения (3.6), кроме первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x₂. Точно так же исключаем переменную x₃ из последних n – 3 уравнений.

На некотором k-ом шаге в предположении, что главный элемент k-ого шага a0, переменная x_k исключается с помощью формул:

m = ,

a = a – ma ,

b= b – mb, i, j = k + 1, k + 2, …, n. (3.7)

Индекс k принимает значения 1, 2, …, n – 1.

При k = n – 1 получим треугольную систему:

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

ax₂ + ax₃ + …+ ax_n = b

ax₃ + …+ ax_n = b (3.8)

ax_n = b

с треугольной матрицей A_n.

Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса.

При использовании метода Гаусса нет необходимости в предварительном обосновании существования и единственности решения (т. е. доказательства, что det A 0). Если на k-ом шаге все элементы a (i = k, k + 1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения.

Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определяем x_n... Подставляя его в предпоследнее уравнение, находим x_n-1, и т. д. Общие формулы имеют вид:

x_n = ,

x_k = (b- a x_k+1– a x_k+2 – … – a x_n), k = n – 1, n – 2, …, 1 (3.9)

Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 2/3n³ операций для прямого хода и n² операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3n³ + n².

Пример 3.1.

Применим метод исключения Гаусса по схеме единственного деления для решения системы уравнений:

2.0x₁ + 1.0x₂ – 0.1x₃ + 1.0x₄ = 2.7

0.4x₁ + 0.5x₂ + 4.0x₃ – 8.5x₄ = 21.9

0.3x₁ – 1.0x₂ + 1.0x₃ + 5.2x₄ = – 3.9 (3.10)

1.0x₁ + 0.2x₂ + 2.5x₃ – 1.0x₄ = 9.9

Будем делать округление чисел до четырех знаков после десятичной точки.

Прямой ход. 1-ый шаг. Вычислим множители:

m = = = 0.2; m = = = 0.15; m = = = 0.5.

Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m, m, m, получим новую систему:

2.0x₁ + 1.0x₂ – 0.1x₃ + 1.0x₄ = 2.7

0.3x₂ + 4.02x₃ – 8.70x₄ = 21.36

-1.15x₂ + 1.015x₃ + 5.05x₄ = – 4.305 (3. 11)

– 0.30x₂ + 2.55x₃ – 1.50x₄ = 8.55

2-ой шаг. Вычислим множители:

m = = = – 3.83333; m = = = -1.0.

Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m и m, приходим к системе:

2.0x₁ + 1.0x₂ – 0.1x₃ + 1.0x₄ = 2.7

0.3x₂ + 4.02x₃ – 8.70x₄ = 21.36

16. 425x₃ – 28.300x₄ = 77.575 (3.12)

6.570x₃ – 10.200x₄ = 29.910

3-ий шаг. Вычислим множитель:

m = = = 0.4.

Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m, приведем систему к треугольному виду:

2.0x₁ + 1.0x₂ – 0.1x₃ + 1.0x₄ = 2.7

0.3x₂ + 4.02x₃ – 8.70x₄ = 21.36

16. 425x₃ – 28.300x₄ = 77.575 (3.13)

1.12x₄ = -1.12

Обратный ход. Из последнего уравнения системы (3.13) находим x₄ = 1.000. Подставляя значение x₄ в третье уравнение, получим x₃ = 2.000. Подставляя найденные значения x₄ и x₃ во второе уравнение, найдем x₂ = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x₄, x₃ и x₂, вычислим x₁ = -1.000.

Итак система (3.10) имеет следующее решение:

x₁ = 1.000, x₂ = 2.000, x₃ = 3.000, x₄ = – 1.000.

studfiles.net

Метод Гаусса — WiKi

Пусть исходная система выглядит следующим образом:

{a11x1+…+a1nxn=b1…am1x1+…+amnxn=bm{\displaystyle \left\{{\begin{array}{lcr}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_{m1}x_{1}+\ldots +a_{mn}x_{n}&=&b_{m}\\\end{array}}\right.} 

Её можно записать в матричном виде:

Ax=b,{\displaystyle Ax=b,} 

где

A=(a11…a1n…am1…amn),x=(x1⋮xn),b=(b1⋮bm).(1){\displaystyle A=\left({\begin{array}{ccc}a_{11}&\ldots &a_{1n}\\\ldots &&\\a_{m1}&\ldots &a_{mn}\end{array}}\right),\quad x=\left({\begin{array}{c}x_{1}\\\vdots \\x_{n}\end{array}}\right),\quad b=\left({\begin{array}{c}b_{1}\\\vdots \\b_{m}\end{array}}\right).\quad (1)} 

Матрица A{\displaystyle A}  называется основной матрицей системы, b{\displaystyle b}  — столбцом свободных членов.

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

{α1j1xj1+α1j2xj2+…+α1jrxjr+…+α1jnxjn=β1α2j2xj2+…+α2jrxjr+…+α2jnxjn=β2…αrjrxjr+…+αrjnxjn=βr0=βr+1…0=βm,{\displaystyle \left\{{\begin{array}{rcl}\alpha _{1j_{1}}x_{j_{1}}+\alpha _{1j_{2}}x_{j_{2}}+\ldots +\alpha _{1j_{r}}x_{j_{r}}+\ldots +\alpha _{1j_{n}}x_{j_{n}}&=&\beta _{1}\\\alpha _{2j_{2}}x_{j_{2}}+\ldots +\alpha _{2j_{r}}x_{j_{r}}+\ldots +\alpha _{2j_{n}}x_{j_{n}}&=&\beta _{2}\\&\ldots &\\\alpha _{rj_{r}}x_{j_{r}}+\ldots +\alpha _{rj_{n}}x_{j_{n}}&=&\beta _{r}\\0&=&\beta _{r+1}\\&\ldots &\\0&=&\beta _{m}\end{array}}\right.,} 

где α1j1,…,αrjr≠0.{\displaystyle \alpha _{1j_{1}},\ldots ,\alpha _{rj_{r}}\neq 0.} 

При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных xj1,…,xjr{\displaystyle x_{j_{1}},\ldots ,x_{j_{r}}} ^[3].

Тогда переменные xj1,…,xjr{\displaystyle x_{j_{1}},\ldots ,x_{j_{r}}}  называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число βi≠0{\displaystyle \beta _{i}\neq 0} , где i>r{\displaystyle i>r} , то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.

Пусть βi=0{\displaystyle \beta _{i}=0}  для любых i>r{\displaystyle i>r} .

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом x{\displaystyle x}  (αiji,i=1,…,r{\displaystyle \alpha _{ij_{i}},\,i=1,\ldots ,r} , где i{\displaystyle i}  — номер строки):

{xj1+α^1j2xj2+…+α^1jrxjr=β^1−α^1jr+1xjr+1−…−α^1jnxjnxj2+…+α^2jrxjr=β^2−α^2jr+1xjr+1−…−α^2jnxjn…xjr=β^r−α^rjr+1xjr+1−…−α^rjnxjn,β^i=βiαiji,α^ijk=αijkαiji(2){\displaystyle \left\{{\begin{array}{rcc}x_{j_{1}}+{\widehat {\alpha }}_{1j_{2}}x_{j_{2}}+\ldots +{\widehat {\alpha }}_{1j_{r}}x_{j_{r}}&=&{\widehat {\beta }}_{1}-{\widehat {\alpha }}_{1j_{r+1}}x_{j_{r+1}}-\ldots -{\widehat {\alpha }}_{1j_{n}}x_{j_{n}}\\x_{j_{2}}+\ldots +{\widehat {\alpha }}_{2j_{r}}x_{j_{r}}&=&{\widehat {\beta }}_{2}-{\widehat {\alpha }}_{2j_{r+1}}x_{j_{r+1}}-\ldots -{\widehat {\alpha }}_{2j_{n}}x_{j_{n}}\\&\ldots &\\x_{j_{r}}&=&{\widehat {\beta }}_{r}-{\widehat {\alpha }}_{rj_{r+1}}x_{j_{r+1}}-\ldots -{\widehat {\alpha }}_{rj_{n}}x_{j_{n}}\\\end{array}}\right.,\qquad {\widehat {\beta }}_{i}={\frac {\beta _{i}}{\alpha _{ij_{i}}}},\quad {\widehat {\alpha }}_{ij_{k}}={\frac {\alpha _{ij_{k}}}{\alpha _{ij_{i}}}}\quad (2)} ,

где i=1,…,r,k=i+1,…,n.{\displaystyle i=1,\ldots ,r,\quad k=i+1,\ldots ,n.} 

Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.

Критерий совместности

Упомянутое выше условие βi=0{\displaystyle \beta _{i}=0}  для всех i>r{\displaystyle i>r}  может быть сформулировано в качестве необходимого и достаточного условия совместности:

Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Алгоритм

Блок схема представлена на рисунке. Данный рисунок адаптированный для написания программы на языке С/С++, где a[0] столбец свободных членов.

Описание

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

• На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.
• На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

Метод Гаусса требует O(n3){\displaystyle O(n^{3})}  арифметических операций.

Этот метод опирается на:

Простейший случай

В простейшем случае алгоритм выглядит так:

{a11⋅x1+a12⋅x2+…+a1n⋅xn=b1(1)a21⋅x1+a22⋅x2+…+a2n⋅xn=b2(2)…am1⋅x1+am2⋅x2+…+amn⋅xn=bm(m){\displaystyle \left\{{\begin{array}{lcc}a_{11}\cdot x_{1}+a_{12}\cdot x_{2}+\ldots +a_{1n}\cdot x_{n}&=b_{1}&(1)\\a_{21}\cdot x_{1}+a_{22}\cdot x_{2}+\ldots +a_{2n}\cdot x_{n}&=b_{2}&(2)\\\ldots &&\\a_{m1}\cdot x_{1}+a_{m2}\cdot x_{2}+\ldots +a_{mn}\cdot x_{n}&=b_{m}&(m)\end{array}}\right.} 

(2)→(2)−(1)⋅(a21a11):a22′⋅x2+a23′⋅x3+…+a2n′⋅xn=b2′(3)→(3)−(1)⋅(a31a11):a32′⋅x2+a33′⋅x3+…+a3n′⋅xn=b3′…(m)→(m)−(1)⋅(am1a11):am2′⋅x2+am3′⋅x3+…+amn′⋅xn=bn′(3)→(3)−(2)⋅(a32′a22′):a33′′⋅x3+…+a3n′′⋅xn=b3′′…(m)→(m)−(m−1)⋅(am,n−1(m−2)am−1,n−1(m−2)):amm(m−1)⋅xm+…+amn(m−1)⋅xn=bm(m−1){\displaystyle {\begin{array}{ccc}(2)\to (2)-(1)\cdot ({\frac {a_{21}}{a_{11}}})&:&a_{22}^{\prime }\cdot x_{2}+a_{23}^{\prime }\cdot x_{3}+\ldots +a_{2n}^{\prime }\cdot x_{n}=b_{2}^{\prime }\\(3)\to (3)-(1)\cdot ({\frac {a_{31}}{a_{11}}})&:&a_{32}^{\prime }\cdot x_{2}+a_{33}^{\prime }\cdot x_{3}+\ldots +a_{3n}^{\prime }\cdot x_{n}=b_{3}^{\prime }\\\ldots &&\\(m)\to (m)-(1)\cdot ({\frac {a_{m1}}{a_{11}}})&:&a_{m2}^{\prime }\cdot x_{2}+a_{m3}^{\prime }\cdot x_{3}+\ldots +a_{mn}^{\prime }\cdot x_{n}=b_{n}^{\prime }\\(3)\to (3)-(2)\cdot ({\frac {a_{32}^{\prime }}{a_{22}^{\prime }}})&:&a_{33}^{\prime \prime }\cdot x_{3}+\ldots +a_{3n}^{\prime \prime }\cdot x_{n}=b_{3}^{\prime \prime }\\\ldots &&\\(m)\to (m)-(m-1)\cdot ({\frac {a_{m,n-1}^{(m-2)}}{a_{m-1,n-1}^{(m-2)}}})&:&a_{mm}^{(m-1)}\cdot x_{m}+\ldots +a_{mn}^{(m-1)}\cdot x_{n}=b_{m}^{(m-1)}\end{array}}} 

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

Пример

Покажем, как методом Гаусса можно решить следующую систему:

{2x+y−z=8−3x−y+2z=−11−2x+y+2z=−3{\displaystyle \left\{{\begin{array}{ccc}2x+y-z&=&8\\-3x-y+2z&=&-11\\-2x+y+2z&=&-3\end{array}}\right.} 

Обнулим коэффициенты при x{\displaystyle x}  во второй и третьей строчках. Для этого прибавим к ним первую строчку, умноженную на 32{\displaystyle \textstyle {\frac {3}{2}}}  и 1{\displaystyle 1} , соответственно:

{2x+y−z=812y+12z=12y+z=5{\displaystyle \left\{{\begin{array}{rcc}2x+y-z&=&8\\{\frac {1}{2}}y+{\frac {1}{2}}z&=&1\\2y+z&=&5\end{array}}\right.} 

Теперь обнулим коэффициент при y{\displaystyle y}  в третьей строке, вычтя из неё вторую строку, умноженную на 4{\displaystyle 4} :

{2x+y−z=812y+12z=1−z=1{\displaystyle \left\{{\begin{array}{rcc}2x+y-z&=&8\\{\frac {1}{2}}y+{\frac {1}{2}}z&=&1\\-z&=&1\\\end{array}}\right.} 

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

На втором этапе разрешим полученные уравнения в обратном порядке. Имеем:

z=−1{\displaystyle z=-1}  из третьего;

y=3{\displaystyle y=3}  из второго, подставив полученное z{\displaystyle z} 

x=2{\displaystyle x=2}  из первого, подставив полученные z{\displaystyle z}  и y{\displaystyle y} .

Таким образом исходная система решена.

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

ru-wiki.org