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 }