Numerical Method with Error

1. Aug 28, 2009

songoku

1. The problem statement, all variables and given/known data
a. Using equation x2 – a = 0, show that $$x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)$$

b. Given that Xn = √a + e, where e is a small error. Show that:

$$x_{n+1}=a^{1/2}+\frac{1}{2}\left(\frac{e^2}{a^{1/2}+e}\right)$$

c. If x0 = 4 and a = 7, where √7 = 2.646, find x3. By using the value of x3, find the error for X4 (1 significant figure)

2. Relevant equations
Newton Raphson

3. The attempt at a solution
I am able to do (a) and (b) and having trouble with (c). I've tried to find x3 using the formulas (a) and (b) and I got different answer.

Using formula (a) :

$$x_{1}=\frac{1}{2}\left(x_0+\frac{a}{x_0}\right)=2.875$$

$$x_{2}=\frac{1}{2}\left(x_1+\frac{a}{x_1}\right)=2.65489$$

$$x_{3}=\frac{1}{2}\left(x_2+\frac{a}{x_2}\right)=2.64577$$

$$x_{4}=\frac{1}{2}\left(x_3+\frac{a}{x_3}\right)=2.64575$$

So :
X4 = √a + e4
e4 = -2.5 x 10-4

Using formula (b) :
I think the error e is not a constant value because if it's constant, the value Xn = √a + e will be constant. So I assume $$e\rightarrow e_n$$ ----> just guessing (is it possible $$e\rightarrow e_{n-1} ?$$ )

Then :
X0 = √a + e0
e0 = 4 - 2.646 = 1.354

Using the value of e0 :

$$x_{1}=a^{1/2}+\frac{1}{2}\left(\frac{(e_0)^2}{a^{1/2}+e_0}\right)=2.875$$

X1 = √a + e1
e1 = 2.875 - 2.646 = 0.229

$$x_{2}=a^{1/2}+\frac{1}{2}\left(\frac{(e_1)^2}{a^{1/2}+e_1}\right)=2.65512$$

X2 = √a + e2
e2 = 2.65512 - 2.646 = 9.12 x 10-3

$$x_{3}=a^{1/2}+\frac{1}{2}\left(\frac{(e_2)^2}{a^{1/2}+e_2}\right)=2.646015663$$

X3 = √a + e3
e3 = 2.646015663 - 2.646 = 1.5663 x 10-3

$$x_{4}=a^{1/2}+\frac{1}{2}\left(\frac{(e_3)^2}{a^{1/2}+e_3}\right)=2.646000461$$

X4 = √a + e4
e4 = 2.646000461 - 2.646 = 4.6136 x 10-7

Which one is right? I think the positive one is right because from the graph of y = x2 - 7 and x0=4, the approximation will be overestimate, so the error should be positive.
But I'm not sure..

Thanks

Last edited: Aug 28, 2009
2. Aug 28, 2009

D H

Staff Emeritus
Neither one is right. You are truncating away the precision in both cases.

You are correct in that the error is not constant. Think of it this way: If the error was constant, what's the point? The entire purpose of the method is to make the error shrink with each step. The error changes with each step. It is thus better to write the nth term as

$$x_n = a^{1/2} + e_n$$

With this, the look at the expression in part (b) becomes

$$x_{n+1}=a^{1/2} +\frac{1}{2}\left(\frac{e_n^2}{a^{1/2}+e_n}\right)$$

This directly gives an expression for the error term:

$$e_{n+1}=\frac{1}{2}\left(\frac{e_n^2}{a^{1/2} + e_n}\right)$$

If you use this to calculate the error for x4 you will know how many significant digits you need to carry when evaluating x4.

3. Aug 28, 2009

songoku

Hi D H
I don't understand this fully. I used the digits until several decimal places and I think it still holds precision. I realized my mistake not answering the question in 1 significant figure, but is it really lost its precision?

My lastest attempt:
x0 = √a + e0
e0 = 4 - 2.646 = 1.354

Using the formula you suggest, I found :
e1 = 0.2291645

And continuing it until e4, I got :
e4 = 4.66179395 x 10-11 = 5 x 10-11 ( 1 SF )

Do I get it right?

The answer is different form my previous two. Now I am starting to think that my answer is really lost the precision. But why ?

Thanks

4. Aug 28, 2009

D H

Staff Emeritus

