  Splitting schemes are a class of powerful algorithms that solve complicated
monotone inclusions and convex optimization problems that are built from many
simpler pieces. They give rise to algorithms in which the simple pieces of the
decomposition are processed individually. This leads to easily implementable
and highly parallelizable algorithms, which often obtain nearly
state-of-the-art performance.
  In the first part of this paper, we analyze the convergence rates of several
general splitting algorithms and provide examples to prove the tightness of our
results. The most general rates are proved for the \emph{fixed-point residual}
(FPR) of the Krasnosel'ski\u{i}-Mann (KM) iteration of nonexpansive operators,
where we improve the known big-$O$ rate to little-$o$. We show the tightness of
this result and improve it in several special cases. In the second part of this
paper, we use the convergence rates derived for the KM iteration to analyze the
\emph{objective error} convergence rates for the Douglas-Rachford (DRS),
Peaceman-Rachford (PRS), and ADMM splitting algorithms under general convexity
assumptions. We show, by way of example, that the rates obtained for these
algorithms are tight in all cases and obtain the surprising statement: The DRS
algorithm is nearly as fast as the proximal point algorithm (PPA) in the
ergodic sense and nearly as slow as the subgradient method in the nonergodic
sense. Finally, we provide several applications of our result to feasibility
problems, model fitting, and distributed optimization. Our analysis is
self-contained, and most results are deduced from a basic lemma that derives
convergence rates for summable sequences, a simple diagram that decomposes each
relaxed PRS iteration, and fundamental inequalities that relate the FPR to
objective error.
