Matrix Proof (Linear Systems)

  • #1

Homework Statement

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:

Homework Equations

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

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

The Attempt at a Solution

I [/B]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!

Answers and Replies

  • #2
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.
  • #3
Still can't seem to get 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.
  • #4
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

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:
  • #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!