7
$\begingroup$

By a barycentric rational interpolant we understand a function of the form

\begin{align*} r(t) := \frac{\sum_{i=0}^{n-1} \frac{w_i y_i}{t-t_i} }{ \sum_{i=0}^{n-1} \frac{w_i}{t-t_i}} \end{align*} In Schneider and Werner, (proposition 12) a stable algorithm for computation of the derivatives of $r^{(k)}$ is presented. (This algorithm is reviewed here in more modern notation, in equation 5.1a.) However, this algorithm requires two passes through the data vectors $\{w_{i}\}_{i=0}^{n-1}$, $\{y_{i}\}_{i=0}^{n-1}$ and $\{t_{i}\}_{i=0}^{n-1}$.

Since I only require the first derivative $r'$, I am curious as to whether I can get the first derivative via automatic differentiation, in one pass, perhaps increasing the speed of evaluation. So I have two questions: What is the automatic differentiation formula for $r$, and by using it, will I lose the stability guaranteed by Werner and Schneider's algorithm?

$\endgroup$
3
  • $\begingroup$ What are the various symbols in the formula, and how is the $x$ on the left related to the symbols on the right? $\endgroup$ Jun 30, 2018 at 13:49
  • $\begingroup$ @WolfgangBangerth, my bad, typo. The $\{w_{i}\}_{i=0}^{n-1}$ are known as barycentric weights, which can be computed in various ways from the list of function values $\{t_i, y_i\}_{i=0}^{n-1}$. $\endgroup$
    – user14717
    Jul 1, 2018 at 1:57
  • 2
    $\begingroup$ Can't you do 5.1a in only one pass by expanding $r[x,x_j]$? Also, could you please inline 5.1a into the question to make it clearer and so that the whole of the question can be read directly here all at once? $\endgroup$
    – Kirill
    Jul 1, 2018 at 22:19

1 Answer 1

2
$\begingroup$

$ \def\a{\alpha} \def\b{\beta} \def\e{\gamma} \def\f{\delta} \def\o{{\tt1}} \def\c{\cdot} \def\d{\oslash} \def\m{\odot} \def\qiq{\quad\implies\quad} \def\g#1#2{\frac{d #1}{d #2}} \def\LR#1{\left(#1\right)} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} $To avoid confusing $t_k$ with $t,\,$ I'll use $z$ for the latter. Let's also introduce $\{\m,\d\}$ to denote Hadamard multiplication and division, and $\o$ as the all-ones vector.

For typing convenience, define the variables $$\eqalign{ x_k &= z-t_k &\qiq dx_k = dz \\ v_k &= x_k^{-1} &\qiq dv_k = -v_k^2\:dz \\ }$$ By collecting all components into vectors, the summations can be replaced with dot products, i.e. $$\eqalign{ r &= \frac{\o\c(y\m w\m v)}{\o\c(w\m v)} \;=\; \frac{(y\m w)\c v}{w\c v} \\ }$$ In vector form, calculating derivatives is easy and familiar $$\eqalign{ \g xz &= \o \\ \g vz &= -(v\m v) \\ \g rz &= \frac{(y\m w)\c \g vz - rw\c\g vz}{w\c v} \\ &= \frac{rw\c(v\m v)-(y\m w)\c(v\m v)}{w\c v} \\ &= \frac{r\o\c(w\d x\d x) - \o\c(y\m w\d x\d x)}{\o\c(w\d x)} \\ \\ }$$ This can be calculated in a single pass by accumulating four scalar sums $$\eqalign{ \a &= \sum_k \frac{w_k}{z-t_k}, \quad \b &= \sum_k \frac{y_k w_k}{z-t_k}, \quad \e &= \sum_k \frac{y_k w_k}{(z-t_k)^2}, \quad \f &= \sum_k \frac{w_k}{(z-t_k)^2} \\ }$$ Then $$\eqalign{ r &= \frac{\b}{\a}, \qquad \g rz &= \fracLR{r\f-\e}{\a} \;=\; \fracLR{\b\f-\a\e}{\a^2} \\ }$$

$\endgroup$
3
  • $\begingroup$ I don't think this computation answers OP's questions; it merely gives another formula to compute the derivative, without discussing its stability. $\endgroup$ Jul 2, 2023 at 12:12
  • $\begingroup$ I thought the OP's main question was whether the calculation could be done in one pass. $\endgroup$
    – greg
    Jul 2, 2023 at 12:20
  • $\begingroup$ The question seems to be the one in the last sentence: “What is the automatic differentiation formula for 𝑟, and by using it, will I lose the stability guaranteed by Werner and Schneider's algorithm?” $\endgroup$ Jul 2, 2023 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.