Coverage for /usr/lib/python3/dist-packages/sympy/polys/polyfuncs.py: 15%

1"""High-level polynomials manipulation functions. """ 

2 

3 

4from sympy.core import S, Basic, symbols, Dummy 

5from sympy.polys.polyerrors import ( 

6 PolificationFailed, ComputationFailed, 

7 MultivariatePolynomialError, OptionError) 

8from sympy.polys.polyoptions import allowed_flags, build_options 

9from sympy.polys.polytools import poly_from_expr, Poly 

10from sympy.polys.specialpolys import ( 

11 symmetric_poly, interpolating_poly) 

12from sympy.polys.rings import sring 

13from sympy.utilities import numbered_symbols, take, public 

14 

15@public 

16def symmetrize(F, *gens, **args): 

17 r""" 

18 Rewrite a polynomial in terms of elementary symmetric polynomials. 

19 

20 A symmetric polynomial is a multivariate polynomial that remains invariant 

21 under any variable permutation, i.e., if `f = f(x_1, x_2, \dots, x_n)`, 

22 then `f = f(x_{i_1}, x_{i_2}, \dots, x_{i_n})`, where 

23 `(i_1, i_2, \dots, i_n)` is a permutation of `(1, 2, \dots, n)` (an 

24 element of the group `S_n`). 

25 

26 Returns a tuple of symmetric polynomials ``(f1, f2, ..., fn)`` such that 

27 ``f = f1 + f2 + ... + fn``. 

28 

29 Examples 

30 ======== 

31 

32 >>> from sympy.polys.polyfuncs import symmetrize 

33 >>> from sympy.abc import x, y 

34 

35 >>> symmetrize(x**2 + y**2) 

36 (-2*x*y + (x + y)**2, 0) 

37 

38 >>> symmetrize(x**2 + y**2, formal=True) 

39 (s1**2 - 2*s2, 0, [(s1, x + y), (s2, x*y)]) 

40 

41 >>> symmetrize(x**2 - y**2) 

42 (-2*x*y + (x + y)**2, -2*y**2) 

43 

44 >>> symmetrize(x**2 - y**2, formal=True) 

45 (s1**2 - 2*s2, -2*y**2, [(s1, x + y), (s2, x*y)]) 

46 

47 """ 

48 allowed_flags(args, ['formal', 'symbols']) 

49 

50 iterable = True 

51 

52 if not hasattr(F, '__iter__'): 

53 iterable = False 

54 F = [F] 

55 

56 R, F = sring(F, *gens, **args) 

57 gens = R.symbols 

58 

59 opt = build_options(gens, args) 

60 symbols = opt.symbols 

61 symbols = [next(symbols) for i in range(len(gens))] 

62 

63 result = [] 

64 

65 for f in F: 

66 p, r, m = f.symmetrize() 

67 result.append((p.as_expr(*symbols), r.as_expr(*gens))) 

68 

69 polys = [(s, g.as_expr()) for s, (_, g) in zip(symbols, m)] 

70 

71 if not opt.formal: 

72 for i, (sym, non_sym) in enumerate(result): 

73 result[i] = (sym.subs(polys), non_sym) 

74 

75 if not iterable: 

76 result, = result 

77 

78 if not opt.formal: 

79 return result 

80 else: 

81 if iterable: 

82 return result, polys 

83 else: 

84 return result + (polys,) 

85 

86 

87@public 

88def horner(f, *gens, **args): 

