Iterative approaches to the solution of nonlinear equations $f(x) = 0$

I am currently studying for a midterm, and I am review over the following methods:

• Fixed point method
• Bisection method
• Regula Falsi method
• Newton-Raphson
• Accelerated Newton-Raphson
• Secant

I know how to use the methods, however I am more concerned with when to use them. I've been asked several times in the book if a method can be used with an equation, but I just can't seem to come up an answer.

Example: $1$. Let $g(x) = x^2+x-4$. Can fixed-point iteration be used to find the solution(s) to the equation $x=g(x)$ ? Why?

Example: $2$. Can Newton-Raphson iteration be used to solve $f(x) = 0$ if $f(x) = x^{1/3}$ ? Why?

Also No.

Can someone quickly summarize when it is appropriate to use a method and when it is not?

Much appreciated!

-
The problem with your cube root example is that the tangent is vertical at where your root is. More specifically, your derivative there is infinite, and since NR requires the evaluation of a derivative... – J. M. Oct 19 '11 at 6:24
...and I'm not entirely sure what "accelerated" NR means; there are quite a number of ways to accelerate NR when the convergence rate isn't quadratic, but I have no way of knowing which of those methods are you referring to... – J. M. Oct 19 '11 at 6:25

...I am more concerned with when to use them...

This might not apply much to you, seeing that you're doing this in the classroom and you aren't wrestling with a problem encountered in the wild, but:

• use Newton-Raphson when you have a good starting point and are able and willing to compute derivatives

• use the secant method when you have good starting point*s* and are unable or unwilling to compute derivatives

• use bisection if your function is not very "well-behaved", you have a bracket on your root (that is, you have an interval $(a,b)$ such that $f(a)f(b) < 0$), and you can tolerate the slow convergence.

(I haven't seen a problem in practice that demanded the use of false position, FWIW.)

One obtains a good starting point either by exploiting the special properties of the equation at hand, or by studying the graph of the function (which I always tell people to do first and foremost before siccing your fancy iterative method on your equation).

In some circumstances, you will encounter library routines that interleave secant/NR with bisection, such that you get the best of both worlds. As might be expected, such polyalgorithms (like this one due to Brent) are a bit more elaborate...

-

First question: We look at the equation $x=g(x)=x^2+x-4$. The solutions are $x=\pm 2$. If we are phenomenally lucky, and, say, make the initial estimate $x=2$, everything is fine. Now let's see what happens if we make an initial estimate which is good but not dead on. Say we are using fixed point iteration to estimate the positive root $x=2$.

The problem is that $x=2$ is a repelling fixed point. The reason it is repelling is that $g'(x)=2x+1$, so near $x=2$, $|g'(x)|$ is near $5$, quite a bit greater than $1$.

Roughly speaking, if we are dealing with a "nice" function, and the derivative at the root has absolute value substantially less than $1$, the root will be an attracting fixed point. In that case, if we start close enough to the root, fixed point iteration sucks us into the root. But if the absolute value of the derivative is greater than $1$, we are driven away from the root.

One can draw a very nice picture of the process, and see the repulsion at work. In the absence of a picture, we will use a formula. Note that $g(2)=2$. Let $x$ be near $2$ but not equal to $2$. We have $$\frac{g(x)-2}{x-2}=\frac{g(x)-g(2)}{x-2}\approx g'(2)=5.$$ Thus if $x$ is "near" $2$, then $$g(x)-2\approx 5(x-2).$$ This means that $g(x)$ is about $5$ times as far from $2$ as $x$ is from $2$.

If we have a good estimate $x_n$ for the positive root, then $x_{n+1}$, the next estimate, is $g(x_n)$, and thus $x_{n+1}$ is about $5$ times further away from the root than $x_n$ was.

The same issue arises at the negative root $x=-2$. We have $g'(-2)=-3$, so the derivative has absolute value $3$. Again, $x=-2$ is a repelling fixed point.

Second question: For the Newton-Raphson process question, the root is of course $0$. The problem is that the derivative of $x^{1/3}$ blows up as we approach the root. In a sense, the issue is somewhat similar to the one in the first question, since Newton-Raphson can be thought of as a sophisticated form of fixed point iteration. We are doing fixed point iteration to solve $g(x)=x$, where $g(x)=x-\frac{f(x)}{f'(x)}$.

For Newton-Raphson for $f(x)=0$, here is a rough use guideline. It should behave fairly nicely if (i) we start close enough to the root and (ii) $f(x)$ is twice differentiable at and near the root and (ii) $f'(x)$ is not $0$ at the root. There is another possible issue. If the root is a multiple root (silly example $f(x)=x^4$) then the convergence will be slow.

For the particular example in the question, we can compute explicitly and see very clearly what happens.

Recall that the Newton-Raphson iteration for approximating solutions of $f(x)=0$ is given by $$x_{n+1}=x_n -\frac{f(x_n)}{f'(x_n)}.$$

Let $f(x)=x^{1/3}$. then, at least for positive $x$, we have $f'(x)=-(1/3)x^{-4/3}$. Substitute in the Newton-Raphson iteration. After some simplification, we obtain $$x_{n+1}=4x_n.$$ Very bad news! Even if we are "lucky" enough to start with a good approximation $x_0$ to the root, say $x_0=1/1000$, after one iteration we will be $4$ times as far away from the truth, after two iterations we will be $16$ times as far away from the truth, and so on.

-

ok, the first thing you have to keep in mind is that this is "Numerical methods". :) why I say this is, we cannot make sharp margins since we are always working with an error.

so one reason for your question is that the ability of finding a root depends on your initial guessed value. The convergence is not assured in open methods but you will get an answer sooner or later in a bracketing method where you are sure about a root inside the bracket.

Bisection method and False position method are bracketing methods from the above list.So if you find an interval where a root lies, you are assured to obtain the root someday.^^ The number of iterations needed depends on the shape of the curve in the given region.

but the problem is worse with open methods. You will never get the desired root if the graph tends to diverge. So my advice is to have a rough graphical sketch of the graph before going to the initial approximation.

The good thing about open methods over bracketing methods is that they are far efficient.

-
"we cannot make sharp margins" - I'm not sure what you intended to say with this, but it is not necessarily true that one cannot give sharp error bounds on the result of a numerical method. – J. M. Oct 19 '11 at 7:21
Your statement about bracketing methods could use a bit more precision: there is a guarantee of convergence only when the function values at the endpoints are of different sign. – J. M. Oct 19 '11 at 7:24
no ..no.. I was not referring to the value of the error.what I wanted to imply was the difference of two approaches used in numerical methods and rigorous analytical answers. – Tharindu Rusira Oct 19 '11 at 7:25
and it's totally true that we need to have apposite signs of values.I thought it was so obvious to a numerical methods student but it's good you mentioned that if it's not the case – Tharindu Rusira Oct 19 '11 at 7:30

First question: We look at the equation $x=g(x)=x^2+x−4$. The solutions are $x=±2.$

Thats wrong. The quadratic formula gives $x = \frac{-1\pm\sqrt{17}}{2}$. As to whether we can use fixed-point iteration for solution, we definitely can.

Rearrange $x^2+x-4=0$ into $x = \pm\sqrt{4-x}\equiv g_{\pm}(x)$. Iterations with $x_{n+1}=g_+(x_n)$ will give you the first root and iterations with $x_{n+1}=g_-(x_n)$ will give you the second root.

-
The equation to solve is not $g(x) = 0$, it's $x = g(x)$. – Robert Israel Oct 25 '11 at 22:26