The temperature anomalies in the Earth's mantle associated with thermal convection can be inferred from seismic tomography, provided that the elastic properties of mantle minerals are known as a function of temperature at mantle pressures. At present, however, such information is difficult to obtain directly through laboratory experiments. We have therefore taken advantage of recent advances in computer technology, and have performed finite-temperature ab initio molecular dynamics simulations of the elastic properties of MgSiO3 perovskite, the major mineral of the lower mantle, at relevant thermodynamic conditions. When combined with the results from tomographic images of the mantle, our results indicate that the lower mantle is either significantly anelastic or compositionally heterogeneous on large scales. We found the temperature contrast between the coldest and hottest regions of the mantle, at a given depth, to be about 800 K at 1,000 km, 1,500 K at 2,000 km, and possibly over 2,000 K at the core-mantle boundary.