Exercise 2 - The roots of a polynomial

Documentation and user's manual

Table of contents

OCaml programs

Exercise 2 - The roots of a polynomial

Assume an Objective Caml toplevel in which the following modules (download an archive containing them) have been loaded and opened:

• All the the modules listed here.
•  Rat_inter : provides the type  rat_inter  to deal with intervals whose bounds are rational numbers (non-empty open intervals and singletons).
•  Rat_poly_common : provides the functions specified in exercise 1.

The irreducible polynomials in R[X] are those whose degree is 1 and those whose degree is 2 and whose corresponding quadratic equation has a negative discriminant. Moreover any non-zero polynomial in R[X] can be factorized as follows and this factorization is unique (not taking into account the order of the factors): p = an p1h1 ... paha s1k1 ... sbkb     avec     h1 + ... + ha + 2 (k1 + ... + kb) = n where: n denotes the degree of p. an denotes its leading coefficient. Each pi (sj respectively) denotes an irreducible polynomial whose leading coefficients is 1 and whose degrees is 1 (2 respectively). It is called an irreducible factors of p. pi<> pi' for i<> i' (sj<> sj' for j<> ' respectively). Each hi (kj respectively) denotes a positive integer. It is called the multiplicity of pi (sj respectively). A polynomial in R[X] is said to be square-free if the multiplicity of each of its irreducible factors is 1.

The Sturm chain (or Sturm sequence) of a square-free polynomial in R[X] whose degree is positive is the sequence q1...qr of polynomials in R[X] defined as follows (where p' denotes the derivative of p): q1=p q2=p' for all i in [2,r-1[ : qi+1=-mod(qi-1,qi) the degree of qr is 0 It can be shown that r >= 2, that each qi is non-zero, and that for all i in [1,r[ the degree of qi is greater than that of qi+1. Clearly if p belongs to Q[X] then each qi belongs to Q[X], too. For instance, the Sturm chain of p1=X3 - 2 X2 - X + 2 consists of p1, followed by p1'=3 X2 - 4 X - 1, then by 14 / 9 X - 16 / 9 and finally by 81 / 49. That of p2=X7 - 1 consists of p2, followed by p2'=7 X6, and finally by 1. That of p3=7 X + 4 consists of p3, followed by p3'=7.

Let I denote the set of intervals of R whose bounds are rational numbers and that are either non-empty and closed or singletons.

1

Write a definition of the function (named  sturm_chain ) that computes the Sturm chain of a polynomial p in S. Its type must be  rat_poly -> rat_poly list .

Let w denote the function that maps any square-free polynomial p in R[X] whose degree is positive to the function from R to N that maps any real number X to the number of sign changes in the list q1(X)...qr(X) of real numbers, where q1...qr denotes the Strum chain of p.

2

Write a definition of the function (named  nb_chang ) that computes the number of sign changes in a list of rational numbers. Its type must be  rat list -> int .

3

Write a definition of the (Objective Caml) function (named  w ) that, given a polynomial p in S, computes the restriction to Q of the (mathematical) function w(p) (which is from R to N). Its type must be  rat_poly -> (rat -> int) .

Let p denote a non-zero polynomial in R[X]. Let n denote its degree. Let (ai)i=n...0 denote its coefficients in degree decreasing order. Let m denote the sum of the absolute values of (ai)i=n...0. Let Mp=m / |an|. Note that Mp>0. Thus (-Mp,Mp) is non-empty. It can be shown that there exists no real root of p out of the non-empty open interval (-Mp,Mp) of R . Moreover note that Mp is a rational number if the coefficients of p are rational numbers.

4

Write a definition of the function (named  sum_of_coef_abs_val ) that sums the absolute values of all the coefficients of a non-zero polynomial in de Q[X]. Its type must be  rat_poly -> rat .

5

Write a definition of the function (named  no_root_out ) that, given a non-zero polynomial p in Q[X], computes the non-empty open interval (-Mp,Mp) of I (its bounds are rational numbers and there exists no real root of p out of it.). The type of  no_root_out  must be  rat_poly -> rat_inter .

It can be shown (Sturm's theorem) that for any square-free polynomial p in R[X] whose degree is positive and for any non-empty open interval (a,b) of R such that neither a nor b is a zero of p, the number of real roots of p belonging to (a,b) is (w(p))(a)-(w(p))(b). It can also be shown that, given a polynomial p in R[X] whose degree is positive, the polynomial qp=div(p,pgcd(p,p')) is square-free (therefore all its real roots are of multiplicity 1) and has exactly the same real roots as p. This polynomial qp will be called the square-free polynomial associated with p.

6

Write a definition of the function (named  variation ) that, given a function f from rational numbers to integers, computes the function that, given an interval i of I whose lower bound a and upper bound b are (rational numbers) such that f(a) and f(b) exist, computes the integer f(a)-f(b) (note that a=b is possible). Its type must be  (rat -> int) -> (rat_inter -> int) .

7

Write a definition of the function (named  nb_roots_in ) that, given a polynomial p in S, computes the function that, given a (non-empty) open interval i of I none of the bounds of which is a root of p, computes the number of real roots of p in I. Its type must be  rat_poly -> (rat_inter -> int) .

8

Write a definition of the function (named  square_free_with_the_same_roots ) that computes the square-free polynomial qp associated with a polynomial p of Q[X] whose degree is positive. Its type must be  rat_poly -> rat_poly .

9

Write a definition of the function (named  nb_roots ) that computes the number of real roots of a non-zero polynomial of Q[X].. Its type must be  rat_poly -> int .

Exercise 2 - The roots of a polynomial

Documentation and user's manual

Table of contents

OCaml programs