11
$\begingroup$

Let $a$ be a non-negative real number, $b_1, b_2, b_3$ be real numbers, and $x, y, z$ be variables. Is it possible to analytically find the root closest to origin $(0, 0, 0)$ of the set of nonlinear equations given by:

$$\begin{cases} ax + yz = b_1\\ ay + xz = b_2\\ az + xy = b_3\;\;\; ?\end{cases}$$

Edit: This question is related to my research on quadrotor control. The roots of the set of nonlinear equations give the equilibrium points of the rigid body dynamics under a specific control input. I couldn't find any solution. I can only solve the problem when at least two of the $ b_1 $, $ b_2 $, and $ b_3 $ are zero.

$\endgroup$
11
  • 6
    $\begingroup$ While this question doesn't exactly include the precise mathematical steps to solving it, overall I find the context sufficient. Therefore, I'm voting to reopen the question. $\endgroup$ Commented Apr 13, 2023 at 2:20
  • 4
    $\begingroup$ @lonestudent I agree with the assessment. I actually did vote to reopen it a few hours ago, though I still see one single reopen vote for whatever reason. $\endgroup$
    – dxiv
    Commented Apr 13, 2023 at 5:59
  • 1
    $\begingroup$ The concept of a "root" to a system of equations is not clear to me! $\endgroup$
    – NoChance
    Commented Apr 13, 2023 at 21:34
  • 1
    $\begingroup$ @lonestudent I suggest you restore your answer since it is a good answer. I don't think that Galois theory was central to the question, even less so in OP's context of applied math. $\endgroup$
    – dxiv
    Commented Apr 14, 2023 at 2:23
  • 1
    $\begingroup$ @NoChance Given the notation and the context, I'd expect "root" to mean a point $(x,y,z)$ in the 3D space that satisfies the equations, and "closest" to mean the euclidean distance. $\endgroup$
    – dxiv
    Commented Apr 14, 2023 at 5:33

3 Answers 3

6
+100
$\begingroup$

If $a=0$ the system is trivial to solve, otherwise substituting $x\mapsto ax$, $y\mapsto ay$, $z\mapsto az$, $b_k \mapsto a^2 b_k$ and canceling out a factor of $a^2$ it can be assumed WLOG that $a=1$ and the system is:

$$ \begin{align} x + yz &= b_1 \tag{1}\\ y + zx &= b_2 \tag{2}\\ z + xy &= b_3 \tag{3} \end{align} $$

This can be approached in several different ways, outlined below, but all of them eventually lead to a quintic equation which is not solvable by radicals in general, so the practical answer is to solve numerically.

  • Two variables can be eliminated between the three equations, leaving an equation in one variable alone. This was done step-by-step in @lonestudent's answer, deleted since but hopefully to be restored at some later time. Rather than duplicating the calculations here, this is the end result courtesy WA: $$ x^5 - b_1 x^4 - 2 x^3 + (2 b_1 + b_2 b_3) x^2 + (-b_2^2 - b_3^2 + 1) x - b_1 + b_2 b_3 = 0 \tag{4} $$

  • The symmetry of the system suggests combining the equations and expressing everything in terms of the elementary symmetric polynomials $e_1=x+y+z$, $e_2=xy+yz+zx$, $e_3=xyz$. After routine calculations, the following system in terms of $e_1,e_2,e_3$ is derived: $$ \begin{align} e_1 + e_2 &= u = b_1 + b_2 + b_3 \tag{5} \\ e_1e_2 + e_1 e_3 + e_2 - 3e_3 &= v = b_1b_2 + b_2b_3 + b_3b_1 \tag{6} \\ e_1^2e_3 - 2e_1e_3 + e_2^2 + e_3^2 - 2e_2e_3 + e_3 &= w = b_1b_2b_3 \tag{7} \end{align} $$ Eliminating (for example) $e_2, e_3$ between the equations gives an equation in $e_1$ alone, unsurprisingly also a quintic: $$ e_1^5 - e_1^4 u + e_1^3 (-4 u + v - 6) + e_1^2 (4 u^2 + 14 u - v - w + 8) + e_1 (-8 u^2 - 4 u v - 12 u + 3 v + 6 w - 3) \\ + 4 u^2 + 4 u v + 3 u + v^2 - 3 v - 9 w = 0 \tag{8} $$

  • If $x=0$ is a solution then it follows from $(2),(3)$ that $y=b_2, z=b_3$, and the system is compatible iff $(1)$ is satisfied i.e. $b_2b_3=b_1$. Same goes for $y,z=0$, which leaves the case $p=xyz \ne 0$ to consider. The equations can then be rewritten as: $$ \begin{align} x^2 - b_1 x + p &= 0 \tag{9}\\ y^2 - b_2 y + p &= 0 \tag{10}\\ z^2 - b_3 z + p &= 0 \tag{11} \end{align} $$ Eliminating $x,y,z$ between $(9),(10),(11)$ and $p = xyz$ gives a (laborious) sextic equation in $p$ alone, which reduces to a quintic after removing the ineligible root $p=0$.

