Метод гаусса для решения слау. Метод Гаусса (последовательного исключения неизвестных)

Пояснительная записка

Данная методическая разработка предназначена для проведения занятия по дисциплине “Математика” на тему “Решение систем линейных уравнений методом Гаусса” по программе учебной дисциплины, разработанной на основе Федерального государственного образовательного стандарта для специальностей среднего профессионального образования.

В результате изучения темы студент должен:

знать:

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

уметь:

• решать системы линейных уравнений методом Гаусса.

Цели занятия:

обучающие:

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

развивающие:

• развивать умения анализировать полученную информацию, делать выводы;

воспитательные:

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

Ход занятия

Оценка “отлично” :

• работа выполнена полностью;

Оценка “хорошо” :

Оценка “удовлетворительно” :

Оценка “неудовлетворительно” :

Общее время - 90 мин.

План занятия:

1. Организационный момент;
2. Проверка внеаудиторной самостоятельной работы;
3. Теоретическая часть;
4. Практическая часть;
5. Итоги занятия.

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

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

Система n линейных уравнений с m неизвестными может имеет вид:

I=1, 2, 3, …, n; j=1, 2, 3,..., m.

Заметим, что число неизвестных m и число уравнений n в общем случае между собой никак не связаны. Возможны три случая: m=n, m > n, m < n.

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

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

1. Система приводится к ступенчатому (треугольному) виду

2. Последовательное определение неизвестных из получившейся ступенчатой системы.

Пусть дана система трех линейных уравнений с тремя неизвестными x, y, z

Введем в рассмотрение матрицу систему и расширенную матрицу .

Элементарные преобразования матриц:

1. Перестановка местами двух рядов матрицы:

;

2. Умножение (деление) всех элементов ряда матрицы на число, отличное от нуля:

Разделим элементы первой строки на 2, а второй – умножим на 2

.

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

Умножим элементы первой строки на 2:

.

Прибавим ко всем элементам первой строки соответствующие элементы второй строки, при этом элементы первой строки запишем без изменений:

Разделим элементы первой строки на 2:

На практике некоторые действия выполняют устно:

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

Рассмотрим суть метода Гаусса на конкретной системе линейных уравнений (см Приложение ):

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

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

Исходная система свелась к ступенчатой:

Из последнего уравнения из предпоследнего уравнения или .

Найдем из первого уравнения : или .

г)

Критерии оценки выполнения самостоятельной работы:

Оценка “отлично” :

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

Оценка “хорошо” :

• работа выполнена полностью, но обоснования шагов решения недостаточны (если умение обосновывать рассуждения не являлось специальным объектом проверки);
• допущены одна ошибка или есть два–три недочёта в выкладках, рисунках, чертежах или графиках (если эти виды работ не являлись специальным объектом проверки).

Оценка “удовлетворительно” :

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

Оценка “неудовлетворительно” :

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

Еще с начала XVI-XVIII веков математики усиленно начали изучать функции, благодаря которым так много в нашей жизни изменилось. Компьютерная техника без этих знаний просто не существовала бы. Для решения сложных задач, линейных уравнений и функций были созданы различные концепции, теоремы и методики решения. Одним из таких универсальных и рациональных способов и методик решения линейных уравнений и их систем стал и метод Гаусса. Матрицы, их ранг, детерминант - все можно посчитать, не используя сложных операций.

Что представляет собой СЛАУ

В математике существует понятие СЛАУ - система линейных алгебраических уравнений. Что же она собой представляет? Это набор из m уравнений с искомыми n неизвестными величинами, обычно обозначающимися как x, y, z, или x 1 , x 2 … x n, или другими символами. Решить методом Гаусса данную систему - означает найти все искомые неизвестные. Если система имеет одинаковое число неизвестных и уравнений, тогда она называется системой n-го порядка.

Наиболее популярные методы решения СЛАУ

В учебных заведениях среднего образования изучают различные методики решения таких систем. Чаще всего это простые уравнения, состоящие из двух неизвестных, поэтому любой существующий метод для поиска ответа на них не займет много времени. Это может быть как метод подстановки, когда из одного уравнения выводится другое и подставляется в изначальное. Или метод почленного вычитания и сложения. Но наиболее легким и универсальным считается метод Гаусса. Он дает возможность решать уравнения с любым количеством неизвестных. Почему именно эта методика считается рациональной? Все просто. Матричный способ хорош тем, что здесь не требуется по несколько раз переписывать ненужные символы в виде неизвестных, достаточно проделать арифметические операции над коэффициентами - и получится достоверный результат.

Где используются СЛАУ на практике

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

Критерий совместимости СЛАУ

