Онлайн калькулятор: Приведение матрицы к треугольному виду

Ниже два калькулятора для приведения матриц к треугольному, или ступенчатому, виду. Первый использует для этого метод Гаусса, второй — метод Барейса. Описание методов и немного теории — под калькуляторами.

Приведение матрицы к треугольному виду (метод Гаусса)

Матрица

Точность вычисления

Знаков после запятой: 4

Треугольная матрица (метод Гаусса)

Треугольная матрица (метод Гаусса с выбором максимума в столбце)

Треугольная матрица (метод Гаусса с выбором максимума по всей матрице)

Приведение матрицы к треугольному виду (метод Барейса)

Матрица

Точность вычисления

Знаков после запятой: 4

Треугольная матрица (метод Барейса)

Треугольная матрица (метод Барейса с выбором максимума в столбце)

Треугольная матрица (метод Барейса с выбором максимума по всей матрице)

Итак, для начала определимся с понятием треугольной, или ступенчатой матрицы:
Матрица имеет ступенчатый вид, если:

Все нулевые строки матрицы стоят последними
Первый ненулевой элемент строки всегда находится строго правее первого ненулевого элемента предыдущей строки
Все элементы столбца под первым ненулевым элементом строки равны нулю (это впрочем следует из первых двух пунктов)

Пример ступенчатой матрицы:
1 0 2 5
0 3 0 0
0 0 0 4

Понятие треугольной матрицы более узкое, оно используется только для квадратных матриц (хотя я думаю, что это не строго), и формулируется проще: треугольная матрица — квадратная матрица, в которой все элементы ниже главной диагонали равны нулю. Строго говоря, это даже определение верхнетреугольной матрицы, но мы будем использовать его. Понятно, что такая верхнетреугольная матрица является также и ступенчатой.

Пример треугольной (верхнетреугольной) матрицы:
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
Кстати, определитель треугольной матрицы вычисляется простым перемножением ее диагональных элементов.

Чем же так интересны ступенчатые (и треугольные) матрицы, что к ним надо приводить все остальные? — спросите вы.
У них есть замечательной свойство, а именно, любую прямоугольную матрицу можно с помощью элементарных преобразований привести к ступенчатой форме.

Что же такое элементарные преобразования? — спросите вы.
Элементарными преобразованиями матрицы называют следующие операции:

перестановка любых двух строк (столбцов) матрицы
умножение любой строки (столбца) на призвольное, отличное от нуля, число
сложение любой строки (столбца) с другой строкой (столбцом), умноженной (умноженным) на произвольное, отличное от нуля, число.

И что? — спросите вы.
А то, что элементарные преобразования матрицы сохраняют эквивалентность матриц. А если вспомнить, что системы линейных алгебраический уравнений (СЛАУ) записывают как раз в матричной форме, то это означает, что элементарные преобразования матрицы не изменяют множество решений системы линейных алгебраических уравнений, которую представляет эта матрица.

Приведя матрицу системы линейных уравнений AX=B к треугольной форме A'X = B', то есть, с соответствующими преобразованиями столбца B, можно найти решение этой системы так называемым «обратным ходом».

Чтобы было понятно, используем треугольную матрицу выше и перепишем систему уравнений в более привычной форме (столбец B я придумал сам):
$1*x_1 + 0*x_2 + 2 * x_3 + 5 * x_4 = 10$
$0*x_1 + 3*x_2 + 1 * x_3 + 3 * x_4 = 7$
$0*x_1 + 0*x_2 + 4 * x_3 + 2 * x_4 = 5$
$0*x_1 + 0*x_2 + 0 * x_3 + 3 * x_4 = 9$
Понятно, что сначала мы найдем $x_4$ , потом, подставив его в предыдущее уравнение, найдем $x_3$ и так далее — двигаясь от последнего уравнения к первому. Это и есть обратный ход.

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

