Методы исключения Гаусса
Материал из MachineLearning.
Содержание |
Постановка задачи
Дана система линейных алгебраических уравнений (СЛАУ), состоящая из уравнений с
неизвестными :
Предполагается, что существует единственное решение системы, то есть .
В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности.
Описание метода
Процесс решения системы линейных уравнений
по методу Гаусса состоит из 2х этапов:
- Прямой ход
- Система (2) приводится к треугольному виду
- 1. Предполагаем, что
. Тогда первое уравнение системы (2) делим на коэффициент
, в результате получаем уравнение
- 1. Предполагаем, что
- Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент
. В результате система преобразуются к виду:
- Затем из каждого из оставшихся уравнений вычитается первое, умноженное на соответствующий коэффициент
- 2. В предположении, что
, делим второе уравнение на коэффициент
и исключаем неизвестное
из всех последующих уравнений и т.д.
- 3. Получаем систему уравнений с треугольной матрицей:
- 2. В предположении, что
- Обратный ход
- Непосредственное определение неизвестных
- 1. Из
го уравнения системы (3) определяем
- 2. Из
го - определяем
и т.д.
- 1. Из
Анализ метода
Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные ( матрица и правая часть уравнения -
) заданы точно и вычисление ведется без округлений.
Для получения решения требуется
умножений и делений, то есть порядка
операций.
Условия, при которых метод выдает точное решение, на практике не выполнимы - неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой (1) рассмотрим возмущенную систему:
Пусть введена некоторая норма .
- называется числом обусловленности матрицы
.
Возможны 3 случая:
1) :
2) :
3) :
Число обусловленности матрицы всегда
. Если оно велико (
) , то говорят, что матрица
плохо обусловлена. В этом случае малые возмущения правых частей системы (1), вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления, существенно влияют на решение системы. Грубо говоря, если погрешность правых частей
, то погрешность решения будет
.
Проиллюстрируем полученные результаты на следующем числовом примере: Дана система
Она имеет решение .
Теперь рассмотрим возмущенную систему:
Решением такой системы будет вектор .
При совсем малом возмущении правой части получили несоизмеримо большое возмущение решения.
Объяснить такую "ненадежность" решения можно тем, что матрица почти вырожденная: прямые, соответствующие двум уравнениям, почти совпадают, что видно на графике:
Такой результат можно было предвидеть в силу плохой обусловленностью матрицы :
[1]
Вычисление является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы.
Способы оценки ошибок
Улучшение метода исключения Гаусса
Выбор главного элемента
Итеративное улучшение результата
Программа, реализующая метод на C++
Рекомендации программисту
Список литературы
- Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков Численные методы