1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from support.expr_types import *
from functools import cache
from support.canonicalize import *
from src.differentiation import evaluate_diff
from fractions import Fraction
EPSILON = 10**(-5)
MAX_ITER = 1000
INFINITY = 10**(1000)
ZERO = 10**(-1000)
@cache
def newton(f, x0, var):
"""
The goal of Newton's method is to find a zero of the provided function f w.r.t. the variable var.
It works by iteratively making guesses (with an initial guess of x0) until it's close enough to
a correct answer.
Some useful functions:
- abs(x): Takes the absolute value of x
- coerce_float(x): Converts any number (int, Fraction, Decimal, float) to a float for
comparison with other floats.
- evaluate_diff(expr, var): This is the function you wrote in the previous part!
- eval_expr(expr, {v1: val1, v2:, val2, ...}): Plugs in val1 for v1, val2 for v2, etc. into expr
and simplifies as much of expr as possible.
Algorithm:
Until we've tried MAX_ITER times...
Our current estimate is x_0.
Calculate f(x_0) and f'(x_0).
If both are at least INFINITY, assume we've failed.
If f'(x_0) is at most ZERO, assume we've failed.
Calculate a new estimate, x_1, where x_1 = x_0 - (f(x_0)/f'(x_0))
If we've converged on a value (x_0 and x_1 are close enough with tolerance EPSILON)...
If f(x_1) is close enough to 0 with tolerance EPSILON, we've found a zero! Return it!
Otherwise, assume we've failed.
"""
return None