Fixed point iteration to find the roots of 0=x-tan(x)

[D H]

Still off course. So let's get back on course. You are trying to find solutions to

x=\tan x

using a fixed point iteration approach. That technique won't work with the above because tan'(x)>=1. Taking the inverse tangent function of both sides doesn't quite work, either, because atan(tan(x)) is only equal to x if x lies in the principal domain of atan.

You have already written x as x=n\pi + \theta. Substituting this on both sides of the above equation yields

n\pi + \theta=\tan(n\pi + \theta) = \tan\theta

By design, \theta\,\in\,(0,\pi/2)\,\forall n>0 In other words, theta is in the principal domain of atan, so you now can take the inverse tangent of both sides of the above. Do that.

 

[Brendy]

Alright, so
atan(n\pi + \theta)= (n\pi +\theta) = \theta
So theta is periodic like the sin or cos functions?

 

[D H]

No. Theta is just a variable here.

You do not know that \arctan(\tan(n\pi+\theta))=n\pi+\theta. In fact, this is not true. The domain of arctan is -pi/2 to pi/2 (at least as implemented in most programming languages). However, you do know that \tan(n\pi+\theta)=\tan\theta due to trig identities.

 

[Brendy]

Ok. Does arctan (tan (\theta))=\theta?
If it does, then arctan (n*pi + \theta)=(\theta). I think I'm going in circles.

 

[D H]

Ok. Does arctan (tan (\theta))=\theta?

It does if theta is in the principal domain of arctan. That was the point of creating that variable: to ensure that it does lie in the principal domain of arctan.

If it does, then arctan (n*pi + \theta)=(\theta). I think I'm going in circles.

Yes, you are. So, one step at a time.

1. You want to find the positive solutions to x=\tan x.
2. This is in the right form for fixed point iteration, but a fixed point iteration using the above will not converge.
3. Taking the inverse tangent of both sides doesn't help immediately because all solutions but the trivial solution lie outside the principal domain of arctan.
4. So, introduce a new variable that will be in the principal domain: x\equiv n\pi+\theta.
5. Now the problem becomes one of solving n\pi+\theta = \tan(n\pi+\theta).
6. The right hand side of the above, \tan(n\pi+\theta), reduces to \tan\theta via the trig identity \tan(a+b) = (\tan a + \tan b)/(1-\tan a \tan b).
7. Now the problem becomes one of solving n\pi+\theta = \tan\theta.
8. And now you can safely apply the arc tangent function to both sides because, by design, theta is in the principal domain of arctan.

Try to take it from here.

 

[Brendy]

Isn't that what I wrote above? arctan (n\pi+\theta) = \theta\<br />

 

[D H]

Fine. Can you take it forward from post#35?

 

[Brendy]

I thought that was taking it forward? I'm sorry, I really don't know what I'm after in this question.
My first instinct is to get everything in terms of x which would mean that arctan(x) = theta but I see that I did that a few posts ago but that was going off course and it doesn't really get me anywhere.

 

[D H]

You seem to have lost sight of the goal of this problem, which is to find an equation of the form x=f(x) than can be used in a fixed point iteration scheme. You need f(x) to involve arctan, not tangent.

This isn't that hard. Look at step 7 in post number 35.

 

[Brendy]

Right.
arctan (x) = x - n\pi\
so,
x = arctan (x) + n\pi\

This actually looks correct for once.

 

[D H]

That's not right. Forget about x! You need to solve for theta.

 

[Brendy]

arctan <br /> (n\pi+\theta) = \theta\<br /> <br />
That's as far as I can get in solving it. I'm not sure how to proceed from there.

 

[D H]

You're there. If you don't see it, just exchange the left and right hand sides. (use the fact that if a=b then b=a).

 

[Brendy]

<br /> \theta\ = arctan (n\pi+\theta) <br /> <br />
So that's it? Do I try and get everything in terms of x now or is this what the algorithm will use?

 

[D H]

That's it. You will solve for x at the very end.

 

[Brendy]

Do you mean at the end of running the algorithm? Also, when I solve for x, the x represents the roots, right? Not just another initial guess? Or do I use what I find x to be as the next initial guess?

 

[D H]

You use a different value for n to find the next root. It doesn't really matter what you use for an initial guess, so long as it is somewhere between 0 and pi/2, exclusive of the end points.

That said, it's not too hard to form a very good guess. The solution for theta will be close to pi/2 (very close for large n). Writing the solution for some particular n as \theta_n,

\theta_n = \frac{\pi}2 - \epsilon_n

Thus \tan\theta_n = 1/\tan\epsilon_n \approx 1/\epsilon_n if \epsilon_n is small (which it will be).

See if you can take it from here. Or just use some value between 0 and pi/2 as your initial guess.

 

[Brendy]

Thanks a lot, you've been a massive help.
One last thing, what are f_old and f_new doing in my code? After I edit the line x_new... to the expression for theta, it will converge on a root but I'm not sure what those two lines after that mean. Are they needed?
Also, is it supposed to converge so quickly? At the moment, it converges on the first root within 5 iterations with 1 as an initial guess.

 

[D H]

You wrote that code; you are the one who should know what it is doing. You will of course have to rewrite your code to use this new formula.

Last thing: I wouldn't bother with the trivial solution. You know that solution, and a fixed point iteration scheme isn't really valid for finding the trivial solution because it sits right at a point where tan'(x)=atan'(x)=1. The derivative has to be strictly less than one for a fixed point iteration to converge.

 

[Brendy]

I didn't write the code. I modified an existing program that was solving x_n+1 = e^-x_n
Which solution are you referring to? Even changing the initial guess to something further away from the root such as 0.5 sees it converging within 6 iterations.

 

[D H]

That algorithm doesn't converge. I just took your code from post #17; it stopped after 50 iterations because it failed to converge.

Look at it this way: \tan x \approx x(1 - x^2/3) for small x. All setting x=\arctan(x) does when x gets even close to zero is to scale x by a factor that is nearly equal to 1.

 

[Brendy]

After rewriting it so that x_new... line is now x_new= atan (pi + x_old) it converged within 6 iterations. So is that just a fluke then? It is giving me the correct number to find the roots though.
I don't follow post #51 at all I'm sorry.