From Wikipedia, the free encyclopedia

Birge-Vieta Method This is an iterative method to find a real root of the nth degree polynomial equation f(x) = Pn(x) = 0 of the form

an xn + an-1 xn-1 + . . . + a1 x + a0 = 0

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

xn + a1 xn-1 + a2 xn-2 + . . . + an-1x + an = 0

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

Qn-1(x) = xn-1 + b1 xn-2 + . . . + bn-2x + bn-1.

If p is any approximation to s then Pn(x) = (x-p)Qn-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 p0, the iterative scheme can be written as

pi+1= pi - Pn(pi)

---

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

Now by comparing the coefficients of Pn and (x-p)Qn-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 b0=1 and R = bn=Pn(p) To find P'n(p), let us differentiate the equation

  bi = ai + pbi-1

with respect to p

Þ dbi / dp = bi-1 + p (dbi-1 / dp)

if we substitute (dbi / dp) = ci-1 then

Þ ci-1 = bi-1 + pci-2 (or)

                                     ci     = bi + pci-1            i=1, 2, . . ., n-1

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

ci-1 = dbn / dp = dR / dp = P'n(p)

That is the Newton's method now can be written as pi+1 = pi - bn / cn-1 On convergence this iterative process will give one root p of the polynomial equation Pn(x) = 0. Now the deflated polynomial equation Qn-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 x3 - x2 - x + 1 = 0 In this problem the coefficients are a0 = 1, a1 = -1, a2 = -1, a3 = 1 Let the initial approximation to p be p0 = 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