Algebraic Theory And Algorithms For Rational Interpolation

As a generalization of polynomial interpolation, rational interpolation has many advantages. The idea that study the problem of rational interpolation by algebraic method was first raised by Professor Feng Guochen in 2002. In this thesis, we study Cauchy rational interpolation problem on the set of distinct nodes by algebraic method and give some algorithms in univariate and multivariate cases.First, we give some notions that will be used hereafter. Given V_n = {X_i ∈R^k | i = 0,1,...,n}, 1 ≤ k ∈ N , functional value set Y_n = {y_i ∈ R |i = 0,1,..., n } and term order (?) . Let l be the polynomial of least formal degree with respect to the given order satisfies l(X_i) = y_i, i = 0,..., n. Denote I(V_n) the vanishing ideal of V_n . Let N(I(V_n)) = {w_i |i = 0,... ,n,w_i1;(?)w_i2,i₁ < i₂} be the standard basis oiV_n,S = Span(N(I(V_n))), U = {q ∈ S|(?)p ∈ S s.t. σ{pq) = 1 }.Definition 1 Let f ∈ R[X], Then there exists a unique g EThen a is a homomorphism and Ker(cr) = l(Vn) .The thesis generalize the definition of solution of rational interpolation and bring out a new concept — extended weak solution.Definition 2 Let Vn = {(Xit yi) G Rk xR\i = 0,..., n }, Wen = {(q,p) ï¿¡ S x S\p = a(ql),}. Then Wen is called the set of extended weak solution of Vn of rational interpolation, denoted by REWS.Because of the special structure of the set of extended weak set, it was endued with an algebraic structure — a linear space, and the dimension of the space is finite.Theorem 1 Let Wen be a REWS, a e R, q1 = (qh crfeZ)), q2 = e Wen. given two operations "+ " and "? " on(l) q(2) aThen Wen forms a linear space onLemma 1 S is linear space of dimension n + 1 on R and there is a isomorphism between S and Wen .Furthermore, the basis of Wen can be given as following. Theorem 2 Wen has a basisFrom the results above, we give the most importance definition— C-Matrix.Theorem 3 Set Qen = {a(ql)\q € S} is a linear sub-space of S. Define a linear map F :F : S -> Qen,Then there is a matrix M corresponding to F with respect to the basis {u>i\i = 0,..., n} of S. â– Definition 3 We call the matrix M in Theorem 3 the characteristic matrix on set { {X^yi) \i = 0,..., n} of basis {ui\i =0, ...,n} , for short, C-Matrix. Let M =0,... ,n, j = 0,... ,n. Some matrices related to M are listedbelow:The rank and determinant of a matrix A are respectively denoted by Rank(A) and det(A) . We always take for X, det(Mo,o) det(Mf) = 1 .Prom the property of linear transform we can get the formula of C-Matrix.nDefinition 4 Let / = Ylaiui ï¿¡ S(an ^ 0). Define the lineari=0functional C; on S :Q(/) = afj 0 Fd(g) + Fd(p) < n, LC{q) = 1. Then {q,p) is called a weak solution to problem of rational interpolation about Vn if and only if one of the conditions holds:(a) gcd(g,p) = 1;(b) g = gcd(g,p), Fd(<7) > 1, and for arbitrary divisor g of gs.t. :Fd(g)>0:(q/g,p/^g)tWen.Denote by Wsn the weak solution of rational interpolation.(2) LetqThen Son is called the solution set of Vn .Theorem 5 If there exists i .s.t. M^i is nonsingular, denoteThen (q,a(ql)) is the unique weak solution of rational interpolation satisfies Fd(<7) = i . â– In the univariate case, Let B — {xl\i = 0, ...,n} be the standard basis of Vn. The relation between the sub-matrix of C-matrix and weak solution is given by the special structure of C-matrix generated from basis B .Theorem 6 Let M be C-Matrix. Then (q,cr(ql)) is a weak solution if and only if Mdeg(g)ideg(g) is nonsingular. â– Then a sufficient and necessary condition is given on the aspect of the existence and uniqueness of the solution of rational interpolation.Theorem 7 Let Miti be a nonsingular sub-matrix of C-Matrix M ,q = det(Miji)-1det(M^)1) . Then (q,a(ql)) is a solution of rational interpolation if and only if = ? ? ? = Rank(M^J = i + 1.At the same time, the thesis study the theory of unattainable point of univariate rational interpolation. A sufficient and necessary condition is given at the recursive progress when the interpolation node is added one by one.Definition 6 Let Vn = {(Xi,yi)\i = 0,... ,n}, {q,p) is a weak solution on Vn ? If q € Ixt , where Ixt is the vanishing ideal onpoint Xi. Then (X{,yi) is called an unattainable point of weak solution {q,p), Xi is called a unattainable node of (q,p).Theorem 8 Let M. and M be C-Matrices about interpolation point set Vn = {{Xh 2/?)l* = 0,..., n} and Vn+i = Vn \J{(xn+i,yn+l)}. ln+i is the least degree interpolation polynomial on Vn+i . If thereexists h, 1 < h < n s.t. Mh,h is nonsingular, then (xn+\, yn+i) is_<sub> _<sub>tx\a unattainable point of (q = det(M/l)/l)¹det(M/l+1),p = a(qln+i)) if and only if Mh,h is singular. â– From the results above, we give three algorithms by the properties of C-Matrix.(1) The algorithm can compute all the solutions on the given interpolation points. This is a new kind of recursive algorithm. The algorithm first compute all the weak solutions of the rational interpolation by C-Matrix, then pick out the solutions from weak solutions. The complexity of computation is 0{n2).(2) The algorithm can compute such rational functions that the deference of the degrees of the numerator and the denominator is least by the recursive relations between C-Matrices and the determination of unattainable point. The complexity of computation is O(n2). Compared to former algorithms, the main difference is how to deal with unattainable point.(3) Adopting the idea of the spline function, this algorithm can avoid unattainable point. If there is no unattainable point in the recursive progress, the algorithm is the same as (2).For the multivariate case, we give a new order set, and give a new algorithm on this set. The complexity of computation is O(n2). We generalize the algorithms (1) and (2) to the lower set in multivariate case. On restrained conditions, we can get the rational interpolation functions and the complexity of computation is O(n2).We give an application of rational interpolation on computing the reliability of highly reliable systems. The complexity is remarkably reduced under the required precision.