Using Linear Algebra to solve systems of non-linear equations

  • Thread starter Edwin
  • Start date
  • #1
162
0
I did some number crunching and found the following:

Given n equations in n unknowns:

a*f(x) + b*g(y) = c
d*f(x) + e*g(y) = f

If there is a solution to these equations, you can use substitution to transform these equations into a set of linear equations and solve using linear algebra.

Let f(x) = u and g(y) = v

Then

a*f(x) + b*g(y) = c
d*f(x) + e*g(y) = f

which becomes

a*u + b*v = c
d*u + e*v = f

Which can be solved for u and v using linear algebra.

x and y can then be solved for by solving the corresponding equations

u = f(x), and v = g(y) thus making it possible to solve systems of non-linear equations of the form above using linear algebra.

Any thoughts?

Edwin G. Schasteen
 

Answers and Replies

  • #2
JasonRox
Homework Helper
Gold Member
2,323
3
You aren't using Linear Algebra to solve for x and y.

Linear Algebra can solve for a,b,d, and e if a solution exists. It doesn't do anything regarding x and y.

You can not solve u and v through that at all.

Let f(x) = x^10 + x^9 + x + 1 = u, and g(y) = y^11 + y^10 + y + 1 = v.

According to you, we can solve for u and v.

a*u + b*v = c
d*u + e*v = f

...then for x and y.

Using my simple polynomials, solve for x and y, which you said you can do. To make it easier, let a=1, b=0, and c=0.

a*u + b*v = c
u + 0 = 0
f(x) = 0
x^10 + x^9 + x + 1 = 0

Hmmm... this isn't helping much.

How does Linear Algebra solve that?
 
Last edited:
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,847
966
Edwin said:
I did some number crunching and found the following:
Given n equations in n unknowns:
a*f(x) + b*g(y) = c
d*f(x) + e*g(y) = f
If there is a solution to these equations, you can use substitution to transform these equations into a set of linear equations and solve using linear algebra.
Let f(x) = u and g(y) = v
Then
a*f(x) + b*g(y) = c
d*f(x) + e*g(y) = f
which becomes
a*u + b*v = c
d*u + e*v = f
Which can be solved for u and v using linear algebra.
x and y can then be solved for by solving the corresponding equations
u = f(x), and v = g(y) thus making it possible to solve systems of non-linear equations of the form above using linear algebra.
Any thoughts?
Edwin G. Schasteen

What you are saying is certainly true but I don't see anything new. If I had, for example, the two equations
x2+ y2= 1 and
x2- y2= 1 then I would add the two equations to get 2x2= 2 so x= 1 or -1. Putting that back into either equation I would have 1+ y2= 1 or 1- y2= 1 both of which give y2= 0 or y= 0. The two solutions to the system of equations are x= 1, y= 0 and x= -1, y= 0.

Of course, you are assuming that you have n LINEAR equations in n functions of single variables. Most "non-linear" equations are more complicated than that: for example x2- 2xy+ y2= 1 and x2+ ey= 1 or sin(x)+ cos(x)= 1.
 
  • #4
JasonRox
Homework Helper
Gold Member
2,323
3
Maybe I misread your question.

Is u and v constants?
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Linear Algebra can solve for a,b,d, and e if a solution exists. It doesn't do anything regarding x and y.

You can not solve u and v through that at all.
Let me try explaining it a different way:

Suppose the system of equations

au + bv = c
du + ev = f

has a unique solution (u,v) = (m,n). (As is typical with 2 equations and 2 unknowns)


Then, if you were asked to solve the system of equations

a*f(x) + b*g(y) = c
d*f(x) + e*g(y) = f

for x and y.

The previous work allows you to immediately reduce this problem to solving

f(x) = m
g(y) = n
 
  • #6
JasonRox
Homework Helper
Gold Member
2,323
3
Hurkyl said:
Let me try explaining it a different way:
Suppose the system of equations
au + bv = c
du + ev = f
has a unique solution (u,v) = (m,n). (As is typical with 2 equations and 2 unknowns)
Then, if you were asked to solve the system of equations
a*f(x) + b*g(y) = c
d*f(x) + e*g(y) = f
for x and y.
The previous work allows you to immediately reduce this problem to solving
f(x) = m
g(y) = n

Yes, but that doesn't really help at all.
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Really? I think solving

x^10 + x^9 + x + 1 = 7
y^11 + y^10 + y + 1 = 3

looks much much easier than trying to solve

5y^11 + 3x^10 + 5y^10 + 3x^9 + 3x + 5y + 8 = 36
y^11 - x^10 + y^10 - x^9 - x + y = -4

Don't you?


And how else were you planning on solving the equation

cos t + 3 sin s = 2
4 cos t - 2 sin s = -1

?
 
  • #8
162
0
Thanks for your input guys!


Hurkyl, I hadn't thought of using this to solve systems of transcendental equations. That's an interesting thought!

Your thoughts regarding simplification of the systems of algebraic equations of the same form into more managable equations of a single variable were exactly what I was aiming at. Given a system of non-linear equations of the form below, you can reduce the equations to a system of non-linear equations of a single variable for each of the variables just as you've shown below. One can then use any variety of numerical methods to approximate sollutions to the given equations.

What do you think?

Inquisitively,

Edwin
 
  • #9
HallsofIvy
Science Advisor
Homework Helper
41,847
966
It's what I would expect to be taught in any intermediate algebra course.
The crucial point is that "non-linear equations of the form below" are not general non-linear equations. Your form is restricted to "linear equations of non-linear functions of a single variable". Obviously one can use linear equation methods to reduce to separate non-linear equations.
 
  • #10
162
0
That's correct.

Best Regards,

Edwin
 

Related Threads on Using Linear Algebra to solve systems of non-linear equations

  • Last Post
Replies
4
Views
7K
Replies
2
Views
2K
Replies
5
Views
2K
Replies
1
Views
6K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
1K
Top