Company
Mathematica Solutions to the ISSAC '97 Systems Challenge

Wolfram Research, Inc.


Problem 5

What is the largest zero of the 1000[Graphics:ISSACChallengegr74.gif] Laguerre polynomial to 12 significant digits?

Result
3943.24739485...


Method 1: Find the root numerically.

A well-known upper bound for the largest root [Graphics:ISSACChallengegr75.gif]of the [Graphics:ISSACChallengegr76.gif] Laguerre polynomial is 4v + 2 (see [4, 5]). The Laguerre polynomials satisfy the well-known differential equation [Graphics:ISSACChallengegr77.gif].

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr78.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr79.gif]

Transforming the equation to Liouville normal form using [Graphics:ISSACChallengegr80.gif], we get [Graphics:ISSACChallengegr81.gif]. When [Graphics:ISSACChallengegr82.gif], the solution [Graphics:ISSACChallengegr83.gif] will oscillate and will therefore have zeros. When [Graphics:ISSACChallengegr84.gif], the solution [Graphics:ISSACChallengegr85.gif] will increase or decrease monotonically. The larger zero,[Graphics:ISSACChallengegr86.gif], approximates the largest zero of [Graphics:ISSACChallengegr87.gif].

This gives us a starting point [Graphics:ISSACChallengegr88.gif]) for the numerical root finding procedure. We slide down the curve on the strictly concave side toward the root.

We define the function f to be the Laguerre polynomial and the gradient g of f. For faster and more reliable numerical calculation we avoid evaluating these functions as explicit polynomials.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr89.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr90.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr91.gif]

The secant method gives the same result.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr92.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr93.gif]

We check numerically to see that this is really the largest root.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr94.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr95.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr96.gif]

Using real root isolation techniques from the package Algebra`RootIsolation`, we can prove that this is the largest root. We can use the same package to find an interval with rational endpoints containing the root to the required precision.


Method 2: Calculate all roots one after another.

We start at the origin and step toward the largest root by explicitly calculating all the roots on the way.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr97.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr98.gif]

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr99.gif]

This is the largest root.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr100.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr101.gif]

Here is the cumulative root density as well as the spacing between the roots.

[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr102.gif]
[Graphics:ISSACChallengegr7.gif][Graphics:ISSACChallengegr103.gif]