Применение метода Гаусса в матричном исчислении. Матрицы теорема гаусса


Решение матриц методом Гаусса, с примерами

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

Алгоритм нахождения обратной матрицы методом Гаусса

1. Пусть задана квадратная матрица

   

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

   

2. С помощью элементарных преобразований строк приведем матрицу к матрице, в левой части которой будет стоять единичная матрица:

   

3. Полученная таким образом матрица, стоящая в правой части матрицы , и будет обратной матрицей к матрице

   

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

Пусть задана система линейных уравнений

   

Записывается матрица – расширенная матрица этой системы:

   

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

   

Эта матрица эквивалентна системе линейных уравнений

   

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

Понравился сайт? Расскажи друзьям!

ru.solverbook.com

6.А. Метод Гаусса

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

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

Решение. Выпишем расширенную матрицу данной системы

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

а) из ее второй и третьей строк вычтем первую, умноженную соответственно на 3 и 2:

;

б) третью строку умножим на (- 5) и прибавим к ней вторую:

.

В результате всех этих преобразований данная система приводится к треугольному виду:

Из последнего уравнения находим . Подставляя это значение во второе уравнение, имеем. Далее из первого уравнения получим.

6.Б. Формулы Крамера

Назовем столбцы матрицы следующим образом: первый столбец -, второй столбец - , и т.д., последний столбец -. Тогда матрицуможно записать в виде.

Составим дополнительных матриц:

, , …,,

и вычислим их определители и определитель исходной матрицы:

, ,, …,.

Тогда значения неизвестных вычисляются по формулам Крамера:

, , …,.

Правило Крамера дает исчерпывающий ответ на вопрос о совместности системы: если главный определитель системы отличен от нуля, то система имеет единственное решение, определяемое по вышеприведенным формулам.

Если главный определитель системы и все вспомогательные определителиравны нулю, то система имеет бесчисленное множество решений.

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

Пример 19. Решить систему уравнений методом Крамера.

,.

Тогда

,,.

Вычисляя определители этих матриц, получаем ,, ,.

И по формулам Крамера находим: ,,.

6.В. Матричный метод

Теперь, рассмотрим матричное уравнение . Если у матрицысуществует обратная матрица, то, умножая матричное уравнение наслева, получим:

.

По определению обратимости матрицы и по свойству единичной, получаем:

.

Пример 20. Решить систему уравнений с помощью обратной матрицы.

Имеем:

, .

Вычислим определитель матрицы , разлагая по первой строке:

Значит, обратная матрица существует. Вычислим алгебраические дополнения элементов матрицы:

,,

,,

,,

,,

.

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

7. Системы линейных уравнений общего вида

Если система уравнений оказалась совместной, т. е. матрицы иимеют один и тот же ранг, то могут представиться две возможности ‑ a), б).

а) Если , то имеемнезависимых уравнений снеизвестными, причем определительэтой системы отличен от нуля. Такая система имеет единственное решение, получаемое, например, по формулам Крамера.

б) Если , то число независимых уравнений меньше числа неизвестных.

Перенесем лишние неизвестные , которые принято называть свободными, в правые части; наша система линейных уравнений примет вид:

Ее можно решить относительно , так как определитель этой системы (порядка) отличен от нуля. Придавая свободным неизвестным произвольные числовые значения, получим по формулам Крамера соответствующие числовые значения для. Таким образом, приимеем бесчисленное множество решений.

Система уравнений называется однородной, если все , т. е. она имеет вид:

Из теоремы Кронекера-Капелли следует, что она всегда совместна, так как добавление столбца из нулей не может повысить ранга матрицы. Это, впрочем, видно и непосредственно - система заведомо обладает нулевым, или тривиальным, решением . Пусть матрицасистемы имеет ранг.

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

Всякий ненулевой вектор ‑ столбец называетсясобственным вектором линейного преобразования (квадратной матрицы ), если найдется такое число , что будет выполняться равенство.

Число называетсясобственным значением линейного преобразования (матрицы ), соответствующим вектору . Матрицаимеет порядок.

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

Для нахождения собственных значений матрицы перепишем равенствов виде, где - единичная матрица порядка или в координатной форме:

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

.

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

Для нахождения собственных векторов матрицы в векторное уравнениеили в соответствующую систему однородных уравнений нужно подставить найденные значенияи решать обычным образом.

Пример 18. Исследовать систему уравнений и решить ее, если она совместна.

Решение. Будем находить ранги матриц иметодом элементарных преобразований, приводя одновременно систему к ступенчатому виду:

.

Очевидно, что . Исходная система равносильна следующей системе, приведенной к ступенчатому виду:

Поскольку определитель при неизвестных x1 и x2отличен от нуля, то их можно принять в качестве главных и переписать систему в виде:

