Is my (Java-code) algorithm for Regula Falsi 100% correct?

[s3a]

Homework Statement

I'm just trying to do homework problems involving the Regula Falsi numerical method, and the solutions in my books seem to have a lot of mistakes, so I was hoping I could make a program to generate solutions for myself, so that I could check if I'm doing things correctly when I learn, and later on, review.

Homework Equations

Regula Falsi formula(e):
x_1 = [a f(b) - b f(a)] / [f(b) - f(a)],

and then for i >= 2,

x_i = [x_L f(x_R) - x_R f(x_L)] / [f(x_L) - f(x_R)], where x_L is the largest left endpoint of the ith sub-interval and x_R is the smallest right endpoint of the ith sub-interval.

The Attempt at a Solution

Here is the computer program I made.:
http://dpaste.com/3CEZ65P

Could someone please let me know if my code is 100% correct? (I ask because I don't know what to trust as being correct, and if someone who knows this stuff better than me could confirm that my code is 100% correct, then it would make me feel more relaxed, knowing that what I'm learning is in fact correct. (I don't want to learn something incorrect, while thinking it's correct.))

Basically, I seem to be getting the correct answers to things, but I'd like to know if I'm just getting the correct final answers because the bounds keep getting smaller, while still surrounding the value, despite doing something else incorrectly, such as computing the incorrect ith intermediate value, or if it's truly the case that I'm doing everything correctly (as the Regula Falsi method requires).

Any input would be GREATLY appreciated!

 

[willem2]

The regula falsi calculation is ok, but there is a problem with the stopping rule.
You stop if the decimals of the current and the next intermediate point rounded to m decimal places are the same. This would always work if the final answer was between those two points, but this is not always so. The final answer is between a and b, so if those have the same decimals you can stop.

 

[s3a]

Thank you very much for checking my code. :)

Just to make sure that I understood what you said, is what you said that the only problem that you can see with my algorithm is that, although it always works on the (open) interval (a,b), it does not always work on the (closed) interval [a,b]?

If so, is the following code sample 100% correct? (The new lines of code that I added range from line 28 to 31.):
http://dpaste.com/3CKC1ZM

(Also, to state it explicitly, my algorithm assumes that there is exactly one root in [a,b] and that f(a) f(b) < 0.)

 

[willem2]

Thank you very much for checking my code. :)

Just to make sure that I understood what you said, is what you said that the only problem that you can see with my algorithm is that, although it always works on the (open) interval (a,b), it does not always work on the (closed) interval [a,b]?

No, I meant your answer is occasionally off by 1 in the least significant digit, because you sometimes stop too early.
For example, if you would compute x*e^x - 2 =0, you get x = 0.852605502...
The intermediate values you get when you round off to 6 digits are:

0.852603699 0.852604
0.852605307 0.852605
0.852605481 0.852605 <-you would stop here.
0.852605500 0.852606 <-but this is closest to the answer.
0.852605502 0.852606

Only if a and b rounded off are the same, you can be sure that you're done.

 

[s3a]

