Question

Write an efficient algorithm to solve a quadratic equation by using the variable tangent method (newton-raphson method)

Answer 1

Algorithm:
Given a continuously differentiable function and an initial approximation x_{0} to the root of f(x)=0, the steps involved in calculating an approximation \xi to the root of f(x)=0 s.t. \ver. are:
(1) Calculate f(x_{0}),f'(x_{0}) and set
(2) For n = 0,1,2... until convergence criteria is satisfied ,do:
Calculat. x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}
Remark (1): This method converges faster than the earlier methods. In fact the method converges at a quadratic rate. We will prove this later.

Remark (2): This method can be derived directly by the Taylor expansion f(x) in the neighbourhood of the root \xi of f(x)=0. The starting approximation x_{0} to \xi is to be properly chosen so that the first order Taylor series approximation of f(x_{0}+h) in the neighbourhood of x_{0} leads to , an improved approximation to \xi. f(x_{0}+h)=f(x_{0})+hf^{'}(x_{0})+\frac{h^{2}}{2}f''(x_{0})+.....=0
\because \qquad h\,\, << \,\, 1, neglecting h^2 and its higher powers, we get f(x_{0})+hf'(x_{0})=0
i.e.
{f(x_{0})}{f'(x_{0})},\qquad \because
h=x_{1}-x_{0}
x_{1}=x_{0}-\{f(x_{0})}{f'(x_{0})}
Now the successive approximations etc may be calculated by the iterative formula x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}
Remark(3) : One may also derive the above iteration formulation starting with the iteration formula for the secant method. In a way this may help one to visualize Newton-Raphson method as an improvement over the secant method. So, let us consider the iteration formula for the secant method i.e.
x_{n+1}=\{f(x_{n})x_{n-1}-f(x_{n-1})x_{n}}{f(x_{n})-f(x_{n-1})}
Add and subtract f(x_{n})x_n to the numerator on the R.H.S. to get
x_{n+1}=x_{n}-/{f(x_{n})(x_{n}-x_{n-1})}{f(x_{n})-f(x_{n-1})}
or, x_{n+1}=x_{n}-\{f(x_{n})}{[f(x_{n})-f(x_{n-1})]/[x_{n}-x_{n-1}]}

Clearly, {f(x_{n})-f(x_{n-1})}{(x_{n}-x_{n-1})}} is the slope of the secant to the curve f(x)=0 through the points (x_{n-1},f(x_{n-1})), (x_{n},f(x_{n})). This also represents slope of the tangent to f(x)=0 parallel to the secant intersecting x-axis between x_{n-1} and x_{n}. If is differentiable one may as well approximate this slope by f'(x_{n}) and thus arrive at the iteration formula.
x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}