# 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]).

For more detailed explanation, see here.

Problem 3: Comparison of Fixed point iterations and Newton's method

Consider the nonlinear system

x1-1- x22 = 0
x2 + 2 x12 = 4

which has three solutions (after rounding to 5 decimal places, black dots):

P1=[0.06275, 3.99213],   P2=[1.24580, 0.89595],   P3=[1.54972, -0.80329],

and use four different starting points (red dots)

Q1=[0.125, 3.5],   Q2=[1.2, 1],   Q3=[0.75, 0.5],   Q4=[1, -1].

for equal axes units:

For Fpi, the rearrangement x1 = x2-2,   x2 = 4 - 2 x12   was used.

For each method and starting point, resulting point and a number of iterations are listed (with accuracy to 5 decimal places):

Method Q1 Q2 Q3 Q4
Newton's     P1 (12)     P2 (2)     P3 (5)     P3 (4)
Fixed point iter.     P1 (7)     P1 (10)     P1 (8)     P1 (10)