Такую систему можно решить только в том случае, если она совместима. Для понятности представим СЛАУ в виде Ax=b. Она имеет решение, если rang(A) равняется rang(A,b). В этом случае (A,b) - это матрица расширенного вида, которую можно получить из матрицы А, переписав ее со свободными членами. Выходит, что решить линейные уравнения методом Гаусса достаточно легко.

Возможно, некоторые обозначения не совсем понятны, поэтому необходимо рассмотреть все на примере. Допустим, есть система: x+y=1; 2x-3y=6. Она состоит всего из двух уравнений, в которых 2 неизвестные. Система будет иметь решение только в том случае, если ранг ее матрицы будет равняться рангу расширенной матрицы. Что такое ранг? Это число независимых строк системы. В нашем случае ранг матрицы 2. Матрица А будет состоять из коэффициентов, находящихся возле неизвестных, а в расширенную матрицу вписываются и коэффициенты, находящиеся за знаком «=».

Почему СЛАУ можно представить в матричном виде

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

Преобразования матриц

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

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

Метод Жордана-Гаусса

Суть решения систем линейных однородных и неоднородных уравнений методом Гаусса в том, чтобы постепенно исключить неизвестные. Допустим, у нас есть система из двух уравнений, в которых две неизвестные. Чтобы их найти, необходимо проверить систему на совместимость. Уравнение методом Гаусса решается очень просто. Необходимо выписать коэффициенты, находящиеся возле каждого неизвестного в матричный вид. Для решения системы понадобится выписать расширенную матрицу. Если одно из уравнений содержит меньшее количество неизвестных, тогда на место пропущенного элемента необходимо поставить «0». К матрице применяются все известные методы преобразования: умножение, деление на число, прибавление соответствующих элементов рядов друг к другу и другие. Получается, что в каждом ряду необходимо оставить одну переменную со значением «1», остальные привести к нулевому виду. Для более точного понимания необходимо рассмотреть метод Гаусса на примерах.

Простой пример решения системы 2х2

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

Перепишем ее в расширенную матрицу.

Чтобы решить данную систему линейных уравнений, требуется проделать всего две операции. Нам необходимо привести матрицу к каноническому виду, чтобы по главной диагонали стояли единицы. Так, переводя с матричного вида обратно в систему, мы получим уравнения: 1x+0y=b1 и 0x+1y=b2, где b1 и b2 - получившиеся ответы в процессе решения.

1. Первое действие при решении расширенной матрицы будет таким: первый ряд необходимо умножить на -7 и прибавить соответственно отвечающие элементы ко второй строке, чтобы избавиться от одного неизвестного во втором уравнении.
2. Так как решение уравнений методом Гаусса подразумевает приведение матрицы к каноническому виду, тогда необходимо и с первым уравнением проделать те же операции и убрать вторую переменную. Для этого вторую строку отнимаем от первой и получаем необходимый ответ - решение СЛАУ. Или, как показано на рисунке, вторую строку умножаем на коэффициент -1 и прибавляем к первой строке элементы второго ряда. Это одно и то же.

Как видим, наша система решена методом Жордана-Гаусса. Переписываем ее в необходимую форму: x=-5, y=7.

Пример решения СЛАУ 3х3

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

Как и в прежнем примере, переписываем систему в вид расширенной матрицы и начинаем приводить ее к каноническому виду.

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

1. Сначала необходимо сделать в первом столбце один единичный элемент и остальные нули. Для этого умножаем первое уравнение на -1 и прибавляем к нему второе уравнение. Важно запомнить, что первую строку мы переписываем в изначальном виде, а вторую - уже в измененном.
2. Далее убираем эту же первую неизвестную из третьего уравнения. Для этого элементы первой строки умножаем на -2 и прибавляем их к третьему ряду. Теперь первая и вторая строки переписываются в изначальном виде, а третья - уже с изменениями. Как видно по результату, мы получили первую единицу в начале главной диагонали матрицы и остальные нули. Еще несколько действий, и система уравнений методом Гаусса будет достоверно решена.
3. Теперь необходимо проделать операции и над другими элементами рядов. Третье и четвертое действие можно объединить в одно. Нужно разделить вторую и третью строку на -1, чтобы избавиться от минусовых единиц по диагонали. Третью строку мы уже привели к необходимому виду.
4. Дальше приведем к каноническому виду вторую строку. Для этого элементы третьего ряда умножаем на -3 и прибавляем их ко второй строчке матрицы. Из результата видно, что вторая строка тоже приведена к необходимой нам форме. Осталось проделать еще несколько операций и убрать коэффициенты неизвестных из первой строки.
5. Чтобы из второго элемента строки сделать 0, необходимо умножить третью строку на -3 и прибавить ее к первому ряду.
6. Следующим решающим этапом будет прибавление к первой строке необходимые элементы второго ряда. Так мы получаем канонический вид матрицы, а, соответственно, и ответ.

Как видно, решение уравнений методом Гаусса довольно простое.

