[Python] Recurrence Relations

1. Recurrence Relations

1.1 Arithmetic Sequence

Tk = T_k-1 + d
a_n = a₁ + (n-1)d

def arithmeticSequenceV1(a, d, n):
    for i in range(1,n):
        a = a + d
    return a

def arithmeticSequenceV2(a1, d, n):
    an = a1 + (n-1)*d
    return an

1.2 Geometric Sequence

Tk = T_k-1 * r
a_n = a₁ * r^n-1

def geometricSequenceV1(a, r, n):
    for i in range(1,n):
        a = a * r
    return a

def geometricSequenceV2(a1, r, n):
    an = a1 * (r**(n-1))
    return an

1.3 Fibonacci

F_n = F_n-1 + F_n-2     เมื่อ F₀ = 0 and F₁ = 1

def fibonacciV1(n): 
    if n < 0:
        print("Incorrect input")
        return None
    elif n == 1: 
        return 0
    elif n == 2: 
        return 1
    else: 
        return fibonacci(n-1) + fibonacci(n-2)

def fibonacciV2(n): 
    a = 0
    b = 1
    if n < 0: 
        print("Incorrect input")
        return None
    elif n == 0: 
        return a 
    elif n == 1: 
        return b 
    else: 
        for i in range(2,n): 
            c = a + b 
            a = b 
            b = c 
        return b 

1.4 Factorial

def factorial(n):
    fact = 1
    for i in range(1,n+1): 
        fact = fact * i 
    return fact

1.5 Tower of Hanoi

Take an example for 2 disks :
Let rod 1 = 'A', rod 2 = 'B', rod 3 = 'C'.

Step 1 : Shift first disk from 'A' to 'B'.
Step 2 : Shift second disk from 'A' to 'C'.
Step 3 : Shift first disk from 'B' to 'C'.

The pattern here is :
Shift 'n-1' disks from 'A' to 'B'.
Shift last disk from 'A' to 'C'.
Shift 'n-1' disks from 'B' to 'C'.

Image illustration for 3 disks :

Input : 2
Output : Disk 1 moved from A to B
         Disk 2 moved from A to C
         Disk 1 moved from B to C

Input : 3
Output : Disk 1 moved from A to C
         Disk 2 moved from A to B
         Disk 1 moved from C to B
         Disk 3 moved from A to C
         Disk 1 moved from B to A
         Disk 2 moved from B to C
         Disk 1 moved from A to C

def TowerOfHanoi(n, a, c, b): 
    if n == 1: 
        print("Move disk 1 from ",a," to ",c) 
    TowerOfHanoi(n-1, a, b, c) 
    print ("Move disk",n,"from ",a," to ",c)
    TowerOfHanoi(n-1, b, c, a) 

2. Taylor's Series for One Variable

เราใช้ taylor's series ในการประมาณการฟังก์ชันที่มีคุณสมบัติการลู่เข้า

ถ้า f(x) เป็นฟังก์ชันต่อเนื่อง ที่มีอนุพันธ์อันดับที่ n^th แล้ว taylor's series ของ f(x) ที่ใกล้เคียง (neighborhood) ของจุด x₀ กำหนดได้ดังนี้

3. Errors

3.1 Types of Errors

1. Inherent Error คือ เออเรอร์ที่มีอยู่แล้วในปัญหาตั้งแต่ก่อนสร้างโมเดลคณิตศาสตร์ เช่น การใช้ assumption ค่า θ แทน sin θ เพื่อให้คำนวณง่าย
2. Rounding Error คือ เออเรอร์จากการปัดเศษ เช่น ปัดทศนิยม
3. Truncation Error คือ เออเรอร์ที่จากการประมาณค่า เช่น การแทนซีรี่ย์อนันต์ด้วยชุดจำกัด

3.2 Calculation of Errors

Absolute Error  

e_abs = | exact value - approximate value |

Relative Error 

e_rel = e_abs / | exact value |

Percentage Error 

e_per = e_rel * 100%

Approximate Error 

e_app = ( V_new - V_new ) / | V_new |     and     V_{app per} = e_app * 100%

4. Stability Analysis

คือ การศึกษาว่า เออเรอร์โตขึ้นอย่างไรในระหว่างการคำนวณ

• Tweet
• Share
• Share
• Share
• Share

Sign up here with your email