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.solvers;
18  
19  import org.apache.commons.math.MathException;
20  import org.apache.commons.math.TestUtils;
21  import org.apache.commons.math.analysis.SinFunction;
22  import org.apache.commons.math.analysis.polynomials.PolynomialFunction;
23  import org.apache.commons.math.complex.Complex;
24  import junit.framework.TestCase;
25  
26  /**
27   * Testcase for Laguerre solver.
28   * <p>
29   * Laguerre's method is very efficient in solving polynomials. Test runs
30   * show that for a default absolute accuracy of 1E-6, it generally takes
31   * less than 5 iterations to find one root, provided solveAll() is not
32   * invoked, and 15 to 20 iterations to find all roots for quintic function.
33   * 
34   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $ 
35   */
36  public final class LaguerreSolverTest extends TestCase {
37  
38      /**
39       * Test deprecated APIs.
40       */
41      @Deprecated
42      public void testDeprecated() throws MathException {
43          double min, max, expected, result, tolerance;
44  
45          // p(x) = 4x - 1
46          double coefficients[] = { -1.0, 4.0 };
47          PolynomialFunction f = new PolynomialFunction(coefficients);
48          UnivariateRealSolver solver = new LaguerreSolver(f);
49  
50          min = 0.0; max = 1.0; expected = 0.25;
51          tolerance = Math.max(solver.getAbsoluteAccuracy(),
52                      Math.abs(expected * solver.getRelativeAccuracy()));
53          result = solver.solve(min, max);
54          assertEquals(expected, result, tolerance);
55      }
56  
57      /**
58       * Test of solver for the linear function.
59       */
60      public void testLinearFunction() throws MathException {
61          double min, max, expected, result, tolerance;
62  
63          // p(x) = 4x - 1
64          double coefficients[] = { -1.0, 4.0 };
65          PolynomialFunction f = new PolynomialFunction(coefficients);
66          UnivariateRealSolver solver = new LaguerreSolver();
67  
68          min = 0.0; max = 1.0; expected = 0.25;
69          tolerance = Math.max(solver.getAbsoluteAccuracy(),
70                      Math.abs(expected * solver.getRelativeAccuracy()));
71          result = solver.solve(f, min, max);
72          assertEquals(expected, result, tolerance);
73      }
74  
75      /**
76       * Test of solver for the quadratic function.
77       */
78      public void testQuadraticFunction() throws MathException {
79          double min, max, expected, result, tolerance;
80  
81          // p(x) = 2x^2 + 5x - 3 = (x+3)(2x-1)
82          double coefficients[] = { -3.0, 5.0, 2.0 };
83          PolynomialFunction f = new PolynomialFunction(coefficients);
84          UnivariateRealSolver solver = new LaguerreSolver();
85  
86          min = 0.0; max = 2.0; expected = 0.5;
87          tolerance = Math.max(solver.getAbsoluteAccuracy(),
88                      Math.abs(expected * solver.getRelativeAccuracy()));
89          result = solver.solve(f, min, max);
90          assertEquals(expected, result, tolerance);
91  
92          min = -4.0; max = -1.0; expected = -3.0;
93          tolerance = Math.max(solver.getAbsoluteAccuracy(),
94                      Math.abs(expected * solver.getRelativeAccuracy()));
95          result = solver.solve(f, min, max);
96          assertEquals(expected, result, tolerance);
97      }
98  
99      /**
100      * Test of solver for the quintic function.
101      */
102     public void testQuinticFunction() throws MathException {
103         double min, max, expected, result, tolerance;
104 
105         // p(x) = x^5 - x^4 - 12x^3 + x^2 - x - 12 = (x+1)(x+3)(x-4)(x^2-x+1)
106         double coefficients[] = { -12.0, -1.0, 1.0, -12.0, -1.0, 1.0 };
107         PolynomialFunction f = new PolynomialFunction(coefficients);
108         UnivariateRealSolver solver = new LaguerreSolver();
109 
110         min = -2.0; max = 2.0; expected = -1.0;
111         tolerance = Math.max(solver.getAbsoluteAccuracy(),
112                     Math.abs(expected * solver.getRelativeAccuracy()));
113         result = solver.solve(f, min, max);
114         assertEquals(expected, result, tolerance);
115 
116         min = -5.0; max = -2.5; expected = -3.0;
117         tolerance = Math.max(solver.getAbsoluteAccuracy(),
118                     Math.abs(expected * solver.getRelativeAccuracy()));
119         result = solver.solve(f, min, max);
120         assertEquals(expected, result, tolerance);
121 
122         min = 3.0; max = 6.0; expected = 4.0;
123         tolerance = Math.max(solver.getAbsoluteAccuracy(),
124                     Math.abs(expected * solver.getRelativeAccuracy()));
125         result = solver.solve(f, min, max);
126         assertEquals(expected, result, tolerance);
127     }
128 
129     /**
130      * Test of solver for the quintic function using solveAll().
131      */
132     public void testQuinticFunction2() throws MathException {
133         double initial = 0.0, tolerance;
134         Complex expected, result[];
135 
136         // p(x) = x^5 + 4x^3 + x^2 + 4 = (x+1)(x^2-x+1)(x^2+4)
137         double coefficients[] = { 4.0, 0.0, 1.0, 4.0, 0.0, 1.0 };
138         LaguerreSolver solver = new LaguerreSolver();
139         result = solver.solveAll(coefficients, initial);
140 
141         expected = new Complex(0.0, -2.0);
142         tolerance = Math.max(solver.getAbsoluteAccuracy(),
143                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
144         TestUtils.assertContains(result, expected, tolerance);
145 
146         expected = new Complex(0.0, 2.0);
147         tolerance = Math.max(solver.getAbsoluteAccuracy(),
148                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
149         TestUtils.assertContains(result, expected, tolerance);
150 
151         expected = new Complex(0.5, 0.5 * Math.sqrt(3.0));
152         tolerance = Math.max(solver.getAbsoluteAccuracy(),
153                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
154         TestUtils.assertContains(result, expected, tolerance);
155 
156         expected = new Complex(-1.0, 0.0);
157         tolerance = Math.max(solver.getAbsoluteAccuracy(),
158                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
159         TestUtils.assertContains(result, expected, tolerance);
160         
161         expected = new Complex(0.5, -0.5 * Math.sqrt(3.0));
162         tolerance = Math.max(solver.getAbsoluteAccuracy(),
163                     Math.abs(expected.abs() * solver.getRelativeAccuracy()));
164         TestUtils.assertContains(result, expected, tolerance);
165     }
166 
167     /**
168      * Test of parameters for the solver.
169      */
170     public void testParameters() throws Exception {
171         double coefficients[] = { -3.0, 5.0, 2.0 };
172         PolynomialFunction f = new PolynomialFunction(coefficients);
173         UnivariateRealSolver solver = new LaguerreSolver();
174 
175         try {
176             // bad interval
177             solver.solve(f, 1, -1);
178             fail("Expecting IllegalArgumentException - bad interval");
179         } catch (IllegalArgumentException ex) {
180             // expected
181         }
182         try {
183             // no bracketing
184             solver.solve(f, 2, 3);
185             fail("Expecting IllegalArgumentException - no bracketing");
186         } catch (IllegalArgumentException ex) {
187             // expected
188         }
189         try {
190             // bad function
191             solver.solve(new SinFunction(), -1, 1);
192             fail("Expecting IllegalArgumentException - bad function");
193         } catch (IllegalArgumentException ex) {
194             // expected
195         }
196     }
197 }