Taking e.g. equation $(4)$, that's a quintic, which is not solvable by radicals in general. To show that $(4)$ is not some special form of quintic which happens to always be solvable, it is enough to exhibit a case where it is not solvable. For example, when $b_1 = 1$, $b_2 = 2$, $b_3 = 3$ the quintic is: $$ x^5 - x^4 - 2 x^3 + 8 x^2 - 12 x + 5 = 0 \tag{12} $$

It can be easily verified that the LHS in $(12)$ is negative at $x = -3, 1$ and positive at $x = 0, 2$, so the quintic has one negative and two positive real roots, and by Descartes' rule of signs these are all the real roots it can have, so the remaining two roots are complex conjugates.

It can also be verified that $(12)$ is irreducible, then it follows that it is not solvable by radicals because the full symmetric group $S_5$ is not solvable, and the Galois group of $(12)$ is $S_5$, based on:

Symmetric group of prime order

If $f$ is an irreducible polynomial of prime degree $p$ with rational coefficients and exactly two non-real roots, then the Galois group of $f$ is the full symmetric group $S_{p}$.

That the quintic $f(x)$ in $(4)$ is not solvable in general does not mean that it cannot be solvable in particular cases. A few examples where the quintic factors and is therefore solvable:

  • $b_2=b_3\text{:}\quad$ f(x) = $\,(x - 1)^2 (x^3 - (b_1 - 2) x^2 - (2 b_1 - 1) x + b_2^2 - b_1)\;$ ;

  • $b_2=b_1^2, b_3=b_1^3\text{:}\quad$ f(x) = $\,{(x - b_1) (x^4 - 2 x^2 + b_1^5 x - b_1^4 + 1)}\;$ ;

  • $b_1=1, b_2=0, b_3=-1\text{:}\quad$ f(x) = $\,{(x^2 - x - 1) (x^3 - x + 1)}\;$.

Algorithms exist to determine whether a given quintic is solvable (e.g. 1), but the calculations are extremely heavy, and if it turns out to be solvable it is even more difficult to determine the roots analytically, which makes it impractical in virtually all applications.

$\endgroup$
3
  • $\begingroup$ Thank you very much for the very detailed answer. It looks like we have no analytic solution for this set of equations, in general. We need additional assumptions on b1 b2 b3. $\endgroup$ Commented Apr 15, 2023 at 2:23
  • 1
    $\begingroup$ @AhmetTahaKORU You are correct. If you have additional information on $b_1,b_2,b_3$ (or, actually, $a^2b_1, a^2b_2, a^2b_3$ with the notations from the original post) you should edit the question and add the information there. It could make the difference between unsolvable and solvable, or even between an easier numeric solution vs. a more complicated one. However, if the additional information changes the question significantly, etiquette would be to leave this one as-is and ask a new question. $\endgroup$
    – dxiv
    Commented Apr 15, 2023 at 2:44
  • $\begingroup$ @AhmetTahaKORU See this desmos graph: explanation in answer: desmos.com/calculator/6oepotjtku $\endgroup$ Commented May 8, 2023 at 17:02
