---
tag: X68MFYW014
kind: statement
role: theorem
name: Additive Schwarz method
msc: [65N55, 65F08, 65F10]
uses: [0B8KZRT28M, KE98SW3SBD, AB3S6MHJ8X, 0KX66CZMBB]
about: [AN054RHT1K, KE98SW3SBD]
sources:
  - url: https://en.wikipedia.org/wiki/Additive_Schwarz_method
same_as:
  wikidata: Q4681340
  wikipedia: Additive Schwarz method
---

## Statement

Let $V$ be a finite-dimensional real vector space with an inner product $a(\cdot, \cdot)$.
Let $V_0, V_1, \dots, V_N$ be subspaces of $V$ with $V = V_0 + V_1 + \cdots + V_N$.
Let $P_i \colon V \to V_i$ be the $a$-[[orthogonal projection|0B8KZRT28M]] onto $V_i$, and let $P = P_0 + P_1 + \cdots + P_N$ be the *additive Schwarz operator*.
Then $P$ is self-adjoint and positive definite with respect to $a$, and for every $v \in V$
$$a(P^{-1} v, v) = \min \Bigl\{ \sum_{i=0}^{N} a(v_i, v_i) : v_i \in V_i, \ \sum_{i=0}^{N} v_i = v \Bigr\}.$$
Suppose that every $v \in V$ has a decomposition $v = \sum_i v_i$ with $v_i \in V_i$ and $\sum_i a(v_i, v_i) \le C_0^2 \, a(v, v)$.
Then the eigenvalues of $P$ lie in $[C_0^{-2}, N + 1]$.
So the [[condition number|AB3S6MHJ8X]] of $P$ is at most $(N + 1) C_0^2$.

## Remarks

Each $P_i$ is self-adjoint and satisfies $0 \le a(P_i w, w) \le a(w, w)$, so $P$ is self-adjoint with eigenvalues at most $N + 1$.
If $a(Pw, w) = 0$, then $P_i w = 0$ for all $i$, so $w$ is orthogonal to every $V_i$ and hence to $V$, and $w = 0$.
For the identity, the choice $v_i = P_i P^{-1} v$ gives $\sum_i a(v_i, v_i) = a(v, P^{-1} v)$.
For any other decomposition, $a(v, P^{-1} v) = \sum_i a(v_i, P_i P^{-1} v)$, and the Cauchy–Schwarz inequality gives $a(v, P^{-1} v) \le \sum_i a(v_i, v_i)$.

In matrix form, let $A$ be the symmetric positive definite stiffness matrix and let $R_i$ be the restriction to the unknowns of subdomain $i$.
Then the method uses the [[preconditioner|KE98SW3SBD]] $M^{-1} = \sum_i R_i^T (R_i A R_i^T)^{-1} R_i$, and $M^{-1} A$ is the matrix of $P$.
One applies it inside the [[conjugate gradient method|AFXZGQB4EN]], and the local solves can run in parallel.
Take finite elements on overlapping subdomains of diameter $H$ with overlap $\delta$, and a coarse space $V_0$ on the coarse grid.
Then the standard bound is $\kappa(P) \le C (1 + H/\delta)$, with $C$ independent of the mesh size and the number of subdomains.
Without the coarse space, the bound degrades as the number of subdomains grows, because a single subdomain solve cannot carry information across the whole domain.

## Explanations

### L1 human

The additive Schwarz method splits a big problem into many overlapping small ones, solves all of them at the same time, and adds the corrections.
Used alone this would overshoot, so it is used as a preconditioner: it turns a hard linear system into an easier one for an iterative solver.
The theorem says the result is well conditioned as long as every function can be split into local pieces whose total energy is not much more than its own.

### L2 human

The identity for $a(P^{-1} v, v)$ is often called Lions' lemma, and it reduces the analysis to finding a stable splitting.
It is the parallel counterpart of the [[Schwarz alternating method|97VNBS15CD]], just as the Jacobi method is the parallel counterpart of Gauss–Seidel.
Coloring the subdomains so that overlapping ones get different colors improves the bound $N + 1$ to one plus the number of colors.
The same abstract framework covers [[multigrid methods|AC9PY6FBYF]] viewed as subspace corrections.