Understanding Bairstow's Method in Polynomial Approximation

Bairstow's Method 1. Bairstow s method is an iterative approach loosely related to both M ller and Newton Raphson methods 2. It is based on dividing the given polynomial by a quadratic polynomial x2-rx-s: = = + + + + 2 n K f ( x) a a x a x a x 1 rx 2 n o x n R ( ) + 2 s f ( x) 2 n where f R = = + + + + 3 2 n n K ( x) b ( x b r ) b b x + b x b x 2 2 3 1 n n n 1 o

Bairstow's Method 3. The coefficients b s are obtained very easily by using recursive relation b a b a rb b a rb + = + + = n n = + 1 1 n- n- n = 2 to 0 sb i n- + 1 2 i i i i 4. Using Newton Raphson approach, r and s are adjusted so as to make both bo and b1approach zero = = + + + b b a a rb rb + sb sb u(r,s) v(r,s) 1 1 2 3 0 0 1 2

Bairstow's Method 5. Obtain corrections in r and s by Newton-Raphson method Changes b r b r and needed to improve guesses will be estimated by s r b s b + = r s b 1 1 1 + = r s b o o o s

Bairstow's Method 6. Bairstow (1920) showed that the partial derivatives of b1 and b2 are obtained by the recursive relation c b = = + = + + n n b c c rc 1 1 n n n = 2 2 b rc sc i n to + + 1 2 i i i i where b r b s b r b s = = = = c c c o o 1 1 1 2 3 7. Iterate the steps untill ( r/r)and ( s/s) drops below a specified threshold

Order of Convergence Definition: Let ?0,?1,?2,?3 be a sequence which converges to . Define en = xn . If there exists a number p and a constant C 0 such that, ??+1 ???= ? lim ? Then, p is called the order of convergence of the sequence and C is the asymptotic error constant. ??+1 ?? = ? ? = C, 1st Order. Fixed Point: ? ? ? ? ??+1 ??2 = 1 Newton Raphson: = C, 2nd Order 2 ? ? ? ? ??+1 ?? ?? 1 = 1 Secant: = C, mixed order, 1.6 2 ? ? ? ? ??+1 Muller: = C, mixed order, 1.84 ?? ?? 1 ?? 2 = 1 6 5

Polynomial Methods: Single Root ? ????= ?0+ ?1? + ?2?2+ + ???? ??? = ?=0 If we divide by a factor (x - r) such that, r = is a root of the polynomial, we will get an exact polynomial of order (n - 1), say ?? 1? . ? 1 ??+1??= ?1+ ?2? + ?3?2+ + ???? 1 ?? 1? = ?=0 If r , dividing by a factor (x - r) will have a remainder b0. 6

Polynomial Methods: Single Root ? ????= ?0+ ?1? + ?2?2+ + ???? ??? = ?=0 ? 1 ??+1??+ ?0 = ? ? ?? 1? + ?0= ? ? ?=0 = ?0+ ?1? ? + ?2? ? ? + ?3?2? ? + + ?? 2?? 3? ? + ?? 1?? 2? ? + ???? 1? ? = ?0 ??1 + ? ?1 ??2 + ?2?2 ??3 + + ?? 2?? 2 ??? 1 + ?? 1?? 1 ??? + ???? ??= ??; ?? ???+1= ??; ? = ? 1 , ? 2 , 2,1,0 ??= ??; ??= ??+ ???+1; ? = ? 1 , ? 2 , 2,1,0 For a given ??? , ?? are known. For a choice of r, one can determine ?? from n+1 equations above having n+1 unknowns 7

Polynomial Methods: Single Root Remainder b0 is a function of r b0(r), at r = , b0(r) = 0 Problem: f(x) = 0, find a root x = such that f( ) = 0 Problem: b0(r) = 0, find a root r = such that b0( ) = 0 Apply Newton-Raphson: Iteration Formula for Step k: ? ?? ? ??or??+1= ?? ?0?? ??+1= ?? ?? ?0 ?0= ?0+ ??1 b0 (r) = b1 ??+1= ?? ?0?? ?1?? Assume a value of r, estimate b0 and b1, compute new r. Continue until b0 becomes zero. (with acceptable relative error) 8

Polynomial Methods: Bairstow's ? ????= ?0+ ?1? + ?2?2+ + ???? ??? = ?=0 Let us divide by a factor (x2 rx s). If the factor is exact, the resulting polynomial will be of order (n 2). Two roots of the polynomial can be estimated simultaneously as the roots of the quadratic factor. For the complex roots, they will be the complex conjugates. ? 2 ??+2??= ?2+ ?3? + ?4?2+ + ???? 2 ?? 2? = ?=0 If the factor (x2 rx s) is not exact, there will be two remainder terms, one function of x and another constant. Let us express the remainder term as b1(x - r) + b0. This form instead of the standard b1x + b0 is chosen to device a convenient iteration formula! 9

