Метод гаусса примеры с выбором главного элемента

Московский Государственный Технически Университет

«МАМИ»

Лабораторная работа №3 по курсу «Вычислительная Математика»

«РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»

3. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Справочная информация

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

,

записываемых в матричной форме в виде

,

,

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

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

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

.

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

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

,

которое на этом шаге считается ведущим, нормируется – делится на значение диагонального элемента a₁₁

,

.

Если в исходной системе a₁₁= 0, то в качестве первого уравнения следует взять любое другое с ненулевым первым коэффициентом, поменяв их местами. Полученное уравнение умножается на первый коэффициент второго уравнения a₂₁ и вычитается из него. В результате во втором уравнении пропадает слагаемое a₂₁x₁, содержащее первое неизвестное x₁. Такие же операции проводятся со всеми последующими уравнениями. В результате система уравнений принимает вид

.

Далее процесс повторяется. За ведущее берется второе уравнение и исключается неизвестное x₂ из всех уравнений, начиная с третьего

.

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

.

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

.

Выполняя аналогичные подстановки найденных неизвестных в вышестоящие уравнения, удается определить все компоненты решения x_n–2. x₂, x₁.

Метод Гаусса даёт точное решение, если все исходные данные точны и все вычисления производятся точно. На практике, при выполнении вычислений, неизбежно проводятся округления. Ошибка округлений вносит погрешность в решение метода Гаусса. Таким образом, при операциях с округленными десятичными числами метод Гаусса даёт не точное решение x_т системы линейных алгебраических уравнений, а некоторое приближённое решение , где

, .

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

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

или или

,

где двойные модульные скобки обозначают норму вектора.

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

,

а затем посредством повторного решения системы уравнений

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

или или ,

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

.

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

Метод Гаусса с выбором главного элемента

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

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

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

Поставленная задача будет решаться методом Гаусса с выбором главного элемента по столбцу.

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

.

б. Нормировка первого уравнения

.

в. Исключение элементов первого столбца

.

г. Выбор главного элемента среди элементов второго столбца второго и третьего уравнений

.

д. Нормировка второго уравнения

.

е. Исключение элементов второго столбца

.

ё. Нормировка последнего уравнения

.

,

.

В итоге получено решение системы уравнений

.

3. Погрешность найденного решения.

а. Пересчёт вектора правых частей системы

б. Формирование системы уравнений, определяющей погрешности решения

,

в. Решение системы относительно погрешностей оно выполняется аналогично пунктам 1 и 2. Прямой ход (пункт 1) даёт следующую систему с верхней треугольной матрицей

,

а обратный ход позволяет получить решение

.

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

,

,

.

Реализация описанного метода без нахождения погрешности решения в рамках программы Excel приведена на рис.1.

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

Каждый из рассмотренных методов имеет свои достоинства и недостатки. В частности, метод Гаусса позволяет получить решение за конечное число шагов. Для этого требуется выполнить n(n 2 + 3n – 1)/3 операций умножения и деления и n(n – 1)(2n + 5)/6 операций сложения и вычитания, количество которых при больших порядках системы (n > 100) можно принять равным n 3 /3 в обоих случаях. Однако его методические ошибки, связанные с размером разрядной сетки вычислений, резко нарастают с увеличением порядка системы и не позволяют применять его для систем высоких порядков без использования специальных приёмов.

Итерационные методы позволяют получать решение систем бóльшего порядка. Для выполнения каждой итерации с их помощью необходимо выполнить n(n + 1) операций умножения и деления и столько же операций сложения и вычитания. При больших порядках системы уравнений (n > 100) их количество можно принять равным n 2 . Из сравнения трудоёмкости итерационных методов и метода Гаусса следует оценка, которой можно руководствоваться при окончательном выборе метода решения системы при необходимости его многократного нахождения. Если количество итераций, требуемое для получения решения системы итерационными методами, не превышает n/3, то выгоднее применять их, а не методы типа Гаусса. Однако здесь следует помнить, что итерационные методы требуют, чтобы матрица системы обладала определёнными свойствами, обеспечивающими их сходимость. Необходимо также отметить, что выполнение этих требований часто не гарантирует высокой скорости их сходимости.

МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.

1. Основная идея метода. Может оказаться, что система

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

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

Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений

Предположим, что . Тогда на первом шаге будем исключать переменное . Такой прием эквивалентен тому, что си­стема (2) переписывается в виде

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

Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что . Перепишем систему (2) в виде

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

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

2. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде

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

ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квад­ратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.

ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок на­зывается матрица, полученная из единичной матрицы перестановкой к-й и l-й строк.

