Mixing
Estimating the multiplicity of a root (numerically)
$begingroup$
I'm working on a modified root finding script that uses the Newton method, but with a modification such that I estimate the order of the root to get faster convergence.
The basis of my motivation is that I read on wikipedia that if the multiplicity m of the root is known, one can use a modified algorithm, but that if the multiplicity is not known, it is possible to estimate m after carrying out one or two iterations, and then use that value to increase the rate of convergence.
Just for clarity, the Newton method I'm referring to is
$$x_{n+1}=x_n-frac{f(x_n)}{f'(x_n)}$$
Now I'm afraid that it is not entirely clear to me how one would do this. It doesn't have to be the 'best' way there is, a simple approximation is just fine.
The way I'd start is from a taylor expansion. If $f(x)$ has a root r of order m, then
$frac{f(x_n)}{f'(x_n)} approx frac{C(x_n-r)^m}{Cm(x_n-r)^{m-1}} = frac{x_n-r}{m}$
Now, from the hint on wikipedia that it is possible to approximate m after a few iterations, I'd think I would just start with $x_0$, compute $x_1$, from that compute $x_2$ (using the approximation I made above of course), and then eliminate r using one of the equations in order to express m in terms of x0, x1 and x2. However, this is proving to be a rather ugly and overcomplicated expression, and I can't imagine that this is the most efficient method of doing so. Could anyone give me a nudge in the right direction?
Edit:
I found an online reference. On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simpler (and thus less efficient) method similar to this.
numerical-methods roots
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
$endgroup$
add a comment |
$begingroup$
I'm working on a modified root finding script that uses the Newton method, but with a modification such that I estimate the order of the root to get faster convergence.
The basis of my motivation is that I read on wikipedia that if the multiplicity m of the root is known, one can use a modified algorithm, but that if the multiplicity is not known, it is possible to estimate m after carrying out one or two iterations, and then use that value to increase the rate of convergence.
Just for clarity, the Newton method I'm referring to is
$$x_{n+1}=x_n-frac{f(x_n)}{f'(x_n)}$$
Now I'm afraid that it is not entirely clear to me how one would do this. It doesn't have to be the 'best' way there is, a simple approximation is just fine.
The way I'd start is from a taylor expansion. If $f(x)$ has a root r of order m, then
$frac{f(x_n)}{f'(x_n)} approx frac{C(x_n-r)^m}{Cm(x_n-r)^{m-1}} = frac{x_n-r}{m}$
Now, from the hint on wikipedia that it is possible to approximate m after a few iterations, I'd think I would just start with $x_0$, compute $x_1$, from that compute $x_2$ (using the approximation I made above of course), and then eliminate r using one of the equations in order to express m in terms of x0, x1 and x2. However, this is proving to be a rather ugly and overcomplicated expression, and I can't imagine that this is the most efficient method of doing so. Could anyone give me a nudge in the right direction?
Edit:
I found an online reference. On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simpler (and thus less efficient) method similar to this.
numerical-methods roots
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
$endgroup$
$begingroup$
I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski?
$endgroup$
– Dennis Kraakman
Mar 7 '15 at 22:23
$begingroup$
Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial.
$endgroup$
– Mariano Suárez-Álvarez
Mar 7 '15 at 22:28
add a comment |
$begingroup$
I'm working on a modified root finding script that uses the Newton method, but with a modification such that I estimate the order of the root to get faster convergence.
The basis of my motivation is that I read on wikipedia that if the multiplicity m of the root is known, one can use a modified algorithm, but that if the multiplicity is not known, it is possible to estimate m after carrying out one or two iterations, and then use that value to increase the rate of convergence.
Just for clarity, the Newton method I'm referring to is
$$x_{n+1}=x_n-frac{f(x_n)}{f'(x_n)}$$
Now I'm afraid that it is not entirely clear to me how one would do this. It doesn't have to be the 'best' way there is, a simple approximation is just fine.
The way I'd start is from a taylor expansion. If $f(x)$ has a root r of order m, then
$frac{f(x_n)}{f'(x_n)} approx frac{C(x_n-r)^m}{Cm(x_n-r)^{m-1}} = frac{x_n-r}{m}$
Now, from the hint on wikipedia that it is possible to approximate m after a few iterations, I'd think I would just start with $x_0$, compute $x_1$, from that compute $x_2$ (using the approximation I made above of course), and then eliminate r using one of the equations in order to express m in terms of x0, x1 and x2. However, this is proving to be a rather ugly and overcomplicated expression, and I can't imagine that this is the most efficient method of doing so. Could anyone give me a nudge in the right direction?
Edit:
I found an online reference. On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simpler (and thus less efficient) method similar to this.
numerical-methods roots
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
$endgroup$
I'm working on a modified root finding script that uses the Newton method, but with a modification such that I estimate the order of the root to get faster convergence.
The basis of my motivation is that I read on wikipedia that if the multiplicity m of the root is known, one can use a modified algorithm, but that if the multiplicity is not known, it is possible to estimate m after carrying out one or two iterations, and then use that value to increase the rate of convergence.
Just for clarity, the Newton method I'm referring to is
$$x_{n+1}=x_n-frac{f(x_n)}{f'(x_n)}$$
Now I'm afraid that it is not entirely clear to me how one would do this. It doesn't have to be the 'best' way there is, a simple approximation is just fine.
The way I'd start is from a taylor expansion. If $f(x)$ has a root r of order m, then
$frac{f(x_n)}{f'(x_n)} approx frac{C(x_n-r)^m}{Cm(x_n-r)^{m-1}} = frac{x_n-r}{m}$
Now, from the hint on wikipedia that it is possible to approximate m after a few iterations, I'd think I would just start with $x_0$, compute $x_1$, from that compute $x_2$ (using the approximation I made above of course), and then eliminate r using one of the equations in order to express m in terms of x0, x1 and x2. However, this is proving to be a rather ugly and overcomplicated expression, and I can't imagine that this is the most efficient method of doing so. Could anyone give me a nudge in the right direction?
Edit:
I found an online reference. On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simpler (and thus less efficient) method similar to this.
numerical-methods roots
numerical-methods roots
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
edited Mar 4 '14 at 16:05
user3183724
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
asked Mar 4 '14 at 12:36
user3183724user3183724
2521412
2521412
$begingroup$
I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski?
$endgroup$
– Dennis Kraakman
Mar 7 '15 at 22:23
$begingroup$
Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial.
$endgroup$
– Mariano Suárez-Álvarez
Mar 7 '15 at 22:28
add a comment |
$begingroup$
I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski?
$endgroup$
– Dennis Kraakman
Mar 7 '15 at 22:23
$begingroup$
Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial.
$endgroup$
– Mariano Suárez-Álvarez
Mar 7 '15 at 22:28
$begingroup$
I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski?
$endgroup$
– Dennis Kraakman
Mar 7 '15 at 22:23
$begingroup$
I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski?
$endgroup$
– Dennis Kraakman
Mar 7 '15 at 22:23
$begingroup$
Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial.
$endgroup$
– Mariano Suárez-Álvarez
Mar 7 '15 at 22:28
$begingroup$
Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial.
$endgroup$
– Mariano Suárez-Álvarez
Mar 7 '15 at 22:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As far as I know, if $f(cdot)$ has a root at $x$, it holds $f(x)=0$. Furthermore, if you want to calculate the multiplicity you have to find the minimum $m$ s.t.:
$$
f^{(m)}=0.
$$
So, you can compute the derivatives, and if $|f^{(m)}|<varepsilon$, where $varepsilon$ represents a tolerance variable, thus $m$ is the number you are looking for.
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
$endgroup$
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
1
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
|
show 2 more comments
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%2f698858%2festimating-the-multiplicity-of-a-root-numerically%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As far as I know, if $f(cdot)$ has a root at $x$, it holds $f(x)=0$. Furthermore, if you want to calculate the multiplicity you have to find the minimum $m$ s.t.:
$$
f^{(m)}=0.
$$
So, you can compute the derivatives, and if $|f^{(m)}|<varepsilon$, where $varepsilon$ represents a tolerance variable, thus $m$ is the number you are looking for.
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
$endgroup$
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
1
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
|
show 2 more comments
$begingroup$
As far as I know, if $f(cdot)$ has a root at $x$, it holds $f(x)=0$. Furthermore, if you want to calculate the multiplicity you have to find the minimum $m$ s.t.:
$$
f^{(m)}=0.
$$
So, you can compute the derivatives, and if $|f^{(m)}|<varepsilon$, where $varepsilon$ represents a tolerance variable, thus $m$ is the number you are looking for.
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
$endgroup$
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
1
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
|
show 2 more comments
$begingroup$
As far as I know, if $f(cdot)$ has a root at $x$, it holds $f(x)=0$. Furthermore, if you want to calculate the multiplicity you have to find the minimum $m$ s.t.:
$$
f^{(m)}=0.
$$
So, you can compute the derivatives, and if $|f^{(m)}|<varepsilon$, where $varepsilon$ represents a tolerance variable, thus $m$ is the number you are looking for.
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
$endgroup$
As far as I know, if $f(cdot)$ has a root at $x$, it holds $f(x)=0$. Furthermore, if you want to calculate the multiplicity you have to find the minimum $m$ s.t.:
$$
f^{(m)}=0.
$$
So, you can compute the derivatives, and if $|f^{(m)}|<varepsilon$, where $varepsilon$ represents a tolerance variable, thus $m$ is the number you are looking for.
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
answered Mar 4 '14 at 12:44
7raiden77raiden7
1,23069
1,23069
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
1
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
|
show 2 more comments
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
1
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
That is true, but I should have been more explicit in my question. Newton's method is a technique for finding roots, so I don't know where the root is at yet. I have to estimate m in order to find the root. Or do you mean in general, take the derivative until it is equal to 0? In that case I have to think about it a bit more.
$endgroup$
– user3183724
Mar 4 '14 at 12:46
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Sorry, I wasn't explicit too. I perfectly know Newton-Rapson method, I was saying that for every $i$, you should compute $f^{(m)}(x_i)$ and see its magnitude. If it is small enough, you should argue that $m$ is the multiplicity.
$endgroup$
– 7raiden7
Mar 4 '14 at 12:48
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Hm, I see. I'm not sure I completely understand. We can write the function $f(x)$ as $(x-r)^mq(x)$, where $r$ is the root and $m$ the multiplicity, and $q(x)$ a function for which it holds that $q(r) neq 0$. Why would it hold that the mth derivative of $(x-r)^mq(x) = 0$ for every $x$?
$endgroup$
– user3183724
Mar 4 '14 at 13:11
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
$begingroup$
Because close to $r$, you can think $f$ as a polynomial. In a arbitrarily small interval of $r$, $f$ is $f(x)=sum a_ix^i$, and it holds that the $m$-th derivative must be null (close to zero in this case).
$endgroup$
– 7raiden7
Mar 4 '14 at 13:44
1
1
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
$begingroup$
Well, it's not going too well so far, but I did find an online reference: books.google.nl/… On page 349, the author gives a method of estimating m, taken from Ostrowski (1973). However, I've tried to look at the derivation and it is much too complicated for my purposes. Ideally I'd use a simplified version of this.
$endgroup$
– user3183724
Mar 4 '14 at 15:37
|
show 2 more comments
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%2f698858%2festimating-the-multiplicity-of-a-root-numerically%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
$begingroup$
I am working on the same problem as you did, so I was wondering what the status is? Did you get it to work using your method instead of the method taken from Ostrowski?
$endgroup$
– Dennis Kraakman
Mar 7 '15 at 22:23
$begingroup$
Numerically, you can suppose that all roots are simple :-) Just add a small random error to each coefficient in the polynomial.
$endgroup$
– Mariano Suárez-Álvarez
Mar 7 '15 at 22:28