Let $M$ be a compact, finite-dimensional Riemannian manifold, let $T: M \rightarrow M$ be an Anosov diffeomorphism, and let $\mathcal{R} = \{ R_1,\dots,R_n \}$ be a Markov partition. Because of structural stability, a small $C^1$ perturbation $T'$ of $T$ will also be Anosov. Is there a well-defined Markov partition $\mathcal{R}'$ for $T'$ that can be regarded as a perturbation of $\mathcal{R}$?
The answer is yes (don't know why I didn't see this before).
Let $T'$ be a small perturbation of $T$ and $U$ the corresponding topological conjugacy, viz. $U^{-1}T'U = T$. Now the key is to show that
$UW^s_{(T)}(x,R_j) = W^s_{(T')}(Ux,UR_j)$
and similarly for the unstable manifolds.
Let $x' \in W^s_{(T)}(x,R_j)$, i.e. $x' \in R_j$ and $d(T^nx,T^nx') \downarrow 0$. Then $Ux' \in UR_j$ and $d(U^{-1}T'^n(Ux),U^{-1}T'^n(Ux')) \downarrow 0$. By continuity, $d(T'^n(Ux),T'^n(Ux')) \downarrow 0$. So $Ux' \in W^s_{(T')}(Ux,UR_j)$.
Now $UW^s_{(T)}(x,R_j) = W^s_{(T')}(Ux,UR_j)$ implies that
$T'UW^s_{(T)}(x,R_j) = T'W^s_{(T')}(Ux,UR_j) \subset UW^s_{(T)}(U^{-1}T'Ux,R_k) = W^s_{(T')}(T'Ux,UR_k)$.
Again, the unstable case follows similarly. So $U\mathcal{R}$ is a Markov partition for $T'$. $\square$