BISECTION METHOD:

The bisection method in mathematics is a root finding method that repeatedly bisects an interval and then selects a sub interval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods. The method is also called the interval halving method,the binary search method, or the dichotomy method

The method:

The method is applicable for numerically solving the equation f(x) = 0 for the real variable x, where f is a continuous function defined on an interval [a, b] and where f(a) and f(b) have opposite signs. In this case a and b are said to bracket a root since, by the intermediate value theorem the continuous function f must have at least one root in the interval (a, b).

At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now only two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(b) have opposite signs and bracket a root.The method selects the sub-interval that is guaranteed to be a bracket as the new interval to be used in the next step. In this way an interval that contains a zero of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

Explicitly, if f(a) and f(c) have opposite signs, then the method sets c as the new value for b, and if f(b) and f(c) have opposite signs then the method sets c as the new a. (If f(c)=0 then c may be taken as the solution and the process stops.) In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval.

Iteration tasks:

The input for the method is a continuous function f, an interval [a, b], and the function values f(a) and f(b). The function values are of opposite sign (there is at least one zero crossing within the interval). Each iteration performs these steps:

Calculate c, the midpoint of the interval, c = a + b/2.
Calculate the function value at the midpoint, f(c).
If convergence is satisfactory (that is, a – c is sufficiently small, or f(c) is sufficiently small), return c and stop iterating.
Examine the sign of f(c) and replace either (a, f(a)) or (b, f(b)) with (c, f(c)) so that there is a zero crossing within the new interval.

When implementing the method on a computer, there can be problems with finite precision, so there are often additional convergence tests or limits to the number of iterations. Although f is continuous, finite precision may preclude a function value ever being zero. For example, consider $f (x) = x - π$ ; there will never be a finite representation of x that gives zero. Additionally, the difference between “a” and “b” is limited by the floating point precision, i.e., as the difference between “a” and “b” decrease, at some point the midpoint of [“a”, “b”] will be numerically identical to (within floating point precision of) either “a” or “b”.

NEWTON METHOD:

Newton method is a method for finding successively better approximations to the roots (or zeroes) of a real-valued funtion

x:f(x)=0\,.

The Newton–Raphson method in one variable is implemented as follows:

The method starts with a function $f$ defined over the real numbers $x$ , the function’s derivative $f '$ , and an initial guess $x 0$ for a root of the function $f$ . If the function satisfies the assumptions made in the derivation of the formula and the initial guess is close, then a better approximation $x 1$ is

x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,.

Geometrically, $(x 1, 0)$ is the intersection of the $x$ -axis and the tangent of the graph of $f$ at $(x 0, f (x 0))$ .

The process is repeated as

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,$

till we get desired result.

Suppose $f : [a, b] \to ℝ$ is a differentiable function defined on the interval $[a, b]$ with values in the real numbers $ℝ$ . The formula for converging on the root can be easily derived. Suppose we have some current approximation $x n$ . Then we can derive the formula for a better approximation, $x n + 1$ by referring to the diagram on the right. The equation of the tangent line to the curve $y = f (x)$ at the point $x = x n$ is

y=f'(x_{n})\,(x-x_{n})+f(x_{n}),

where $f'$ denotes the derivative of the function $f$ .

The $x$ -intercept of this line (the value of $x$ such that $y = 0$ ) is then used as the next approximation to the root, $x n + 1$ . In other words, setting $y$ to zero and $x$ to $x n + 1$ gives

0=f'(x_{n})\,(x_{n+1}-x_{n})+f(x_{n}).

Solving for $x n + 1$ gives

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.

SECANT METHOD:

The secant method is defined by the recurrance relation

x_{n}=x_{n-1}-f(x_{n-1}){\frac {x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}}={\frac {x_{n-2}f(x_{n-1})-x_{n-1}f(x_{n-2})}{f(x_{n-1})-f(x_{n-2})}}

As can be seen from the recurrence relation, the secant method requires two initial values, x₀ and x₁, which should ideally be chosen to lie close to the root.

Derivation of the method

Starting with initial values $x 0$ and $x 1$ , we construct a line through the points $(x 0, f (x 0))$ and $(x 1, f (x 1))$ , as demonstrated in the picture on the right. In slope-intercept form, this line has the equation

y={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{1})+f(x_{1})

We find the root of this line – the value of $x$ such that $y = 0$ – by solving the following equation for $x$ :

0={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{1})+f(x_{1})

The solution is

x=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}

We then use this new value of $x$ as $x 2$ and repeat the process using $x 1$ and $x 2$ instead of $x 0$ and $x 1$ . We continue this process, solving for $x 3$ , $x 4$ , etc., until we reach a sufficiently high level of precision (a sufficiently small difference between $x n$ and $x n - 1$ ).

x_{2}=x_{1}-f(x_{1}){\frac {x_{1}-x_{0}}{f(x_{1})-f(x_{0})}}

x_{3}=x_{2}-f(x_{2}){\frac {x_{2}-x_{1}}{f(x_{2})-f(x_{1})}}