Classwork 4

INSERT YOUR NAME HERE

Directions: Add work to this notebook to solve the problems below.

Be careful to name the objects you create as described in the problem. Some problems may include some tests you can run to test your code.

This code below is used to conduct some of the provided tests. Execute it before working on the problems.

def _pass(s):
    s = s.replace('\n','<br/>')
    from IPython.display import HTML
    display(HTML(f'<span style="color: darkgreen; ">{s}</span>'))
_pass('Results of a successful test will be printed like this.')

def _fail(s, stop=True):
    s = s.replace('\n','<br/>')
    from IPython.display import HTML
    display(HTML(f'<span style="color: red; font-weight: bold; ">{s}</span>'))
    if stop:
        raise ValueError('You failed a test')
_fail('''Results of a failed test will be printed like this.
Typically a ValueError will also be raised, causing futher execution to stop.''', stop=False)

1. Higher dimensional Newton's method

A root of a function $f:\mathbb R^n \to \mathbb R^n$ is a vector $\mathbf x \in \mathbb R^n$ such that $f(\mathbf x)=\mathbf 0 \in \mathbb R^n$.

The linear approximation of a differentiable function $f$ at $x_0$ is given by $$L(\mathbf x) = f(\mathbf x_0) + [Df(\mathbf x_0)] (\mathbf x-\mathbf x_0),$$ where $Df(\mathbf x_0)$ is the matrix of partial derivatives. Given an approximate root $\mathbf x_0$, the next approximate given by Newton's method is the value $\mathbf x_1$ such that $L(\mathbf x_1)=\mathbf 0$.

Write a function newtons_method(f, x_0, n) which returns the point x_n obtained by applying Newton's method n times to the vector x_0. You may assume that f is a Sage function given say as

f(x,y,z) = (  x^2 + y^2 + z^2 - 25,
             (x-3)^2 + (y-2)^2 + (z-1)^2 - 25,
             (x-10)^2 + (y+3)^2 + (z+3)^2 - 10 )

To apply f to a vector x_0, you would use f(*x_0). The function sending a point to the derivative matrix can be obtained with Df = f.derivative(), and to find the derivative matrix at a particular point you could then do Df(*x_0).

The tests below assume your code does exact arithmetic.

Tests for your code:

The following finds the intersection between the circle of radius one in the plane and the line through the origin of slope $4/3$. So there are two roots: $\pm (3/5, 4/5)$.

f1(x,y) = (x^2+y^2-1, 4*x-3*y)
show(f1)

x_0 = vector(QQ, (1,1))
try:
    x_1 = newtons_method(f1, x_0, 1)
    print(f'x_1 is approximately {x_1.n()}')
    if vector(QQ,x_1) != vector(QQ, (9/14, 6/7)):
        _fail('The first application of Newton\'s method is incorrect.')
except Exception as e:
    _fail('Attempting to apply Newton\'s method once resulted in an error.')
_pass('Your code passed this test of one application of Newton\'s method.')

x_0 = vector(QQ, (1,1))
try:
    x_2 = newtons_method(f1, x_0, 2)
    print(f'x_2 is approximately {x_2.n()}')
    if vector(QQ,x_2) != vector(QQ, (421/700, 421/525)):
        _fail('The second application of Newton\'s method is incorrect.')
except Exception as e:
    _fail('Attempting to apply Newton\'s method twice resulted in an error.')
_pass('Your code passed this test of two applications.')

x_0 = vector(QQ, (1,1))
try:
    x_4 = newtons_method(f1, x_0, 4)
    print(f'x_4 is approximately {x_4.n()}')
    if abs(x_4-vector(QQ,[3/5,4/5])).n() > 10^-10:
        _fail('The forth application of Newton\'s method is incorrect.')
except Exception as e:
    _fail('Attempting to apply Newton\'s method four times resulted in an error.')
_pass('Your code passed this test of four applications.')

Here we attempt to find a point on the intersection of three spheres.

f2(x,y,z) = (x^2 + y^2 + z^2 - 25,
            (x-3)^2 + (y-2)^2 + (z-1)^2 - 25,
            (x-10)^2 + (y+3)^2 + (z+3)^2 - 100
           )
show(f2)

x_0 = vector(QQ, (3, -2, 3))
try:
    x_1 = newtons_method(f2, x_0, 1)
    print(f'x_1 is approximately {x_1.n()}')
    if vector(QQ,x_1) != vector(QQ, (695/268, -605/268, 1001/268)):
        _fail('The first application of Newton\'s method is incorrect.')
except Exception as e:
    _fail('Attempting to apply Newton\'s method once resulted in an error.')
_pass('Your code passed this test of one application of Newton\'s method.')

x_0 = vector(QQ, (3, -2, 3))
try:
    x_2 = newtons_method(f2, x_0, 2)
    print(f'x_2 is approximately {x_2.n()}')
    if vector(QQ,x_2) != vector(QQ, (19686719/7612808, -50503321/22838424, 83695139/22838424)):
        _fail('The second application of Newton\'s method is incorrect.')
except Exception as e:
    _fail('Attempting to apply Newton\'s method twice resulted in an error.')
_pass('Your code passed this test of two applications.')

x_0 = vector(QQ, (3, -2, 3))
try:
    x_5 = newtons_method(f2, x_0, 5)
    print(f'x_5 is approximately {x_2.n()}')
    if f2(*x_5).n().norm() > 10^-10:
        _fail('The 5th application of Newton\'s method is incorrect.')
except Exception as e:
    _fail('Attempting to apply Newton\'s method 5 times resulted in an error.')
_pass('Your code passed this test of 5 applications.')