Anonymous user
Talk:Formal power series: Difference between revisions
m
moved Talk:Formal Power Series to Talk:Formal power series
(→Multiplication and division: No division) |
m (moved Talk:Formal Power Series to Talk:Formal power series) |
||
| (9 intermediate revisions by 5 users not shown) | |||
Line 16:
: I hope multiplication of the Ada solution is correct. As for division, it is impossible to implement because the result can infinite (example: 1-''x'') or non-existent (example: ''x''). --[[User:Dmitry-kazakov|Dmitry-kazakov]] 15:14, 10 March 2009 (UTC)
:: Division introduces two problems. One problem has to do with remainders (as in the 1/(1-x) or 1/x cases suggested by [[User:Dmitry-kazakov|Dmitry-kazakov]]), and the task specification did not specify how they should be treated. A related but deeper problem is that the quotient is not knowable unless every element can be inspected (or treated in some symbolic fashion). In other words, the Kth element of the result depends on the Jth element of the divisor and the (J+K)th element of the numerator for arbitrary K and J. In the general case, significant examples of both J and J+K can be infinite for any finite K. This problem becomes tractable when we deal with finite sequences (which, in essence, is what lazy evaluation gives us, though without the tractability). --[[User:Rdm|Rdm]] 19:32, 22 January 2010 (UTC)
It is like normal multiplication of polynomials, but done on (potentially) infinite elements (we shall truncate the series anyway at some point...) It is enough to do the right grouping according to the ''power'', so say you have (a<sub>0</sub> + a<sub>1</sub>x + ...) and (b<sub>0</sub> + b<sub>1</sub>x + ...) then you do what you would normally do: a<sub>0</sub> with all the b<sub>i</sub>x<sup>i</sup> and so on; but of course you must group equal powers. You could write it shortly as
<math>p_n = \sum_{i=0}^n a_ib_{n-i}x^n</math>
About division, it is possible: it should be enough that at least one ''coordinate'' is not zero. Of course, if it makes sense or not it still depends on the value where we shall compute the ''function''. The procedure (at least, done by hand...) is the same as for the multiplication. Then you compare the powers and find the right coefficients. On the fly I am not able to write it in a general form that is useful in order to write a computer algorithm, anyway it should be a start point (''a'' are the coeffs of the dividend, ''b'' of the divisor and ''c'' of the quotient):
<math>a_0+a_1x+a_2x^2+\dots = c_0b_0 + (c_0b_1+b_0c_1)x + (c_0b_2+c_1b_1+c_2b_0)x^2+\dots</math>
This is simply the multiplication, hence you obtain
<math>c_0=\frac{b_0}{a_0}</math>
<math>c_1=\frac{a_1-c_0b_1}{b_0}</math>
where you can substitute c<sub>0</sub> from the previous expression.
Apparently this gives inconsistent results when a coefficient is zero; but this is just because of this is not the right generalized formulation. You can try yourself with something like
<math>\frac{\cos x}{\sin x}=\sum_{i=0}^\infty c_ix^i</math>
expanding cos/sin as you know. Then you will see that having zero coeffs is not really a problem; doing it by hand is easier than thinking about a general algo that should work for every ''situation'' —I'm thinking about but not this wine-poisoned-evening (likely someone else more talented has already done it, but there's no fun without selfmade (re)discovering). --[[User:ShinTakezou|ShinTakezou]] 22:45, 10 March 2009 (UTC)
:No, it does not work. As I said above, divide 1 by ''x'':
<blockquote>
<math>\frac{1}{x}</math>
</blockquote>
:It just does not have Taylor series in ''x''<sub>0</sub>=0. As for the method you refer to. It is based on solving a linear equations system. The system for 1/''x'' does not have a solution (''a''<sub>0</sub>=1, ''b''<sub>0</sub>=0). That's it, it could not be otherwise. In other cases, like also mentioned above
<blockquote>
<math>\frac{1}{1-x}=\sum_{n=0}^\infty x^n</math> (sum of a geometric progression |x|<1)
</blockquote>
:the solution is infinite. And we ignored the convergence issue, so far. --[[User:Dmitry-kazakov|Dmitry-kazakov]] 09:36, 11 March 2009 (UTC)
:: There are several real problems. One is that we can't expand in 0 if the function (or any of the derivative) diverges in 0. Instead of sin, use the 1/x function itself to find its coefficients "directly" the same way you use for sin... Another problem is that we expand in powers of x where the exponent is positive, so it exists no expansion for x<sup>-1</sup>. We should drop Taylor series and use Laurent series (always with care I suppose). If we can "generate" the Taylor series in 0 for r(x), being r(x) = f(x)/g(x), then we can divide the expansion of f(x) (its formal power series) by the one for g(x). There are still problems anyway; e.g. if it exists N so that f<sub>i</sub> = 0 for i>N, and similar for g<sub>i</sub> but with M, and N<M, what happens? (Similar to 1/x case I suppose), at a glance this situation gives problem too. But this still does not say that division is '''always''' impossible. It is "sometimes"! --[[User:ShinTakezou|ShinTakezou]] 19:15, 11 March 2009 (UTC)
:::Yep, the task name is misleading. When it says "formal series" that gives an impression of some generalized framework for dealing with more or less '''any''' series, Fourier, Chebyshev, not just Taylor ones. Laurent series is yet another story. It goes in direction of approximations by rational polynomials, Padé etc. So what is the task about? The example of a definition of cos-sin has almost nothing to do with either series or approximations and how they are dealt with in real world. (I addressed this issue in a subthread.) --[[User:Dmitry-kazakov|Dmitry-kazakov]] 09:44, 12 March 2009 (UTC)
:::: I am trying to understand better, and it's why I still haven't added code: to me one thing is to "handle" a formal power series (big but still finite array for a computer language?), another thing is to ''generate'' a formal power series. The first can be accomplished without caring too much, we need only to put constraints over some coefficient for operations like / (maybe, not sure, enough the constant is not zero for the division? ... anyway still problems, since we indeed manipulate "finite" series, can arise, but maybe the task asks to disregard these details). I admit I've not taken a deep look to posted codes yet. --[[User:ShinTakezou|ShinTakezou]] 13:37, 13 March 2009 (UTC)
==About solving equations==
Line 58 ⟶ 96:
Summarizing: is the task accomplished even if the goals are (partially) missed? --[[User:ShinTakezou|ShinTakezou]] 17:30, 9 March 2009 (UTC)
== Java and generics ==
It was my understanding that generics had been added to Java recently, yet the Java example indicates that they're not available. A generic implementation would be far better than using the "swap out the type for the one you want" implementation it currently uses. --[[User:Short Circuit|Short Circuit]] 17:31, 17 May 2009 (UTC)
: Alas, <tt>java.lang.Number</tt> is not a very useful base-class in this regard, nor are its standard subclasses any better. In particular, there's no built in methods for performing arithmetic; those operations are only defined on the atomic numeric types, which can't participate in the generic type system. This means that the example would have to build its own type framework, and suddenly that's looking like real work and not elegant examples. (FWIW, the reason why the atomic types don't participate in the generics system is that they are treated specially by the JVM spec; addition on integers is completely different to addition on doubles. This would have forced recompilation for handling generic atomics, which was rejected as being silly and expensive. By contrast, swapping one object type for another is pretty straight-forward.) —[[User:Dkf|Dkf]] 21:40, 22 May 2009 (UTC)
| |||