Non Linear Equation Solver

Ishan Joshi edited this page Mar 17, 2018 · 1 revision

Introduction

A system of equations involving non-linear equations could be referred as non-linear system of equations.
A non-linear system of equations could be:

  • Inconsistent (Having no solutions)
  • Zero dimensional (with finite number of solutions)
  • Positive dimensional (with infinite solutions)

Solution to a system of Non-linear equations:

  1. By substitution method
  2. By elimination method (not used by solveset)
  3. By combination of both

Quadratic formula(solve_poly_system()) method has also been applied in nonlinsolve()

Current logic and Implementation

The Logic

Nonlinsolve identifies the type of equation(s) and divides its work into two parts:

1. If some of the equations of the system are non-polynomials: Substitution method is used.

2. If all the equations of the system are polynomials: Then again the work gets divided into:

  • Zero dimensional system: solve_poly_system() is used. If in case this throws an error, again substitution method is used.
  • Positive dimensional system: Here again substitution method is used.

Gröbner Basis for a system of equation is used to determine whether a system of equations is inconsistent, zero dimensional, or positive dimensional as mentioned here.

Gröbner Basis

A Gröbner basis G for a system of polynomials A is an equivalence system that possesses useful properties, for example, that another polynomial f is a combination of those in A iff the remainder of f with respect to G is 0. (Here, the division algorithm requires an order of a certain type on the monomials). Furthermore, the set of polynomials in a Gröbner basis have the same collection of roots as the original polynomials. For linear functions in any number of variables, a Gröbner basis is equivalent to Gaussian elimination.
More about Grobner Basis and its application can be found out here

Implementation

Nonlinsolve() identifies the kind of system as mentioned above and invokes the related function to solve it.

  • _handle_positive_dimensional(): It computes the grobner basis for the system and appends it to the new_system(list) and sends it to the substitution() function to get the solutions. Since the Grobner system is an equivalence system, the initial nonlinear equation now gets converted into a simplified form.
  • _handle_zero dimensional(): it computes the solution via solve_poly_system(). But there might be some extra solutions(as unrad was used in _separate_poly_nonpoly()).These need to be checked and removed if not a solution. For this purpose checksol is used.
  • Substitution():
    • _solve_using _known_values(): It is a helper to substitution() which finds solution with the help of solveset. It initially sorts the equations in the system such that eq with less number of variable is first in the list. Solution of every equation is found out with respect to the unsolved symbol. The result is appended to the newresult via _append_new_solution().

      • _append_new_solution(): Appends the solution if it is a valid solution. And returns delete_res in addition to the newresult, if it satilsfies the exclude list as returned by _check_exclude(). _check_exclude uses checksol to verify the solution.
      • If the solveset returns a coditionset or an Intersection or an Imageset, then such case is handled by the _extract_main_soln and add_intersection_complement.

Current limitations in nonlinsolve

  • It doesn't return a solution in LambertW form.
  • It is not capable of solving system of equations having trigonometric functions.
  • It is not able to solve if any of the equations is an inquality
Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.