 |
Алгоритм нахождения решения по методу Гаусса
|
|
|
|
Лабораторная работа 1
Тема: Решение СЛАУ по формулам Крамера и методом Гаусса.
Цель: оказание студентам помощи в овладении навыками решения задач, отражающих тематику данной лабораторной работы; научить студентов решать СЛАУ.
Теоретическое обоснование
Системы линейных алгебраических уравнений
Система 
линейных уравнений с 
переменными имеет вид:
(1)
где 
(
) – произвольные числа называющиеся коэффициентами при переменных, а 
– свободными членами уравнений.
Система (1) называется однородной, если все её свободные члены равны нулю, если хотя бы одно из чисел отлично от нуля, то система называется неоднородной.
Решением системы называется такая совокупность чисел 
, 
, …, 
, при подстановке которых данное уравнение системы обращается в верное равенство.
Система уравнений называется совместной, если она имеет хотя бы одно решение, и несовместной, если решений нет.
Совместная система называется определённой, если она имеет единственное решение, и неопределенной, если она имеет более одного решения.
Две системы уравнений называются равносильными или эквивалентными, если они имеют одно в тоже множество решения. Преобразование, применение которого превращает систему в новую систему, эквивалентную исходной, называется эквивалентным или равносильным преобразованием. Примерами эквивалентных преобразований могут служить следующие преобразования: перестановка местами двух уравнений системы, умножение обеих частей какого-либо уравнения системы на отличное от нуля число. С помощью элементарных преобразований системы уравнений получается система равносильная данной.
Теорема (Кронекера - Капелли):
|
|
|
Для того чтобы система (1) линейных алгебраических уравнений относительно неизвестных была совместна (имела решение), необходимо и достаточно, чтобы ранг основной матрицы (А) системы и ранг
расширенной матрицы (А, В) системы (1) были равны, т. е. 
.
Рангом матрицы 
(обозначается 
или 
) называется наибольший порядок порожденной ею определителей, отличных от нуля.
Методы решения СЛАУ
1. Матричный метод.
Пусть дана система уравнений (1) записанная в виде матричного уравнения
(2)
Если основная матрица невырожденная, т.е. 
, тогда для матрицы 
существует обратная матрица 
. Умножив матричное уравнение (2) слева на , получим:
Откуда
(3)
Следовательно, (3) – матричное решение уравнения (2).
Обратная матрица для матрицы определяется по формуле:
или 
где 
– определитель матрицы ; 
– присоединенная матрица, составленная из алгебраических дополнений; 
– алгебраические дополнения элементов матрицы .
2. Метод Крамера.
Рассмотрим систему из уравнений с неизвестными:
(4)
Определитель -го порядка 
, составленный из коэффициентов при неизвестных, называется определителем системы. В зависимости от определителя различают следующие случаи:
1) если определитель системы отличен от нуля, то система имеет единственное решение, которое может быть определено по формулам Крамера
, 
, …, 
,
где определитель -го порядка 
(
) получается из 
путем замены 
-го столбца свободными членами 
, 
, …, 
.
2) Если 
, но хотя бы один из 
(), то система несовместна.
3) Если и (), то система либо несовместна, либо имеет бесчисленное множество решений.
3. Метод Гаусса.
Эффективным методом решения и исследования систем линейных уравнений является метод исключения неизвестных, называемый методом Гаусса. Преобразование системы по методу Гаусса состоит из нескольких шагов, на каждом из которых производится исключение одного неизвестного. Для каждого такого шага необходимо указать ведущее неизвестное и ведущее уравнение, а также определить из каких уравнений исключается ведущее неизвестное.
|
|
|
В качестве первого ведущего элемента (ведущего элемента 1-го шага можно выбрать любой отличный от нуля коэффициент данной системы уравнений). Произведя такой выбор, исключим 1-ое ведущее неизвестное из всех уравнений системы, используя элементарные преобразования:
1) прибавление к обеим частям одного уравнения системы соответствующих частей другого уравнения той же системы, умноженных на некоторое число;
2) перестановка местами уравнений в системе;
3) удаление из системы уравнений вида 0=0.
Совокупность уравнений системы, кроме 1-го ведущего, назовём первой подсистемой. Первое ведущее уравнение дальнейшим преобразованиям подвергать не будем. В качестве второго ведущего элемента (ведущего элемента 2-го шага) можем выбрать любой отличный от нуля коэффициент в 1-ой подсистеме. Произведя такой выбор, исключим 2-ое ведущее неизвестное из всех уравнений 1-ой подсистемы, кроме 2-го ведущего.
Совокупность уравнений системы, кроме 1-го и 2-го ведущих, назовём 2-ой подсистемой. Второе ведущее уравнение также как и 1-ое, дальнейшим преобразованиям подвергать не будем.
В качестве третьего ведущего элемента (ведущего элемента 3-го шага) можно выбрать любой отличный от нуля коэффициент во 2-ой подсистеме и т.д.
Если в процессе хотя бы одно уравнение вида 
(5) (
), то исследование закончено – система несовместна. Если же появится уравнение вида 
(6), то его просто удалим. Если в процессе не появятся уравнения (5) и (6), то данная система совместна.
Процесс её преобразования закончится тогда, когда на очередном шаге мы получим подсистему, состоящую только из 1-го уравнения, или подсистема вообще не будет иметь вид (7).
На каждом шаге преобразования системы линейных, уравнений по методу Гаусса мы имеем большую свободу в выборе ведущего элемента (он не может только равняться нулю). Но как бы мы эти элементы не выбирали, число уравнений в окончательно полученной системе будет одним и тем же, оно равно максимальному числу независимых уравнений в исходной системе это число и является рангом системы (
).
Приведение системы к виду (7) называется прямым ходом, отыскание решения системы (7) – обратным ходом метода Гаусса.
|
|
|
(7)
или
В случае 
система имеет единственное решение, которое легко найти. Если же 
, то из системы (7) находим значения неизвестных 
, 
, …, 
через неизвестные 
,…, 
.
Придавая неизвестным ,…, произвольные значения будем получать решение системы.
При этом неизвестные 
,…, 
называют свободными, а неизвестные , , …, – базисными. Число базисных неизвестных равно рангу системы 
, а число свободных неизвестных 
( – число неизвестных).
Базисные неизвестные единственным образом выражаются через свободные неизвестные.
Если свободным неизвестным приданы конкретные числовые значения и через них выражены базисные неизвестные, то полученное решение называется частным решением.
Если свободные неизвестные выражены через параметры, то получается решение, которое называется общим решением.
Все бесконечное множество решений системы можно получить, придавая свободным неизвестным любые числовые значения и находя соответствующие значения базисных неизвестных.
Если всем свободным неизвестным приданы нулевые значения, то полученное решение называется базисным.
Метод Гаусса – матричный способ.
Оформляют решение по методу Гаусса так: записывают расширенную матрицу системы. Затем над строками производят элементарные преобразования, приводя данную матрицу к диагональному виду.
Алгоритм нахождения решения по методу Гаусса
1) Полагая, что в расширенной матрице системы коэффициент 
(если это не так, то следует на первое место поставить строку с отличным от нуля коэффициентом при ), преобразуем матрицу следующим образом: первую строку оставляем без изменения, а из всех остальных строк исключаем неизвестную с помощью эквивалентных преобразований.
2) В полученной матрице, считая, что 
(что всегда можно получить, переставив строки), оставляем без изменений первые две строки, а из остальных строк расширенной матрицы, используя вторую строку, с помощью элементарных преобразований исключаем неизвестную .
|
|
|
3) Во вновь полученной матрице, при условии 
оставляем без изменений первые три строки, а из всех остальных с помощью третьей строки элементарными преобразованиями исключаем неизвестную 
.
Этот процесс продолжается до тех пор, пока не реализуется один из трех возможных случаев:
1) если в результате приходим к ступенчатой матрице соответствующей системе, одно из уравнений которой имеет нулевые коэффициенты при всех неизвестных и отличный от нуля свободный член, то исходная система несовместна;
2) если в результате преобразований получаем систему с матрицей коэффициентов треугольного вида, то система совместна и является определенной;
3) если получается система с трапецеидальной матрицей коэффициентов и при этом не выполняется условие пункта 1), то система совместна и неопределенна.
Если матрицу размера 
можно разделить вертикальной чертой на две матрицы: стоящую слева треугольную матрицу размера и стоящую справа прямоугольную матрицу, то матрицу назовем трапециевидной или трапецеидальной.
Матрица 
– трапециевидная матрица.
|
|
|
