修订单纯形法不用存储完整表格,但每次更换基底后仍须解线性方程。每次都重新分解基底固然可行;乘积形式更新则展示如何重用之前的计算。本节在精确算术下推导公式,说明运算次序,并区分代数上有效的更新与数值上可靠的实现。
换一列等于矩阵相乘
考虑标准形式的极大化问题 ,设 是可逆基底,其基本变量满足 。假设非基底列 进入基底的第 个位置,先解
定义 19.1.1
(基底替换的 eta 矩阵)
设 是列已排序的可逆基底,列 取代第 个位置的列,而 满足 。这次替换的 eta 矩阵 是把单位矩阵的第 列换成 所得的矩阵:
其中 是第 个坐标向量。 的第 列是 ,即原来的列;第 列是 。因此 恰好是新基底矩阵。
注意 是有序基底中的位置,未必等于离开变量的标号。
常见错误
(按离开变量的标号决定 eta 列)
若有序基底为 而 离开,替换发生在位置 ,所以应把单位矩阵的第 2 列换成 。若因离开变量叫 而换掉第 1 列,乘积 便对应另一个基底:它移走 、保留 ,此后的更新都在解错误的方程。
定理 19.1.2
(单次更新及其逆运算)
替换后的基底 可逆,当且仅当 。在此条件下,解 的公式为
解 时先取 的 ,再计算
证明
(行列式与两种 eta 求解)
除第 列外都是标准坐标向量;沿第 列展开可得 ,所以 ,而 可逆当且仅当 。在方程 中,第 行是 ,其他行是 ,得到第一组公式。对 ,除第 行外均为 ,第 行则是 ,代入即得第二组公式。由于 ,各步都可逆。
原始可行主元的比率检验选取 的行,故主元非零。步长为零仍可产生有效新基底:离开的基本变量可为零,尽管 为正。反之,若在方向分量为零的位置替换,新矩阵奇异,便不是合法主元。
概念视角代数
逆更新就是表格的主元运算
解方程的公式说明 也是 eta 矩阵:它是把单位矩阵第 列换成 的矩阵,其中 ,而对 有 。因此 ;把 作用于整个表格 ,就是把第 行除以 ,再从每个第 行减去新第 行的 倍。这正是对进基列(其当前元素为 )所做的主元运算。乘积形式存储的是这些主元运算,而不是表格本身。
一连串更新
由可逆而已有分解的 开始。若连续主元产生 ,则
命题 19.1.3
(用乘积形式基底求解)
设 可逆, 是主元均非零的 eta 矩阵,因此 可逆。
- 解 :先解 ,再按 依次解 ,取 。
- 解转置方程 :先解 ,再按 依次解 ,最后解 。
若 ,只需解原始基底方程。
证明
(从左边逐个剥去因子)
每个因子都可逆: 是假设,每个 的行列式等于其非零主元。对普通方程, 即 ,它成立当且仅当 ,其中 是 的唯一解。假设解了 次之后方程变为 。把左边写成 ,它成立当且仅当 ,其中 。经过 步后不再剩下因子,得 。
对转置方程,。同样的剥除步骤首先遇到 : 成立当且仅当 ,其中 。继续消去 ,最后剩下 。
证明透视
为何转置求解要反序
证明只重复一个步骤:方程最左边的可逆因子可以用一次求解消去,留下形状相同、少一个因子的方程。非零主元的假设只在这里使用;若 ,某一步可能无解或有无穷多解。两种方程唯一的区别在于乘积的转置法则:转置会把因子反序,使 变成最左、 变成最右。论证中没有任何一步让因子互相越过,所以 eta 矩阵从不需要交换;而每步消去一个因子,论证在恰好 次求解后结束。
对当前基底,解 可计算约化成本 。考虑进入列时,解 ;再配合 ,便得到原始比率检验及约化成本检验所需数据。每次基本变量改变, 也须更新,旧价格向量一般不再正确。
常见错误
(沿用上一个价格向量)
主元之后, 第 个位置的成本改变了,旧的 不再满足 。在下面的算例中,第一次更新后基底的价格是 ;把它用于第二个基底 ,得到 ,而不是 。必须用更新后的 重做转置求解。
算例
例题 19.1.4
(从单位基底开始的两次替换)
令 、。首先让 进入位置 1。方向 ,候选比率为 及 ,因此位置 1 离开。新的基本向量是 ,且
再让 进入。解 得 ;比率分别为 及 ,所以位置 2 离开。于是
新基本向量为 :原第一个基本值减去 ,进入变量的值则为 2。也可先解 ,再解 ,得到同一结果。直接相乘可核对 。
例题 19.1.5
(用反序转置求解计算价格)
沿用 ,并设基本成本为 。转置求解先由 得 、,即 。再解 ,即 、,得 。直接计算也有 。
假如两个原单位列的成本均为零,其约化成本都是 ;若没有其他列,原始可行性及非正约化成本便证明最大值为 。以此成本计算,两次指定进入列在各自起始基底的约化成本确为正:首次为 3,第一次主元后第二列为 ,其中 是 的解。
反例模式
次序错误的更新
对同样两个因子,若先把 、再把 作用于 ,得到 ,不是 。用 相乘得到 ,亦不是 。每次单独求解都正确,也不能因此任意交换矩阵逆的次序。
下一个算例专门处理比率检验的边界情况:方向分量为正而步长为零的主元。
例题 19.1.6
(步长为零而更新仍可逆)
取 、,并让 进入,故 。候选比率为 及 ,位置 1 以零步长离开。eta 矩阵就是上面的 ,;解 得 、。基底改变了,基本值却没有改变,而这个更新是有效的。
改为替换位置 2 在代数上也合法,因为 ,但这忽略了比率检验。取 ,解 得 、。新基底可逆却不可行。非零主元保证得到基底;保持可行性的是比率检验。
计算与限制
一个 eta 更新只需存储主元位置及方向;套用它的工作量与所存储的非零项数及一次主元运算成正比。方向稀疏时可节省计算,但乘法或求解可能产生填入,过长的更新链也会增加工作及存储。实务中会定期重新分解当前基底,然后丢弃旧更新链。适当频率取决于稀疏性、硬件及数值表现,本节并未证明一个适用所有问题的固定门槛。
公式需要除以 。精确算术下极小的非零主元仍合法,浮点计算时却可能放大误差。应检查残差 及 ,并在数值软件中采用合适的缩放、稳定性控制及重新分解。若基底病态,小残差本身不保证小的前向误差。精确约化成本的符号和有限主元论证不会自动保留于四舍五入运算;严格证书需要另行证明误差界。
练习
快速检查
(三阶单位矩阵的第 2 列换成 ,所得矩阵为 。分别解 和 。)
以 、 套用更新定理的两组公式。
解答 · 答案
第一组公式给 、、。转置方程有 、,以及 。直接代入可核对两个答案。
快速检查
(在两次主元的例子中,第三列为 ,成本为 4。求基底 的方向及约化成本;它可否作为改进极大值的进入列?)
使用已在 算出的价格 。
解答 · 答案
解 得 ,因为 、。因 ,约化成本是 ;从零增加这个变量不能改进当前极大值。
快速检查
(若 ,能否把可逆基底的第 列换成 而得到另一基底?不用比率检验解释。)
计算替换后矩阵的行列式。
解答 · 答案
不能。替换结果为 ,行列式是 ,故各列线性相关。即使不讨论原始比率检验,非零主元仍是必要的代数条件。
快速检查
(求解器把显示的残差四舍五入至小数点后六位而得到零,这能证明计算出的基本向量完全准确吗?)
把显示数值的舍入与基底的条件数分开考虑。
解答 · 答案
不能。未四舍五入的残差可能非零。即使残差确实很小,病态基底也可造成显著前向误差。必须控制逆矩阵的作用和舍入误差,才能把残差转成前向误差界。