Метод гаусса онлайн. Методы решения слу

Рассмотрим точные методы решения системы ; здесь - матрица размерности

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

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

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

делим на коэффициент , в результате получаем уравнение

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

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

Совокупность проведенных вычислений, в ходе которых исходная задача преобразовалась к виду (2), называется прямым ходом метода Гаусса.

Из уравнения системы (2) определяем , из и т. д. до . Совокупность таких вычислений называют обратным ходом метода Гаусса.

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

Исключение происходит в результате следующих операций: 1) деления уравнения на , 2) вычитания получающегося после такого деления уравнения, умноженного на , из уравнений с номерами к . Первая операция равносильна умножению системы уравнений слева на диагональную матрицу

вторая операция равносильна умножению слева на матрицу

Таким образом, система (2), получаемая в результате этих преобразований, запишется в виде

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

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

Введем обозначение . Согласно построению все и матрица D правая треугольная. Отсюда получаем представление матрицы А в виде произведения левой и правой треугольных матриц:

Равенство вместе с условием , образует систему уравнений относительно элементов треугольных матриц В и : . Поскольку при и при , эта система может быть записана в виде

(3)

или, что то же самое,

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

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

Таким образом, вместо последовательных преобразований системы (1) к виду (2) можно непосредственно произвести вычисление матриц В и с помощью формул (4). Эти вычисления можно осуществить, если только все элементы окажутся отличными от нуля. Пусть - матрицы главных миноров порядка матриц А, В, D. Согласно (3) . Поскольку , то . Следовательно,

Итак, для осуществления вычислений по формулам (4) необходимо и достаточно выполнение условий

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

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

Последовательность операций по разложению матрицы А на произведение треугольных матриц и по определению вектора d часто удобно объединить. Уравнения

системы можно записать в виде

Следовательно, значения могут вычисляться одновременно с остальными значениями по формулам (4).

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

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

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

Задача 2. Оценить объем загружаемой памяти ЭВМ в методе Гаусса для ленточных матриц.

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

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

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

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

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

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

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

Часто требуется решить несколько систем уравнений , с одной и той же матрицей А. Удобно поступить следующим образом: введя обозначения

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

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

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

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

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

Наряду с исходной системой тем же методом решается система

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

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

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

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

причем все - диагональная матрица с элементами , равными или -1. Матричное равенство (6) образует систему уравнений

Аналогичные уравнения при отброшены, так как уравнения, соответствующие парам и , эквивалентны. Отсюда получаем рекуррентные формулы для определения элементов и :

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

Задача 3. Оценить число арифметических операций и загрузку памяти ЭВМ (при условии объем памяти, требуемый для запоминания матрицы А, уменьшается) при решении системы с вещественной положительно определеннной матрицей А методом квадратного корня.

Многие пакеты прикладных программ для решения краевых задач математической физики методом конечных элементов организованы по следующей схеме. После формирования матрицы системы А путем перестановки строк и столбцов (одновременно переставляются и строки и и столбцы) система преобразуется к виду с наименьшей шириной ленты. Далее применяется метод квадратного корня. При этом с целью уменьшения объема вычислений при решении системы с другими правыми частями матрица S запоминается.

Две системы линейных уравнений называются равносильными, если множество всех их решений совпадает.

Элементарные преобразования системы уравнений - это:

1. Вычеркивание из системы тривиальных уравнений, т.е. таких, у которых все коэффициенты равны нулю;
2. Умножение любого уравнения на число, отличное от нуля;
3. Прибавление к любому i -му уравнению любого j -то уравнения, умноженного на любое число.

Переменная x i называется свободной, если эта переменная не является разрешенной, а вся система уравнений - является разрешенной.

Теорема. Элементарные преобразования переводят систему уравнений в равносильную.

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

Итак, метод Гаусса состоит из следующих шагов:

1. Рассмотрим первое уравнение. Выберем первый ненулевой коэффициент и разделим все уравнение на него. Получим уравнение, в которое некоторая переменная x i входит с коэффициентом 1;
2. Вычтем это уравнение из всех остальных, умножая его на такие числа, чтобы коэффициенты при переменной x i в остальных уравнениях обнулились. Получим систему, разрешенную относительно переменной x i , и равносильную исходной;
3. Если возникают тривиальные уравнения (редко, но бывает; например, 0 = 0), вычеркиваем их из системы. В результате уравнений становится на одно меньше;
4. Повторяем предыдущие шаги не более n раз, где n - число уравнений в системе. Каждый раз выбираем для «обработки» новую переменную. Если возникают противоречивые уравнения (например, 0 = 8), система несовместна.

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

