Барицентрическая формула является ещё одним методом интерполяции, связанным с интерполяционными многочленами.
Она не позволяет вычислить коэффициенты интерполяционного многочлена, но позволяет найти его значения в целевых точках.
Однако, её возможности не ограничиваются значениями интерполяционного многочлена — и определённым образом (описанным ниже) с помощью этой формулы можно успешно интерполировать функции даже с использованием равноотстоящих (равномерно распределённых) узловых точек, что проблематично для интерполяционных многочленов из-за феномена Рунге.
Вывод формулы #
Вспомним улучшенную формулу многочлена Лагранжа:
$$P(x) = l(x) \sum_{i=0}^n{\frac{w_i}{x-x_i} y_i}$$Заметим, что функция $f \equiv 1$ все значения $y_i$ будут равны 1, поэтому формула для интерполяции этой функции будет выглядеть так:
$$1 = l(x) \sum_{i=0}^n{\frac{w_i}{x-x_i}}$$Так как при делении на единицу значение не меняется, мы можем поделить улучшенную формулу многочлена Лагранжа для нужной нам функции на формулу для функции $f \equiv 1$. При этом множители $l(x)$ сократятся:
$$\boxed{p(x) = \frac{\displaystyle \sum_{i=0}^n{\frac{w_i}{x-x_i} y_i}}{\displaystyle \sum_{i=0}^n{\frac{w_i}{x-x_i}}}}$$Это и есть барицентрическая формула.
Заметим, что у весовых коэффициентов $w_i$ в числителе и знаменателе можно вынести и сократить любые общие множители.
Это поможет нам упростить вычисления для известных формул $w_i$, которые зависят от распределения узловых точек.
Известные формулы для барицентрических весов $w_i$ #
Приведём несколько распределений узловых точек на отрезке $[-1, 1]$ и соответствующие им формулы для коэффициентов $w_i$.
Если интерполяция происходит не на отрезке $[-1, 1]$, а на неком отрезке $[a, b]$, то барицентрические веса домножаются на $2^n(b-a)^{-n}$, однако этот общий множитель сокращается так же, как другие общие множители, поэтому мы не будем его учитывать.
1. Равноотстоящие узлы #
$h = 2/n$
$x_i = -1 + ih$
$w_i = \frac{(-1)^i \binom{n}{k}}{h^n n!}$
После сокращения общих множителей получаем:
$w_i = (-1)^i \binom{n}{k}$
2. Узлы Чебышёва (первого рода) #
$x_i = -\cos{\frac{(2i+1)\pi}{2n+2}} = \cos{\frac{(2n-2i+1)\pi}{2n+2}}, \quad i = 0,...,n$
$w_i = (-1)^i \sin{\frac{(2i+1)\pi}{2n+2}}$
2.1 “Растянутые” узлы Чебышёва первого рода #
Для “растянутых” до границ отрезка узлов получаются такие же веса:
$\displaystyle x_{i_{stretched}} = \frac{x_i}{\cos{\frac{\pi}{2n+2}}} = - \frac{\cos{\frac{(2i+1)\pi}{2n+2}}}{\cos{\frac{\pi}{2n+2}}} = \frac{\cos{\frac{(2n-2i+1)\pi}{2n+2}}}{\cos{\frac{\pi}{2n+2}}}, \quad i = 0,...,n$
$w_{i_{stretched}} = w_i = (-1)^i \sin{\frac{(2i+1)\pi}{2n+2}}$
3. “Дополненные” узлы Чебышёва первого рода #
Чтобы получить “дополненные” $(n+1)$ узлов Чебышёва первого рода, нужно добавить к $(n-1)$ узлам Чебышёва первого рода точки $\{-1\}$ и $\{1\}$:
$ x_i = \begin{cases} -1, & i = 0 \\ \cos{\frac{(2n-2i-1)\pi}{2n-2}}, & i = 1, ..., n - 1 \\ 1, & i = n \end{cases} $
$ w_i = \begin{cases} 1/2, & i = 0 \\ \displaystyle \frac{(-1)^i}{(n - 1) \sin{\frac{(2i - 1)\pi}{2n-2}}}, & i = 1, ..., n - 1 \\ (-1)^{n+1}/2, & i = n \end{cases} $
4. Узлы Чебышёва второго рода #
$x_i = -\cos{\frac{in}{n}} = \cos{\frac{(n-i)\pi}{n}}, \quad i = 0,...,n$
$w_i = (-1)^i \delta_i, \quad \delta_i = \begin{cases} \frac{1}{2}, & i = 0 \text{ or } i = n \\ 1, & \text{иначе} \end{cases}$
5. Узлы Чебышёва третьего рода #
В других источниках могут называться узлами Чебышёва четвёртого рода.
$x_i = -\cos{\frac{2i\pi}{2n+1}} = \cos{\frac{(2n-2i+1)\pi}{2n+1}}, \quad i = 0,...,n$
$w_i = (-1)^i \delta_i \cos{\frac{i\pi}{2n+1}}, \quad \delta_i = \begin{cases} \frac{1}{2}, & i = 0 \\ 1, & \text{иначе} \end{cases}$
5.1 “Растянутые” узлы Чебышёва третьего рода #
Для узлов, “растянутых” до границ отрезка (точнее, до правой границы отрезка, поскольку первая точка уже лежит на левой границе), получаются такие же веса:
$\displaystyle x_{i_{stretched}} = -1 + \frac{2(x_i + 1)}{1 + \cos{\frac{1}{2n+1}}}, \quad i = 0,...,n$
$w_{i_{stretched}} = w_i = (-1)^i \delta_i \cos{\frac{i\pi}{2n+1}}, \quad \delta_i = \begin{cases} \frac{1}{2}, & i = 0 \\ 1, & \text{иначе} \end{cases}$
6. Узлы Чебышёва четвёртого рода #
В других источниках могут называться узлами Чебышёва третьего рода.
$x_i = -\cos{\frac{(2i+1)\pi}{2n+1}} = \cos{\frac{(2n-2i)\pi}{2n+1}}, \quad i = 0,...,n$
$w_i = (-1)^i \delta_i \sin{\frac{i\pi}{2n+1}}, \quad \delta_i = \begin{cases} \frac{1}{2}, & i = n \\ 1, & \text{иначе} \end{cases}$
6.1 “Растянутые” узлы Чебышёва четвёртого рода #
Для узлов, “растянутых” до границ отрезка (точнее, до левой границы отрезка, поскольку последняя точка уже лежит на правой границе), получаются такие же веса:
$\displaystyle x_{i_{stretched}} = 1 + \frac{2(x_i - 1)}{1 + \cos{\frac{1}{2n+1}}}, \quad i = 0,...,n$
$w_{i_{stretched}} = w_i = (-1)^i \delta_i \sin{\frac{i\pi}{2n+1}}, \quad \delta_i = \begin{cases} \frac{1}{2}, & i = n \\ 1, & \text{иначе} \end{cases}$
Ссылки #
- Jean-Paul Berrut and Lloyd N. Trefethen, Barycentric Lagrange Interpolation, SIAM Review, Vol. 46, No. 3, pp. 501–517, 2004.
- J.-P. Berrut, Baryzentrische Formeln zur trigonometrischen Interpolation I, Z. Angew. Math. Phys. (ZAMP), 35 (1984), pp. 91–105.