# Approximate solution for the root of a non-linear function

I have been working with a system which involves computing the roots of functions that look like

$$e^t (g\cos(\omega t) + b) = c$$

where $t$ is the independent variable and the parameters $g$, $\omega$ and $b$ are real and positive and $c$ is real.

This, apparently has no analytical solution and I have been doing it in the computer easily. However, for some parts of my research it would be very useful to have some approx. solution. For instance, in the form of a series where successive approx. may be computed. However, I have no idea how to even start. Would anyone Have some guidelines as to how to approach this problem?

Thanks very much in advance.

Edit:

So, the full problem is as follows. Suppose we start with some value $t_0$. Then we want the first root of $$e^{t_1} (g\cos(\omega t_1) + b) = e^{t_0} (g\cos(\omega t_0) + b)$$

ie, the value of $t_1$ that satisfies this equation and is closer to $t_0$. Note that the RHS is simply the number which I previously called $c$. With $t_1$, the next step is to compute $t_2$ from the equation

$$e^{t_2} (g\cos(\omega t_2) - b) = e^{t_1} (g\cos(\omega t_1) - b)$$ (note the sign change in $b$).

This is the framework of my current problem: find successive roots $t_i$ with the sign in $b$ alternating between each computation.

The questions that arise are: for what values of $t_0$ are there roots and are there infinitely many? For instance, if $\omega=3$, $b=0.8$ and $g=1.75$ then $t_0 = 0.174765$ is unstable. It yields roughly $20$ roots and then stop.

## Update

Thank you all for the support. As for the instability (cf. @LeonidKovalev's answer), here is an example:

This is for $\omega = 3$, $g= 1.75$ and $b = 0.8$. This shows that as time progresses the crossing times begin to grow so that after some time there is no longer a root. Perhaps, and this is a mistake which I apologise for, this instability is brought about by the fact that I am solving a slightly different system in which $\cos\omega t$ is replaced by $\cos(\omega t-\phi)$, with $\phi = \text{atan}(\omega)$ (I thought this would go away by rescaling $t$ appropriately).

-
If you just write out a function name like cos, $\TeX$ interprets it as a sequence of variable names, which it italicizes. To get the right formatting, you need to use the predefined commands such as \cos. If you need a function name for which there's no predefined command, you can use \operatorname{name}. –  joriki Jul 17 '12 at 13:38
You could write out the Taylor series for $\exp t$ and $\cos \omega t$, carry out the multiplication, and truncate after any $t^4$ powers. This will give you an (ugly, and probably not terribly accurate) closed form solution. If you go to orders higher than 4, you run into general unsolvability of polynomials of order $\ge 5$. –  Arkamis Jul 17 '12 at 13:48
"Note that the RHS is simply a positive number" -- why is that? $g\cos (\omega t_0)+b$ could be negative for all I know. –  user31373 Jul 18 '12 at 16:28
Oh my! I am sorry Leonid, you are right. My mistake. The RHS may be both pos. and neg. I will correct that in the question. –  Gabriel Landi Jul 18 '12 at 19:29
Newton's method comes to mind -- in the form of a series and you have ac losed form of the derivative, so can explicitly make the formula for the next iteration. –  gt6989b Jul 20 '12 at 16:28

## 4 Answers

(New answer)

Some of this overlaps with the answer by Jayesh Badwaik, but it does not hurt to see two people's perspective.

Concerning the sequence $t_k$, let's begin with a simple observation based on Rolle's theorem: there exists $t$ strictly between $t_k$ and $t_{k+1}$ where the derivative of $e^t(g\cos\omega t\pm b)$ vanishes. This means $g\cos\omega t-g\omega \sin\omega t\pm b=0$. If $g\sqrt{1+\omega^2}\le b$, the derivative never changes its sign; therefore in this case you don't even have $t_1$. If $g\sqrt{1+\omega^2}> b$, there are infinitely many solutions which form a periodic pattern. This does not tell us that the sequence $t_k$ is infinite, but if it is infinite, then it grows at least linearly: $t_k\ge Ak+B$.

When $g>b$, the function $e^t(g\cos\omega t\pm b)$ is oscillating with increasing amplitude, roughly between $\pm g e^t$. It is not hard to see that in this case there is always $t_{k+1} \in (t_k, t_k+2\pi/\omega]$. So, the sequence $t_k$ is infinite and it grows at linear rate. Notice that this contradicts your observation that the sequence stops with $b=0.8$ and $g=1.75$. I suspect that you ran into overflow issues due to the exponential growth of the function.

The case $g=b$ is about the same as $g>b$: here the function does not change sign, but it returns to zero infinitely often. The sequence $t_k$ is infinite and grows at linear rate.

In the interval $g< b< g\sqrt{1+\omega^2}$ the elementary observations above do not suffice.

Let's step back from the case-by-case analysis and try to see more structure. Let $F(t)=e^t(g\cos\omega t+ b)$. The equation $F(t_{k+1})=F(t_k)$ is invariant under adding an integer multiple of $2\pi/\omega$ to both $t_k,t_{k+1}$. So, we can choose the starting point $t_0$ to be in an interval of length $2\pi/\omega$ of our choice: it appears to be convenient to take the interval between two consecutive local minima of $F$. We can also choose to subtract a multiple of $2\pi/\omega$ from subsequent points $t_k$ to avoid the exponential growth and associated numerical issues.

On every other step you want to solve a modified equation with $-b$ in place of $b$: namely, $e^{t_{k+1}} (g\cos(\omega t_{k+1}) - b) = e^{t_k} (g\cos(\omega t_k) - b)$. But this equation can be put in terms of the same function $F$ as follows: $F(t_{k+1}-\pi/\omega)=F(t_k-\pi/\omega)$. I could as well use $+\pi/\omega$ since the integer multiples of $2\pi/\omega$ do not matter. But it seems advisable to jump to the left rather than to the right, to keep the sequence from growing. Here is the algorithm:

1. Start with $s_0$.
2. Find the smallest $s_{k+1}>s_{k}$ such that $F(s_{k+1})=F(s_k)$. If there is no solution, stop.
3. Replace $s_{k+1}$ with $s_{k+1}-\pi/\omega$.
4. Increment $k$ and return to step 2.

This process continues for as long as the original process with $t_k$, and $s_k$ agrees with $t_k$ up to an integer multiple of $\pi/\omega$.

This algorithm can be useful not just for computations, but also for understanding of what can happen. For example, if $F(s)=F(s+\pi/\omega)$, and this common value of $F$ does not occur in between, then starting with $s_0=s$ we get $s_1=s_2=\dots=s$, and the process goes on forever. Here is a concrete example: $f=e^t(\cos 3t+2)$; the starting point is $(1/3)\cos^{-1}(2(e^{\pi/3}-1)/(e^{\pi/3}+1))$. This example shows that infinite process is possible even if $g<b$.

You can get more information by following the algorithm yourself with a printout of the graph of $F$. From the starting point, draw horizontal line to the right until it crosses the graph again (if it does not, the game is over). Then move the point $\pi/\omega$ to the left, adjust the vertical coordinate so that it lies on the graph of $F$, and repeat. After a few tries you should get a pretty good idea of how this dynamical system behaves.

(Old answer)

First of all, you can divide both sides by c. So let's assume this was done, and our equation is $g\cos\omega t+b = \exp(-t)$. This means we are looking for intersections between the exponential curve and a cosine wave. In general, there may be many intersections, in fact there are infinitely many when $g>b$. Are all of these solutions relevant to your task, or is there a preferred one?

If $g<b$, we have an upper and lower bounds for solutions, namely $-\log(b\pm g)$. The number $-\log b$ looks like a good starting point for Newton's method, which can indeed be written in the form of a series.

I might be able to say more if you can clarify a) what to do with nonunique solutions, and b) if you know anything about the relative size of the constants involved. For example, is b much larger than g? Etc.

