Метод Гаусса для чайников: примеры решений. Метод гаусса для чайников: решаем слау легко

Систему уравнений (1.1) представим в виде

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

Метод Гаусса можно интерпретировать как метод, в котором первоначально матрица приводится к верхней треугольной форме (прямой ход), а далее - к единичной (обратный ход). Очевидно, что если матрица единичная, то x t = b r

Пусть матрица системы (1.3) - верхняя треугольная, поэтому a tj = 0 при i > j, т. е. все элементы ниже главной диагонали равны нулю. Тогда из последнего уравнения сразу определяем х п. Подставляя х п в предпоследнее уравнение, находим х а _ х и т. д. Общие формулы имеют вид

При k > I коэффициенты а ы = 0.

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

Запишем общие формулы метода Гаусса. Пусть проведено исключение коэффициентов из (А - 1)-го столбца. Тогда останутся уравнения с ненулевыми элементами ниже главной диагонали:

Умножим k-ю строку на число с тк = т > k и вычтем

из m-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам

Проведя вычисления по этим формулам при всех указанных индексах, обратим в нуль элементы k-ro столбца, лежащие ниже главной диагонали. Аналогичная процедура приводит матрицу системы к верхней треугольной форме, при этом весь процесс приведения называется ПРЯМЫМ ХОДОМ МЕТОДА ГАУССА. Вычисление неизвестных по формулам (1.4) называют ОБРАТНЫМ ХОДОМ метода.

Обратный ход можно совершить иначе, если обратить в нуль и все коэффициенты, лежащие выше главной диагонали. Например, элементы п -го столбца обращаются в нуль, если ej^| умножить на (-a^V ax t = б| 2л) , где Ь^ п) - коэффициенты правой части i-го уравнения после указанных преобразований.

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

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

Для реализации метода требуется примерно п 3 /3 операций типа умножения и п 3 /3 операций типа сложения . Полезно помнить, что оценка числа операций определяется в основном операциями, затрачиваемыми при выполнении прямого хода метода Гаусса. Обратный ход метода Гаусса требует примерно п 2 операций. Следовательно, если требуется решить несколько систем линейных алгебраических уравнений вида Ах = b с одной и той же матрицей и различными правыми частями, то общее число операций при решении S систем будет оцениваться величиной (2/3)п 3 + Sn 2 . В этом случае целесообразно реализовать алгоритм метода Гаусса в виде двух подпрограмм: первая подпрограмма должна реализовывать прямой ход алгоритма и получать на выходе верхнюю треугольную матрицу, а вторая подпрограмма должна, используя полученную матрицу, вычислять решение системы для произвольной правой части.

2. Модификации метода Гаусса

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

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

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

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

Если на k-м шаге в качестве главного элемента выбирается ¹ , то в матрице A¢ должны быть переставлены местами строки c номерами k и p и столбцы с номерами k и q.

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

Существуют две более простые модификации метода Гаусса:

С выбором главного элемента по столбцу;

С выбором главного элемента по строке.

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

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

LU-разложение. В современном математическом обеспечении ЭВМ метод Гаусса реализуется с использованием LU-разложения, под которым понимают представление матрицы коэффициентов A в виде произведения A = LU двух матриц L и U, где L – нижняя треугольная матрица, U - верхняя треугольная матрица

Если LU-разложение получено, то решение исходной системы уравнений (2) сводится к последовательному решению двух следующих систем уравнений с треугольными матрицами коэффициентов

линейный алгебраический уравнение численный

где Y = - вектор вспомогательных переменных.

Такой подход позволяет многократно решать системы линейных уравнений с разными правыми частями B. При этом наиболее трудоемкая часть (LU-разложение матрицы A) выполняется только один раз. Эта процедура соответствует прямому ходу метода Гаусса и имеет оценку трудоемкости O(n 3). Дальнейшее решение систем уравнений (6) и (7) может выполняться многократно (для различных B), причем решение каждой из них соответствует обратному ходу метода Гаусса и имеет оценку вычислительной сложности O(n 2).