откуда ,‑ общее решение системы, имеющей бесчисленное множество решений. Придавая свободным неизвестнымx3, x4, x5конкретные числовые значения, будем получать частные решения. Например, при ,,. Вектор является частным решением данной системы.

Пример 19. Исследовать систему уравнений и найти общее решение в зависимости от значения параметра .

Решение. Данной системе соответствует матрица

.

Имеем

следовательно, исходная система равносильна такой:

Отсюда видно, что система совместна только при . Общее решение в этом случае имеет вид:

, .

Пример 20. Выяснить, будет ли линейно зависимой система векторов:

Решение. Система векторов является линейно зависимой, если найдутся такие числа x1, x2, x3, x4, x5, из которых хотя бы одно отлично от нуля, что выполняется векторное равенство:

.

В координатной записи оно равносильно системе уравнений:

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

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

Имеем:

, ,.

Система имеет бесчисленное множество решений; если свободные неизвестные x3и x5не равны нулю одновременно, то и главные неизвестные отличны от нуля. Следовательно, векторное уравнение

имеет коэффициенты, не равные нулю одновременно; пусть например, ,. Тогда,,и мы получим соотношение

,

т.е. данная система векторов линейно независима.

Пример 21. Найти собственные значения и собственные векторы матрицы

.

Решение. Вычислим определитель матрицы :

Итак, . Корни характеристического уравнения‑ это числаи. Другими словами, мы нашли собственные значения матрицы. Для нахождения собственных векторов матрицыподставим найденные значенияв систему: приимеем систему линейных однородных уравнений

Следовательно, собственному значению отвечают собственные векторы вида(8, 8, -3, 15), где- любое отличное от нуля действительное число. Приимеем:

,

и поэтому координаты собственных векторов должны удовлетворять системе уравнений

Поэтому собственному значению отвечают собственные векторы вида(0, 0,-1, 1), где- любое отличное от нуля действительное число.

FVB

studfiles.net

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

Рассмотрим систему линейных уравнений:

   

С этой системой связываются две матрицы: матрица коэффициентов

   

и расширенная матрица — с присоединенными свободными членами:

   

Элементарными преобразованиями системы линейных уравнений называются:

1. умножение уравнения на отличное от нуля число;

2. прибавление к одному уравнению любого другого, умноженного на любое число;

3. перестановка уравнений местами.

Теорема. Любая система линейных уравнений с помощью элементарных преобразований и, может быть, изменением нумерации неизвестных, может быть приведена к системе с трапециевидной матрицей.

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

   

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

   

Эту систему удобно решать, определив из -го уравнения , затем из -го и т.д. Таким образом, можно выразить переменные через и получить общее решение системы. Если , то система (в случае совместности) имеет единственное решение.

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

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

   

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

   

Первую строку умножим на 3 и вычтем из второй. Затем первую строку умножим на 2 и вычтем из третьей. Получим

   

Далее вторую строку прибавим к третьей и отбросим нулевую строку, получим

   

Запишем полученные уравнения:

   

Из второго уравнения выразим :

   

Полученное выражение подставляем в первое уравнение и выражаем из него :

   

Ответ. Общее решение данной системы:

   

Задачи.

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

   

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

   

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

   

hijos.ru

5 Метод Гаусса и теорема Крамера

Лекция 5

ТЕМА: Построение решений систем линейных уравнений

Пусть задана система линейных уравнений

(4.1)

Если в заданной системе , то берут любой отличный от нуля минор основной матрицы порядкаи рассматриваютуравнений, коэффициенты которых входят в этот базисный минор, а остальные уравнения отбрасывают. Неизвестные, которые входят в выбранный минор объявляютглавными, а остальные неизвестные – свободными. Новую систему переписывают так, что в левых частях уравнений остаются только члены, содержащие главных неизвестных, а остальные члены уравнений, содержащиенеизвестных, переносятся в правые части уравнений (выражаются через главные), затем находят главные неизвестные (например, по правилу Крамера). При этом главные неизвестные выражаются через свободные, каждое из которых может принимать любое числовое значение.

Полученные решения новой системы с главными неизвестными называетсяобщим решением системы (4.1).

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

Пример 4.1

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

, найдем ранг матрицы методом «окаймляющих миноров»:

Рассмотрим миноры третьего порядка: ;

система совместна,

- базисный минор;

x, y – главные переменные,

z – свободная переменная.

решим систему по правилу Крамера.

,

.

Общим решением исходной системы является бесконечное множество наборов вида

Частным решением будет, например, числовой набор , получающийся приt=o.

Метод Гаусса

(метод последовательного исключения переменных)

На практике чаще всего применяется метод Гаусса – построения решения систем линейных уравнений.

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

, (5.1).

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

