Rapid and wide application of the complex surface in modern manufacturing makes new demands of the registration techniques on complex surface. Although significant progress has been made in complex surface registration, it remains a difficult problem in some situation. For a complex part with multiple freeform surfaces, the precision of measurement points often exists different in different surface regions due to a variety of measurement methods. Meanwhile, the manufacture precision in different regions is also not the same in complex manufacture process. Problems of registration on complex surface, have become increasingly prominent and new methods are bound to be found. Robust principle was generalized to the complex surface registration in which the precision difference existed in different surface regions. A robust registration was presented based on M-estimation. The effect of low precision measured data was weakened for the registration result by M-estimation functions. But the solving efficiency of the model was low due to the highly nonlinear and piecewise of the objective function. A good initial position was easily available with current registration method, and the error functions were linearly approximated by Taylor expansion when the rotation transform was slight. A linear registration model was found and the efficiency was improved. An approximation of the rotation matrix based on the minimization of Fibonacci norm was adopted in each iteration. Both theoretical and experimental results confirmed the stabilization and efficiency.