Skip to content

bisection method for minimization added - #1

Merged
clbustos merged 1 commit into
SciRuby:masterfrom
rajatkapoor:bisection
Feb 20, 2014
Merged

bisection method for minimization added#1
clbustos merged 1 commit into
SciRuby:masterfrom
rajatkapoor:bisection

Conversation

@rajatkapoor

@rajatkapoor rajatkapoor commented Feb 18, 2014

Copy link
Copy Markdown

I have added the bisection method for minimization.
Below is the output log for first 15 iterations compared to the results given on the wikipedia page (https://en.wikipedia.org/wiki/Bisection_method#Example:_Finding_the_root_of_a_polynomial).
The results match.
NOTE:
The wikipedia page mentions the first iteration in the state before the iteration, but my log mentions the state of the interval after the iteration, because that was the convention followed in the previously implemented Golden Section Method. Also, the Cn mentioned on the wikipedia page is equivalent to bx in my code(again following the convention of the previously written code)

PS: I will come up with a test suite for all methods soon.
Thanks

1 #iteration number
1.5 #lower limit of interval after first iteration, equivalent to wikipedia's interval lower limit in iteration 2
2.0 #upper limit of interval after first iteration, equivalent to wikipedia's interval lower limit in iteration 2
-0.125 # f(ax)
4.0 # f(cx) NOTE that f(cn) on wiki page is equal to f(bx) in the code
0.5 # (ax-cx).abs
4.125 # (f(ax)-f(cx)).abs
2
1.5
1.75
-0.125
1.609375
0.25
1.734375
3
1.5
1.625
-0.125
0.666015625
0.125
0.791015625
4
1.5
1.5625
-0.125
0.252197265625
0.0625
0.377197265625
5
1.5
1.53125
-0.125
0.059112548828125
0.03125
0.184112548828125
6
1.515625
1.53125
-0.034053802490234375
0.059112548828125
0.015625
0.09316635131835938
7
1.515625
1.5234375
-0.034053802490234375
0.012250423431396484
0.0078125
0.04630422592163086
8
1.51953125
1.5234375
-0.010971248149871826
0.012250423431396484
0.00390625
0.02322167158126831
9
1.51953125
1.521484375
-0.010971248149871826
0.0006221756339073181
0.001953125
0.011593423783779144
10
1.5205078125
1.521484375
-0.005178886465728283
0.0006221756339073181
0.0009765625
0.005801062099635601
11
1.52099609375
1.521484375
-0.002279443317092955
0.0006221756339073181
0.00048828125
0.0029016189510002732
12
1.521240234375
1.521484375
-0.0008289058605441824
0.0006221756339073181
0.000244140625
0.0014510814944515005
13
1.5213623046875
1.521484375
-0.0001034331235132413
0.0006221756339073181
0.0001220703125
0.0007256087574205594
14
1.5213623046875
1.52142333984375
-0.0001034331235132413
0.0002593542519662151
6.103515625e-05
0.0003627873754794564
15
1.5213623046875
1.521392822265625
-0.0001034331235132413
7.795631350404619e-05
3.0517578125e-05
0.0001813894370172875

@agarie

agarie commented Feb 19, 2014

Copy link
Copy Markdown
Member

Thanks for the patch!

I don't like this coding style... we should improve it somehow. @MohawkJohn what do you think about adopting GitHub coding styleguide?

Apart from that, it's all good. :)

@rajatkapoor

rajatkapoor commented Feb 19, 2014

Copy link
Copy Markdown
Author

Thanks @agarie
Please let me know if you want me to run the Rubocop style checker(mentioned in GitHub coding styleguide) on the code and change it accordingly.

@translunar

translunar commented Feb 19, 2014

Copy link
Copy Markdown
Member

So I'm not @clbustos, and he may say otherwise, but I'd like to see a little bit clearer variable names. If not, if the bisection method names its variables like this, then you should include a description of what the variables do.

Regardless, can you please cite the source of your code / this method? It's important for us to verify with all patches that we're honoring other people's licenses.

@rajatkapoor

rajatkapoor commented Feb 19, 2014

Copy link
Copy Markdown
Author

The Bisection method is implemented taking directives from the book Numerical Analysis by R.L. Burden, J. Faires. I have mentioned the names of the authors in the comments just after the usage examples. I will also comment the code so as to mention the importance of each of the variables soon. Please let me know if I could change anything else for the betterment of the code.
Please excuse me for all the mistakes.
Thanks.

@translunar

translunar commented Feb 19, 2014

Copy link
Copy Markdown
Member

And just to check, does the licensing on the book say anything about how
the algorithms can be used? Numerical Recipes, for example, doesn't allow
use of its code in GPL software.

On Wed, Feb 19, 2014 at 1:53 PM, Rajat Kapoor notifications@github.comwrote:

The Bisection method is implemented taking directives from the book
Numerical Analysis by R.L. Burden, J. Faires. I have mentioned the names of
the authors in the comments just after the usage examples. I will also
comment the code so as to mention the importance of each of the variables
soon. Please let me know if I could change anything else for the betterment
of the code.
Please excuse me for all the mistakes.
Thanks.

Reply to this email directly or view it on GitHubhttps://github.com//pull/1#issuecomment-35533910
.

@rajatkapoor

rajatkapoor commented Feb 19, 2014

Copy link
Copy Markdown
Author

The licensing on the book does not say anything about the algorithms, it just states a general statement:

No part of this work covered by the copyright herein maybe reproduced transmitted, 
stored or used in any form except as permitted under section 107 or 108 of the
1976 United States Copyright Act, without the prior permission of the publisher

But I really don't think that this algorithm is the intellectual property of the writer, because it is a widely used algorithm. Also the wikipedia page for the algorithm states the same book as the source. I could cite the source as the wiki article, which would not be a problem, as WIki uses Creative Commons ShareAlike license.

@translunar

translunar commented Feb 19, 2014

Copy link
Copy Markdown
Member

Yeah, I'd say mention in the comments both places, and that you assume the Wikipedia editor who added it there had permission from the author. Another option is to figure out where the author of the book got it (usually they cite these things) and look that up. Probably a peer-reviewed paper or something, which you can cite.

@rajatkapoor

rajatkapoor commented Feb 19, 2014

Copy link
Copy Markdown
Author

The book, unfortunately, does not mention any sources of the algorithm. Maybe it is because that is algorithm is very basic and is based on the concept of binary search algorithm and intermediate value theorem. I will cite the wiki page for this one.

clbustos added a commit that referenced this pull request Feb 20, 2014
@clbustos
Merge pull request #1 from rajatkapoor/bisection
c1bb552 
bisection method for minimization added
@clbustos
clbustos merged commit c1bb552 into SciRuby:master Feb 20, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

5 participants

@rajatkapoor @agarie @translunar @lasandun @clbustos