Birge-Vieta Method and Problems Roots polynomials

https://mat.iitm.ac.in/home/sryedida/public_html/caimna/transcendental/polynomial%20methods/bv%20method.html


Birge-Vieta Method

This is an iterative method to find a real root of the nth degree polynomial equation f(x) = P_n(x) = 0 of the form 

a_n xⁿ + a_n-1 x^n-1 + .  .  . + a₁ x + a₀ = 0

The theory can be understood better if we consider the above nth degree polynomial in the form

xⁿ + a₁ x^n-1 + a₂ x^n-2 + .  .  . + a_n-1x + a_n = 0

If s is a real root of P_n(x) = 0 then P_n(x) = (x-s)Q_n-1(x) where Q_n-1(x) is an (n-1)th degree polynomial of the form

Q_n-1(x) = x^n-1 + b₁ x^n-2 +  .  .  . + b_n-2x + b_n-1.

If p is any approximation to s then P_n(x) = (x-p)Q_n-1(x) + R where R is the residue which depends on p.

Now starting with p, we can use some iterative method to improve the value of p such that 
R(p) = 0.

If we apply the Newton-Raphson method with a starting value p₀, the iterative scheme can be written as

 

pi+1= pi -	Pn(pi)
		i = 0,1,2...
	P'(pi)

Now by comparing the coefficients of  P_n and (x-p)Q_n-1(x) + R we get

a1	=	b1 - p	Þ	b1	=	a1 + p
a2	=	b2 - pb1	Þ	b2	=	a2 + pb1
. . .		. . .		. . .		. . .
ai	=	bi - pbi-1	Þ	bi	=	ai + pbk-1
. . .		. . .		. . .		. . .
an	=	R - pbn-1	Þ	R = bn	=	an + pbn-1
(or)
bi	=	ai + pbi-1				i=1,2,...n

with b₀=1 and R = b_n=P_n(p)

To find P'_n(p), let us differentiate the equation

   b_i = a_i + pb_i-1

with respect to p

Þ                 db_i / dp = b_i-1 + p (db_i-1 / dp)

if we substitute (db_i / dp) = c_i-1  then

Þ            c_i-1 = b_i-1 + pc_i-2              (or)
                                      c_i     = b_i + pc_i-1            i=1, 2, . . ., n-1

Then the  c_n-1 obtained from the last equation is nothing but 

c_i-1 = db_n / dp = dR / dp = P'_n(p)

That is the Newton's method now can be written as

p_i+1 = p_i - b_n / c_n-1

On convergence this iterative process will give one root p of the polynomial equation P_n(x) = 0. Now the deflated polynomial equation Q_n-1(x) = 0 can be used to find the other real roots. 

This method is often called as Birge-Vieta method.

 

Example :

Find the real root of  x³ - x² - x + 1 = 0

In this problem the coefficients are a₀ = 1, a₁ = -1, a₂ = -1, a₃ = 1

Let the initial approximation to p be p₀ = 0.5

	a0	a1	a2	a3
p0 = 5	+1	-1	-1	+1
		+0.5	-0.25	-0.625
	+1	-0.5	-1.25	+0.375	(b4 = R)
		+0.5	0	-0.625
	+1	0	-1.25		(c2 = R')

  
  
 

p1 = p0 - b4 / c3	= 0.5 -	0.375	= 0.5 +	0.375	= 0.5 + 0.3 = 0.8
		-1.25		1.25

  
  
 

	a0	a1	a2	a3
p1 = 0.8	+1	-1	-1	+1
		+0.8	-0.16	-0.928
	+1	-0.2	-1.16	+0.072	(b4 = R)
		+0.8	+0.48
	+1	+0.6	-0.68		(c2 = R')

  
 

p2	= 0.8 -	0.072	= 0.8 +	0.072	= 0.8 + 0.1059 = 0.9059
		-0.68		0.68

  
 

	a0	a1	a2	a3
p2 = 0.9059	+1	-1	-1	+1
		+0.9059	-0.0852	-0.9831
	+1	-0.0941	-1.0852	+0.0169	(b4 = R)
		+0.9059	+0.7354
	+1	+0.8118	-0.3498		(c2 = R')

  
 

p3	= 0.905 -	0.0169	= 0.905 +	0.0169	= 0.905 + 0.0483 = 0.9533
		-0.3498		0.3498

The exact root is 1.0

Worked out problems

Find a root and the corrponding polynomial factor for the following polynomial equations
Exapmple 1	x4 - 3x3 + 3x2 - 3x + 2 = 0	Solution
Exapmple 2	x4-x-10 = 0	Solution
Exapmple 3	x3 - 6x2  + 11x  - 6 = 0	Solution
Exapmple 4	x3 - 4x2 + 5x - 2 = 0	Solution
Exapmple 5	x4 - x3 + 3x2 + x - 4 = 0	Solution
Exapmple 6	x3 - x - 4 = 0	Solution
Problems to workout