U've to pay big - €149.00!!! PhotoZoom's excellent in this sense.. it uses S-Spline method to extrapolate, which gives best resized output with min distortion. Nuthin can give u a perfect result. This comes the most close. They even have a photoshop plugin for it, if i remember well. They work extremely well. I tried it. The algorithm is almost flawless. It maintains detail, sharpness of the edges and texture of the original, avoids artifacts and creates perfect photo enlargements without much quality loss.
Free trail for Windows
Or u can try another way, self-devised of course, try converting the image to vector form, and then enlarge the vector, then convert back to jpg. Well, u might miss out extreme details, but the main lines will still b intact. Blend both. Just sayin.