lu

LU-разложение матрицы

Описание

пример

[L,U] = lu(A) разлагает на множители полную или разреженную матрицу A в верхнюю треугольную матрицу U и переставленный нижний треугольный матричный L таким образом, что A = L*U.

пример

[L,U,P] = lu(A) также возвращает матрицу перестановок P таким образом, что A = P'*L*U. С этим синтаксисом, L нижний треугольный модуль и U верхний треугольный.

пример

[L,U,P] = lu(A,outputForm) возвращает P в форме, заданной outputForm. Задайте outputForm как 'vector' возвратить P как сочетание векторизовали таким образом что A(P,:) = L*U.

пример

[L,U,P,Q] = lu(S) разлагает на множители разреженную матрицу S в модуль нижний треугольный матричный L, верхняя треугольная матрица U, матрица перестановок строки P, и матрица перестановок столбца Q, таким образом, что P*S*Q = L*U.

[L,U,P,Q,D] = lu(S) также возвращает диагональный масштабирующийся матричный D таким образом, что P*(D\S)*Q = L*U. Как правило, масштабирование строки приводит к более разреженной и более устойчивой факторизации.

[___] = lu(S,thresh) задает пороги для вертящейся стратегии, используемой lu использование любой из предыдущих комбинаций выходного аргумента. В зависимости от количества заданных выходных аргументов, значение по умолчанию и требования для thresh вход отличается. Смотрите thresh описание аргумента для деталей.

пример

[___] = lu(___,outputForm) возвращает P и Q в форме, заданной outputForm. Задайте outputForm как 'vector' возвратить P и Q как векторы сочетания. Можно использовать любую из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Вычислите LU-факторизацию матрицы и исследуйте получившиеся факторы. LU-факторизация является способом анализировать матрицу A в верхнюю треугольную матрицу U, нижняя треугольная матрица L, и матрица перестановок P таким образом, что PA=LU. Эти матрицы описывают шаги, должен был выполнить Исключение Гаусса на матрице, пока это не находится в приведенном ступенчатом по строкам виде матрицы. L матрица содержит все множители и матрицу перестановок P счета на обмены строки.

Создайте 3х3 матрицу и вычислите факторы LU.

A = [10 -7 0
     -3  2 6
      5 -1 5];
[L,U] = lu(A)
L = 3×3

    1.0000         0         0
   -0.3000   -0.0400    1.0000
    0.5000    1.0000         0

U = 3×3

   10.0000   -7.0000         0
         0    2.5000    5.0000
         0         0    6.2000

Умножьте факторы, чтобы воссоздать A. С 2D входным синтаксисом, lu включает матрицу перестановок P непосредственно в L фактор, такой, что L быть возвращенным является действительно P'*L и таким образом A = L*U.

L*U
ans = 3×3

   10.0000   -7.0000         0
   -3.0000    2.0000    6.0000
    5.0000   -1.0000    5.0000

Можно задать три выходных параметров, чтобы разделить матрицу перестановок от множителей в L.

[L,U,P] = lu(A)
L = 3×3

    1.0000         0         0
    0.5000    1.0000         0
   -0.3000   -0.0400    1.0000

U = 3×3

   10.0000   -7.0000         0
         0    2.5000    5.0000
         0         0    6.2000

P = 3×3

     1     0     0
     0     0     1
     0     1     0

P'*L*U
ans = 3×3

   10.0000   -7.0000         0
   -3.0000    2.0000    6.0000
    5.0000   -1.0000    5.0000

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

Создайте матрицу магического квадрата 5 на 5 и решите линейную систему Ax=b со всеми элементами b равняйтесь 65, волшебная сумма. С тех пор 65 волшебная сумма для этой матрицы (все строки и столбцы добавляют к 65), ожидаемое решение для x вектор 1 с.

A = magic(5);
b = 65*ones(5,1);
x = A\b
x = 5×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000

Для типовых квадратных матриц оператор обратной косой черты вычисляет решение линейной системы с помощью LU-разложения. LU-разложение описывает A когда продукт треугольных матриц и линейные системы, включающие треугольные матрицы, легко решены с помощью формул замены.

Чтобы воссоздать ответ, вычисленный обратной косой чертой, вычислите LU-разложение A. Затем используйте факторы, чтобы решить две треугольных линейных системы:

y = L\(P*b);
x = U\y;

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

[L,U,P] = lu(A)
L = 5×5

    1.0000         0         0         0         0
    0.7391    1.0000         0         0         0
    0.4783    0.7687    1.0000         0         0
    0.1739    0.2527    0.5164    1.0000         0
    0.4348    0.4839    0.7231    0.9231    1.0000

U = 5×5

   23.0000    5.0000    7.0000   14.0000   16.0000
         0   20.3043   -4.1739   -2.3478    3.1739
         0         0   24.8608   -2.8908   -1.0921
         0         0         0   19.6512   18.9793
         0         0         0         0  -22.2222

P = 5×5

     0     1     0     0     0
     1     0     0     0     0
     0     0     0     0     1
     0     0     1     0     0
     0     0     0     1     0

y = L\(P*b);
x = U\y
x = 5×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000

decomposition объект также полезен, чтобы решить линейные системы с помощью специализированных факторизаций, поскольку вы получаете многие выигрыши в производительности предварительного вычисления матричных факторов, но вы не должны знать, как использовать факторы. Используйте объект разложения с 'lu' введите, чтобы воссоздать те же результаты.

dA = decomposition(A,'lu');
x = dA\b
x = 5×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000

Вычислите LU-факторизацию разреженной матрицы и проверьте идентичность L*U = P*S*Q.

Создайте 60 60 разреженную матрицу смежности графика возможности соединения Buckminster-более-полного геодезического купола.

S = bucky;

Вычислите LU-факторизацию S использование синтаксиса разреженной матрицы с четырьмя выходными параметрами, чтобы возвратить матрицы сочетания строки и столбца.

[L,U,P,Q] = lu(S);

Переставьте строки и столбцы S с P*S*Q и сравните результат с умножением треугольных множителей L*U. 1 норма их различия в ошибке округления, указывая на тот L*U = P*S*Q.

e = P*S*Q - L*U;
norm(e,1)
ans = 2.4425e-15

Вычислите LU-факторизацию матрицы. Сохраните память путем возврата сочетаний строки как вектора вместо матрицы.

Создайте случайную матрицу 1000 на 1000.

A = rand(1000);

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

[L1,U1,P] = lu(A);
[L2,U2,p] = lu(A,'vector');
whos P p
  Name         Size                Bytes  Class     Attributes

  P         1000x1000            8000000  double              
  p            1x1000               8000  double              

Используя вектор сочетания также сохраняет на времени выполнения в последующих операциях. Например, можно использовать предыдущие LU-факторизации, чтобы решить линейную систему Ax=b. Несмотря на то, что решения, полученные из вектора сочетания и матрицы перестановок, эквивалентны (чтобы округлить), решение с помощью вектора сочетания обычно требует немного меньшего количества времени.

Сравните результаты вычисления LU-факторизации разреженной матрицы с и без сочетаний столбца.

Загрузите west0479 матрица, которая является с действительным знаком 479 479 разреженная матрица.

load west0479
A = west0479;

Вычислите LU-факторизацию A путем вызова lu с тремя выходными параметрами. Сгенерируйте графики шпиона L и факторов U.

[L,U,P] = lu(A);
subplot(1,2,1)
spy(L)
title('L factor')
subplot(1,2,2)
spy(U)
title('U factor')

Figure contains 2 axes objects. Axes object 1 with title L factor contains an object of type line. Axes object 2 with title U factor contains an object of type line.

Теперь вычислите LU-факторизацию A использование lu с четырьмя выходными параметрами, который переставляет столбцы A сокращать количество ненулей в факторах. Получившиеся факторы намного более разреженны, чем, если сочетания столбца не используются.

[L,U,P,Q] = lu(A);
subplot(1,2,1)
spy(L)
title('L factor')
subplot(1,2,2)
spy(U)
title('U factor')

Figure contains 2 axes objects. Axes object 1 with title L factor contains an object of type line. Axes object 2 with title U factor contains an object of type line.

Входные параметры

свернуть все

Введите матрицу. A может быть полным или разреженным, а также квадратным или прямоугольным в размере.

Типы данных: single | double
Поддержка комплексного числа: Да

Разреженная входная матрица. S может быть квадратным или прямоугольным в размере.

Типы данных: double
Поддержка комплексного числа: Да

Вертящиеся пороги для разреженных матриц в виде скалярного или двухэлементного вектора. Допустимые значения находятся в интервале [0 1]. Путем вы задаете thresh зависит от того, скольких выходные параметры заданы в вызове lu:

  • Для трех выходных параметров или меньше, thresh должен быть скаляр, и значением по умолчанию является 1.0.

  • Для четырех выходных параметров или больше, thresh может быть скаляр или два вектора элемента. Значением по умолчанию является [0.1 0.001]. Если вы задаете thresh как скаляр, затем это только заменяет первое значение в векторе.

На высоком уровне этот вход позволяет вам сделать компромиссы между точностью и общее время выполнения. Меньшие значения thresh будьте склонны приводить к более разреженным факторам LU, но решение может стать неточным. Большие значения могут привести к более точному решению (но не всегда), и обычно увеличение общей работы и использования памяти.

