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

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

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

Содержание

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

Дана система линейных алгебраических уравнений (СЛАУ), состоящая из 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]

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

Рассмотренные ниже модификации метода Гаусса позволяют уменьшить погрешность результата.

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

Основное увеличение ошибки в методе происходит во время прямого хода, когда ведущая k-я строка умножается на коэффициенты \frac{a_{i, k}}{a_{k, k}}, \quad i=k+1, \ldots, n.Если коэффициенты  >1 , то ошибки, полученные на предыдущих шагах накапливаются. Чтобы этого избежать, применяется модификация метода Гаусса с выбором главного элемента. На каждом шаге к обычной схеме добавляется выбор максимального элемента по столбцу следующим образом:

Пусть по ходу исключения неизвестных получена система уравнений:

x_i+\sum_{j=i+1}^{n}a_{ij}^i x^j = b_i^i, \quad \quad i=1, \ldots, k-1,
\sum_{j=k}^{n}a_{ij}^{k-1}x_j = b_i^{k-1}, \quad \quad i=k, \ldots, n.

Найдем такое l, что |a_{l,k}^{k-1}|=\max_{j=k,...,n} |a_{j,k}^{k-1}| и поменяем местами k-е и l-е уровнения.

Такое преобразование во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях.

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

Если есть подозрение, что полученное решение x^{1} сильно искажено, то можно улучшить результат следующим образом. Величина b^1=b-Ax^{0} называется невязкой. Погрешность r^1=x-x^{1} удовлетворяет системе уравнений

Ar^1=Ax-Ax^1=b^1.

Решая эту систему, получаем приближение r^{(1)} к r^1 и полагаем

x^2=x^1+r^{(1)}.

Если точность данного приближения неудовлетворительна, то повторяем эту операцию.

Процесс можно продолжать до тех пор, пока все компоненты r^{(i)} не станут достаточно малыми. При этом нельзя останавливать вычисления только потому, что все компоненты вектора невязки стали достаточно малыми: это может быть результатом плохой обусловленности матрицы коэффициентов.

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

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


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

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

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

См. также

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