-
Hi, I really appreciate the answer. So: only the first root is of interest. The parameters are all positive and have the following usual ranges: $0<b<2$, $0<g<10$ and $0<\omega<10$. This is approximate, but shows they are not very different from one another. I will edit the question to post a slightly more general panorama of the question. –  Gabriel Landi Jul 18 '12 at 14:32

Let

$$y \left( x \right) = \exp( t )\left( g \cos \left ( \omega t \right) + b \right)$$

For $\omega \ll 1$, I don't know if next solution will exist or not. The next solution will only exist if the slope of the function is negative at that point.

CASE 1 : $b < g\sqrt{\omega^{2} + 1} \text{ and } \frac{\omega}{t} \gg 1$

Then, let

$$\frac{dy}{dt} = y - \exp(t)\left(g \omega \sin\left(\omega t \right) \right)$$

Solving for $\frac{dy}{dt} = 0$

$$\exp( t )\left( g \cos \left ( \omega t \right) + b \right) - \exp(t)\left(g \omega \sin\left(\omega t \right) \right) = 0$$

And reducing it,

$$\omega \sin \left( \omega t \right) - \cos\left( \omega t \right) = \frac{b}{g}$$

which implies

$$\sin\left(\omega t + \phi \right) = \frac{b}{g\sqrt{\omega^{2} + 1}} = K$$

where $\phi = atan\left( \frac{-1}{\omega}\right)$ and hence, the requirement for $b < g\sqrt{\omega^{2} + 1}$.

Hence,

$$t_{en} = \frac{asin(K) - \phi + 2n\pi}{\omega}$$