lu выбирает вертящуюся стратегию, базирующуюся сначала на количестве выходных аргументов и вторую на свойствах разлагаемой на множители матрицы. Во всех случаях, устанавливая пороговое значение (значения) на 1.0 результаты в частичном повороте, при установке их на 0 заставляет центры быть выбранными только на основе разреженности получившейся матрицы. Все значения L имейте абсолютное значение 1/min(thresh) или меньше.

  • Три или меньше выходных аргументов — алгоритм выбирает диагональный центр, если это удовлетворяет уравнению

    A(j,j) >= thresh * max(abs(A(j:m,j)))
    В противном случае это выбирает строку, которая содержит элемент самого большого абсолютного значения.

  • Симметричная вертящаяся стратегия — если S квадратная разреженная матрица с в основном симметричной структурой и в основном ненулевой диагональю, затем lu использует симметричную вертящуюся стратегию. Для этой стратегии алгоритм выбирает диагональный центр j если это удовлетворяет неравенству:

    A(i,j) >= thresh(2) * max(abs(A(j:m,j)))
    Если диагональный элемент проваливает этот тест, то lu выбирает самую разреженную строку i удовлетворение неравенству:
    A(i,j) >= thresh(1) * max(abs(A(j:m,j)))

  • Несимметричная вертящаяся стратегия — если S не удовлетворяет требованиям для симметричной вертящейся стратегии, затем lu использует несимметричную стратегию. В этом случае, lu выбирает самую разреженную строку i удовлетворение неравенству:

    A(i,j) >= thresh(1) * max(abs(A(j:m,j)))
    Значение 1.0 для thresh(1) результаты в обычном частичном повороте. Записи в L имейте абсолютное значение 1/thresh(1) или меньше. Второй элемент thresh входной вектор не используется с несимметричной стратегией.

Примечание

В некоторых редких случаях неправильная факторизация приводит к P*S*QL*U. Если это происходит, увеличение thresh к максимуму 1.0 (регулярный частичный поворот), и попробовали еще раз.

Форма сочетания выходные параметры в виде 'matrix' или 'vector'. Этот флаг управляет ли lu возвращает сочетания строки P и сочетания столбца Q как матрицы сочетания или векторы сочетания.

Как матрицы, выходные параметры P и Q удовлетворите этим тождествам:

  • Три выходных параметров — P удовлетворяет P*A = L*U.

  • Четыре выходных параметров — P и Q удовлетворите P*S*Q = L*U.

  • Пять выходных параметров — PQ, и D удовлетворите P*(D\S)*Q = L*U.

Как векторы, выходные параметры P и Q удовлетворите этим тождествам:

  • Три выходных параметров — P удовлетворяет A(P,:) = L*U

  • Четыре выходных параметров — P и Q удовлетворите S(P,Q) = L*U

  • Пять выходных параметров — PQ, и D удовлетворите D(:,P)\S(:,Q) = L*U.

Пример: [L,U,P] = lu(A,'vector')

Выходные аргументы

свернуть все

Фактор Нижней треугольной, возвращенный как матрица. Форма L зависит от ли сочетания строки P возвращены в отдельном выходе:

  • Если третий выход P задан, затем L возвращен как модуль нижняя треугольная матрица (то есть, нижняя треугольная матрица с 1 с на основной диагонали).

  • Если третий выход P не задан, затем L возвращен как сочетание строки модуля нижняя треугольная матрица. А именно, это - продукт P'*L из выходных параметров P и L возвращенный в трех выходных случаях.

Фактор Верхней треугольной, возвращенный как верхняя треугольная матрица.

Сочетание строки, возвращенное как матрица перестановок или, если 'vector' опция задана как вектор сочетания. Используйте этот выход, чтобы улучшить числовую устойчивость вычисления.

Смотрите outputForm для описания тождеств, которым удовлетворяет этот выход.

Сочетание столбца, возвращенное как матрица перестановок или, если 'vector' опция задана как вектор сочетания. Используйте этот выход, чтобы уменьшать временную замену (количество ненулей) в факторах разреженной матрицы.

Смотрите outputForm для описания тождеств, которым удовлетворяет этот выход.

Масштабирование строки, возвращенное как диагональная матрица. D используется, чтобы масштабировать значения в S таким образом, что P*(D\S)*Q = L*U. Как правило, но не всегда, масштабирование строки приводит к более разреженной и более устойчивой факторизации.

Алгоритмы

LU-факторизация вычисляется с помощью варианта Исключения Гаусса. Вычисление точного решения зависит от значения числа обусловленности исходного матричного cond(A). Если матрица имеет большое число обусловленности (это почти сингулярно), то вычисленная факторизация не может быть точной.

LU-факторизация является ключевым шагом в получении инверсии с inv и определитель с det. Это - также базис для решения для линейного уравнения или матричного деления, полученного с операторами \ и /. Это обязательно означает что числовые ограничения lu также присутствуют в этих зависимых функциях.

Расширенные возможности

Смотрите также

| | | | | | |

Представлено до R2006a