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

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

Версия от 15:11, 4 декабря 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)$