Факторизации

Введение

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

Факторизация Холесского

Факторизация Холесского выражает симметричную матрицу как продукт треугольной матрицы и ее транспонирование

A = <reservedrangesplaceholder1> <reservedrangesplaceholder0>,

где R - верхняя треугольная матрица.

Не все симметричные матрицы могут быть факторизованы таким образом; говорят, что матрицы, которые имеют такую факторизацию, положительно определены. Это подразумевает, что все диагональные элементы A положительны и что off-диагональные элементы «не слишком большие». Матрицы Паскаля обеспечивают интересный пример. На протяжении всей этой главы пример матрицы A был матрицей Паскаля 3 на 3. Временно переключитесь на 6 на 6:

A = pascal(6)

A =
       1     1     1     1     1     1
       1     2     3     4     5     6
       1     3     6    10    15    21
       1     4    10    20    35    56
       1     5    15    35    70   126
       1     6    21    56   126   252

Элементы A являются биномиальными коэффициентами. Каждый элемент является суммой его северных и западных соседей. Это Факторизация Холесского

R = chol(A)

R =
     1     1     1     1     1     1
     0     1     2     3     4     5
     0     0     1     3     6    10
     0     0     0     1     4    10
     0     0     0     0     1     5
     0     0     0     0     0     1

Элементы снова являются биномиальными коэффициентами. Тот факт, что R'*R равно A демонстрирует тождества, включающую суммы продуктов биномиальных коэффициентов.

Примечание

Это Факторизация Холесского также относится к комплексным матрицам. Любая сложная матрица, которая имеет факторизацию Холесского, удовлетворяет

A′ = A

и говорят, что гермитин положительно определен.

Это Факторизация Холесского позволяет линейной системе

Ax = b

будет заменено на

<reservedrangesplaceholder3> <reservedrangesplaceholder2> <reservedrangesplaceholder1> = b.

Поскольку оператор обратной косой черты распознает треугольные системы, это может быть решено в MATLAB^® окружение быстро с

x = R\(R'\b)

Если A n -by - n, вычислительная сложность chol(A) is O (n³), но сложность последующих решений обратной косой черты только O (n²).

LU-факторизация

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

A = LU,

где L - сочетание нижней треугольной матрицы с таковыми на ее диагонали, а U - верхняя треугольная матрица.

Сочетания необходимы как по теоретическим, так и по вычислительным причинам. Матрица

$[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}]$

не может быть выражено как продукт треугольных матриц, не меняя их две строки. Хотя матрица

$[\begin{matrix} ε & 1 \\ 1 & 0 \end{matrix}]$

может быть выражено как продукт треугольных матриц, когда ε мало, элементы в факторах большие и увеличивают ошибки, поэтому, даже несмотря на то, что сочетания не являются строго необходимыми, они желательны. Частичное вращение гарантирует, что элементы L ограничены одним по величине и что элементы U не намного больше, чем элементы A.

Для примера:

[L,U] = lu(B)

L =
    1.0000         0         0
    0.3750    0.5441    1.0000
    0.5000    1.0000         0

U =
    8.0000    1.0000    6.0000
         0    8.5000   -1.0000
         0         0    5.2941

LU-факторизация A позволяет линейную систему

A*x = b

чтобы быть решенным быстро с

x = U\(L\b)

Определяющие и обратные значения вычисляются из LU-факторизации с помощью

det(A) = det(L)*det(U)

inv(A) = inv(U)*inv(L)

Можно также вычислить определяющих с помощью det(A) = prod(diag(U))хотя признаки определяющих могут быть обращены вспять.

QR-факторизация

Ортогональная матрица или матрица с ортонормальными столбцами - это действительная матрица, столбцы которой все имеют единичную длину и перпендикулярны друг другу. Если Q ортогональна, то

Q^TQ = I,

где I - матрица тождеств.

Простейшие ортогональные матрицы являются двумерными вращениями координат:

$[\begin{matrix} \cos (θ) & \sin (θ) \\ - \sin (θ) & \cos (θ) \end{matrix}] .$

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

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

A = QR

или

AP = QR,

где Q ортогональна или унитарна, R - верхняя треугольная, а P - сочетание.

Существует четыре варианта QR-факторизации - полный или экономичный размер, и с сочетанием столбца или без.

Переопределенные линейные системы включают прямоугольную матрицу с большим количеством строк, чем столбцы, то есть m -by - n с m > n. Полноразмерное QR-факторизация создает квадратный, m -by m ортогональный Q и прямоугольный m -by n верхний треугольный R:

