1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ the conditions $|x_k-1|\leq 1$ make this a system of quadratic equations and (quadratic) inequalities. $\endgroup$
    – Dima Pasechnik
    Commented May 31, 2014 at 7:27
  • 1
    $\begingroup$ Why approximated solution is acceptable, but you reject numerical methods? $\endgroup$
    – Michael
    Commented Jun 3, 2014 at 16:58
  • $\begingroup$ 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. $\endgroup$
    – A13j0
    Commented Jun 4, 2014 at 18:19

1 Answer 1

Reset to default
1
$\begingroup$

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)$

Improve this answer
$\endgroup$
6
  • $\begingroup$ the question explicitly says "without using a numerical method". $\endgroup$
    – Dima Pasechnik
    Commented Jun 3, 2014 at 16:54
  • 2
    $\begingroup$ OK Dima. Let $n=2$ ; how do you find a root of an irreducible polynomial of degree $16$ without using numerical methods ? $\endgroup$
    – loup blanc
    Commented Jun 3, 2014 at 18:43
  • $\begingroup$ just as computer algebra systems do. E.g. by specifying Thom encoding, i.e. the signs of the derivatives at the root. $\endgroup$
    – Dima Pasechnik
    Commented Jun 4, 2014 at 0:19
  • $\begingroup$ 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... $\endgroup$
    – loup blanc
    Commented Jun 4, 2014 at 9:07
  • $\begingroup$ 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. $\endgroup$
    – loup blanc
    Commented Jun 4, 2014 at 9:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .