Successive Approximations, Method of

Successive Approximations, Method of 

a method of solving mathematical problems by means of a sequence of approximations that converges to the solution and is constructed recursively— that is, each new approximation is calculated on the basis of the preceding approximation; the choice of the initial approximation is, to some extent, arbitrary. The method is used to approximate the roots of algebraic and transcendental equations. It is also used to prove the existence of a solution and to approximate the solutions of differential, integral, and integro-differential equations. Other uses include the obtaining of a qualitative characterization of a solution.

To solve the equation

(1) f(x) = 0

we can form the equivalent equation x = Φ(x), where Φ(x) denotes, for example, the difference x — kf(x), where k is a constant. We select an initial approximation a₀ to the root of the equation and then construct the sequence of numbers a₀, a₁ = Φ(a₀), a₂ = Φ(a₁)..... a_n = Φ(a_n-1), …. If

exists, it is a root of equation (1); the numbers a₀, a₁, a₂,…, a_n,.......... are approximations to this root. The limit a exists if, for example,

and any number may be taken as the initial approximation a₀.

Usually when it is necessary to approximate the root of an equation, a sufficiently small interval is established within which the root lies; this may be done, for example, by graphical methods. A number k is then chosen so that condition (2) is satisfied over the interval. Any number in the interval can be selected as the initial approximation a₀, whereupon the method of successive approximations is applied. In actual practice, once two successive approximations a_n — 1 and a_n differ by less than a specified amount, the computation is halted, and we set a ≈ a_n.

Suppose, for example, the equation f(x) = e^x — l/x = 0 is given. Since f(l/2)f(1) < 0, a root of the equation will lie in the interval (1/2, 1). If we set Φ (x) = x — k(e^x — 1 /x), it is easy to see that condition (2) is satisfied over the entire interval (1/2, 1) when k = 1/4. Let us choose a₀ = 3/4 and apply the method of successive approximations to the equation x = x — (1/4)- (e^x - 1 /x). We obtain a₁ = 0.554, a₂= 0.570, and a₃= 0.566; in fact, the root of the equation, correct to three places, is a ≈ 0.567.

The method of successive approximations is used in the approximate solution of systems of linear algebraic equations with a large number of unknowns. Suppose we are given the system of three equations with three unknowns

a₁₁x + a₁₂y + a₁₃z = b₁

(3) a₂₁x + a₂₂y + a₂₃z = b₂

a₃₁x + a₃₂y + a₃₃z = b₃

We construct the equivalent system

x = c₁₁x + c₁₂y + c_l3z + d₁

(4) y = c_2lx + c₂₂y + c₂₃z + d₂

z = c₃₁x + c₃₂y + c₃₃z + d₃

setting, for example,

where i, k = 1, 2, 3. Using the recurrence formulas

X_j = C₁₁x_{j –1} + C_l2y_j–l + C_l3z_j–l + d₁

y_j = c₂₁x_j–1 + C₂₂y_j–1 + C₂₃z_j–l + d₂

z_j = C₃₁x_j–1 + C₂₃y_j–1 + C₂₃z_j–l + d₃

we form the sequence (x₀, y₀, Z₀),…. (x₁, y₁, z₁), … (x_n, y_n z_n)…. If x_n →α, y_n → β, and z_n → γ as n increases without bound, the three numbers x = a, y = β, and z = γ are the solution of system (3). The limits α, β, and γ clearly exist for arbitrary initial approximations x₀ y₀ and z₀ if, for example, the sum of the absolute values of the coefficients c_ij in each equation of system (4) is less than unity.

In order to find a solution y = y(x) of the differential equation dy/dx = f(x, y) under the condition y₀ = y(x₀) we write the equation in the form

Using the recurrence formula

we construct the sequence of functions y₁(x), y₂(x),…., y_n(x)…. If this sequence converges uniformly, its limit is the desired solution.

To find the solution of the first boundary value problem for the equation

an arbitrary, twice differentiable function u₀ (x, y) is selected and the linear equation

then formed. Suppose u₁ (x, y) is a solution of the first boundary value problem for equation (5). We can take u₁ as the first approximation and then construct equations of the type of equation (5) for the succeeding approximations. The resulting sequence {un (x, y)} converges under certain assumptions and yields a solution of the problem.