Алгоритм триангуляции матрицы

      Комментарии к записи Алгоритм триангуляции матрицы отключены

Главная Форумы Программирование Алгоритмы и структуры данных Алгоритм триангуляции матрицы

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 4 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #3420

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

    • перестановка строк;
    • прибавление к элементам одной строки соответствующих элементов другой строки, домноженной на константу.

    Выполнение над матрицей эквивалентных преобразований не изменит значение определителя матрицы, а также корни системы уравнений, заданной матрицей. Построение треугольной матрицы является частью алгоритма Гаусса-Жордана решения СЛАУ, а также вычисления определителя методом Гаусса.

    Для «обнуления» элементов i-того столбца матрицы достаточно ко всем строкам с номерами j = i+1, ... n прибавить i-тую строку, домноженную на -a[j][i]/a[i][i]. При выполнении такой операции может возникать деление на ноль если элемент на главной диагонали окажется равным нулю — в этом случае выполняют перестановку строк матрицы. Наиболее эффективным подходом к перестановке строк является перестановка i-той строки со строкой, имеющей максимальный по модулю элемент в i-том столбце. Доказано, что при выполнении такой перестановки для каждой строки (а не только когда a[i][i] равен нулю) для матрицы с ненулевым определителем мы всегда найдем строку для замены.

    Такой алгоритм можно изобразить в виде следующей блок-схемы:

    Так например, возьмем следующую матрицу:

    Умножаем первую строку на 3/5 и отнимаем ее от второй:

    Умножаем первую строку на 13/5 и отнимаем ее от третьей:

    Обнулились элементы ниже главной диагонали в первом столбце матрицы — переходим ко второму столбцу. Умножаем вторую строку на -8,2/11,8 и отнимаем ее от третьей:

    Матрица приведена к треугольному виду. Теперь мы можем очень легко найти ее определитель или корни соответствующей СЛАУ (если есть столбец свободных членов).

Для ответа в этой теме необходимо авторизоваться.