Все три из матричных факторизаций, обсужденных в этом разделе, используют треугольные матрицы, где все элементы любой выше или ниже диагонали - нуль. Системы линейных уравнений, включающих треугольные матрицы, легко и быстро решены с помощью или вперед или задняя замена.
Факторизация Холесского выражает симметрическую матрицу как продукт треугольной матрицы и транспонировала
A = R ′R,
где R является верхней треугольной матрицей.
Не все симметричные матрицы могут быть учтены таким образом; матрицы, которые имеют такую факторизацию, как говорят, положительны определенный. Это подразумевает, что все диагональные элементы A положительны и что недиагональные элементы являются “не слишком большими”. Матрицы Паскаля обеспечивают интересный пример. В этой главе матрица в качестве примера A был 3х3 матрицей Паскаля. Переключатель Temporarily к 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 (n 3), но сложность последующих решений для наклонной черты влево только O (n 2).
LU-факторизация или Исключение Гаусса, выражает любую квадратную матрицу A как продукт перестановки нижней треугольной матрицы и верхней треугольной матрицы
A = LU,
где 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.2941LU-факторизация 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 является ортогональным, то
Q ′Q = 1.
Самые простые ортогональные матрицы являются двумерными координатными вращениями:
Для комплексных матриц соответствующий термин унитарен. Ортогональные и унитарные матрицы желательны для численного расчета, потому что они сохраняют длину, сохраняют углы и не увеличивают ошибки.
Ортогональное, или 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 1QR-факторизация преобразовывает сверхрешительную линейную систему в эквивалентную треугольную систему. Выражение
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 элементов).