A new study on some Vandermonde matrices and systems
- PDF / 388,822 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 16 Downloads / 203 Views
A new study on some Vandermonde matrices and systems S. Sohrabi1 · A. Moradinejad1 Received: 9 March 2020 / Revised: 8 August 2020 / Accepted: 20 August 2020 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2020
Abstract In this paper, we first introduce a new concept on matrices which we call annihilator vectors. Then using the shifted form of these vectors, we propose new algorithms for (1) computing the inverse of a Vandermonde matrix, (2) solving some Vandermonde systems of linear equations, both algorithms in O(n 2 ) arithmetic operations. Our methods are based on a new technique which lead to novel algorithms, need less storage and, from experimental results, are more efficient than the previous usual methods. Finally, comparisons with other methods are broached and some numerical examples are supplied. Keywords Vandermonde matrix · Vandermonde system · Matrix inversion · Annihilator vector Mathematics Subject Classification 15A09 · 15A15 · 15A06 · 65F05
1 Introduction The Vandermonde matrix and its inverse have been widely used in many applications, such as polynomial interpolation (Phillips 2003), construction of spline functions (Jerome and Schumaker 1967), approximation of linear functionals (Lyness and Moler 1966), curve fitting (Wilf 1958), the solution of multivariate interpolation problem (Chui and Lai 1988), the moving least squares approximation (Lancaster and Salkauskas 1981), signal reconstruction (Olkkonen and Olkkonen 2010), wireless communication (Wang et al. 1999), and signal processing (Ryan and Debbah 2009). As a usual application, consider a set of given n observations, (ti , yi ), i = 0, 1, . . . , n − 1, where ti = 0, i = 0, 1, . . . , n − 1, are distinct. We can find a unique polynomial p of degree n − 1 such that p(ti ) = yi , i = 0, 1, . . . , n − 1 (Phillips 2003). Suppose that the interpolation polynomial p is given by p(t) = p0 + p1 t + p2 t 2 + · · · + pn−1 t n−1 . Then the problem can be written in the following
Communicated by Jinyun Yuan.
B
S. Sohrabi [email protected] A. Moradinejad [email protected]
1
Department of Mathematics, Faculty of Science, Urmia University, Urmia 57561-51818, Iran 0123456789().: V,-vol
123
258
Page 2 of 17
matrix form:
S. Sohrabi, A. Moradinejad
⎛
1 t0 t02 ⎜ 1 t1 t 2 1 ⎜ ⎜. . .. ⎝ .. .. . 2 1 tn−1 tn−1
⎞⎛ ⎞ ⎛ ⎞ · · · t0n−1 p0 y0 ⎟ ⎜ ⎟ ⎜ · · · t1n−1 ⎟ ⎟ ⎜ p1 ⎟ ⎜ y1 ⎟ = ⎟ ⎜ ⎟ ⎜ ⎟. . . . · · · .. ⎠ ⎝ .. ⎠ ⎝ .. ⎠ n−1 pn−1 yn−1 · · · tn−1
(1)
Eq. (1) is a system of n linear equations and the unknown coefficients pi , i = 0, 1, . . . , n −1 are given by ⎛ ⎞ ⎛ ⎞ p0 y0 ⎜ p1 ⎟ ⎜ y1 ⎟ ⎜ ⎟ ⎜ ⎟ (2) ⎜ .. ⎟ = V −1 ⎜ .. ⎟ , ⎝ . ⎠ ⎝ . ⎠ pn−1 yn−1 where
⎛
1 t0 t02 ⎜ 1 t1 t 2 1 ⎜ V =⎜. . .. ⎝ .. .. . 2 1 tn−1 tn−1
⎞ · · · t0n−1 · · · t1n−1 ⎟ ⎟ .. ⎟ ··· . ⎠ n−1 · · · tn−1
is an n × n Vandermonde matrix. It is clear from (2) that finding the unknown coefficients involves computing the inverse of the associated Vandermonde matrix and multiplying it by [y0 , y1 , . . . , yn−1 ]T . Computing the inverse of a Vandermonde matri
Data Loading...
