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

Содержание: 

1. Система линейных алгебраических уравнений………………………………3
1. Понятие системы линейных алгебраических уравнений……………….3
2. Решение системы линейных алгебраических уравнений……………….4
2. Метод исключения Гаусса……………………………………………..………5

2.1  Сущность  метода исключения Гаусса……………………………………5

2.2  Примеры  решения СЛАУ методом Гаусса………………………………8

3. Преимущества и недостатки метода Гаусса………………………………….12
4. Список использованных источников…………………………………………14

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Система линейных алгебраических уравнений

1. Понятие системы линейных алгебраических уравнений 
   

     Система уравнений - это условие, состоящее  в одновременном выполнении нескольких уравнений относительно нескольких переменных. Системой линейных алгебраических уравнений (далее - СЛАУ), содержащей m уравнений и n неизвестных, называется система вида:

   

где числа  a_ij называются коэффициентами системы, числа b_i— свободными членами, a_ij и b_i (i=1,…,m; b=1,…,n) представляют собой некоторые известные числа, а x₁,…,x_n – неизвестные. В обозначении коэффициентов a_ij первый индекс i обозначает номер уравнения, а второй j – номер неизвестного, при котором стоит этот коэффициент. Подлежат нахождению числа x_n.                   

     Такую систему удобно записывать в компактной матричной форме: AX=B. Здесь А — матрица коэффициентов системы, называемая основной матрицей;

— вектор-столбец из неизвестных  xj.

— вектор-столбец из свободных членов bi.

     Произведение  матриц  А*Х определено, так как в матрице А столбцов столько же, сколько строк в матрице Х (n штук).

     Расширенной матрицей системы называется матрица A системы, дополненная столбцом свободных членов

 
 

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

 

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

     Решением системы называется n значений неизвестных  х1=c1, x2=c2, ..., xn=cn, при подстановке которых все уравнения системы обращаются в верные равенства. Всякое решение системы можно записать в виде матрицы-столбца

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

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

     Решить  систему — это значит выяснить, совместна она или несовместна. Если система совместна, найти ее общее решение.

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

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

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

     Однородная система всегда совместна, так как  x1=x2=x3=...=xn=0 является решением системы. Это решение называется нулевым или тривиальным. 

2. Метод исключения Гаусса

2.1 Сущность метода исключения Гаусса 

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

     Процесс решения по методу Гаусса состоит  из двух этапов: прямой и обратный ходы.

1. Прямой ход.

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

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

     На  первом этапе (прямой ход) система приводится к ступенчатому (в частности, треугольному) виду.

     Приведенная ниже система имеет ступенчатый  вид:

      ,

где

     Коэффициенты  aii называются главными (ведущими) элементами системы.

      1-й шаг.

     Будем считать, что элемент   (если a11=0 , переставим строки матрицы так, чтобы a₁₁ не был равен 0. Это всегда возможно, т.к. в противном случае матрица содержит нулевой столбец, ее определитель равен нулю и система несовместна).

      Преобразуем систему, исключив неизвестное х1 во всех уравнениях, кроме первого (используя элементарные преобразования системы). Для этого умножим обе части первого уравнения на  и сложим почленно со вторым уравнением системы (или из второго уравнения почленно вычтем первое, умноженное на ). Затем умножим обе части первого уравнения на  и сложим с третьим уравнением системы (или из третьего почленно вычтем первое, помноженное на ). Таким образом, последовательно умножаем первую строку на число и прибавляем к i-й строке, для i=2, 3, …, n.

      Продолжая этот процесс, получим эквивалентную  систему:

     

      Здесь  — новые значения коэффициентов при неизвестных и свободные члены в последних m-1 уравнениях системы, которые определяются формулами:

      Таким образом, на первом шаге уничтожаются все коэффициенты, лежащие под  первым ведущим элементом a₁₁ 0, на втором шаге уничтожаются элементы, лежащие под вторым ведущим элементом а₂₂⁽¹⁾ (если a₂₂⁽¹⁾ 0) и т.д. Продолжая этот процесс и дальше, мы, наконец, на (m-1) шаге приведем исходную систему к треугольной системе.

     Если  в процессе приведения системы к ступенчатому виду появятся нулевые уравнения, т. е. равенства вида 0=0, их отбрасывают. Если же появится уравнение вида  то это свидетельствует о несовместности системы.

      На  этом прямой ход метода Гаусса заканчивается.

