Finding the root of a polynomial

• 08-05-2009
budala
Finding the root of a polynomial
I can find the root of a polinomial in a segment [A,B]. I can find it if root == A, root == B or if root is between A and B. And all of this using 2 methods not one.

But for the life of me I cannot determine if the root is not in the segment. For example, let's say that the polynomial is a simple one
Code:

`x-5=0`
The root is obviously 5. But if A and B are both bigger (A=10, B=14) or both smaller (A=-1, B=4) than the root (5 here), then I am stuck!! :(

EDIT: EUREKA!!! I figured it out. If both A and B are of the same sign (both positive or negative) than the root simply isn't in the segment [A,B].

EDIT 2: IDIOT!!! why shouldn't A and B be both positive, A= 3, B=10. A and B don't matter. There values once inputed in the polynomial matter.

so if we transform
Code:

`x-5=0`
into
Code:

`f(x) = x-5`
then f(A) and f(B) must be of the same sign.
• 08-05-2009
KBriggs
• 08-06-2009
transgalactic2
so you are given a string like this one
"x-5=0"

and you want to solve it?
i couldnt understand in details what is your goal?
• 08-06-2009
budala
Ok, this is my code. I half the segment if the root is in it until the segment length reaches an error tolerance.

Code:

```#include <stdio.h> #include <math.h> float f(float x) {         return (x-5); } void Halfing () {         float a,b,s,e;         int n = 0;         int test = 0;                 do         {                 printf("Enter the beginning of the segment -> ");                 scanf("%f",&a);                 printf("Enter the end of the segment -> ");                 scanf("%f",&b);                 if ((f(a) > 0 && f(b) > 0) || (f(a) < 0 && f(b) < 0))                 {                         printf("The root is not inside the segment [%4.2f,%4.2f]",a,b);                         printf("\nChoose other endpoints\n");                 }                 else test = 1;         } while  (test != 1);                 printf("Enter error tolerance -> ");         scanf("%f",&e);                 if (f(a) == 0) printf("The root is at an endpoint and it is %6.4f\n",a);         else if (f(b) == 0) printf("The root is at an endpoint and it is %6.4f\n",b);         else                {                 do                 {                         n++;                         s = (a+b)/2;                         printf("%d. pass x = %6.4f\n",n,s);                         if (f(a)*f(s)<0)  b = s;                         else  a = s;                 } while (fabsf(a-b)>e);                                        printf("\nRoot = %6.4f", (a+b)/2);         } } int main (int argc, const char * argv[]) {         Halfing ()         return 0; }```
• 08-06-2009
sirjis
You probably can't just look at the values of the endpoints. Consider

f(x) = x^2 - 3,

with A = -2 and B = 2.

Then f(A) = 1 and f(B) = 1. However, even though they have the same sign, there are two roots in the domain, sqrt(3) and -sqrt(3). If you are limited to just linear functions, your algorithm is fine, but I don't think there's any foolproof way for a general polynomial (although there is a way for 2nd order, and maybe some higher orders). You can make it better by checking many points for sign changes, though, instead of just two.