0

$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.

tent123
  • 57
  • 1
    How about using Laurent series? – MH.Lee Oct 20 '21 at 22:01
  • what book are you reading for this topic? –  Oct 20 '21 at 22:05
  • 1
    @user Numerical Analysis, Richard L. Burden & J. Douglas Faires – tent123 Oct 20 '21 at 22:06
  • I am not sure if this is the same thing, but it looks like nesting is factoring out the powers of x? In the given problem the powers on $x$ are $\frac12$ and $1$. Note that $(x^2+1) = (x + i)(x - i)$ and $ - x = - x + i - i$. Then you could factor out $(x + i)^\frac12$ but I don't think you could factor out an $x$ by this approach. – Gwendolyn Anderson Oct 20 '21 at 22:08
  • Thanks. I have a copy. Which section is that from? –  Oct 20 '21 at 22:09
  • @user section 1.2 , page 26, Accuracy loss due to round-off error can also be reduced by rearranging calculations – tent123 Oct 20 '21 at 22:13
  • What about a trig substitution with $x = tan\theta$? Then from $sec\theta - tan\theta$ factor out $\frac{1}{cos\theta} = sec\theta$? Or factor out $ x = tan\theta$ by multiplying by $\frac{sin\theta}{sin\theta}$? – Gwendolyn Anderson Oct 20 '21 at 22:17
  • perhaps my edition is different from yours; I don't find the exercise on page 26 –  Oct 20 '21 at 22:17
  • @Gwendolyn Anderson yep it is but I want to calculate $f(x)$ and $\frac{1}{f(x)}$ when $x=10,10^2,...,10^6$ – tent123 Oct 20 '21 at 22:19
  • Not sure I did the figures all right but I get $x \times (csc(tan^{-1}x) - 1)$ which has trig functions but it is in any case nested $x$'s. – Gwendolyn Anderson Oct 20 '21 at 22:26
  • You are plugging in larger and larger values of $x$ so perhaps the point is that $\sqrt(x^2 + 1)$ approaches $x$. You do mention in the problem that it is an approximation. – Gwendolyn Anderson Oct 20 '21 at 22:28
  • 1
    "Polynomial nesting technique" is usually called "Horner's Method". – Gerry Myerson Oct 20 '21 at 22:47
  • @Gerry Myerson ok thanks – tent123 Oct 20 '21 at 22:49
  • @Gerry Myerson but I actually want to reduce round-off error by rearranging calculations – tent123 Oct 20 '21 at 22:56
  • @user yep I think it is. – tent123 Oct 20 '21 at 22:57
  • 2
    @tent123 The loss of precision occurs because of taking the difference of two values which get closer and closer as $x$ increases. That problem can be circumvented by rewriting it as $,f(x) = \frac{1}{\sqrt{x^2+1},+,x},$. – dxiv Oct 21 '21 at 01:23
  • BTW, for large $x$, $\sqrt{x^2+1}-x \approx \frac1{2x}$. Even better: $\frac{2x}{4x^2+1}$ – PM 2Ring Oct 21 '21 at 02:26

2 Answers2

3

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

Claude Leibovici
  • 260,315
1

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.

Gwendolyn Anderson
  • 457