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

 

Департамент общего и  профессионального образования Брянской области

ГБОУ СПО «Новозыбковский профессионально-педагогический колледж»

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

 

 

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

 

 

 

 

 

Дремин Анатолий Александрович

Специальность 230105

IV курс, 47 группа  

Научный руководитель:

Саросек Светлана Валерьевна

 

 

 

Новозыбков, 2012

 

Содержание

 

Введение

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

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

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

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

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

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

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

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

Для достижения поставленной цели необходимо реализовать следующие  задачи:

1. Подобрать литературу по теме исследования.
2. Описать основные понятия по теме исследования.
3. Описать основные методы решения систем линейных алгебраических уравнений.
4. Описать алгоритмы решения систем линейных алгебраических уравнений.

 

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

 

Система m линейных алгебраических уравнений с n неизвестными – это некоторая совокупность соотношений

,

в которой  – есть заданные изначально вещественные числа; – неизвестные величины. При этом, называют коэффициентами системы, – свободными членам.

Существует также матричный  способ записи системы уравнений [3]:

.

Здесь

 – матрица системы;

 – вектор-столбец неизвестных;

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

Расширенная матрица  системы состоит из матрицы системы  А и вектора-столбца свободных  членов:

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

.

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

Совместность системы  устанавливается при помощи теоремы Кронекера-Капелли [4], которая гласит: для того, чтобы система была совместна, необходимо и достаточно, чтобы ранг матрицы системы r_A был равен рангу расширенной матрицы системы .

Предположим, система  совместна. Обозначим ранг системы: , число уравнений: m и число неизвестных: n, тогда:

• Если r<m, базисный минор расположен в левом верхнем углу исходной матрицы А. Это значит, что первые r строк и столбцов расширенной матрицы являются линейно независимыми. Следовательно, последние уравнений системы можно отбросить, поскольку они могут быть линейно выражены через первые r. В таком случае, имеем систему, в которой ранг и число уравнений равны:

• Предположим r=n, тогда система уравнений имеет одно единственное решение
• Если r<n, то также считая, что базисный минор расположен в левом верхнем углу матрицы системы А, назовем переменные

 – базисными, а переменные

 – свободными.

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

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

• Совместные ( ):

определенные ( )

неопределенные ( )

• Несовместные ( )

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

 

Метод Гаусса

 

Метод Гаусса [2] – это метод, подходящий для исследования и решения любых систем линейных уравнений. Он состоит их трех основных этапов.

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

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

Расширенная матрица  системы приводится к ступенчатому виду:

,

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

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

.

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

 

Для обратного хода метода Гаусса можно использовать рекуррентные формулы:

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

Существует также модификация  метода Гаусса, называемая методом Жордана-Гаусса, которая применяется для решения квадратных систем линейных уравнений, нахождения координат вектора в заданном базисе, нахождения обратной матрицы, а так же, определения ранга матрицы. Алгоритм данного метода состоит в следующих шагах:

• Выбирается первый слева столбец матрицы, в котором имеется хотя бы одно значение, отличное от нуля.
• Если самое верхнее число в выбранном столбце – ноль, то вся первая строка матрицы меняется местами с другой строкой, где в данной колонке нет нуля.
• Все элементы первой строки делятся на верхний элемент выбранного столбца.
• Из оставшихся строк вычитается первая строка, умноженная на первый элемент соответствующей строки. Целью данного действия является получить в качестве первого элемента каждой строки (кроме первой) ноль.
• Затем такая же процедура проводится с матрицей, получившейся из исходной после вычёркивания первой строки и первого столбца.
• Эта процедура повторяется n–1 раз, после чего получается верхняя треугольная матрица
• Из предпоследней строки вычитается последняя строка, умноженная на соответствующий коэффициент, для того, чтобы в предпоследней строке осталась только единица на главной диагонали.
• Предыдущий шаг повторяется для всех последующих строк. В результате, получается единичная матрица и решение на месте свободного вектора.
• Для получения обратной матрицы необходимо применить все операции в том же порядке к единичной матрице.

Метод Крамера

 

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

, где 

,

,

Алгоритм использования  метода Крамера:

• Вычисляется определитель матрицы системы, выясняется, действительно ли он отличен от нуля.
• Находятся все определители
• С помощью формул Крамера вычисляются неизвестные переменные
• Производится проверка результатов: если подставить полученные неизвестные в исходные уравнения системы, последние должны обратиться в тождества. Кроме того, для проверки можно вычислить произведение матриц A∙X, и если в результате получится матрица, равная B, то решение верно. В противном случае, в вычислениях допущена ошибка.