Extra Homework 1 Solutions

• extra01.zip

Solutions: You can find the file with solutions for all questions here.

Newton's Method

Q1: Intersect

Implement intersect, which takes two functions f and g and their derivatives df and dg. It returns an intersection point x, at which f(x) is equal to g(x).

def intersect(f, df, g, dg):
    """Return where f with derivative df intersects g with derivative dg.

    >>> parabola, line = lambda x: x*x - 2, lambda x: x + 10
    >>> dp, dl = lambda x: 2*x, lambda x: 1
    >>> intersect(parabola, dp, line, dl)
    4.0
    """
    return find_zero(lambda x: f(x)-g(x), lambda x: df(x)-dg(x))

Q2: Polynomials

Differentiation of polynomials can be performed automatically by applying the product rule and the fact that the derivative of a sum is the sum of the derivatives of the terms.

In the following example, polynomials are expressed as two-argument Python functions. The first argument is the input x. The second argument called derive is True or False. When derive is True, the derivative is returned. When derive is False, the function value is returned.

For example, the quadratic function below returns a quadratic polynomial. The linear term X and constant function K are defined using conditional expressions.

X = lambda x, derive: 1 if derive else x
K = lambda k: lambda x, derive: 0 if derive else k

def quadratic(a, b, c):
    """Return a quadratic polynomial a*x*x + b*x + c.

    >>> q_and_dq = quadratic(1, 6, 8) # x*x + 6*x + 8
    >>> q_and_dq(1.0, False)  # value at 1
    15.0
    >>> q_and_dq(1.0, True)   # derivative at 1
    8.0
    >>> q_and_dq(-1.0, False) # value at -1
    3.0
    >>> q_and_dq(-1.0, True)  # derivative at -1
    4.0
    """
    A, B, C = K(a), K(b), K(c)
    AXX = mul_fns(A, mul_fns(X, X))
    BX = mul_fns(B, X)
    return add_fns(AXX, add_fns(BX, C))

To complete this implementation and apply Newton's method to polynomials, fill in the bodies of add_fns, mul_fns, and poly_zero below.

def add_fns(f_and_df, g_and_dg):
    """Return the sum of two polynomials."""
    return lambda x, derive: f_and_df(x, derive) + g_and_dg(x, derive)
def mul_fns(f_and_df, g_and_dg):
    """Return the product of two polynomials."""
    f, df = lambda x: f_and_df(x, False), lambda x: f_and_df(x, True)
    g, dg = lambda x: g_and_dg(x, False), lambda x: g_and_dg(x, True)
    def product(x, derive):
        if derive:
            return f(x) * dg(x) + df(x) * g(x)
        else:
            return f(x) * g(x)
    return product
def poly_zero(f_and_df):
    """Return a zero of polynomial f_and_df, which returns:
        f(x)  for f_and_df(x, False)
        df(x) for f_and_df(x, True)

    >>> q = quadratic(1, 6, 8)
    >>> round(poly_zero(q), 5) # Round to 5 decimal places
    -2.0
    >>> round(poly_zero(quadratic(-1, -6, -9)), 5)
    -3.0
    """
    return find_zero(lambda x: f_and_df(x, False), lambda x: f_and_df(x, True))

Q3: Cycles

Newton's method is not guaranteed to find a zero. One way that it can fail is due to a cycle: after applying k newton updates from an initial guess x, the result is x again.

Implement cycle, which returns an x near the given guess for which applying k Newton updates for the provided function f and its derivative df results in x. The doctests use a function print_updates which prints out the result of applying k Newton updates.

Hint: Part of your solution will involve computing the result of applying k updates from a starting point.

Hint: The provided differentiate function will find the derivative of a function automatically. The result is approximate, but good enough for this problem.

def print_updates(f, df, x, k, digits=4):
    """Print the first k Newton guesses for a zero of f, starting at x.

    >>> print_updates(lambda x: x*x - 2, lambda x: 2*x, 1, 4)
    1, 1.5, 1.4167, 1.4142, 1.4142
    """
    update = newton_update(f, df)
    guesses = [x]
    for _ in range(k):
        guesses.append(update(guesses[-1]))
    print(*[round(guess, digits) for guess in guesses], sep=', ')

def cycle(f, df, k, guess):
    """Find a k-step cycle in Newton's method starting near guess.

    >>> f = lambda x: x*x*x - 8*x*x + 17*x - 3
    >>> df = lambda x: 3*x*x - 16*x + 17
    >>> f(find_zero(f, df, 1)) # Starting at a guess of 1 finds a zero
    0.0
    >>> print_cycle = lambda k, x: print_updates(f, df, cycle(f, df, k, x), k)
    >>> print_cycle(3, 4.2)  # A 3-step cycle starting near 4.2
    4.2123, 3.7175, 4.7112, 4.2123
    >>> print_cycle(3, 3.7)  # A 3-step cycle starting near 3.7 (the same cycle)
    3.7175, 4.7112, 4.2123, 3.7175
    >>> print_cycle(5, 4)    # A 5-step cycle starting near 4
    4.003, 3.0234, 3.7591, 5.0564, 4.4548, 4.003
    """
    update = newton_update(f, df)

    def offset(x):
        original = x
        for _ in range(k):
            x = update(x)
        return x - original

    return find_zero(offset, differentiate(offset), guess)

Use Ok to test your code:

python3 ok -q cycle
Copy
✂️