Nonlinear Equations Solved using the Successive Substitution Method

Consider a set of nonlinear equations in several unknowns.

Iterative methods are employed to solve these equations by choosing a guess, getting a better value, and continuing. We denote the k-th iteration as x^k. The successive substitution method is written as

{x⁰_i} = guessed

If the constant b is chosen correctly these iterations will converge to a solution, but it may be hard to find an acceptable value of b. The convergence is linear and may be slow, requiring many iterations, but the method is easy to program.

The theorem proving convergence is: 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. Proof (link)

How does one apply this theory when one doesn't know the answer? It is necessary that the inequalities be satisfied for all x near the solution, which is unknown. Sometimes, however, the derivatives can be bounded for all x, and then the theory can be applied. In particular, we expect convergence to hold for small b. From the structure of the iterations it is clear that the function itself has a smaller and smaller influence as b goes to zero. Thus one might expect that the convergence to the solution is slower for smaller b, and this is indeed true. See the figure as an example and the

proof of the theorem (link). Even if one cannot find a value of µ that satisfies the theorem, the condition does give suggestions about what is needed for convergence, and these ideas may be useful when interpreting your computer results.

Note also that the theorem gives conditions guaranteeing convergence, but says nothing about what happens when the conditions of the theory are not satisfied. In that case the iteration may converge or diverge, and the theorem is not applicable. It may converge because the conditions of the theorem are too restrictive and were only needed to prove the theorem, rather than being needed to ensure convergence. Often, however, it does not converge when the conditions of the theorem are not satisfied.

Consider the following example involving two equations.

The solution to these equations is derived with the Newton-Raphson method (link) and is x = ­1.44555, y = ­2.41216. If successive substitution is applied to the system of equations, we define the functions as follows.

If we try to apply the theorem on convergence, it is necessary that the derivatives be bounded by µ < 1.

Here the derivatives are

Thus the conditions for the theorem become

and

The first equation requires that b be negative, while the second equation requires that it be positive. Thus there is no single value of b that will cause the conditions of the theorem to be satisfied. Experimentation with a MATLAB code failed to find a successive substitution method that works for this problem. While the method didn't work for this example, the method is usefully applied in the solution of ordinary differential equations. In that case, the constant b is proportional to ∆t, and ∆t is reduced until the method converges (link).

Take Home Message: The successive substitution method may not converge for multiple equations.