Using Linear Algebra to solve systems of non-linear equations

  • Thread starter Edwin
  • Start date
165
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
 

JasonRox

Homework Helper
Gold Member
2,228
2
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:

HallsofIvy

Science Advisor
41,618
821
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.
 

JasonRox

Homework Helper
Gold Member
2,228
2
Maybe I misread your question.

Is u and v constants?
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,828
14
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
 

JasonRox

Homework Helper
Gold Member
2,228
2
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.
 

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,828
14
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

?
 
165
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
 

HallsofIvy

Science Advisor
41,618
821
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.
 
165
0
That's correct.

Best Regards,

Edwin
 

Want to reply to this thread?

"Using Linear Algebra to solve systems of non-linear equations" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Top Threads

Top