Есть ли простой способ инвертировать треугольную (верхнюю или нижнюю) матрицу?

Question

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

Спасибо.

Answer 1

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

Answer 2

Не переворачивайте его, если можете. Это одна из основных заповедей числовой линейной алгебры.

Гораздо быстрее и численно стабильнее хранить саму матрицу L в памяти и вычислять

inv(L)b

с обратной заменой всякий раз, когда вам нужно сделать что-то еще с inv (L).

Обратите внимание, что обычный алгоритм для его инвертирования требует решения систем

inv(L)[1 0 0 ...],
inv(L)[0 1 0 ....],
inv(L)[0 0 1 ....]

и т. Д., Так что вы видите, что намного проще вообще не инвертировать его.

Answer 3

Учитывая нижнюю треугольную матрицу L, обратное замещение позволяет решить систему L x = b быстро для любой правой стороны б.

Чтобы инвертировать L, вы можете решить эту систему для правых частей e1 = (1,0, ..., 0), e2 = (0,1, ..., 0), ..., en = (0,0, ..., 1) и объединить полученные векторы решений в одну (обязательно нижне-треугольную) матрицу.

Если вас интересует решение в замкнутой форме, диагональные элементы обратного являются обратными по отношению к исходным диагональным элементам, а формула для остальных элементов обратного становится все более и более сложной по мере перемещения от диагонали.

Answer 4

Если вы говорите о вещественных значениях одинарной точности, взгляните на исходный код подпрограмм LAPACK STRTRI и STRTI2 .

Answer 5

Ого, это практически половина содержания курса численного анализа. Стандартные алгоритмы сделают это, и здесь есть куча стандартного кода здесь . Конечный источник для этой и большинства других обычных задач численного анализа - Числовые рецепты .