Is this ( http://dpaste.com/2A85W61 ) closer to what you're saying?

(It's infinite looping, though; for some reason, f(intermediatePoint) is always less than 0, so b always remains 1.0.)

 

[Mark44]

Is this ( http://dpaste.com/2A85W61 ) closer to what you're saying?

(It's infinite looping, though; for some reason, f(intermediatePoint) is always less than 0, so b always remains 1.0.)

Your code checks only to see if f(a) and f(b) are opposite in sign. You need additional else clauses to check for both being the same sign, either both positive or both negative.

Also, inside each of your two if / else if blocks, you're not checking for f(intermediatePoint) == 0.0.

BTW, why not post your code directly here instead of linking to it? It's only text. Put it inside a pair of code tags like so:
[code=java]
// Some java code
[/code]

 

[s3a]

After unsuccessfully trying to do what you said to do in my code, I tried doing this problem, by hand, and I'm running into the same problem as my Java code.

Basically, why is it wrong to just check if two consecutive roots, x_i and x_(i+1), are equal, when rounded to a certain common amount of decimal places? Aren't x_i and x_(i+1) always bounds to the actual root? If f(x_i) * f(x_(i+1)) < 0, then by the intermediate value theorem, that should be the case, shouldn't it? Do the f(x_i) and f(x_(i+1)) pairs not always differ in sign?

 

[Mark44]

I don't believe your round() function is working like you think it is. I think your intent is to add a 0 character in each iteration of the for loop, but it's actually adding the number 0. These are very different things. The character '0' has an ASCII code of 48; the number 0 corresponds to ASCII code 0, or the null character.

public static double round(double value, int places) {

        String pattern = "0.";
        for(int i = 0; i < places; i++) {          
            pattern += 0;   // <--- This is flaky
        }
      
        DecimalFormat decimalFormat = new DecimalFormat(pattern); // https://docs.oracle.com/javase/8/docs/api/java/text/DecimalFormat.html#DecimalFormat-java.lang.String-
        decimalFormat.setRoundingMode(RoundingMode.HALF_UP);
      
        return Double.parseDouble(decimalFormat.format(value));
    }

The statement inside the for loop should be

pattern += "0";​

You want to append the string consisting of the character 0, not just the number 0.

 

[s3a]

I'm pretty sure that "Hello" + 5 yields the exact same thing as "Hello" + "5", but I added the quotation marks anyways, just to be safe. That, and it's what I intended to do anyways. Running the program with the quotation marks added yielded the same result, as I expected.

Having said that, when I do this problem by hand, I seem to encounter the same problem as when I do it by software (which is obtaining 0.852605, instead of 0.852606), so I strongly believe something is wrong with the theory, not the Java syntax.

Basically, if I'm correct (but I guess I'm wrong somewhere), the regula-falsi formula always yields an x value between the largest lower bound and smallest upper bound, where the most-recently-computed x_i becomes one of the ends of the most-recent bounding interval, which seems to satisfy what willem2 said, which is "Only if a and b rounded off are the same, you can be sure that you're done." I also feel like I could make a very similar argument about the bisection method, with which I also happen to encounter the exact same problem (which is obtaining 0.852605, instead of 0.852606).

 

[Mark44]

I'm pretty sure that "Hello" + 5 yields the exact same thing as "Hello" + "5", but I added the quotation marks anyways, just to be safe. That, and it's what I intended to do anyways. Running the program with the quotation marks added yielded the same result, as I expected.

That's surprising to me, but then I'm a bit rusty with Java, and haven't really written any Java code for about 20 years. Apparently, in this regard, Java operates very differently from C and C++, with the + operator doing a lot of conversions "under the hood."

Having said that, when I do this problem by hand, I seem to encounter the same problem as when I do it by software (which is obtaining 0.852605, instead of 0.852606), so I strongly believe something is wrong with the theory, not the Java syntax.

Basically, if I'm correct (but I guess I'm wrong somewhere), the regula-falsi formula always yields an x value between the largest lower bound and smallest upper bound, where the most-recently-computed x_i becomes one of the ends of the most-recent bounding interval, which seems to satisfy what willem2 said, which is "Only if a and b rounded off are the same, you can be sure that you're done." I also feel like I could make a very similar argument about the bisection method, with which I also happen to encounter the exact same problem (which is obtaining 0.852605, instead of 0.852606).

As a guess, I would say that instead of rounding a and b as you are doing, compare the previous solution value with the current solution value. When their values agree in however many decimal places are required, then you're done. I would also truncate the values I'm comparing rather than round them, using the FLOOR RoundingMode instead of HALF_UP.

 

[s3a]

That's surprising to me, but then I'm a bit rusty with Java, and haven't really written any Java code for about 20 years. Apparently, in this regard, Java operates very differently from C and C++, with the + operator doing a lot of conversions "under the hood."

I'm making a mental note of this for when I deeply study C and/or C++. :)

As a guess, I would say that instead of rounding a and b as you are doing, compare the previous solution value with the current solution value. When their values agree in however many decimal places are required, then you're done.

Unless I'm misunderstanding you, I am checking to see if if the two consecutive root approximations agree to m decimal places (where, if I'm correct, comparing the current approximation to the next approximation, like I am doing, is the same thing as comparing the current approximation to the previous one, like you are suggesting); checking to see if the two consecutive root approximations agree to m decimal places is what the rounding's for; I don't do any rounding, until the end.

I would also truncate the values I'm comparing rather than round them, using the FLOOR RoundingMode instead of HALF_UP.

I feel like that could cause more problems, such as if root approximations of 3.15 (I chose this number arbitrarily) from some function were being approximated on both ends; for example, if the left side would be converging like 3.148888888888888888888, 3.1499999999999999999, etc and if the right side would be converging like 3.151111111111111111, 3.1500000000000000001, etc; a solution would never be found, if truncation would be used (since the left side's approximation would always be truncated to 3.14 and the right side's approximation would always be truncated to 3.15).

Also, most importantly, truncating would not solve the bug willem2 mentioned, though. That is, both 0.852605307 and 0.852605481 would be truncated to 0.852605 (instead of 0.852606).

 

[Mark44]

Unless I'm misunderstanding you, I am checking to see if if the two consecutive root approximations agree to m decimal places (where, if I'm correct, comparing the current approximation to the next approximation, like I am doing, is the same thing as comparing the current approximation to the previous one, like you are suggesting); checking to see if the two consecutive root approximations agree to m decimal places is what the rounding's for; I don't do any rounding, until the end.

