Linear Algebra and Its Applications · Problem 7.4.6

Linear Programming and Game Theory — Gilbert Strang

Mathematics · iterative-refinement

Problem

The true solution to Ax=bAx = b is slightly different from the elimination solution to LUx0=bLUx_0 = b; A−LUA - LU misses zero because of roundoff. One strategy is to do everything in double precision, but a better and faster way is iterative refinement: Compute only one vector r=b−Ax0r = b - Ax_0 in double precision, solve LUy=rLUy = r, and add the correction yy to x0x_0. Problem: Multiply x1=x0+yx_1 = x_0 + y by LULU, write the result as a splitting Sx1=Tx0+bSx_1 = Tx_0 + b, and explain why TT is extremely small. This single step brings us almost exactly to xx.

Browse the problem library