7

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?

user14717
  • 2,155
  • 13
  • 14
  • What are the various symbols in the formula, and how is the $x$ on the left related to the symbols on the right? – Wolfgang Bangerth Jun 30 '18 at 13:49
  • @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}$. – user14717 Jul 01 '18 at 01:57
  • 2
    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? – Kirill Jul 01 '18 at 22:19

1 Answers1

2

$ \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} \\ }$$

greg
  • 604
  • 4
  • 9
  • I don't think this computation answers OP's questions; it merely gives another formula to compute the derivative, without discussing its stability. – Federico Poloni Jul 02 '23 at 12:12
  • I thought the OP's main question was whether the calculation could be done in one pass. – greg Jul 02 '23 at 12:20
  • 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?” – Federico Poloni Jul 02 '23 at 12:38