2
$\begingroup$

Let $$ \begin{cases} ax+yz=b_1\\ ay+zx=b_2\\ az+xy=b_3 \end{cases}\quad \begin{cases} s=x+y+z\\ r=xy+yz+zx\\ p=xyz, \end{cases}\quad \begin{cases} u=b_1+b_2+b_3\\ v=b_1^2+b_2^2+b_3^2\\ w=b_1^3+b_2^3+b_3^3, \end{cases}\quad $$ then $$\sum\limits_\bigcirc x^2=s^2-2r,\quad \sum\limits_\bigcirc y^2z^2=r^2-2sp,\quad \sum\limits_\bigcirc x^3=s^3-3sr+3p,$$ $$\sum_\bigcirc y^3z^3=r^3-3srp+3p^2,$$ $$\begin{align} &\sum_\bigcirc (ax+yz)=as+r,\\ &\sum_\bigcirc (ax+yz)^2=\sum_\bigcirc (a^2x^2+2axyz+y^2z^2)=a^2(s^2-2r)+6ap+ r^2-2sp,\\ &\sum_\bigcirc (ax+yz)^3=\sum_\bigcirc (a^3x^3+3a^2x^2yz+3axy^2z^2+y^3z^3\\ &=a^3(s^3-3sr+3p)+3a^2sp+3arp+r^3-3rsp+3p^2, \end{align}$$ easily to get the system in the form of $$ \left\{\begin{align} &as+r=u\\ &a^2(s^2-2r)+6ap+ r^2-2sp=v\\ &a^3(s^3-3sr+3p)+3a^2sp+3arp+r^3-3rsp+3p^2=w,\\ \end{align}\right.$$ $$ \left\{\begin{align} &as+r=u\\ &2a^2r-6ap+2ars+2ps=u^2-v\\ &3a^3(sr-p)+3a^2s(sr-p)+3ar(sr-p)+3p(sr-p)=u^3-w,\\ \end{align}\right.$$ $$ \left\{\begin{align} &as+r=u\\ &2a(sr-p)+2a^2r+2p(s-2a)=u^2-v\\ &3(a^3+au+p)(sr-p)=u^3-w,\\ \end{align}\right.$$ or, in the notation $$c=a^3+au,\quad d=\dfrac{u^2-2a^2u-v}2,\quad q=sr-p,\tag1$$ $$ \left\{\begin{align} &as+r=u\\ &(s-2a)p+aq=d+a^3s\\ &p+q=s(u-as)\\ &(p+c)q=\dfrac{u^3-w}3,\\ \end{align}\right.\tag2$$ The second and the third equations of the system $(2)$ present a linear system by $\;p,q.\;$

If $\;s=3a,\,$ then the system has not solutions (if the equations are not proportional) or infinity much solutions (otherwize).

If $\;s=3a,\;$ then $$p=-\dfrac{a^2s^2+(a-u)as+d}{3a-s},\quad q=\dfrac{as^3-(2a^2+u)s^2+(a^2+2au)s+d}{3a-s}.\tag3$$

Substitution of $(3)$ transforms the fourth equation of $(2)$ to the quintic by $s,$ which does not have analytic solution. However, it looks suitable for numeric solutions.

Note, that for each obtained trinity ${s, r, p}$ should get corresponding trinity $x, y, z$ from the cubic $$x^3-sx^2+rx+p=0.$$

$\endgroup$
2
$\begingroup$

This system can be easily solved using the iteration $$\mathbf v_{n+1}=\mathbf v_n-\frac{f(\mathbf v_n)}{\|\nabla f(\mathbf v_n)\|^2}\nabla f(\mathbf v_n)$$ where $$f(x,y,z)=(ax+yz-b_1)^2+(ay+xz-b_2)^2+(az+xy-b_3)^2.$$ Pick $\mathbf v_0=(0,0,0).$

I actually have it on desmos for you here: you don't even need to code it: https://www.desmos.com/calculator/erzwdi0n2u. For $$a=3.5,b_1=-1.8,b_2=2.9,b_3=2.6$$ we get $$\mathbf v_{12}\approx(−0.807653573837,1.0549512409,0.985243174676)$$

My old answer is in the grey below.


Newton's Method


Just use Newton's method for higher dimensions. Our iteration on the vector $v=(x,y,z)$ will be $$v_{k+1}=v_k-J(v_k)^{-1}f(v_k),$$ where $$f(x,y,z)=(ax+yz-b_1,ay+xz-b_2,az+xy-b_3),$$ so $$J=\begin{pmatrix}a&z&y\\ z&a&x\\ y&x&a\end{pmatrix}\ \therefore > J^{-1}=\frac{\begin{pmatrix}a^2-x^2&-(za-xy)&zx-ay\\ > -(za-xy)&a^2-y^2&-(ax-zy)\\ zx-ay&-(ax-zy)&a^2-z^2\end{pmatrix}}{a(a^2-x^2)-z(az-xy)+y(zx-ay)}.$$

You can choose an intial point $v_0$ near $\bf{0}$.


Solving the Quintic

--- Your system, courtesy of @dxiv, is reducible to the quintic equality $$x^5-2x^3-b_1 x^4 + (2 b_1 + b_2 b_3) x^2 + (-b_2^2 - b_3^2 > + 1) x - b_1 + b_2 b_3 =0.$$ From here, if your quintic doesn't have a repeating root, then either one or the other of the following iterations will converge on a given root, but not both: $$x_{k+1}=\sqrt[5]{-(-2x^3_k-b_1 x^4_k + (2 b_1 + b_2 b_3) x^2_k + > (-b_2^2 - b_3^2 + 1) x_k - b_1 + b_2 b_3)}$$ OR $$ > x_{k+1}=-\frac{x^5_k-2x^3-b_1 x^4_k + (2 b_1 + b_2 b_3) x^2_k + - b_1 > + b_2 b_3}{(-b_2^2 - b_3^2 + 1)} .$$ The way these iterations are derived are from the fact that, supposing one has obtained the condition $|C(x)|<1$ for the former iteration's convergence on the root $x$, the latter will have condition $|C(x)|>1,$ and a repeated root will yield the condition $|C(x)|=1$ anyway, so then either the one or the other converges on a given root, but not both. It is possible that both converge to different roots. There is a combinatorial identity for the series expansion of $x$ as a function of the variables in its coefficients, that is, if $$x^n+\alpha > x^{n-1}+\beta x^{n-2}+\cdots+\zeta=0,$$ then

$$x=\sum_{i,j,...,k}C_{i,j,...,k}\alpha^i\beta^j\cdots \zeta^k$$ for known $C_{i,j,...,k}$ which are a generalization of a well known sequence. However, I know this from a research mathematician's YouTube channel who has not yet published these results, and will publish in the near future, so I will not reveal his results until I can appropriately cite his paper. His channel is [Wild Egg Maths][1], and with a paid subscription to the channel (by becoming a member), you'll be able to review all his polynomial content. It's fairly cheap and you'll only need the subscription long enough to view a few of the videos in his "[Solving Polynomial Equations][2]" playlist.


If you're not into any of these methods, just solve the quintic brute force. Apply a quartic Tschirnhaus transformation and get to work, or use the method of differential resolvents. If you manage to get it into the Bring Quintic form, then see the results from [Wolfram Math World][3].

[1]: https://www.youtube.com/channel/UCriFv3G22iOUidUhkIGXuhw [2]: https://www.youtube.com/watch?v=XHC1YLh67Z0&list=PLzdiPTrEWyz7hk_Kzj4zDF_kUXBCtiGn6&ab_channel=WildEggMaths [3]: https://mathworld.wolfram.com/QuinticEquation.html

$\endgroup$

You must log in to answer this question.

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