Approximating polynomial roots without complex arithmeticsSuppose that we have polynomial of degree greater than two P ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 with real coefficients and we want to approximate all roots of this polynomial without complex arithmeticIt seems to be good idea to get quadratic factors of P(x) P ( x ) = Q ( x ) ( x 2 − p x + q ) + R ( p , q ) x + S ( p , q )Now we want that after each iteration R(p,q) and S(p,q) be closer to zero until given tolerance εNow we need to solve system of nonliear equations R ( p , q ) = 0 S ( p , q ) = 0 and how to solve this system and present solution in such way it is easy to write code for it

Question

Approximating polynomial roots without complex arithmeticsSuppose that we have polynomial of degree greater than two  P  (  x  )  =      a          n            x    n    +      a          n      −      1            x          n      −      1            +    ⋯    +      a          1        x  +      a          0      with real coefficients and we want to approximate all roots of this polynomial without complex arithmeticIt seems to be good idea to get quadratic factors of P(x)  P  (  x  )  =  Q  (  x  )  (      x    2    −  p  x  +  q  )  +  R  (  p  ,  q  )  x  +  S  (  p  ,  q  )Now we want that after each iteration R(p,q) and S(p,q) be closer to zero until given tolerance   εNow we need to solve system of nonliear equations  R  (  p  ,  q  )  =  0    S  (  p  ,  q  )  =  0  and how to solve this system and present solution in such way it is easy to write code for it

zastenjkcy · Accepted Answer

Step 1The (Lin-)Bairstow method is what you ask for, the Newton method applied to the task of splitting of a quadratic factor from a polynomialThe factorization task to solve is  P  (  x  )  =  Q  (  x  )  ·  N  (  x  )  ,                 N  (  x  )  =      x    2    −  p  x  +  q  .With an approximation for the second factor, the linearization can be written as  P  (  x  )  =  Q  (  x  )  ·  N  (  x  )  +  Q  (  x  )  ·      Δ    N  (  x  )  +      Δ    Q  (  x  )  ·  N  (  x  )The aim is to compute the update       Δ    N. This polynomial does not change under reduction of the whole equation and all operations in it modulo N  [  P  (  x  )  mod  N  (  x  )  ]  =            (        [  Q  (  x  )  mod  N  (  x  )  ]  ·      Δ    N  (  x  )            )        mod  N  (  x  )Step 2This last system is now effectively a   2  ×  2 linear system for the coefficients p,q in       Δ    N  (  x  )  =  −      Δ    p  ·  x  +      Δ    q.Repeat until the changes are small, or any other convergence test for Newton&#039;s method (tests for at least halving of the update length from one step to the next, tests for quadratic convergence,...)In practical tests this iteration converges globally to some random factor for even degree polynomials. In odd-degree polynomials divergence can happen in a considerable part of the initial values, indicating a linear factor with root   x  =  q      /    p. Either use that as a single root or split off a real root with some other method for polynomials with real coefficients, so that the next steps can proceed from even degree to even degree.

Approximating polynomial roots without complex arithmetics. Suppose that we have polynomial of degree greater than two P(x)=a_n x^n+a_{n-1} x^{n-1}+ cdots +a_1x+a_0 with real coefficients and we want to approximate all roots of this polynomial without complex arithmetic

Answered question

Answer & Explanation

New Questions in Algebra II