如何在C ++中使用n维进行插值？ [英] How to interpolate with n-dimension in C++?

问题描述

你好，

我有一个问题：mutivariate插值，如下：

我有m个点（y [i]，x [i]），其中x [i]是向量n维，y [i]是值。现在，我有一个向量x，我想在向量x处定义y值。我还没有找到任何算法来解决这个问题。你可以帮我找到解决它的算法。谢谢。

Hello,
I have a problem: mutivariate interpolation, as follows:
I have m points (y[i], x[i]), where x[i] is a vector n-dimension, and y[i] is a value. Now, I have a vector x, I want to define y value at vector x. I havent found any algorithm to solve this simply. You can help me find an algorithm to solve it. Thanks.

推荐答案

首先看一下最简单的非平凡案例，我可能会有所帮助。即n ==可2。您正在查看的函数将2空格映射到实数，如果将结果y与参数向量（x [0]，x [1]）组合，则得到3空间中的点，（x [ 0]，x [1]，y）。你现在拥有的是一个表面。对于n> 2，你会在（n + 1） - 空格中得到一个n维超曲面。



如果你想近似一个曲面（即n） == 2），周围有很多样条插值和近似算法，但如果你知道的点（yi值）任意地分布在xi的2空间上，那么这是一个相当复杂的问题！



根据你知道的点数，你可以想出各种有意义的方法：例如：如果你从n + 1个已知点开始，这些点将定义一个超平面（对于n == 2，你需要三个点来定义一个平面），你可以简单地将任何参数向量x投影到该平面上以获得相应的y值。如果你只有n个或更少的已知点，你可以类似地定义一个线性子空间并将你的X投射到那个子空间。



如果你有超过n + 1然而，它们并非共同（超）平面，那么不仅这些点描述了非线性子空间，甚至可能没有一个独特的最佳拟合解决它们描述的流形。在那种情况下，我不知道任何通用算法。对于n == 1，您可以简单地按大小排序xi，确定x所在的区间[xk，xk + 1]，然后在yk和yk + 1之间插入y。对于n = 2，相应的算法会更复杂，因为您需要根据xi计算出平面的三角剖分，检查参数向量x所在的三角形，然后使用该三角形对y进行插值。这里棘手的部分是如何定义三角测量。对于更高的n值，同样的想法可能会起作用，但是将X的超平面细分为n维单形的任务变得更加复杂和模糊！



无论如何，这种方法只能提供非线性曲面的线性近似。更通用的方法是计算yi的加权和，其中权重应该基于参数向量X与相应的Xis的距离而减小。棘手的部分是以某种方式平衡权重，使它们总是加起来总共一个。目前我不知道如何实现n> 2。

It may help to first look at the easiest non-trivial case, i. e. n==2. The function you are looking at maps 2-space to a real number, and if you combine the result y with the argument vector (x[0], x[1]), you get a point in 3-space, (x[0], x[1], y). What you have, now, is a surface. For n>2 you'd get an n-dimensional hypersurface in (n+1)-space instead.

If you want to approximate a surface (i. e. for n==2), there are plenty of spline interpolation and approximation algorithms around, but if the points you know (the yi values) are arbitrarily spread over the 2-space of the xi, then it's a rather complex matter!

Depending on the number of points you know, you can come up with various methods that make some sense: e.g. if you start with exactly n+1 known points, these points will define a hyperplane (for n==2, you need three points to define a plane), and you can simply project any argument vector x onto that plane to get the corresponding y value. If you have only n or less known points, you'd similarly define a linear subspace and project your X onto that subspace.

If you have more than n+1 known points however, and they are not co-(hyper)planar, then not only do the points describe a nonlinear subspace, there may not even be a unique 'best' fit solution to the manifold they describe. In that case, I am not aware of any generic algorithm. For n==1 you might simply order the xi by size, determine the interval [xk,xk+1] that x lies in, and then interpolate y between yk and yk+1. For n=2 the corresponding algorithm would be more complex, since you'd need to figure out a triangulation of the plane based on the xi, check which triangle the argument vector x lies in, and then interpolate y using that triangle. The tricky part here is how to define the triangulation. For higher values of n, the same idea may work, but the task of subdividing the hyperplane of Xs into n-dimensional simplexes gets even more complex an ambiguous!

In any case, this approach would only deliver a linear approximation of a non-linear surface. A more generic approach would be to calculate a weighted sum of the yi, where the weights should diminish based on the distance of the argument vector X from the correponding Xis. The tricky part is to somehow balance the weights so that they always add up to a total of one. At the moment I have no idea how to achieve that for n>2.

你可以看看曲线拟合。

当你有匹配的多项式方程时，它是容易放入任何x值。



使用拉格朗日插值的曲线拟合 [ ^ ]



我希望它可以帮助您入门。

You can look into curve fitting.
When you have matching polynomial equation it is easy to put in any x-value.

Curve Fitting using Lagrange Interpolation[^]

I hope it helps you to get started.

这篇关于如何在C ++中使用n维进行插值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！