区域分解法

区域分解法（domain decomposition method）将一个偏微分方程区域或离散线性系统划分为若干子区域，通过局部求解和界面信息交换构造全局解。不同子区域可以并行处理，但局部答案并不能直接拼成全局答案；重叠区、界面条件、组合权重及粗层校正决定它们怎样协调。

两个重叠子问题

考虑线性系统 $$A=\left(\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right),b=\left(\begin{array}{c}1\\ 0\\ 1\end{array}\right).$$ 精确解为 $x_{\ast }=(1,1,1{)}^T$。将未知量分成 ${\Omega }_1=\{1,2\}$ 与 ${\Omega }_2=\{2,3\}$，第二个未知量位于重叠区。两份局部矩阵都是 $A_i=\left(\begin{array}{cc}2& -1\\ -1& 2\end{array}\right)$，其逆为 $\frac{1}{3}\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$。

从零开始，局部残差分别为 $(1,0{)}^T$ 和 $(0,1{)}^T$。局部校正为 $(2/3,1/3{)}^T$ 和 $(1/3,2/3{)}^T$。嵌回原位置并相加，得到全局校正 $(2/3,2/3,2/3{)}^T$。重叠点的两份贡献相加，这一步必须明确；若只任取其中一个局部值，就变成了另一种算法。

加法 Schwarz 的双子区域例子。局部逆作用于当前残差，重叠点的校正通过延拓求和。

加法 Schwarz 算子

令 $R_i$ 从全局向量抽取第 $i$ 个子区域的分量，$R_i^T$ 将局部向量嵌回全局并在其他位置补零。对对称正定矩阵 $A$，定义 $A_i=R_{i}A{R}_i^T$，并构造 $$B=\sum _i{R}_i^T{A}_i^{-1}{R}_i.$$ 这是局部求解的组合，不是全局逆矩阵。用它作残差校正得到 $$x^{k+1}=x^k+\omega B(b-A{x}^k).$$ 加法形式的各局部校正都使用同一轮残差，所以可以同时计算。乘法 Schwarz 则让后一个子问题读取前一个校正后的状态，类似块 Gauss–Seidel；其并行性与收敛结构不同。PETSc 的 PCASM 文档说明了重叠 Schwarz 作为预条件子的实现及局部组合选项。

本例组合后为 $$B=\frac{1}{3}\left(\begin{array}{ccc}2& 1& 0\\ 1& 4& 1\\ 0& 1& 2\end{array}\right).$$ 取 $\omega =1/2$，首步变成 $x^1=(1/3,1/3,1/3{)}^T$。第二步因 $BA(1,1,1{)}^T=(2/3)(1,1,1{)}^T$，得到 $x^2=(5/9,5/9,5/9{)}^T$。这个对称初值只激发一个模式，不能据此断定其他模式也有同样速度。

正定性与松弛条件的证明

每个 $A_i$ 都是正定主子矩阵。若子区域覆盖所有未知量，则对任意非零向量 $z$，至少有一个 $R_{i}z\ne 0$，于是 $$z^{T}Bz=\sum _i(R_{i}z{)}^T{A}_i^{-1}(R_{i}z)>0.$$ 因此 $B$ 对称正定。误差满足 $e^{k+1}=(I-\omega BA)e^k$。矩阵 $BA$ 与对称正定矩阵 $B^{1/2}A{B}^{1/2}$ 相似，所有特征值为正。若 $$0<\omega <2/{\lambda }_{max}(BA),$$ 则每个误差模式的因子 $1-\omega \lambda$ 的模都小于一，迭代收敛。正定性给出了可选松弛步长的基础，但不保证直接取一就合适。

本例 $BA$ 的特征值为 $2/3,4/3,2$。取 $\omega =1/2$ 时误差因子分别为 $2/3,1/3,0$。有解反例是 $b=0$、初值 $x^0=(0,1,0{)}^T$：它对应特征值二，若取 $\omega =1$，每轮只会换号，不能趋零；取 $\omega =1/2$ 则一步消除。这个变式揭示了主算例未激发的困难模式。

子域、界面与粗层

重叠法允许相邻局部区域共享一部分未知量。非重叠法则在界面上通过 Schur 补、通量或拉格朗日乘子耦合子域。局部子问题的边界是算法构造的边界，不能与原问题物理边界混为一谈。

只有局部校正时，远距离的平滑误差可能要经过多轮通信才能传播。加入覆盖全局低频行为的粗空间，可构成两层 Schwarz 预条件子，改善子域数量增加时的可扩展性；它与多重网格法都使用多尺度校正，但层级构造和局部算子不同。总成本必须计入局部因子分解、每轮求解、重叠通信以及粗层处理，不能只统计并行子问题的数目。

本例的可运行实现

下面专门实现上述三未知量模型，明确展示局部逆和重叠求和。每轮为常数成本，保存轨迹需要 $O(K)$ 空间；一般 $n$ 维问题则取决于子域大小、稀疏性和局部求解器。程序返回新轨迹，不修改初值，并允许用残差检验停止，而不是凭局部解看起来接近就停止。

Python 3

import math


def schwarz_three(b, initial, omega=0.5, steps=2):
    b, x = list(map(float, b)), list(map(float, initial))
    omega = float(omega)
    if len(b) != 3 or len(x) != 3 or not all(math.isfinite(v) for v in b+x+[omega]):
        raise ValueError("three finite components required")
    if not 0 < omega < 1 or not isinstance(steps, int) or steps < 0:
        raise ValueError("this model requires 0 < omega < 1 and nonnegative integer steps")
    history = [x[:]]
    for _ in range(steps):
        Ax = [2*x[0]-x[1], -x[0]+2*x[1]-x[2], -x[1]+2*x[2]]
        r = [v-w for v, w in zip(b, Ax)]
        left = [(2*r[0]+r[1])/3, (r[0]+2*r[1])/3]
        right = [(2*r[1]+r[2])/3, (r[1]+2*r[2])/3]
        correction = [left[0], left[1]+right[0], right[1]]
        x = [v+omega*d for v, d in zip(x, correction)]
        if not all(math.isfinite(v) for v in x):
            raise OverflowError("nonfinite Schwarz update")
        history.append(x[:])
    return history


print(schwarz_three([1, 0, 1], [0, 0, 0]))
# [[0, 0, 0], [1/3, 1/3, 1/3], [5/9, 5/9, 5/9]] up to floating-point rounding
print(schwarz_three([0, 0, 0], [0, 1, 0], 0.5, 1)[-1])  # [0, 0, 0]