Trying to solve any equation ever with Recurrences

  • Thread starter Gackhammer
  • Start date
In summary, a recurrence equation is an equation that defines a sequence of numbers or functions where the next term is defined in terms of previous terms. To solve a recurrence equation, you can use methods such as substitution, iteration, or generating functions to find a closed-form solution. They have many applications in various fields, but not all equations can be solved using recurrences. There are also limitations to using recurrence equations, such as not always providing an exact solution and becoming computationally expensive for larger values of n.
  • #1
Gackhammer
13
0
So, I am trying to make up this theory of trying to solve any equation ever using recurrences... Ill show you what I mean

Consider the quadratic function -
f(x) = x^2 - 3x + 2

Well, obviously you could do this the easy way and do factoring and figure out x = 2 or 1... no big deal right?

But what if we try a different way... albeit harder and more complicated... but Itll make a bit more sense later in this post

So what if we do this

x^2 - 3x + 2 = 0
x(x) - 3x + 2 = 0
x(x) = 3x-2
x = (3x-2)/x

So what does this mean?

Well, plug in a random number into your calculator... say 10...
Now do (3x-2)/x, and youll get 2.8...
now (if your using a TI-84 like me), plug in ((3*Ans)-2)/Ans
So Ans = 2.8, this should yield 2.28
Now Ans = 2.28, this should yield 2.125
From 2.125, you get 2.0588...

Basically, If you do this an infinite amount of times, it will converge to 2... which is one of the solutions of the equation...

Now say you rearrange the equation differently...
x^2 -3x+2 = 0
x(x) - 3x + 2 = 0
(x-3)x = -2
x = (-2)/(x-3)

If you do the same method as above, it will converge to 1 for any initial value you put in for x, which is the other zero for the quadratic equation...So... why am I wasting my time with this?

Well, consider this equation

4x = e^(.5x)

Well... idk how to solve this equation... but what if we do the thing I just did, where we set one side of the equation to x then infinitely compute the other side...

x = e^(.5x)
ln(4x) = .5x
2ln(4x) = x

If you pick 20 for the first x, 2ln(4x) will yield 8.76, then 7.11, then 6.69, and so on, until it converges to a number 6.523371369...

Is this right? well
4(x) = e^(.5x)
4(6.523371369) = e^(.5(6.523371369))
26.09 = e^(3.26)
26.09 = 26.09

So... that's the solution... by using an infinite recursion of setting one side of the equation to x, then we will get some sort of solution...

Now... this doesn't always work... for example, say we did (from the previous equation)

4x = e^(.5x)
x = (e^(.5x))/4

If you do this, then x will converge to infinity. Now you may think that this is wrong... but I feel this is right, since they both technically (intersect) at infinity. In theory, 4(infinity) = e^(infinity)... so is it really wrong? I don't believe so...Anyway... my theory is that you can solve a solution for an equation when you set the equation to the form of
x = f(x)
Using an infinite recursive calculation.Now, I really don't know how to dive more into this theory, since I think this involves math that's super crazy (more than I know). I am a computer engineer, so I don't have the biggest arsenal of theoretical math at my disposal. I do know that this might have to do something with damping, since some of the recurrences will have an overdamped, underdamped, and critically damped response to converging to the solution... but... i don't know...
So... any thoughts on this? Any suggestions on how to move forward with this? Or has someone done this before?

And no, this does not have anything to do with homework, this is just fun theoretical stuff I am doing on my own and I would like input/other ideas to help me move forward with this. If this post is deemed by the admins to not belong here, then Ill delete this post (no questions asked) and move it to the Homework Section (or wherever they tell me to put it). All I want is some outside input for this.
 
Last edited:
Mathematics news on Phys.org
  • #2
