This work presents an analysis of relationships between the non-linear vibrations in machining and the machined surface quality from an analytical model based on a predictive machining theory. In order to examine the influences of tool oscillations, several non-linear mechanisms were considered. Additionally, to solve the non-linear problem, a new computational strategy was developed. The resolution algorithm significantly reduces the computational times and makes the iterative approach more stable. In the present approach, the coupling between the tool oscillations and (i) the regenerative effect due to the variation of the uncut chip thickness between two successive passes and/or when the tool leaves the work (i.e., the tool disengagement from the cut), (ii) the friction conditions at the tool–chip interface, and (iii) the tool rake angle was considered. A parametric study was presented. The correlation between the surface quality, the cutting speed, the tool rake angle, and the friction coefficient was analyzed. The results show that, during tool vibrations, the arithmetic mean deviation of the waviness profile is highly non-linear with respect to the cutting conditions, and the model can be useful for selecting optimal cutting conditions.