# coding: utf-8
# # CSC338. Homework 8
#
# Due Date: Wednesday March 18, 9pm
#
# Please see the guidelines at https://www.cs.toronto.edu/~lczhang/338/homework.html
#
# ### What to Hand In
#
# Please hand in 2 files:
#
# - Python File containing all your code, named `hw8.py`.
# - PDF file named `hw8_written.pdf` containing your solutions to the written parts of the assignment. Your solution can be hand-written, but must be legible. Graders may deduct marks for illegible or poorly presented solutions.
#
# If you are using Jupyter Notebook to complete the work, your notebook can be exported as a .py file (File -> Download As -> Python). Your code will be auto-graded using Python 3.6, so please make sure that your code runs. There will be a 20% penalty if you need a remark due to small issues that renders your code untestable.
#
# **Make sure to remove or comment out all matplotlib or other expensive code before submitting your homework!**
#
# Submit the assignment on **MarkUs** by 9pm on the due date. See the syllabus for the course policy regarding late assignments. All assignments must be done individually.
# In[ ]:
import math
import numpy as np
# ## Question 1. Fixed-Point Iteration -- 3pts
#
# In homework 7, we considered using fixed-point iteration to find a root of the equation
# $f(x) = x^2 - 3x + 2 = 0$ using these functions:
#
# 1. $g_1(x) = \frac{x^2 + 2}{3}$
# 2. $g_2(x) = \sqrt{3x - 2}$
# 3. $g_3(x) = 3 - \frac{2}{x}$
#
# Analyze the convergence properties of each of the corresponding fixed-point iteration schemes
# for the root x = 2 by analyzing $g_i'(x)$.
# Do you expect the fix-point iteration to diverge or converge?
# Do these expectations match your empirical results from homework 7?
#
# ## Question 2. Newton's Method
#
# ### Part (a) -- 4 pts
#
# Write a function `newton` to find a root of `f(x)` using Newton's Method.
# This Python function should take as argument both the mathematical function `f` and
# its derivative `df`, and return a list of successively better estimates of a
# root of `f` obtained from applying Newton's method.
# In[ ]:
def newton(f, df, x, n=5):
""" Return a list of successively better estimate of a root of `f`
obtained from applying Newton's method. The argument `df` is the
derivative of the function `f`. The argument `x` is the initial estimate
of the root. The length of the returned list is `n + 1`.
Precondition: f is continuous and differentiable
df is the derivative of f
>>> def f(x):
... return x * x - 4 * np.sin(x)
>>> def df(x):
... return 2 * x - 4 * np.cos(x)
>>> newton(f, df, 3, n=5)
[3,
2.1530576920133857,
1.9540386420058038,
1.9339715327520701,
1.933753788557627,
1.9337537628270216]
"""
# ### Part (b) -- 2 pts
#
# Use your function from part (a) to solve for a root of
#
# $$f(x) = x^2 - 3x + 2 = 0$$
#
# Start with $x_0$ = 3, and stop when the root is accurate to at least 8 significant decimal digits.
#
# Show your work in your python file, and store the root you find in the variable `newton_root`.
# In[ ]:
def f(x):
return x ** 2 - 3 * x + 2
newton_root = None
# ### Part (c) -- 6 pts
#
# Consider the following non-linear equations $h_i(x) = 0$.
#
# 1. $h_1(x) = x^3 - 5x^2 + 8x - 4$
# 2. $h_2(x) = x cos(20x) - x$
# 3. $h_3(x) = e^{-2x} + e^{x} - x - 4$
#
# Write out the statement for updating the iterate $x_k$ using Newtonâ€™s
# method for solving each of the equations $h_i(x) = 0$.
#
# For each $h_i$, do you expect Newton's method to converge?
#
# Include your solution in your PDF writeup.
#
#
# ### Part (d) -- 3 pt
#
# Use the `newton` function to try and solve $h_i(x) = 0$, for `n = 100` iterations, starting with `x = 1.5`.
#
# Save the return values of calls to the function `newton` to the variables `newton_h1`, `newton_h2`, `newton_h3`,.
# In[ ]:
newton_h1 = None
newton_h2 = None
newton_h3 = None
# ## Question 3. Secant Method
#
# ### Part (a) [5 pt]
#
# Write a function `secant` to find a root of `f(x)` using the secant method.
# The function should return a list of successively better estimates of a
# root of `f` obtained from applying the secant method.
# In[ ]:
def secant(f, x0, x1, n=5):
""" Return a list of successively better estimate of a root of `f`
obtained from applying secant method. The arguments `x0` and `x1` are
the two starting guesses. The length of the returned list is `n + 2`.
>>> secant(lambda x: x ** 2 + x - 4, 3, 2, n=6)
[3,
2,
1.6666666666666667,
1.5714285714285714,
1.5617977528089888,
1.5615533980582523,
1.561552812843596,
1.5615528128088303]
"""
# ### Part (b) [1 pt]
#
# Use the `secant` function to find a root of $f(x) = x^3 + x^2 + x - 4$,
# accurate up to 8 significant decimal digits.
#
# Show your work in your Python file. You can choose starting positions $x_0$
# and $x_1$.
#
# Save the result in the variable `secant_root`.
# In[ ]:
secant_root = None
# ### Part (c) [4 pt]
#
# Show that the iterative method
#
# $$x_{k+1} = \frac{x_{k-1} f(x_k) - x_k f(x_{k-1})}{f(x_k) - f(x_{k-1})}$$
#
# is mathematically equivalent to the secant method for solving a scalar nonlinear equation $f(x) = 0$.
#
# Include your solution in your PDF writeup.
#
#
# ### Part (d) [2 pt]
#
# When implemented in finite-precision floating-point arithmetic, what advantages or disadvantages
# does the formula given in part (c) have compared with the formula for the secant method
# given in lecture?
#
# This is the formula given in lecture:
#
# $$x_{k+1} = x_k - f(x_k)\frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}$$
#
# Include your solution in your PDF writeup.