89 """ 

90 Rewrite a polynomial in Horner form. 

91 

92 Among other applications, evaluation of a polynomial at a point is optimal 

93 when it is applied using the Horner scheme ([1]). 

94 

95 Examples 

96 ======== 

97 

98 >>> from sympy.polys.polyfuncs import horner 

99 >>> from sympy.abc import x, y, a, b, c, d, e 

100 

101 >>> horner(9*x**4 + 8*x**3 + 7*x**2 + 6*x + 5) 

102 x*(x*(x*(9*x + 8) + 7) + 6) + 5 

103 

104 >>> horner(a*x**4 + b*x**3 + c*x**2 + d*x + e) 

105 e + x*(d + x*(c + x*(a*x + b))) 

106 

107 >>> f = 4*x**2*y**2 + 2*x**2*y + 2*x*y**2 + x*y 

108 

109 >>> horner(f, wrt=x) 

110 x*(x*y*(4*y + 2) + y*(2*y + 1)) 

111 

112 >>> horner(f, wrt=y) 

113 y*(x*y*(4*x + 2) + x*(2*x + 1)) 

114 

115 References 

116 ========== 

117 [1] - https://en.wikipedia.org/wiki/Horner_scheme 

118 

119 """ 

120 allowed_flags(args, []) 

121 

122 try: 

123 F, opt = poly_from_expr(f, *gens, **args) 

124 except PolificationFailed as exc: 

125 return exc.expr 

126 

127 form, gen = S.Zero, F.gen 

128 

129 if F.is_univariate: 

130 for coeff in F.all_coeffs(): 

131 form = form*gen + coeff 

132 else: 

133 F, gens = Poly(F, gen), gens[1:] 

134 

135 for coeff in F.all_coeffs(): 

136 form = form*gen + horner(coeff, *gens, **args) 

137 

138 return form 

139 

140 

141@public 

142def interpolate(data, x): 

143 """ 

144 Construct an interpolating polynomial for the data points 

145 evaluated at point x (which can be symbolic or numeric). 

146 

147 Examples 

148 ======== 

149 

150 >>> from sympy.polys.polyfuncs import interpolate 

151 >>> from sympy.abc import a, b, x 

152 

153 A list is interpreted as though it were paired with a range starting 

154 from 1: 

155 

156 >>> interpolate([1, 4, 9, 16], x) 

157 x**2 

158 

159 This can be made explicit by giving a list of coordinates: 

160 

161 >>> interpolate([(1, 1), (2, 4), (3, 9)], x) 

162 x**2 

163 

164 The (x, y) coordinates can also be given as keys and values of a 

165 dictionary (and the points need not be equispaced): 

166 

167 >>> interpolate([(-1, 2), (1, 2), (2, 5)], x) 

168 x**2 + 1 

169 >>> interpolate({-1: 2, 1: 2, 2: 5}, x) 

170 x**2 + 1 

171 

172 If the interpolation is going to be used only once then the 

173 value of interest can be passed instead of passing a symbol: 

174 

175 >>> interpolate([1, 4, 9], 5) 

176 25 

177 

178 Symbolic coordinates are also supported: 

179 

180 >>> [(i,interpolate((a, b), i)) for i in range(1, 4)] 

181 [(1, a), (2, b), (3, -a + 2*b)] 

182 """ 

183 n = len(data) 

184 

185 if isinstance(data, dict): 

186 if x in data: 

187 return S(data[x]) 

188 X, Y = list(zip(*data.items())) 

189 else: 

190 if isinstance(data[0], tuple): 

191 X, Y = list(zip(*data)) 

192 if x in X: 

193 return S(Y[X.index(x)]) 

194 else: 

195 if x in range(1, n + 1): 

196 return S(data[x - 1]) 

197 Y = list(data) 

198 X = list(range(1, n + 1)) 

199 

200 try: 

201 return interpolating_poly(n, x, X, Y).expand() 

202 except ValueError: 

203 d = Dummy() 

204 return interpolating_poly(n, d, X, Y).expand().subs(d, x) 

205 

206 

207@public 

208def rational_interpolate(data, degnum, X=symbols('x')): 

