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