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

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 

Институт  ИПР

Направление подготовки (специальность) Нефтегазовое дело

 

 

 

 

 

 

 

 

РЕФЕРАТ

 

по дисциплине: «Математика»

 

на тему: «Прямые методы решения систем линейных алгебраических уравнений»

 

 

 

 

 

 

 

 

Выполнили студенты гр. 2Б44

Абдурагимов Ф.Р.

Важенин Р.А.

Гасанов Ф.А

Гвоздев Н.С.

Проверил: доцент, кандидат наук Сухотин А.М.

              

 

 

 

 

 

 

Томск-2014

Содержание

1. Введение…………………………………………………………………3
2. Определение, понятие, обозначение………………………………….4-5
3. Прямые методы решения СЛАУ……………………………………….6

3.1 Метод Крамера………………………………………………………..7,8

     3.2. Матричный метод………………………………………………….9,10,11

     3.3. Метод Гаусса……………………………………………………….12-19

4. Заключение……………………………………………………………..20
5. Список  используемой литературы……………………………………21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение

    Данный реферат включает в себя три прямых метода решения систем линейных алгебраических уравнений (СЛАУ): метод Крамера, матричный метод (метод обратной матрицы),  метод Гаусса.

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

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

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

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Определения, понятия, обозначения.

 

      Будем рассматривать системы из p линейных алгебраических уравнений с n неизвестными переменными (p может быть равно n) вида 

- неизвестные переменные, - коэффициенты (некоторые действительные или комплексные числа), - свободные члены (также действительные или комплексные числа).

      Такую форму записи СЛАУ называют координатной.

В матричной форме записи эта система уравнений имеет вид , 
где - основная матрица системы,

- матрица-столбец неизвестных переменных, - матрица-столбец свободных членов.

 

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

   

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

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

      Если система уравнений решений не имеет, то она называется несовместной.

      Если СЛАУ имеет единственное решение, то ее называют определенной; если решений больше одного, то – неопределенной.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.Прямые методы

Прямые методы дают алгоритм, по которому можно найти точное решение СЛАУ. И если бы точность была абсолютной, они бы нашли его. Реальная ЭВМ, естественно, работает с погрешностью, поэтому решение будет приближённым.  Основными прямыми методами решения элементарных систем линейных уравнений являются:

1. метод Крамера
2. матричный метод
3. метод Гаусса

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.1. Метод Крамера

        Ме́тод Кра́мера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно). Назван по имени Габриэля Крамера (1704—1752), предложившего этот метод в 1750 г.

 Описание метода.

     Для системы линейных уравнений с неизвестными (над произвольным полем)

с определителем матрицы системы , отличным от нуля, решение записывается в виде

(i-ый столбец матрицы системы заменяется столбцом свободных членов). 
В другой форме правило Крамера формулируется так: для любых коэффициентов c1, c2, …, cn справедливо равенство:

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

 

 

 

 

 Пример.

   Система линейных уравнений с вещественными коэффициентами:

   Определители:

 

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

    Решение:

    Пример:

  Определители:

 

 

  Вывод:

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

 

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

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

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

      Так как , то матрица А – обратима, то есть, существует обратная матрица . Если умножить обе части равенства на слева, то получим формулу для нахождения матрицы-столбца неизвестных переменных .

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

 

  Пример.

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

 

  Решение.

Перепишем систему уравнений в матричной форме: 

Так как 
 
то СЛАУ можно решать матричным методом. С помощью обратной матрицы решение этой системы может быть найдено как .

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

Осталось вычислить - матрицу неизвестных переменных, умножив обратную матрицу на матрицу-столбец свободных членов (при необходимости смотрите статью операции над матрицами): 

 

Ответ:

или в другой записи x1 = 4, x2 = 0, x3 = -1.

 

 

   Вывод:

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

 

 

 

 

 

 

 

 

 

3.3. Метод Гаусса

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

    В настоящее время данный метод повсеместно называется методом Гаусса, хотя он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I веком до н. э. и II веком н. э.

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

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

1. Иметь единственное решение.
2. Иметь бесконечно много решений.
3. Не иметь решений (быть несовместной).

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

 Пример:

  и решим ее методом Гаусса.

На первом этапе нужно записать расширенную матрицу системы: 
.

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

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

. 

 

 

     Расширенная матрица системы – это та же матрица системы плюс столбец свободных членов, в данном случае: 

.

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

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

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

1. Строки матрицы можно переставлять местами. Например, в рассматриваемой матрице можно безболезненно переставить первую и вторую строки:

 

 

2. Если в матрице есть (или появились) пропорциональные (как частный случай – одинаковые) строки, то следует удалить из матрицы все эти строки кроме одной. Рассмотрим, например матрицу

 

  .

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

.

3) Если в матрице в ходе  преобразований появилась нулевая  строка, то ее также следует удалить.

4) Строку матрицы можно умножить (разделить) на любое число, отличное от нуля. Рассмотрим, например, матрицу 

.

Здесь целесообразно первую строку разделить на –3, а вторую строку – умножить на 2: 

.

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

5) К строке матрицы можно прибавить другую строку, умноженную на число, отличное от нуля. Рассмотрим нашу матрицу из практического примера:

.

Сначала распишем преобразование очень подробно. Умножаем первую строку на –2: 

