Участник:PopovaElizaveta/Метод Гаусса приведения матрицы к верхнему треугольному виду: различия между версиями
| Строка 3: | Строка 3: | ||
==== Общее описание алгоритма ==== | ==== Общее описание алгоритма ==== | ||
''' Метод Гаусса приведения матрицы к верхнему треугольному виду ''' - часть (прямой ход) метода Гаусса решения систем линейных алгебраических уравнений и нахождения обратных матриц. Применения только прямого хода достаточно для подсчета ранга матриц. | ''' Метод Гаусса приведения матрицы к верхнему треугольному виду ''' - часть (прямой ход) метода Гаусса решения систем линейных алгебраических уравнений и нахождения обратных матриц. Применения только прямого хода достаточно для подсчета ранга матриц. | ||
| − | + | Метода Гаусса приведения матрицы к верхнему треугольному виду состоит в последовательном исключении элементов матрицы, стоящих под главной диагональю, с помощью элементарных преобразований. Вначале среди элементов превого столбца матрицы выбирают ненулевой, далее путем перестановки строк помещают его на крайнее верхнее положение. Полученную после перестановки первую строку домножают на число, обратное к первому элементу этой строки. Таким образом, элемент в первом столбце первой строки становится равным единице. После этого первую строку вычитают из всех последующих, домножая ее на число, равное первому элементу каждой из этих строк. Таким образом, "зануляются" все элементы первого столбца матрицы кроме того, который находится в первой строке. После данных преобразований первая строка и первый столбец исходной матрицы ''"вычеркиваются"'' из рассмотрения, и аналогичные преобразования применяются к полученной после ''"вычеркивания"'' матрице до тех пор, пока не останется матрица нулевого размера. Если на каком-то шаге среди элементов первого столбца не найдено ненулевого, то переходят к следующему столбцу и проделывают аналогичные операции. | |
==== Математическое описание алгоритма ==== | ==== Математическое описание алгоритма ==== | ||
| Строка 23: | Строка 23: | ||
Основным ограничением метода является предположение, что все элементы <math> a_{kk}^{(k-1)}</math>, на которые проводится деление, отличны от нуля. Число <math> a_{kk}^{(k-1)}</math> называется ведущим элементом на <math> k-</math>ом шаге исключения. | Основным ограничением метода является предположение, что все элементы <math> a_{kk}^{(k-1)}</math>, на которые проводится деление, отличны от нуля. Число <math> a_{kk}^{(k-1)}</math> называется ведущим элементом на <math> k-</math>ом шаге исключения. | ||
| + | ==== Вычислительное ядро алгоритма ==== | ||
| + | Вычислительное ядро метода Гаусса можно составить из множественных (всего их <math> {m(m-1)} \over {2} </math> ) вычислений отношений | ||
| + | |||
| + | <math> u_{kj} = {a_{kj}^{(k-1)} \over {a_{kk}^{(k-1)}}}</math> | ||
| + | |||
| + | в режиме накомпления или без него, в зависимости от требований задачи, и дальнейших вычислений (всего их <math> {(m-1)m(2m-1)} \over {6} </math> ) элементов <math> a_{ij}^{(k)} </math> по формуле | ||
| + | |||
| + | <math> a_{ij}^{(k-1)} - a_{ik}^{(k-1)}u_{kj} </math> | ||
=== Программная реализация алгоритма === | === Программная реализация алгоритма === | ||
Версия 23:01, 31 октября 2017
Автор описания: Попова Елизавета
Содержание
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]ом шаге исключения.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро метода Гаусса можно составить из множественных (всего их [math] {m(m-1)} \over {2} [/math] ) вычислений отношений
[math] u_{kj} = {a_{kj}^{(k-1)} \over {a_{kk}^{(k-1)}}}[/math]
в режиме накомпления или без него, в зависимости от требований задачи, и дальнейших вычислений (всего их [math] {(m-1)m(2m-1)} \over {6} [/math] ) элементов [math] a_{ij}^{(k)} [/math] по формуле
[math] a_{ij}^{(k-1)} - a_{ik}^{(k-1)}u_{kj} [/math]
2 Программная реализация алгоритма
3 Литература
1. А.А. Самарский, А.В. Гулин. Численные метода. М.: Наука 1989
2. В.А. Ильин, Г.Д. Ким. Линейная алгебра и аналитическая геометрия
