  We present a method to non-perturbatively determine the parameters of the
on-shell, $O(a)$-improved relativistic heavy quark action. These three
parameters, $m_0$, $\zeta$, and $c_B=c_E$ are obtained by matching
finite-volume, heavy-heavy and heavy-light meson masses to the exact
relativistic spectrum through a finite-volume, step-scaling recursion
procedure. We demonstrate that accuracy on the level of a few percent can be
achieved by carrying out this matching on a pair of lattices with equal
physical spatial volumes but quite different lattice spacings. A fine lattice
with inverse lattice spacing $1/a=5.4$ GeV and $24^3 \times 48$ sites and a
coarse, $1/a=3.6$ GeV, $16^3 \times 32$ lattice are used together with a heavy
quark mass $m$ approximately that of the charm quark. This approach is unable
to determine the initially expected, four heavy-quark parameters: $m_0$,
$\zeta$, $c_B$ and $c_E$. This apparent non-uniqueness of these four parameters
motivated the analytic result, presented in a companion paper, that this set is
redundant and that the restriction $c_E=c_B$ is permitted through order $a|\vec
p|$ and to all orders in $m a$ where $\vec p$ is the heavy quark's spatial
momenta.
