<jupyter_start><jupyter_text>Nonlinear Equations  Outline1. Setup2. Bisection method3. Function iteration4. Newton's method5. Quasi-Newton method6. Choosing a solution method7. Convergence8. Resources  Setup The nonlinear equation takes one of two forms.* **Rootfinding problem** Given a function $f: R^n \mapsto R^n$,compute an $n$-vector $x^*$, called root of $f$, such that $f(x^*) = 0$.* **Fixed-point problem** Given a function $g: R^n \mapsto R^n$, compute an $n$-vector $x^*$ called fixed point of $g$ such that $g(x^*) = x^*$The two forms are equivalent.* A root of $f$ is a fixed-point of $g(x) = x - f(x)$.* A fixed-point of $g$ is a root ot $f(x) = x - g(x)$.Nonlinear equations arise naturally in economics:* Multicommodity market equilibrium models* Multiperson static game models * Unconstrained optimization modelsNonlinear equations also arise indirectly when numerically solving economic models involving functional equations:* Dynamic optimization models * Rational expectations models * Arbitrage pricing modelsBuilding on our earlier lecture on the solution to linear systems of equations, often the solution to a nonlinear problem is computed iteratively by solving a sequence of linear problems. * sensitivity to intial condition* susceptible to rounding error<jupyter_code># access python PATH

import sys
sys.path # here, jupyter looks for python libraries that we try to import
#from temfpy.nonlinear_equations import exponential  # noqa: F401
from scipy import optimize
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

from nonlinear_algorithms import bisect
from nonlinear_plots import plot_bisection_test_function

from nonlinear_algorithms import fixpoint
from nonlinear_plots import plot_fixpoint_example
from nonlinear_plots import plot_newton_pathological_example
from nonlinear_plots import plot_convergence
from nonlinear_plots import plot_newtons_method
from nonlinear_plots import plot_secant_method

from nonlinear_algorithms import newton_method

from nonlinear_problems import bisection_test_function
from nonlinear_problems import function_iteration_test_function
from nonlinear_problems import newton_pathological_example<jupyter_output><empty_output><jupyter_text>Bisection methodWe start with the implementation (and testing) of the bisection algorithm.* The bisection method is perhaps the simplest and most robust method for computing the root of a continuous real-valued function defined on a bounded interval of the real line. The bisection method is based on the Intermediate Value Theorem, which asserts that if a continuous real-valued function defined on an interval assumes two distinct values, then it must assume all values in between. In particular, if $f$ is continuous, and $f (a)$ and $f (b)$ have different signs, then $f$ must have at least one root $x$ in $[a, b]$.* Each iteration begins with an interval known to contain or to bracket a root of $f$, because the function has different signs at the interval endpoints. The interval is bisected into two subintervals of equal length. One of the two subintervals must have endpoints of different signs and thus must contain a root of $f$. This subinterval is taken as the new interval with which to begin the subsequent iteration. In this manner, a sequence of intervals is generated, each half the width of the preceding one, and each known to contain a root of $f$. The process continues until the width of the bracketing interval containing a root shrinks below an acceptable convergence tolerance.<jupyter_code>def bisect_prototype(f, a, b, tolerance=1e-8):
    
    # Get sign of f(a)
    s = np.sign(f(a))
    
    # Get starting values for x and interval length
    x = (a+b)/2
    d = (b-a)/2
    
    xvals = [x] # use list since we don't know how long our array would have to be
    
    while d > tolerance:
        d = d/2
        if s == np.sign(f(x)):
            x += d
        else:
            x -= d
        xvals.append(x)
        
    return x, np.array(xvals)<jupyter_output><empty_output><jupyter_text>Let's visualize a test function to get a sense of what result can should expect.<jupyter_code>??bisection_test_function
fig, ax = plt.subplots() # use seaborn for matplotlib with nice default settings; bokeh for interactive visualization
grid = np.linspace(1,2)

values = list()
for value in grid:
    values.append(bisection_test_function(value))

# alternative for loop:
# values = bisection_test_function(grid)
    
ax.plot(grid,values)
ax.axes.axhline(0,color='grey')
ax.set_xlabel('$x^2$')<jupyter_output><empty_output><jupyter_text>* The ability to vectorize functions using [np.vectorize](https://numpy.org/doc/stable/reference/generated/numpy.vectorize.html) comes in very handy when evaluating functions over a grid. However, be aware that this is a simple replacement of a `for loop` and thus does not improve performance.  We are ready to go ...<jupyter_code>tol = 1e-10
lower, upper = 1,2
x, xvals = bisect_prototype(bisection_test_function, lower, upper, tolerance = tol)

print(f"Number of function evaluations: {len(xvals)} Root: {x}")<jupyter_output>Number of function evaluations: 34 Root: 1.2599210498738103<jupyter_text>Now we are ready to check our implementation and investigate the sensitivity of results to alternative tuning parameter.<jupyter_code>np.testing.assert_almost_equal(bisection_test_function(x) , 0)

fig, ax = plt.subplots()
ax.plot(np.linspace(1, len(xvals), len(xvals)), xvals)
ax.set_xlabel('iteration')
ax.set_ylabel('$x$')
plt.show()
# Solution Alexandros

def test_root(f, root, error=1e-6, true_sol=None):
    if f(root)<error:
        print("Root is sufficiently accurate.")
        return True
    else:
        print(f"Root is of, f(x)={f(root):6.6f}")
        return false
test_root(bisection_test_function, x)
def plot_iterates(vals):
    fix,ax = plt.subplots()
    
    ax.set_yscale('log')
    ax.scatter(range(len(xvals)), xvals-x)
    plt.show()
    
plot_iterates(xvals)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07934131736526946, 'fraction_numerical': 0.008483033932135729, 'mean_word_length': 4.798457087753134, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 1, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '249418', 'license': 'MIT', 'n_tokens_mistral': 1796, 'n_tokens_neox': 1712, 'n_words': 700, 'path': 'labs/nonlinear_equations/notebook_canvas.ipynb', 'repo_name': 'MImmesberger/ose-course-scientific-computing', 'size': '6012'}