Program for Approximating nth root of a Number

[annie122]

I have a question for a programming exercise I'm working on for C.

The problem is to "Write a program that uses Newton's method to approximate the nth root of a number to six decimal places." The problem also said to terminate after 100 trials if it failed to converge.

Q1. What does "converge" mean?
Does it mean the difference between two approximation can be made as small as I like?

Q2. On what condition should the program terminate?
There are two such conditions: 1) if the loop has been executed 100 times, 2) the difference between the "true" answer and the approximation is less than 0.000001.
I know how to set 1), but how should I express 2)?
Right now, I am setting the condition as
|approximation - root| < 0.00001,
but I feel it's kind of cheating, because I'm not supposed to know the real answer if I'm making approximations.
Are there any other any ways to express the condition, especially one involving the function f(x) = x^n - c (x is the nth root of c)?

 

[I like Serena]

Re: question on program for approximating nth root of a number

Hi Yuuki! :)

I have a question for a programming exercise I'm working on for C.

The problem is to "Write a program that uses Newton's method to approximate the nth root of a number to six decimal places." The problem also said to terminate after 100 trials if it failed to converge.

Q1. What does "converge" mean?
Does it mean the difference between two approximation can be made as small as I like

Yes. Basically.
More specifically, that you can get as close to the nth root as you want by just taking enough trials.

Q2. On what condition should the program terminate?
There are two such conditions: 1) if the loop has been executed 100 times, 2) the difference between the "true" answer and the approximation is less than 0.000001.
I know how to set 1), but how should I express 2)?
Right now, I am setting the condition as
|approximation - root| < 0.00001,
but I feel it's kind of cheating, because I'm not supposed to know the real answer if I'm making approximations.
Are there any other any ways to express the condition, especially one involving the function f(x) = x^n - c (x is the nth root of c)?

Exactly. You're not supposed to use the real root.
But what you can do is setting the condition as for instance
$$|\text{approximation} - \text{previous approximation}| < 0.0000001$$
If you achieve that, it is unlikely that the first 6 decimal digits will change in more iterations.

 

[annie122]

Re: question on program for approximating nth root of a number

Thanks. :)

I set a new variable root0 to store the previous approximation, and set the condition as you said.
It worked beautifully.

 

[zzephod]

It is possible to estimate the error in an iterate directly (assuming it small anyway).

Let $$x$$ be the 6-th root of $$k$$ and $$x_n$$ an estimate of $$x$$ with error $$\varepsilon_n$$ such that:

$$x=x_n+\varepsilon_n$$

Then raising this to the 6-th power gives:

$$x^6=x_n^6 + 6 \varepsilon_n x_n^5 + O(\varepsilon_n^2)$$

Now ignoring second and higher order terms in $$\varepsilon$$ and rearranging we get:

$$\varepsilon_n=\frac{x_n^6-x^6}{6x_n^5}=\frac{x_n^6-k}{6x_n^5}$$

OK let's look at an example: Take $$k=66$$, and $$x_n=2$$, so $$x_n^6=64$$, then

$$\varepsilon_n=\frac{66-64}{6\times32}\approx 0.01042$$

which compares nicely with $$66^{1/6}=2.01028...$$

The above is very similar (for similar read identical) to computing the next iterate and taking the difference of the iterates as an estimate of the error in the first.

 

[I like Serena]

It is possible to estimate the error in an iterate directly (assuming it small anyway).

It is also possible to specify an upper boundary for the remaining error in a specific iteration (in this specific case).

First off, after the first (positive) iteration, all iterations are guaranteed to be above the root.
The remaining error in those iterations is guaranteed to be less than the change in the approximation.