So, now you have maxima and minima. So, now the next value of your variable lies either between the two minima or two maxima, depending on whether the slope is positive or negative at that point. So, suppose, your $t$ is $\theta$ after the extrema. Then, the next value would be $\theta$ before the next same extrema (if $t_{1}$ was $\theta$ after a minima, then $t_{2}$ would be $\theta$ before the next minima), approximately.

$\theta = \omega t - 2\pi m$ where $m = \lfloor\frac{\omega t}{2\pi}\rfloor$

and then

$$t_{2} = t_{1} + \frac{2\pi - \theta}{\omega}$$

This was the easiest way to calculate approximate formula. But I doubt, it is much useful if you want to apply further analytical tools mainly because of floor function.

CASE 2 : for $b > g\sqrt{\omega^{2} + 1}$

I am hoping one can apply a similar procedure using some sort of transformation and back, I am not sure though. Will try to get back to you on it.

-

Taking Leonid's $c=1$ I would try to divide this problem into two regimes.

$\omega >1$ and fast oscillations. If $g+b <1$ then the intersection will happen at the peak of the oscillation and we can approximate as $g+b = e^{-t}$ and solve for $t$. To do better, perturb around this solution. If $g+b >1$ then the solution would be at $g \cos \omega t + b \sim 1$.

$\omega <1$ and slow oscillations. If $g+b <1$ then the cosine is nearly fixed and one solves $g+b = e^{-t}$. If $g+b >1$ the intersection happens near $t=\pi/2$.

The only region where it will be hard to get an approximation will be the $\omega \sim 1$ regime. One could divide things into quadrants and make conditions on which phase of $\omega t$ the intersection is likely to happen. This is work, might be faster to use your non-linear root finding solutions for the transition region, plot it and fit something to the solution (a quick polynomial for example).

-

Dividing by $g$, we may assume that $g=1$. I will consider then the equation $$e^t(\cos(\omega\,t)+b)=c,\quad \omega>0,\quad b>0,\quad c\in\mathbb{R}.$$ Case 1: $b>1$. Then $0<b-1\le\cos(\omega\,t)+b\le1+b$ for all $t$. There are no solutions if $c\le0$. If $c>0$ there is a finite number of solutions in the interval $\Bigl[\dfrac{\log c}{b-1},\dfrac{\log c}{1+b}\Bigr]$.

Case 2: $b=1$. Then $0\le\cos(\omega\,t)+1\le2$ for all $t$. There are no solutions if $c<0$. If $c=0$ there are infinitely many solutions, given by $t=\dfrac{(2\,k+1)\pi}{\omega}$, $k\in\mathbb{Z}$. If $c>0$ there are two solutions on each interval $\Bigl(\dfrac{(2\,k-1)\pi}{\omega},\dfrac{(2\,k+1)\pi}{\omega}\Bigr)$ with $k\ge\dfrac{\omega}{2\,\pi}\log\dfrac{c}{2}$ (only one if equality holds).

Case 3: $0<b<1$. Then $\cos(\omega\,t)+b$ takes both positive and negative values. There are infinitely many solutions for all $c\in\mathbb{R}$. Let $\beta\in(0,\pi/(2\,\omega))$ be such that $\cos(\omega\,\beta)=b$. If $c=0$, then the solutions are $\pm\,\beta+2\,k\,\pi$, $k\in\mathbb{Z}$. If $c>0$ the solutions lie in intervals $\Bigl(-\beta+\dfrac{2\,k\,\pi}{\omega},\beta+\dfrac{2\,k\,\pi}{\omega}\Bigr)$ with $k\ge\dfrac{\omega}{2\,\pi}\log\dfrac{c}{1+b}$. If $c<0$, then the solutions lie in the intervals $\Bigl(\beta+\dfrac{2\,k\,\pi}{\omega},-\beta+\dfrac{2(k+1)\pi}{\omega}\Bigr)$ with $2\,k+1\ge\dfrac{\omega}{\pi}\log\dfrac{|c|}{1-b}$.

Edit

In the above, I have made the error of assuming that the maxima and minima of $e^t(\cos(\omega\,t)+b)$ are attained at points where $\cos(\omega\,t)=\pm1$. The correct statement for Case 2 ($b=1$) when $c>0$ should be:

Let $M_k$ be the maximum of $e^t(\cos(\omega\,t)+b)$ on the interval $\Bigl[\dfrac{(2\,k-1)\pi}{\omega},\dfrac{(2\,k+1)\pi}{\omega}\Bigr]$. Then there are two solutions on $\Bigl(\dfrac{(2\,k-1)\pi}{\omega},\dfrac{(2\,k+1)\pi}{\omega}\Bigr)$ for all $k$ such that $M_k\ge c$ (only one if equality holds).

Case 3 has to be changed in a similar way.

-