2. Обратный ход.

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

     Эта процедура начинается с последнего уравнения, из которого выражают соответствующую  базисную переменную (она в нем всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх.

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

     Примечание: на практике удобнее работать не с  системой, а с расширенной ее матрицей, выполняя все элементарные преобразования над ее строками. Удобно, чтобы коэффициент a11 был равен 1 (уравнения переставить  местами, либо разделить обе части  уравнения на a11).

2. Примеры решения СЛАУ методом  Гаусса

 

      В данном разделе на трех различных  примерах покажем, как методом Гаусса можно решить СЛАУ.

      Пример 1. Решить СЛАУ 3-го порядка.

      

      Обнулим коэффициенты при во второй и третьей строчках. Для этого домножим их на 2/3 и 1 соответственно и сложим с первой строкой:

      

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

      

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

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

 из третьего;

 из второго, подставив полученное ;

 из первого, подставив полученные и .

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

     Пример 2. Решить неопределенную СЛАУ 4-го порядка:

     

     В результате элементарных преобразований над расширенной матрицей системы

     

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

     

     Поэтому общее решение системы: x2=5x4-13x3-3; x1=5x4-8x3-1. Если положить, например, что x3=0, x4=0, то найдем одно из частных решений этой системы  x1=-1, x2=-3, x3=0, x4=0.

     Пример 3. Решить СЛАУ 4-ого порядка.

       Условие:

х1 – 2х2 – х3  + х4  = 1

х1 – 8х2 – 2х3 – 3х4 = -2

2х1 + 2х2 – х3 + 7х4 = 7

х1 + х2 + 2х3 + х4 = 1 

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

1  -2  -1   1  |   1

1  -8  -2  -3 |  -2

2   2  -1   7  |   7

1   1   2   1  |   1

      Проведём  следующие действия:

1. из второй строки вычтем первую строку (cтрока 2 - строка 1);
2. из третьей строки вычтем первую строку, умноженную на 2(cтрока3-2х строка1)
3. из четвертой строки вычтем первую строку (cтрока 4 - строка 1). Получим:

1  -2  -1   1  |   1

0  -6  -1  -4 |  -3

0   6  1   5  |   5

0   3   3   0  |   0

      Проведём  следующие действия:

1. к третьей строке прибавим вторую строку (строка 3 + строка 2);
2. четвертую строку поделим на 3 (строка 4 = строка 4 / 3). Получим:

1  -2  -1   1  |   1

0  -6  -1  -4 |  -3

0   0  0   1  |   2

0   1   1   0  |   0

      Проведём  следующие действия:

1. четвертую строку поставим на место второй строки;
2. третью строку поставим на место четвертой строки;
3. вторую строку поставим на место третьей строки. Получим:

1  -2  -1   1  |   1

0 1  1    0 | 0

0  -6  -1  -4  |  -3

0   0   0   1  |   2

      К третьей строке прибавим вторую строку, умноженную на 6 (строка 3 + 6 × строка 2). Получим:

1  -2  -1   1  |   1

0 1  1    0 | 0

0  0  5 -4  |  -3

0   0   0   1  |   2

      Проведём  следующие действия:

1. к третьей строке прибавим четвертую, умноженную на 4 (строка3 + 4×строка4);
2. из первой строки вычтем четвертую строку (строка 1 - строка 4);
3. третью строку поделим на 5 (строка 3 = строка 3 / 5). Получим:

1  -2  -1   1  |   1

0 1  1    0 | 0

0  0  1   0  | 1

0   0   0   1  |   2

      Проведём  следующие действия:

1. из второй строки вычтем третью строку (строка 2 - строка 3);
2. к первой строке прибавим третью строку (строка 1 + строка 3). Получим:

1  -2 0   0  |   0

0 1  0    0 | -1

0  0  1   0  | 1

0   0   0   1  |   2

3. К первой строке прибавим вторую строку, умноженную на 2 (строка 1 + 2 × строка 2). Получим:

1  0 0   0  |   -2

0 1  0    0 | -1

0  0  1   0  | 1

0   0   0   1  |   2

      В левой части матрицы по главной  диагонали остались одни единицы. В  правом столбце получаем решение:

      х₁ = -2

      х₂ = -1

      х₃ = 1

      х₄ = 2

      
 

   

3. Преимущества  и недостатки метода Гаусса

 

      Итак, метод Гаусса применим к любой системе линейных уравнений, он идеально подходит для решения систем, содержащих больше трех линейных уравнений. Метод Гаусса решения СЛАУ с числовыми коэффициентами в силу простоты и однотипности выполняемых операций пригоден для счета на электронно-вычислительных машинах.

      Достоинства метода:

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

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

      Помимо  аналитического решения СЛАУ, метод Гаусса также применяется для:

1. нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: , после чего приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица: );
2. определения ранга матрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равен числу её главных переменных);
3. численного решения СЛАУ в вычислительной технике (ввиду погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент).

      Существуют  и другие методы решения и исследования систем линейных уравнений, которые  лишены отмеченных недостатков. Эти  методы основаны на теории матриц и  определителей. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Список использованный источников: 

1. Кремер  Н.Ш., Путко Б.А. Высшая математика для экономистов.-М.: Учеб.пособие, 1998.
2. Курош А.Г. Курс высшей алгебры.-М.: Учеб.пособие, 1968.
3. Справочник по математике для экономистов. Под ред. В.И. Ермакова//Инфра-М, Москва – 2009.
4. http://www.fizmatik.ru/index.php?option=com_content&view=article&id=146&Itemid=128.
5. http://ru.wikipedia.org/wiki/Метод_Гаусса.
6. http://www.webmath.ru/primeri_reshenii/primeri_reshenii_slay_gauss1_1.php.