 View Question Question
 Subject: Best way to solve a system made of linear and quadratic equations Category: Science > Math Asked by: vincent72-ga List Price: \$50.00 Posted: 06 Aug 2006 10:20 PDT Expires: 05 Sep 2006 10:20 PDT Question ID: 753149
 ```I am looking for an algorithm to solve systems made of linear AND quadratic equations of the form: A X = 0 X^T Q_i X = k_i^2 for i = 1..n My idea is to infer quadratic equations from the linear part (it is easy to create many of them) to get only quadratic equations and solve them by linearization. Is there a better way ?``` Request for Question Clarification by hedgie-ga on 11 Aug 2006 01:45 PDT ```Vincent 1) Are you interested in numerical solution? You do not need to linearize, and it may be only one available in most cases. 2) Your notation is a bit unclear, perhaps yoy can post a link to a gif? I suppose X.i (i,j =1,2, ... n) is n unknown A is (n x n ?? ) matrix ? (of rank n?) X Q X is quadratic form what is k_i ?? ^ means power? Hedgie``` Clarification of Question by vincent72-ga on 15 Aug 2006 00:14 PDT ```Hi Hedgie, thanks for your interest, 1) yes I am just looking for a numerical solution. 2) I used LaTeX conventions: ^ states the following character is an exponant _ states the following character is an index X is a n-vector of unknowns A is m x n matrix with m > n but rank(A) < n the k_i are just real numbers, some are 0, some aren't I have more linear equations than quadratic ones. I have a very vague intuition that (number of quadratic equations + rank A) = n but it can be wrong. vincent``` Request for Question Clarification by hedgie-ga on 21 Aug 2006 07:03 PDT ```Hi Vincent I can find a (free) numerical library, which will contain routines necessary to solve this type of sustem of eq. That is more then algorithm (since you get the soiurce of the program). However, I still need to know more of your specs: FORTRAN or c ? OS (windows? Linux, .. ) Or - does it matter? Is a subroutine sufficient (meaning, are you able to write a calling front end..)? Also, you did not explain X^T :: is it transpose or power ? if X is a vector and Q is n x n matrix then X Q X is a number, namely sum ove i,j ( X_i Q_i_j X_j) ??? not k_i (n numbers). Please , be a bit less telegraphic and more consistent . Hedgie``` Clarification of Question by vincent72-ga on 22 Aug 2006 00:46 PDT ```> I can find a (free) numerical library, which will contain routines necessary to solve this type of sustem of eq. > That is more then algorithm (since you get the soiurce of the program). > However, I still need to know more of your specs: FORTRAN or c ? OS (windows? Linux, .. ) > Or - does it matter? Is a subroutine sufficient (meaning, are you able to write a calling front end..)? C would be better than FORTRAN, the OS does not matter. I'd prefer an algorithm than source code, but if your library provides mathematical explanations for the source code, it's OK. Please note that, as I said in my original question, I already have a solution. However making quadratic equations from linear ones looks quite awkward, and I'd like to know what "real mathematicians" would do. > Also, you did not explain X^T :: is it transpose or power ? How do you compute the power of a vector ? :-) Yes, it is transpose. > if X is a vector and Q is n x n matrix then X Q X is a number, namely > sum ove i,j ( X_i Q_i_j X_j) ??? > not k_i (n numbers). X^T Q X = k is a single quadratic equation. I have several ones, that's why in my question BOTH Q and k are indexed by i. If you prefer, I can denote my quadratic equations by: X^T Q0 X = k0 X^T Q1 X = k1 X^T Q2 X = k2 X^T Q3 X = k3 ... where Q0, Q1, Q2 are nxn matrices, and k0, k1, k2... are real numbers, and X is a n-vector. They are the quadratic equations that must be solved in addition to a linear system of the form: A X = 0 where rank A < n as said above.``` Subject: Re: Best way to solve a system made of linear and quadratic equations Answered By: hedgie-ga on 22 Aug 2006 21:45 PDT
 ```Problem: find (real) roots of a system of L equations Sum over (i,j) X_i Q_i_j_l X_j = K_l where i,j, .. = 1,2, .. n and l= 1,2,.. L K_l is given real vector and Q is given real n x n x L matrix. Single polynomial of N-th degree will have N complex roots and 0 to N real roots. Then set of two quadratic equations will then have 0 to 4 sets of real roots, etc. There is large amount of literature on numerical determination of zeros of a system of polynomials, and most popular packages for symbolic algebra maple, reduce, maxyma, ... have routines dealing with this problem. There is no general solution - a solution which would provide approximation with arbitrary selected precision of all roots in a finite computer time. Most effective algorithm, Gr�bner Bases Algorithm, approximates real solutions by rational numbers and is limited, in some cases, by high demands on memory and CPU time. It is a open field of study in computational algebra; At the end of this answer I list book which provides intro to the field. For practical purposes, one would use a symbolic algebra package (mathematica, maple, reduce, maxyma, ...) and try to factorise the polynomials and to reduce the system to a triangular form. Here we focus on the theory and algorithms for general solutions: History http://www.math.utah.edu/~preszler/research/grobner.pdf Overview: Solving Algebraic Systems using Matrix Computations Finding roots of polynomial equations, http://www.research.att.com/areas/visualization/ papers_videos/pdf/242965-mk96.pdf Tutorial on Gr�bner Bases Algorithm Systems of Equations The Problem of Exact Solution of Systems of Algebraic Equations. Questions about the Solvability of Systems of Algebraic Equations. Solution of Linear Homogeneous Equations with Polynomial Coefficients. http://www.symbolicnet.org/areas/GB_and_CS/groebner.html Limitations of the method Some theoretical problems when solving systems of polynomial equations using Gro�bner bases http://portal.acm.org/citation.cfm?id=122523 Specialised packages: http://dmoz.org/Computers/Algorithms/Computational_Algebra/ Bibliography http://www1.elsevier.com/homepage/sac/cam/mcnamee/10.htm http://www.risc.uni-linz.ac.at/people/wwindste/Research/GB/Bibliography/bibliography/bibliography.html Books: Computer algebra: systems and algorithms for algebraic computation Pages: 267 Year of Publication: 1988 ISBN:0-12-204230-1 Authors J. H. Davenport at al. Publisher Academic Press Ltd. London, UK, UK http://portal.acm.org/citation.cfm?id=48243&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 http://www.bestwebbuys.com/0122042301 SEARCH TERMS: Grobner base roots of system of algebraic equations roots of system of polynomial equations zeros of multivariate polynomials polynomials, lexicographical ordering This answer aims to show what is known about this problem in the technical literature. As stated on the beginning, complete and general algorithm is not known. I hope that this overview of the state of the art is useful. Hedgie``` ```I'm not sure what linearization is, but it seems to me that the best way to get rid of the linear equations is as follows: Get the row reduced echelon form of the matrix A. This is standard procedure for solving a system of linear equations. It identifies the independent variables (say, x(1) thru x(k) ) and the dependent variables (say x(k+1) thru x(n) ). Substitute the dependencies into the quadratic equations and simplify them to get new quadratic equations in the independent unknowns. Then solve them using your method. It seems that this would be more efficient than making quadratic equations from linear ones.```
 ```Hi Berkeleychocolate, Linearization is a simple way to solve systems of quadratic equations. You just turn the quadratic system into a linear one where the unknows are products of two unknowns of the original system ie x2 y2 xy ... It is a little bit rude but it is simple and it gives a solution in closed form when you have enough quadratic equations --> that is why I wanted to convert my linear eq into quadratic eq. Your idea of using the row reduced echelon form is a good one, but I am not sure I will get enough equations for the linearization. vincent``` 