1. Число переменных равно числу уравнений. Значит, система определена;
2. Число переменных больше числа уравнений. Собираем все свободные переменные справа - получаем формулы для разрешенных переменных. Эти формулы так и записываются в ответ.

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

Задача. Решить систему уравнений:

Описание шагов:

1. Вычитаем первое уравнение из второго и третьего - получим разрешенную переменную x 1 ;
2. Умножаем второе уравнение на (−1), а третье уравнение делим на (−3) - получим два уравнения, в которых переменная x 2 входит с коэффициентом 1;
3. Прибавляем второе уравнение к первому, а из третьего - вычитаем. Получим разрешенную переменную x 2 ;
4. Наконец, вычитаем третье уравнение из первого - получаем разрешенную переменную x 3 ;
5. Получили разрешенную систему, записываем ответ.

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

Когда может понадобиться общее решение? Если приходится делать меньше шагов, чем k (k - это сколько всего уравнений). Однако причин, по которым процесс заканчивается на некотором шаге l < k , может быть две:

1. После l -го шага получилась система, которая не содержит уравнения с номером (l + 1). На самом деле это хорошо, т.к. разрешенная система все равно получена - даже на несколько шагов раньше.
2. После l -го шага получили уравнение, в котором все коэффициенты при переменных равны нулю, а свободный коэффициент отличен от нуля. Это противоречивое уравнение, а, следовательно, система несовместна.

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

Описание шагов:

1. Вычитаем первое уравнение, умноженное на 4, из второго. А также прибавляем первое уравнение к третьему - получим разрешенную переменную x 1 ;
2. Вычитаем третье уравнение, умноженное на 2, из второго - получим противоречивое уравнение 0 = −5.

Итак, система несовместна, поскольку обнаружено противоречивое уравнение.

Задача. Исследовать совместность и найти общее решение системы:

Описание шагов:

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

Итак, система совместная и неопределенная, поскольку есть две разрешенных переменных (x 1 и x 2) и две свободных (x 3 и x 4).

(СЛАУ), состоящая из уравнений с неизвестными:

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

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

Описание метода

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

по методу Гаусса состоит из 2х этапов:

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

• Обратный ход Непосредственное определение неизвестных

1. Из го уравнения системы определяем 2. Из го - определяем и т.д.

Анализ метода

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

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

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

Возможны 3 случая:

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

Проиллюстрируем полученные результаты на следующем числовом примере: Дана система

Она имеет решение .

Теперь рассмотрим возмущенную систему:

Решением такой системы будет вектор .

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

Такой результат можно было предвидеть в силу плохой обусловленностью матрицы :

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

Способы оценки ошибок

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

Составляем контрольный столбец , состоящий из контрольных элементов системы:

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

2) Относительная погрешность известного решения позволяет без существенных дополнительных затрат получить суждение о погрешности решения.

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

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

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

Наряду с исходной системой тем же методом решается система

, где и - числа

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

Улучшение метода исключения Гаусса

Рассмотренные ниже модификации метода Гаусса позволяют уменьшить погрешность результата.

Выбор главного элемента

Основное увеличение ошибки в методе происходит во время прямого хода, когда ведущая -я строка умножается на коэффициенты .Если коэффициенты 1%20" alt=" >1 ">, то ошибки, полученные на предыдущих шагах накапливаются. Чтобы этого избежать, применяется модификация метода Гаусса с выбором главного элемента. На каждом шаге к обычной схеме добавляется выбор максимального элемента по столбцу следующим образом:

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

, .

Найдем такое , что и поменяем местами -е и -е уровнения.

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

Итеративное улучшение результата

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

.

Решая эту систему, получаем приближение к и полагаем

.

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

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

Числовой пример

Рассмотрим для примера матрицу Вандермонда размером 7х7 и 2 различные правые части:

Данные системы были решены двумя способами. Тип данных - float. B итоге получили следующие результаты:

Обычный метод
1		2
1	2	1	2
0.999991	1	0.999996	1
1.00019	1	7.4774e-005	2,33e-008
0.998404	1	0.999375	1
1.00667	1	0.00263727	1,12e-006
0.985328	1	0.994149	1
1.01588	1	0.00637817	3,27e-006
0.993538	1	0.99739	1
0,045479	2,9826e-006	0,01818	8,8362e-006
0,006497	4,2608e-007	0,0045451	2,209e-006
0,040152	4,344e-005	0,083938	2,8654e-006

