Proof of Theorem on Convergence of Successive Substitution Method

Theorem: Let a be the solution to a_i = g_i(a). Assume that given an h > 0 there exists a number

0 < µ < 1 such that

Consider the iteration scheme

Then x_i^k converges to a_i as k increases.

To prove the theorem, first subtract the exact solution from this equation.

Next write a Taylor series for the equation about the solution a, using the Mean Value Theorem to subsume all higher order terms.

This equation holds for some 0 < z_i < 1 by the Mean Value Theorem. If each term in the summation is made positive the result will be larger than if some of the terms are negative and offset the positive ones. Thus

The maximum norm is defined as (link)

Then replace the left-hand side with its biggest value; it is less than or equal to the right-hand side for the same i, and the other values on the left-hand side are all smaller. Thus

If we replace by on the right-hand side (making it even bigger) we get

We apply this for k = 0, 1, 2, ...

Combining the results gives

and if µ < 1, as assumed, the right-hand side goes to zero as k increases, proving the theorem.

The theorem also says something about the rate of convergence. The error goes to zero faster if µ is smaller rather than larger (but still less than 1.0).

Take Home Message: The successive substitution method needs µ less than one to insure convergence.