Wie löst man Wiederholungsrelationen in Python

Question

Ich versuche, Code zu schreiben, um numerische Antworten auf eine Wiederholungsrelation zu geben. Die Beziehung selbst ist einfach und wie folgt definiert. Die Variable x ist eine ganze Zahl

• p (i) = p (i + 2)/2 + p (i-1)/2, wenn i> 0 und i < x
• p (0) = p (2)/2
• p (i) = 1 wenn i> = x

Dies ist auch in diesem Code.

from __future__ import division 
def p(i): 
    if (i == 0): 
     return p(2)/2 
    if (i >= x): 
     return 1 
    return p(i-1)/2+p(i+2)/2 


x = 4 
#We would like to print p(0) for example. 

Dies ermöglicht natürlich nicht die Berechnung von p (0). Wie kannst du das in Python machen?

---

Ist es möglich, ein System simultaner Gleichungen aufzustellen, die numpy.linalg.solve dann lösen kann?

Answer 1

Sie haben Recht, das kann mit linearer Algebra gelöst werden. Was ich unten getan habe, ist eine einfache, hartcodierte Übersetzung. Ihre Gleichungen für p(0) bis p(3) sind codiert, indem Sie sie so umordnen, dass die rechte Seite =0 ist. Für p(4) und p(5), die in den Wiederholungsrelationen als Basisfälle auftreten, befindet sich auf der rechten Seite ein =1.

• -p(0) + p(2)/2 = 0

• p(i-1)/2 - p(i) + p(i+2)/2 = 0 für i> 0 und i < x

• p(i) = 1 wenn i> = x

Hier ist das Programm für n=4 fest einprogrammiert

import numpy 
a=numpy.array([[-1, 0, 0.5, 0, 0, 0], # 0 
       [0.5, -1, 0,0.5, 0, 0], # 1 
       [0, 0.5, -1, 0, 0.5, 0], # 2 
       [0, 0, 0.5, -1, 0, 0.5], # 3 
       [0, 0, 0, 0, 1, 0], # 4 
       [0, 0, 0, 0, 0, 1], # 5 
       ]) 
b=numpy.array([0,0,0,0,1,1]) 
# solve ax=b 
x = numpy.linalg.solve(a, b) 
print x 

Bearbeiten, hier ist der Code, der die Matrix programmgesteuert erstellt, nur für n=4 getestet!

n = 4 

# construct a 
diag = [-1]*n + [1]*2 
lowdiag = [0.5]*(n-1) + [0]*2 
updiag = [0.5]*n 
a=numpy.diag(diag) + numpy.diag(lowdiag, -1) + numpy.diag(updiag, 2) 

# solve ax=b 
b=numpy.array([0]*n + [1]*2) 
x = numpy.linalg.solve(a, b) 

print a 
print x[:n] 

Diese gibt

[[-1. 0. 0.5 0. 0. 0. ] 
[ 0.5 -1. 0. 0.5 0. 0. ] 
[ 0. 0.5 -1. 0. 0.5 0. ] 
[ 0. 0. 0.5 -1. 0. 0.5] 
[ 0. 0. 0. 0. 1. 0. ] 
[ 0. 0. 0. 0. 0. 1. ]] 
[ 0.41666667 0.66666667 0.83333333 0.91666667] 

, die die Lösung in Ihrem Kommentar unter Ihrer Frage passt.

Answer 2

Ich bin verwirrt, weil Ihr Code scheint, dass es genau das tun sollte.

def p(i): 
    x = 4 # your constant should be defined in-function 

    if (i == 0): 
     return p(2)/2 
    elif (i >= x): 
     return 1 
    return p(i-1)/2+p(i+2)/2 

Das große Problem hier ist Ihre Rekursion. Für p(1) es tut:

p(0)/2     +     p(3)/2 
p(2)/2     +   p(2)/2 + p(4)/2 
p(1)/2     +    p(1)/2 + 1/2 
# each side of the operator is now the same as the original problem! 
# that's a sure sign of infinite recursion. 

Was erwartest du die Ausgabe sein?

Answer 3

Das Problem hier ist, dass Sie in einer unendlichen Rekursion landen, unabhängig davon, wo Sie anfangen, weil die Rekursion nicht explizit ist, sondern am Ende ergibt Systeme lineare Gleichungen zu lösen. Wenn dies ein Problem war, das Sie mit Python lösen mussten, würde ich Python verwenden, um die Koeffizienten dieses Gleichungssystems zu berechnen und Cramers Regel zu verwenden, um es zu lösen.

Bearbeiten: Insbesondere sind Ihre Unbekannten p (0), ..., p (x-1). Ein Koeffizient-Reihenvektor rechts von der Fledermaus ist (1, 0, -1/2, 0, ..., 0) (von p (0) -p (2)/2 = 0), und alle anderen sind von die Form (..., -1/2, 1, 0, -1/2, ...). Es gibt x-1 davon (eins für jedes von p (1), ..., p (x-1)), so dass das System entweder eine eindeutige oder gar keine Lösung hat. Intuitiv scheint es, dass es immer eine einzigartige Lösung geben sollte.

Die beiden letzten Gleichungen wären einzigartig, da sie p (x) und p (x + 1) enthalten würden, also würden diese Terme weggelassen; der Spaltenvektor für die RHS von Cramers Regel wäre dann (0, 0, ..., 0, 1/2, 1/2), glaube ich.

Numpy hat Matrixunterstützung.