polynomial nesting technique for $f(x)=\sqrt{x^2+1}-x$

Question

$f(x)=\sqrt{x^2+1}-x$

$x=10,10^2,...,10^6$

I want to calculate $f(x)$ and $\frac{1}{f(x)}$ and I want to use polynomial nesting technique that closest approximation to the real value.

I'm beginner in this topics so how can I use polynomial nesting when there is square?

when we don't have square, for example

$f(x) = 6x^2 -7x + 3x^4 +11 - 2x^3$

we can write as:

$((((3)x - 2)x + 6)x - 7)x + 11$

Sorry for trivial question but I'm really confused.

Answer 1

In comments, you precised that your goal is "to reduce round-off error by rearranging calculations" .

Using Horner's method means that you will approximate $f(x)$ by a long polynomial, probably comming from series expansions.

Expanded as series, we have $$f(x)=\sqrt{x^2+1}-x=\frac{1}{2 x}-\frac{1}{8 x^3}+O\left(\frac{1}{x^5}\right)$$

So, better than series would be the $[n,n+1]$ Padé approximant $P_n$. I give you below the very first ones $$P_1=P_2=\frac{2 x}{4 x^2+1} \qquad P_3=P_4=\frac{4x\left(2 x^2+1\right)}{16 x^4+12 x^2+1}$$ The last one is quite accurate since $$f(x)-P_3=\frac{1}{512 x^9}+O\left(\frac{1}{x^{11}}\right)$$

For the "worst" case $x=10$ $$\sqrt{101}-10= \color{red}{0.0498756211}21\quad \text{and} \quad P_3=\frac{8040}{161201}=\color{red}{0.049875621119}$$

For the reciprocal of $f(x)$, it would be the $[n+1,n]$ Padé approximant $Q_n=\frac 1{P_n}$. Tried again for $x=10$ $$\frac{1}{\sqrt{101}-10}=\color{red}{20.049875621}12\quad \text{and} \quad Q_3=\frac{161201}{8040}=\color{red}{20.04987562189}$$

For sure, we can do better. I give you the next one $$P_5=P_6=\frac{x(32 x^4+32 x^2+6)}{64 x^6+80 x^4+24 x^2+1}$$ which, for $x=10$ will give an absolute error of $1.18\times 10^{-17}$.

Answer 2

Let me give this a shot, and I will not use complex numbers or trigonometric functions.

Part I.

$f(x)=\sqrt{x^2+1}-x$

Let $g(x)=\sqrt{x^2+1}$ ... and setting $a = x^2, b = 1,$ and $n = \frac12$

Then $(a + b)^n = $$\sum_{i=0}^n$$ $$n\choose{i}$ $a^{n-i} b^i$

$ = 1 + \frac{x^2}2 - \frac{x^4}8 + \frac{x^6}{16} - \frac{5x^8}{128} + ...$

Then $f(x) = g(x) - x = 1 - x + \frac{x^2}2 - \frac{x^4}8 + \frac{x^6}{16} - \frac{5x^8}{128} + ...$

$f(x) \approx (((\frac1{16}x^2 - \frac18)x^2 + \frac12)x - 1)x + 1$

The tail of this series will be significant for large $x$.

Part II.

$f(x)=\sqrt{x^2+1}-x = (x^2+1)^\frac12 - (x^2)^\frac12$

$= (x^2+1)^\frac12 - (x^2 + 1 - 1)^\frac12$

Let $ w = x^2+1$

$f(w)= (w)^\frac12 - (w-1)^\frac12 = (w)^\frac12 \times ( 1 - \frac{w-1}{w}^\frac12$ )

Now we can see as $x$ grows large, $w = x^2 + 1$ grows even larger and $\frac{w-1}{w}^\frac12$ approaches $1^-$ so $( 1 - \frac{w-1}{w}^\frac12 )$ approaches $0^+$ and $f(w)$ similarly approaches $0^+$.

I believe this would be the only way to factor out the variable since there are not many powers of $x$ in the equation of $f(x)$, the powers are low.