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

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

一天,你正拿着茶杯在喝茶,上头突然来了文件,要求你的城市十年后这个时候人口数量增长到现在的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分解在某些情况下更加容易一些。

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

你也可以在我的博客里查看这篇文章:https://clatterrr.com/archives/1677

Leave a Reply