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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Постановка задачи)
(→Изложение метода)
Строка 16: Строка 16:
В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности.
В данной статье будут рассмотрены причины погрешности, возникающей во время решения системы с помощью метода Гаусса, способы выявления и ликвидации(уменьшения) этой погрешности.
-
== Изложение метода ==
+
== Описание метода ==
 +
Процесс решения системы линейных уравнений
 +
{{eqno|2}}
 +
<center><tex>\sum_{j=1}^n a_{ij}x_{j} = b_{i}, \qquad i=1,\ldots,n,</tex></center>
 +
по методу Гаусса состоит из 2х этапов:
 +
* Прямой ход
 +
*: Система {{eqref|2}} приводится к треугольному виду
 +
:: 1. Предполагаем, что <tex>a_{11} \neq 0</tex> . Тогда первое уравнение системы {{eqref|2}} делим на коэффициент <tex>a_{11}</tex>, в результате получаем уравнение
 +
<center><tex>x_{1}+\sum_{j=2}^n a_{ij}^{1}x_{j} = b_{i}^{1}</tex></center>.
 +
::Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствующий коэффициент <tex>a_{i1}</tex>. В результате уравнения преобразуются к виду:
 +
<center><tex>\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)</tex></center>
 +
:: 2. В предположении, что <tex>a_{22}^1 \neq 0</tex>, делим второе уравнение на коэффициент <tex>a_{22}^1</tex> и исключаем неизвестное <tex>x_2</tex> из всех последующих уравнений и т.д.
 +
:: 3. Получаем систему уравнений с треугольной матрицей:
 +
{{eqno|3}}
 +
<center><tex>\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)</tex></center>
 +
 
 +
* Обратный ход
 +
*: Непосредственное определение неизвестных
 +
:: 1. Из <tex>n-</tex>го уравнения системы {{eqref|3}} определяем <tex>x_{n}:\: \quad x_n=b_n^n</tex>
 +
:: 2. Из <tex>(n-1)-</tex>го - определяем <tex>x_{n-1}:\: \quad x_{n-1}=b_{n-1}^n-a_{(n-1)n}^n x_n</tex> и т.д.
 +
 
== Анализ метода и оценка ошибок ==
== Анализ метода и оценка ошибок ==
== Числовой пример ==
== Числовой пример ==

Версия 15:23, 26 октября 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 и т.д.

Анализ метода и оценка ошибок

Числовой пример

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

Заключение

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

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

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

См. также

Источник — «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»
Личные инструменты