C=gallery('uniformdata',[5 4], 0);
[Q,R] = qr(C)

Q =

    0.6191    0.1406   -0.1899   -0.5058    0.5522
    0.1506    0.4084    0.5034    0.5974    0.4475
    0.3954   -0.5564    0.6869   -0.1478   -0.2008
    0.3167    0.6676    0.1351   -0.1729   -0.6370
    0.5808   -0.2410   -0.4695    0.5792   -0.2207


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648
         0         0         0         0

Во многих случаях последние m – n столбцы Q не нужны, потому что они умножаются на нули в нижнем фрагменте R. Таким образом, QR-факторизация экономического размера создает прямоугольный, m -by n Q с ортонормальными столбцами и квадратным n -by n верхним треугольным R. Для примера 5 на 4 это немного сохранение, но для больших, сильно прямоугольных матриц экономия как времени, так и памяти может оказаться довольно важной:

[Q,R] = qr(C,0)	
Q =

    0.6191    0.1406   -0.1899   -0.5058
    0.1506    0.4084    0.5034    0.5974
    0.3954   -0.5564    0.6869   -0.1478
    0.3167    0.6676    0.1351   -0.1729
    0.5808   -0.2410   -0.4695    0.5792


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648

В отличие от LU-факторизации, QR-факторизация не требует никакого поворота или сочетаний. Но необязательное сочетание столбца, вызванная наличием третьего выходного аргумента, полезно для обнаружения особенности или дефицита ранга. На каждом шаге факторизации в качестве базиса для этого шага используется столбец оставшейся не факторизованной матрицы с наибольшей нормой. Это гарантирует, что диагональные элементы R происходят в порядке уменьшения и что любая линейная зависимость среди столбцов почти наверняка обнаруживается путем исследования этих элементов. Для небольшого примера, приведенного здесь, второй столбец C имеет большую норму, чем первая, поэтому происходит обмен двумя столбцами:

[Q,R,P] = qr(C)

Q =
   -0.3522    0.8398   -0.4131
   -0.7044   -0.5285   -0.4739
   -0.6163    0.1241    0.7777

R =
  -11.3578   -8.2762
         0    7.2460
         0         0

P =
     0     1
     1     0

Когда экономический размер и сочетания столбца объединяются, третий выходной аргумент является вектором сочетания, а не матрицей сочетания:

[Q,R,p] = qr(C,0)

Q =
   -0.3522    0.8398
   -0.7044   -0.5285
   -0.6163    0.1241

R =
  -11.3578   -8.2762
         0    7.2460


p =
     2     1

QR-факторизация преобразует переопределенную линейную систему в эквивалентную треугольную систему. Выражение

norm(A*x - b)

равняется

norm(Q*R*x - b)

Умножение на ортогональные матрицы сохраняет евклидову норму, поэтому это выражение также равно

norm(R*x - y)

где y = Q'*b. Поскольку последние m - n строки R равны нулю, это выражение разбивается на две части:

norm(R(1:n,1:n)*x - y(1:n))

norm(y(n+1:m))

Когда A имеет полный ранг, можно решить за x так что первое из этих выражений равняется нулю. Затем второе выражение приводит норму невязки. Когда A не имеет полного ранга, треугольной структуры R позволяет найти базовое решение задачи наименьших квадратов.

Использование многопоточных расчетов для факторизации

MATLAB поддерживает многопоточные расчеты для ряда линейных алгебр и поэлементных числовых функций. Эти функции автоматически выполняются в нескольких потоках. Чтобы функция или выражение выполнялись быстрее на нескольких центральных процессорах, ряд условий должен быть true:

Функция выполняет операции, которые легко разделяются на разделы, которые выполняются одновременно. Эти разделы должны быть способны выполняться при ограниченной коммуникации между процессами. Они должны потребовать мало последовательных операций.
Размер данных достаточно велик, так что любые преимущества параллельного выполнения перевешивают время, необходимое для разбиения данных и управления отдельными потоками выполнения. Для примера большинство функций ускоряются только тогда, когда массив содержит несколько тысяч элементов и более.
Операция не связана с памятью; время вычислений не определяется временем доступа к памяти. Как общее правило, сложные функции ускоряют больше, чем простые функции.

lu и qr показать значительное увеличение скорости на больших массивах двойной точности (порядка 10 000 элементов).

См. также

chol | lu | qr

Документация