Участник:PopovaElizaveta/Метод Гаусса приведения матрицы к верхнему треугольному виду

Автор описания: Попова Елизавета

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Метод Гаусса приведения матрицы к верхнему треугольному виду - часть (прямой ход) метода Гаусса решения систем линейных алгебраических уравнений и нахождения обратных матриц. Применения только прямого хода достаточно для подсчета ранга матриц. Метод Гаусса приведения матрицы к верхнему треугольному виду состоит в последовательном исключении элементов матрицы, стоящих под главной диагональю, с помощью элементарных преобразований. Вначале среди элементов превого столбца матрицы выбирают ненулевой, далее путем перестановки строк помещают его на крайнее верхнее положение. Полученную после перестановки первую строку домножают на число, обратное к первому элементу этой строки. Таким образом, элемент в первом столбце первой строки становится равным единице. После этого первую строку вычитают из всех последующих, домножая ее на число, равное первому элементу каждой из этих строк. Таким образом, "зануляются" все элементы первого столбца матрицы кроме того, который находится в первой строке. После данных преобразований первая строка и первый столбец исходной матрицы "вычеркиваются" из рассмотрения, и аналогичные преобразования применяются к полученной после "вычеркивания" матрице до тех пор, пока не останется матрица нулевого размера. Если на каком-то шаге среди элементов первого столбца не найдено ненулевого, то переходят к следующему столбцу и проделывают аналогичные операции.

1.2 Математическое описание алгоритма

Исходные данные: вещественная матрица [math] A [/math] (элементы [math] a_{ij}[/math]).

Вычисляемые данные: верхняя треугольная матрица [math] U [/math].

В прямом ходе метода Гаусса элементы матрицы [math] A [/math] преобразуются по следующему правилу:

[math] a_{kj}^{(0)} = a_{kj}, \qquad k,j = 1, 2, \ldots, m, [/math]

[math] u_{kj} = {a_{kj}^{(k-1)} \over {a_{kk}^{(k-1)}}}, \qquad j = k+1, k+2, \ldots ,m, \quad k = 1, 2, \ldots, m-1. [/math]

[math] a_{ij}^{(k)} = a_{ij}^{(k-1)} - a_{ik}^{(k-1)}u_{kj}, \qquad i,j = k+1, k+2, \ldots, m, \quad k = 1, 2, \ldots, m-1. [/math]

Основным ограничением метода является предположение, что все элементы [math] a_{kk}^{(k-1)}[/math], на которые проводится деление, отличны от нуля. Число [math] a_{kk}^{(k-1)}[/math] называется ведущим элементом на [math] k-[/math]ом шаге исключения.

3 Литература

1. А.А. Самарский, А.В. Гулин. Численные метода. М.: Наука 1989

2. В.А. Ильин, Г.Д. Ким. Линейная алгебра и аналитическая геометрия