Rekursion



  • Hi, ich schon wieder...:)
    Kann mir jemand sagen wie ich dies mittels Schleife und Rekursion für die Berechnung von Pn(x) für ein zulässiges x und n algorithmiere?
    P1(x)=1
    P2(x)=x;
    n*Pn(x)=(2n-1)x*P_n-1(x)-(n-1)P_n-2(x) für n=2,3... .
    Schöne Grüße
    MIkka



  • rek:
    int P(int n,double x){
      if(n<=1) //Fehler in Deiner Definition. P2(x) bezieht sich auf P0(x)! Deshalb <=
        return 1;
      else
        return (2*n-1)*x*P(n-1,x)-(n-1)*P(n-2,x);
    }
    iter:
    int P(int n,double x){
      double a,b=1,c={rechne selber P1(x) aus};
      for(int i=2;i<=n;++i){
        a=b,b=c;
        c=(2*n-1)*x*b-(n-1)*a;
      }
      return c;
    }
    


  • n*Pn(x) = ...

    Also noch durch n teilen.



  • Oh cool...vielen Dank!
    VG Mikka



  • mikka7019 schrieb:

    P1(x)=1
    P2(x)=x;
    n*Pn(x)=(2n-1)x*P_n-1(x)-(n-1)P_n-2(x) für n=2,3... .

    Hallo Mikka,

    wie nennt man dieses Polynom? Es sieht so ähnlich aus wie das Tschebyschow-Polynom und hat auch ähnliche Eigenschaften. Gibt es einen Namen für Pn(x)?

    Gruß
    Werner



  • Ich glaub das sind die Legendre-Polynome.



  • Ist N bei dir eine Compilezeit-Konstante? Dann kann man den Laufzeit-Aufwand der Rechnungen deutlich reduzieren.

    Laut Wikipedia ist eine alternative Darstellung der Polynome

    P\_n(x) = \sum\_{k=0}^{k_\mathrm{MAX}} (-1)^k \frac{(2n - 2k)! \ x^{n-2k}}{(n-k)! \ (n-2k)! \ k! \ 2^n}$$, mit $$k_\text{MAX} = \begin{cases} \frac{n}{2} & n \ \text{gerade}\\ \frac{n-1}{2} & n \ \text{ungerade} \end{cases}

    Das heißt $$P_n(x) = \sum_{k=0}^{k_\mathrm{MAX}} c(n,k) x^{n-2k}$$ mit $$c(n,k) = (-1)^k \frac{(2n - 2k)! }{(n-k)! \ (n-2k)! \ k! \ 2^n}$$

    c rekursiv definiert ergibt $$c(n,k) = c(n,k-1) \cdot -\frac{(n-k+1) \ (n-2k+1)(n-2k+2)}{k(2n-2k+1)(2n-2k+2)}$$ für k>0 und

    c(n,0)=(2n)!n! n!2nc(n,0) = \frac{(2n)!}{n! \ n! 2^n}

    Definiert man jetzt $$s(n,i,x) = \sum_{k=0}^{i} c(n,k) x^{n-2k}$$ und $$s(n,0,x) = c(n,0) x^{n}$$
    Kann man auch s rekusiv definieren als $$s(n,i,x) = c(n,i) x^{n-2i} + s(n,i-1,x)$$

    als einziges "schwierig" zu berechnen (im Sinne von C++-Compilezeit Berechnungen) ist dabei jetzt noch die Potenz von x, die durch eine Hilfsvariable y=x^(n-2i+2) gelöst werden kann:

    s(n,i,x,y) = c(n,i) y + s(n,i-1,x, y\*x\*x)

    Alles zusammen ergibt sich

    P\_n(x) = s(n,k\_\mathrm{MAX},x,y_0)$$ mit $$y_0 = \begin{cases} 1 & n \ \text{gerade}\\ x & n \ \text{ungerade} \end{cases}

    Als Template-möglichst-Meta-Programm:

    template <int N>
    struct fac { enum {value = N*fac<N-1>::value}; };
    template <>
    struct fac<0> {enum {value = 1};};
    
    template <int N, int I>
    struct S
    {
      const static int c = -( (N-I+1)*(N-2*I+1)*(N-2*I+2) ) / ( I*(2*N-2*I+1)*(2*N-2*I+2) ) * S<N, I-1>::c;
    
      static double eval(double x, double y)
      {
        return c*y + S<N, I-1>::eval(x, y*x*x);
      }
    };
    
    template <int N>
    struct S<N,0>
    {
      const static int c = fac<2*N>::value / (fac<N>::value * fac<N>::value * (1<<N));
    
      static double eval(double x, double y)
      {
        return c*y;
      }
    };
    
    template <int N>
    struct P
    {
      double operator()(double x)
      {
        return S<N,N/2>::eval(x, (N%2) ? 1.0 : x);
      }
    };
    

    Hier werden jetzt bei gegebenem N alle Koeffizienten zur Compilezeit ausgerechnet, zur Laufzeit gibts pro Berechnung N Multiplikationen und N/2 Additionen.

    Ungetestet und evtl. noch mit Fehlern...


Anmelden zum Antworten