What would be the $g(x)$ of fixed point iteration method for the equation $f(x)=x\sin(x)+\cos(x)=0$ which satisfies the condition $|g'(x)| < 1?$

Question

I've tried finding the $g(x)$ for the equation $f(x)=x\sin(x)+\cos(x)=0$ by squaring or multiplying, but nothing seems to fulfil the condition of $|g'(x)|<1.$

Answer 1

The goal is to find an approximate root of $$x \sin x + \cos x = 0$$ by fixed-point iteration. An equivalent equation is $$\tan x = - \frac{1}{x} \tag{1}$$ Now we must ask "Which root?" because it becomes evident there are infinitely many roots. Plotting $\tan x$ and $-1/x$, it appears that one root is near $2.8$; so let's assume that is the root we want to find.

At first, we might try taking the inverse tangent of both sides of $(1)$: $$ x = - \tan^{-1} \left( \frac{1}{x} \right) \tag{2}$$ But the range of the principal value of $\tan^{-1} x$ is defined to be $-\pi/2$ to $\pi/2$, which does not include $2.8$, so $(2)$ won't work. Instead, we need the alternative branch of $\tan^{-1} x$ with range from $\pi/2$ to $3 \pi/2$, i.e. the principal value plus $\pi$, yielding $$ x = - \tan^{-1} \left( \frac{1}{x} \right) + \pi \tag{3}$$ If we define $g(x)$ to be the right-hand side of $(3)$,then it turns out $|g'(x)| < 1$ for $x$ near $2.8$, so fixed-point iteration will converge to a root.

Answer 2

You get the "easy" function values $$f(k\pi)=(-1)^k~~\text{ and }~~f((k+\frac12)\pi))=(-1)^k(k+\frac12)\pi).$$ This means that there is a root between $(k-\frac12)\pi$ and $k\pi$ for every positive integer $k$. You need to show that these are the only roots, for instance by exploring the monotonicity intervals.

$f$ is a symmetric function, so that for every positive root you also get a negative root.

Fix some positive integer $k$ and set $x_k^0=k\pi$. With $A_k=f'(x_k^0)=(-1)^kx_k^0$, the simplified Newton method $$ x_k^{n+1}=g(x_k^n)=x_k^n-A_k^{-1}f(x_k^n) $$ has good chances to converge to the root closest to $x_k^0$ and $x_k^1=x_k^0-\frac1{x_k^0}=k\pi-\frac{1}{k\pi}$.

The numerical experiment

k = np.arange(1,10)
x = k*np.pi
A = x*np.cos(x);
def f(x): return x*np.sin(x)+np.cos(x)
for j in range(6):
    print j,x 
    x = x - f(x)/A

confirms the good behavior.

n     x1[n]       x2[n]       x3[n]       x4[n]      x5[n]       x6[n]         x7[n]       x8[n]       x9[n]

0 [ 3.14159265  6.28318531  9.42477796 12.56637061 15.70796327 18.84955592  21.99114858 25.13274123 28.27433388]
1 [ 2.82328277  6.12403036  9.31867467 12.48679314 15.64430129 18.79650427  21.94567573 25.09295249 28.23896612]
2 [ 2.80221509  6.12135633  9.31788012 12.48645761 15.64412942 18.79640479  21.94561307 25.09291051 28.23893663]
3 [ 2.79899888  6.12125454  9.31786669 12.48645443 15.64412838 18.79640437  21.94561288 25.09291041 28.23893658]
4 [ 2.79848472  6.12125062  9.31786647 12.4864544  15.64412837 18.79640437  21.94561288 25.09291041 28.23893658]
5 [ 2.79840195  6.12125047  9.31786646 12.4864544  15.64412837 18.79640437  21.94561288 25.09291041 28.23893658]

---

See also Selection of the numerical method for other approaches to a similar problem.