Все три из матричных факторизаций, обсужденных в этом разделе, используют треугольные матрицы, где все элементы любой выше или ниже диагонали - нуль. Системы линейных уравнений, включающих треугольные матрицы, легко и быстро решены с помощью или вперед или задняя замена.
Факторизация Холесского выражает симметрическую матрицу как продукт треугольной матрицы и транспонировала
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 элементов).