NonlinearSolvers plugin - BDQRF, Bisection, Brent's, Broyden's, Newton-Raphson, Ridder's, Secant, Homotopy - Messages
This plugin contains some root-finding methods and optimization algorithms.
Password (Extensions Manager): NonlinearSolvers
Since the plugin may have big changes in future, I can't make a complete documentation but you can referrer to:
- Martin's handbook
- this album
;PLEASE REPORT HERE ANY ISSUE
Best regards,
Davide
requirements: .Net Framework 2.0 / AnyCPU / SMath Studio 0.95.4594 (30 July 2012)
BETA_testing sm files.zip
Many things like this one would make me very happy
Regards,
Radovan
P.S. Do not take me wrong please, I am very happy that you've made this plugin but I think that my "home made" function does not deserve to be the reference to this rather welcome and appreciated plugin. I hope that your updates would base this plugin to some more trustworthy source.
Rather surprised and excited with this sys() thing regarding Broyden()
As I do not know how is this working yet, this is a minor observation at a first glance.
It seems that the vector indices play main role here.
[MATH=eng]Broyden(sys(el(x,1)-2*el(x,2)+5,el(x,1)+3*el(x,2)-1,2,1),sys(1,2,2,1),eps,maxiter)=mat(-2.6,1.2,2,1)[/MATH]
[MATH=eng]Broyden(sys(el(a,1)-el(2*b,2)+5,el(c,1)+3*el(d,2)-1,2,1),sys(1,2,2,1),eps,maxiter)=mat(-2.6,1.2,2,1)[/MATH]
[MATH=eng]Broyden(sys(el(a,1)-el(2*b,2)+el(e,1),el(c,1)+3*el(d,2)+el(f,1),2,1),sys(1,2,2,1),eps,maxiter)=mat(0,0,2,1)[/MATH]
This might be a confusion because vectors a,b,c,d,e,f are not defined and there is still a result returned. You managed to avoid mentioning vector of unknowns like in the roots(), and I think that vector indices are crucial things here to distinguish between unknowns, not sure. Am I right? If that is the case, I thing that this should be taken care of in the case of different vectors elements with the same indices in order what to refer to as vector of unknowns.
Best wishes,
Radovan
w3b5urf3r you are my hero
Many things like this one would make me very happy
Regards,
Radovan
P.S. Do not take me wrong please, I am very happy that you've made this plugin but I think that my "home made" function does not deserve to be the reference to this rather welcome and appreciated plugin. I hope that your updates would base this plugin to some more trustworthy source.
you're right, but I did not know where to start and that function was a good starting point. :d
Currently, the plugin follows almost exactly that function, but if anyone has a more efficient version of the algorithm could certainly be implemented.
Hello w3b5urf3r
Rather surprised and excited with this sys() thing regarding Broyden()
Yes, I have lost a bit of time on this, I wanted the function to accept both individual functions or systems defined in vectors or in the "multiple values" item.
As I do not know how is this working yet, this is a minor observation at a first glance.
It seems that the vector indices play main role here.
[MATH=eng]Broyden(sys(el(x,1)-2*el(x,2)+5,el(x,1)+3*el(x,2)-1,2,1),sys(1,2,2,1),eps,maxiter)=mat(-2.6,1.2,2,1)[/MATH]
[MATH=eng]Broyden(sys(el(a,1)-el(2*b,2)+5,el(c,1)+3*el(d,2)-1,2,1),sys(1,2,2,1),eps,maxiter)=mat(-2.6,1.2,2,1)[/MATH]
[MATH=eng]Broyden(sys(el(a,1)-el(2*b,2)+el(e,1),el(c,1)+3*el(d,2)+el(f,1),2,1),sys(1,2,2,1),eps,maxiter)=mat(0,0,2,1)[/MATH]
This might be a confusion because vectors a,b,c,d,e,f are not defined and there is still a result returned. You managed to avoid mentioning vector of unknowns like in the roots(), and I think that vector indices are crucial things here to distinguish between unknowns, not sure. Am I right? If that is the case, I thing that this should be taken care of in the case of different vectors elements with the same indices in order what to refer to as vector of unknowns.
Best wishes,
Radovan
You're right, my parser check if there are undefined variables but it doesn't distinguish between them... Actually the assumption is that there is "one variable" (x,X,K,or something you want) or "a system of variables" (x[1],x[2],x[3],...), so actually a[1] and b[1] are both the same thing (the first element of the starting values vector)
I think I can easily add a control that returns an error on the number of vars...
If you want to use "multiple variables" (one varibale -> one vector element) I think we can do something, but with some limitations regarding the names (f.e. "i" and "e" are both constants).
regards,
w3b5urf3r
Whatever you do regarding this plugin will be very welcome AFAIC
I have just to mention in the case you based your plugin on my SMath function, that I made it from a simple code found somewhere on the Net (even do not remember where from). If you are interested to spare some more of your time, you could try to find yourself some better algorithm and make a plugin from it
.Regards,
Radovan
Here is a bit of testing the Broyden plugin. It is a clasical "driving crasy" situation with multiple solutions. It was mentioned by kilele in the link to the document http://en.smath.info/forum/yaf_postsm7678_solve---and-roots-----again.aspx#post7678
Your plugin failed (if I did not do something wrong) but do not worry about it - it is a common situation. The problem is why "Can not calculate" error returned. I do not know. My function returned another solution than few Newton-Raphson iterations or roots(). I also used another software that uses some kind of broyden algorithm and here is the result - the same as roots() returned
>function f(x):=[(x[1]+3)*(x[2]^3-7)+18,sin(x[2]*exp(x[1])-1)]
>x0:=[-0.5,1.4]
[ -0.5 1.4 ]
>f(x0)
[ 7.36 -0.150285529841 ]
>res:=broyden("f",x0)
[ 0 1 ]
>f(res)
[ 0 0 ]Here is the picture and the sm file
Regards,
Radovan
Broyden_testings-1.sm
or obtaining good approximations of roots with a generalized bisection method and then refine with broyden or other method, as explained at the conclusions of this document:
( see the link "pdf download" )
A Rapid Generalized Method of Bisection for Solving Systems of Non-linear Equations
Feel free to explore that strategy, as for me I'll take it easy with a first plugin for a one dimension bisection :d
I hope you would not mind if I repeat some of my comments I've already posted here on the Forum.
All of you who are trying to make any SMath plugin have all my respect and appreciation. I really hope that you will enjoy this and the SMath users will benefited from that, no doubt. On the other hand, this will very likely take quite a long time until most of the basic numerical functions and procedures SMath needs would be realized, regarding that you are starting from scratch. In order not to "inventing the will" there must be some more pragmatical way to "fill up" the SMath with some already made, free available, mature and well tested numerical code (using them like black boxes and make plugins from them). Actually, I was told that this is not likely to be possible in SMath and I regret for that very much. I think this will, unfortunately, slow down the SMath progress and restrict the SMath user community. Many of the SMath users are (actual/former) Mathcad users as well, and I think that most of them would like that SMath had some Mathcad functionality comparing to even Mathcad 6 (originated from 1996).
Regarding,
Radovan
Currently, the plugin follows almost exactly that function, but if anyone has a more efficient version of the algorithm could certainly be implemented.
I've just read that this implementation is better for large problems (see pag 133 of this pdf)
and this is its matlab code
@Radovan
As for making use of third part libraries on SMath, I don't know if that is possible aside from license issues
Currently, the plugin follows almost exactly that function, but if anyone has a more efficient version of the algorithm could certainly be implemented.
I've just read that this implementation is better for large problems (see pag 133 of this pdf)
and this is its matlab code
Thank you for this link
. I do not know if w3b5urf3r has enough time to devote to the Broyden method explained there (or any other one) 
This might be an example of how to make a plugin - as far as I understood this process. Ordinary user who understands Matlab could try to make the SMath function following this code. It might be more or less time consuming. A plugin developer could also use this Matlab code directly or the already made SMath function (do not know which one could make less trouble) and make a plugin by using some software tools. I have no idea how difficult might that be. On the other hand (have a vague idea about this) if there would be a plugin mechanism which will just include some kind of compiled Matlab (or C,C++,C#,F95) code where there should be defined input arguments output arguments and using a "black box" of this compiled function. This is working in many other software with the goal of reusing already made code. Otherwise, it would be a disaster to write everything from the beginning. I thought that the idea of "plugin" will follow this concept but as I was told this is not working in SMath this way. How is this actually working, I do not know.
@Radovan
As for making use of third part libraries on SMath, I don't know if that is possible aside from license issues
I was thinking about the freely available libraries, open source software etc. I do not see then any license problems (am I right?) except the ones I was talking about.
Regards,
Radovan
an optional argument at the end of the function arguments, different from 0, can show you the number of iterations...
Hello w3b5urf3r,
Here is a bit of testing the Broyden plugin. It is a clasical "driving crasy" situation with multiple solutions. It was mentioned by kilele in the link to the document http://en.smath.info/forum/yaf_postsm7678_solve---and-roots-----again.aspx#post7678
Your plugin failed (if I did not do something wrong) but do not worry about it - it is a common situation. The problem is why "Can not calculate" error returned. I do not know. My function returned another solution than few Newton-Raphson iterations or roots(). I also used another software that uses some kind of broyden algorithm and here is the result - the same as roots() returnedTry, for instance to change the guess values (vector x0) from [-0.5,1.4] to [1,4].>function f(x):=[(x[1]+3)*(x[2]^3-7)+18,sin(x[2]*exp(x[1])-1)] >x0:=[-0.5,1.4] [ -0.5 1.4 ] >f(x0) [ 7.36 -0.150285529841 ] >res:=broyden("f",x0) [ 0 1 ] >f(res) [ 0 0 ]
Here is the picture and the sm file
Regards,
Radovan
The function as in the *.sm file doesn't work because the first approximated inverse jacobian ( B ) is an Identity matrix... i've seen that is a common issue (f.e. root finding methods)... in SMath this could be fixed using the Jacob() function on the user input solution (see the attachment).
Unfortunately the function Jacob() (as well as other functions such as error() function) are not in the 4 standard libraries; I will try to see if importing the library on which it was made by Andrey can be implemented.
Currently, the plugin follows almost exactly that function, but if anyone has a more efficient version of the algorithm could certainly be implemented.
I've just read that this implementation is better for large problems (see pag 133 of this pdf)
and this is its matlab code
@Radovan
As for making use of third part libraries on SMath, I don't know if that is possible aside from license issues
Thank you, is very useful;
i've implemented this script in a Smath sheet and it's more readable, unfortunately the issue related to the first Jacob approximation still remains
regards,
w3b5urf3r
Just keep up this way
I would suggest you to strictly avoid using Jacob() inside Broyden - it will get new troubles. I really do not know what to use instead as a first Jacobian approximation. If someone have any idea, please help.
When you have the time, put some examples using Bisection() as well in the next update.
If I understood you well, you are trying to use Broyden with units (Dimensional analysis check failed...). Am I right? My suggestion is to skip this as well at the moment.
Best wishes,
Radovan
also i've searched information about the broyden method over time and it seems the most advanced/recent version is a modification of Johnson's by Baran :
http://arxiv.org/abs/0805.4446
As for the Jacob() function, I thought that Broyden didn't use Jacob directly but an approximation..
EDIT:
Never mind, the above paper refers to a gpl program based on other libraries.
There you have the historial of Broyden method,
http://www.unedf.org/content/PackForest2008_talks/Day2/PackForest_JJM.pdf
it seems to me that the "compact" version of 1994 corresponds to the matlab code that I linked above.
1) check for results with the "bad" Broyden method
- if solutions works -> output the results
- if solutions are not closest to zero -> 2
2) check for results with the "good" Broyden method
- if solutions works -> output the results
- if solutions are not closest to zero -> output a can not solve error
the algorithm is similar to that shown in the attachment (replace the B update definition to see the different behavior).
Added a SMath file with examples for the Bisection() function.
wow, have you used bisection as an initialization of broyden ?
also i've searched information about the broyden method over time and it seems the most advanced/recent version is a modification of Johnson's by Baran :
http://arxiv.org/abs/0805.4446
As for the Jacob() function, I thought that Broyden didn't use Jacob directly but an approximation..
EDIT:
Never mind, the above paper refers to a gpl program based on other libraries.
There you have the historial of Broyden method,
http://www.unedf.org/content/PackForest2008_talks/Day2/PackForest_JJM.pdf
it seems to me that the "compact" version of 1994 corresponds to the matlab code that I linked above.
Very interesting articles, thank you
regards,
w3b5urfer
Broyden_alpha.sm
Thanks for your work!!
Edit:
Again since Broyden is not globally convergent, bisection might be interesting as an initial approaching to the roots
I was thinking about the freely available libraries, open source software etc. I do not see then any license problems (am I right?) except the ones I was talking about.
since SMath is not a commercial software i guess we can be not too strict about licenses :d
anyway some licenses like gpl don't allow to publish opensource plugins for closed programs (unlike lgpl)
as for distributing compiled matlab scripts, I think you are right! see this link
don't know how this black boxes could be used in SMAth though, however the approach of making plugins out of matlab, fortran, pseudo-code from scientific papers.. could be more convenient due to compatibility and dll size
This is one of my working problems I was already mentioned Primer 65a and struggled in SMath with. I reported there the problems of solve() and roots() solutions.
I used it again for testing and attached it to this post. It seems the problem is a bit numerically "tricky" for solving in SMath. The original file is not working in the recent SMath version, neither solve() nor roots() (error message about T as undefined variable - not quite sure why). Here I attached the revised file - just removed eval() I was talking about in the previous post. Fortunately, solve() will now get the more accepted result
, roots() will fail, Broyden() will give the answer if the guess value is quite close to the solution, Bisection() will fail as well. I hope I did not make any serious mistake here.Regarding this problem, I am satisfied that at least one of the possible tool in SMath can give the result.
Regards,
Radovan
Primer65aa.sm
Without insight into the nature of the problem, root finding is more or less blind search, this is why I suggested a multidimensional bisection method for a initial guess with just a few iterations.
With some insight into the nature of the root, Newton’s method using derivative information, and Broyden’s method using only function information seem good candidates.
Some information about methods followed by Octave:
fsolve in Octave implements the multidimensional Newton method
fzero in Octave uses Brent’s method for one dimension (bisection+secant)
All these info is nearly copy-pasted of this doc :d
I think also that there are some interesting advice on this pdf on page 20:Final Considerations, about how to rephrase your function so that all these algorithms work better.
As a final suggestion (sorry for so many links to documents) it could be a good idea to make plugins for several methods: Brent (one dimension); Newton, Broyden and Homotopy methods (multidimension); and It could be even better combine some of these methods in a row or according to the type of function entered by the user (I assume that's how Smath Solve() works)
Hello,
This is one of my working problems I was already mentioned Primer 65a and struggled in SMath with. I reported there the problems of solve() and roots() solutions.
I used it again for testing and attached it to this post. It seems the problem is a bit numerically "tricky" for solving in SMath. The original file is not working in the recent SMath version, neither solve() nor roots() (error message about T as undefined variable - not quite sure why). Here I attached the revised file - just removed eval() I was talking about in the previous post. Fortunately, solve() will now get the more accepted result
Regarding this problem, I am satisfied that at least one of the possible tool in SMath can give the result.
Regards,
Radovan
I omorr, i'll check this issue ASAP, especially because in this case the script seems to work while the plugin don't work...
about eval(), you cannot use it where there are undefined variables because the function "force" the numeric evaluation.
best regards,
w3b5urf3r
As a final suggestion (sorry for so many links to documents) it could be a good idea to make plugins for several methods: Brent (one dimension); Newton, Broyden and Homotopy methods (multidimension); and It could be even better combine some of these methods in a row or according to the type of function entered by the user (I assume that's how Smath Solve() works)
I agree with you completely
I also agree about the mentioned observation on the 20-page of your reference. This is up to the user. A simple advice is to rearrange the function f(x)= 0 by avoiding division of terms when denominator can be close to zero. @w3b5urf3r Based on the picture in your previous post (many methods in a plugin), did I say that you are my hero?
Regards,
Radovan
-
New Posts
-
No New Posts