Методы исключения Гаусса

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(→Анализ метода)
Строка 89: Строка 89:
== Программа, реализующая метод на C++ ==
== Программа, реализующая метод на C++ ==
== Рекомендации программисту ==
== Рекомендации программисту ==
 +
 +
<references/>
 +
== Список литературы ==
== Список литературы ==
* ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков'' Численные методы
* ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков'' Численные методы

Версия 20:05, 4 декабря 2008

Содержание

Постановка задачи

Дана система линейных алгебраических уравнений (СЛАУ), состоящая из n уравнений с n неизвестными :

(1)

\left\{\begin{array}{lcr} a_{11}x_1+\ldots+a_{1n}x_n &=& b_1 \\ \\ \cdots & & \\ \\ a_{n1}x_1+\ldots+a_{nn}x_n &=& b_n \\ \end{array} \right. \quad \Longleftrightarrow \quad A\vec{x}=\vec{b}, \quad A=\left( \begin{array}{ccc} a_{11} & \ldots & a_{1n}\\ \\ \cdots & & \\ \\ a_{n1} & \ldots & a_{nn} \end{array}\right),\quad \vec{b}=\left( \begin{array}{c}b_1 \\ \\ \vdots \\ \\ b_n \end{array} \right).

Предполагается, что существует единственное решение системы, то есть detA \neq 0.

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

Описание метода

Процесс решения системы линейных уравнений

(2)
\sum_{j=1}^n a_{ij}x_{j} = b_{i}, \qquad i=1,\ldots,n,

по методу Гаусса состоит из 2х этапов:

  • Прямой ход
    Система (2) приводится к треугольному виду
1. Предполагаем, что a_{11} \neq 0 . Тогда первое уравнение системы (2) делим на коэффициент a_{11}, в результате получаем уравнение
x_{1}+\sum_{j=2}^n a_{ij}^{1}x_{j} = b_{i}^{1}
.
Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствующий коэффициент a_{i1}. В результате уравнения преобразуются к виду:
\left( \begin{array}{ccc} 1 & a_{12}^{1} & \ldots & a_{1n}^{1}\\ \\ 0 & a_{22}^{1} & \ldots & a_{2n}^{1}\\ \\ \vdots & \vdots & \ddots & \vdots\\ \\ 0 & a_{n2}^{1} & \ldots & a_{nn}^{1} \end{array}\right) \left( \begin{array}{c}x_1 \\ \\ x_2 \\ \\ \vdots \\ \\ \\ x_n \end{array}\right) = \left( \begin{array}{c}b_1^1 \\ \\ b_2^1 \\ \\ \vdots \\ \\ b_n^1 \end{array}\right)
2. В предположении, что a_{22}^1 \neq 0, делим второе уравнение на коэффициент a_{22}^1 и исключаем неизвестное x_2 из всех последующих уравнений и т.д.
3. Получаем систему уравнений с треугольной матрицей:
(3)
\left( \begin{array}{ccc} 1 & a_{12}^n & \ldots & a_{1n}^n\\ \\ 0 & 1 & \ldots & a_{2n}^n\\ \\ \vdots & \vdots & \ddots & \vdots\\ \\ 0 & 0 & \ldots & 1 \end{array}\right) \left( \begin{array}{c}x_1 \\ \\ x_2 \\ \\ \vdots \\ \\ \\ x_n \end{array}\right) = \left( \begin{array}{c}b_1^n \\ \\ b_2^n \\ \\ \vdots \\ \\ b_n^n \end{array}\right)
  • Обратный ход
    Непосредственное определение неизвестных
1. Из n-го уравнения системы (3) определяем x_{n}:\: \quad x_n=b_n^n
2. Из (n-1)-го - определяем x_{n-1}:\: \quad x_{n-1}=b_{n-1}^n-a_{(n-1)n}^n x_n и т.д.

Анализ метода

Данный метод относится к классу прямых методов решения системы уравнений, а это значит, что за конечное число шагов можно получить точное решение, при условии, что входные данные ( матрица A и правая часть уравнения - b) заданы точно и вычисление ведется без округлений. Для получения решения требуется \frac{m^3}{3}+ m^2 - \frac{m}{3} умножений и делений, то есть порядка O(\frac{m^3}{3}) операций.

Условия, при которых метод выдает точное решение, на практике не выполнимы - неизбежны как ошибки входных данных, так и ошибки округления. Тогда встает вопрос: насколько точное решение можно получить, используя метод Гаусса, насколько метод корректен? Определим устойчивость решения относительно входных параметров. Наряду с исходной системой (1) рассмотрим возмущенную систему:

(A + \delta A)(x + \delta x)=b + \delta b

Пусть введена некоторая норма || . ||. CondA=|| A || * || A^{-1}|| - называется числом обусловленности матрицы A.

Возможны 3 случая:

1) \delta A = 0 , \quad \delta b \neq 0 :

\frac{||\delta x||}{||x||} &\leq& Cond A \frac{||\delta b ||}{|| b ||}

2) \delta A \neq 0 , \quad \delta b = 0 :

<tex>\frac{||\delta x||}{||x||} \leq Cond A \frac{||\delta A ||}{|| A ||}

3) \delta A \neq 0 , \quad \delta b \neq 0 :

<tex>\frac{||\delta x||}{||x||} \leq \frac{Cond A}{1-Cond A\frac{||\delta A ||}{|| A ||}}(\frac{||\delta A ||}{|| A ||}+ \frac{||\delta b ||}{|| b ||})

Число обусловленности матрицы A всегда \geq 1. Если оно велико ( Cond A \approx 10^k k \geq 2 ) , то говорят, что матрица A плохо обусловлена. В этом случае малые возмущения правых частей системы (1), вызванные либо неточностью задания исходных данных, либо вызванные погрешностями вычисления, существенно влияют на решение системы. Грубо говоря, если погрешность правых частей 10^{-l} , то погрешность решения будет 10^{-l+k} .

Проиллюстрируем полученные результаты на следующем числовом примере: Дана система

\left\{\begin{array}{lcr}5x_1+7x_2 &=& 12 \\ \\ 7x_1+10x_2 &=& 17 \\ \end{array} \right.

Она имеет решение (1, \quad 1).

Теперь рассмотрим возмущенную систему:

\left\{\begin{array}{lcr}5x_1+7x_2 &=& 12.075 \\ \\ 7x_1+10x_2 &=& 16.905 \\ \end{array} \right.

Решением такой системы будет вектор (2.415, \quad 0).

При совсем малом возмущении правой части получили несоизмеримо большое возмущение решения. Объяснить такую "ненадежность" решения можно тем, что матрица A почти вырожденная: прямые, соответствующие двум уравнениям, почти совпадают, что видно на графике:

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

Такой результат можно было предвидеть в силу плохой обусловленностью матрицы A = \left( \begin{array}{ccc} 5 & 7\\ \\ 7 & 10 \end{array}\right) : Cond A = 17^2 [1]

Вычисление Cond A является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы.

Способы оценки ошибок

Улучшение метода исключения Гаусса

Выбор главного элемента

Итеративное улучшение результата

Программа, реализующая метод на C++

Рекомендации программисту


Список литературы

  • Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков Численные методы

Внешние ссылки

См. также

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B8%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D1%8F_%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%B0»