If you use 78xx the caps *should* be there in any case - should means no must anyhow. So at least you should use one cap (like 1000 µF) between the power and the 7809 and another one after the 7809. And then the normal caps already on the core.
I would even think about adding more of those things, because: 16 Volt - 9 Volt = 7 Volts; 7 Volts * lets say 300 mA = 2,1 watts pure heat - really much for a 78xx (heatsink!!!)
Perhaps a 7812, then the 7809 and back to the core (7805)?