Construction of dual bases (Q1947491)

Given a set \(\{b_i\}_{i=0}^N\) of linearly independent functions and the space \({\mathcal B}_{N}=\text{span}\{b_i,i=0,\ldots,N\}\), the author proposes a simple recurrent way of constructing a dual basis \(\{d_i^{(N)}\}_{i=0}^N\) of \({\mathcal B}_{N}\) in the time \(O(N^3)\). Such a method and the corresponding algorithm is an improvement of those already known in literature because of their disadvantage of either inverting a full matrix or precomputing an orthonormal basis of the considered space. The new efficient algorithm leads to a system of linear equations whose coefficient matrix has a simple LU decomposition, it is non singular and it can be easily inverted. An application to least squares approximation is presented. Finally, four examples on monomial basis, Bernstein basis, B-spline functions and best polynomial approximation are shown.