1. Not finding help here? Sign up for a free 30min 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!

Matrix Proof (Linear Systems)

  1. Jan 28, 2015 #1
    1. The problem statement, all variables and given/known data
    The question relates to iterative refinement. The idea is that the computer generates a solution to the linear system Ax=b which is inexact (due to roundoff errors), denoted by x0. You then iterate the algorithm given in (1) until it converges to (something much closer to) the exact solution, denoted x.
    So k denotes iteration number. B is the matrix such that Bx0 = b, which is close to the value of A such that (B-1A ≈ I) where I is the identity matrix.
    I'm stuck on trying to show that the first equation is equivalent to the second:

    2. Relevant equations

    (1) xk+1 = xk + B-1(b - Axk)

    (2) xk+1 - x = (I - B-1A)k(x0 - x)


    3. The attempt at a solution

    I
    have been working on this for a while but just can't figure out how to get to (2) or even get from (2) to (1). I can't find a way to get the exponent of k into the equation, the only manipulations I can think of is that the B-1b term can be substituted with x0. Also, that x can be written as A-1b but not sure if either of these help me.
    Any tips appreciated!
     
  2. jcsd
  3. Jan 29, 2015 #2

    RUber

    User Avatar
    Homework Helper

    What if you were to think of this from the initial point x0 which is a small number m away from the solution,
    ##x_0 = x-m ##
    Then there is another small value n, such that ##| I - B^{-1}A | = n##.
    So: ##x_1 = x_0 + B^{-1}(b-Ax_0) = x_0 + x_0 - B^{-1}A x_0##
    Means, ## x_1 - x = [x_0 -x]+ [I - B^{-1}A ]x_0= m - n x_0 ##.
    Iterate on this a few times, and you might see the pattern.
     
  4. Jan 30, 2015 #3
    Still can't seem to get anywhere...in the above equations wouldn't it be x1 - x = nx0 - m ? I feel it would be more useful to express the difference between x0 and x as m = (x0 - x) as you can then just look for equation (2) as xk+1 - x = m * nk.
    Either way, in order to iterate the algorithm for k+1 i need to substitute in xk, not xk - x so I end up having to get rid of the m anyway.
    Maybe I am overcomplicating it but iterating it just seems to give me a long list of terms beginning with x0 + ... or m + ...

    Also, one of my classmates brought up that she thinks the exponent in equation 2 should be k+1 rather than k (although I can't get either!)

    I can't manage to make (1) equal to (2) even when I choose k=0 and write down both expressions. As you say above, using equation (1) I will get

    x1 - x = (x0 - x) + (I - B-1A) x0

    Then, using equation 2 for k=0 I will get:

    x1 - x = (x0 - x) * (I - B-1 A)0 = x0 - x

    If equation (1) and (2) are equivalent then the above two expressions should be equal but as far as I can see they are not, unless x0( I - B-1A) is zero. Even if my classmate is correct and the exponent should be k+1, I can't see any way to show that

    x1 - x = (x0 - x) + (I - B-1A) x0 = (x0 - x) * (I - B-1 A)

    Sorry for the long reply but I feel I have tried everything! Thanks for your help.
     
  5. Jan 30, 2015 #4

    O_o

    User Avatar

    I think you just need to use the fact that [tex]Ax = b[/tex]
    From what you wrote: [tex] x_{k+1} = x_k + B^{-1}\left(b - Ax_k\right) [/tex] subsituting Ax = b we get [tex]x_{k+1} = x_k + B^{-1}\left(Ax - Ax_k\right) \\ x_{k+1} = x_k + B^{-1}A\left(x - x_k\right) \\ x_{k+1} - x = x_k - x+ B^{-1}A\left(x - x_k\right) \\ x_{k+1} - x = x_k - x - B^{-1}A\left(x_k - x\right) \\ x_{k+1} - x = (I - B^{-1}A)\left(x_k - x\right)[/tex]

    Now try to solve for x1-x starting with k = 0. Then plug that result into the equation for k = 1 and you should see a pattern emerge fairly easily. I don't know how rigorous your class is but the second equation you stated can be proved by induction after you notice the pattern

    edit:
    I didn't notice the exponent was k. You should ask your prof if the exponent should be k+1. I don't see how it can be k. I've had professors make typos on assignments before and if I show them why I think it's a typo they've always responded well. What I wrote above does work if equation (2) is modified so the exponent is k+1.
     
    Last edited: Jan 30, 2015
  6. Jan 30, 2015 #5
    Just finished writing out the whole problem - thanks so much. I think the main issue was the temptation to substitute the B-1b with x0 but as soon as I just put in Ax everything came together. And yeah I agree it should definitely be k not k + 1 so I'll just add a note there.

    Thanks again!
     
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: Matrix Proof (Linear Systems)
  1. Matrix Linear Systems (Replies: 3)

Loading...