Home > front end >  solving recurrence relations with far-off initial values
solving recurrence relations with far-off initial values

Time:04-28

I want to get values of a_1, a_2, ..., a_9 when setting the initial values of a_0 and a_10 and recurrence relation a_(i 2) = (a_(i 1))^2 / (a_i 0.5).

How should I write a code in python?

CodePudding user response:

You're problem can only be solved when a0 and a1 are given.

There are two ways to implement it. One recursive and one iterative approach. You should favor the iterative approach as it is much faster, needs constant memory and there is an upper limit for recursion depth in Python.

My implementation allows to set initial values for a0 and a1 as you please.

def rec_a(i, a0, a1):
    """
    Recursive function to calculate the i-th value of sequence
    :param i: i-th value of sequence for i >= 0
    :param a0: first value of sequence
    :param a1: seconds value of sequence
    :return: i-th value of sequence
    """
    if i < 0:
        raise ValueError("i must be >= 0")
    # the first value of sequence is a0
    if i == 0:
        return a0
    # the second value of sequence is a1
    if i == 1:
        return a1
    # all other sequences can now be calculated using recursion
    return rec_a(i - 1, a0, a1) ** 2 / (rec_a(i - 2, a0, a1)   0.5)


def a_iter(i, init_a0, init_a1):
    """
    Iterative function to calculate the i-th value of sequence
    :param init_a0: first value of sequence
    :param init_a1: seconds value of sequence
    :param i: i-th value of sequence for i >= 0

    :return: i-th value of sequence
    """
    if i < 0:
        raise ValueError("i must be >= 0")
    a0 = init_a0
    # first value of sequence is a0
    if i == 0:
        return a0
    a1 = init_a1
    for j in range(2, i   1):
        # calculate next sequence value
        a_next = a1 ** 2 / (a0   0.5)
        # shift all values a0 becomes a1, a1 becomes the next value of sequence (similar to iterative Fibonacci-number implementation)
        a0 = a1
        a1 = a_next
    return a1


initial_value_a0 = 2
initial_value_a1 = 1

# Calculate a_0
print(rec_a(0, initial_value_a0, initial_value_a1))
print(a_iter(0, initial_value_a0, initial_value_a1))

# Calculate a_1
print(rec_a(1, initial_value_a0, initial_value_a1))
print(a_iter(1, initial_value_a0, initial_value_a1))

# Calculate a_2
print(rec_a(2, initial_value_a0, initial_value_a1))
print(a_iter(2, initial_value_a0, initial_value_a1))

# Calculate a_4
print(rec_a(4, initial_value_a0, initial_value_a1))
print(a_iter(4, initial_value_a0, initial_value_a1))

# ValueError as 0 is first value of sequence
print(rec_a(-1, 1, 2))
print(a_iter(-1, 1, 2))

Expected output:

Traceback (most recent call last):
  File "main.py", line 60, in <module>
    print(rec_a(-1, 1, 2))
  File "main.py", line 10, in rec_a
    raise ValueError("i must be >= 0")
ValueError: i must be >= 0
2
2
1
1
0.4
0.4
0.01264197530864198
0.01264197530864198

As you can see both solutions yield the same result. Due to the recursion depth limit in Python the recursive solution will fail for large inputs.

CodePudding user response:

The following approach uses sympy, Python's symbolic math library. As the equations are of a high degree, a symbolic solver probably won't find a solution.

The code below supposes numeric values for a[0] and a[10] are given. A list of equations is generated following the recursion relation. (Note that in Python, ** is used for powers, while ^ is reserved for the boolean xor operation).

from sympy import Symbol, Eq, nsolve

a = [Symbol(f'a{i}') for i in range(11)]
a[0] = 1
a[10] = 20
eqs = [Eq(a[i   2], a[i   1] ** 2 / (a[i]   0.5)) for i in range(9)]

sol = nsolve(eqs, a[1:10], [1] * 9)
for i, a_i in enumerate(sol, start=1):
     print(f'a[{i}] = {a_i}')

Output:

a[1] = 2.65489718159571
a[2] = 4.69898602989657
a[3] = 6.99879217553299
a[4] = 9.42166253854625
a[5] = 11.8376030315757
a[6] = 14.1235246601829
a[7] = 16.1679662018854
a[8] = 17.8755216119038
a[9] = 19.1705616046603
  • Related