区间线性系统的解集与包围

形式陈述

一组区间数据代表哪些方程

把实区间逐项放进矩阵和向量，写成

\boldsymbol A=[A_c-\Delta,A_c+\Delta],\qquad \boldsymbol b=[b_c-\delta,b_c+\delta],\qquad \Delta,\delta\ge0.

以下矩阵为实 $n\times n$ 方阵， $n\ge1$ ，所有不等式和绝对值均逐分量解释。区间内各系数可以独立取值。它们定义一族线性方程组 $Ax=b$ ，而非一个普通矩阵方程。其联合解集是

\Sigma(\boldsymbol A,\boldsymbol b) =\{x\in\mathbb R^n:\exists A\in\boldsymbol A,\ \exists b\in\boldsymbol b,\ Ax=b\}. \tag{1}

这里同一个 $x$ 只需对应一组合法数据。说 $\Sigma\subseteq X$ ，则是在说所有合法点系统的每个解都落进外包围 $X$ ；这不要求所有系统共享同一个解。称 $\boldsymbol A$ 正则，是指其中每个点矩阵都可逆，不只是中心矩阵可逆。

一个精确的成员判据

Oettli–Prager判据把式(1)中的数据存在量词消去：

x\in\Sigma(\boldsymbol A,\boldsymbol b) \quad\Longleftrightarrow\quad |A_cx-b_c|\le\Delta|x|+\delta. \tag{2}

它判断一个指定向量能否由允许的数据产生；并未声称解集是盒，也没有自动算出最窄包围。[1]

必要性直接来自 $A=A_c+E$ 、 $b=b_c+e$ ： $A_cx-b_c=e-Ex$ ，而 $|E|\le\Delta$ 、 $|e|\le\delta$ 。充分性也可以逐行构造。设 $r=A_cx-b_c$ 、 $s_i=(\Delta|x|+\delta)_i$ 。若 $s_i>0$ ，取 $\theta_i=r_i/s_i$ ，并令

e_i=\theta_i\delta_i,\qquad E_{ij}=-\theta_i\Delta_{ij}\operatorname{sgn}(x_j).

约定 $\operatorname{sgn}(0)=0$ 。由 $|\theta_i|\le1$ ，这些扰动都合法，且 $e_i-\sum_jE_{ij}x_j=\theta_i s_i=r_i$ 。若 $s_i=0$ ，式(2)迫使 $r_i=0$ ，该行取零扰动即可。于是构造出的 $A,b$ 确实满足 $Ax=b$ 。

不显式求区间逆的统一证书

给定一个实矩阵 $C$ 和候选中心 $x_0$ 。用可靠区间运算算出非负上界

G\ge\operatorname{mag}(I-C\boldsymbol A),\qquad z\ge\operatorname{mag}\bigl(C(\boldsymbol b-\boldsymbol A x_0)\bigr),

其中区间的 $\operatorname{mag}$ 是绝对值的最大值。若找到逐分量正向量 $w$ ，使 $Gw<w$ ，便有

q:=\max_i\frac{(Gw)_i}{w_i}<1. \tag{3}

此时 $\boldsymbol A$ 正则， $C$ 也可逆。再找到非负向量 $r$ 满足

z+Gr\le r, \tag{4}

就得到所有点系统的统一包围

\Sigma(\boldsymbol A,\boldsymbol b)\subseteq x_0+[-r,r]. \tag{5}

式(3)和式(4)是两件事：前者认证逆问题确实成立，后者认证给出的半径够大。若 $z=0,r=0$ ，式(4)即使对奇异系统也可能成立，因而不能单独替代式(3)。

直觉

先把近似中心代回所有允许方程， $z$ 记录预条件后的最坏缺口。 $G$ 则记录校正一次后还会留下多少旧误差。式(4)的意思是：外来缺口加上旧误差的残留，仍装得进预留半径。加权向量 $w$ 允许不同坐标有不同自然尺度。

为什么这确实控制全部数据

使用由诱导矩阵范数得到的加权最大范数

\|v\|_w=\max_i |v_i|/w_i.

对任意 $A\in\boldsymbol A$ ，有 $\|I-CA\|_w\le q<1$ 。因此几何级数 $\sum_{k\ge0}(I-CA)^k$ 收敛并是 $CA$ 的逆；方阵乘积可逆也迫使 $A,C$ 各自可逆。注意这里没有把“ $C$ 是计算出来的近似逆”当作未经验证的前提。

