Алгоритм Гаусса. Приведение системы линейных уравнений к ступенчатому виду и исследование таких систем

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ПЕРМСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

КАФЕДРА МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ СИСТЕМ И ПРОЦЕССОВ

Курсовая работа по линейной алгебре

«Алгоритм Гаусса. Приведение системы линейных уравнений к ступенчатому виду и исследование таких систем»

Пермь, 2011 г.



Введение

Данный метод решения систем линейных алгебраических уравнений был описан еще в китайском трактате «Математика в девяти книгах» (I в. до н.ээ - II в. н.э.), но доработан он был именно Гауссом.

Иоганн Карл Фридрих Гаусс (1777-1855) - немецкий математик, астроном и физик, считается одним из величайших математиков всех времен, «королем математиков».

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

гаусс математика алгебраический



1. Теоретическая часть

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

Итак, пусть дана система линейных уравнений

Размещено на http://www.allbest.ru/

Коэффициенты при неизвестных составляют прямоугольную таблицу называемую матрицей системы.

А = Размещено на http://www.allbest.ru/

Первый индекс у коэффициента aij означает номер уравнения, второй - номер неизвестного ,при котором стоит этот коэффициент. Коэффициенты b1,b2, …, bmназывают свободными членами уравнений системы. Если свободные члены равны нулю, система является однородной, в противном случае - неоднородной.

Матрицу

B = Размещено на http://www.allbest.ru/

называют расширенной матрицей системы (I). Решением системы (I) называют упорядоченный набор (x1,x2, …, xn) из n чисел, при подстановке которых в уравнения системы вместо соответствующих неизвестных каждое уравнение системы превращается в тождество. Система, не имеющая ни одного решения, называется несовместной или противоречивой. Система, имеющая хотя бы одно решение, называется совместной. Совместные системы делятся наопределенные, обладающие единственным решением, и неопределённые, обладающие множеством решений. Однородная система всегда совместна, так как имеет, по крайней мере, нулевое решение x1=x2= …=xn=0. Выражение для неизвестных x1,x2, …, xn, из которого может быть получено любое конкретное решение системы, называют её общим решением, а любое конкретное решение системы - её частным решением. Две системы с одними и теми же неизвестными эквивалентны (равносильны), если каждое решение одной из них является решением другой, или обе системы несовместны.

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

Умножение обеих частей какого-либо уравнения на число, отличное от нуля;

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

Перестановка уравнений;

Вычеркивание уравнений вида 0* x1+0*x2+ …+0* xn=0, то есть тождеств 0=0;

Перестановка столбцов или строк в системе уравнений.

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

Предположим, что коэффициент a11 системы (I) отличен от нуля. Этого всегда можно добиться, переставляя, в случае необходимости, уравнения системы или столбцы в ней и меняя нумерацию неизвестных. Умножим первое уравнение на a21/a11 и вычтем из второго уравнения, затем - на a31/a11 и вычтем из последнего уравнения. В результате неизвестное x1 будет исключено из всех уравнений, кроме первого, и система примет вид:

a11x1 + a12x2 + … +a1nxn = b1,

a'22x2+ … +a'2nxn = b'2, (2)

. . . . . . . . . . . . . . . . .

a'm2x2+ … +a'mnxn= b'm.

В системе (2) следует вычеркнуть уравнения вида 0* x1+0*x2+ …+0* xn=0, если такие появились. На этом первый шаг метода Гаусса заканчивается. Элемент a11 называют ведущим элементом этого шага. Следующие шаги прямого хода осуществляются аналогично. Так, на втором шаге при a'22?0 последовательно умножают второе уравнение на a'32/ a'22, a'42 /a'22, …, a'm2/ a'22 и соответственно вычитают его из 3, 4, …, m-го уравнений. В результате исключится неизвестное X2 из всех уравнений, кроме I и 2-го. На третьем шаге исключается неизвестное X3 из всех уравнений, кроме первых трех, и так далее.

Возможно, что на некотором шаге прямого хода метода Гаусса встретится уравнение вида

0* x1+0*x2+ …+0* xn=bi , bi?0 (3).

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

a11x1 + a12x2 +…+a1zxz+… +a1nxn = b1,

a22x2 + …+a2zxz +a2nxn= b2,

. . . . . . . . . . . . . (4)

azzxz+…+aznxn=bz

Для упрощения записи в системе (4) штрихи над коэффициентами опущены. В ней не более mуравнений, т.е. z?m, так как некоторые уравнения, возможно, были приведены к виду 0=0 и вычеркнуты.

При z=n система (4) имеет треугольный вид

a11x1 + a12x2 +…+a1nxn = b1,

a22x2 + … +a2nxn= b2,

. . . . . . . . . . . . . (5)

annxn=bn

и в ней легко совершить обратный ход метода Гаусса. Для чего из последнего уравнения в системе найдем значение неизвестногоxn. Подставив его в предпоследнее уравнение, найдем значение xn-1. Продолжая так далее, однозначно определим все неизвестные x1, x2,…, xn. Следовательно, еслисистема (I) при прямом ходе метода Гаусса сводится к системе треугольного вида, то такая система - определенная, то есть имеет единственное решение. При z<n система (4) имеет вид трапеции. В ней неизвестные x1, x2,…, xzпринимаются за главные, а неизвестные xz+1,…, xz- свободные. Свободные неизвестные могут принимать любые фиксированные значения. Полагая

