next up previous contents
Next: Другие методы Up: Системы линейных уравнений Previous: Системы линейных уравнений   Contents

Алгоритм Гаусса

        

Алгоритм Гаусса также называется методом исключений. Пусть имеется система линейных уравнений

$\displaystyle \textbf{Ax }=\textbf{b},$ (3.1)

где $ \textbf{A }$ - матрица размера $ (n*n)$ с постоянными коэффициентами; $ \textbf{b}$ - $ n$ -мерный вектор известных констант и $ \textbf{x}$ - $ n$ -мерный вектор неизвестных:

$\displaystyle \left\Vert \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n}\...
...ft\Vert \begin{array}{c} b_{1}\\ b_{2}\\ \vdots\\ b_{n}\end{array}\right\Vert .$ (3.2)

Формально эту систему уравнений можно решить, обратив матрицу $ \textbf{A }$ :

$\displaystyle \textbf{x}=\textbf{A}^{-1}\textbf{b}.$ (3.3)

Когда требуется найти только одну ``выходную'' переменную, используют метод, называемый правилом Крамера. Это правило гласит, что для системы (3.1) $ k$ -я компонента $ x_{k}$ вектора $ \textbf{x}$ равна отношению определителя матрицы $ \textbf{A }$ , в которой $ k$ -й столбец заменён вектором $ \textbf{b}$ , и определителя матрицы $ \textbf{A }$ :

$\displaystyle x_{k}=\frac{\det(\textbf{A}_{k})}{\det(\textbf{A})}.$ (3.4)

Правило Крамера используется для решения уравнений низкого порядка и при теоретических исследованиях. Этот метод требует больших затрат машинного времени и редко применяетя в вычислительных программах.

Численное решение систем линейных уравнений часто базируется на методе исключений Гаусса. Он основываетия на том факте, что сложение одного уравнения системы с другим, возможно умноженным на константу, не изменяет решения системы.

Перепишем матричное уравнение (3.2) в координатной форме:

\begin{displaymath}\begin{array}{c} a_{11}x_{1}+a_{12}x_{2}+\cdots\,+a_{1n}x_{n}...
...\ a_{n1}x_{1}+a_{n2}x_{2}+\cdots\,+a_{nn}x_{n}=b_{n}\end{array}\end{displaymath} (3.5)

Разделим первое уравнение на $ a_{11}$ и запишем его:

$\displaystyle x_{1}+a_{12}^{(1)}x_{2}+a_{13}^{1)}x_{3}+\cdots\,=b_{1}^{(1)},$

где $ a_{12}^{(1)}=\dfrac{a_{12}}{a_{11}},$ и т.д. Умножим это уравнение на $ -a_{21}$ и сложим его со вторым уравнением. Коэффициенты вновь полученного второго уравнения $ a_{2j}^{(1)}=a_{2j}-a_{21}a_{1j}^{(1)},\, j=1,2,\ldots,n+1$ . Такой выбор множителя обеспечивает равенство нулю коэффициента $ a_{21}^{(1)}$ . Аналогично для других уравнений подстановка

$\displaystyle a_{ij}^{(1)}=a_{ij}-a_{i1}a_{1j}^{(1)},\,\begin{array}{l}
i=2,3,\ldots,n,\\
j=1,2,\ldots,n+1,\end{array}$

обеспечивает равенство нулю всех коэффициентов в первом столбце матрицы $ \textbf{A }$ , за исключением $ a_{11}^{(1)}$ , который равен $ 1$ . В результате этих операций уравнения примут вид:

\begin{displaymath}
\begin{array}{r}
x_{1}+a_{12}^{(1)}x_{2}+a_{13}^{(1)}x_{3}+\...
...}^{(1)}x_{3}+\cdots\,+a_{nn}^{(1)}x_{n}=b_{n}^{(1)}.\end{array}\end{displaymath}

Индекс в скобках показывает, что коэффициенты были один раз изменены. На следующем шаге исключается из рассмотрения первые строка и столбец. Аналогично надо выполнить ранее описанные процедуры для уравнений от второго до $ n$ -го.

Исключение по Гауссу требует выполнения $ \sim\dfrac{n^{3}}{3},$ где $ n$ - порядок матрицы, а обратная подстановка может быть выполнена приблизительно за $ \dfrac{n^{2}}{2}$ операций.

Ниже приводится пример программы расчёта системы линейных уравнений методом Гаусса, написанный на языке Паскаль (4.5.1).


next up previous contents
Next: Другие методы Up: Системы линейных уравнений Previous: Системы линейных уравнений   Contents
Eugene Misnik 2005-07-29