我的朋友吉尔斯特朗著称的讲座从麻省理工学院课程18.06,线性代数,它们可以在麻省理工学院开放课程。他现在是描述一个新的方法和一系列的主题视频,线性代数2020年愿景。这个愿景在一本新书,线性代数为每个人。

内容

CR分解

吉尔的方法将熟悉MATLAB用户和读者的博客。矩阵分解的关键组件——陆,QR,特征值和奇异值分解。但在他到达之前,吉尔喜欢从更基本的分解,一个= C * R,表示任何一个矩阵的矩阵作为一个产品描述列空间和矩阵描述行空间。

例如,也许第一个3×3矩阵谁写

一个=

1 2 3 4 5 6 7 8 9

注意到中间列是第一个和最后一个列的平均值,所以最明显的CR分解

C =

1 3 4 6 7 9

R =

1 0 0 0.5 0.5 1

但是,这不是唯一可能的CR分解。另一个,继续阅读。

CR分解工作漂亮的矩阵中遇到任何介绍线性代数。这些矩阵并不太大,他们的条目通常小整数。在输入数据没有错误,没有预计在随后的计算。但是,正如吉尔坦言,CR分解成为任何严重的技术使用不是一个竞争者。

的分解一个= C * R是rank_revealing。列的数量C必须相同的行数R。最小列数的产品C * R繁殖一个是定义是排名的一个。这里,前几天的课程,介绍了基本概念。它有许多名字,低秩近似模型降阶,主成分分析,它渗透到现代矩阵计算。看下罩在许多人工智能和ML的成功故事,你可能会发现类似于一个CR分解。

行简化阶梯形

我认为吉尔很高兴当他意识到一个不错的选择R一个老朋友,行简化阶梯形几十年来,在线性代数教科书。因为他们,你可能已经忘记或不知道,这些都是要求一个矩阵行简化阶梯形。

在上面的例子中,这个矩阵R是不行简化阶梯形,因为在第二行第一个非零元素不是一个1。

名称中的“减少”指的是每个领导1 0以上。计算简化型的算法称为高斯消去法。其计算复杂度比传统的高斯消元法增加了50%。

一个单位矩阵行简化阶梯形,如果一个广场和可逆的,也就是说,在一般情况下,有吗n线性无关的列,那么一个=C和R是n——- - - - - -n的身份。我们预计排名缺乏矩阵可以分解成更有趣的CR。

关于减少形式是一个重要的事实,它是独一无二的。不管你怎么计算它,有一个矩阵满足所有的标准在我们的项目符号列表。因此,如果我们需要R行简化阶梯形,CR的分解矩阵是独一无二的。

你可以看到MATLAB的源代码rref与

类型rref

80年我最初的功能之一pre-MathWorks Fortran MATLABrref,尽管它没有来自LINPACK或EISPACK。

函数cr

由于MATLAB已经rref,我花了五分钟,尽可能多的可执行文件,编写这个函数。

函数[C R] = cr (A) R = rref(一个);j =找到(和(双(R) ~ = 0) = = 1);%指数领先的。r =长度(j);% r =。R = R (1: R:);%删除所有零行R (:, j) = = (R)。C = (:, j);结束

事实上,我最初只有四个可执行的行rref还提供了指标j的列包含1的领先。但这只是如果类的一个是单或双。如果一个是一个信谊符号数学工具箱,让我计算j从R。

的列C是第一个r线性无关的列一个。来自所有的线性组合动作R。

的长度j数量,等级,是最重要的这个函数计算。一切都取决于它。

在我们的例子中,上面的一个,

[C R] = cr (A)

C =

1 2 4 5 7 8

R =

1 0 1 0 1 2

现在C的前两列一个和R是在行简化阶梯形(没有零行)。

魔法(4 * k)

我最喜欢的等级不足矩阵是魔术方块的MATLAB版本是4的倍数的大小。他们所有人,无论多么大,等级3。让我们找到CR分解魔法(8)。

=魔法(8)[C R] = cr (A)

= 64 2 3 61 60 6 7 57 9 55 54 12 13 51 50 16 17 47 46 20 21 43 42 24 40 26日27日37 36 30 31 33 32 34 35 29 28 38 39 25 41 23 22 44 45 19 18 48 49 15 14 52 53 11 10 56 8 58 59 62 63 1 C = 64 4 2 3 9 55 54 17 47 46 40 26日27日32 34 35 41 23 22 49 15 14 8 58 59 R = 1 0 0 1 1 0 0 1 0 1 0 3 4 3 4 7 0 0 1 3 4 5 7

这一事实C有三个列和R三行显示的吗一个是3。的列C的前三列一个。的前三行和列R形成3 x3的单位矩阵。的其余部分R包含生成所有的系数一个前三列。

我们看到的模式C和R来自算法生成的魔术方块订单4 * k。这里有块C和R为24-by-24幻方。

=魔法(24)[C R] = cr (A)情节(C)图(右)

west0479

我们不期望CR分解工作更大的矩阵与不精确的条目,但是让我们试一试。

矩阵west0479有一个古老的历史。维斯特伯格艺术,1983年,卡内基梅隆大学化学工程教授,贡献了11个矩阵从模型中提取化学工程植物Harwell-Boeing稀疏矩阵集合。其中的一个矩阵,west0479,是一个模型,一个蒸馏塔盛行一时。它是由- 479和479 - 1887 0的条目。

1990年,当我们介绍了稀疏矩阵在MATLAB中,包括我们west0479在演示目录中。它已经在所有后续版本可用。

清晰的负载west0479谁

类属性名称大小字节west0479 479 x479 34032双稀疏

今天,谷歌发现71个网页,提及west0479。我停止计数的图片在网络上生成的。

我们的cr将工作在稀疏矩阵,但快先转化成完整。

一= (west0479);[C R] = cr (A);r =大小(C, 2)

r = 479

所以,cr决定这个矩阵满秩,并返回了C=一个和R=我。不是很有用。

决斗rref

经仔细观察,我们发现rref一个可选的第二个输入参数命名托尔。看看,这将帮助我们计算一个更有用的CR分解。的帮助项说

(R, jb) = rref (A, TOL)使用给定的公差等级测试。

我写了rref年前,现在我必须说,这个描述不是很具体。应该说,任何列的还原过程中遇到最大的元素是小于或等于托尔是所有零所取代。

最大的元素west0479约为3.2 e5 e-6最小非零是1.0,所以元素范围/ 11个数量级。事实证明,只有两个非零矩阵有很多列条目,其中最大的是+ 1或- 1。所以,任何托尔大于1的原因rref忽略这些列。和任何托尔小于1包括那些列。这导致了过度的稀疏矩阵填写。

这个动画比较rref与托尔= 0.99来rref与托尔= 1.01。看的非零项间谍情节。的数托尔= 0.99上升到超过七次原始矩阵的计算,最后才有所下降。最后一个非零的数托尔= 1.01小于起始nnz。这不是一个好迹象。

最终,没有价值托尔产生一个CR接近原始矩阵分解,和任何其他值做任何更好。正如我们所料,CR不是有用的。

得到了MATLAB代码

发表与MATLAB®R2019b