Convergence of Newton's method
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
For a polynomial $P$ of degree $n$ with real coefficients and with $n$ distinct real roots, the Newton's method $z_n+1 = z_n + P(z_n) over P'(z_n)$ converges for almost all initial values $z_0$ in $bf C$ to a root of $P$. This is a result due to M. Lyubich (~ 1984).
I think I remember that for a polynomial with complex coefficients, almost all initial values $z_0$ has an orbit that converges to a periodic orbit in $bf C cup infty$, but there are examples where that orbit is not a root of $P$.
Unfortunately, I can't remember who is the author of that result and I would like to find a reference.
reference-request complex-dynamics
add a comment |Â
up vote
3
down vote
favorite
For a polynomial $P$ of degree $n$ with real coefficients and with $n$ distinct real roots, the Newton's method $z_n+1 = z_n + P(z_n) over P'(z_n)$ converges for almost all initial values $z_0$ in $bf C$ to a root of $P$. This is a result due to M. Lyubich (~ 1984).
I think I remember that for a polynomial with complex coefficients, almost all initial values $z_0$ has an orbit that converges to a periodic orbit in $bf C cup infty$, but there are examples where that orbit is not a root of $P$.
Unfortunately, I can't remember who is the author of that result and I would like to find a reference.
reference-request complex-dynamics
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
For a polynomial $P$ of degree $n$ with real coefficients and with $n$ distinct real roots, the Newton's method $z_n+1 = z_n + P(z_n) over P'(z_n)$ converges for almost all initial values $z_0$ in $bf C$ to a root of $P$. This is a result due to M. Lyubich (~ 1984).
I think I remember that for a polynomial with complex coefficients, almost all initial values $z_0$ has an orbit that converges to a periodic orbit in $bf C cup infty$, but there are examples where that orbit is not a root of $P$.
Unfortunately, I can't remember who is the author of that result and I would like to find a reference.
reference-request complex-dynamics
For a polynomial $P$ of degree $n$ with real coefficients and with $n$ distinct real roots, the Newton's method $z_n+1 = z_n + P(z_n) over P'(z_n)$ converges for almost all initial values $z_0$ in $bf C$ to a root of $P$. This is a result due to M. Lyubich (~ 1984).
I think I remember that for a polynomial with complex coefficients, almost all initial values $z_0$ has an orbit that converges to a periodic orbit in $bf C cup infty$, but there are examples where that orbit is not a root of $P$.
Unfortunately, I can't remember who is the author of that result and I would like to find a reference.
reference-request complex-dynamics
reference-request complex-dynamics
edited 1 hour ago
asked 2 hours ago
coudy
11.5k14591
11.5k14591
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
I don't think your initial assertion is accurate. Consider, for example, $f(z)=z^5-z-1$. If you iterate the Newton's method function $N(z) = z-f(z)/f'(z)$ from $z_0=0$, you'll quickly find an attractive orbit of period 3. The basin of attraction of that orbit is a positive measure set with no point converging to a root of $f$. The standard Newton method picture looks like so:
Those black regions are exactly where your assertion fails. Notice, also, the five regions converging to five simple roots.
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
add a comment |Â
up vote
2
down vote
For Newton's method (and more general iterative methods) for finding roots of complex polynomials, you may want to look at Curt McMullen's paper:
Families of Rational Maps and Iterative Root-Finding Algorithms,
Curt McMullen,
Annals of Mathematics,
Second Series, Vol. 125, No. 3 (May, 1987), pp. 467-493
From the abstract: "In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms. We answer a question of Smale's by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more. We settle the case of degree 3 by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms."
add a comment |Â
up vote
1
down vote
Your statement that iterates of the Newton method converge to a cycle almost everywhere is equivalent to the statement that for every polynomial $f$
the Julia set of the rational function $z-f(z)/f'(z)$ has zero area.
This is unlikely to be true, but I do not know a published counterexample.
For the state of the art on Newton Method for polynomials, I recommend these papers:
MR1859017
J. Hubbard, D. Schleicher, S. Sutherland,
How to find all roots of complex polynomials by Newton's method.
Invent. Math. 146 (2001), no. 1, 1âÂÂ33.
MR3659421 D. Schleicher, R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoret. Comput. Sci. 681 (2017), 146âÂÂ166.
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
I don't think your initial assertion is accurate. Consider, for example, $f(z)=z^5-z-1$. If you iterate the Newton's method function $N(z) = z-f(z)/f'(z)$ from $z_0=0$, you'll quickly find an attractive orbit of period 3. The basin of attraction of that orbit is a positive measure set with no point converging to a root of $f$. The standard Newton method picture looks like so:
Those black regions are exactly where your assertion fails. Notice, also, the five regions converging to five simple roots.
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
add a comment |Â
up vote
2
down vote
I don't think your initial assertion is accurate. Consider, for example, $f(z)=z^5-z-1$. If you iterate the Newton's method function $N(z) = z-f(z)/f'(z)$ from $z_0=0$, you'll quickly find an attractive orbit of period 3. The basin of attraction of that orbit is a positive measure set with no point converging to a root of $f$. The standard Newton method picture looks like so:
Those black regions are exactly where your assertion fails. Notice, also, the five regions converging to five simple roots.
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
I don't think your initial assertion is accurate. Consider, for example, $f(z)=z^5-z-1$. If you iterate the Newton's method function $N(z) = z-f(z)/f'(z)$ from $z_0=0$, you'll quickly find an attractive orbit of period 3. The basin of attraction of that orbit is a positive measure set with no point converging to a root of $f$. The standard Newton method picture looks like so:
Those black regions are exactly where your assertion fails. Notice, also, the five regions converging to five simple roots.
I don't think your initial assertion is accurate. Consider, for example, $f(z)=z^5-z-1$. If you iterate the Newton's method function $N(z) = z-f(z)/f'(z)$ from $z_0=0$, you'll quickly find an attractive orbit of period 3. The basin of attraction of that orbit is a positive measure set with no point converging to a root of $f$. The standard Newton method picture looks like so:
Those black regions are exactly where your assertion fails. Notice, also, the five regions converging to five simple roots.
answered 1 hour ago
Mark McClure
1,438613
1,438613
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
add a comment |Â
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
Indeed, I forgot to add that the roots of $P$ must all be real in Lyubich's result. Corrected, thanks.
â coudy
1 hour ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
This answer does not address the question.
â Alexandre Eremenko
36 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@AlexandreEremenko this post most certainly addresses the question as originally stated.
â Mark McClure
8 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
@Mark McClure: How? He asks about convergence TO A CYCLE. (Not convergence to a root). In your example trajectories originating on a dense open set converge to cycles of length 1 or 3. So what?
â Alexandre Eremenko
5 mins ago
add a comment |Â
up vote
2
down vote
For Newton's method (and more general iterative methods) for finding roots of complex polynomials, you may want to look at Curt McMullen's paper:
Families of Rational Maps and Iterative Root-Finding Algorithms,
Curt McMullen,
Annals of Mathematics,
Second Series, Vol. 125, No. 3 (May, 1987), pp. 467-493
From the abstract: "In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms. We answer a question of Smale's by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more. We settle the case of degree 3 by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms."
add a comment |Â
up vote
2
down vote
For Newton's method (and more general iterative methods) for finding roots of complex polynomials, you may want to look at Curt McMullen's paper:
Families of Rational Maps and Iterative Root-Finding Algorithms,
Curt McMullen,
Annals of Mathematics,
Second Series, Vol. 125, No. 3 (May, 1987), pp. 467-493
From the abstract: "In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms. We answer a question of Smale's by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more. We settle the case of degree 3 by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms."
add a comment |Â
up vote
2
down vote
up vote
2
down vote
For Newton's method (and more general iterative methods) for finding roots of complex polynomials, you may want to look at Curt McMullen's paper:
Families of Rational Maps and Iterative Root-Finding Algorithms,
Curt McMullen,
Annals of Mathematics,
Second Series, Vol. 125, No. 3 (May, 1987), pp. 467-493
From the abstract: "In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms. We answer a question of Smale's by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more. We settle the case of degree 3 by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms."
For Newton's method (and more general iterative methods) for finding roots of complex polynomials, you may want to look at Curt McMullen's paper:
Families of Rational Maps and Iterative Root-Finding Algorithms,
Curt McMullen,
Annals of Mathematics,
Second Series, Vol. 125, No. 3 (May, 1987), pp. 467-493
From the abstract: "In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms. We answer a question of Smale's by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more. We settle the case of degree 3 by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms."
answered 1 hour ago
Joe Silverman
29.8k178156
29.8k178156
add a comment |Â
add a comment |Â
up vote
1
down vote
Your statement that iterates of the Newton method converge to a cycle almost everywhere is equivalent to the statement that for every polynomial $f$
the Julia set of the rational function $z-f(z)/f'(z)$ has zero area.
This is unlikely to be true, but I do not know a published counterexample.
For the state of the art on Newton Method for polynomials, I recommend these papers:
MR1859017
J. Hubbard, D. Schleicher, S. Sutherland,
How to find all roots of complex polynomials by Newton's method.
Invent. Math. 146 (2001), no. 1, 1âÂÂ33.
MR3659421 D. Schleicher, R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoret. Comput. Sci. 681 (2017), 146âÂÂ166.
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
add a comment |Â
up vote
1
down vote
Your statement that iterates of the Newton method converge to a cycle almost everywhere is equivalent to the statement that for every polynomial $f$
the Julia set of the rational function $z-f(z)/f'(z)$ has zero area.
This is unlikely to be true, but I do not know a published counterexample.
For the state of the art on Newton Method for polynomials, I recommend these papers:
MR1859017
J. Hubbard, D. Schleicher, S. Sutherland,
How to find all roots of complex polynomials by Newton's method.
Invent. Math. 146 (2001), no. 1, 1âÂÂ33.
MR3659421 D. Schleicher, R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoret. Comput. Sci. 681 (2017), 146âÂÂ166.
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Your statement that iterates of the Newton method converge to a cycle almost everywhere is equivalent to the statement that for every polynomial $f$
the Julia set of the rational function $z-f(z)/f'(z)$ has zero area.
This is unlikely to be true, but I do not know a published counterexample.
For the state of the art on Newton Method for polynomials, I recommend these papers:
MR1859017
J. Hubbard, D. Schleicher, S. Sutherland,
How to find all roots of complex polynomials by Newton's method.
Invent. Math. 146 (2001), no. 1, 1âÂÂ33.
MR3659421 D. Schleicher, R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoret. Comput. Sci. 681 (2017), 146âÂÂ166.
Your statement that iterates of the Newton method converge to a cycle almost everywhere is equivalent to the statement that for every polynomial $f$
the Julia set of the rational function $z-f(z)/f'(z)$ has zero area.
This is unlikely to be true, but I do not know a published counterexample.
For the state of the art on Newton Method for polynomials, I recommend these papers:
MR1859017
J. Hubbard, D. Schleicher, S. Sutherland,
How to find all roots of complex polynomials by Newton's method.
Invent. Math. 146 (2001), no. 1, 1âÂÂ33.
MR3659421 D. Schleicher, R. Stoll, Newton's method in practice: Finding all roots of polynomials of degree one million efficiently. Theoret. Comput. Sci. 681 (2017), 146âÂÂ166.
answered 20 mins ago
Alexandre Eremenko
47.6k6130245
47.6k6130245
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
add a comment |Â
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
I'm tempted to say that this doesn't address the question, but .. +1 instead. :) Isn't it true, though, that the Julia set of a rational function either has zero area or is the whole Riemann sphere?
â Mark McClure
9 mins ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
@Mark McClure: No, this is not true in general. Function $z^2+c$ can have the Julia set of positive measure, according to a result of Buff and Cheritat. However this function is not a Newton method of a polynomial.
â Alexandre Eremenko
1 min ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f313781%2fconvergence-of-newtons-method%23new-answer', 'question_page');
);
Post as a guest
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
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
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