Look at Bayesian optimisation.

An interesting example is Michael Faraday, who couldn't do any but the most basic mathematics (not even trigonometry!). It was Maxwell who translated his physical intuition into mathematics.

New link: staff.science.uu.nl/~gadda001/goodtheorist/index.html

Thanks! So computing the whole inverse is essentially not harder than computing just one entry of it. On the other hand this only lets you compute diagonal entries of a matrix with special structure, so perhaps there is a better method.

Thanks for your answer. I added extra information namely that A is symmetric and positive definite. What is the reason that this cannot be done more efficiently than first forming $A^{-1}b$?