![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которого последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.
Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах», составленном между I в. до н.э. и II в. н. э.
Пусть исходная система выглядит следующим образом
Матрица A называется основной матрицей системы, b — столбцом свободных членов.
Тогда согласно свойству элементарных преобразований над строками основную матрицу этой системы можно привести к ступенчатому виду(эти же преобразования нужно применять к столбцу свободных членов):
При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных .
Тогда переменные называются главными переменными. Все остальные называются свободными.
Если хотя бы одно число , где i > r, то рассматриваемая система несовместна.
Пусть для любых i > r.
Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом (
, где
— номер строки):
где
Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.
Упомянутое выше условие для всех
может быть сформулировано в качестве необходимого и достаточного условия совместности:
Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).
Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.
· На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получившуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.
· На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.
Метод Гаусса требует порядка O (n 3) действий.
В простейшем случае алгоритм выглядит так:
· Прямой ход:
· Обратный ход. Из последнего ненулевого уравнения выражаем базисную переменную через небазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру для всех базисных переменных, получаем фундаментальное решение.
Пример
Покажем, как методом Гаусса можно решить следующую систему:
Обнулим коэффициенты при во второй и третьей строчках. Для этого вычтем из них первую строчку, умноженную на
и
, соответственно:
Теперь обнулим коэффициент при в третьей строке, вычтя из неё вторую строку, умноженную на
:
В результате мы привели исходную систему к треугольному виду, тем самым закончив первый этап алгоритма.
На втором этапе разрешим полученные уравнения в обратном порядке. Имеем:
из третьего;
из второго, подставив полученное
из первого, подставив полученные
и
.
Таким образом исходная система решена.
В случае, если число уравнений в совместной системе получилось меньше числа неизвестных, то тогда ответ будет записываться в виде фундаментальной системы решений.
Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:
· нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: , после чего
приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица:
);
· определения ранга матрицы (согласно следствию из теоремы Кронекера—Капелли ранг матрицы равен числу её главных переменных);
· численного решения СЛАУ в вычислительной технике (ввиду погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент).
Достоинства метода
· Менее трудоёмкий по сравнению с другими методами.
· Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.
· Позволяет найти максимальное число линейно независимых уравнений — ранг матрицы системы.
2.МетодГаусса — Жордана
Метод Гаусса — Жордана (метод полного исключения неизвестных) используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе, отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К. Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана.
Алгоритм
1. Выбирают первую колонку слева, в которой есть хоть одно отличное от нуля значение.
2. Если самое верхнее число в этой колонке есть ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.
3. Все элементы первой строки делят на верхний элемент выбранной колонки.
4. Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.
5. Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.
6. После повторения этой процедуры n − 1 раз получают верхнюю треугольную матрицу
7. Вычитаем из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.
8. Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).
9. Чтобы получить обратную матрицу, нужно применить все операции в том же порядке к единичной матрице.
Пример
Для решения следующей системы уравнений:
запишем её в виде матрицы 3×4, где последний столбец является свободным членом:
Проведём следующие действия:
· К строке 2 добавим: −4 × Строку 1.
· К строке 3 добавим: −9 × Строку 1.
Получим:
· К строке 3 добавим: −3 × Строку 2.
· Строку 2 делим на −2
· К строке 1 добавим: −1 × Строку 3.
· К строке 2 добавим: −3/2 × Строку 3.
· К строке 1 добавим: −1 × Строку 2.
В правом столбце получаем решение:
Дата публикования: 2015-04-07; Прочитано: 971 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!