Math4501 Lecture 2

Solving non-linear equations

Let $\vec{f}:\mathbb{R}^n\to\mathbb{R}^n$ we want to solve $\vec{f}(\vec{x})=\vec{0}$. ($m$ equations, $m$ variables)

In case if $\vec{f}$ is linear, we can solve it by Gaussian elimination.

Closely related to the problem: eigenvalue problem.

related to root finding problem for polynomial.

Polynomial approximations

Let $f:[0,1]\to\mathbb{R}$ be a continuous function.

Find polynomial $p_n$ of degree $n$ such that $p_n(x_i)=f(x_i)$ for $i=0,1,\cdots,n$.

Then, some key questions are involved:

1. How to compute $c_0,c_1,\cdots,c_n$?
2. If $f$ is continuously differentiable, does $p_n'$ approximate $f'$?
3. If $f$ is integrable, does $\int_0^1 p_n(x)dx$ approximate $\int_0^1 f(x)dx$?

Deeper questions:

Is the approximation efficient?

Scalar problem

Problem 1: Let $f:[a,b]\to\mathbb{R}$ be a continuous function. Find $\xi\in[a,b]$ such that $f(\xi)=0$.

Problem 2: Let $f:[a,b]\to\mathbb{R}$ be a continuous function. Find $\xi\in[a,b]$ such that $f(\xi)=\xi$.

P1, P2 are equivalent. $f(x)\coloneqq f(x)-x$ is a continuous function.

Intermediate value theorem 

Some advantage in solving P1 as P2

When does a solution exists

Trivial case: $f(x)=0$ for some $x\in[a,b]$.

Without loss of generality, assume $f(a)f(b)<0$, Then there exists $\xi\in(a,b)$ such that $f(\xi)=0$.

Bisection algorithm:

def bisection(f, a, b, tol=1e-6, max_iter=100):
    # first we setup two sequences $a_n$ and $b_n$
    # require:
    # |a_n - b_n| \leq 2^{-n} (b-a)
    for i in range(max_iter):
        c = (a + b) / 2
        if c < tol or f(c) == 0:
            return c
        elif f(a) * f(c) < 0:
            b = c
        else:
            a = c
    return None

Let $f(a_n)<0$ for all $n$ and $f(b_n)>0$ for all $n$.

$\lim_{n\to\infty} f(a_n)\leq 0$ and $\lim_{n\to\infty} f(b_n)\geq 0$.

If limit exists, then $\lim_{n\to\infty} f(a_n)=\lim_{n\to\infty} f(b_n)=0$.

Such limit exists by the sequence $a_n$ and $b_n$ is Cauchy and we are in real number field.

This can be used to solve P2:

Recall that if we define $f(x)\coloneqq g(x)-x$, then $f(x)=0$ if and only if $f(a)f(b)<0$. That is $(g(a)-a)(g(b)-b)\leq 0$.