Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
#101 2016-06-18 03:10:00
Re: Polynomial Root Finding
sqrt' :: Double -> Double -> Double
sqrt' x guess
| guessIsGoodEnough = guess
| otherwise = sqrt' x improvedGuess
where
-- Test the precision of the guess
precision = 1e-15
guessIsGoodEnough = abs (guess * guess - x) < precision * x
-- Improve our guessed square
improvedGuess = (guess + x / guess) / 2
main = putStrLn.show $ 1.0/((sqrt' 1234567899 1) + (sqrt' 1234567898 1))1.4230249486517707e-5'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#102 2016-06-18 03:13:40
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
I am sorry, the question was a bit vague.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#103 2016-06-18 03:14:27
Re: Polynomial Root Finding
What question?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#104 2016-06-18 03:15:44
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#105 2016-06-18 03:19:29
Re: Polynomial Root Finding
What's wrong?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#106 2016-06-18 03:22:10
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
Modern languages are constructed to defeat to some extent "subtractive cancellation." This does not mean that problem has gone away, it just means that people do not notice it.
The idea was to use a basic calculator on the problem so that you could see an important algebraic point about numerical stability.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#107 2016-06-18 03:24:04
Re: Polynomial Root Finding
Modern languages are constructed to defeat to some extent "subtractive cancellation.
Oy! I used the conjugate surds method.
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#108 2016-06-18 03:25:37
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
The point is to eliminate the subtraction because in floating point arithmetic the subtraction of two nearly equal numbers results in a loss of digits.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#109 2016-06-18 03:30:04
Re: Polynomial Root Finding
BRB after dinner. Will take ~20 min
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#110 2016-06-18 03:31:01
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
The answer is to 50 places:
The first method to eliminate the subtraction is to make use of the identity:
This form does not suffer from subtractive cancellation and is therefore numerically stable.
Another way is to use the workhorse of numerical analysis... the Taylor series.
If we take the first term of the Mclaurin series of
in terms of , we get
This too, does not suffer from subtractive cancellation and should be numerically stable.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#111 2016-06-18 03:51:38
Re: Polynomial Root Finding
Did you read my code?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#112 2016-06-18 03:55:50
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
Please look at the answer in post #110. Looks like you used the first method.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#113 2016-06-18 03:57:34
Re: Polynomial Root Finding
Part II works only if epsilon is small enough wrt x
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#114 2016-06-18 03:59:27
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
It would always be small enough. If it were not small enough you would not have to do it!
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#115 2016-06-18 04:01:59
Re: Polynomial Root Finding
Modern languages are constructed to defeat to some extent "subtractive cancellation." This does not mean that problem has gone away, it just means that people do not notice it.
The idea was to use a basic calculator on the problem so that you could see an important algebraic point about numerical stability.
I know. When I try to do the subtraction right away, most significant digits cancel out. Haskell is not immune to this. For example:
*Main> ((sqrt' 1234567899 1) - (sqrt' 1234567898 1))
1.4230252418201417e-5'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#116 2016-06-18 04:03:52
- thickhead
- Member
- Registered: 2016-04-16
- Posts: 1,086
Re: Polynomial Root Finding
I used the same method multiplying and dividing by conjugate but excel has limitation. In the second one I expanded (x+1)^(1/2) by taylor series and could get better result.
{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}
Offline
#117 2016-06-18 04:04:02
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
@Agnishom Yes, lots of digits given but most of them are wrong!
@thickhead if you knew enough to use the Taylor series as well as the conjugate method then you either have had some experience in numerical work or you did some research.
Very good from both of you.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#118 2016-06-18 04:05:35
Re: Polynomial Root Finding
Yep.
What does stability mean?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#119 2016-06-18 04:08:51
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
Stability used here means resistance to subtractive cancellation. There are other forms of error too, we are only looking at one.
The first point being made is that that to a computer, (a - b)^2 is not equal to a^2 - 2 a b + b^2.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#120 2016-06-18 04:10:58
Re: Polynomial Root Finding
Why would (a-b)^2 = a^2 - b^2? That does not make sense to humans either
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#121 2016-06-18 04:13:54
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
Oh boy, my typing is getting so bad I can not even copy and paste correctly!
I meant, to a computer (a-b)^2 is not equal to a^2 - 2 a b + b^2
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#122 2016-06-18 04:18:09
Re: Polynomial Root Finding
Hm, what is it equal to, then?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline
#123 2016-06-18 04:21:24
- bobbym
- bumpkin
- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606
Re: Polynomial Root Finding
Here is how M sees it:
Change a to x and substitute b = 1.
Plot[(x - 1)^2 - (x^2 - 2 x + 1), {x, 0, 5}]
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
#124 2016-06-18 04:24:49
- thickhead
- Member
- Registered: 2016-04-16
- Posts: 1,086
Re: Polynomial Root Finding
Yep.
What does stability mean?
Stability means as iterations continue the value comes nearer and nearer to a point or you can say the difference between successive values goes on reducing. I used a term moderation factor in earlier postings but it is wrong, it is actually called damping factor.the numerical analysis is something similar to physical vibrations. if we use dampers physical system stabilizes. It is same here also.When you calculate new value from old value you need not blindly take new value for next iterations. you can blend old and new values by c*old value +(1-c)* new value where c is damping factor.0<c<1. If c is more, damping is more. In those cases where iterations slowly converge from one side without overshooting to the other side you can use negative damping. c<0 for fast convergence.
regarding experience I was professor in engineering college in engineering subjects but I had more fancy towards mathematics. I had taught "Finite Element methods" for mechanical engineering students. Possibly this should have been in the introduction.
{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}
Offline
#125 2016-06-18 04:25:41
Re: Polynomial Root Finding
eww. What was that?
'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.
Offline