Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#101 2016-06-18 03:10:00

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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))

Run here

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

Re: Polynomial Root Finding

bobbym wrote:

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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}]

JJebxi2.png


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

Agnishom wrote:

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,843
Website

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

Board footer

Powered by FluxBB