Polynomial Methods: Bairstow's ? ????= ?0+ ?1? + ?2?2+ + ???? ??? = ?=0 = ?2 ?? ? ?? 2? + ?1? ? + ?0 ? 2 = ?2 ?? ? ??+2??+ ?1? ? + ?0 ?=0 = ?0+ ?1? ? + ?2?2 ?? ? + ?3? ?2 ?? ? + + ?? 2?? 4?2 ?? ? + ?? 1?? 3?2 ?? ? + ???? 2?2 ?? ? = ?0 ??1 ??2 + ? ?1 ??2 ??3 + ?2?2 ??3 ??4 + + ?? 2?? 2 ??? 1 ??? + ?? 1?? 1 ??? + ???? ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 For a given ??? , ?? are known. For a choice of r and s, one can determine ?? from n+1 equations above having n+1 unknowns 10

Polynomial Methods: Bairstow's b0 and b1 are functions of r and s b0(r, s) and b1(r, s) Expand in Taylor s series: Apply 2-d Newton-Raphson 0 = ?0? + ?,? + ? = ?0+??0 ?? ? +??0 ?? ? +??1 ?? ? + ??? 0 = ?1? + ?,? + ? = ?1+??1 ?? ? + ??? ??0 ?? ??1 ?? ??0 ?? ??1 ?? ?0 ?1 ? ? = Need to evaluate: ??0 ??, ??0 ??, ??1 ?? and ??1 ?? 11

Polynomial Methods: Bairstow's ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 Partial differentials with respect to r: ??? ??= 0; ??= ?? ??? 1 ?? ?? 1= ?? 1+ ??? = ??= ?? = 0 ??? 2 ?? = ?? 1+ ???? 1 + ???? ?? 2= ?? 2+ ??? 1+ ??? ??= ?? 1+ ??? ?? = ?? 1 ?? 3= ?? 3+ ??? 2+ ??? 1 ??? 3 = ?? 2+ ???? 2 + ???? 1 ?? ?? ?? = ?? 2+ ??? 1+ ???= ?? 2 ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 ??? ??= ??+1; ? = ? 1 , 2,1,0 12

Polynomial Methods: Bairstow's ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 Partial differentials with respect to s: ??? ??= 0; ??= ?? ??? 1 ?? ?? 1= ?? 1+ ??? = 0 = 0 = 0 ??? 2 ?? = ??+ ???? 1 + ???? ??= ??= ?? (say) + ???? 1 ?? ?? 2= ?? 2+ ??? 1+ ??? ?? ?? 3= ?? 3+ ??? 2+ ??? 1 ??? 3 = ?? 1+ ???? 2 = ?? 1+ ??? ?? ?? = ?? 1 ?? 4= ?? 4+ ??? 3+ ??? 2 ??? 4 = ?? 2+ ???? 3 + ???? 2 ?? ?? ?? = ?? 2+ ??? 1+ ???= ?? 2 ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 ??? ??= ??+2; ? = ? 2 , 2,1,0 13

Polynomial Methods: Bairstow's ??? ??= ??+1; ? = ? 1 , 2,1,0 and??? ??= ??+2; ? = ? 2 , 2,1,0 ??0 ??= ?1; ??1 ??= ?2; ??0 ??= ?2 and ??1 ??= ?3 ??0 ?? ??1 ?? ??0 ?? ??1 ?? ?1 ?2 ?2 ?3 ?0 ?1 ? ? ? ? = = For any given polynomial, we know {a0, a1, an}. Assume r and s. Compute {b0, b1, bn} and {c0, c1, cn}. Compute r and s. 14

Polynomial Methods: Bairstow's Algorithm Step 1: input a0, a1, an and initialize r and s. Step 2: compute b0, b1, bn ??= ??;?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 Step 3: compute c0, c1, cn ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 ?1 ?2 ?2 ?3 ?0 ?1 ? ? Step 4: compute r and s from = Step 5: compute rnew = r + r, snew = s + s ???? ? ???? ???? ? ???? Step 6: check for convergence, ? and b0, b1 , Step 7: Stop if all convergence checks are satisfied. Else, set r = rnew , s = snew and go to step 2. 15

Bairstow's Method Step 8. The roots quadratic polynomial x2-rx-s are obtained as r x = + 2 4 r s 2 Step 9. At this point three possibilities exist: 1. The quotient is a third-order polynomial or greater. The previous values of r and s serve as initial guesses and Bairstow s method is applied to the quotient to evaluate new r and s values. 2. The quotient is quadratic. The remaining two roots are evaluated directly, using the above eqn. 3. The quotient is a 1st order polynomial. The remaining single root can be evaluated simply as x=-s/r.