Теперь про сам метод.
Собственно, как можно занулить переменную $x_1$ во втором уравнении? Вычтя из него первое, домноженное на коэффициент $\frac{a_{21}}{a_{11}}$
Поясним на примере:
$2*x_1 + 3*x_2 + 4 * x_3 = 10$
$6*x_1 + 3*x_2 - 4 * x_3 = 7$
Зануляем $x_1$ во втором уравнении:
$6*x_1 + 3*x_2 - 4 * x_3 - \frac{6}{2}(2*x_1 + 3*x_2 + 4 * x_3)= 7 - \frac{6}{2}10$
$6*x_1 + 3*x_2 - 4 * x_3 - 6*x_1 - 9*x_2 - 12 * x_3 = 7 - 30$
$-6*x_2 - 16 * x_3 = -23$
Во втором уравнении больше не содержится $x_1$

Обобщенно алгоритм метода Гаусса можно представить следующим образом:
$\begin{matrix}For\, j = 0,..., N-2 \\ \qquad \qquad For\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \vec{a_i} - \frac{a_{ij}}{a_{jj}} \vec{a_j} \end{matrix}$
где N — число строк,
$\vec{a_i}$ — i-тая строка,
$a_{ij}$ — элемент, находящийся в i-той строке, j-том столбце

И все бы ничего, да и метод отличный, но. Дело все в делении на $a_{jj}$ , присутствующем в формуле. Во-первых, если диагональный элемент будет равен нулю, то метод работать не будет. Во-вторых, в процессе вычисления будет накапливаться погрешность, и чем дальше, тем больше. Результат будет отличаться от точного.

Для уменьшения погрешности используют модификации метода Гаусса, которые основаны на том, что погрешность тем меньше, чем больше знаменатель дроби. Эти модификации — метод Гаусса с выбором максимума в столбце и метод Гаусса с выбором максимума по всей матрице. Как следует из названия, перед каждым шагом исключения переменной по столбцу (всей матрице) ищется элемент с максимальным значением и проводится перестановка строк (строк и столбцов), таким образом, чтобы он оказался на месте $a_{jj}$ .

Но есть еще более радикальная модификация метода Гаусса, которая называется методом Барейса (Bareiss).
Как можно избавиться от деления? Например, умножив перед вычитанием строку $\vec{a_i}$ на $a_{jj}$ . Тогда вычитать надо будет строку $\vec{a_i}$ , домноженную только на $a_{ij}$ , без всякого деления.
$\vec{a_i} \leftarrow a_{jj}\vec{a_i} - a_{ij} \vec{a_j}$ .
Уже хорошо, но возникает проблема с ростом значений элементов матрицы в ходе вычисления.

Барейс предложил делить выражение выше на $a_{j-1,j-1}$ и показал, что если исходные элементы матрицы — целые числа, то результатом вычисления такого выражения тоже будет целое число. При этом принимается, что для нулевой строки $a_{-1,-1}=1$ .

Кстати, то, что в случае целочисленных элементов исходной матрицы алгоритм Барейса приводит к треугольной матрице с целочисленными элементами, то есть без накопления погрешности вычислений — довольно важное свойство с точки зрения машинной арифметики.

Алгоритм Барейса можно представить следующим образом:
$\begin{matrix} a_{-1,-1}=1 \\For\, j = 0,..., N-2 \\ \qquad \qquad For\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \frac{a_{jj}\vec{a_i} - a_{ij} \vec{a_j}}{a_{j-1,j-1}} \end{matrix}$

Алгоритм, аналогично методу Гаусса, также можно улучшить поиском максимума по столбцу(всей матрице) и перестановкой соответствующих строк (строк и столбцов).

PLANETCALC Онлайн калькуляторы

Приведение матрицы к треугольному виду

Эта страница существует благодаря следующим персонам

Timur

Приведение матрицы к треугольному виду (метод Гаусса)

Приведение матрицы к треугольному виду (метод Барейса)

Похожие калькуляторы

Комментарии

PLANETCALC Онлайн калькуляторы

Приведение матрицы к треугольному виду (метод Гаусса)

Приведение матрицы к треугольному виду (метод Барейса)

Похожие калькуляторы

Комментарии

Поделиться этой страницей