001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    package org.apache.commons.math.analysis.solvers;
018    
019    import org.apache.commons.math.MathException;
020    import org.apache.commons.math.TestUtils;
021    import org.apache.commons.math.analysis.SinFunction;
022    import org.apache.commons.math.analysis.polynomials.PolynomialFunction;
023    import org.apache.commons.math.complex.Complex;
024    import junit.framework.TestCase;
025    
026    /**
027     * Testcase for Laguerre solver.
028     * <p>
029     * Laguerre's method is very efficient in solving polynomials. Test runs
030     * show that for a default absolute accuracy of 1E-6, it generally takes
031     * less than 5 iterations to find one root, provided solveAll() is not
032     * invoked, and 15 to 20 iterations to find all roots for quintic function.
033     * 
034     * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $ 
035     */
036    public final class LaguerreSolverTest extends TestCase {
037    
038        /**
039         * Test deprecated APIs.
040         */
041        @Deprecated
042        public void testDeprecated() throws MathException {
043            double min, max, expected, result, tolerance;
044    
045            // p(x) = 4x - 1
046            double coefficients[] = { -1.0, 4.0 };
047            PolynomialFunction f = new PolynomialFunction(coefficients);
048            UnivariateRealSolver solver = new LaguerreSolver(f);
049    
050            min = 0.0; max = 1.0; expected = 0.25;
051            tolerance = Math.max(solver.getAbsoluteAccuracy(),
052                        Math.abs(expected * solver.getRelativeAccuracy()));
053            result = solver.solve(min, max);
054            assertEquals(expected, result, tolerance);
055        }
056    
057        /**
058         * Test of solver for the linear function.
059         */
060        public void testLinearFunction() throws MathException {
061            double min, max, expected, result, tolerance;
062    
063            // p(x) = 4x - 1
064            double coefficients[] = { -1.0, 4.0 };
065            PolynomialFunction f = new PolynomialFunction(coefficients);
066            UnivariateRealSolver solver = new LaguerreSolver();
067    
068            min = 0.0; max = 1.0; expected = 0.25;
069            tolerance = Math.max(solver.getAbsoluteAccuracy(),
070                        Math.abs(expected * solver.getRelativeAccuracy()));
071            result = solver.solve(f, min, max);
072            assertEquals(expected, result, tolerance);
073        }
074    
075        /**
076         * Test of solver for the quadratic function.
077         */
078        public void testQuadraticFunction() throws MathException {
079            double min, max, expected, result, tolerance;
080    
081            // p(x) = 2x^2 + 5x - 3 = (x+3)(2x-1)
082            double coefficients[] = { -3.0, 5.0, 2.0 };
083            PolynomialFunction f = new PolynomialFunction(coefficients);
084            UnivariateRealSolver solver = new LaguerreSolver();
085    
086            min = 0.0; max = 2.0; expected = 0.5;
087            tolerance = Math.max(solver.getAbsoluteAccuracy(),
088                        Math.abs(expected * solver.getRelativeAccuracy()));
089            result = solver.solve(f, min, max);
090            assertEquals(expected, result, tolerance);
091    
092            min = -4.0; max = -1.0; expected = -3.0;
093            tolerance = Math.max(solver.getAbsoluteAccuracy(),
094                        Math.abs(expected * solver.getRelativeAccuracy()));
095            result = solver.solve(f, min, max);
096            assertEquals(expected, result, tolerance);
097        }
098    
099        /**
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    }