,

и ко второй строке прибавляем первую строку, умноженную на –2: 

.

Теперь первую строку можно разделить «обратно» на –2: 

.

 Как видите, строка, которую  прибавляли – не изменилась. Всегда меняется строка, к которой прибавляют.

На практике так подробно, конечно, не расписывают, а пишут короче: 

 
Еще раз: ко второй строке прибавили первую строку, умноженную на –2. «Переписываю матрицу и переписываю первую строку: 

»

«Сначала первый столбец. Внизу нужно получить ноль. Поэтому единицу вверху умножаю на –2: 

, и ко второй строке прибавляю  первую: 2 + (–2) = 0. Записываю результат  во вторую строку:  

»

«Теперь второй столбец. Вверху –1 умножаю на –2: 

. Ко второй строке прибавляю  первую: 1 + 2 = 3. Записываю результат  во вторую строку:  

»

«И третий столбец. Вверху –5 умножаю на –2: 

. Ко второй строке прибавляю  первую: –7 + 10 = 3. Записываю результат  во вторую строку:  

»

! ВНИМАНИЕ: рассмотренные манипуляции нельзя использовать, если Вам предложено задание, где матрицы даны «сами по себе». Например, при «классических» действиях с матрицами  что-то переставлять внутри матриц ни в коем случае нельзя! 
 
Вернемся к нашей системе 

.

Она практически разобрана по косточкам.

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

(1) Ко второй строке прибавили  первую строку, умноженную на  –2. И снова: почему первую строку  умножаем именно на –2? Для  того чтобы внизу получить  ноль, а значит, избавиться от  одной переменной во второй  строке.

(2) Делим вторую строку на 3.

 

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

.

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

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

Теперь систему нужно «раскрутить» в обратном направлении – снизу вверх, этот процесс называется обратным ходом метода Гаусса.

В нижнем уравнении у нас уже готовый результат: 

.

Рассмотрим первое уравнение системы 

и подставим в него уже известное значение «игрек»: 
 

Ответ: 

 

Пример:

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

Пример 1

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

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

Наша цель – с помощью элементарных преобразований привести матрицу к треугольной матрице.

Сначала смотрим на левое верхнее число:  
 
Почти всегда здесь должна находиться единица. Вообще говоря, устроит и –1 (а иногда и другие числа), но как-то так традиционно сложилось, что туда обычно помещают единицу. Как организовать единицу? Смотрим на первый столбец – готовая единица у нас есть! Преобразование первое: меняем местами первую и третью строки: 

Теперь первая строка у нас останется неизменной до конца решения. Уже легче.

Единица в левом верхнем углу организована. Теперь нужно получить нули вот на этих местах: 

Нули получаем как раз с помощью «трудного» преобразования. Сначала разбираемся со второй строкой (2, –1, 3, 13). Что нужно сделать, чтобы на первой позиции получить ноль? Нужно ко второй строке прибавить первую строку, умноженную на –2. Мысленно или на черновике умножаем первую строку на –2: (–2, –4, 2, –18). И последовательно проводим (опять же мысленно или на черновике) сложение, ко второй строке прибавляем первую строку, уже умноженную на –2: 

Результат записываем во вторую строку: 

Аналогично разбираемся с третьей строкой (3, 2, –5, –1). Чтобы получить на первой позиции ноль, нужно к третьей строке прибавить первую строку, умноженную на –3. Мысленно или на черновике умножаем первую строку на –3: (–3, –6, 3, –27). И к третьей строке прибавляем первую строку, умноженную на –3: 

Результат записываем в третью строку: 

На практике эти действия обычно выполняются устно и записываются в один шаг: 

Не нужно считать всё сразу и одновременно. Порядок вычислений и «вписывания» результатов последователен и обычно такой: сначала переписываем первую строку, и пыхтим себе потихонечку – ПОСЛЕДОВАТЕЛЬНО и ВНИМАТЕЛЬНО: 
 
А мысленный ход самих расчётов я уже рассмотрел выше.

Далее нужно получить единицу на следующей «ступеньке»: 

В данном примере это сделать легко, вторую строку делим на –5 (поскольку там все числа делятся на 5 без остатка). Заодно делим третью строку на –2, ведь чем меньше числа, тем проще решение: 

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

 

 

 

 

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

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

    Теперь в действие вступает обратный ход метода Гаусса. Уравнения «раскручиваются» снизу вверх.

    В третьем уравнении у нас уже готовый результат: 

   Смотрим на второе уравнение: 

 
 

   И, наконец, первое уравнение: 

 
 
 

Ответ: 

 

 

 

 

 

 

 

4.Заключение

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

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

   К достоинствам  метода Гаусса относятся:

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Список используемой литературы
1. http://bibliofond.ru/view.aspx?id=457343
2. http://pers.narod.ru/study/methods/02.html
3. https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BB%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D1%85_%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9
4. http://www.cleverstudents.ru/system_of_equations/solving_systems_of_linear_equations.html
5. http://ru.m.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9A%D1%80%D0%B0%D0%BC%D0%B5%D1%80%D0%B0
6. https://ru.wikipedia.org/wiki/
7. http://mathprofi.ru/metod_gaussa_dlya_chainikov.html
8. Мальцев А. И. Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c