Example Problem ????????? ? ? ????? ?? ? ? ?????????? ?(?) = ?5 3.5?4+ 2.75?3+ 2.125?2 3.875? + 1.25 Use initial guesses of r = s = -1 and iterate to a 0.1% Soln: Step 1: Input a0, a1, an and initialize r and s. In ??? = ?=0 ????= ?0+ ?1? + ?2?2+ + ???? Here n = 5; ?5? = ?=0 ????= ?0+ ?1? + ?2?2+ + ?5?5 ? 5 ?0 = 1.25; ?1 = -3.875; ?2 = 2.125; ?3 = 2.75; ?4 = -3.5; ?5 = 1; 17

Example Problem Step 2: compute b0, b1, bn using recursive relations derived ??= ??; ?? 1= ?? 1+ ??? ; ??= ??+ ???+1+ ???+2; ? = ? 2 , 2,1,0 Here, n =5 ?5= ?5;?4= ?4+ ??5 ;??= ??+ ???+1+ ???+2; ? = 3,2,1,0 ?3= ?3+ ??4+ ??5; ?2= ?2+ ??3+ ??4 ?1= ?1+ ??2+ ??3 ?0= ?0+ ??1+ ??2 18

Example Problem Step 3: compute c0, c1, cnusing recursive relations derived ??= ??; ?? 1= ?? 1+ ??? ; ?? = ??+ ???+1+ ???+2; Here, n =5 ? = ? 2 , 2,1,0 ?5= ?5;?4= ?4+ ??5 ;??= ??+ ???+1+ ???+2; ? = 3,2,1,0 ?3= ?3+ ??4+ ??5 ?2= ?2+ ??3+ ??4 ?1= ?1+ ??2+ ??3 ?0= ?0+ ??1+ ??2 19

Example Problem ?1 ?2 ?2 ?3 ?0 ?1 ? ? Step 4: compute r and s from = ? ? Here, 16.375 4.875 Solving, ? = 0.3558 and ? = 1.1381 4.875 10.75 = 11.375 10.5 Step 5: compute rnew = r + r, snew = s + s rnew = -1 + 0.3558 = -0.6442, snew = -1 + 1.1381 = 0.1381 ???? ? ???? ???? ? ???? Step 6: check for convergence, ?; b0, b1 , ???? ? ???? 0.6442 ( 1) 0.6442 ???? ? ???? 0.1381 ( 1) 0.1381 = 100%; ??,? = = 100%; ??,? = Step 7: Stop if all convergence checks are satisfied. Else, set r = rnew , s = snew and go to step 2. 20

Bairstow's Method Step 8. The roots quadratic polynomial x2-rx-s are obtained as r x = + 2 4 r s 2 Step 9. At this point three possibilities exist: 1. The quotient is a third-order polynomial or greater. The previous values of r and s serve as initial guesses and Bairstow s method is applied to the quotient to evaluate new r and s values. 2. The quotient is quadratic. The remaining two roots are evaluated directly, using the above eqn. 3. The quotient is a 1st order polynomial. The remaining single root can be evaluated simply as x=-s/r.

Multiple Roots Definition: A root of the equation f(x) = 0 is said to have a multiplicity of q if, ? ? ? ?? ? ? = 0 ? ? < when, q > 1, the order of convergence is no longer valid. Solution: Suppose a function f(x) is q-times continuously differentiable in the neighbourhood of a root of multiplicity q, 1 ?!? ????? and ? ? = 1 ? 1 !? ?? 1??? ? ? = where ?,? ?,? ??? ??? ? ? ? ?=1 Define ? ? = ?? ? ? ? ? ? =1 lim ? ? ? Therefore, is a root of f(x) of multiplicity q but is a simple root of u(x)! 22

Revision of Solution of Non-linear Equations 1. Graphical Method Provide insights but tedious/subjective 2. Bracketing methods 1. Bisection method Guaranteed convergence Linear or better convergence 2. False position method 3. Modified false position method 3. Open methods May diverge FP - linear convergence NR quadratic convergence Secant between linear & quadratic 1. Fixed-point iteration 2. Newton-Raphson 3. Secant & Modified Secant NR problems near zero gradient

Revision of Solution of Non-linear Equations Hybrid Methods Combination - Bracketing method at the beginning - Open method near convergence 1. Dekker method 2. Brent method Multiple roots 1. Bracketing method Only for odd number of roots 2. Newton-Raphson - Linear convergence 3. Modified Newton Raphson Quadratic convergence a. Known multiplicity b. Derivative function

Revision of Solution of Non-linear Equations Roots of polynomials 1. Evaluation of polynomials 2. Division of polynomials 3. Deflation of polynomials 4. Effective degree of polynomials Method of finding roots 1. M ller method Real and complex rooots 2. Bairstow's method

Revision of Solution of Non-linear Equations 1. Except for rare cases, computers will provide approximate solution. 2. No method is universally better than others. 3. Domain knowledge should guide the selection of algorithm and guess value(s).

Comparison of different algorithms