Mercurial > hg > de.mpg.mpiwg.itgroup.digilib.plugin

comparison libs/commons-math-2.1/docs/apidocs/src-html/org/apache/commons/math/analysis/polynomials/PolynomialsUtils.html @ 13:cbf34dd4d7e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commons-math-2.1 added
author dwinter
date Tue, 04 Jan 2011 10:02:07 +0100
parents
children
comparison
equal deleted inserted replaced
12:970d26a94fb7 13:cbf34dd4d7e6
1 <HTML>
2 <BODY BGCOLOR="white">
3 <PRE>
4 <FONT color="green">001</FONT> /*<a name="line.1"></a>
5 <FONT color="green">002</FONT> * Licensed to the Apache Software Foundation (ASF) under one or more<a name="line.2"></a>
6 <FONT color="green">003</FONT> * contributor license agreements. See the NOTICE file distributed with<a name="line.3"></a>
7 <FONT color="green">004</FONT> * this work for additional information regarding copyright ownership.<a name="line.4"></a>
8 <FONT color="green">005</FONT> * The ASF licenses this file to You under the Apache License, Version 2.0<a name="line.5"></a>
9 <FONT color="green">006</FONT> * (the "License"); you may not use this file except in compliance with<a name="line.6"></a>
10 <FONT color="green">007</FONT> * the License. You may obtain a copy of the License at<a name="line.7"></a>
11 <FONT color="green">008</FONT> *<a name="line.8"></a>
12 <FONT color="green">009</FONT> * http://www.apache.org/licenses/LICENSE-2.0<a name="line.9"></a>
13 <FONT color="green">010</FONT> *<a name="line.10"></a>
14 <FONT color="green">011</FONT> * Unless required by applicable law or agreed to in writing, software<a name="line.11"></a>
15 <FONT color="green">012</FONT> * distributed under the License is distributed on an "AS IS" BASIS,<a name="line.12"></a>
16 <FONT color="green">013</FONT> * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.<a name="line.13"></a>
17 <FONT color="green">014</FONT> * See the License for the specific language governing permissions and<a name="line.14"></a>
18 <FONT color="green">015</FONT> * limitations under the License.<a name="line.15"></a>
19 <FONT color="green">016</FONT> */<a name="line.16"></a>
20 <FONT color="green">017</FONT> package org.apache.commons.math.analysis.polynomials;<a name="line.17"></a>
21 <FONT color="green">018</FONT> <a name="line.18"></a>
22 <FONT color="green">019</FONT> import java.util.ArrayList;<a name="line.19"></a>
23 <FONT color="green">020</FONT> <a name="line.20"></a>
24 <FONT color="green">021</FONT> import org.apache.commons.math.fraction.BigFraction;<a name="line.21"></a>
25 <FONT color="green">022</FONT> <a name="line.22"></a>
26 <FONT color="green">023</FONT> /**<a name="line.23"></a>
27 <FONT color="green">024</FONT> * A collection of static methods that operate on or return polynomials.<a name="line.24"></a>
28 <FONT color="green">025</FONT> *<a name="line.25"></a>
29 <FONT color="green">026</FONT> * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $<a name="line.26"></a>
30 <FONT color="green">027</FONT> * @since 2.0<a name="line.27"></a>
31 <FONT color="green">028</FONT> */<a name="line.28"></a>
32 <FONT color="green">029</FONT> public class PolynomialsUtils {<a name="line.29"></a>
33 <FONT color="green">030</FONT> <a name="line.30"></a>
34 <FONT color="green">031</FONT> /** Coefficients for Chebyshev polynomials. */<a name="line.31"></a>
35 <FONT color="green">032</FONT> private static final ArrayList&lt;BigFraction&gt; CHEBYSHEV_COEFFICIENTS;<a name="line.32"></a>
36 <FONT color="green">033</FONT> <a name="line.33"></a>
37 <FONT color="green">034</FONT> /** Coefficients for Hermite polynomials. */<a name="line.34"></a>
38 <FONT color="green">035</FONT> private static final ArrayList&lt;BigFraction&gt; HERMITE_COEFFICIENTS;<a name="line.35"></a>
39 <FONT color="green">036</FONT> <a name="line.36"></a>
40 <FONT color="green">037</FONT> /** Coefficients for Laguerre polynomials. */<a name="line.37"></a>
41 <FONT color="green">038</FONT> private static final ArrayList&lt;BigFraction&gt; LAGUERRE_COEFFICIENTS;<a name="line.38"></a>
42 <FONT color="green">039</FONT> <a name="line.39"></a>
43 <FONT color="green">040</FONT> /** Coefficients for Legendre polynomials. */<a name="line.40"></a>
44 <FONT color="green">041</FONT> private static final ArrayList&lt;BigFraction&gt; LEGENDRE_COEFFICIENTS;<a name="line.41"></a>
45 <FONT color="green">042</FONT> <a name="line.42"></a>
46 <FONT color="green">043</FONT> static {<a name="line.43"></a>
47 <FONT color="green">044</FONT> <a name="line.44"></a>
48 <FONT color="green">045</FONT> // initialize recurrence for Chebyshev polynomials<a name="line.45"></a>
49 <FONT color="green">046</FONT> // T0(X) = 1, T1(X) = 0 + 1 * X<a name="line.46"></a>
50 <FONT color="green">047</FONT> CHEBYSHEV_COEFFICIENTS = new ArrayList&lt;BigFraction&gt;();<a name="line.47"></a>
51 <FONT color="green">048</FONT> CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);<a name="line.48"></a>
52 <FONT color="green">049</FONT> CHEBYSHEV_COEFFICIENTS.add(BigFraction.ZERO);<a name="line.49"></a>
53 <FONT color="green">050</FONT> CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE);<a name="line.50"></a>
54 <FONT color="green">051</FONT> <a name="line.51"></a>
55 <FONT color="green">052</FONT> // initialize recurrence for Hermite polynomials<a name="line.52"></a>
56 <FONT color="green">053</FONT> // H0(X) = 1, H1(X) = 0 + 2 * X<a name="line.53"></a>
57 <FONT color="green">054</FONT> HERMITE_COEFFICIENTS = new ArrayList&lt;BigFraction&gt;();<a name="line.54"></a>
58 <FONT color="green">055</FONT> HERMITE_COEFFICIENTS.add(BigFraction.ONE);<a name="line.55"></a>
59 <FONT color="green">056</FONT> HERMITE_COEFFICIENTS.add(BigFraction.ZERO);<a name="line.56"></a>
60 <FONT color="green">057</FONT> HERMITE_COEFFICIENTS.add(BigFraction.TWO);<a name="line.57"></a>
61 <FONT color="green">058</FONT> <a name="line.58"></a>
62 <FONT color="green">059</FONT> // initialize recurrence for Laguerre polynomials<a name="line.59"></a>
63 <FONT color="green">060</FONT> // L0(X) = 1, L1(X) = 1 - 1 * X<a name="line.60"></a>
64 <FONT color="green">061</FONT> LAGUERRE_COEFFICIENTS = new ArrayList&lt;BigFraction&gt;();<a name="line.61"></a>
65 <FONT color="green">062</FONT> LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);<a name="line.62"></a>
66 <FONT color="green">063</FONT> LAGUERRE_COEFFICIENTS.add(BigFraction.ONE);<a name="line.63"></a>
67 <FONT color="green">064</FONT> LAGUERRE_COEFFICIENTS.add(BigFraction.MINUS_ONE);<a name="line.64"></a>
68 <FONT color="green">065</FONT> <a name="line.65"></a>
69 <FONT color="green">066</FONT> // initialize recurrence for Legendre polynomials<a name="line.66"></a>
70 <FONT color="green">067</FONT> // P0(X) = 1, P1(X) = 0 + 1 * X<a name="line.67"></a>
71 <FONT color="green">068</FONT> LEGENDRE_COEFFICIENTS = new ArrayList&lt;BigFraction&gt;();<a name="line.68"></a>
72 <FONT color="green">069</FONT> LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);<a name="line.69"></a>
73 <FONT color="green">070</FONT> LEGENDRE_COEFFICIENTS.add(BigFraction.ZERO);<a name="line.70"></a>
74 <FONT color="green">071</FONT> LEGENDRE_COEFFICIENTS.add(BigFraction.ONE);<a name="line.71"></a>
75 <FONT color="green">072</FONT> <a name="line.72"></a>
76 <FONT color="green">073</FONT> }<a name="line.73"></a>
77 <FONT color="green">074</FONT> <a name="line.74"></a>
78 <FONT color="green">075</FONT> /**<a name="line.75"></a>
79 <FONT color="green">076</FONT> * Private constructor, to prevent instantiation.<a name="line.76"></a>
80 <FONT color="green">077</FONT> */<a name="line.77"></a>
81 <FONT color="green">078</FONT> private PolynomialsUtils() {<a name="line.78"></a>
82 <FONT color="green">079</FONT> }<a name="line.79"></a>
83 <FONT color="green">080</FONT> <a name="line.80"></a>
84 <FONT color="green">081</FONT> /**<a name="line.81"></a>
85 <FONT color="green">082</FONT> * Create a Chebyshev polynomial of the first kind.<a name="line.82"></a>
86 <FONT color="green">083</FONT> * &lt;p&gt;&lt;a href="http://mathworld.wolfram.com/ChebyshevPolynomialoftheFirstKind.html"&gt;Chebyshev<a name="line.83"></a>
87 <FONT color="green">084</FONT> * polynomials of the first kind&lt;/a&gt; are orthogonal polynomials.<a name="line.84"></a>
88 <FONT color="green">085</FONT> * They can be defined by the following recurrence relations:<a name="line.85"></a>
89 <FONT color="green">086</FONT> * &lt;pre&gt;<a name="line.86"></a>
90 <FONT color="green">087</FONT> * T&lt;sub&gt;0&lt;/sub&gt;(X) = 1<a name="line.87"></a>
91 <FONT color="green">088</FONT> * T&lt;sub&gt;1&lt;/sub&gt;(X) = X<a name="line.88"></a>
92 <FONT color="green">089</FONT> * T&lt;sub&gt;k+1&lt;/sub&gt;(X) = 2X T&lt;sub&gt;k&lt;/sub&gt;(X) - T&lt;sub&gt;k-1&lt;/sub&gt;(X)<a name="line.89"></a>
93 <FONT color="green">090</FONT> * &lt;/pre&gt;&lt;/p&gt;<a name="line.90"></a>
94 <FONT color="green">091</FONT> * @param degree degree of the polynomial<a name="line.91"></a>
95 <FONT color="green">092</FONT> * @return Chebyshev polynomial of specified degree<a name="line.92"></a>
96 <FONT color="green">093</FONT> */<a name="line.93"></a>
97 <FONT color="green">094</FONT> public static PolynomialFunction createChebyshevPolynomial(final int degree) {<a name="line.94"></a>
98 <FONT color="green">095</FONT> return buildPolynomial(degree, CHEBYSHEV_COEFFICIENTS,<a name="line.95"></a>
99 <FONT color="green">096</FONT> new RecurrenceCoefficientsGenerator() {<a name="line.96"></a>
100 <FONT color="green">097</FONT> private final BigFraction[] coeffs = { BigFraction.ZERO, BigFraction.TWO, BigFraction.ONE };<a name="line.97"></a>
101 <FONT color="green">098</FONT> /** {@inheritDoc} */<a name="line.98"></a>
102 <FONT color="green">099</FONT> public BigFraction[] generate(int k) {<a name="line.99"></a>
103 <FONT color="green">100</FONT> return coeffs;<a name="line.100"></a>
104 <FONT color="green">101</FONT> }<a name="line.101"></a>
105 <FONT color="green">102</FONT> });<a name="line.102"></a>
106 <FONT color="green">103</FONT> }<a name="line.103"></a>
107 <FONT color="green">104</FONT> <a name="line.104"></a>
108 <FONT color="green">105</FONT> /**<a name="line.105"></a>
109 <FONT color="green">106</FONT> * Create a Hermite polynomial.<a name="line.106"></a>
110 <FONT color="green">107</FONT> * &lt;p&gt;&lt;a href="http://mathworld.wolfram.com/HermitePolynomial.html"&gt;Hermite<a name="line.107"></a>
111 <FONT color="green">108</FONT> * polynomials&lt;/a&gt; are orthogonal polynomials.<a name="line.108"></a>
112 <FONT color="green">109</FONT> * They can be defined by the following recurrence relations:<a name="line.109"></a>
113 <FONT color="green">110</FONT> * &lt;pre&gt;<a name="line.110"></a>
114 <FONT color="green">111</FONT> * H&lt;sub&gt;0&lt;/sub&gt;(X) = 1<a name="line.111"></a>
115 <FONT color="green">112</FONT> * H&lt;sub&gt;1&lt;/sub&gt;(X) = 2X<a name="line.112"></a>
116 <FONT color="green">113</FONT> * H&lt;sub&gt;k+1&lt;/sub&gt;(X) = 2X H&lt;sub&gt;k&lt;/sub&gt;(X) - 2k H&lt;sub&gt;k-1&lt;/sub&gt;(X)<a name="line.113"></a>
117 <FONT color="green">114</FONT> * &lt;/pre&gt;&lt;/p&gt;<a name="line.114"></a>
118 <FONT color="green">115</FONT> <a name="line.115"></a>
119 <FONT color="green">116</FONT> * @param degree degree of the polynomial<a name="line.116"></a>
120 <FONT color="green">117</FONT> * @return Hermite polynomial of specified degree<a name="line.117"></a>
121 <FONT color="green">118</FONT> */<a name="line.118"></a>
122 <FONT color="green">119</FONT> public static PolynomialFunction createHermitePolynomial(final int degree) {<a name="line.119"></a>
123 <FONT color="green">120</FONT> return buildPolynomial(degree, HERMITE_COEFFICIENTS,<a name="line.120"></a>
124 <FONT color="green">121</FONT> new RecurrenceCoefficientsGenerator() {<a name="line.121"></a>
125 <FONT color="green">122</FONT> /** {@inheritDoc} */<a name="line.122"></a>
126 <FONT color="green">123</FONT> public BigFraction[] generate(int k) {<a name="line.123"></a>
127 <FONT color="green">124</FONT> return new BigFraction[] {<a name="line.124"></a>
128 <FONT color="green">125</FONT> BigFraction.ZERO,<a name="line.125"></a>
129 <FONT color="green">126</FONT> BigFraction.TWO,<a name="line.126"></a>
130 <FONT color="green">127</FONT> new BigFraction(2 * k)};<a name="line.127"></a>
131 <FONT color="green">128</FONT> }<a name="line.128"></a>
132 <FONT color="green">129</FONT> });<a name="line.129"></a>
133 <FONT color="green">130</FONT> }<a name="line.130"></a>
134 <FONT color="green">131</FONT> <a name="line.131"></a>
135 <FONT color="green">132</FONT> /**<a name="line.132"></a>
136 <FONT color="green">133</FONT> * Create a Laguerre polynomial.<a name="line.133"></a>
137 <FONT color="green">134</FONT> * &lt;p&gt;&lt;a href="http://mathworld.wolfram.com/LaguerrePolynomial.html"&gt;Laguerre<a name="line.134"></a>
138 <FONT color="green">135</FONT> * polynomials&lt;/a&gt; are orthogonal polynomials.<a name="line.135"></a>
139 <FONT color="green">136</FONT> * They can be defined by the following recurrence relations:<a name="line.136"></a>
140 <FONT color="green">137</FONT> * &lt;pre&gt;<a name="line.137"></a>
141 <FONT color="green">138</FONT> * L&lt;sub&gt;0&lt;/sub&gt;(X) = 1<a name="line.138"></a>
142 <FONT color="green">139</FONT> * L&lt;sub&gt;1&lt;/sub&gt;(X) = 1 - X<a name="line.139"></a>
143 <FONT color="green">140</FONT> * (k+1) L&lt;sub&gt;k+1&lt;/sub&gt;(X) = (2k + 1 - X) L&lt;sub&gt;k&lt;/sub&gt;(X) - k L&lt;sub&gt;k-1&lt;/sub&gt;(X)<a name="line.140"></a>
144 <FONT color="green">141</FONT> * &lt;/pre&gt;&lt;/p&gt;<a name="line.141"></a>
145 <FONT color="green">142</FONT> * @param degree degree of the polynomial<a name="line.142"></a>
146 <FONT color="green">143</FONT> * @return Laguerre polynomial of specified degree<a name="line.143"></a>
147 <FONT color="green">144</FONT> */<a name="line.144"></a>
148 <FONT color="green">145</FONT> public static PolynomialFunction createLaguerrePolynomial(final int degree) {<a name="line.145"></a>
149 <FONT color="green">146</FONT> return buildPolynomial(degree, LAGUERRE_COEFFICIENTS,<a name="line.146"></a>
150 <FONT color="green">147</FONT> new RecurrenceCoefficientsGenerator() {<a name="line.147"></a>
151 <FONT color="green">148</FONT> /** {@inheritDoc} */<a name="line.148"></a>
152 <FONT color="green">149</FONT> public BigFraction[] generate(int k) {<a name="line.149"></a>
153 <FONT color="green">150</FONT> final int kP1 = k + 1;<a name="line.150"></a>
154 <FONT color="green">151</FONT> return new BigFraction[] {<a name="line.151"></a>
155 <FONT color="green">152</FONT> new BigFraction(2 * k + 1, kP1),<a name="line.152"></a>
156 <FONT color="green">153</FONT> new BigFraction(-1, kP1),<a name="line.153"></a>
157 <FONT color="green">154</FONT> new BigFraction(k, kP1)};<a name="line.154"></a>
158 <FONT color="green">155</FONT> }<a name="line.155"></a>
159 <FONT color="green">156</FONT> });<a name="line.156"></a>
160 <FONT color="green">157</FONT> }<a name="line.157"></a>
161 <FONT color="green">158</FONT> <a name="line.158"></a>
162 <FONT color="green">159</FONT> /**<a name="line.159"></a>
163 <FONT color="green">160</FONT> * Create a Legendre polynomial.<a name="line.160"></a>
164 <FONT color="green">161</FONT> * &lt;p&gt;&lt;a href="http://mathworld.wolfram.com/LegendrePolynomial.html"&gt;Legendre<a name="line.161"></a>
165 <FONT color="green">162</FONT> * polynomials&lt;/a&gt; are orthogonal polynomials.<a name="line.162"></a>
166 <FONT color="green">163</FONT> * They can be defined by the following recurrence relations:<a name="line.163"></a>
167 <FONT color="green">164</FONT> * &lt;pre&gt;<a name="line.164"></a>
168 <FONT color="green">165</FONT> * P&lt;sub&gt;0&lt;/sub&gt;(X) = 1<a name="line.165"></a>
169 <FONT color="green">166</FONT> * P&lt;sub&gt;1&lt;/sub&gt;(X) = X<a name="line.166"></a>
170 <FONT color="green">167</FONT> * (k+1) P&lt;sub&gt;k+1&lt;/sub&gt;(X) = (2k+1) X P&lt;sub&gt;k&lt;/sub&gt;(X) - k P&lt;sub&gt;k-1&lt;/sub&gt;(X)<a name="line.167"></a>
171 <FONT color="green">168</FONT> * &lt;/pre&gt;&lt;/p&gt;<a name="line.168"></a>
172 <FONT color="green">169</FONT> * @param degree degree of the polynomial<a name="line.169"></a>
173 <FONT color="green">170</FONT> * @return Legendre polynomial of specified degree<a name="line.170"></a>
174 <FONT color="green">171</FONT> */<a name="line.171"></a>
175 <FONT color="green">172</FONT> public static PolynomialFunction createLegendrePolynomial(final int degree) {<a name="line.172"></a>
176 <FONT color="green">173</FONT> return buildPolynomial(degree, LEGENDRE_COEFFICIENTS,<a name="line.173"></a>
177 <FONT color="green">174</FONT> new RecurrenceCoefficientsGenerator() {<a name="line.174"></a>
178 <FONT color="green">175</FONT> /** {@inheritDoc} */<a name="line.175"></a>
179 <FONT color="green">176</FONT> public BigFraction[] generate(int k) {<a name="line.176"></a>
180 <FONT color="green">177</FONT> final int kP1 = k + 1;<a name="line.177"></a>
181 <FONT color="green">178</FONT> return new BigFraction[] {<a name="line.178"></a>
182 <FONT color="green">179</FONT> BigFraction.ZERO,<a name="line.179"></a>
183 <FONT color="green">180</FONT> new BigFraction(k + kP1, kP1),<a name="line.180"></a>
184 <FONT color="green">181</FONT> new BigFraction(k, kP1)};<a name="line.181"></a>
185 <FONT color="green">182</FONT> }<a name="line.182"></a>
186 <FONT color="green">183</FONT> });<a name="line.183"></a>
187 <FONT color="green">184</FONT> }<a name="line.184"></a>
188 <FONT color="green">185</FONT> <a name="line.185"></a>
189 <FONT color="green">186</FONT> /** Get the coefficients array for a given degree.<a name="line.186"></a>
190 <FONT color="green">187</FONT> * @param degree degree of the polynomial<a name="line.187"></a>
191 <FONT color="green">188</FONT> * @param coefficients list where the computed coefficients are stored<a name="line.188"></a>
192 <FONT color="green">189</FONT> * @param generator recurrence coefficients generator<a name="line.189"></a>
193 <FONT color="green">190</FONT> * @return coefficients array<a name="line.190"></a>
194 <FONT color="green">191</FONT> */<a name="line.191"></a>
195 <FONT color="green">192</FONT> private static PolynomialFunction buildPolynomial(final int degree,<a name="line.192"></a>
196 <FONT color="green">193</FONT> final ArrayList&lt;BigFraction&gt; coefficients,<a name="line.193"></a>
197 <FONT color="green">194</FONT> final RecurrenceCoefficientsGenerator generator) {<a name="line.194"></a>
198 <FONT color="green">195</FONT> <a name="line.195"></a>
199 <FONT color="green">196</FONT> final int maxDegree = (int) Math.floor(Math.sqrt(2 * coefficients.size())) - 1;<a name="line.196"></a>
200 <FONT color="green">197</FONT> synchronized (PolynomialsUtils.class) {<a name="line.197"></a>
201 <FONT color="green">198</FONT> if (degree &gt; maxDegree) {<a name="line.198"></a>
202 <FONT color="green">199</FONT> computeUpToDegree(degree, maxDegree, generator, coefficients);<a name="line.199"></a>
203 <FONT color="green">200</FONT> }<a name="line.200"></a>
204 <FONT color="green">201</FONT> }<a name="line.201"></a>
205 <FONT color="green">202</FONT> <a name="line.202"></a>
206 <FONT color="green">203</FONT> // coefficient for polynomial 0 is l [0]<a name="line.203"></a>
207 <FONT color="green">204</FONT> // coefficients for polynomial 1 are l [1] ... l [2] (degrees 0 ... 1)<a name="line.204"></a>
208 <FONT color="green">205</FONT> // coefficients for polynomial 2 are l [3] ... l [5] (degrees 0 ... 2)<a name="line.205"></a>
209 <FONT color="green">206</FONT> // coefficients for polynomial 3 are l [6] ... l [9] (degrees 0 ... 3)<a name="line.206"></a>
210 <FONT color="green">207</FONT> // coefficients for polynomial 4 are l[10] ... l[14] (degrees 0 ... 4)<a name="line.207"></a>
211 <FONT color="green">208</FONT> // coefficients for polynomial 5 are l[15] ... l[20] (degrees 0 ... 5)<a name="line.208"></a>
212 <FONT color="green">209</FONT> // coefficients for polynomial 6 are l[21] ... l[27] (degrees 0 ... 6)<a name="line.209"></a>
213 <FONT color="green">210</FONT> // ...<a name="line.210"></a>
214 <FONT color="green">211</FONT> final int start = degree * (degree + 1) / 2;<a name="line.211"></a>
215 <FONT color="green">212</FONT> <a name="line.212"></a>
216 <FONT color="green">213</FONT> final double[] a = new double[degree + 1];<a name="line.213"></a>
217 <FONT color="green">214</FONT> for (int i = 0; i &lt;= degree; ++i) {<a name="line.214"></a>
218 <FONT color="green">215</FONT> a[i] = coefficients.get(start + i).doubleValue();<a name="line.215"></a>
219 <FONT color="green">216</FONT> }<a name="line.216"></a>
220 <FONT color="green">217</FONT> <a name="line.217"></a>
221 <FONT color="green">218</FONT> // build the polynomial<a name="line.218"></a>
222 <FONT color="green">219</FONT> return new PolynomialFunction(a);<a name="line.219"></a>
223 <FONT color="green">220</FONT> <a name="line.220"></a>
224 <FONT color="green">221</FONT> }<a name="line.221"></a>
225 <FONT color="green">222</FONT> <a name="line.222"></a>
226 <FONT color="green">223</FONT> /** Compute polynomial coefficients up to a given degree.<a name="line.223"></a>
227 <FONT color="green">224</FONT> * @param degree maximal degree<a name="line.224"></a>
228 <FONT color="green">225</FONT> * @param maxDegree current maximal degree<a name="line.225"></a>
229 <FONT color="green">226</FONT> * @param generator recurrence coefficients generator<a name="line.226"></a>
230 <FONT color="green">227</FONT> * @param coefficients list where the computed coefficients should be appended<a name="line.227"></a>
231 <FONT color="green">228</FONT> */<a name="line.228"></a>
232 <FONT color="green">229</FONT> private static void computeUpToDegree(final int degree, final int maxDegree,<a name="line.229"></a>
233 <FONT color="green">230</FONT> final RecurrenceCoefficientsGenerator generator,<a name="line.230"></a>
234 <FONT color="green">231</FONT> final ArrayList&lt;BigFraction&gt; coefficients) {<a name="line.231"></a>
235 <FONT color="green">232</FONT> <a name="line.232"></a>
236 <FONT color="green">233</FONT> int startK = (maxDegree - 1) * maxDegree / 2;<a name="line.233"></a>
237 <FONT color="green">234</FONT> for (int k = maxDegree; k &lt; degree; ++k) {<a name="line.234"></a>
238 <FONT color="green">235</FONT> <a name="line.235"></a>
239 <FONT color="green">236</FONT> // start indices of two previous polynomials Pk(X) and Pk-1(X)<a name="line.236"></a>
240 <FONT color="green">237</FONT> int startKm1 = startK;<a name="line.237"></a>
241 <FONT color="green">238</FONT> startK += k;<a name="line.238"></a>
242 <FONT color="green">239</FONT> <a name="line.239"></a>
243 <FONT color="green">240</FONT> // Pk+1(X) = (a[0] + a[1] X) Pk(X) - a[2] Pk-1(X)<a name="line.240"></a>
244 <FONT color="green">241</FONT> BigFraction[] ai = generator.generate(k);<a name="line.241"></a>
245 <FONT color="green">242</FONT> <a name="line.242"></a>
246 <FONT color="green">243</FONT> BigFraction ck = coefficients.get(startK);<a name="line.243"></a>
247 <FONT color="green">244</FONT> BigFraction ckm1 = coefficients.get(startKm1);<a name="line.244"></a>
248 <FONT color="green">245</FONT> <a name="line.245"></a>
249 <FONT color="green">246</FONT> // degree 0 coefficient<a name="line.246"></a>
250 <FONT color="green">247</FONT> coefficients.add(ck.multiply(ai[0]).subtract(ckm1.multiply(ai[2])));<a name="line.247"></a>
251 <FONT color="green">248</FONT> <a name="line.248"></a>
252 <FONT color="green">249</FONT> // degree 1 to degree k-1 coefficients<a name="line.249"></a>
253 <FONT color="green">250</FONT> for (int i = 1; i &lt; k; ++i) {<a name="line.250"></a>
254 <FONT color="green">251</FONT> final BigFraction ckPrev = ck;<a name="line.251"></a>
255 <FONT color="green">252</FONT> ck = coefficients.get(startK + i);<a name="line.252"></a>
256 <FONT color="green">253</FONT> ckm1 = coefficients.get(startKm1 + i);<a name="line.253"></a>
257 <FONT color="green">254</FONT> coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])).subtract(ckm1.multiply(ai[2])));<a name="line.254"></a>
258 <FONT color="green">255</FONT> }<a name="line.255"></a>
259 <FONT color="green">256</FONT> <a name="line.256"></a>
260 <FONT color="green">257</FONT> // degree k coefficient<a name="line.257"></a>
261 <FONT color="green">258</FONT> final BigFraction ckPrev = ck;<a name="line.258"></a>
262 <FONT color="green">259</FONT> ck = coefficients.get(startK + k);<a name="line.259"></a>
263 <FONT color="green">260</FONT> coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])));<a name="line.260"></a>
264 <FONT color="green">261</FONT> <a name="line.261"></a>
265 <FONT color="green">262</FONT> // degree k+1 coefficient<a name="line.262"></a>
266 <FONT color="green">263</FONT> coefficients.add(ck.multiply(ai[1]));<a name="line.263"></a>
267 <FONT color="green">264</FONT> <a name="line.264"></a>
268 <FONT color="green">265</FONT> }<a name="line.265"></a>
269 <FONT color="green">266</FONT> <a name="line.266"></a>
270 <FONT color="green">267</FONT> }<a name="line.267"></a>
271 <FONT color="green">268</FONT> <a name="line.268"></a>
272 <FONT color="green">269</FONT> /** Interface for recurrence coefficients generation. */<a name="line.269"></a>
273 <FONT color="green">270</FONT> private static interface RecurrenceCoefficientsGenerator {<a name="line.270"></a>
274 <FONT color="green">271</FONT> /**<a name="line.271"></a>
275 <FONT color="green">272</FONT> * Generate recurrence coefficients.<a name="line.272"></a>
276 <FONT color="green">273</FONT> * @param k highest degree of the polynomials used in the recurrence<a name="line.273"></a>
277 <FONT color="green">274</FONT> * @return an array of three coefficients such that<a name="line.274"></a>
278 <FONT color="green">275</FONT> * P&lt;sub&gt;k+1&lt;/sub&gt;(X) = (a[0] + a[1] X) P&lt;sub&gt;k&lt;/sub&gt;(X) - a[2] P&lt;sub&gt;k-1&lt;/sub&gt;(X)<a name="line.275"></a>
279 <FONT color="green">276</FONT> */<a name="line.276"></a>
280 <FONT color="green">277</FONT> BigFraction[] generate(int k);<a name="line.277"></a>
281 <FONT color="green">278</FONT> }<a name="line.278"></a>
282 <FONT color="green">279</FONT> <a name="line.279"></a>
283 <FONT color="green">280</FONT> }<a name="line.280"></a>
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344 </PRE>
345 </BODY>
346 </HTML>