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

Посмотреть архив целиком

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


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


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



    где числа aij называются коэффициентами системы, числа bi – свободными членами, aij и bi (i=1,…, m; b=1,…, n) представляют собой некоторые известные числа, а x1,…, xn – неизвестные. В обозначении коэффициентов aij первый индекс i обозначает номер уравнения, а второй j – номер неизвестного, при котором стоит этот коэффициент. Подлежат нахождению числа xn. Такую систему удобно записывать в компактной матричной форме: AX=B. Здесь А – матрица коэффициентов системы, называемая основной матрицей;



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


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


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

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



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


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

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



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

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

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

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

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

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



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



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


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


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

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

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

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

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

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

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


    ,


    где

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

    1-й шаг.

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

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

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




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



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

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

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

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

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

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

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

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


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


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

    Пример 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 х3 + х4 = 1

    х1 – 8х2 – 2х3 – 3х4 = -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

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

    1 0 0 0 | -2

    0 1 0 0 | -1

    0 0 1 0 | 1

    0 0 0 1 | 2

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

    х1 = -2

    х2 = -1

    х3 = 1

    х4 = 2


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


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

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

    1. менее трудоёмкий по сравнению с другими методами;

    2. позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение;

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

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

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

    1. нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: , после чего приводится к виду единичной матрицы методом Гаусса–Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица: );

    2. определения ранга матрицы (согласно следствию из теоремы Кронекера–Капелли ранг матрицы равен числу её главных переменных);

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

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




    Список источников


    1. Кремер Н.Ш., Путко Б.А. Высшая математика для экономистов. - М.: Учеб. пособие, 1998.

    2. Курош А.Г. Курс высшей алгебры. - М.: Учеб. пособие, 1968.

    3. Справочник по математике для экономистов. Под ред. В.И. Ермакова // Инфра-М, Москва – 2009.


  • Случайные файлы

    Файл
    95013.rtf
    work.doc
    164700.doc
    138055.rtf
    55496.rtf




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