Numerical solutions of the eikonal (Hamilton-Jacobi) equation for transversely isotropic (TI) media are essential for integral imaging and traveltime tomography applications. Such solutions, however, suffer from the inherent higher-order nonlinearity of the TI eikonal equation, which requires solving a quartic polynomial at each computational step. Using perturbation theory, we approximate the first-order discretized form of the TI eikonal equation with a series of simpler equations for the coefficients of a polynomial expansion of the eikonal solution in terms of the anellipticity anisotropy parameter. Such perturbation, applied to the discretized form of the eikonal equation, does not impose any restrictions on the complexity of the perturbed parameter field. Therefore, it provides accurate traveltime solutions even for the anisotropic Marmousi model, with complex distribution of velocity and anellipticity anisotropy parameter. The formulation allows tremendous cost reduction compared to using the exact TI eikonal solver. Furthermore, comparative tests with previously developed approximations illustrate remarkable gain in accuracy of the proposed approximation, without any addition to the computational cost.