You are not logged in.
login | register

Discussion: All Topics in Calculus on Sketchpad
Topic: RE: Bisector Method in C Programming.


Post a new topic to the All Content in Calculus on Sketchpad discussion
<< see all messages in this topic
<previous message | next message >


Subject:   RE: Bisector Method in C Programming.
Author: Sione
Date: Apr 15 2004
On Apr 15, 2004, donalds wrote:

>suppose you are give a function of polynomial f(x) = >4-x3 and the question
calls to implement a program that >will finds the root of a polynomial using the
bisector >method, and that program should print the seven 7th >root of 126, the
cube root of 43 and the 5th root of >729 such that f(X) = o;

>I will be very glad to hearing from any one out there.
>Donalds,
>Uganda.


Finding roots of polynomial using BISECTION method is inefficient. BISECTION are
best use in non-polynomial functions where zeros are needed to be located. The
reason BISECTION method is not popular in polynomial root finding is because the
method does LOCAL search, where the user specifies an initial interval (closed
interval) such as between 'a' and 'b' [a,b] to search for a root. However if the
user specifies an initial interval that no roots falls in it, then BISECTION
fails because it cannot find one (root). There is also other method of making
BISECTION adaptive that given an initial guess interval [a,b] , the if it does
not find a root, then it moves along to a new interval say [b,c]  and it fails
again to find a root, then move along to [c,d] and so on until the stopping
condition reaches usually specifies by the user (say, 10 incremental interval
search maximum if no roots are found then stop). In computer algorithm (code
implementation) , this way of incremental searching for a root is VERY COSTLY in
computation (computer memory), and THERE is NO GUARANTEE that it will find a
root.

The popular method for polynomial root finding is using 'Eigen Value
Decomposition' (EVD) also called Matrix factorization. The good thing about EVD
method is it is guarantee to find ALL roots of a polynomial including the
COMPLEX roots and this method (EVD) is FAST. EVD can solve up to any order of
polynomial. Say you specify a polynomial of  100 or higher order, EVD can find
all the roots.

I wrote an applet that finds roots up to 5th order polynomial and I used EVD for
solving roots. It is found here: [WARNING - It takes a while to load]

http://mathforum.org/te/exchange/hosted/palu/polynomialroots/EducationApplets.html

I have not updated the applet yet, because the default precision I used (it is
hard coded) is ~ 2.0E-8 , this precision is too small for roots that involves
REPEATED roots. It misses some repeated roots , since the applet filters out the
complex root solution leaving only the real ones. Next version will allow the
user to specify any preferred precision.

Sorry, I do not know  C  Programming language. I write software in Java.

Cheers,
Sione.







Reply to this message          Quote this message when replying?
yes  no
Post a new topic to the All Content in Calculus on Sketchpad discussion
Visit related discussions:
Calculus
Sketchpad

Discussion Help