Систему уравнений (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х этапов:
1. Предполагаем, что . Тогда первое уравнение системы делим на коэффициент , в результате получаем уравнение . Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент . В результате система преобразуются к виду: 2. В предположении, что , делим второе уравнение на коэффициент и исключаем неизвестное из всех последующих уравнений и т.д. 3. Получаем систему уравнений с треугольной матрицей:- Обратный ход Непосредственное определение неизвестных
Анализ метода
Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные (матрица и правая часть уравнения - ) заданы точно и вычисление ведется без округлений. Для получения решения требуется умножений и делений, то есть порядка операций.
Условия, при которых метод выдает точное решение, на практике не выполнимы - неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой рассмотрим возмущенную систему:
Пусть введена некоторая норма . - называется числом обусловленности матрицы .
Возможны 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 |
Продолжаем рассматривать системы линейных уравнений. Этот урок является третьим по теме. Если вы смутно представляете, что такое система линейных уравнений вообще, чувствуете себя чайником, то рекомендую начать с азов на странице Далее полезно изучить урок .
Метод Гаусса – это просто! Почему? Известный немецкий математик Иоганн Карл Фридрих Гаусс еще при жизни получил признание величайшего математика всех времен, гения и даже прозвище «короля математики». А всё гениальное, как известно – просто! Кстати, на деньги попадают не только лохи, но еще и гении – портрет Гаусса красовался на купюре в 10 дойчмарок (до введения евро), и до сих пор Гаусс загадочно улыбается немцам с обычных почтовых марок.
Метод Гаусса прост тем, что для его освоения ДОСТАТОЧНО ЗНАНИЙ ПЯТИКЛАССНИКА.Необходимо уметь складывать и умножать! Не случайно метод последовательного исключения неизвестных преподаватели часто рассматривают на школьных математических факультативах. Парадокс, но у студентов метод Гаусса вызывает наибольшие сложности. Ничего удивительного – всё дело в методике, и я постараюсь в доступной форме рассказать об алгоритме метода.
Сначала немного систематизируем знания о системах линейных уравнений. Система линейных уравнений может:
1) Иметь единственное решение. 2) Иметь бесконечно много решений. 3) Не иметь решений (быть несовместной ).
Метод Гаусса – наиболее мощный и универсальный инструмент для нахождения решениялюбой системы линейных уравнений. Как мы помним, правило Крамера и матричный метод непригодны в тех случаях, когда система имеет бесконечно много решений или несовместна. А метод последовательного исключения неизвестных в любом случае приведет нас к ответу! На данном уроке мы опять рассмотрим метод Гаусса для случая №1 (единственное решение системы), под ситуации пунктов №№2-3 отведена статья. Замечу, что сам алгоритм метода во всех трёх случаях работает одинаково.
Вернемся к простейшей системе с урока Как решить систему линейных уравнений? и решим ее методом Гаусса.
На первом этапе нужно записать расширенную матрицу системы : . По какому принципу записаны коэффициенты, думаю, всем видно. Вертикальная черта внутри матрицы не несёт никакого математического смысла – это просто отчеркивание для удобства оформления.
Справка : рекомендую запомнить термины линейной алгебры. Матрица системы – это матрица, составленная только из коэффициентов при неизвестных, в данном примере матрица системы: . Расширенная матрица системы – это та же матрица системы плюс столбец свободных членов, в данном случае: . Любую из матриц можно для краткости называть просто матрицей.
После того, как расширенная матрица системы записана, с ней необходимо выполнить некоторые действия, которые также называются элементарными преобразованиями .
Существуют следующие элементарные преобразования:
1) Строки
матрицы можно
переставлять
местами.
Например, в рассматриваемой матрице
можно безболезненно переставить первую
и вторую строки: 
2)
Если в матрице есть (или появились)
пропорциональные (как частный случай
– одинаковые) строки, то следует удалить
из
матрицы все эти строки кроме одной.
Рассмотрим, например матрицу 
.
В данной матрице последние три строки
пропорциональны, поэтому достаточно
оставить только одну из них: 
.
3) Если в матрице в ходе преобразований появилась нулевая строка, то ее также следуетудалить . Рисовать не буду, понятно, нулевая строка – это строка, в которой одни нули .
4)
Строку матрицы можно умножить
(разделить)
на
любое число, отличное
от нуля
.
Рассмотрим, например, матрицу .
Здесь целесообразно первую строку
разделить на –3, а вторую строку –
умножить на 2: 
.
Данное действие очень полезно, поскольку
упрощает дальнейшие преобразования
матрицы.
5)
Это преобразование вызывает наибольшие
затруднения, но на самом деле ничего
сложного тоже нет. К строке матрицы
можно прибавить
другую строку, умноженную на число
,
отличное от нуля. Рассмотрим нашу матрицу
из практического примера: .
Сначала я распишу преобразование очень
подробно. Умножаем первую строку на
–2: 
,
и ко
второй строке прибавляем первую строку
умноженную на –2
: 
.
Теперь первую строку можно разделить
«обратно» на –2: .
Как видите, строка, которую ПРИБАВЛЯЛИ
– не
изменилась
. Всегда
меняется
строка, К КОТОРОЙ ПРИБАВЛЯЮТ
.
На
практике так подробно, конечно, не
расписывают, а пишут короче:
Еще
раз: ко второй строке прибавили
первую строку, умноженную на –2
.
Умножают строку обычно устно или на
черновике, при этом мысленный ход
расчётов примерно такой:
«Переписываю
матрицу и переписываю первую строку: 
»
«Сначала
первый столбец. Внизу мне нужно получить
ноль. Поэтому единицу вверху умножаю
на –2: ,
и ко второй строке прибавляю первую: 2
+ (–2) = 0. Записываю результат во вторую
строку: 
»
«Теперь
второй столбец. Вверху –1 умножаю на
–2: .
Ко второй строке прибавляю первую: 1 + 2
= 3. Записываю результат во вторую
строку: 
»
«И
третий столбец. Вверху –5 умножаю на
–2: .
Ко второй строке прибавляю первую: –7
+ 10 = 3. Записываю результат во вторую
строку: 
»
Пожалуйста, тщательно осмыслите этот пример и разберитесь в последовательном алгоритме вычислений, если вы это поняли, то метод Гаусса практически «в кармане». Но, конечно, над этим преобразованием мы еще поработаем.
Элементарные преобразования не меняют решение системы уравнений
! ВНИМАНИЕ : рассмотренные манипуляции нельзя использовать , если Вам предложено задание, где матрицы даны «сами по себе». Например, при «классических» действиях с матрицами что-то переставлять внутри матриц ни в коем случае нельзя! Вернемся к нашей системе . Она практически разобрана по косточкам.
Запишем расширенную матрицу системы и с помощью элементарных преобразований приведем ее к ступенчатому виду :
(1) Ко второй строке прибавили первую строку, умноженную на –2. И снова: почему первую строку умножаем именно на –2? Для того чтобы внизу получить ноль, а значит, избавиться от одной переменной во второй строке.
(2) Делим вторую строку на 3.
Цель
элементарных преобразований
–
привести
матрицу к ступенчатому виду: 
.
В оформлении задания прямо так и
отчеркивают простым карандашом
«лестницу», а также обводят кружочками
числа, которые располагаются на
«ступеньках». Сам термин «ступенчатый
вид» не вполне теоретический, в научной
и учебной литературе он часто
называется трапециевидный
вид
или треугольный
вид
.
В результате элементарных преобразований получена эквивалентная исходной система уравнений:
Теперь систему нужно «раскрутить» в обратном направлении – снизу вверх, этот процесс называется обратным ходом метода Гаусса .
В нижнем уравнении у нас уже готовый результат: .
Рассмотрим первое уравнение системы и подставим в него уже известное значение «игрек»:
Рассмотрим наиболее распространенную ситуацию, когда методом Гаусса требуется решить систему трёх линейных уравнений с тремя неизвестными.
Пример 1
Решить
методом Гаусса систему уравнений:
Запишем
расширенную матрицу системы:
Сейчас
я сразу нарисую результат, к которому
мы придём в ходе решения:
И
повторюсь, наша цель – с помощью
элементарных преобразований привести
матрицу к ступенчатому виду. С чего
начать действия?
Сначала
смотрим на левое верхнее число:
Почти
всегда здесь должна находиться единица
.
Вообще говоря, устроит и –1 (а иногда и
другие числа), но как-то так традиционно
сложилось, что туда обычно помещают
единицу. Как организовать единицу?
Смотрим на первый столбец – готовая
единица у нас есть! Преобразование
первое: меняем местами первую и третью
строки:
Теперь первая строка у нас останется неизменной до конца решения . Уже легче.
Единица
в левом верхнем углу организована.
Теперь нужно получить нули вот на этих
местах:
Нули
получаем как раз с помощью «трудного»
преобразования. Сначала разбираемся
со второй строкой (2, –1, 3, 13). Что нужно
сделать, чтобы на первой позиции получить
ноль? Нужно ко
второй строке прибавить первую строку,
умноженную на –2
.
Мысленно или на черновике умножаем
первую строку на –2: (–2, –4, 2, –18). И
последовательно проводим (опять же
мысленно или на черновике) сложение, ко
второй строке прибавляем первую строку,
уже умноженную на –2
:
Результат
записываем во вторую строку:
Аналогично
разбираемся с третьей строкой (3, 2, –5,
–1). Чтобы получить на первой позиции
ноль, нужно к
третьей строке прибавить первую строку,
умноженную на –3
.
Мысленно или на черновике умножаем
первую строку на –3: (–3, –6, 3, –27). И к
третьей строке прибавляем первую строку,
умноженную на –3
:
Результат записываем в третью строку:
На
практике эти действия обычно выполняются
устно и записываются в один шаг:
Не
нужно считать всё сразу и одновременно
.
Порядок вычислений и «вписывания»
результатов последователен
и
обычно такой: сначала переписываем
первую строку, и пыхтим себе потихонечку
– ПОСЛЕДОВАТЕЛЬНО иВНИМАТЕЛЬНО
:
А
мысленный ход самих расчётов я уже
рассмотрел выше.
В данном примере это сделать легко, вторую строку делим на –5 (поскольку там все числа делятся на 5 без остатка). Заодно делим третью строку на –2, ведь чем меньше числа, тем проще решение:
На
заключительном этапе элементарных
преобразований нужно получить еще один
ноль здесь:
Для
этого к
третьей строке прибавляем вторую строку,
умноженную на –2
:
Попробуйте
разобрать это действие самостоятельно
– мысленно умножьте вторую строку на
–2 и проведите сложение.
Последнее выполненное действие – причёска результата, делим третью строку на 3.
В
результате элементарных преобразований
получена эквивалентная исходной система
линейных уравнений:
Круто.
Теперь в действие вступает обратный ход метода Гаусса. Уравнения «раскручиваются» снизу вверх.
В третьем уравнении у нас уже готовый результат:
Смотрим на второе уравнение: . Значение «зет» уже известно, таким образом:
И, наконец, первое уравнение: . «Игрек» и «зет» известны, дело за малым:
Ответ
: 
Как уже неоднократно отмечалось, для любой системы уравнений можно и нужно сделать проверку найденного решения, благо, это несложно и быстро.
Пример 2
Это пример для самостоятельного решения, образец чистового оформления и ответ в конце урока.
Следует отметить, что ваш ход решения может не совпасть с моим ходом решения, и это – особенность метода Гаусса . Но вот ответы обязательно должны получиться одинаковыми!
Пример 3
Решить
систему линейных уравнений методом
Гаусса
Смотрим на левую верхнюю «ступеньку». Там у нас должна быть единица. Проблема состоит в том, что в первом столбце единиц нет вообще, поэтому перестановкой строк ничего не решить. В таких случаях единицу нужно организовать с помощью элементарного преобразования. Обычно это можно сделать несколькими способами. Я поступил так: (1) К первой строке прибавляем вторую строку, умноженную на –1 . То есть, мысленно умножили вторую строку на –1 и выполнили сложение первой и второй строки, при этом вторая строка у нас не изменилась.
Теперь слева вверху «минус один», что нас вполне устроит. Кто хочет получить +1, может выполнить дополнительное телодвижение: умножить первую строку на –1 (сменить у неё знак).
(2) Ко второй строке прибавили первую строку, умноженную на 5. К третьей строке прибавили первую строку, умноженную на 3.
(3) Первую строку умножили на –1, в принципе, это для красоты. У третьей строки также сменили знак и переставили её на второе место, таким образом, на второй «ступеньке у нас появилась нужная единица.
(4) К третьей строке прибавили вторую строку, умноженную на 2.
(5) Третью строку разделили на 3.
Скверным
признаком, который свидетельствует об
ошибке в вычислениях (реже – об опечатке),
является «плохая» нижняя строка. То
есть, если бы у нас внизу получилось
что-нибудь вроде ,
и, соответственно, 
,
то с большой долей вероятности можно
утверждать, что допущена ошибка в ходе
элементарных преобразований.
Заряжаем обратный ход, в оформлении примеров часто не переписывают саму систему, а уравнения «берут прямо из приведенной матрицы». Обратный ход, напоминаю, работает, снизу вверх. Да тут подарок получился:
Ответ
: 
.
Пример 4
Решить
систему линейных уравнений методом
Гаусса
Это пример для самостоятельного решения, он несколько сложнее. Ничего страшного, если кто-нибудь запутается. Полное решение и образец оформления в конце урока. Ваше решение может отличаться от моего решения.
В
последней части рассмотрим некоторые
особенности алгоритма Гаусса.
Первая
особенность состоит в том, что иногда
в уравнениях системы отсутствуют
некоторые переменные, например:
Как
правильно записать расширенную матрицу
системы? Об этом моменте я уже рассказывал
на уроке Правило
Крамера. Матричный метод
.
В расширенной матрице системы на месте
отсутствующих переменных ставим
нули:
Кстати,
это довольно легкий пример, поскольку
в первом столбце уже есть один ноль, и
предстоит выполнить меньше элементарных
преобразований.
Вторая
особенность состоит вот в чём. Во всех
рассмотренных примерах на «ступеньки»
мы помещали либо –1, либо +1. Могут ли там
быть другие числа? В ряде случаев могут.
Рассмотрим систему: 
.
Здесь на левой верхней «ступеньке» у нас двойка. Но замечаем тот факт, что все числа в первом столбце делятся на 2 без остатка – и другая двойка и шестерка. И двойка слева вверху нас устроит! На первом шаге нужно выполнить следующие преобразования: ко второй строке прибавить первую строку, умноженную на –1; к третьей строке прибавить первую строку, умноженную на –3. Таким образом, мы получим нужные нули в первом столбце.
Или
еще такой условный пример: 
.
Здесь тройка на второй «ступеньке» тоже
нас устраивает, поскольку 12 (место, где
нам нужно получить ноль) делится на 3
без остатка. Необходимо провести
следующее преобразование: к третьей
строке прибавить вторую строку, умноженную
на –4, в результате чего и будет получен
нужный нам ноль.
Метод Гаусса универсален, но есть одно своеобразие. Уверенно научиться решать системы другими методами (методом Крамера, матричным методом) можно буквально с первого раза – там очень жесткий алгоритм. Но вот чтобы уверенно себя чувствовать в методе Гаусса, следует «набить руку», и прорешать хотя бы 5-10 десять систем. Поэтому поначалу возможны путаница, ошибки в вычислениях, и в этом нет ничего необычного или трагического.
Дождливая осенняя погода за окном.... Поэтому для всех желающих более сложный пример для самостоятельного решения:
Пример 5
Решить
методом Гаусса систему 4-х линейных
уравнений с четырьмя неизвестными.
Такое задание на практике встречается не так уж и редко. Думаю, даже чайнику, который обстоятельно изучил эту страницу, интуитивно понятен алгоритм решения такой системы. Принципиально всё так же – просто действий больше.
Случаи, когда система не имеет решений (несовместна) или имеет бесконечно много решений, рассмотрены на уроке Несовместные системы и системы с общим решением . Там же можно закрепить рассмотренный алгоритм метода Гаусса.
Желаю успехов!
Решения и ответы:
Пример
2:
Решение
:
Запишем
расширенную матрицу системы и с помощью
элементарных преобразований приведем
ее к ступенчатому виду.
Выполненные
элементарные преобразования:
(1)
Ко второй строке прибавили первую
строку, умноженную на –2. К третьей
строке прибавили первую строку, умноженную
на –1.
Внимание!
Здесь
может возникнуть соблазн из третьей
строки вычесть первую, крайне не
рекомендую вычитать – сильно повышается
риск ошибки. Только складываем!
(2)
У второй строки сменили знак (умножили
на –1). Вторую и третью строки поменяли
местами.
Обратите
внимание
,
что на «ступеньках» нас устраивает не
только единица, но еще и –1, что даже
удобнее.
(3)
К третьей строке прибавили вторую
строку, умноженную на 5.
(4)
У второй строки сменили знак (умножили
на –1). Третью строку разделили на 14.
Обратный ход:
Ответ
:
.
Пример
4:
Решение
:
Запишем
расширенную матрицу системы и с помощью
элементарных преобразований приведем
ее к ступенчатому виду:
Выполненные преобразования: (1) К первой строке прибавили вторую. Таким образом, организована нужная единица на левой верхней «ступеньке». (2) Ко второй строке прибавили первую строку, умноженную на 7. К третьей строке прибавили первую строку, умноженную на 6.
Со второй «ступенькой» всё хуже , «кандидаты» на неё – числа 17 и 23, а нам нужна либо единичка, либо –1. Преобразования (3) и (4) будут направлены на получение нужной единицы (3) К третьей строке прибавили вторую, умноженную на –1. (4) Ко второй строке прибавили третью, умноженную на –3. Нужная вещь на второй ступеньке получена . (5) К третьей строке прибавили вторую, умноженную на 6. (6) Вторую строку умножили на –1, третью строку разделили на -83.
Обратный ход:
Ответ :
Пример
5:
Решение
:
Запишем
матрицу системы и с помощью элементарных
преобразований приведем ее к ступенчатому
виду:
Выполненные преобразования: (1) Первую и вторую строки поменяли местами. (2) Ко второй строке прибавили первую строку, умноженную на –2. К третьей строке прибавили первую строку, умноженную на –2. К четвертой строке прибавили первую строку, умноженную на –3. (3) К третьей строке прибавили вторую, умноженную на 4. К четвертой строке прибавили вторую, умноженную на –1. (4) У второй строки сменили знак. Четвертую строку разделили на 3 и поместили вместо третьей строки. (5) К четвертой строке прибавили третью строку, умноженную на –5.
Обратный
ход:
Ответ :
При решении системы уравнений
простейшим вариантом метода Гаусса имеют место большие погрешности. Причина заключается в появлении больших коэффициентов, при округлении которых получается большая абсолютная погрешность 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 различные значения, можно описать все возможные решения системы. à