Proving Equivalence of Iterative Refinement Equations for Linear Systems

[beth92]

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 x₀. 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 Bx₀ = 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) x_k+1 = x_k + B^-1(b - Ax_k)

(2) x_k+1 - x = (I - B^-1A)^k(x₀ - 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 x₀. Also, that x can be written as A^-1b but not sure if either of these help me.
Any tips appreciated!

 

[RUber]

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.

 

[beth92]

Still can't seem to get anywhere...in the above equations wouldn't it be x₁ - x = nx₀ - m ? I feel it would be more useful to express the difference between x₀ and x as m = (x₀ - x) as you can then just look for equation (2) as x_k+1 - x = m * n^k.
Either way, in order to iterate the algorithm for k+1 i need to substitute in x_k, not x_k - 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 x₀ + ... 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

x₁ - x = (x₀ - x) + (I - B^-1A) x₀

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

x₁ - x = (x₀ - x) * (I - B^-1 A)⁰ = x₀ - 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 x₀( 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

x₁ - x = (x₀ - x) + (I - B^-1A) x₀ = (x₀ - x) * (I - B^-1 A)

Sorry for the long reply but I feel I have tried everything! Thanks for your help.

 

[O_o]

I think you just need to use the fact that Ax = b
From what you wrote: x_{k+1} = x_k + B^{-1}\left(b - Ax_k\right) subsituting Ax = b we get 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)

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.

 

[beth92]

Just finished writing out the whole problem - thanks so much. I think the main issue was the temptation to substitute the B^-1b with x₀ 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!