# Solving a system of nonlinear equations

Tags:
1. Feb 21, 2017

### dumbperson

This is actually not a homework problem, but a problem I'm encountering while working on a little project and I'm not sure if it's even solvable or if it makes sense what I'm doing

1. The problem statement, all variables and given/known data

First, I have the equation
$$p_{ij} = \frac{1}{2}\left( \tanh{(-\frac{\theta_i + \theta_j}{2} + 2Kp_{ij} )} + 1 \right)$$
where $1 \leq i,j \leq N$. $N$ and $K$ are known quantities and $\theta_i, \theta_j$ are unknown.

2. Relevant equations
The $N$ equations are $$C_i = \sum_{j\neq i}p_{ij}^* = \frac{N-1}{2} + \frac{1}{2}\sum_{j\neq i} \tanh{\left( - \frac{\theta_i + \theta_j}{2} + 2Kp_{ij}^* \right)}$$
where $C_i$ is a known quantity and $p_{ij}^*$ is the solution to the equation in the problem statement.
I want to solve for $\theta_i, \theta_j$.

3. The attempt at a solution
I don't necessarily need to solve this exactly, it can be done numerically.
I first tried to solve this problem by expanding the tanh to first order, which simply gives me a system of $N$ linear equations.

I feel as if this system of equations is only solvable if instead of the $2Kp_{ij}^*$ in the argument of the tanh, I had $2K\sum_{j\neq i}p_{ij}$. This way, I would have the value of $\sum_{j\neq i}p_{ij}^* = C_i (\textrm{given})$ for every $i$, I could plug this value into the tanh, and then solve for $\theta_i$.

Is this problem solvable? Or do I not have enough information. To me it seems that I have $N$ unknown quantities ($\theta_i$) and $N$ equations, which should be doable. or am I missing something?

2. Feb 21, 2017

### Ray Vickson

Newton-Raphson ought to be able to do it, but getting a good starting point might be difficult. One possible way would be to start with an "easy"version, then gradually move to the exact version in a series of steps, using the solution of the previous step as a (hopefully) good starting point for the next step.

For example, you could start with the approximate problem in which $C_i = \bar{C}$ for all $i = 1,2, \ldots, N$, with $\bar{C}$ equal to the average of the true $C_i$ values. Then all $p_{ij}$ are equal to a common value $p$, and all $\theta_i$ equal some common value $\theta$ in the solution of the approximate problem. The solution is $p = \bar{C}/(N-1)$ and $\theta$ solves $2p = 1 + \tanh(2Kp -\theta)$, so is easy to obtain. Then, you can work towards the numerical solution of the true problem by solving a sequence of problems with $C_i = C_i(t) = (1-t)\bar{C} + t C_i(\text{true})$ for a sequence of $t$-values going from 0 to 1. The solution of the current $t$-problem can be used as the starting point of the next-$t$ problem. It might not work to go all the way from $t=0$ to $t=1$ in one step, but going in several smaller steps ought to work.

Last edited: Feb 21, 2017
3. Feb 21, 2017

### Ray Vickson

My response in #2 was a bit too hasty.

For $N = 2$ there is either no solution or infinitely many solutions. Letting $\theta_i /2 = u_i$, the system for $N=2$ reads as
$$\begin{array}{ccl}2 p_{12} &=& 1 + \tanh( 2 K p_{12} - u_1-u_2)\\ 2 p_{21} &=& 1 + \tanh( 2 K p_{21} - u_2 - u_2) \\ C_1 &=& p_{12} \\ C_2 &=& p_{21} \end{array}$$
The first two equations are the same, so $p_{12} = p_{21} = p.$ Then the last two equations read as $C_1 = p$ and $C_2 = p.$ If $C_1 \neq C_2$ the system has no solution; if $C_1 = C_2 = C$ then we have $p = C$, and the first equation gives a simple solution for $u_1 + u_2$. However, we cannot obtain $u_1$ and $u_2$ separately.

For $N = 3$ we can get an exact, complete solution. First, the $p_{ij}$ equations imply that $p_{ij} = p_{ji}$, so we have three $p$-variables $p_{12}, p_{13}, p_{23}$. The $p$-$C$ equations read as
$$\begin{array}{ccc} p_{12}+p_{13} &=& C_1\\ p_{12}+p_{23} &=& C_2 \\ p_{13} + p_{23} &=& C_3 \end{array}$$
For given $C_i$ this system has a unique solution for $p_{12}, p_{13}, p_{23}$, and getting it is just a matter of elementary algebra.

Now each $u_i + u_j$ can be determined by solving the equations connecting the $p$'s to the $u$'s:
$$u_i + u_j = 2Kp_{ij} -\text{arctanh}(2 p_{ij}-1),$$
for $ij = 12, 13, 23.$ In a way similar to the $p$-$C$ equations, these last three equations also have a unique solution that can be obtained by elementary (but increasingly messy) algebra.

For $N \geq 4$ I think you need to start using numerical methods, and you have the correct number of equations and variables to make it probable that the problem is solvable.

4. Feb 22, 2017

### dumbperson

Hey Ray, thanks for the answer! The next 2 days I'm quite busy so I'll fully read and think about your answer after that!

5. Feb 22, 2017

### haruspex

I can see how to show that if K<1 (any N), but how do you show it generally?

6. Feb 23, 2017

### Ray Vickson

Good point: for some $K > 1$ and some $\theta_i, \theta_j$ there are three positive roots to the equation
$$2x = 1 + \tanh(2*K*x -(\theta_i + \theta_j)/2),$$
so we could have $p_{ij}$ equal to one of the roots and $p_{ji}$ equal to one of the others. However, I don't see any way of handling such a situation numerically, since requiring two $p$s to be two separate numerical roots of some common equation is not something that can be implemented in any way that I can see. If we did have multi-armed formulas for the $p$s, we could set one $p$ to one arm of those formulas and the other $p$ to another arm, but if all we have are numerical methods, I think we are out of luck.

However, at least we can say that there exists a solution in which $p_{ij} = p_{ji}$ for all $i \neq j.$ However, the possible existence of multiple roots---even in this case---could cause real problems for a nonlinear solver such as Newton-Raphson, so it is probably even more important than I first hinted at to sneak up on a solution by small steps from some easily-solved starting approximation.

For the OP: the method I suggested to solve a sequence of problems in working towards the true solution is a well-known technique that falls under the general title of "homotopy method". There is a large literature on this topic, and a Google search under "homotopy method for nonlinear equations" will lead you to numerous relevant sources.

Last edited: Feb 23, 2017
7. Mar 6, 2017

### dumbperson

Hey Ray,

In general, we have $N(N-1)/2$ different $p_{ij}$ variables, correct? But we have $N$ amount of $p-C$ equations. So we have the right amount of equations / variables if $N(N-1)/2 = N$, which is true for $N =3$. Am I missing something or is this then not solvable if $N\neq 3$ ?

Last edited: Mar 6, 2017
8. Mar 6, 2017

### dumbperson

Ah, after solving the $p-C$ equations, we have $N(N-1)/2 - N$ unknown $p_{ij}$ variables left. In total (with the $u_i$), we have $N(N-1)/2 - N + N = N(N-1)/2$ unknown variables left. We have $N(N-1)/2$ equations that connect the $p$'s to the $u$'s, so it should be solvable numerically, I guess