С выбором ведущего элемента по строке
1		2
1	2	1	2
1	1	1	1
1	1	-3.57628e-005	1,836e-007
1.00001	1	1.00031	1
0.999942	1	-0.00133276	7,16e-006
1.00005	1	1.00302	0,99998
1.00009	1	-0.0033505	1,8e-005
0.99991	1	1.00139	0,99999
0,000298	4,3835e-007	0,009439	5,0683e-005
4,2571e-005	6,2622e-008	0,0023542	1,2671e-005
0,010622	9,8016e-007	0,29402	1,4768e-006

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

Преобразуем систему, исключив неизвестное х1 во всех уравнениях, кроме первого (используя элементарные преобразования системы). Для этого умножим обе части первого уравнения на

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

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

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

Таким образом, на первом шаге уничтожаются все коэффициенты, лежащие под первым ведущим элементом a 11

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

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

то это свидетельствует о несовместности системы.

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

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

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

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

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

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

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

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

Пример 1. Решить СЛАУ 3-го порядка.

Обнулим коэффициенты при

во второй и третьей строчках. Для этого домножим их на 2/3 и 1 соответственно и сложим с первой строкой:

Метод Гаусса прекрасно подходит для решения систем линейных алгебраических уравнений (СЛАУ). Он обладает рядом преимуществ по сравнению с другими методами:

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

Краткий обзор статьи.

Сначала дадим необходимые определения и введем обозначения.

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

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

Навигация по странице.

Основные определения и обозначения.

Рассмотрим систему из p линейных уравнений с n неизвестными (p может быть равно n ):

Где - неизвестные переменные, - числа (действительные или комплексные), - свободные члены.

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

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

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

Если СЛАУ имеет единственное решение, то она называется определенной . Если решений больше одного, то система называется неопределенной .

Говорят, что система записана в координатной форме , если она имеет вид
.

Эта система в матричной форме записи имеет вид , где - основная матрица СЛАУ, - матрица столбец неизвестных переменных, - матрица свободных членов.

Если к матрице А добавить в качестве (n+1)-ого столбца матрицу-столбец свободных членов, то получим так называемую расширенную матрицу системы линейных уравнений. Обычно расширенную матрицу обозначают буквой Т , а столбец свободных членов отделяют вертикальной линией от остальных столбцов, то есть,

Квадратная матрица А называется вырожденной , если ее определитель равен нулю. Если , то матрица А называется невырожденной .

Следует оговорить следующий момент.

Если с системой линейных алгебраических уравнений произвести следующие действия

• поменять местами два уравнения,
• умножить обе части какого-либо уравнения на произвольное и отличное от нуля действительное (или комплексное) число k ,
• к обеим частям какого-либо уравнения прибавить соответствующие части другого уравнения, умноженные на произвольное число k ,

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

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

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

Теперь можно переходить к описанию метода Гаусса.

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

Как бы мы поступили в школе, если бы получили задание найти решение системы уравнений .

Некоторые сделали бы так.

Заметим, что прибавив к левой части второго уравнения левую часть первого, а к правой части - правую, можно избавиться от неизвестных переменных x 2 и x 3 и сразу найти x 1 :

Подставляем найденное значение x 1 =1 в первое и третье уравнение системы:

Если умножить обе части третьего уравнения системы на -1 и прибавить их к соответствующим частям первого уравнения, то мы избавимся от неизвестной переменной x 3 и сможем найти x 2 :

Подставляем полученное значение x 2 =2 в третье уравнение и находим оставшуюся неизвестную переменную x 3 :

Другие поступили бы иначе.

Разрешим первое уравнение системы относительно неизвестной переменной x 1 и подставим полученное выражение во второе и третье уравнение системы, чтобы исключить из них эту переменную:

Теперь разрешим второе уравнение системы относительно x 2 и подставим полученный результат в третье уравнение, чтобы исключить из него неизвестную переменную x 2 :

Из третьего уравнения системы видно, что x 3 =3 . Из второго уравнения находим , а из первого уравнения получаем .

Знакомые способы решения, не правда ли?

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

Следует заметить, что когда мы выражаем x 1 через x 2 и x 3 в первом уравнении, а затем подставляем полученное выражение во второе и третье уравнения, то к такому же результату приводят следующие действия:

Действительно, такая процедура также позволяет исключить неизвестную переменную x 1 из второго и третьего уравнений системы:

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

