Square root of x : $\sqrt{x}$ (Numerical Method)

Question

$$f(x) = \sqrt{x}$$
has to be approximated by polynomial interpolation $p(x_n) = f(x_n)$ with the positions $\{x_n\} = \{1,4\}$. For such problem which method is the fastest? And find $p(2)$.

My attempt:

Newton's Method:

$p(x) = x_{n+1} = x_n + \frac{g(x_i)}{g'(x_n)}$

where $g(x) = x^2 - 1$

then we can find the roots of the given number. But I'm not sure if its the fastest way to calculate the square roots.

Thanks.

Also (as far as computer methods go), it depends on how big $x$ is, and how precise the answer needs to be — Ben Grossmann, Jun 07 '16 at 13:27
For pencil/paper, there is the "digit by digit" method given here — Ben Grossmann, Jun 07 '16 at 13:29
OK. So you have a derivative bound of $1/2$ on this interval (why?). If you want to compute $\sqrt{x}$ to within $\epsilon$ on all of $[1,4]$ you can choose a mesh where the grid spacing is at most $\frac{\frac{\epsilon}{2}}{\frac{1}{2}}=\epsilon$, precompute $\sqrt{x}$ at the mesh points to within an accuracy of $\epsilon/2$ using something like Newton iteration, and then piecewise linearly interpolate. — Ian, Jun 07 '16 at 13:43
However it looks like in your problem they specifically tell you to use just two grid points, in which case you're taking the interpolating polynomial of $(1,1),(4,2)$ which is just the line between them. — Ian, Jun 07 '16 at 13:44
OK, well, it's essentially the same, you just have to do some actual work to do the interpolation in that case. Do you know how to do polynomial interpolation? — Ian, Jun 07 '16 at 13:46

score 1 · Accepted Answer · answered Jun 07 '16 at 13:37

1

You problem asks for $p(x) = \frac{4-x}{4} + \frac{x}{2}$ for which $p(0) = 1 = f(1)$ and $p(4) = 2 = f(4)$. Then $p(2) = \frac{3}{2}$.

answered Jun 07 '16 at 13:37

Carl Christian

12,583
1
14
37

how do we know $p(x) = \frac{4-x}{4} + \frac{x}{2}$ ?? – rndflas Jun 07 '16 at 13:42
Your problem specified two nodes, namely $x_0 = 1$ and $x_1 = 4$ and said to apply interpolation. As there is one and only one polynomial of degree 1 which interpolates $f$ on those two nodes and $p$ does the job it must be the interpolating polynomial required. – Carl Christian Jun 07 '16 at 13:54
what would be p(x) if ${x_n} = {0,1,4,9}$?? – rndflas Jun 07 '16 at 13:59
1

Then you need to apply the general formula for interpolating polynomial of degree at most 3. Either compute Lagrange's form or Newton's form of the interpolating polynomial. – Carl Christian Jun 07 '16 at 14:22

score 0 · Answer 2 · answered Jun 07 '16 at 13:26

0

There are available many methods like

1> the Quasi Newton

2> Secant method

3>fixed point iteration method

All of these you can find explained in Justin Solomon's book Numerical Algorithms

answered Jun 07 '16 at 13:26

Qwerty

6,165

Square root of x : $\sqrt{x}$ (Numerical Method)

2 Answers2