固定任意合法 $A,b$ ，其唯一解误差 $e=A^{-1}b-x_0$ 满足

e=C(b-Ax_0)+(I-CA)e.

展开几何级数并逐项取绝对值，得 $|e|\le\sum_{k\ge0}G^kz$ 。另一方面，由式(4)归纳得 $\sum_{k=0}^{m-1}G^kz\le r-G^mr\le r$ 。令 $m\to\infty$ 就得到式(5)。证明对每组数据都相同，因此给的是整族的包围。

例子与边界

一个可以全用分数复算的二维例子

取

\boldsymbol A= \begin{pmatrix}1&[-1/5,1/5]\\{}[-1/10,1/10]&1\end{pmatrix}, \qquad b=\binom11,\qquad C=I,\quad x_0=\binom11.

可取 $G=\left(\begin{smallmatrix}0&1/5\\1/10&0\end{smallmatrix}\right)$ 、 $z=(1/5,1/10)^{\mathsf T}$ 。用 $w=(1,1)^{\mathsf T}$ 得 $q=1/5$ 。解 $r=z+Gr$ 得

r=\binom{11/49}{6/49},\qquad x_1\in[38/49,60/49],\quad x_2\in[43/49,55/49]. \tag{6}

把两个非对角元同时取负端点，精确解为 $(60/49,55/49)^{\mathsf T}$ ，所以这两个上端点确实能达到。下端点只是安全界，不因此宣称式(6)是最窄盒。成员判据在本例化为

|x_1-1|\le |x_2|/5,\qquad |x_2-1|\le |x_1|/10.

读者可用它逐点检验包围内哪些位置真能由合法矩阵产生。

量词和相关性不能省略

标量 $a,b\in[1,2]$ 独立变化时，联合解集为 $\{b/a\}=[1/2,2]$ 。若问题改为“这个 $x$ 对每个 $a\in[1,2]$ 都能找到一个 $b\in[1,2]$ 使 $ax=b$ ”，则要求 $[x,2x]\subseteq[1,2]$ ，只剩 $x=1$ 。改变数据量词就改变了问题。

若真实模型规定 $a=b\in[1,2]$ ，同样只可能有 $x=1$ 。把这两个出现位置改成可独立取值的区间，会得到较大的 $[1/2,2]$ ；它仍是外包围，却丢失了参数关系。式(2)的充分性依赖逐项独立选取数据，不能原封不动用于带相关性或对称性约束的矩阵族。

中心矩阵可逆也不保证整族正则，例如 $[1-2,1+2]=[-1,3]$ 包含零。反过来，式(3)检验失败只是这个充分判据未成功，不能推断区间中必有奇异矩阵。

推论与应用

计算 $C$ 可先用普通近似算法；认证阶段必须可靠地包住 $I-C\boldsymbol A$ 和残差，包括端点运算误差。稠密无结构矩阵下，形成 $C$ 和矩阵乘积的常见算术成本是 $O(n^3)$ ，检查给定 $w,r$ 只需 $O(n^2)$ ；这是浮点或有理算术操作数，有理数位长还需另计。这里交付充分包围，没有求解最窄区间逆的问题。

区间Newton法正需要这样的线性接口：它的系数矩阵覆盖整个盒上的Jacobian，右端则来自一个中心残差。每次线性包围都要说明包住的是全部可能修正，而不是只解中心矩阵。

参考资料

[1] W. Oettli and W. Prager, “Compatibility of Approximate Solution of Linear Equations with Given Error Bounds for Coefficients and Right-Hand Sides,” Numerische Mathematik 6, 1964, pp. 405–409；IBM原论文目录与摘要。本页逐行写出充要条件的直接构造。
Siegfried M. Rump, “Verification Methods: Rigorous Results Using Floating-Point Arithmetic”, Acta Numerica 19, 2010, pp. 287–449，作者修订稿§10.5、Theorems 10.6–10.8及§10.7；误差中心化、整族包含与数据依赖。本页使用便于逐分量复核的加权范数充分条件。

形式陈述 ​

一组区间数据代表哪些方程 ​

一个精确的成员判据 ​

不显式求区间逆的统一证书 ​

为什么这确实控制全部数据 ​

一个可以全用分数复算的二维例子 ​

量词和相关性不能省略 ​

反向链接