1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.analysis;
18  
19  import org.apache.commons.math.MathException;
20  import org.apache.commons.math.TestUtils;
21  import org.apache.commons.math.complex.Complex;
22  import junit.framework.TestCase;
23  
24  /**
25   * Testcase for Laguerre solver.
26   * <p>
27   * Laguerre's method is very efficient in solving polynomials. Test runs
28   * show that for a default absolute accuracy of 1E-6, it generally takes
29   * less than 5 iterations to find one root, provided solveAll() is not
30   * invoked, and 15 to 20 iterations to find all roots for quintic function.
31   * 
32   * @version $Revision$ $Date$ 
33   */
34  public final class LaguerreSolverTest extends TestCase {
35  
36      /**
37       * Test of solver for the linear function.
38       */
39      public void testLinearFunction() throws MathException {
40          double min, max, expected, result, tolerance;
41  
42          // p(x) = 4x - 1
43          double coefficients[] = { -1.0, 4.0 };
44          PolynomialFunction f = new PolynomialFunction(coefficients);
45          UnivariateRealSolver solver = new LaguerreSolver(f);
46  
47          min = 0.0; max = 1.0; expected = 0.25;
48          tolerance = Math.max(solver.getAbsoluteAccuracy(),
49                      Math.abs(expected * solver.getRelativeAccuracy()));
50          result = solver.solve(min, max);
51          assertEquals(expected, result, tolerance);
52      }
53  
54      /**
55       * Test of solver for the quadratic function.
56       */
57      public void testQuadraticFunction() throws MathException {
58          double min, max, expected, result, tolerance;
59  
60          // p(x) = 2x^2 + 5x - 3 = (x+3)(2x-1)
61          double coefficients[] = { -3.0, 5.0, 2.0 };
62          PolynomialFunction f = new PolynomialFunction(coefficients);
63          UnivariateRealSolver solver = new LaguerreSolver(f);
64  
65          min = 0.0; max = 2.0; expected = 0.5;
66          tolerance = Math.max(solver.getAbsoluteAccuracy(),
67                      Math.abs(expected * solver.getRelativeAccuracy()));
68          result = solver.solve(min, max);
69          assertEquals(expected, result, tolerance);
70  
71          min = -4.0; max = -1.0; expected = -3.0;
72          tolerance = Math.max(solver.getAbsoluteAccuracy(),
73                      Math.abs(expected * solver.getRelativeAccuracy()));
74          result = solver.solve(min, max);
75          assertEquals(expected, result, tolerance);
76      }
77  
78      /**
79       * Test of solver for the quintic function.
80       */
81      public void testQuinticFunction() throws MathException {
82          double min, max, expected, result, tolerance;
83  
84          // p(x) = x^5 - x^4 - 12x^3 + x^2 - x - 12 = (x+1)(x+3)(x-4)(x^2-x+1)
85          double coefficients[] = { -12.0, -1.0, 1.0, -12.0, -1.0, 1.0 };
86          PolynomialFunction f = new PolynomialFunction(coefficients);
87          UnivariateRealSolver solver = new LaguerreSolver(f);
88  
89          min = -2.0; max = 2.0; expected = -1.0;
90          tolerance = Math.max(solver.getAbsoluteAccuracy(),
91                      Math.abs(expected * solver.getRelativeAccuracy()));
92          result = solver.solve(min, max);
93          assertEquals(expected, result, tolerance);
94  
95          min = -5.0; max = -2.5; expected = -3.0;
96          tolerance = Math.max(solver.getAbsoluteAccuracy(),
97                      Math.abs(expected * solver.getRelativeAccuracy()));
98          result = solver.solve(min, max);
99          assertEquals(expected, result, tolerance);
100 
101         min = 3.0; max = 6.0; expected = 4.0;
102         tolerance = Math.max(solver.getAbsoluteAccuracy(),
103                     Math.abs(expected * solver.getRelativeAccuracy()));
104         result = solver.solve(min, max);
105         assertEquals(expected, result, tolerance);
106     }
107 
108     /**
109      * Test of solver for the quintic function using solveAll().
110      */
111     public void testQuinticFunction2() throws MathException {
112         double initial = 0.0, tolerance;
113         Complex expected, result[];
114 
115         // p(x) = x^5 + 4x^3 + x^2 + 4 = (x+1)(x^2-x+1)(x^2+4)
116         double coefficients[] = { 4.0, 0.0, 1.0, 4.0, 0.0, 1.0 };
117         PolynomialFunction f = new PolynomialFunction(coefficients);
118         LaguerreSolver solver = new LaguerreSolver(f);
119         result = solver.solveAll(coefficients, initial);
120 
121         expected = new Complex(0.0, -2.0);
122         tolerance = Math.max(solver.getAbsoluteAccuracy(),
123                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
124         TestUtils.assertContains(result, expected, tolerance);
125 
126         expected = new Complex(0.0, 2.0);
127         tolerance = Math.max(solver.getAbsoluteAccuracy(),
128                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
129         TestUtils.assertContains(result, expected, tolerance);
130 
131         expected = new Complex(0.5, 0.5 * Math.sqrt(3.0));
132         tolerance = Math.max(solver.getAbsoluteAccuracy(),
133                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
134         TestUtils.assertContains(result, expected, tolerance);
135 
136         expected = new Complex(-1.0, 0.0);
137         tolerance = Math.max(solver.getAbsoluteAccuracy(),
138                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
139         TestUtils.assertContains(result, expected, tolerance);
140         
141         expected = new Complex(0.5, -0.5 * Math.sqrt(3.0));
142         tolerance = Math.max(solver.getAbsoluteAccuracy(),
143                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
144         TestUtils.assertContains(result, expected, tolerance);
145     }
146 
147     /**
148      * Test of parameters for the solver.
149      */
150     public void testParameters() throws Exception {
151         double coefficients[] = { -3.0, 5.0, 2.0 };
152         PolynomialFunction f = new PolynomialFunction(coefficients);
153         UnivariateRealSolver solver = new LaguerreSolver(f);
154 
155         try {
156             // bad interval
157             solver.solve(1, -1);
158             fail("Expecting IllegalArgumentException - bad interval");
159         } catch (IllegalArgumentException ex) {
160             // expected
161         }
162         try {
163             // no bracketing
164             solver.solve(2, 3);
165             fail("Expecting IllegalArgumentException - no bracketing");
166         } catch (IllegalArgumentException ex) {
167             // expected
168         }
169         try {
170             // bad function
171             UnivariateRealFunction f2 = new SinFunction();
172             new LaguerreSolver(f2);
173             fail("Expecting IllegalArgumentException - bad function");
174         } catch (IllegalArgumentException ex) {
175             // expected
176         }
177     }
178 }