Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I want to solve this system of N non-linear equations without using a numerical method:

$x_{k}^{2}= \alpha_{k }+ \sum\limits_{m=1}^{N} (\beta_{km} x_{m} + \psi_{km} x_{m}^{*})$

With

$\left| x_{k}-1 \right| \leq 1 $

All values are complex and $x^{*} $ is the conjugate of x. Any idea? An approximated solution could be usefull

share|improve this question
    
the conditions $|x_k-1|\leq 1$ make this a system of quadratic equations and (quadratic) inequalities. –  Dima Pasechnik May 31 at 7:27
1  
Why approximated solution is acceptable, but you reject numerical methods? –  Michael Jun 3 at 16:58
    
The are many roots for this polinomial. However I am only interested in the solutions that fullfils the inequality. I would like to know how many solutions fullfils the inequality. If I have an approximate solution the I have an initial point for the Newton Raphson methods. –  A13j0 Jun 4 at 18:19

1 Answer 1

Put $X=[x_1,\cdots,x_N]^T$. We consider an equation in the form $X\circ X+A'+B'X+C'\overline{X}=0$ where $\circ$ is the Hadamard product, $A'$ is a vector and $B',C'$ are square matrices.

Step 1. Put, for every $k$, $x_k=1+y_k$. Then $Y$ satisfies an equation in the previous form. Then we may assume that $|x_k|\leq 1$.

Step 2. Separate real and imaginary parts with $X=U+iV$. We obtain a system (in the unknown REAL vectors $U,V$) in the following form $\{f(U,V)=U\circ U-V\circ V+A+BU+CV=0,\;\;g(U,V)=2U\circ V+D+EU+FV=0\}$.

Solving (exactly) this system is hopeless. For $N=2$, there are $2^4$ solutions in $\mathbb{C}$ (using the Grobner basis method, we must solve an irreducible polynomial of degree $2^4$). I think that, more generally, there are $2^{2N}$ solutions in $\mathbb{C}$. Obviously, we keep only the real solutions!

You search local solutions ; then you can use the Newton's method. Let $F=[f,g]^T$. The recurrence formula is well-known: $[U_{n+1},V_{n+1}]^T=[U_n,V_n]^T-(DF([U_n,V_n]^T))^{-1}([f(U_n,V_n),g(U_n,V_n)]^T$. Here $DF([U,V]^T)=\begin{pmatrix}2\tilde{U}+B&-2\tilde{V}+C\\2\tilde{V}+E&2\tilde{U}+F\end{pmatrix}$ where $\tilde{U}=diag(u_1,\cdots,u_N)$ and $\tilde{V}=diag(v_1,\cdots,v_N)$

share|improve this answer
    
the question explicitly says "without using a numerical method". –  Dima Pasechnik Jun 3 at 16:54
2  
OK Dima. Let $n=2$ ; how do you find a root of an irreducible polynomial of degree $16$ without using numerical methods ? –  loup blanc Jun 3 at 18:43
    
just as computer algebra systems do. E.g. by specifying Thom encoding, i.e. the signs of the derivatives at the root. –  Dima Pasechnik Jun 4 at 0:19
    
Dima, a computer algebra system gives an approximation of the real solutions of a system. Its uses Thom encoding , resultants and especially Grobner basis theory. Behind that , there is an enormous amount of formal calculations. Yet, at the end of the process, if you want a good localization of the roots, you must use successive approximations (cf. Salsa, a software due to Rouiller). Sequel below... –  loup blanc Jun 4 at 9:07
    
If we want to use Newton's method, we must know a poor localization of the roots. Else we must use a software ; yet if, for instance , $n=5$, then there are $1024$ complex solutions and I think that the software cannot do the calculation in a reasonable time. –  loup blanc Jun 4 at 9:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.