1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Convergence of iterative method and spectral radius

  1. Aug 12, 2014 #1
    1. The problem statement, all variables and given/known data
    Show that if given [itex]\mathbf{x}_0[/itex], and a matrix [itex]R[/itex] with spectral radius [itex]\rho(R)\geq 1[/itex], there exist iterations of the form,
    [tex]\mathbf{x}_{n+1}=R\mathbf{x}_0+\mathbf{c}[/tex]
    which do not converge.


    3. The attempt at a solution

    Let [itex]\mathbf{x}_0[/itex] be given, and let [itex](\lambda_0,\mathbf{v}_0)[/itex] be the eigenpair corresponding to [itex]\rho(R)[/itex]. Then choose [itex]\mathbf{c}=\mathbf{v}_0[/itex] so that,
    [tex]\mathbf{x}_n = R^n\mathbf{x}_0+\left(\sum_{i = 0}^{n - 1}\lambda_0^i\right)\mathbf{v}_0[/tex]

    I'm not sure how to proceed from here. Thanks!
     
  2. jcsd
  3. Aug 12, 2014 #2

    Zondrina

    User Avatar
    Homework Helper

    The supremum of the absolute values in the spectrum of ##R## is some ##\rho(R) \geq 1##.

    I think you need to show that ##(1 + \lambda_0 + \lambda_0^2 + \lambda_0^3 + \space...)## somehow diverges. So the iteration would diverge.
     
  4. Aug 12, 2014 #3
    Right, that sum diverges, but how do I show that [itex]\Vert \mathbf{x}_n\Vert[/itex] diverges as [itex]n\rightarrow\infty[/itex]? I can only show the norm is not greater than [itex]\Vert R^n\mathbf{x}_0\Vert + \infty [/itex] with the triangle inequality.
     
  5. Aug 12, 2014 #4

    Zondrina

    User Avatar
    Homework Helper

    Can you show that:

    ##\displaystyle \lim_{n → ∞} R^n = 0 \iff \rho(R) < 1##?

    Since ##\rho(R) ≥ 1##, it would be clear as to why ##||R^n||## is not bounded.
     
  6. Aug 13, 2014 #5

    pasmith

    User Avatar
    Homework Helper

    As it stands the statement is false, since [itex]\mathbf{x}_{n+1} = R\mathbf{x}_0 + \mathbf{c}[/itex] is a constant map. Perhaps the [itex]\mathbf{x}_0[/itex] is supposed to be an [itex]\mathbf{x}_n[/itex].

    You need only consider the case where [itex]\mathbf{x}_0 = z_0\mathbf{v}_0[/itex] and [itex]\mathbf{c} = c\mathbf{v}_0[/itex]. You are justified in making this assumption since you're asked to show that divergent iterations exist, so you only need to find one such iteration.

    Thus your problem is to show that the complex sequence [tex]
    z_{n+1} = \lambda z_n + c[/tex] diverges if [itex]|\lambda| > 1[/itex]. Fortunately this linear recurrence can be solved analytically to obtain [itex]z_n[/itex] in closed form.
     
  7. Aug 13, 2014 #6
    Yep, thank you for noticing my error, I meant to say,

    [tex]\mathbf{x}_{n+1} = R\mathbf{x}_n +\mathbf{c}[/tex]

    I'm just still unclear why I am allowed to assume [itex]\mathbf{x}_0[/itex] is a scalar multiple of the eigenvector corresponding to the spectral radius. Doesn't the question read, "If I am provided with some [itex]\mathbf{x}_0[/itex] I can choose a [itex]\mathbf{c}[/itex] that will result in a nonconvergent sequence"?
     
  8. Aug 13, 2014 #7

    pasmith

    User Avatar
    Homework Helper

    You're right, I missed that. You are stuck with the given [itex]\mathbf{x}_0[/itex].

    However, I can still achieve my goal (reducing the problem to finding a sequence of scalars [itex]z_n[/itex] with [itex]|z_n| \to \infty[/itex]) by suitable choice of [itex]\mathbf{c}[/itex]. I'm stuck with [itex]\mathbf{x}_0[/itex], so it may be that the best I can do is [itex]\mathbf{x}_n = \mathbf{x}_0 + z_n\mathbf{v}_0[/itex]. But that would suffice, since
    [tex]
    \|\mathbf{x}_n\| = \|\mathbf{x}_0 + z_n \mathbf{v}_0\|
    = |z_n|\left\| \frac{\mathbf{x}_0}{z_n} + \mathbf{v}_0\right\| \to \infty
    [/tex]
    since by definition [itex]\mathbf{v}_0 \neq 0[/itex].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Convergence of iterative method and spectral radius
  1. Iterative Methods (Replies: 6)

  2. Spectral Radius: Matrix (Replies: 22)

  3. Radius of convergence (Replies: 7)

  4. Radius of convergence (Replies: 6)

Loading...