Fixed Point Iteration and Newton's Method in 2D and 3D

Fixed Point Iteration and Newton's Method in 2D and 3D

Background

Iterative techniques will now be introduced that extend the fixed point and Newton methods for finding a root of an equation.We desire to have a method for finding a solution for the system of nonlinear equations


(1)
.

Each equation in (1) implicitly defines a curve in the plane and we want to find their points of intersection.Our first method will be be fixed point iteration and the second one will be Newton's method.

Definition (Jacobian Matrix).Assume that are functions of the independent variables , then their Jacobian matrix is

.

Similarly, if are functions of the independent variables, then their Jacobian matrix is

.

Generalized Differential

For a function of several variables, the differential is used to show how changes of the independent variables affect the change in the dependent variables. Suppose that we have







Suppose that the values of these functions in are known at the point and we wish to predict their value at a nearby point .Let,denote differential changes in the dependent variables and , anddenote differential changes in the independent variables. These changes obey the relationships

,

,

.

If vector notation is used, then this can be compactly written by using the Jacobian matrix. The function changes aredFand the changes in the variables are denoteddX.


or
.

Convergence near a Fixed Point

In solving for solutions of a system of equations, iteration is used.We now turn to the study of sufficient conditions which will guarantee convergence.

Definition (Fixed Point).A fixed point for the system of two equations

,
.

is a point such that .Similarly, in three dimensions a fixed point for the system of three equations

,
,
.

is a point such that .

Definition (Fixed Point Iteration).For a system of two equations, fixed point iteration is

,and
,


Similarly, for a system of three equations, fixed point iteration is


,and
,

Theorem (Fixed-Point Iteration).Assume that all the functions and their first partial derivatives are continuous on a region that contains the fixed point or , respectively.If the starting point is chosen sufficiently close to the fixed point, then one of the following cases apply.

Case (i)Two dimensions.If is sufficiently close to and if

,

,

then fixed point iteration will converge to the fixed point .


Case (ii)Three dimensions.If is sufficiently close to and if

+ + < 1,

+ + < 1,

+ + < 1,

then fixed point iteration will converge to the fixed point .

If these conditions are not met, the iteration might diverge, which is usually the case.

ProofNonlinear SystemsNonlinear Systems

Algorithm (Fixed Point Iteration for Non-Linear Systems) In two dimensions, solve the non-linear fixed point system

given one initial approximation , and generating a sequence which converges to the solution,i.e.

Algorithm (Fixed Point Iteration for Non-Linear Systems)In three dimensions, solve the non-linear fixed point system

given one initial approximation , and generating a sequence which converges to the solution,i.e.

Algorithm (Fixed Point Iteration for Non-Linear Systems)Solve the non-linear fixed point system

,

given one initial approximation , and generating a sequence which converges to the solution,

.

Remark. First we give a subroutine for performing fixed point iteration.

Computer ProgramsNonlinear SystemsNonlinear Systems

Mathematica Subroutine (Fixed Point Iteration in n-Dimensions).

Example 1.Use fixed point iteration to find a solution to the nonlinear system

Solution 1.

Newton's Method for Nonlinear Systems

We now outline the derivation of Newton�s method in two dimensions.Newton�s method can easily be extended to higher dimensions.Consider the system


(1)


which can be considered a transformation from thexy-plane to the uv-plane.We are interested in the behavior of this transformation near the point whose image is the point .If the two functions have continuous partial derivatives, then the differential can be used to write a system of linear approximations that is valid near the point :



then substitute the changes for,respectively.Then we will have

or
(2)
.

Consider the system (1) with u and v set equal to zero,


(3)


Suppose we are trying to find the solution and we start iteration at the nearby point , then we can apply (2) and write

.

Since , this becomes

,
or

.

When we solve this latter equation forwe get and the next approximation is

Theorem (Newton-Raphson Method for 2-dimensional Systems).To solve the non-linear system

,

given one initial approximation , and generating a sequence which converges to the solution ,i.e.

.

Suppose that has been obtained, use the following steps to obtain .

Step 1.Evaluate the function.

Step 2.Evaluate the Jacobian.

Step 3.Solve the linear systemfor.

Step 4.Compute the next approximation.