5. Aug 28, 2009

songoku

Hi D H

I re-calculate my answer without truncating it, i.e. I directly use the answer from calculator to compute the next value and get the answer pretty close to my previous two, which are different from the answer I got using the formula you suggested. Are my answer still not precise?

Thanks

6. Aug 28, 2009

D H

Staff Emeritus
"Pretty close" isn't good enough when you are trying to find an error that is about 5 x 10-11 (which, BTW, is correct). Too how many decimal places do you need to carry out your work to detect that small an error?

7. Aug 28, 2009

songoku

Hi D H

Yes I can't find the error until 10-11 using my previous work. But I don't know the reason. I didn't truncate my calculation so I think the reason is not truncation.

8. Aug 29, 2009

D H

Staff Emeritus
Going back to your original post, you used a truncated value for the square root of 7. This worked fine up to the calculation of e2 because the truncation error was smaller than the numerical error up to this point. Beyond this point, the truncation error overwhelms the errors inherent in Heron's method. Your calculated errors for e3 and beyond have zero precision because of your use of 2.646 for the square root of 7.

There is an important lesson to be learned here: You need to take care when you are truncating a result.

9. Aug 29, 2009

songoku

Hi D H
That approximation is given by the question and I think it should be used.

Sorry, I don't get it. What is truncation error and what is numerical error ?

Heron's method? I think Heron's method is used to find area of triangle. Can it be used here? Or maybe there is another formula called Heron besides for triangle?

Thanks

10. Aug 29, 2009

D H

Staff Emeritus
Regarding 2.646: State the question, please. Did it explicitly say to use 2.646 as the value for the square root of seven, or did it say something along the lines of "If x0 = 4 and a = 7, where $\surd 7 \approx 2.646$, find x0 ..."

Using the error estimation technique,

$$e_{n+1}=\frac{1}{2}\left(\frac{e_n^2}{a^{1/2} + e_n}\right)$$

with e2=9.12x10-3 and 2.646 as an approximation of √7 yields e3=1.57x10-5. So, what is 2.646+1.57x10-5? The answer is 2.646. Saying 2.6460157 as you did in the original post is erroneous. The correction term e3 is much smaller than the truncation error.

Regarding truncation error (better stated as rounding error) versus numerical error: Rounding error is what you get when you arbitrarily round a numerical result to some degree of precision. Each step of the application of this iterative algorithm has some error in it, even with infinite precision. The zeroth and first steps of the iteration, x0=4 and x1=(4+7/4)/2=23/8, will have zero rounding error in a base 2 representation (e.g., a computer) or on a base 10 calculator with four or more decimal places of accuracy. The numerical error is anything but zero.

Regarding this algorithm as a whole: While this algorithm can be derived from Newton's method, it is much older than that. The algorithm predates Newton by a couple thousand years. It may have been known to the Babylonians and was described by Heron (or Hero) of Alexandria. See http://www.mathpages.com/HOME/kmath190.htm, for example.

11. Sep 6, 2009

songoku

Hi D H
I've posted all the question. It didn't explicitly state that we have to use √7 = 2.646, but it did mention that √7 = 2.646 so I think that we should use this value. Or maybe not?

Why is 2.6460157 is erroneous compared to 2.646? I think it should be more precise because it contains more digits and it's not rounded.

And I found out my mistake when calculating e3. It should be 1.5663 x 10-5, not 1.5663 x 10-3, although it's still differs when using your formula (e3=1.57331257 x 10-5).

But when I used this value to calculate x4, I got x4=2.646 and e4=0, which is absolutely wrong.

I still don't get the idea about precision...
Thanks

12. Sep 6, 2009

D H

Staff Emeritus
If you want to compute the error in the fourth iteration of this square root algorithm, absolutely not

It is erroneous because you rounded √7 to 4 significant digits. This rounding poisons all subsequent calculations. 2.646+0.0000157 = 2.646 is correct; the addend is lost in the truncation error. Saying √7+0.0000157=2.6460157 is incorrect. The correct answer (to the accuracy implied by the addend) is 2.6457670.

Another way to look at it: The difference between 2.646 and √7 is 0.000248688935... That is your truncation error, and it is almost 16 times greater than the number your are trying to add to 2.646.

13. Sep 6, 2009

songoku

Hi D H

Oh I think I get it now.

Thanks a lot for your help and passion :)