<jupyter_start><jupyter_text>Problem 2<jupyter_code>def bisection(func, interval, tol, max_iter = 100):
    low = interval[0]
    high = interval[1]
    if np.sign(func(low)) == np.sign(func(high)):
        raise ValueError("No root in interval [%s, %s]"%(low, high))
    
    midpoint = np.mean([low, high])
    history = []
    while ((high - low) / 2) >= tol and len(history) < max_iter:
        # split the interval
        midpoint = np.mean([low, high])
        
        if func(midpoint) == 0:
            break
            
        # Figure out which side to go to
        if np.sign(func(midpoint)) != np.sign(func(low)):
            high = midpoint
        else:
            low = midpoint
            
        history.append(midpoint)
    
    return midpoint, history<jupyter_output><empty_output><jupyter_text>Problem 3c<jupyter_code>f = lambda x : 2*x - 1 - np.sin(x)
x = np.linspace(-10, 10)
plt.plot(x, f(x))
plt.grid(alpha=0.25)
plt.plot(x, 0*x)
_ = plt.legend(["2x - 1 - sin(x)", "x=0"])
plt.show()
x = np.linspace(-10, 10)
plt.plot(x, np.sin(x))
plt.plot(x, 2*x - 1)
plt.grid(alpha=0.25)
_ = plt.legend(["sin(x)", "2x - 1"])
plt.show()
root, history = bisection(f, [0,2], tol = 1e-8)

for i, root in enumerate(history):
    print("Iter {:2d}, r={:.16f}".format(i,root))
x = np.linspace(0,2)
plt.plot(x, f(x))
plt.grid(alpha=0.25)
plt.plot(x, 0*x)
plt.plot(history, f(np.array(history)), 'o')
plt.plot(root, f(root), 'o', markersize=10)
_ = plt.legend(["2x - 1 - sin(x)", "x=0", "roots", "final root"])
plt.show()<jupyter_output><empty_output><jupyter_text>Probelm 3d<jupyter_code>compact = lambda x : (x-5)**9
poly = lambda x : np.polyval(np.poly([5]*9), x)
root_compact, history_compact = bisection(compact, (4.82, 5.2), tol=1e-4, max_iter=20)
root_poly, history_poly = bisection(poly, (4.82, 5.2), tol=1e-4, max_iter=20)
# Plot absolute error
true_answer = 5
plt.plot(abs(np.array(history_compact) - true_answer) ,'o-')
plt.plot(abs(np.array(history_poly) - true_answer) ,'o-')
plt.yscale('log')
plt.grid(alpha=0.25)
plt.minorticks_on()
plt.ylabel("Absolute error (log scale)");
plt.xlabel("Iteration");
plt.title("Error for the bisection method");
_ = plt.legend(["Compact", "Poly"])
plt.show()
# Run with lower tolerance to get a more complete plot
root_compact, history_compact = bisection(compact, (4.82, 5.2), tol=1e-16, max_iter=20)
root_poly, history_poly = bisection(poly, (4.82, 5.2), tol=1e-16, max_iter=20)
# Plot absolute error
true_answer = 5
fig, ax = plt.subplots()
plt.plot(abs(np.array(history_compact) - true_answer) ,'o-')
plt.plot(abs(np.array(history_poly) - true_answer) ,'o-')
ax.set_yscale('log')
ax.grid(alpha=0.25)
ax.minorticks_on()
ax.set_ylabel("Absolute error (log scale)");
ax.set_xlabel("Iteration");
ax.set_title("Error for the bisection method");

_ = plt.legend(["Compact", "Poly"])
plt.show()<jupyter_output><empty_output><jupyter_text>What is going on: It seems that, due to the lack of precision of the fully expanded polynomial version, the accuracy is no longer decreasing, so it has gotten "stuck", and cannot improve the guess.  Problem 4<jupyter_code># Define tent function to work with lists and with single values
def tent(mu, x):
    if np.shape(x) == ():
        # single value
        min_func = min
    else:
        # list, do elementwise
        min_func = np.minimum
    return mu * min_func(x, 1-x)
# Visualize tent for a few values of mu
x = np.linspace(0,1, 1000)
plt.plot(x, tent(0.5, x))
plt.plot(x, tent(1, x))
plt.plot(x, tent(1.5, x))
plt.plot(x, tent(2, x))
plt.plot(x, x, 'k')
plt.grid(alpha=0.25)
_ = plt.legend(["mu = 0.5", "mu = 1", "mu = 1.5", "mu = 2", "y = x"])
plt.show()
# Function to find fixed point of the tent function
def tent_fixed_point(mu, x0, maxiter=100, tol=1e-8):
    error = np.inf
    curr_iter = 0
    xs = []
    while(error > tol and curr_iter < maxiter):
        # iterate
        x = tent(mu, x0)
        error = np.linalg.norm(x0 - x)
        # append to history
        xs.append(x)
        curr_iter += 1
        x0 = x
    return x, xs
x_start = np.pi/6
mu = 1.1
xf, x_history = tent_fixed_point(mu, x_start, maxiter=10)
x_history = np.array(x_history)
x = np.linspace(0,1,100)
y = tent(mu, x)
plt.plot(x, y, 'b')
plt.plot(x_history, tent(mu, x_history), 'bo')
plt.plot(x_start, tent(mu, x_start), 'ro')
plt.plot(xf, tent(mu, xf), 'go')
plt.plot(x,x,'k')
plt.grid(alpha=0.25)
_ = plt.legend(["tent function (mu = %s)"%mu, "iterations", "start", "end", "y = x"])
plt.show()
x_start = np.pi/6
mu = 1.5
xf, x_history = tent_fixed_point(mu, x_start, maxiter=10)
x_history = np.array(x_history)
x = np.linspace(0,1,100)
y = tent(mu, x)
plt.plot(x, y, 'b')
plt.plot(x_history, tent(mu, x_history), '-bo')
plt.plot(x_start, tent(mu, x_start), 'ro')
plt.plot(xf, tent(mu, xf), 'go')
plt.plot(x,x,'k')
plt.grid(alpha=0.25)
_ = plt.legend(["tent function (mu = %s)"%mu, "iterations", "start", "end", "y = x"])
plt.show()
x_start = np.pi/6
mu = 1.1
xf, x_history = tent_fixed_point(mu, x_start, maxiter=10**6)
plt.hist(x_history)
plt.title("Histogram of fixed point iteration for mu = %s"%mu)
plt.xlabel("fixed point")
plt.ylabel("count")
plt.show()
x_start = np.pi/6
mu = 1.5
xf, x_history = tent_fixed_point(mu, x_start, maxiter=10**6)
plt.hist(x_history)
plt.title("Histogram of fixed point iteration for mu = %s"%mu)
plt.xlabel("fixed point")
plt.ylabel("count")
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1833641404805915, 'fraction_numerical': 0.03216266173752311, 'mean_word_length': 3.932543299908842, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '440658', 'license': 'BSD-3-Clause', 'n_tokens_mistral': 2354, 'n_tokens_neox': 2209, 'n_words': 512, 'path': 'Homework/my_solutions/HW2/hw2.ipynb', 'repo_name': 'skhadem/numerical-analysis-class', 'size': '5410'}