Metodos numericos: raices multiples

Chapter 3.1: Multiple Roots

PEDRO FERNANDO QUIROGA NOVOA

Escuela de Ingeniería de Petróleos

UNIVERSIDAD INDUSTRIAL DE SANTANDER

Multiple Roots

* Basic operation of polynomials.

* Conventional methods

* Müller Method.

* Bairstow Method.

* Complex roots

Multiple Roots
The multiple roots are determinate to polynomial equations that have the generalform:
fx=a0+a1x+a2x2+…+anxn

Where n is the degree of the polynomial and a are the coefficients. The roots of polynomials can be real and / or complex, and comply with three rules:
* In an equation of degree n, there are n real or complex roots. It should be noted that the roots are not necessarily different.

* If n is odd there is at least one real root.

* If there are complexroots, these are found in conjugate pairs.

1. Basic operation of polynomials

* Evaluation of polynomials:
Although this form of the equation:
fx=a0+a1x+a2x2+…+anxn
Is the most common, is not the best for determining the value of a polynomial for a given value of x. Since for a polynomial of order n requires n sums n (n +1) / 2 multiplications.
So you can use the form nested tominimize the number of operations and reduce rounding errors. For example for a polynomial of degree 3 in this way would be:
fx=a0+x(a1+(xa2+a3x)
* Deflation polynomial:
When determining the root of a polynomial of degree n, if the procedure is repeated to find the root will yield the same result. Therefore it is necessary to remove the root before continuing so-called polynomial deflation. Toperform this procedure should factor the polynomial, to eliminate the root already found, or using synthetic division, in either case the new polynomial will have a degree less.

2. Conventional methods

Conventional methods for finding the roots of a polynomial are open and closed methods, the efficiency of these methods depends if the problem has complex roots. If there are only realroots of the two methods are useful but have the difficulty of finding an initial value and diverge in the result.
When there are complex roots, the closed methods are not applicable because the sign change criterion is not applicable to complex values. Therefore the Newton-Raphson method is the most viable.

3. Müller Method:

The secant method obtained root of a function by estimating aprojection of a straight line on the x-axis, through the values of the function. Müller's method, works similarly but instead of projecting a line using two points, requires three points to calculate a parable.
For this we need three points [x0, f(x0)], [x1, f(x1)] y [x2, f(x2)]. The approximation we can write as:
f(x)= a(x – x2)2 +b(x – x2)+c
The parabola's coefficients are calculated by solvingthe following system of equations.
fx0= ax0 – x22 + b(x0 – x2) + c
f(x1) = a(x1 – x2)2 + b(x1 – x2) + c
f(x2) = a(x2 – x2)2 + b(x2 – x2) + c
From the last equation we can see that the value of C = f(x2). Substituting the values of C in the other two equations we have:
f(x0)- f(x2) = a(x0 – x2)2 + b(x0 – x2)
f(x1)- f(x2) = a(x1 – x2)2 + b(x1 – x2)
(Equation 1 and 2)
Definingthe differences:
h0=x1 – x0
h1 =x2 – x1

δ0=f(x1) – f(x0)x1 – x0

δ1=f(x2) –f(x1)x2 – x1
These are replaced in equations 1 and 2 to obtain:
(h0+h1)b-(h0+h1)2a=h0δ0+h1δ1
h1b-h12a=h1δ1
The values of the coefficients are:
a=δ1-δ0h1-h0

b=ah1+δ1

c=fx2
To find the root we applied of the alternative quadratic formula, that is to say:
x3-x2=-2cb±b2-4ac
The approximation error isdetermined by the formula:
ε=x3-x2x3100%
* Example:
With the initial values x0,x1 y x2 =4.5, 5.5 y 5 to determine the roots of the equation.
First the function is evaluated with the initial values
f4.5=20.625
f5.5=82.875
f5=48
With these values are calculated:
h0=5.5-4.5=1 h1=5-5.5=-0.5
δ0=82.875 –20.6255.5-4.5=62.25
δ1=48 –82.8755-5.5 =69.75
With these values are...