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 }