Например, в СЛАУ в первом уравнении отсутствует неизвестная переменная x 1 (иными словами, коэффициент перед ней равен нулю). Поэтому мы не можем разрешить первое уравнение системы относительно x 1 , чтобы исключить эту неизвестную переменную из остальных уравнений. Выходом из этой ситуации является перестановка местами уравнений системы. Так как мы рассматриваем системы линейных уравнений, определители основных матриц которых отличны от нуля, то всегда существует уравнение, в котором присутствует нужная нам переменная, и мы это уравнение можем переставить на нужную нам позицию. Для нашего примера достаточно поменять местами первое и второе уравнения системы , дальше можно разрешить первое уравнение относительно x 1 и исключить ее из остальных уравнений системы (хотя во втором уравнении x 1 уже отсутствует).

Надеемся, что суть Вы уловили.

Опишем алгоритм метода Гаусса.

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

Будем считать, что , так как мы всегда можем этого добиться перестановкой местами уравнений системы. Исключим неизвестную переменную x 1 из всех уравнений системы, начиная со второго. Для этого ко второму уравнению системы прибавим первое, умноженное на , к третьему уравнению прибавим первое, умноженное на , и так далее, к n-ому уравнению прибавим первое, умноженное на . Система уравнений после таких преобразований примет вид

где , а .

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

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

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

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

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

Так продолжаем прямой ход метода Гаусса пока система не примет вид

С этого момента начинаем обратный ход метода Гаусса: вычисляем x n из последнего уравнения как , с помощью полученного значения x n находим x n-1 из предпоследнего уравнения, и так далее, находим x 1 из первого уравнения.

Разберем алгоритм на примере.

Пример.

методом Гаусса.

Решение.

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

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

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

Можно начинать обратный ход метода Гаусса.

Из последнего уравнения имеем ,
из третьего уравнения получаем ,
из второго ,
из первого .

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

Ответ:

А сейчас приведем решение этого же примера методом Гаусса в матричной форме записи.

Пример.

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

Решение.

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

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

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

Далее полученную матрицу преобразуем так, чтобы во втором столбце все элементы, начиная с третьего стали нулевыми. Это будет соответствовать исключению неизвестной переменной x 2 . Для этого к элементам третьей и четвертой строк прибавим соответствующие элементы первой строки матрицы, умноженные соответственно на и :

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

Следует отметить, что эта матрица соответствует системе линейных уравнений

которая была получена ранее после прямого хода.

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

стала диагональной, то есть, приняла вид

где - некоторые числа.

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

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

Теперь прибавим к элементам второй и первой строк соответствующие элементы третьей строки, умноженные на и на соответственно:

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

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

Ответ:

ОБРАТИТЕ ВНИМАНИЕ.

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

Пример.

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

Решение.

Отметим, что в этом примере неизвестные переменные имеют другое обозначение (не x 1 , x 2 , x 3 , а x, y, z ). Перейдем к обыкновенным дробям:

Исключим неизвестную x из второго и третьего уравнений системы:

В полученной системе во втором уравнении отсутствует неизвестная переменная y , а в третьем уравнении y присутствует, поэтому, переставим местами второе и третье уравнения:

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

Приступаем к обратному ходу.

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


из первого уравнения имеем

Ответ:

X = 10, y = 5, z = -20 .

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

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

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

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

Переходим к самому важному этапу.

Итак, допустим, что система линейных алгебраических уравнений после завершения прямого хода метода Гаусса приняла вид и ни одно уравнение не свелось к (в этом случае мы бы сделали вывод о несовместности системы). Возникает логичный вопрос: «Что делать дальше»?

Выпишем неизвестные переменные, которые стоят на первом месте всех уравнений полученной системы:

В нашем примере это x 1 , x 4 и x 5 . В левых частях уравнений системы оставляем только те слагаемые, которые содержат выписанные неизвестные переменные x 1 , x 4 и x 5 , остальные слагаемые переносим в правую часть уравнений с противоположным знаком:

Придадим неизвестным переменным, которые находятся в правых частях уравнений, произвольные значения , где - произвольные числа:

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

Из последнего уравнений системы имеем , из предпоследнего уравнения находим , из первого уравнения получаем

Решением системы уравнений является совокупность значений неизвестных переменных

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

Ответ:

где - произвольные числа.

Для закрепления материала подробно разберем решения еще нескольких примеров.

Пример.

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

Решение.

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

Теперь исключим y из третьего уравнения полученной системы уравнений:

Полученная СЛАУ равносильна системе .

Оставляем в левой части уравнений системы только слагаемые, содержащие неизвестные переменные x и y , а слагаемые с неизвестной переменной z переносим в правую часть: