LUP-разложение

LUP-разложение (LUP-декомпозиция) — представление данной матрицы <math>A</math> в виде произведения <math>PA = LU</math> где матрица <math>L</math> является нижнетреугольной с единицами на главной диагонали, <math>U</math> — верхнетреугольная общего вида, а <math>P</math> — т. н. матрица перестановок, получаемая из единичной матрицы путём перестановки строк или столбцов. Такое разложение можно осуществить для любой невырожденной матрицы. LUP-разложение используется для вычисления обратной матрицы по компактной схеме, вычисления решения системы линейных уравнений. По сравнению с алгоритмом LU-разложения алгоритм LUP-разложения может обрабатывать любые невырожденные матрицы и при этом обладает более высокой устойчивостью.

Алгоритм LUP-разложения

Пусть <math>A=(a_{ij})</math>, <math>L=(l_{ij})</math>, <math>U=(u_{ij})</math>. На практике как правило вместо матрицы перестановок P используют вектор перестановок получаемый из вектора <math>p_{i}=(1, 2, ..., n)</math> путём перестановки элементов соответствующих номерам строк переставляемых в матрице P. Например, если

<math>P = \begin{pmatrix}

 0 & 1 & 0 \\
 1 & 0 & 0 \\
 0 & 0 & 1 \\

\end{pmatrix} </math>

то <math>p = (2, 1, 3)</math> так как матрица P получена путём перестановки первой и второй строки. Вычисление LUP-разложения ведётся в несколько шагов. Пусть матрица C = A. На каждом i-м шаге сначала производится поиск опорного (ведущего) элемента — максимального по модулю элемента среди элементов i-го столбца, находящихся не выше i-й строки, после чего строка с опорным элементом меняется местами с i-й строкой. Одновременно производится такой же обмен в матрице P. При этом, если матрица невырождена, то опорный элемент гарантированно будет отличен от нуля. После этого все элементы текущего i-го столбца, находящиеся ниже i-й строки, делятся на опорный. Далее из всех элементов <math>c_{jk}</math> находящихся ниже i-й строки и i-го столбца (то есть таких что j>i и k>i) вычитается произведение <math>c_{ji}c_{ik}</math>. После этого счётчик i увеличивается на единицу и процесс повторяется пока i<n где n — размерность исходной матрицы. После того как все шаги будут выполнены матрица C будет представлять собой следующую сумму:

<math>C = L+U-E</math>

где E — единичная матрица.

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

Реализация алгоритма на языке С++

Ниже представлен программный код приведённого выше алгоритма на языке С++. Здесь Matrix — некоторый контейнер, поддерживающий операцию индексирования. Обратите внимание, что отсчёт ведётся с нуля, а не с единицы.

void LUP(const Matrix &A, Matrix &C, Matrix &P) {
    //n - размерность исходной матрицы
    const int n = A.Rows();

    C = A;

    //загружаем в матрицу P единичную матрицу
    P = IdentityMatrix();

    for( int i = 0; i < n; i++ ) {
        //поиск опорного элемента
        double pivotValue = 0;
        int pivot = -1;
        for( int row = i; row < n; row++ ) {
            if( fabs(C[ row ][ i ]) > pivotValue ) {
                pivotValue = fabs(C[ row ][ i ]);
                pivot = row;
            }
        }
        if( pivotValue == 0 ) {
            error("Матрица вырождена");
            return;
        }

        //меняем местами i-ю строку и строку с опорным элементом
        P.SwapRows(pivot, i);
        C.SwapRows(pivot, i);
        for( int j = i+1; j < n; j++ ) {
            C[ j ][ i ] /= C[ i ][ i ];
            for( int k = i+1; k < n; k++ ) 
                C[ j ][ k ] -= C[ j ][ i ] * C[ i ][ k ];
        }
    }
}

//теперь матрица C = L + U - E

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Отрывок, характеризующий LUP-разложение

– Матёрый, ваше сиятельство, – отвечал Данила, поспешно снимая шапку.
Граф вспомнил своего прозеванного волка и свое столкновение с Данилой.
– Однако, брат, ты сердит, – сказал граф. – Данила ничего не сказал и только застенчиво улыбнулся детски кроткой и приятной улыбкой.


Старый граф поехал домой; Наташа с Петей обещались сейчас же приехать. Охота пошла дальше, так как было еще рано. В середине дня гончих пустили в поросший молодым частым лесом овраг. Николай, стоя на жнивье, видел всех своих охотников.
Насупротив от Николая были зеленя и там стоял его охотник, один в яме за выдавшимся кустом орешника. Только что завели гончих, Николай услыхал редкий гон известной ему собаки – Волторна; другие собаки присоединились к нему, то замолкая, то опять принимаясь гнать. Через минуту подали из острова голос по лисе, и вся стая, свалившись, погнала по отвершку, по направлению к зеленям, прочь от Николая.
Он видел скачущих выжлятников в красных шапках по краям поросшего оврага, видел даже собак, и всякую секунду ждал того, что на той стороне, на зеленях, покажется лисица.
Охотник, стоявший в яме, тронулся и выпустил собак, и Николай увидал красную, низкую, странную лисицу, которая, распушив трубу, торопливо неслась по зеленям. Собаки стали спеть к ней. Вот приблизились, вот кругами стала вилять лисица между ними, всё чаще и чаще делая эти круги и обводя вокруг себя пушистой трубой (хвостом); и вот налетела чья то белая собака, и вслед за ней черная, и всё смешалось, и звездой, врозь расставив зады, чуть колеблясь, стали собаки. К собакам подскакали два охотника: один в красной шапке, другой, чужой, в зеленом кафтане.
«Что это такое? подумал Николай. Откуда взялся этот охотник? Это не дядюшкин».
Охотники отбили лисицу и долго, не тороча, стояли пешие. Около них на чумбурах стояли лошади с своими выступами седел и лежали собаки. Охотники махали руками и что то делали с лисицей. Оттуда же раздался звук рога – условленный сигнал драки.
– Это Илагинский охотник что то с нашим Иваном бунтует, – сказал стремянный Николая.
Николай послал стремяного подозвать к себе сестру и Петю и шагом поехал к тому месту, где доезжачие собирали гончих. Несколько охотников поскакало к месту драки.
Николай слез с лошади, остановился подле гончих с подъехавшими Наташей и Петей, ожидая сведений о том, чем кончится дело. Из за опушки выехал дравшийся охотник с лисицей в тороках и подъехал к молодому барину. Он издалека снял шапку и старался говорить почтительно; но он был бледен, задыхался, и лицо его было злобно. Один глаз был у него подбит, но он вероятно и не знал этого.
– Что у вас там было? – спросил Николай.
– Как же, из под наших гончих он травить будет! Да и сука то моя мышастая поймала. Поди, судись! За лисицу хватает! Я его лисицей ну катать. Вот она, в тороках. А этого хочешь?… – говорил охотник, указывая на кинжал и вероятно воображая, что он всё еще говорит с своим врагом.
Николай, не разговаривая с охотником, попросил сестру и Петю подождать его и поехал на то место, где была эта враждебная, Илагинская охота.