分解
介绍
在这一节中讨论的所有三个矩阵的分解利用三角矩阵,对角线上方或下方的所有元素为零。涉及三角矩阵的线性方程组轻松快速地解决了使用向前或回来替换。
柯列斯基分解
柯列斯基分解表达一个对称矩阵三角矩阵及其转置的产物
一个=R′R,
在哪里R是一个上三角矩阵。
并不是所有的对称矩阵可以分解以这种方式;这种分解的矩阵是正定的。这意味着所有的对角元素一个是积极的,而非对角元素是“不太大。“帕斯卡矩阵提供了一个有趣的例子。在本章的例子矩阵一个
3×3的帕斯卡一直是矩阵。暂时切换到6-by-6:
=帕斯卡(6)= 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 126 252 35 70 126 1 6 21 56
的元素一个
二项式系数。每个元素是北部和西部邻国的总和。柯列斯基分解的
R =胆固醇(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 0 0 0 0 1 5 0 0 0 0 0 1
再次二项式系数的元素。这一事实‘* R
等于一个
演示了一个身份涉及大笔的二项式系数的产物。下载188bet金宝搏
柯列斯基分解允许线性系统
斧头=b
,取而代之的是
R′Rx=b。
因为反斜杠符识别三角系统,这在MATLAB可以解决®环境下迅速
x = R \ (R \ b)
如果一个
是n——- - - - - -n的计算复杂度胆固醇(A)
是O (n3),但是随后的反斜杠的复杂性的解决方案仅为O (金宝搏官方网站n2)。
LU分解
LU分解或高斯消去法,表达任何方阵一个的产品排列的下三角矩阵和一个上三角矩阵
一个=陆,
在哪里l是一个排列的下三角矩阵的对角线和U是一个上三角矩阵。
的排列是必要的理论和计算的原因。矩阵
可以表示为三角矩阵的乘积,什么时候ε很小,因素中的元素大,放大错误,所以即使排列并不必要,他们是可取的。部分旋转确保的元素l是由一个有限大小的元素U并不比那些更大的一个。
例如:
陆[L U] = (B) L = 1.0000 0 0 0 0.3750 0.5441 1.0000 0.5000 1.0000 U = 8.0000 5.2941 1.0000 - 6.0000 8.5000 - -1.0000 0 0
LU分解的一个
允许线性系统
A * x =
迅速得到解决
x = U \ (L \ b)
的决定因素和逆计算LU分解使用
依据(A) =侦破(L) *侦破(U)
和
发票(A) =发票(U) *发票(左)
您还可以使用计算行列式依据(A) = prod(诊断接头(U))
的迹象,但决定因素可能会逆转。
QR分解
一个正交与正交矩阵、矩阵列,是一个真正的矩阵的列都有单位长度和互相垂直。如果问是正交的,那么
问T问=我,
在哪里我是单位矩阵。
最简单的二维坐标旋转正交矩阵:
对于复杂的矩阵,对应的术语统一的。正交和酉矩阵的数值计算,因为他们保持长度、保护角度,不要放大错误。
正交或QR分解表达任何矩形矩阵正交的产物或酉矩阵和一个上三角矩阵。一列排列也可以参与进来:
一个=QR
或
美联社=QR,
在哪里问正交或单一,R是上三角,P是一个排列。
有四个不同的QR factorization-full或经济规模,并有或没有列排列。
超定的线性系统包括一个矩形矩阵比列,行米——- - - - - -n与米>n。全尺寸的QR分解产生一个广场,米——- - - - - -米正交问和一个矩形米——- - - - - -n上三角R:
C =画廊(uniformdata, 4 [5], 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.7245 0.3474 -0.0126 0 0 0.9320 0.6596 0.6648 0 0 0 0 0 0 0
在许多情况下,最后一次m - n列问因为它们不需要乘以0的底部吗R。因此,大包装QR分解产生一个矩形,米——- - - - - -n问与正交列和一个正方形n——- - - - - -n上三角R。5-by-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.7245 0.3474 -0.0126 0 0 0 0 0 0.6596 0.9320 0.6648
相比之下LU分解,QR分解不需要任何旋转或排列。但一个可选的列排列,由第三个输出参数的存在,有助于检测奇异点或等级不足。分解的每一步,其余unfactored矩阵的列与最大这一步规范作为依据。这可以确保的对角元素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 7.2460 R = -11.3578 - -8.2762 0 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 7.2460 R = -11.3578 - -8.2762 0 p = 2 1
的QR分解将一个超定的线性系统转化为一个等价的三角系统。表达式
规范(A * x - b)
=
规范(Q * R * x - b)
由正交矩阵保存欧几里得范数乘法,所以这个表达式也等于
规范(R * x - y)
在哪里y =问' * b
。自从上次米- - - - - -n行R为零,这个表达式优惠分为两块:
规范(R (1: n, 1: n) * x - y (1: n))
和
规范(y (n + 1: m))
当一个
满秩,可以解决x
所以,第一个表达式是零。第二个表达式给出了残余的规范。当一个
没有满秩,三角形结构的R
可以找到一个最小二乘问题的基本解决方案。
使用多线程计算分解
MATLAB软件支持多线程计算的金宝app线性代数和element-wise数值函数。这些函数自动执行多个线程。函数或表达式执行得更快在多个cpu,大量的条件必须是真实的:
函数执行操作容易分区为并发执行的部分。这些部分必须能够执行进程之间的通信。他们应该需要几个顺序操作。
数据规模足够大,这样任何并发执行的优势超过分区数据所需的时间和管理单独的执行线程。例如,大多数功能加速只有当该数组包含几千元素或更多。
操作不是内存受限的;处理时间不是由内存访问时间。作为一般规则,复杂的功能加速超过简单的功能。