xz+1= гz+1, …, xn= гn,

где гz+1, …, гn- произвольные постоянные, и проведя в системе обратный ход метода Гаусса, придем к системе

x1=в1+б1,z+1,гz+1+…+ б1nгn,

x2= в2+б2,z+1,гz+1+…+ б2nгn,

. . . . . . . . . . . . . . .

xz=вz+бz,z+1,гz+1+…+ бznгn, (6)

. . . . . . . . . . .

xz+1=гz+1,

. . . . . .

xn=гn ,

которая является общим решением системы (I). Из общего решения (6) при конкретных значениях гz+1, …, гnбудут получаться частные решения системы (I). Так как каждое свободное неизвестное может принимать бесчисленное множество значений, система (I) при z<n, то есть в случае, когда оно приводится к трапецеидальному виду, обладает бесчисленным множеством решений. Так всегда будет для совместных систем, имеющих меньше уравнений, чем неизвестных.

2. Алгоритм решения матриц систем

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

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

0 … 0 1 * * … * * * … * * * … *

0 … 0 0 1 * … * * * … * * * … *

0 … 0 0 0 0 … 0 1 * … * * * … * 1 - единичные элементы матрицы

? ? ? ? ? ? … ? ? ? ? ? ? ? ? ? * - элементы с произвольными значениями

? ? ? ? ? ? … ? ? ? ? ? * * ? * 0 - нулевые элементы матрицы

0 … 0 0 0 0 … 0 0 0 … 0 1 * … *

0 … 0 0 0 0 … 0 0 0 … 0 0 0 … 0

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

0 … 0 0 0 0 … 0 0 0 … 0 0 0 … 0

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

Алгоритм приведения матриц к ступенчатому виду:

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

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

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

4). Исключив из рассмотрения строку и столбец, на пересечении которых стоит ведущий элемент,перейти к пункту 1), в котором все описанные действия применяются к оставшейся части матрицы.

3. Замечания дополнительные сведения

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

0 … 0 1 0 * … * 0 * … * 0 * … *

0 … 0 0 1 * … * 0 * … * 0 * … *

0 … 0 0 0 0 … 0 1 * … * 0 * … * 1 - единичные элементы матрицы

? ? ? ? ? ? … ? ? ? ? ? ? ? ? ? * - элементы с произвольными значениями

? ? ? ? ? ? … ? ? ? ? ? 0 * ? * 0 - нулевые элементы матрицы

0 … 0 0 0 0 … 0 0 0 … 0 1 * … *

0 … 0 0 0 0 … 0 0 0 … 0 0 0 … 0

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

0 … 0 0 0 0 … 0 0 0 … 0 0 0 … 0

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

1 … 0 0 … 0

? ? ? ? ? ?

0 … 1 0 … 0 = Er 0

0 … 0 0 … 0 0 0

? ? ? ? ? ?

0 … 0 0 … 0

Особенность матрицы простейшего вида - левый верхний угол матрицы представляет собой единичную матрицу порядка r (0 ?r ? min {m;n}), а остальные элементы равны нулю. Считается, что нулевая матрица уже имеет простейший вид ( при r=0).

Преобразования, обратные к элементарным, являются элементарными.

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

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

Алгоритм:

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

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

Все элементы первой строки делят на верхний элемент выбранного столбца.

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

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

После повторения этой процедуры n ? 1 раз получают верхнюю треугольную матрицу

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

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

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

4. Практическая часть

Решение различных СЛАУ.

Пр.1) (стандартная СЛАУ):

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

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

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

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

из третьего;

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

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

Пр.2) (несовместная СЛАУ):

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

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

Пр.3) (неопределенная СЛАУ):

Перейдём к матричному виду и проведем преобразования:

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

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

Получили общее решение системы линейных уравнений. Его можно записать в виде:

Найти одно из частных значений можно, задав значение x3и х3и вычислив остальные переменные.

Пр. 4) (метод Гаусса-Жордана)

Для решения следующей системы уравнений:



Запишем её в виде матрицы 3Ч4, где последний столбец является свободным членом:

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

К строке 2 добавим: ?4 Ч Строку 1.

К строке 3 добавим: ?9 Ч Строку 1.

Получим:

К строке 3 добавим: ?3 Ч Строку 2.

Строку 2 делим на ?2

К строке 1 добавим: ?1 Ч Строку 3.

К строке 2 добавим: ?3/2 Ч Строку 3.

К строке 1 добавим: ?1 Ч Строку 2.

В правом столбце получаем решение:

.



Заключение

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

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

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

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

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

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

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

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



Список используемой литературы

1. Бортаковский, А.С. «Линейная алгебра в примерах и задачах»

2. Г.С. Шевцов «Линейная алгебра (начальные главы, линейные пространства и линейные операторы в них)

3. www.wikipedia.com

Размещено на Allbest.ru