10.6 Iterative Improvement

---

 

	Java Number Cruncher: The Java Programmer's Guide to Numerical Computing By Ronald  Mak
	Table of Contents
	Chapter  10.   Solving Systems of Linear Equations

---

10.6 Iterative Improvement

In Chapter 5, we examined root-finding algorithms, such as Newton's algorithm, that converge toward a correct solution. Each iteration step generated an approximate solution, which was then used in the next iteration to generate a better approximation . We stopped when we deemed an approximation to be "close enough." We can do something similar when we use matrices to solve systems of equations.

Let's say we use the matrix operations described in the previous section to solve a system of equations Ax = b, and we compute our first solution x ₁ . Most likely, this solution isn't exact because of roundoff errors, and so we can compute the residual vector

We use r ₁ to solve the system

for z ₁ .

The values of z ₁ represent the discrepancies in the corresponding values of x ₁ that caused the residual values in r ₁ . In other words, if we compute x ₂ = x ₁ + z ₁ , then x ₂ is the correct solution to the original equation Ax = b. That's assuming z ₁ was computed correctly, but, of course, it probably wasn't, either.

So we iterate again:

We solve

for z ₂ , and then x ₃ = x ₂ + z ₂ .

We continue iterating, and if all goes well, the x _i will converge toward the correct solution. We stop when we decide we're "close enough."

---

Top