Error Analysis in Numerical Methods for Solving Equations

[songoku]

Homework Statement

a. Using equation x² – a = 0, show that [tex]x_{n+1}=\frac{1}{2}\left(x_n+\frac{a}{x_n}\right)[/tex]


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

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


c. If x₀ = 4 and a = 7, where √7 = 2.646, find x₃. By using the value of x₃, find the error for X₄ (1 significant figure)

Homework Equations

Newton Raphson

The Attempt at a Solution

I am able to do (a) and (b) and having trouble with (c). I've tried to find x₃ using the formulas (a) and (b) and I got different answer.

Using formula (a) :

[tex]x_{1}=\frac{1}{2}\left(x_0+\frac{a}{x_0}\right)=2.875[/tex]

[tex]x_{2}=\frac{1}{2}\left(x_1+\frac{a}{x_1}\right)=2.65489[/tex]

[tex]x_{3}=\frac{1}{2}\left(x_2+\frac{a}{x_2}\right)=2.64577[/tex]

[tex]x_{4}=\frac{1}{2}\left(x_3+\frac{a}{x_3}\right)=2.64575[/tex]


So :
X₄ = √a + e₄
e₄ = -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 [tex]e\rightarrow e_n[/tex] ----> just guessing (is it possible [tex]e\rightarrow e_{n-1} ?[/tex] )

Then :
X₀ = √a + e₀
e₀ = 4 - 2.646 = 1.354


Using the value of e₀ :

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

X₁ = √a + e₁
e₁ = 2.875 - 2.646 = 0.229


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

X₂ = √a + e₂
e₂ = 2.65512 - 2.646 = 9.12 x 10^-3


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

X₃ = √a + e₃
e₃ = 2.646015663 - 2.646 = 1.5663 x 10^-3


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

X₄ = √a + e₄
e₄ = 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 = x² - 7 and x₀=4, the approximation will be overestimate, so the error should be positive.
But I'm not sure..

Thanks

 

[D H]

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

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 n^th term as

[tex]x_n = a^{1/2} + e_n[/tex]

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

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

This directly gives an expression for the error term:

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

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

 

[songoku]

Hi D H

You are truncating away the precision in both cases.

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?

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

The question is asking about e₄ , not x₄

My lastest attempt:
x₀ = √a + e₀
e₀ = 4 - 2.646 = 1.354

Using the formula you suggest, I found :
e₁ = 0.2291645

And continuing it until e₄, I got :
e₄ = 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

 

[D H]

You lost precision precisely because you truncated your answers. The truncation destroyed your precision.

 

[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

 

[D H]

"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?

 

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

 

[D H]

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 e₂ 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 e₃ 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.

 

[songoku]

Hi D H

Going back to your original post, you used a truncated value for the square root of 7.

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

This worked fine up to the calculation of e₂ because the truncation error was smaller than the numerical error up to this point.

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

Beyond this point, the truncation error overwhelms the errors inherent in Heron's method.

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

 

[D H]

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 x₀ = 4 and a = 7, where [itex]\surd 7 \approx 2.646[/itex], find x₀ ..."

Using the error estimation technique,

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

with e₂=9.12x10^-3 and 2.646 as an approximation of √7 yields e₃=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 e₃ 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, x₀=4 and x₁=(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.

 

[songoku]

Hi D H

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 x₀ = 4 and a = 7, where [itex]\surd 7 \approx 2.646[/itex], find x₀ ..."

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?

Using the error estimation technique,

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

with e₂=9.12x10^-3 and 2.646 as an approximation of √7 yields e₃=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 e₃ is much smaller than the truncation error.

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 e₃. It should be 1.5663 x 10^-5, not 1.5663 x 10^-3, although it's still differs when using your formula (e₃=1.57331257 x 10^-5).

But when I used this value to calculate x₄, I got x₄=2.646 and e₄=0, which is absolutely wrong.

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

 

[D H]

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?

If you want to compute the error in the fourth iteration of this square root algorithm, absolutely 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.

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.

 

[songoku]

Hi D H

Oh I think I get it now.

Thanks a lot for your help and passion :)