Все три матричные факторизации, обсуждаемые в этом разделе, используют треугольные матрицы, где все элементы выше или ниже диагонали равны нулю. Системы линейных уравнений, включающие треугольные матрицы, легко и быстро решаются с помощью прямой или обратной подстановки.
Факторизация Холеского выражает симметричную матрицу как произведение треугольной матрицы и её транспонирование
A = R′R,
где R - верхняя треугольная матрица.
Не все симметричные матрицы могут быть факторизованы таким образом; матрицы, которые имеют такую факторизацию, считаются положительными определенными. Это подразумевает, что все диагональные элементы A являются положительными и что внедиагональные элементы являются «не слишком большими». Матрицы Паскаля являются интересным примером. В этой главе приводится пример матрицы 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
заменить на
R′Rx = b.
Поскольку оператор обратной косой черты распознает треугольные системы, это можно быстро решить в среде MATLAB ® с помощью
x = R\(R'\b)
Если A является n-by-n, вычислительная сложность chol(A) равно O (n3), но сложность последующих решений обратной косой черты равна только O (n2).
Факторизация LU, или гауссова элиминация, выражает любую квадратную матрицу A как произведение перестановки нижней треугольной матрицы и верхней треугольной матрицы
A = ЛОГИЧЕСКАЯ ЕДИНИЦА,
где L - перестановка нижней треугольной матрицы с единицами на её диагонали и U - верхней треугольной матрицы.
Перестановки необходимы как по теоретическим, так и по вычислительным причинам. Матрица
не может быть выражено как произведение треугольных матриц без замены его двух строк. Хотя матрица
может быть выражено в виде произведения треугольных матриц, когда λ мал, элементы в факторах велики и увеличивают ошибки, поэтому, даже если перестановки не являются строго необходимыми, они желательны. Частичное вращение гарантирует, что элементы 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Факторизация логической единицы 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)), хотя признаки определителей могут быть обращены вспять.
Ортогональная матрица, или матрица с ортонормированными столбцами, является вещественной матрицей, все столбцы которой имеют единичную длину и перпендикулярны друг другу. Если Q ортогональен, то
QTQ = I,
где I - единичная матрица.
Простейшими ортогональными матрицами являются двумерные повороты координат:
(
Для комплексных матриц соответствующий термин является унитарным. Ортогональные и унитарные матрицы желательны для числовых вычислений, поскольку они сохраняют длину, сохраняют углы и не увеличивают погрешности.
Ортогональная, или 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-на-n Q с ортонормированными столбцами и квадратным n-на-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 поддерживает многопоточные вычисления для ряда линейных алгебр и числовых функций. Эти функции автоматически выполняются в нескольких потоках. Для более быстрого выполнения функции или выражения на нескольких ЦП должно быть выполнено несколько условий:
Функция выполняет операции, которые легко разделяются на разделы, которые выполняются одновременно. Эти разделы должны быть способны выполнять с незначительным взаимодействием между процессами. Они должны требовать нескольких последовательных операций.
Размер данных достаточно велик, чтобы любые преимущества параллельного выполнения перевешивали время, необходимое для разделения данных и управления отдельными потоками выполнения. Например, большинство функций ускоряется, только если массив содержит несколько тысяч элементов или более.
Операция не привязана к памяти; время обработки не зависит от времени доступа к памяти. Как правило, сложные функции ускоряют более чем простые функции.
lu и qr показывают значительное увеличение скорости на больших массивах двойной точности (порядка 10 000 элементов).