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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Способы оценки ошибок)
(Способы оценки ошибок)
Строка 104: Строка 104:
:<tex>\left( \alpha A\right)x' = \beta b</tex>, где <tex>\alpha</tex> и <tex>\beta</tex> - числа
:<tex>\left( \alpha A\right)x' = \beta b</tex>, где <tex>\alpha</tex> и <tex>\beta</tex> - числа
-
Если бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: <tex>x=\alpha \beta^{-1}x'</tex>. Поэтому при <tex>\alpha</tex> и <tex>\beta</tex>, не являющихся степенями двойки, сравнение векторов <tex>x</tex> и <tex>\alfa \beta^{-1}x'</tex> дает представление о величине вычислительной погрешности <ref>Например, можно взять <tex>\alfa=\sqrt{2}, \quad \beta=\sqrt{3}</tex></ref>
+
Если бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: <tex>x=\alpha \beta^{-1}x'</tex>. Поэтому при <tex>\alpha</tex> и <tex>\beta</tex>, не являющихся степенями двойки, сравнение векторов <tex>x</tex> и <tex>\alpha \beta^{-1}x'</tex> дает представление о величине вычислительной погрешности <ref>Например, можно взять <tex>\alpha=\sqrt{2}, \quad \beta=\sqrt{3}</tex></ref>
== Улучшение метода исключения Гаусса==
== Улучшение метода исключения Гаусса==

Версия 17:30, 5 декабря 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 является достаточно сложным, сравнимо с решением всей системы, поэтому для оценки пограшности применяются более грубые, но простые в реализации методы.

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

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

Составляем контрольный столбец a_{n+1} = \left( a_{1,n+1}, \ldots, a_{n, n+1}\right), состоящий из контрольных элементов системы:

a_{i, n+1} = \sum_{j=1}^n a_{i, j} + b_i

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

2) Относительная погрешность известного решения позволяет без существенных дополнительных затрат получить суждение о погрешности решения.

Задается некоторый ветор z с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения [1]. Вычисляется вектор c=Az, и на ряду с исходной системой уравнения решается система Az=c.

Пусть x' и z' - реально получаемые решения этих систем. Суждение о погрешности x-x' искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины \frac{||x-x'||}{||x'||} и \frac{||z-z'||}{||z'||}, отличаются не в очень большое число раз.

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

Наряду с исходной системой тем же методом решается система

\left( \alpha A\right)x' = \beta b, где \alpha и \beta - числа

Если бы не было погрешности округления, то выполнялось бы равенство для решений исходной и масштабированной систем: x=\alpha \beta^{-1}x'. Поэтому при \alpha и \beta, не являющихся степенями двойки, сравнение векторов x и \alpha \beta^{-1}x' дает представление о величине вычислительной погрешности [1]

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

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

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

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

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


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

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

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

См. также

Личные инструменты