Progressive Iterative Approximation Based On The Classical Iterative Algorithm

Progressive iterative approximation (referred to as PIA) is a new data fitting method. Thecomputations of each point are independent, so it has good parallel property, and can improve thequality of the curves and surface gradually during the iteration. Furthermore, it has other goodproperties, such as intuitional geometric meaning, simple calculation, stable evaluation, easyprogramming, and so on. In this paper, we combine the idea behind the Jacobi iteration method andthe Gauss-Seidel iterative method and the PIA scheme to construct two new PIA algorithms,namely, Jacobi-PIA and GA-PIA, respectively.Firstly, we briefly review the process of PIA algorithm and its convergence. For the blendedcurve defined by normalized totally positive (referred to as NTP) bases, we introduce thecorresponding local PIA procedure. Then we review the Jacobi iteration and the Gauss-Seideliteration for solving linear equations, and the necessary and sufficient conditions for theirconvergences. In fact, if the interpolation curves are blended curves by NTP bases, the algebraicinterpolation method is equal to PIA method, i.e., the PIA method is an iterative approximation ofalgebraic interpolation method. Furthermore, we review the conclusions for Jacobi iteration andGauss-Seidel iteration.Secondly, we propose the Jacobi-PIA algorithm. Through combination of PIA and the classicalJacobi iteration method, we get the adjustment vector for each control point by an appropriateweight according to the Jacobi-PIA algorithm. We point out the specific process of the algorithmand prove that it is convergence. We compare the computational costs of PIA, Jacobi-PIA andPIA-Best algorithms and show that the Jacobi-PIA algorithm has the least computational costs.Finally, we present some numerical examples, which show that the Jacobi-PIA algorithm has thefastest convergence rate.Thirdly, we introduce the GS-PIA algorithm. Through combination of the PIA and the idea ofclassical Gauss-Seidel iteration method, we derive the GS-PIA algorithm. Because the Gauss-Seideliteration method is not suitable for parallel processing, we only compare the PIA algorithm andGS-PIA algorithm. Theoretical analysis shows that GS-PIA algorithm has less store than PIA. Wealso present some numerical examples to compare the PIA method and GS-PIA method, whichshow that the GS-PIA algorithm is better than original PIA algorithm in computational costs andconvergent rate.Finally，by estimating the distance between the new inserted points and the control polygonand the length of the control polygon after some subdivision steps, we get some bounds of thedistance between the limit curves of four-point subdivision scheme and its control polygon. Theoretical analysis and calculation examples show that our distance bound is better than theexisted one.