Пример решения системы уравнений 4х4

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

Ниже описана пошаговая инструкция решения такого примера.

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

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

Проверка правильности решения

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

Метод Гаусса: наиболее часто встречающиеся ошибки при решении СЛАУ

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

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

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

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

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

О методе

При решении системы линейных уравнений методом Гаусса выполняются следующие шаги.

1. Записываем расширенную матрицу.
2. Фактически алгоритм разделяют на прямой и обратный ход. Прямым ходом называется приведение матрицы к ступенчатому виду. Обратным ходом называется приведение матрицы к специальному ступенчатому виду. Но на практике удобнее сразу занулять то, что находится и сверху и снизу рассматриваемого элемента. Наш калькулятор использует именно этот подход.
3. Важно отметить, что при решении методом Гаусса, наличие в матрице хотя бы одной нулевой строки с НЕнулевой правой частью (столбец свободных членов) говорит о несовместности системы. Решение в таком случае не существует.

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

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

Формально задача ставится следующим образом: решить систему:

где коэффициенты и известны, а переменные — искомые неизвестные.

Удобно матричное представление этой задачи:

где — матрица , составленная из коэффициентов , и — векторы-столбцы высоты .

Стоит отметить, что СЛАУ может быть не над полем действительных чисел, а над полем по модулю какого-либо числа , т.е.:

— алгоритм Гаусса работает и для таких систем тоже (но этот случай будет рассмотрен ниже в отдельном разделе).

Алгоритм Гаусса

Строго говоря, описываемый ниже метод правильно называть методом "Гаусса-Жордана" (Gauss-Jordan elimination), поскольку он является вариацией метода Гаусса, описанной геодезистом Вильгельмом Жорданом в 1887 г. (стоит отметить, что Вильгельм Жордан не является автором ни теоремы Жордана о кривых, ни жордановой алгебры — всё это три разных учёных-однофамильца; кроме того, по всей видимости, более правильной является транскрипция "Йордан", но написание "Жордан" уже закрепилось в русской литературе). Также интересно заметить, что одновременно с Жорданом (а по некоторым данным даже раньше него) этот алгоритм придумал Класен (B.-I. Clasen).

Базовая схема

Кратко говоря, алгоритм заключается в последовательном исключении переменных из каждого уравнения до тех пор, пока в каждом уравнении не останется только по одной переменной. Если , то можно говорить, что алгоритм Гаусса-Жордана стремится привести матрицу системы к единичной матрице — ведь после того как матрица стала единичной, решение системы очевидно — решение единственно и задаётся получившимися коэффициентами .

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

На первом шаге алгоритм Гаусса-Жордана делит первую строку на коэффициент . Затем алгоритм прибавляет первую строку к остальным строкам с такими коэффициентами, чтобы их коэффициенты в первом столбце обращались в нули — для этого, очевидно, при прибавлении первой строки к -ой надо домножать её на . При каждой операции с матрицей (деление на число, прибавление к одной строке другой) соответствующие операции производятся и с вектором ; в некотором смысле, он ведёт себя, как если бы он был -ым столбцом матрицы .

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

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

Поиск опорного элемента (pivoting)

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

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

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

К счастью, для корректности метода достаточно одних только обменов строк (т.н. "partial pivoting", в отличие от "full pivoting", когда обмениваются и строки, и столбцы). Но какую же именно строку следует выбирать для обмена? И правда ли, что поиск опорного элемента надо делать только тогда, когда текущий элемент нулевой?

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

Иными словами, перед выполнением -ой фазы алгоритма Гаусса-Жордана с эвристикой partial pivoting необходимо найти в -ом столбце среди элементов с индексами от до максимальный по модулю, и обменять строку с этим элементом с -ой строкой.

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

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

Вырожденные случаи

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

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

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

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

Впрочем, проще это проверить явной подстановкой найденного решения: всем независимыми переменным присвоить нулевые значения, зависимым переменным присвоить найденные значения, и подставить это решение в текущую СЛАУ.

Реализация

Приведём здесь реализацию алгоритма Гаусса-Жордана с эвристикой partial pivoting (выбором опорного элемента как максимума по столбцу).

На вход функции передаётся сама матрица системы . Последний столбец матрицы — это в наших старых обозначениях столбец свободных коэффициентов (так сделано для удобства программирования — т.к. в самом алгоритме все операции со свободными коэффициентами повторяют операции с матрицей ).

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

В функции поддерживаются два указателя — на текущий столбец и текущую строку .

Также заводится вектор , в котором для каждой переменной записано, в какой строке должна она получиться (иными словами, для каждого столбца записан номер строки, в которой этот столбец отличен от нуля). Этот вектор нужен, поскольку некоторые переменные могли не "определиться" в ходе решения (т.е. это независимые переменные, которым можно присвоить произвольное значение — например, в приведённой реализации это нули).

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

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

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

Асимптотика

Оценим асимптотику полученного алгоритма. Алгоритм состоит из фаз, на каждой из которых происходит:

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

Таким образом, итоговая асимптотика алгоритма принимает вид .

При эта оценка превращается в .

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

Более точная оценка числа действий

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

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

Дополнения

Ускорение алгоритма: разделение его на прямой и обратный ход

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

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

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

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

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

Таким образом, если , то данный алгоритм будет делать уже операций — что в два раза меньше алгоритма Гаусса-Жордана.

Решение СЛАУ по модулю

Для решения СЛАУ по модулю можно применять описанный выше алгоритм, он сохраняет свою корректность.

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

Если модуль простой, то никаких сложностей вообще не возникает — происходящие по ходу работы алгоритма Гаусса деления не создают особых проблем.

Особенно замечателен модуль, равный двум : для него все операции с матрицей можно производить очень эффективно. Например, отнимание одной строки от другой по модулю два — это на самом деле их симметрическая разность ("xor"). Таким образом, весь алгоритм можно значительно ускорить, сжав всю матрицу в битовые маски и оперируя только ими. Приведём здесь новую реализацию основной части алгоритма Гаусса-Жордана, используя стандартный контейнер C++ "bitset":

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

Если модуль произвольный (не обязательно простой), то всё становится несколько сложнее. Понятно, что пользуясь Китайской теоремой об остатках , мы сводим задачу с произвольным модулем только к модулям вида "степень простого". [ дальнейший текст был скрыт, т.к. это непроверенная информация — возможно, неправильный способ решения ]

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

Немного о различных способах выбора опорного элемента

Как уже говорилось выше, однозначного ответа на этот вопрос нет.

Эвристика "partial pivoting", которая заключалась в поиске максимального элемента в текущем столбце, работает на практике весьма неплохо. Также оказывается, что она даёт практически тот же результат, что и "full pivoting" — когда опорный элемент ищется среди элементов целой подматрицы — начиная с текущей строки и с текущего столбца.

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

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

Улучшение найденного ответа

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

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

Таким образом, решение превращается в двухшаговое: сначала выполняется алгоритм Гаусса-Жордана, затем — какой-либо численный метод, принимающий в качестве начальных данных решение, полученное на первом шаге.

Такой приём позволяет несколько расширить множество задач, решаемых алгоритмом Гаусса-Жордана с приемлемой погрешностью.

Литература

• William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes: The Art of Scientific Computing
• Anthony Ralston, Philip Rabinowitz. A first course in numerical analysis

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

Метод Гаусса

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

1. Система имеет единственное решение (определитель главной матрицы системы не равен нулю);
2. Система имеет бесконечное множество решений;
3. Решений нет, система несовместна.

Итак, у нас есть система (пусть у нее будет одно решение), и мы собираемся решать ее методом Гаусса. Как это работает?

Метод Гаусса состоит из двух этапов – прямого и обратного.

Прямой ход метода Гаусса

Сначала запишем расширенную матрицу системы. Для этого в главную матрицу добавляем столбец свободных членов.

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

Что можно делать:

1. Можно переставлять строки матрицы местами;
2. Если в матрице есть одинаковые (или пропорциональные) строки, можно удалить их все, кроме одной;
3. Можно умножать или делить строку на любое число (кроме нуля);
4. Нулевые строки удаляются;
5. Можно прибавлять к строке строку, умноженную на число, отличное от нуля.

Обратный ход метода Гаусса

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

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

Пример решения системы уравнений методом Гаусс

А теперь - пример, чтобы все стало наглядно и понятно. Пусть дана система линейных уравнений, и нужно решить ее методом Гаусса:

Сначала запишем расширенную матрицу:

Теперь займемся преобразованиями. Помним, что нам нужно добиться треугольного вида матрицы. Умножим 1-ую строку на (3). Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой и получим:

Затем умножим 3-ую строку на (-1). Добавим 3-ую строку к 2-ой:

Умножим 1-ую строку на (6). Умножим 2-ую строку на (13). Добавим 2-ую строку к 1-ой:

Вуаля - система приведена к соответствующему виду. Осталось найти неизвестные:

Система в данном примере имеет единственное решение. Решение систем с бесконечным множеством решений мы рассмотрим в отдельной статье. Возможно, сначала Вы не будете знать, с чего начать преобразования матрицы, но после соответствующей практики набьете руку и будете щелкать СЛАУ методом Гаусса как орешки. А если Вы вдруг столкнетесь со СЛАУ, которая окажется слишком крепким орешком, обращайтесь к нашим авторам! вы можете, оставив заявку в Заочнике. Вместе мы решим любую задачу!

Главная » Артикли » Метод гаусса для решения слау. Метод Гаусса (последовательного исключения неизвестных)