  No analytic solution is known to date for a black hole in a compact
dimension. We develop an analytic perturbation theory where the small parameter
is the size of the black hole relative to the size of the compact dimension. We
set up a general procedure for an arbitrary order in the perturbation series
based on an asymptotic matched expansion between two coordinate patches: the
near horizon zone and the asymptotic zone. The procedure is ordinary
perturbation expansion in each zone, where additionally some boundary data
comes from the other zone, and so the procedure alternates between the zones.
It can be viewed as a dialogue of multipoles where the black hole changes its
shape (mass multipoles) in response to the field (multipoles) created by its
periodic "mirrors", and that in turn changes its field and so on. We present
the leading correction to the full metric including the first correction to the
area-temperature relation, the leading term for black hole eccentricity and the
"Archimedes effect". The next order corrections will appear in a sequel. On the
way we determine independently the static perturbations of the Schwarzschild
black hole in dimension d>=5, where the system of equations can be reduced to
"a master equation" - a single ordinary differential equation. The solutions
are hypergeometric functions which in some cases reduce to polynomials.