A lot of these methods are pretty generic numerical techniques (see e.g. Newton's method). Note that you're not really "solving", only approximating solutions.
 
  • #3
Gackhammer said:
Now... this doesn't always work... for example, say we did (from the previous equation)

4x = e^(.5x)
x = (e^(.5x))/4

If you do this, then x will converge to infinity. Now you may think that this is wrong... but I feel this is right, since they both technically (intersect) at infinity. In theory, 4(infinity) = e^(infinity)... so is it really wrong? I don't believe so...

You don't converge to infinity, you diverge to infinity.
Two real valued functions cannot intersect at infinity.
And "in theory" (i.e. in real analysis), 4 times infinity is not defined. Neither is e to the power of infinity.
You are also using the term "technically" is very non-technical manner.

Anyway... my theory is that you can solve a solution for an equation when you set the equation to the form of
x = f(x)
Using an infinite recursive calculation.

Try it with the logistic map.
 
  • #4
pwsnafu said:
Try it with the logistic map.

if x := f(x) gets you in a cycle,

x := k f(x) + (1-k)x with k < 1 will probably work. Use a smaller k if there are still problems
 
  • #5
Gackhammer said:
So, I am trying to make up this theory of trying to solve any equation ever using recurrences... Ill show you what I mean

Consider the quadratic function -
f(x) = x^2 - 3x + 2

Well, obviously you could do this the easy way and do factoring and figure out x = 2 or 1... no big deal right?

But what if we try a different way... albeit harder and more complicated... but Itll make a bit more sense later in this post

So what if we do this

x^2 - 3x + 2 = 0
x(x) - 3x + 2 = 0
x(x) = 3x-2
x = (3x-2)/x

So what does this mean?

Well, plug in a random number into your calculator... say 10...
Now do (3x-2)/x, and youll get 2.8...
now (if your using a TI-84 like me), plug in ((3*Ans)-2)/Ans
So Ans = 2.8, this should yield 2.28
Now Ans = 2.28, this should yield 2.125
From 2.125, you get 2.0588...

Basically, If you do this an infinite amount of times, it will converge to 2... which is one of the solutions of the equation...

Now say you rearrange the equation differently...
x^2 -3x+2 = 0
x(x) - 3x + 2 = 0
(x-3)x = -2
x = (-2)/(x-3)

If you do the same method as above, it will converge to 1 for any initial value you put in for x, which is the other zero for the quadratic equation...


So... why am I wasting my time with this?

Well, consider this equation

4x = e^(.5x)

Well... idk how to solve this equation... but what if we do the thing I just did, where we set one side of the equation to x then infinitely compute the other side...

x = e^(.5x)
ln(4x) = .5x
2ln(4x) = x

If you pick 20 for the first x, 2ln(4x) will yield 8.76, then 7.11, then 6.69, and so on, until it converges to a number 6.523371369...

Is this right? well
4(x) = e^(.5x)
4(6.523371369) = e^(.5(6.523371369))
26.09 = e^(3.26)
26.09 = 26.09

So... that's the solution... by using an infinite recursion of setting one side of the equation to x, then we will get some sort of solution...

Now... this doesn't always work... for example, say we did (from the previous equation)

4x = e^(.5x)
x = (e^(.5x))/4

If you do this, then x will converge to infinity. Now you may think that this is wrong... but I feel this is right, since they both technically (intersect) at infinity. In theory, 4(infinity) = e^(infinity)... so is it really wrong? I don't believe so...


Anyway... my theory is that you can solve a solution for an equation when you set the equation to the form of
x = f(x)
Using an infinite recursive calculation.


Now, I really don't know how to dive more into this theory, since I think this involves math that's super crazy (more than I know). I am a computer engineer, so I don't have the biggest arsenal of theoretical math at my disposal. I do know that this might have to do something with damping, since some of the recurrences will have an overdamped, underdamped, and critically damped response to converging to the solution... but... i don't know...



So... any thoughts on this? Any suggestions on how to move forward with this? Or has someone done this before?

And no, this does not have anything to do with homework, this is just fun theoretical stuff I am doing on my own and I would like input/other ideas to help me move forward with this. If this post is deemed by the admins to not belong here, then Ill delete this post (no questions asked) and move it to the Homework Section (or wherever they tell me to put it). All I want is some outside input for this.

I've learned this before what you found is actually called iteration...
the idea is that as you keep on feeding in the values generated by f(x) in x=f(x), you will converge to the solution.

However the sequence won't always converge (i.e it will diverge from the solution). As you might have noticed, there are different ways of isolating x from the equation. But the values will only converge to the solution if |f'(x)|<1 near the solution.

Therefore, you must try different equations of the form x=f(x). Then you find the gradient/slope of f'(x) near the root. If it lies between -1 and 1, it will converge. Also you can modify the equation such that the slope of f(x) near the solution is close to zero; then the iteration will converge more rapidly!
 
  • #9
What does this have to do with Newton's method? It looks to me like the Banach fixed point theorem at work here.
 
  • #10
So, just wanted to make some other interesting points (on the damping point i mentioned in the first post)

So here's the equation [itex]x^2 -4x-9[/itex], with an input of 1.

For the recurrence equation [itex]x = \frac{9+4x}{x}[/itex], here is the plot of number of recurrences (n = 1,2,3) and the value it produces

PFPic1_zpsa1a4b692.png


(its in Excel, I am lazy)

As you can see, there is a damped curve, which is underdamped (I hope I got that right, been a while since I took Circuits for RLC stuff)

Anyway, as n approaches infinity, it reaches one of the zeros for the equation of 5.6ish

Now, if we manipulate the recurrence function to be [itex]x = \frac{9}{x-4}[/itex], here is the plot

PFPic2_zps0f763f22.png


Also underdamped... and gets to the -1.6 zero of the quadratic function



So... how about x = ln(x+3), can we find some overdamped or critically damped?

Well, here is that recurrence function with two different inputs

PFPic3_zps012a922b.png


PFPic4_zps92efa890.png



Im not sure if this is critically damped or overdamped...

I thought this was interesting to note, as (and I am not an expert on damping systems), we could probably describe this in a Second ODE...
 
  • #11
Vargo said:
What does this have to do with Newton's method? It looks to me like the Banach fixed point theorem at work here.

It looked similar to Newton's method- converges on a 'fixed point' in some cases, divergent in others. It also looked similar to several root finding algorithms for the same reason.

Never heard of a fixed point theorem before now, although it sounds like an excellent term for describing several things I've seen through the years.
 

1. What is a recurrence equation?

A recurrence equation is an equation that defines a sequence of numbers or functions where the next term is defined in terms of previous terms. It is often used to describe the relationship between two or more variables in a mathematical model.

2. How do you solve a recurrence equation?

To solve a recurrence equation, you can use several methods such as substitution, iteration, or generating functions. In general, you need to find a closed-form solution that expresses the nth term of the sequence in terms of n and the initial terms of the sequence.

3. What are the applications of recurrence equations?

Recurrence equations have many applications in various fields such as computer science, physics, chemistry, and economics. They are often used to model natural phenomena, analyze algorithms, and solve optimization problems.

4. Can all equations be solved using recurrences?

No, not all equations can be solved using recurrences. Recurrence equations are specifically useful for solving problems that involve repeated processes or have a recursive structure. They may not be applicable to all types of equations.

5. Are there any limitations to using recurrence equations?

Yes, there are some limitations to using recurrence equations. They may not always provide an exact solution and may require additional techniques such as asymptotic analysis. Additionally, they may become computationally expensive for larger values of n.

Similar threads

  • General Math
Replies
13
Views
1K
Replies
7
Views
1K
  • General Math
Replies
4
Views
771
Replies
11
Views
765
  • General Math
Replies
18
Views
2K
  • General Math
Replies
10
Views
2K
  • General Math
Replies
3
Views
1K
  • General Math
Replies
6
Views
1K
Replies
2
Views
127
Back
Top