Numerical Methods: Convergence and Root Finding Analysis

This assignment delves into the realm of numerical analysis, focusing on the investigation of convergence and the determination of roots for polynomial equations. The student's work encompasses an analysis of error convergence, visualized through plots illustrating the relationship between error and iteration steps for various polynomials. The assignment also explores the Newton-Raphson method, a technique for finding roots, and its modification for identifying multiple roots. The student provides the root values obtained using Python code, along with the initial guesses (x0) used. A critical component of the assignment is the Python code itself, which is thoroughly commented to explain each line's functionality, and the code is structured to align with the different sections of the project. The assignment also includes references to relevant literature in the field of numerical analysis.

Investigating convergence
Figure 1:Error vs iterations
The figure above shows error in each step ofcalculating root ofthe function.
The error is measured as a difference with respect to the known root of a ev-
ery function.As each function has root equalto 2, the error is formulated as
E = |2 − x|. E1 indicates error in calculation ofroot of function f (x),E2
indicates the error in calculation of root of function g(x) and so on.This error
is being calculated at each step in the program and plotted against the step
number (iteration), and the resulting plot is plot in figure-1 where all the error
plots are super-imposed.
Where the error plots meet the 0 line:horizontalline y = 0,we can say that
the error is almost diminished and root is achieved.As can be seen from the
figure, lower degree polynomials f (x) and g(x) with error E1 and E2 meet this
line in no time,in less than 10 iterations.Which higher degree polynomials
h(x) and onward,with error E3,E4 and E5, take a longer time to meet the
0 line, around 20 to 70 iteration.We can therefore conclude that lower degree
polynomials converge more rapidly compared to higher degree polynomials.
1

Finding Multiple roots:
The regular Newton Raphson method (used for the problem above), converges
rapidly to a single root.But for polynomials with multiple roots,this method
is limited as it always finds that single root.
Method needs to be modified slightly in order to compute allthe roots ofa
higher degree polynomial.Idea for it is explained below:
f(x) = P n (x)
is a higher (n ≥ 2) degree polynomialwith multiple roots for its equation.
Factorize it:
f (x) = (x − r1)(x − r2) (x − r3) . . . (x − rn )
r1, r2, . . . , rn are the roots.
Newton-Raphson method will find a single root say r1.
Define a new polynomial as:
g(x) = f (x)
(x − r1)
The next root of f (x) is obtained by using the Newton-Raphson method on this
modified polynomial:
xr 2 = x − g(x)
g0(x)
There generalized formula for finding nth root of f (x) can be found in [3].It is:
xn = xn − f (x)
f 0(x) − f (x)P k−1
i=1 (xn − xi )
The way this method is initialized is as follows:
Start with a initial guess x0 and use the regular Newton-Raphson method.This
will result in a root (single) of f (x).At this point we will be using the modified
N-R method to find the next root.We need to re-initialize the method as we
cannot continue with the previous value ofx, which was a root (first root),
otherwise we willbe stuck in an infinite loop.Re-initialize at this point and
obtain the second root using the modified method.And then for the third root
we again need to re-initialize and so on.
The algorithm to obtain multiple roots with is method is demonstrated in figure
below [3].
2

Results from python code:
root number x0 root value
1 10 0.9659258263205169
2 10 -0.9659258262891601
3 10 0.7071067812895969
4 10 -0.2588190451025142
5 10 0.2588190451322682
6 10 -0.7071067811865477
References:
[1]E. Cheney,NumericalMathematics and Computing,Brooks Cole,6th edi-
tion, 2010.
[2] J. Stoer, Introduction to Numerical Analysis, Springer, 3rd edition, 2012.
[3] V. Barrera-Figueroa, ‘Multiple root finder algorithm for Legendre and Cheby-
shev polynomials via Newton’s method ’.Annales Mathematicae et Informati-
cae.33. pp. 3–13.
Available:http://www.kurims.kyoto-u.ac.jp/EMIS/journals/AMI/2006/barrera.pdf
3