矩阵因式分解——在游戏中的应用

假如你是某市的市长，自上岗一来一直兢兢业业，不是给人民修水坝储存水资源，就是给人民修收费站提供就业岗位。

一天，你正拿着茶杯在喝茶，上头突然来了文件，要求你的城市十年后这个时候人口数量增长到现在的169%。

嗯，如果你的现在的人口为x，那么你很容易算出十年后的人口y为

                                                            y = 1.69x

不过，这个增长率要求着实不低，十年内不可控因素太多了。因此，你得先定它个小目标，比如定个五年计划，弄清楚每五年的增长率。你很快就发现，1.69 = 1.3 * 1.3，你的人口每五年增长率要达到30%才能完成上头的目标。

作为一个好市长，你立马开始研究要在哪儿建立红灯区。但你电脑还没打开，上头又一通电话过来，说，需求改了，你需要控制十年时间后控制郊区-城市的人口，又给了你一份文件:

这个矩阵中的数字的每个单位表示100%，即郊区自己要增长到是现在800%的人口，还要额外分出200%的人口去城市。城市自己增长到900%的人口，还要额外分出100%的人口去支援郊区。注意，这儿的百分比是相对于计划开始前来说。

你粗略算了一下，假设现在城市有100人，郊区有100人，城市自己增长到900%就是900人，郊区再赶过来800%就是800人，十年后城市一共有1700人。郊区同理，十年后为300人。

你不知道，上头为什么天天改需求，你也不知道，明明你的城区公共交通堵了已经有一年多了，为什么还有那么人往你的城市跑。增长20倍的人口啊，经济肯定吃不消，还是多修几个收费站吧。

但闲着也不行，上头指标还在那儿呢。你想想，还是分阶段更容易完成，也定个小目标，也弄两个五年个计划，到了第十年刚好完成。

不过，这玩意，不是一个数字而是一个矩阵啊，怎么个定目标法呢？嗯，这时候就要用到矩阵的因式分解了。

你翻了一下放在书柜里吃灰的《线性代数及其应用(David C.lay著)》，上面有一段话：

矩阵M的因式分解是把A表示为两个或更多个矩阵的乘积。首先设M为m*n的矩阵，则一般情况下，M可以写成形式M = LU，其中L是m*m的下三角矩阵，主对角线元素全是1。而U是一个M的m*n阶梯型矩阵。

你看了之后，完全不知道它在说什么，只好拿出纸和笔，自己演算了起来：

嗯，你很高兴，你成功地把一个两年计划分成了两个一年计划。你坐下了，端起茶杯喝了一口，开始解读起你的计划来：

按照矩阵乘法的规则，你第一个五年需要用到的是U矩阵。嗯，你得保证郊区人口增长到200%的，城市100%的人口迁往郊区，再继续增长到现在人口的500%的人口留在城市。

再详细一点，假如城区原来有100人，郊区原来也有100人，那么第一个五年计划后，城区还有500人，郊区还有300人。

继续第二个五年计划。这次你需要用到是L矩阵。也就是保证第十年结束时，相比第五年结束，郊区100%的人留在郊区，再多出400%的人口去城市。城市100%的人口继续留在城市。

那么第二个五年计划后，城市就有了1700人，郊区就有了300人。与预期相符。

你又翻了几下那本书，里面说这种矩阵因式分解叫做LU分解，在解方程的时候很有用。例如求解 Ax = b，其中A为已知矩阵，x 是未知向量 ， b是已知向量。当A = LU时，方程Ax = b写为L(Ux)) = b，把Ux 写成 y ,即可由下面的方程：

                                                                Ux = y

                                                                Ly = b

先由Ly = b解出y ，再由Ux = y 解出x。由于L是下三角矩阵，而U是阶梯形矩阵，比较容易求解。所以比起直接用A的逆矩阵乘b，使用LU分解在某些情况下更加容易一些。

“很好，但这和我这个市长有什么关系呢？”你合上了书本，思索着那些刁民怎样才能达到那么高的人口增长率。这时候，上头又来一通电话：“需求又改了，现在要求明天就让那些市民人间蒸发——不，离开这片城市和郊区。准备好炸水坝了吗？”

欢迎来我的博客看此文章！