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

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

(Различия между версиями)

Перейти к: навигация, поиск

Версия 17:29, 5 декабря 2008

Содержание

1 Постановка задачи
2 Описание метода
3 Анализ метода
4 Способы оценки ошибок
5 Улучшение метода исключения Гаусса
- 5.1 Выбор главного элемента
- 5.2 Итеративное улучшение результата
6 Программа, реализующая метод на C++
7 Рекомендации программисту
8 Список литературы
9 Внешние ссылки
10 См. также

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

Дана система линейных алгебраических уравнений (СЛАУ), состоящая из $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$ и $\alfa \beta^{-1}x'$ дает представление о величине вычислительной погрешности ^[1]

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

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

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

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

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

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

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

Обратная матрица

См. также

Практикум ММП ВМК, 4й курс, осень 2008

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/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»

Категории: Незавершённые статьи | Решение СЛАУ | Учебные задачи

@@ Строка 85: / Строка 85: @@
 == Способы оценки ошибок ==
+:1) <u>'''Контрольная сумма:'''</u> обычно применяется для предупреждения случайных погрешностей в процессе вычисления без помощи компьютеров.
+Составляем контрольный столбец <tex>a_{n+1} = \left( a_{1,n+1}, \ldots, a_{n, n+1}\right)</tex>, состоящий из контрольных элементов системы:
+:<tex>a_{i, n+1} = \sum_{j=1}^n a_{i, j} + b_i</tex>
+При преобразовании уравнений над контрольными элементами производятся те же операции, что и над свободными членами уравнеий. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности.
+:2) <u>'''Относительная погрешность известного решения'''</u> позволяет без существенных дополнительных затрат получить суждение о погрешности решения.
+Задается некоторый ветор <tex>z</tex> с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения <ref>Часто из-за отсутствия доплнительной информации берут <tex>z=\left(1, \ldots, 1\right)</tex></ref>. Вычисляется вектор <tex>c=Az</tex>, и на ряду с исходной системой уравнения решается система <tex>Az=c</tex>.
+Пусть <tex>x'</tex> и <tex>z'</tex> - реально получаемые решения этих систем. Суждение о погрешности <tex>x-x'</tex> искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины <tex>\frac{||x-x'||}{||x'||}</tex> и <tex>\frac{||z-z'||}{||z'||}</tex>, отличаются не в очень большое число раз.
+:3) <u>'''Изменение масштабов'''</u> - прием, применяющийся для получения представления о реальной величине погрешности, возникающей за счет округлений при вычислениях.
+Наряду с исходной системой тем же методом решается система
+:<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>
 == Улучшение метода исключения Гаусса==