Try splitting at Peterborough and York.
There are £9 Advances from Norwich to Peterborough, £17.20 Advances on some trains from Peterborough to York and £9-11 Advances on some trains from York to Newcastle. Book from the East Coast website. I can't be more specific without knowing times of travel.
EDIT: Looks like I was beaten to it, but I will emphasise that booking on the East Coast website will save you money on the ticket from Peterborough to York as East Coast offer a roughly 10% online discount on most of their Advance fares.