Problem: each time the relay turns on, the temperature jumps ~2 degrees up - so from 22 C temp gets 24.
I've tried many software solutions,
1) How is the system powered? If the relay draws too much the reference voltage of the analogRead() may be not 5.0V (check with voltmeter?)
Try connecting the sensor and relay to a physically different ground on the arduino.