Этот минор является верхнетреугольным и равен произведению .

Нулевые строки матрицы отбросим

(им соответствуют уравнения ).

(5.2)

(отбросили нулевые столбцы и перенумеровали переменные).

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

(5.3),

или к системе (5.4)

из которой видно, что если , то система (5.4) имеет единственное решение:

, …, .

Если , то переменные– базисные,– свободные и придавая им произвольные значения, …,, можно записать общее решение системы в виде:

(5.5).

Итак, метод Гаусса состоит в следующем:

  1. расширенную матрицу системы элементарными преобразованиями приводят к ступенчатому виду;

  2. сравнивают ранги основной и расширенной матриц и делают вывод о совместности или несовместности системы;

  3. в случае совместности системы в основной матрице выбирают базисный минор и дальнейшими элементарными преобразованиями строк добиваются того, чтобы в этом миноре все элементы вне главной диагонали стали равными нулю, а элементы главной диагонали стали равными единице;

  4. выписывают систему, соответствующую полученной расширенной матрице, после чего переписывают систему, оставляя базисные неизвестные слева и переведя остальные слагаемые в правую часть;

  5. если ,то в правой части стоят только свободные члены и получено единственное решение;

  6. если , то в правой части есть свободные неизвестные. Придавая им произвольные значения, получаем общее решение по формуле (5.5).

Пример 5.2

.

Теорема Крамера 5.1

Линейная система (4.2) с квадратной матрицей имеетрешение, притом единственное, тогда и только тогда, когда .

Доказательство

Пусть система (4.2) имеет и притом единственное решение. Допустим, что . Это значит, что единственный минор-го порядка в основной матрице (который является ее определителем), равен нулю, и потому(т.е. ранг матрицы меньше числа неизвестных). Но согласно следствию (2) теоремы (4.1) в этом случае система имеет бесконечное множество решений, что противоречит условию. Значит допущенноеневерно, и потому.

Пусть . Тогда, а так как, то и. Но по теореме (4.1) это означает, что СЛУ (4.2) имеет решение, а так как ранг основной матрицы системы равен числу неизвестных, то в силу следствия (1) теоремы (4.1) это решение единственное.

Нахождение обратной матрицы методом Гаусса

Напомним, что матрица называется обратной к, если. Обратные матрицы существуют лишь для невырожденных матриц, т.е.. Было показано, что, где– присоединенная матрица, полученная из алгебраических дополнений, т. е. вычислением определителей-ого порядка. Вместе с тем, операция вычисления определителя, запрограммированная в ЭВМ, требует больших машинных ресурсов. Поэтому более предпочтительным выглядит вычисление обратной матрицы с помощью метода Гаусса.

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

.

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

; ; …;

Все эти системы объединим в одной расширенной матрице:

.

Приведение этой матрицы к ступенчатому виду должно обозначать приведение к ступенчатому виду всех расширенных матриц подсистем. Так как она может быть приведена к следующему виду:

.

Решение каждой из подсистем имеет вид:

, , …,

матрица , стоящая за вертикальной чертой, является обратной матрицей.

Пример 5.3

.

7

studfiles.net

Метод Гаусса — Википедия РУ

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

{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) эквивалентны, то есть множества их решений совпадают.

  Следствия: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} .

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

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

http-wikipediya.ru

Метод Гаусса Википедия

Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы[1].

История[ | код]

Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах».[2]

Описание метода[ | код]

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

{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} — столбцом свободных членов.

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

ru-wiki.ru

Теорема Гаусса | Математика, которая мне нравится

Теорема Гаусса. Пусть дан треугольник . Пусть прямая пересекает его стороны и в точках и соответственно, а продолжение стороны — в точке . Тогда середины отрезков и лежат на одной прямой.

Доказательство. Середины отрезков и обозначим через и соответственно. Эти точки лежат на прямых и , где и — середины сторон и треугольника .

Из подобия треугольников и получаем

   

а из подобия треугольников и :

   

Отсюда

   

Аналогично получаем соотношения

и

Перемножим полученные три равенства:

   

Так как точки и лежат на одной прямой, то по теореме Менелая левая часть этого равенства равна . Следовательно, учитывая правую часть равенства, по обратной теореме Менелая точки и лежат на одной прямой.

Источник: Понарин Я.П. Элементарная геометрия. Т.1. Планиметрия, преобразования плоскости. М.: Изд-во МЦНМО, 2004.

hijos.ru



О сайте

Онлайн-журнал "Автобайки" - первое на постсоветском пространстве издание, призванное осветить проблемы радовых автолюбителей с привлечение экспертов в области автомобилестроения, автоюристов, автомехаников. Вопросы и пожелания о работе сайта принимаются по адресу: Онлайн-журнал "Автобайки"