System of nonlinear equations F(X) = 0

Newton's method

Problem 1: Find the solution of the nonlinear system
x2 = x13 + 1
x12 + x22 = 4

Graphical solution:
>> ezplot('x_1^2 + x_2^2 - 4')
>> hold on
>> ezplot('x_2 - x_1^3 - 1')

Numerical solution: First of all, transform the system to the form F(X) = 0,
where X = [ x1 , x2 ]T, F = [ f1(X) , f2(X) ]T :
f1(X) = x12 + x22 - 4 ,
f2(X) = x2 - x13 - 1 .

Using Matlab, define F as

>> syms x1 x2          % define symbolic variables x1, x2
>> XV = [ x1 ; x2]     % vector of the variables x1, x2
>> f1 = x1^2 + x2^2 -4 % function f1 of x1, x2
>> f2 = x2-x1^3-1      % function f2 of x1, x2
>> F = [ f1 ; f2 ]     % vector function F of x1, x2

Jacobi matrix of F:

>> J = jacobian(F, XV)    

Choose a first approximation X:

>> X = [1; 2]

Repeat following 4 commands:

>> JX = subs( J, {x1, x2}, {X(1), X(2)})  % substitute a value of X to J
>> FX = subs( F, {x1, x2}, {X(1), X(2)})  % substitute a value of X to F
>> D = - JX \ FX                          % solve linear system JX * D = - FX
>> X = X + D                              % upgrade the approximation X


Fixed point iterations

Solving the Problem 1 using fixed point iterations.

Using Matlab, define F as above:

>> syms x1 x2          % define symbolic variables x1, x2
>> X = [ x1 ; x2]      % vector of the variables x1, x2
>> f1 = x1^2 + x2^2 -4 % function f1 of x1, x2
>> f2 = x2-x1^3-1      % function f2 of x1, x2
>> F = [ f1 ; f2 ]     % vector function F of x1, x2

Fixed point iterations:

>> maxit = 20;     % number of iterations
>> X = [1; 2];     % a first approximation
>> alfa = 0.1;     % a coefficient for improving convergence - a guess
>> G = [x1; x2] - alfa*F;  % transformation of F(x) = 0 to x = G(x)

>> for k=1:maxit
>>   X = subs(G, {x1, x2}, {X(1), X(2)}); % x_{k} = G(x_{k-1})
>>     % displaying of the last 3 iterations:
>>   if (k > (maxit-3))
>>     if(k == (maxit-2))
>>       disp('the last 3 approximations of X:')
>>     end
>>     disp(X)
>>   end
>> end

>>   % test of the result by computing F(X) - should be close to zero
>> FX = subs(F, {x1, x2}, {X(1), X(2)})

Experiment with different values of maxit (number of iterations), X (the first approximation) and alfa (the coefficient influencing convergence).

Solve a similar problem with second equation changed to

x2 = sin(x1) + 1

so that

>> f2 = x2 - sin(x1) - 1 ; 

(now the better choice of the parameter alfa would be 0.25)



Problem 2: Newton's method - illustration of basins of attraction

Consider the nonlinear system
x13 - 3 x1 x22 - 1 = 0
3 x12 x2 - x23 = 0
which has three solutions:  [1,0],   1/2 [-1, 31/2]   and  1/2 [-1, -31/2].

They can be found inside the three largest areas on the picture bellow: red, green and blue, respectively. For starting point at any colored area, Newton's method converges to the solution of the corresponding color (for example if the starting point lies at any of the red areas, Newton's method will converge to the solution [1,0]).

Julia set for the rational function

For more detailed explanation, see here.