Is Gershgorin bound of roots sharp?bound the distance of two roots of multivariate polynomial systemsIs it possible to find a companion matrix of a polynomial which is also hermitian?Explicit example of Gershgorin circle theorem edge caseMinimize the rank of a matrix with some entries knownConnection between the spectra of a family of matrices and a modelization of particles' scattering?Gershgorin disk boundCondition number for polynomial interpolation matrixDisjointing the Gershgorin DisksA collection of most of the properties about a linear operator and its trace.Gershgorin circle and complex eigenvalues
Is it possible to do 50 km distance without any previous training?
I see my dog run
Is there a minimum number of transactions in a block?
Can town administrative "code" overule state laws like those forbidding trespassing?
Why is "Reports" in sentence down without "The"
I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine
LED on same Pin as Toggle Switch, not illuminating
Why do we use polarized capacitor?
How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?
Schwarzchild Radius of the Universe
Calculus Optimization - Point on graph closest to given point
I probably found a bug with the sudo apt install function
Draw simple lines in Inkscape
Mean and Variance of Continuous Random Variable
"which" command doesn't work / path of Safari?
Could a US political party gain complete control over the government by removing checks & balances?
How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)
Infinite past with a beginning?
Simulate Bitwise Cyclic Tag
What is the offset in a seaplane's hull?
Prevent a directory in /tmp from being deleted
How old can references or sources in a thesis be?
When blogging recipes, how can I support both readers who want the narrative/journey and ones who want the printer-friendly recipe?
What would happen to a modern skyscraper if it rains micro blackholes?
Is Gershgorin bound of roots sharp?
bound the distance of two roots of multivariate polynomial systemsIs it possible to find a companion matrix of a polynomial which is also hermitian?Explicit example of Gershgorin circle theorem edge caseMinimize the rank of a matrix with some entries knownConnection between the spectra of a family of matrices and a modelization of particles' scattering?Gershgorin disk boundCondition number for polynomial interpolation matrixDisjointing the Gershgorin DisksA collection of most of the properties about a linear operator and its trace.Gershgorin circle and complex eigenvalues
$begingroup$
Gershgorin circle theorem tells that the eigenvalues of a matrix $A$ lie in the union of the associated Gershgorin circles.
$A=beginpmatrix
0 & 0 & dots & 0 & -a_0 \
1 & 0 & dots & 0 & -a_1 \
0 & 1 & dots & 0 & -a_2 \
vdots & vdots & vdots & vdots & vdots \
0 & 0 & dots & 1 & -a_d-1 \
endpmatrix$
has characteristic polynomial $(-1)^d(X^d+a_d-1X^d-1+ldots+a_0)$.
Thus, the roots of $X^d+a_d-1X^d-1+ldots+a_0$ lie in $displaystylebigcup_i=1^d-2barD(0,1+|a_i|)cupbarD(-a_n-1,1)$, which of course can be rewritten as $displaystylebarD(0,1+max_1leq ileq d-2|a_i|)cupbarD(-a_n-1,1)$
Is this bound sharp ?
linear-algebra polynomials eigenvalues-eigenvectors roots
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
$endgroup$
add a comment |
$begingroup$
Gershgorin circle theorem tells that the eigenvalues of a matrix $A$ lie in the union of the associated Gershgorin circles.
$A=beginpmatrix
0 & 0 & dots & 0 & -a_0 \
1 & 0 & dots & 0 & -a_1 \
0 & 1 & dots & 0 & -a_2 \
vdots & vdots & vdots & vdots & vdots \
0 & 0 & dots & 1 & -a_d-1 \
endpmatrix$
has characteristic polynomial $(-1)^d(X^d+a_d-1X^d-1+ldots+a_0)$.
Thus, the roots of $X^d+a_d-1X^d-1+ldots+a_0$ lie in $displaystylebigcup_i=1^d-2barD(0,1+|a_i|)cupbarD(-a_n-1,1)$, which of course can be rewritten as $displaystylebarD(0,1+max_1leq ileq d-2|a_i|)cupbarD(-a_n-1,1)$
Is this bound sharp ?
linear-algebra polynomials eigenvalues-eigenvectors roots
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
$endgroup$
$begingroup$
What is a sharp bound?
$endgroup$
– Git Gud
Apr 5 '15 at 10:08
$begingroup$
I mean,when compared to other bounds, is it sharper ?
$endgroup$
– Gabriel Romon
Apr 5 '15 at 11:55
add a comment |
$begingroup$
Gershgorin circle theorem tells that the eigenvalues of a matrix $A$ lie in the union of the associated Gershgorin circles.
$A=beginpmatrix
0 & 0 & dots & 0 & -a_0 \
1 & 0 & dots & 0 & -a_1 \
0 & 1 & dots & 0 & -a_2 \
vdots & vdots & vdots & vdots & vdots \
0 & 0 & dots & 1 & -a_d-1 \
endpmatrix$
has characteristic polynomial $(-1)^d(X^d+a_d-1X^d-1+ldots+a_0)$.
Thus, the roots of $X^d+a_d-1X^d-1+ldots+a_0$ lie in $displaystylebigcup_i=1^d-2barD(0,1+|a_i|)cupbarD(-a_n-1,1)$, which of course can be rewritten as $displaystylebarD(0,1+max_1leq ileq d-2|a_i|)cupbarD(-a_n-1,1)$
Is this bound sharp ?
linear-algebra polynomials eigenvalues-eigenvectors roots
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
$endgroup$
Gershgorin circle theorem tells that the eigenvalues of a matrix $A$ lie in the union of the associated Gershgorin circles.
$A=beginpmatrix
0 & 0 & dots & 0 & -a_0 \
1 & 0 & dots & 0 & -a_1 \
0 & 1 & dots & 0 & -a_2 \
vdots & vdots & vdots & vdots & vdots \
0 & 0 & dots & 1 & -a_d-1 \
endpmatrix$
has characteristic polynomial $(-1)^d(X^d+a_d-1X^d-1+ldots+a_0)$.
Thus, the roots of $X^d+a_d-1X^d-1+ldots+a_0$ lie in $displaystylebigcup_i=1^d-2barD(0,1+|a_i|)cupbarD(-a_n-1,1)$, which of course can be rewritten as $displaystylebarD(0,1+max_1leq ileq d-2|a_i|)cupbarD(-a_n-1,1)$
Is this bound sharp ?
linear-algebra polynomials eigenvalues-eigenvectors roots
linear-algebra polynomials eigenvalues-eigenvectors roots
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
edited Apr 5 '15 at 13:44
Gabriel Romon
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
asked Apr 5 '15 at 10:01
Gabriel RomonGabriel Romon
18k53387
18k53387
$begingroup$
What is a sharp bound?
$endgroup$
– Git Gud
Apr 5 '15 at 10:08
$begingroup$
I mean,when compared to other bounds, is it sharper ?
$endgroup$
– Gabriel Romon
Apr 5 '15 at 11:55
add a comment |
$begingroup$
What is a sharp bound?
$endgroup$
– Git Gud
Apr 5 '15 at 10:08
$begingroup$
I mean,when compared to other bounds, is it sharper ?
$endgroup$
– Gabriel Romon
Apr 5 '15 at 11:55
$begingroup$
What is a sharp bound?
$endgroup$
– Git Gud
Apr 5 '15 at 10:08
$begingroup$
What is a sharp bound?
$endgroup$
– Git Gud
Apr 5 '15 at 10:08
$begingroup$
I mean,when compared to other bounds, is it sharper ?
$endgroup$
– Gabriel Romon
Apr 5 '15 at 11:55
$begingroup$
I mean,when compared to other bounds, is it sharper ?
$endgroup$
– Gabriel Romon
Apr 5 '15 at 11:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The two bounds
$$
R_1=1+max_k=0,...,n-1|a_k|text and R_2=max(1,|a_0|+|a_1|+...+|a_n-1|)
$$
are fast to compute but not very sharp. You get better results by computing the unique positive root of the convex and monotone function
$$
f(R)=R^n-|a_n-1|·R^n-1-…-|a_1|·R-|a_0|.
$$
Both $f(R_1)ge 0$ and $f(R_2)ge0$ show that the root will be smaller. A sufficient approximation is computed with a few rounds of Newtons method.
Even stricter bounds are obtained from Graeffe iterates of the original polynomial $p(x)=x^n+an-1x^n-1+…+a_0$, which are
$$
p_(1)(x^2)=p(x)·p(-x),quad p_(k+1)(x^2)=p_(k)(x)·p_(-k)(x).
$$
For a numerical application of these principles see for instance J.-C. YAKOUBSOHN: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
$endgroup$
add a comment |
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%2f1220870%2fis-gershgorin-bound-of-roots-sharp%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$
The two bounds
$$
R_1=1+max_k=0,...,n-1|a_k|text and R_2=max(1,|a_0|+|a_1|+...+|a_n-1|)
$$
are fast to compute but not very sharp. You get better results by computing the unique positive root of the convex and monotone function
$$
f(R)=R^n-|a_n-1|·R^n-1-…-|a_1|·R-|a_0|.
$$
Both $f(R_1)ge 0$ and $f(R_2)ge0$ show that the root will be smaller. A sufficient approximation is computed with a few rounds of Newtons method.
Even stricter bounds are obtained from Graeffe iterates of the original polynomial $p(x)=x^n+an-1x^n-1+…+a_0$, which are
$$
p_(1)(x^2)=p(x)·p(-x),quad p_(k+1)(x^2)=p_(k)(x)·p_(-k)(x).
$$
For a numerical application of these principles see for instance J.-C. YAKOUBSOHN: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
$endgroup$
add a comment |
$begingroup$
The two bounds
$$
R_1=1+max_k=0,...,n-1|a_k|text and R_2=max(1,|a_0|+|a_1|+...+|a_n-1|)
$$
are fast to compute but not very sharp. You get better results by computing the unique positive root of the convex and monotone function
$$
f(R)=R^n-|a_n-1|·R^n-1-…-|a_1|·R-|a_0|.
$$
Both $f(R_1)ge 0$ and $f(R_2)ge0$ show that the root will be smaller. A sufficient approximation is computed with a few rounds of Newtons method.
Even stricter bounds are obtained from Graeffe iterates of the original polynomial $p(x)=x^n+an-1x^n-1+…+a_0$, which are
$$
p_(1)(x^2)=p(x)·p(-x),quad p_(k+1)(x^2)=p_(k)(x)·p_(-k)(x).
$$
For a numerical application of these principles see for instance J.-C. YAKOUBSOHN: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
$endgroup$
add a comment |
$begingroup$
The two bounds
$$
R_1=1+max_k=0,...,n-1|a_k|text and R_2=max(1,|a_0|+|a_1|+...+|a_n-1|)
$$
are fast to compute but not very sharp. You get better results by computing the unique positive root of the convex and monotone function
$$
f(R)=R^n-|a_n-1|·R^n-1-…-|a_1|·R-|a_0|.
$$
Both $f(R_1)ge 0$ and $f(R_2)ge0$ show that the root will be smaller. A sufficient approximation is computed with a few rounds of Newtons method.
Even stricter bounds are obtained from Graeffe iterates of the original polynomial $p(x)=x^n+an-1x^n-1+…+a_0$, which are
$$
p_(1)(x^2)=p(x)·p(-x),quad p_(k+1)(x^2)=p_(k)(x)·p_(-k)(x).
$$
For a numerical application of these principles see for instance J.-C. YAKOUBSOHN: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
$endgroup$
The two bounds
$$
R_1=1+max_k=0,...,n-1|a_k|text and R_2=max(1,|a_0|+|a_1|+...+|a_n-1|)
$$
are fast to compute but not very sharp. You get better results by computing the unique positive root of the convex and monotone function
$$
f(R)=R^n-|a_n-1|·R^n-1-…-|a_1|·R-|a_0|.
$$
Both $f(R_1)ge 0$ and $f(R_2)ge0$ show that the root will be smaller. A sufficient approximation is computed with a few rounds of Newtons method.
Even stricter bounds are obtained from Graeffe iterates of the original polynomial $p(x)=x^n+an-1x^n-1+…+a_0$, which are
$$
p_(1)(x^2)=p(x)·p(-x),quad p_(k+1)(x^2)=p_(k)(x)·p_(-k)(x).
$$
For a numerical application of these principles see for instance J.-C. YAKOUBSOHN: Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
edited Mar 29 at 21:28
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
answered Apr 5 '15 at 13:50
LutzLLutzL
60.3k42057
60.3k42057
add a comment |
add a comment |
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%2f1220870%2fis-gershgorin-bound-of-roots-sharp%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$
What is a sharp bound?
$endgroup$
– Git Gud
Apr 5 '15 at 10:08
$begingroup$
I mean,when compared to other bounds, is it sharper ?
$endgroup$
– Gabriel Romon
Apr 5 '15 at 11:55