Обращение матрицы

- алгоритм, применяемый при численном нахождении обратной матрицы. Как и в задаче решения линейных систем, методы численного обращения подразделяются на прямые и итерационные; однако итерационные методы вследствие их трудоемкости играют здесь существенно меньшую роль. Большинство прямых методов О. м. основано на идее разложения заданной матрицы в произведение легко обращаемых сомножителей. Если [img: http://localhost:8080/file/031602-616.jpg] - такое разложение, то [img: http://localhost:8080/file/031602-617.jpg] Типичным (и одним из наиболее употребительных) прямых методов О. м. является метод Жордана (см. [1]). Пусть А- невырожденная матрица порядка п. Построение обратной матрицы А -1 происходит в пшагов; результатом k-го шага будет матрица [img: http://localhost:8080/file/031602-618.jpg], первые кстолбцов к-рой совпадают с одноименными столбцами единичной матрицы. Переход от [img: http://localhost:8080/file/031602-619.jpg] (пусть А=А 0)к [img: http://localhost:8080/file/031602-620.jpg] с матричной точки зрения эквивалентен умножению. [img: http://localhost:8080/file/031602-621.jpg] слева на матрицу [img: http://localhost:8080/file/031602-622.jpg], к-рая отличается от единичной лишь (k+1)-м столбцом. Элементы этого столбца выбираются так, чтобы привести (k+1)-й столбец [img: http://localhost:8080/file/031602-623.jpg] к единичному, и имеют вид [img: http://localhost:8080/file/031602-624.jpg] Из соотношений [img: http://localhost:8080/file/031603-1.jpg] вытекает [img: http://localhost:8080/file/031603-2.jpg] и [img: http://localhost:8080/file/031603-3.jpg] Получение факторизованного представления (1) для обратной матрицы [img: http://localhost:8080/file/031603-4.jpg] требует примерно [img: http://localhost:8080/file/031603-5.jpg] операций умножения и примерно [img: http://localhost:8080/file/031603-6.jpg] операций сложения. Приблизительно такое же число дополнительных операций необходимо для того, чтобы перемножить матрицы в (1) и получить явный вид [img: http://localhost:8080/file/031603-7.jpg]. Во многих приложениях операции О. м. использование факторизованной формы (1) столь же удовлетворительно, что и явного вида. Напр., вычисление произведения [img: http://localhost:8080/file/031603-8.jpg], где b- вектор-столбец, требует одинаковой арифметич. работы в обоих случаях. Одинаковы и требования к памяти при реализации на ЭВМ. В приведенном описании метода Жордана предполагалось для простоты, что все элементы [img: http://localhost:8080/file/031603-9.jpg] (называемые ведущими элементами) отличны от нуля. В действительности метод Жордана, как и методы типа Гаусса для решения линейных систем, как правило, применяется с той или иной схемой выбора ведущих элементов. Использование такой схемы равносильно введению в (1) дополнительных множителей, учитывающих перестановки строк и столбцов обратной матрицы. Точность вычисленного решения, как и в случае линейных систем, зависит от степени роста матричных элементов на промежуточных шагах метода. Такой рост и, следовательно, ухудшение точности вычисляемого решения в методе Жордана, даже при выборе ведущего элемента, более вероятны, чем в методах типа Гаусса. Невязкой, соответствующей приближенной обратной матрице Xдля А, наз. матрица [img: http://localhost:8080/file/031603-10.jpg]. Имеет место оценка [img: http://localhost:8080/file/031603-11.jpg] Таким образом, норма невязки является оценкой относительной точности приближенной обратной матрицы X. В этом состоит важное отличие задачи численного О. м. от задачи решения линейных систем, где (напр., в ортогональных методах или методах типа Гаусса) невязка обычно мала, а качество полученного решения зависит от обусловленности системы. Обращение ряда важных классов матриц может быть достигнуто значительно более экономичными, чем в общем случае, методами. Таковы теплицевы, ганкелевы, ленточные (и, в частности, трехдиагональные) матрицы, блочные матрицы, имеющие теплицеву структуру или структуру кронекерова произведения, и т. д. Напр., пусть Т- теплицева матрица порядка n+1 с элементами из Rили С: [img: http://localhost:8080/file/031603-12.jpg] Предполагается, что не только Т, но и ее главная подматрица порядка пневырождены. Тогда для матрицы [img: http://localhost:8080/file/031603-13.jpg] уже, вообще говоря, не являющейся теплицевой, справедливо представление (см. [2]): [img: http://localhost:8080/file/031603-14.jpg] При этом векторы [img: http://localhost:8080/file/031603-15.jpg] суть соответственно первый и последний столбцы [img: http://localhost:8080/file/031603-16.jpg] Таким образом, Тполностью определяется заданием первого и последнего столбцов. При необходимости из (2) [img: http://localhost:8080/file/031603-17.jpg] могут быть последовательно вычислены все элементы [img: http://localhost:8080/file/031603-18.jpg] Это вычисление требует [img: http://localhost:8080/file/031603-19.jpg] арифметич. операций. В экономичных алгоритмах обращения теплицевых. матриц (см., напр., [3]) вычисление [img: http://localhost:8080/file/031603-20.jpg] проводится по рекуррентным формулам и также требует [img: http://localhost:8080/file/031603-21.jpg] операций. Условие невырожденности главных подматриц может быть ослаблено с сохранением порядка О(п 2)необходимой арифметич. работы. Иногда операцию О. м. используют с тем, чтобы решать линейные системы [img: http://localhost:8080/file/031603-22.jpg] по формуле [img: http://localhost:8080/file/031603-23.jpg] В случае матрицы общего вида такой образ действий имеет мало смысла, т. к. сопровождается проигрышем и в арифметич. работе, и в численной устойчивости по-сравнению с прямым решением линейной системы. Для теплицевых (и родственных им) матриц ситуация иная. Как показывает представление (2), вычисление [img: http://localhost:8080/file/031603-24.jpg] сводится к выполнению четырех умножений, теплицевых матриц на векторы и вычитанию векторов. Существуют экономичные алгоритмы умножения теплицевой матрицы на вектор, требующие (для порядка п} [img: http://localhost:8080/file/031603-25.jpg] операций. Для задачи решения теплицевых систем такая асимптотика арифметич. работы пока недостигнута. Поэтому при многократном решении линейных систем [img: http://localhost:8080/file/031603-26.jpg] с одной и той же теплицевой матрицей [img: http://localhost:8080/file/031603-27.jpg] и различными правыми частями bпредварительное обращение [img: http://localhost:8080/file/031603-28.jpg], по-видимому, целесообразно. Предварительное О. м. может быть оправданным и в случае многократного решения линейных систем с одной и той же матрицей общего вида на ЭВМ с большим; числом параллельно работающих процессоров. Причина в том, что по сравнению с операцией умножения матрицы на вектор прямые методы решения линейных систем не имеют столь же удобного распараллеливания. Во многих случаях (напр., в квазиньютоновых методах математич. программирования) требуется обратить матрицу А, отличающуюся от матрицы Вс известной обратной [img: http://localhost:8080/file/031603-29.jpg] матрицей ранга 1 или (в случае симметричной матрицы В)симметричной матрицей ранга 2. Такая перестройка обратной матрицы может быть выполнена для матриц порядка пза [img: http://localhost:8080/file/031603-30.jpg] арифметич. операций. Примером может служить следующая формула (см. [4]): если [img: http://localhost:8080/file/031603-31.jpg] и [img: http://localhost:8080/file/031603-32.jpg] - векторы-столбцы, то [img: http://localhost:8080/file/031603-33.jpg] где [img: http://localhost:8080/file/031603-34.jpg] считается отличным от нуля. С точки зрения теории вычислительной сложности задача О. м. общего вида имеет (на последовательной машине) сложность того же порядка, что и задача решения линейной системы (при выполнении нек-рых естественных условий на скорость роста сложности обеих задаче увеличением их порядка [5]). Эта сложность имеет порядок, не превышающий nlog2 7.