Например, элементарными матрицами перестановок третьего по­рядка являются матрицы

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

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

2) Для любой квадратной матрицы А матрица отличается от А перестановкой к-й и l-é ñòðîê.

3) Для любой квадратной матрицы А матрица отличается от А перестановкой к-го и l-го столбцов.

Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка:

Система имеет вид (1), где

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

Систему (6) можно записать в виде

т.е. она получается из системы (4) путем умножения на матрицу

Далее, к системе (6) надо применить первый шаг обычного метода ис­ключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу

В результате от системы (7) перейдем к эквивалентной системе

или в развернутом виде

Из последних двух уравнений системы (9) надо теперь исключить перемен­ное . Поскольку максимальным элементом первого столбца уко­роченной системы

является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе

которую можно записать в матричном виде как

Таким образом система (12) получена из (8) применением элемен-тар­ной матрицы перестановок

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

В результате получим систему

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

что эквивалентно умножению (13) на элементарную нижнюю треугольную мат­рицу

Таким образом, для рассмотренного примера процесс исключения Гаусса с вы­бором главного элемента по столбцу записывается в

По построению матрица

является верхней треугольной матрицей с единичной главной диаго­налью.

Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матри­цами могут присутствовать элементарные матрицы перестановок .

Покажем еще, что из (16) следует разложение

где L —нижняя треугольная матрица, имеющая обратную, P – матрица перестановок.

Для этого найдем матрицу

По свойству 2) матрица получается из матрицы переста­новкой второй и третьей строк,

Матрица согласно свойству 3) получается из перестановкой второго и третьего столбцов

т.е. -нижняя треугольная матрица, имеющая обратную.

Из (18), учитывая равенство , получим

Отсюда и из (16) видно, что

где обозначено . Поскольку Р-матрица перестановок и L-нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к мат­рице РА, т.е. к системе, полученной из исходной системы перестанов­кой некоторых уравнений.

3. Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1).

А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде

где — элементарные матрицы перестановок такие, что

и -элементарные нижние треугольные матрицы.

Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к си­стеме

где Р – некоторая матрица перестановок.

Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.

ТЕОРЕМА 1. Если то существует матрица перестано-

вок Р такая, что матрица РА имеет отличные от нуля угловые ми-

Доказательство в п.4.

СЛЕДСТВИЕ. Если то существует матрица престана-

вок Р такая, что справедливо разложение

где L— нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента.

4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А.

Если то утверждение теоремы выполняется при Р=Е, где Е – единичная матрица второго порядка. Если , то , т.к. При этом у матрицы

все угловые миноры отличны от нуля.

Пусть утверждение теоремы верно для любых квадратных матриц порядка m-1. Покажем, что оно верно и .для матриц порядка m. Разобьем матрицу А порядка m на блоки

Достаточно рассмотреть два случая : и . В первом случае по предположению индукции существует матрица перестановок порядка m-1 такая, что имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок

причем . Тем самым все угловые миноры матрицы РА отличны от нуля.

Рассмотрим второй случай, когда . Т.к. , найдется хотя бы один отличный от нуля минор порядка m-1 матрицы А, полученный вычеркиванием последнего столбца и какой-либо строки. Пусть, например,

Переставляя в матрице А строки с номерами l и m, получим матрицу , у которой угловой минор порядка m-1 имеет вид

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

Материал из MachineLearning.

Содержание

Постановка задачи

Дана система линейных алгебраических уравнений (СЛАУ), состоящая из уравнений с неизвестными :

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

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

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

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

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

• Прямой ход Система (2) приводится к треугольному виду

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Способ решения
Номер столбца в
Номер итерации
x1
x2
x3
x4
x5
x6
x7
Абс. погрешность
Отн. погрешность
Невязка

Обычный метод
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	2
—	—

1 1 1 1 1 1 1 1 1 1 1

Программа, реализующая метод на C++

Gauss_Elimination.zip [30КБ] — В архиве содержится исходный код, exe-файл и пример файла с входными данными

Рекомендации пользователю

• Метод Гаусса удобно применять для систем маленькой и средней размерности (до порядка ). Для больших же размерностей или разреженных матриц более эффективными представляются итерационные методы.

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

• Итерационное улучшение результата стоит провести 2-3 раза, если погрешность уменьшается очень медленно — возможно, матрица плохо обусловлена, тогда метод в любом случае даст не лучшие результаты — лучше попробовать применить итерационные методы.

• Важно, чтобы данные считывались из файла правильно.

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

• Есть возможность менять точность вычислений (float и double), но в исходниках.