Для получения LU-разложения можно воспользоваться следующим алгоритмом.

1. Для исходной системы (1) выполнить прямой ход метода Гаусса и получить систему уравнений треугольного вида (5).

2. Определить элементы матрицы U по правилу

u ij = C ij (i = ; j = )

3. Вычислить элементы матрицы L по правилам

Расчетные формулы для решения системы (6) имеют следующий вид:

y 1 = b 1 / l 11 ;

Расчетные формулы для решения системы (7)

(i = n - 1, n - 2, …, 1).

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

35437 x4=0.58554 5 x1=1.3179137 x2=-1.59467 x3=0.35371 x4=0.58462 6 x1=1.3181515 x2=-1.59506 x3=0.35455 x4=0.58557 5. Сравнительный анализ различных методов численного дифференцирования и интегрирования 5.1 Методы численного дифференцирования 5.1.1 Описание метода Предположим, что в окрестности точки xiфункция F (x) дифференцируема достаточное число раз. ...

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

Числа). Далее по формулам (2) последовательно находятся xn-1 , xn-2 ,…, x1 при i=n-1, n-2,...,1 соответственно. Таким образом, решение уравнений вида (1) описываем способом, называемым методом прогонки, сводится к вычислениям по трём простым формулам: нахождение так называемых прогоночных коэффициентов δi, λiпо формулам (3) при i=1,2,…,n (прямая прогонка) и затем неизвестных xi по...

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

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

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

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

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

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

Вторая модификация метода Гаусса – поиск по столбцам. Указанное требование можно обеспечить, если неизвестные х i исключаются в произвольном порядке, а в ведущей строке ищется , доставляющий . Это и будет очередной ведущий элемент. После определения ведущего элемента меняем местами k-й и r-й столбцы .

Внимание. При такой замене меняется нумерация неизвестных x i . Чтобы обеспечить такую замену, надо при программировании ввести массив p 1 ,…p n с настоящими номерами неизвестных. В начале прямого хода все p i = i – обычная нумерация. После нахождения ведущего элемента меняем местами p k и p r . При обратном ходе по формуле (7) вычисляются перенумерованные x i . После вычисления всех неизвестных надо положить y]:=x[i] , и массив y[i] будет окончательным решением задачи.

Третья модификация метода Гаусса – полный поиск. В качестве ведущего выбирается элемент , доставляющий . При этом меняются местами k-й и r-й столбцы, p k и p r , а также m-я и k-я строки. Эта модификация обеспечивает максимальную точность, но и наиболее сложна.

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

1. Обращение матриц. Пусть необходимо вычислить обратную матрицу к квадратной матрице А. Обозначим Х = А –1 . Как известно АХ = I, где I – единичная матрица, в которой по диагонали расположены 1, а остальные элементы – 0. Иными словами, i-й столбец матрицы I равен

(1 стоит на i-м месте). Пусть х (i) – i-й столбец матрицы Х. Тогда, в силу правила умножения матриц (строка умножается на столбец) имеем А х (i) = e (i) . Значит, для обращения матрицы надо решить n систем линейных уравнений с одинаковыми матрицами и разными правыми частями:

Ах = е (1) ; Ах = е (2) ; …; Ах = е ( n ) . (2.1)

Решив эти системы, получим, что найденные решения х (1) , х (2) , …, х (n) являются столбцами матрицы А –1 .

2. Вычисление определителей. В процессе преобразования матрицы А к треугольному виду методом Гаусса мы выполняли с ней следующие действия:

1) переставляли строки или столбцы в зависимости от модификации метода;

2) делили ведущую строку на ненулевой ведущий элемент;

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

Как известно, при таких преобразованиях определитель матрицы претерпевает соответствующие изменения:

1) изменяет знак;

2) делится на тот же элемент;

3) не меняется.

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

det A = (–1) s × a 11 × a 22 ×…× a n n ,

где a j j – ведущие элементы, s – число перестановок строк и/или столбцов при поиске ведущих элементов.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

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

и выполнить следующие задания

1) Решить эту систему уравнений

2) Вычислить определитель матрицы данной системы (методом Гаусса – см. п 2 ).

3) Обратить матрицу этой системы (методом Гаусса – см. п 1 ).

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

2. Составить программу решения линейной системы методом Гаусса (с поиском по строкам, по столбцам, по всей матрице – в зависимости от варианта задания) и выполнить обращение матриц с использованием этой программы.

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

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

Метод Гаусса (метод последовательного исключения неизвестных ) заключается в том, что с помощью элементарных преобразований система приводится к эквивалентной системе ступенчатого вида. Сначала с помощью 1-го уравнения исключается x 1 из всех последующих уравнений системы. Затем с помощью2-го уравнения исключается x 2 из 3-го и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса , продолжается до тех пор, пока в левой части последнего уравнения останется только одно неизвестное x n . После этого производится обратный ход метода Гаусса – решая последнее уравнение, находим x n ; после этого, используя это значение, из предпоследнего уравнения вычисляем x n –1 и т.д. Последним находим x 1 из первого уравнения.

Преобразования Гаусса удобно проводить, осуществляя преобразования не с самими уравнениями, а с матрицами их коэффициентов. Рассмотрим матрицу:

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

Пример 5.1. Решить систему методом Гаусса:

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

получим нули во 2-й, 3-й и 4-й строках первого столбца:

Теперь нужно чтобы все элементы во втором столбце ниже 2-й строки были равны нулю. Для этого можно умножить вторую строку на –4/7 и прибавить к 3-й строке. Однако чтобы не иметь дело с дробями, создадим единицу во 2-й строке второго столбца и только

Теперь, чтобы получить треугольную матрицу, нужно обнулить элемент четвертой строки 3-го столбца, для этого можно умножить третью строку на 8/54 и прибавить ее к четвертой. Однако чтобы не иметь дело с дробями поменяем местами 3-ю и 4-ю строки и 3-й и 4-й столбец и только после этого произведем обнуление указанного элемента. Заметим, что при перестановке столбцов меняются местами, соответствующие переменные и об этом нужно помнить; другие элементарные преобразования со столбцами (сложение и умножение на число) производить нельзя!

Последняя упрощенная матрица соответствует системе уравнений, эквивалентной исходной:

Отсюда, используя обратный ход метода Гаусса, найдем из четвертого уравнения x 3 = –1; из третьего x 4 = –2, из второго x 2 = 2 и из первого уравнения x 1 = 1. В матричном виде ответ записывается в виде

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

Пример 5.2. Исследовать систему методом Гаусса:

Решение . Выписываем и преобразуем расширенную матрицу системы

Записываем упрощенную систему уравнений:

Здесь, в последнем уравнении получилось, что 0=4, т.е. противоречие. Следовательно, система не имеет решения, т.е. она несовместна . à

Пример 5.3. Исследовать и решить систему методом Гаусса:

Решение . Выписываем и преобразуем расширенную матрицу системы:

В результате преобразований, в последней строке получились одни нули. Это означает, что число уравнений уменьшилось на единицу:

Таким образом, после упрощений осталось два уравнения, а неизвестных четыре, т.е. два неизвестных "лишних". Пусть "лишними", или, как говорят, свободными переменными , будут x 3 и x 4 . Тогда

Полагая x 3 = 2a и x 4 = b , получим x 2 = 1–a и x 1 = 2b –a ; или в матричном виде

Записанное подобным образом решение называется общим , поскольку, придавая параметрам a и b различные значения, можно описать все возможные решения системы. à

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

Метод Гаусса

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

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-ой:

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

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