209 """ 

210 Returns a rational interpolation, where the data points are element of 

211 any integral domain. 

212 

213 The first argument contains the data (as a list of coordinates). The 

214 ``degnum`` argument is the degree in the numerator of the rational 

215 function. Setting it too high will decrease the maximal degree in the 

216 denominator for the same amount of data. 

217 

218 Examples 

219 ======== 

220 

221 >>> from sympy.polys.polyfuncs import rational_interpolate 

222 

223 >>> data = [(1, -210), (2, -35), (3, 105), (4, 231), (5, 350), (6, 465)] 

224 >>> rational_interpolate(data, 2) 

225 (105*x**2 - 525)/(x + 1) 

226 

227 Values do not need to be integers: 

228 

229 >>> from sympy import sympify 

230 >>> x = [1, 2, 3, 4, 5, 6] 

231 >>> y = sympify("[-1, 0, 2, 22/5, 7, 68/7]") 

232 >>> rational_interpolate(zip(x, y), 2) 

233 (3*x**2 - 7*x + 2)/(x + 1) 

234 

235 The symbol for the variable can be changed if needed: 

236 >>> from sympy import symbols 

237 >>> z = symbols('z') 

238 >>> rational_interpolate(data, 2, X=z) 

239 (105*z**2 - 525)/(z + 1) 

240 

241 References 

242 ========== 

243 

244 .. [1] Algorithm is adapted from: 

245 http://axiom-wiki.newsynthesis.org/RationalInterpolation 

246 

247 """ 

248 from sympy.matrices.dense import ones 

249 

250 xdata, ydata = list(zip(*data)) 

251 

252 k = len(xdata) - degnum - 1 

253 if k < 0: 

254 raise OptionError("Too few values for the required degree.") 

255 c = ones(degnum + k + 1, degnum + k + 2) 

256 for j in range(max(degnum, k)): 

257 for i in range(degnum + k + 1): 

258 c[i, j + 1] = c[i, j]*xdata[i] 

259 for j in range(k + 1): 

260 for i in range(degnum + k + 1): 

261 c[i, degnum + k + 1 - j] = -c[i, k - j]*ydata[i] 

262 r = c.nullspace()[0] 

263 return (sum(r[i] * X**i for i in range(degnum + 1)) 

264 / sum(r[i + degnum + 1] * X**i for i in range(k + 1))) 

265 

266 

267@public 

268def viete(f, roots=None, *gens, **args): 

269 """ 

270 Generate Viete's formulas for ``f``. 

271 

272 Examples 

273 ======== 

274 

275 >>> from sympy.polys.polyfuncs import viete 

276 >>> from sympy import symbols 

277 

278 >>> x, a, b, c, r1, r2 = symbols('x,a:c,r1:3') 

279 

280 >>> viete(a*x**2 + b*x + c, [r1, r2], x) 

281 [(r1 + r2, -b/a), (r1*r2, c/a)] 

282 

283 """ 

284 allowed_flags(args, []) 

285 

286 if isinstance(roots, Basic): 

287 gens, roots = (roots,) + gens, None 

288 

289 try: 

290 f, opt = poly_from_expr(f, *gens, **args) 

291 except PolificationFailed as exc: 

292 raise ComputationFailed('viete', 1, exc) 

293 

294 if f.is_multivariate: 

295 raise MultivariatePolynomialError( 

296 "multivariate polynomials are not allowed") 

297 

298 n = f.degree() 

299 

300 if n < 1: 

301 raise ValueError( 

302 "Cannot derive Viete's formulas for a constant polynomial") 

303 

304 if roots is None: 

305 roots = numbered_symbols('r', start=1) 

306 

307 roots = take(roots, n) 

308 

309 if n != len(roots): 

310 raise ValueError("required %s roots, got %s" % (n, len(roots))) 

311 

312 lc, coeffs = f.LC(), f.all_coeffs() 

313 result, sign = [], -1 

314 

315 for i, coeff in enumerate(coeffs[1:]): 

316 poly = symmetric_poly(i + 1, roots) 

317 coeff = sign*(coeff/lc) 

318 result.append((poly, coeff)) 

319 sign = -sign 

320 

321 return result