Odpověď na názor

No zakmitávat to jistě bude, ale chyba by i tak měla klesat nebo zůstávat stejná. Tím to není.

Stejný program v Matlabu a klesá mi to do stupně 22, pak to roste.

x = linspace(0, 10, 100);
y = [0.5*rand(1,50),1+0.5*rand(1,50)];
for i=1:30,
    p = polyfit(x,y,i);
    MSE=sum((polyval(p,x)-y).^2)/length(x)
end;

Ale od stupně 12 už to hlásí:

Warning: Polynomial is badly conditioned. Add points with distinct X values, reduce the degree of the polynomial, or try centering and scaling as described in HELP POLYFIT.

Takže chyba je v tom, že systém rovnic je špatně podmíněný (blízko singulárnímu) a ve výsledku se projeví velká chyba kvůli pevné přesnosti operací.

Závěr - polynom od 12 už nemá cenu na tato vstupní data fitovat. Trochu divné je, že scikitu ta špatná podmíněnost nijak nevadí a jede prostě dál.