Обновление матрицы A ^-1 при изменении нескольких элементов матрицы A

В некоторых случаях надо решить такую задачу: есть матрица A, которую мы обратили, получив A ^-1. Затем мы изменили несколько элементов матрицы A, получив матрицу B, и нам требуется обратить матрицу B.

Разумеется, эта задача может быть решена "в лоб" путем применения алгоритма обращения к матрице B. Однако есть более эффективный алгоритм, позволяющий использовать тот факт, что у нас уже есть матрица A ^-1, а матрица B лишь незначительно отличается от матрицы A.

Алгоритм обновления обратной матрицы

В основе алгоритма лежит формула Шермана-Моррисона:

Здесь A - квадратная матрица размером NxN, чья обратная матрица нам известна, а u и v - столбцы высоты N, задающие модификацию матрицы A (к элементу a_i,j  добавляется u_i v_j ). Можно видеть, что для обновления обратной матрицы по этой формуле требуется порядка N ² операций с вещественными числами, что в N раз лучше, чем обращение более общим алгоритмом.

В зависимости от выбора векторов u и v возможны различные варианты модификации матрицы A и обновления матрицы A ^-1, выполняющиеся с различной трудоемкостью. Рассмотрим основные варианты:

• Если только i-ая компонента вектора u и j-ая компонента вектора v неравны нолю, то такой набор векторов обозначает добавление к элементу a_i,j  числа u_i v_j .
• Если i-ая компонента вектора u равна единице, а остальные равны нолю, то к i-ой строке матрицы A добавляется вектор v.
• Если j-ая компонента вектора v равна единице, а остальные равны нолю, то к j-ому столбцу матрицы A добавляется вектор u.
• Если нет ограничений на компоненты векторов u и v, то это можно трактовать, как добавление строки v (или столбца u) к разным строкам (столбцам) матрицы с разными множителями.

Различные варианты обновления могут быть осуществлены с разной эффективностью, учитывая особую структуру векторов u и v. Самым быстрым является обновление обратной матрицы при модификации только одного элемента исходной матрицы, поэтому имеет смысл выбрать его эталоном.

Обновление обратной матрицы при модификации строки или столбца исходной матрицы всего лишь в два раза медленее (так что при модификации трех и более элементов, расположенных в одном столбце или строке, оно является более выгодным, чем многократный вызов предыдущего алгоритма). Обновление обратной матрицы при произвольном выборе векторов u и v в три раза медленее, чем обновление при модификации только одного элемента.

Замечание #1
Устойчивость алгоритма находится под вопросом, но как минимум один шаг алгоритма достаточно устойчив, если матрицы A и B хорошо обусловлены.

Описание программы

Модуль содержит несколько подпрограмм, позволяющих эффективно проводить обновление матрицы A ^-1 как в общем случае, заданном векторами u и v, так и в описанных выше специальных случаях.

Подпрограмма RMatrixInvUpdateSimple обновляет матрицу A ^-1 при добавлении числа UpdVal к элементу матрицы A, расположенному в строке UpdRow, столбце UpdColumn.

Подпрограммы RMatrixInvUpdateRow и RMatrixInvUpdateColumn позволяют обновить матрицу при добавлении вектора к указанной строке или столбцу.

Подпрограмма RMatrixInvUpdateUV обрабатывает более общий случай, задаваемый векторами U и V.

Manual entries

C++		inverseupdate.h
C#		inverseupdate.cs
MPFR		inverseupdate.h
Delphi		inverseupdate.pas
FreePascal		inverseupdate.pas
VBA		inverseupdate.bas

This article is intended for personal use only.

Скачать ALGLIB