I think there's a misunderstanding of terms. I don't see a and b as being root approximations -- I see them as endpoints of an interval that contains the root. You actually get an approximation of the root in what you call intermediatePoint. What I am saying is to compare the previous intermediatePoint value to the present one.

With regard to "I don't do any rounding, until the end." -- that's not true. In each iteration of the while loop in findRootCorrectToMDecimalPlaces(), you round both a and b before comparing them. Here's your code.

while( true ) {
            
            if( round(a,correctToMDecimalPlaces) == round(b,correctToMDecimalPlaces) ) {
                
                return round(a,correctToMDecimalPlaces);
            }

Again, what I am saying is to not round a and b, but instead round (or truncate) successive values of intermediatePoint.

I feel like that could cause more problems, such as if root approximations of 3.15 (I chose this number arbitrarily) from some function were being approximated on both ends; for example, if the left side would be converging like 3.148888888888888888888, 3.1499999999999999999, etc and if the right side would be converging like 3.151111111111111111, 3.1500000000000000001, etc; a solution would never be found, if truncation would be used (since the left side's approximation would always be truncated to 3.14 and the right side's approximation would always be truncated to 3.15).

Also, most importantly, truncating would not solve the bug willem2 mentioned, though. That is, both 0.852605307 and 0.852605481 would be truncated to 0.852605 (instead of 0.852606).

Rounding or truncating both of those numbers to 6 decimal places would result in .852605.

If you search online, you can find algorithms for the Regula Falsi method or variations on it (see https://en.wikipedia.org/wiki/False_position_method). Here's one I found, in C, the Illinois variation on Regula Falsi. It should look fairly recognizable to you, even though you are coding in Java. The only thing you might not recognize is fabs(), the (floating point) absolute value function.

/* s,t: endpoints of an interval where we search
   e: half of upper bound for relative error
   m: maximal number of iterations */
double FalsiMethod(double s, double t, double e, int m)
{
   double r,fr;
   int n, side=0;
   /* starting values at endpoints of interval */
   double fs = f(s);
   double ft = f(t);

   for (n = 0; n < m; n++)
   {

       r = (fs*t - ft*s) / (fs - ft);
       if (fabs(t-s) < e*fabs(t+s)) break;
       fr = f(r);

       if (fr * ft > 0)
       {
         /* fr and ft have same sign, copy r to t */
         t = r; ft = fr;
         if (side==-1) fs /= 2;
         side = -1;
       }
       else if (fs * fr > 0)
       {
         /* fr and fs have same sign, copy r to s */
         s = r;  fs = fr;
         if (side==+1) ft /= 2;
         side = +1;
       }
       else
       {
         /* fr * f_ very small (looks like zero) */
         break;
       } 
    }
    return r;
}

 

[s3a]

I don't mind trying to decypher C code, but I'd like to have an algorithm that, like mine, only needs to know the endpoints of the interval and to what accuracy I want my root (as in how many decimal places, not as in giving a maximum error). That algorithm asks for an error as well as a maximal number of iterations. (I find what my algorithm asks to be more intuitive.) (I'd also prefer fixing my algorithm, rather than just copying some random one from the Internet, since, for one, it'd be more enlightening to figure out the flaw with my logic.)

By the way, for what it's worth, I think I found the algorithm you pasted, written in Java, here.:
http://www.sanfoundry.com/java-program-regular-falsi-algorithm/