Most efficient root finding algorithm for a monotonic function
$begingroup$
This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.
I have approximated a manifold with a piece-wise defined polynomial. The manifold is periodic and so I am only considering its unit cell (one period). I split the domain of the manifold, a parallelogram, into triangles. I then approximate each sheet of the manifold within each triangle with a unique quadratic polynomial. Here is the approximated manifold. I would like to find the root that satisfies the equation
begin{equation}
sum_{i}^{mathrm{sheets}} sum_{j}^{mathrm{triangles}} int p_{i,j}(x,y) , mathrm{d}C_{i,j} - A = 0
end{equation}
where $i$ is a sum over the sheets of the manifold, $j$ is a sum over the triangular tiles, $p_{i,j}$ is the second degree polynomial approximation of the manifold's $i$th sheet within the $j$th tile, and $C_{i,j}$ is the region within a level curve of the polynomial approximation of the manifold's $i$th sheet within the $j$th tile. Here is a plot of the $C_{i,j}$ for each triangle and sheet for some estimate of the root. Said another way, I would like to find an isovalue where the area within the level curves of the polynomials, regions where the polynomials are less than the isovalue, is some predetermined value $A$.
At the moment I am using the bisection method, which is very slow because at each iteration it takes a significant amount of time to interpolate the manifold and then calculate the level curves and their containing areas. I may have hundreds of triangles and tens of sheets. I also tried the regular falsi method but ran into cases where its convergence was worse than the bisection method.
I was thinking that a bracketing method would work best. I also thought that I could take advantage of the fact that the function is monotonic.
numerical-methods algorithms roots computational-mathematics
asked Jan 10 at 20:21
jerjorgjerjorg
12
$endgroup$
add a comment |
$begingroup$
This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.
I have approximated a manifold with a piece-wise defined polynomial. The manifold is periodic and so I am only considering its unit cell (one period). I split the domain of the manifold, a parallelogram, into triangles. I then approximate each sheet of the manifold within each triangle with a unique quadratic polynomial. Here is the approximated manifold. I would like to find the root that satisfies the equation
begin{equation}
sum_{i}^{mathrm{sheets}} sum_{j}^{mathrm{triangles}} int p_{i,j}(x,y) , mathrm{d}C_{i,j} - A = 0
end{equation}
where $i$ is a sum over the sheets of the manifold, $j$ is a sum over the triangular tiles, $p_{i,j}$ is the second degree polynomial approximation of the manifold's $i$th sheet within the $j$th tile, and $C_{i,j}$ is the region within a level curve of the polynomial approximation of the manifold's $i$th sheet within the $j$th tile. Here is a plot of the $C_{i,j}$ for each triangle and sheet for some estimate of the root. Said another way, I would like to find an isovalue where the area within the level curves of the polynomials, regions where the polynomials are less than the isovalue, is some predetermined value $A$.
At the moment I am using the bisection method, which is very slow because at each iteration it takes a significant amount of time to interpolate the manifold and then calculate the level curves and their containing areas. I may have hundreds of triangles and tens of sheets. I also tried the regular falsi method but ran into cases where its convergence was worse than the bisection method.
I was thinking that a bracketing method would work best. I also thought that I could take advantage of the fact that the function is monotonic.
numerical-methods algorithms roots computational-mathematics
asked Jan 10 at 20:21
jerjorgjerjorg
12
$endgroup$
1
$begingroup$
You can improve Regula Falsi to prevent stalling of one end of the bracketing interval and thus slow linear convergence. Easiest to code is the Illinois variation. If you want faster than that, you need a variant of Dekker's fzeroin with hyperbolic or inverse quadratic approximation. The latter fleshed out is Brent's method. Complicated step logic but very few function evaluations, close to quadratic convergence if the function is smooth enough.
$endgroup$
– LutzL
Jan 10 at 23:02
$begingroup$
Thanks, I'll look into Brent's method.
$endgroup$
– jerjorg
Jan 10 at 23:30
add a comment |
$begingroup$
This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.
I have approximated a manifold with a piece-wise defined polynomial. The manifold is periodic and so I am only considering its unit cell (one period). I split the domain of the manifold, a parallelogram, into triangles. I then approximate each sheet of the manifold within each triangle with a unique quadratic polynomial. Here is the approximated manifold. I would like to find the root that satisfies the equation
begin{equation}
sum_{i}^{mathrm{sheets}} sum_{j}^{mathrm{triangles}} int p_{i,j}(x,y) , mathrm{d}C_{i,j} - A = 0
end{equation}
where $i$ is a sum over the sheets of the manifold, $j$ is a sum over the triangular tiles, $p_{i,j}$ is the second degree polynomial approximation of the manifold's $i$th sheet within the $j$th tile, and $C_{i,j}$ is the region within a level curve of the polynomial approximation of the manifold's $i$th sheet within the $j$th tile. Here is a plot of the $C_{i,j}$ for each triangle and sheet for some estimate of the root. Said another way, I would like to find an isovalue where the area within the level curves of the polynomials, regions where the polynomials are less than the isovalue, is some predetermined value $A$.
At the moment I am using the bisection method, which is very slow because at each iteration it takes a significant amount of time to interpolate the manifold and then calculate the level curves and their containing areas. I may have hundreds of triangles and tens of sheets. I also tried the regular falsi method but ran into cases where its convergence was worse than the bisection method.
I was thinking that a bracketing method would work best. I also thought that I could take advantage of the fact that the function is monotonic.
numerical-methods algorithms roots computational-mathematics
asked Jan 10 at 20:21
jerjorgjerjorg
12
$endgroup$
This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.
I have approximated a manifold with a piece-wise defined polynomial. The manifold is periodic and so I am only considering its unit cell (one period). I split the domain of the manifold, a parallelogram, into triangles. I then approximate each sheet of the manifold within each triangle with a unique quadratic polynomial. Here is the approximated manifold. I would like to find the root that satisfies the equation
begin{equation}
sum_{i}^{mathrm{sheets}} sum_{j}^{mathrm{triangles}} int p_{i,j}(x,y) , mathrm{d}C_{i,j} - A = 0
end{equation}
where $i$ is a sum over the sheets of the manifold, $j$ is a sum over the triangular tiles, $p_{i,j}$ is the second degree polynomial approximation of the manifold's $i$th sheet within the $j$th tile, and $C_{i,j}$ is the region within a level curve of the polynomial approximation of the manifold's $i$th sheet within the $j$th tile. Here is a plot of the $C_{i,j}$ for each triangle and sheet for some estimate of the root. Said another way, I would like to find an isovalue where the area within the level curves of the polynomials, regions where the polynomials are less than the isovalue, is some predetermined value $A$.
At the moment I am using the bisection method, which is very slow because at each iteration it takes a significant amount of time to interpolate the manifold and then calculate the level curves and their containing areas. I may have hundreds of triangles and tens of sheets. I also tried the regular falsi method but ran into cases where its convergence was worse than the bisection method.
I was thinking that a bracketing method would work best. I also thought that I could take advantage of the fact that the function is monotonic.
numerical-methods algorithms roots computational-mathematics
numerical-methods algorithms roots computational-mathematics
asked Jan 10 at 20:21
jerjorgjerjorg
12
asked Jan 10 at 20:21
jerjorgjerjorg
12
edited Jan 10 at 21:43
jerjorg
asked Jan 10 at 20:21
jerjorgjerjorg
12
asked Jan 10 at 20:21
jerjorgjerjorg
12
asked Jan 10 at 20:21
jerjorgjerjorg
12
12
1
$begingroup$
You can improve Regula Falsi to prevent stalling of one end of the bracketing interval and thus slow linear convergence. Easiest to code is the Illinois variation. If you want faster than that, you need a variant of Dekker's fzeroin with hyperbolic or inverse quadratic approximation. The latter fleshed out is Brent's method. Complicated step logic but very few function evaluations, close to quadratic convergence if the function is smooth enough.
$endgroup$
– LutzL
Jan 10 at 23:02
$begingroup$
Thanks, I'll look into Brent's method.
$endgroup$
– jerjorg
Jan 10 at 23:30
add a comment |
1
$begingroup$
You can improve Regula Falsi to prevent stalling of one end of the bracketing interval and thus slow linear convergence. Easiest to code is the Illinois variation. If you want faster than that, you need a variant of Dekker's fzeroin with hyperbolic or inverse quadratic approximation. The latter fleshed out is Brent's method. Complicated step logic but very few function evaluations, close to quadratic convergence if the function is smooth enough.
$endgroup$
– LutzL
Jan 10 at 23:02
$begingroup$
Thanks, I'll look into Brent's method.
$endgroup$
– jerjorg
Jan 10 at 23:30
1
1
$begingroup$
You can improve Regula Falsi to prevent stalling of one end of the bracketing interval and thus slow linear convergence. Easiest to code is the Illinois variation. If you want faster than that, you need a variant of Dekker's fzeroin with hyperbolic or inverse quadratic approximation. The latter fleshed out is Brent's method. Complicated step logic but very few function evaluations, close to quadratic convergence if the function is smooth enough.
$endgroup$
– LutzL
Jan 10 at 23:02
$begingroup$
You can improve Regula Falsi to prevent stalling of one end of the bracketing interval and thus slow linear convergence. Easiest to code is the Illinois variation. If you want faster than that, you need a variant of Dekker's fzeroin with hyperbolic or inverse quadratic approximation. The latter fleshed out is Brent's method. Complicated step logic but very few function evaluations, close to quadratic convergence if the function is smooth enough.
$endgroup$
– LutzL
Jan 10 at 23:02
$begingroup$
Thanks, I'll look into Brent's method.
$endgroup$
– jerjorg
Jan 10 at 23:30
$begingroup$
Thanks, I'll look into Brent's method.
$endgroup$
– jerjorg
Jan 10 at 23:30
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069129%2fmost-efficient-root-finding-algorithm-for-a-monotonic-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3069129%2fmost-efficient-root-finding-algorithm-for-a-monotonic-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
You can improve Regula Falsi to prevent stalling of one end of the bracketing interval and thus slow linear convergence. Easiest to code is the Illinois variation. If you want faster than that, you need a variant of Dekker's fzeroin with hyperbolic or inverse quadratic approximation. The latter fleshed out is Brent's method. Complicated step logic but very few function evaluations, close to quadratic convergence if the function is smooth enough.
$endgroup$
– LutzL
Jan 10 at 23:02
$begingroup$
Thanks, I'll look into Brent's method.
$endgroup$
– jerjorg
Jan 10 at 23:30