Vandermonde matrices are usually exponentially ill-conditioned and often result in unstable approximations. In this paper, we introduce and analyze the \textit{multivariate Vandermonde with Arnoldi (V+A) method}, which is based on least-squares approximation together with a Stieltjes orthogonalization process, for approximating continuous, multivariate functions on $d$-dimensional irregular domains. The V+A method addresses the ill-conditioning of the Vandermonde approximation by creating a set of discrete orthogonal basis with respect to a discrete measure. The V+A method is simple and general. It relies only on the sample points from the domain and requires no prior knowledge of the domain. In this paper, we first analyze the sample complexity of the V+A approximation. In particular, we show that, for a large class of domains, the V+A method gives a well-conditioned and near-optimal $N$-dimensional least-squares approximation using $M=\mathcal{O}(N^2)$ equispaced sample points or $M=\mathcal{O}(N^2\log N)$ random sample points, independently of $d$. We also give a comprehensive analysis of the error estimates and rate of convergence of the V+A approximation. Based on the multivariate V+A approximation, we propose a new variant of the weighted V+A least-squares algorithm that uses only $M=\mathcal{O}(N\log N)$ sample points to give a near-optimal approximation. Our numerical results confirm that the (weighted) V+A method gives a more accurate approximation than the standard orthogonalization method for high-degree approximation using the Vandermonde matrix.
翻译:Vandermonde 矩阵通常是指数性不完善的, 并且往往导致不稳定的近似值。 在本文中, 我们引入并分析\ textit{ 多元变异 Vandermonde 与 Arnoldi (V+A) 方法} 。 该方法基于最小平方近似, 与 Stieltjes 或thoconal化进程一起, 以近似于连续、 多变异功能 $d- 维元非常规域。 V+A 方法解决 Vandermonde 近似不完善的问题, 方法是在离散测量测量时建立一套离散或异基基。 V+A 方法仅以域的样本点为基础, 并且不需要对域进行事先了解。 V+A+A ormod 近端的快速中位数值 。 我们的 V+A+ mal mal 直径直径直径直径直径直径直径直径直径直径直径直径直径直径直值分析。