MATH 349 - Numerical Analysis

Intermediate Value Theorem

Suppose f is a continuous on [a,b]. If k is a number between f(a) and f(b), then there exists some c ∈ [a,b] such that f(c) = k

Conditions for bisection method

1. f is continuous on [a,b]

2. f(a)*f(b)<0 therefore f(a) and f(b) have opposite signs so IVT gurantees a root x^* ∈ (a,b)

midpoint in bisection method

p =(a+b)/2

After computing p=(a+b)/2 how do i choose the next interval

1. If f(p)=0 stop, p is the root

2. if f(a)f(p)<0 use [a,p]

3. if f(p)f(b) <0 use [p,b]

why does bisection work

the endpoints always retain a sign change so IVT guarantees a root remains inside the retained interval. Each iteration cuts that interval in half.

Bisection Error Bound

|x_n-x^*|≤(b-a)/(2ⁿ)

how many iterations are sufficient to obtain error < ε?

choose N sufficiently large that N>log2((b-a)/ε).

(b-a)/(2^N)<ε

difference between IVT and bisection method

IVT is an existence theorem (guarantees root exists) while bisection is constructive (approximate root)

tangent line approximation for newtons method

l(n)=f(x₀)+f’(x₀)(x^*-x₀)+((f’’(ξ))/2)(x^*-x₀)²
Because the difference between x^* and x_0 is small we drop this term and are left with just
l(n)=f(x₀)+f’(x₀)(x^*-x₀)

Newton’s Method formula

x_n+1=x_n-(f(x_n)/f’(x_n))
We get this because 0=f(x^*)≈f(x₀)+f’(x₀)(x^*-x₀) and then we solve for x^*.

Requirements to use Newtons Method

1. f is differentiable on [a,b]

2. f’ is continuous on [a,b] (just needed for guarantees)

3. We need f’(x_n)≠0

absolute error

|p-p^*|

relative error

(|p-p^*|/|p|)

this is better because it tells you how big the error is compared to the true value

Definition. Rate of Convergence

1. At least linear if there exists a positive constant C<1 and an integer N such that |x_{n+1}-L| ≤ C|x_n-L|, n ≥ N.

2. At least quadratic if there exists a positive constant C and an integer N such that |x_{n+1}-L| ≤ C|x_n-L|^2, n ≥ N.

3. More generally, the order is at least “a” if there exists a constant C>0 and an integer N such that |x_{n+1}-L|≤ C|x_n-L|^{“a”}, n ≥N.

Local Quadratic Convergence of Newton's Method

1. f ∈ C^2[a,b];

2. x^* ∈ (a,b) is a zero of f;

3. f'(x^*) ≠ 0;

4. x^* is the unique zero in a neighborhood of x^*.

Then there exists a neighborhood of x^* and a constant K>0 such that, if Newton's Method is initialized in that neighborhood, the approximations x_n converge to x^* and satisfy |x^*-x_{n+1}| ≤ K|x^*-x_n|^2.

Thus, Newton's Method has quadratic order of convergence near x^*.

Proof: Local Quadratic Convergence of Newton's Method

1. Let f(x^*)=0 and consider the Taylor expansion of f centered at xn.

2. Since f(x^*)=0 we set the whole eqn to 0

3. Then subtract the quadratic term to left side

4. Divide by f’(xn)

5. Then use newtons method formula to simplify right side to x^*-x_{n+1}

6. take absolute values

7. Bc f’’ is continuous and f’(x^*)≠0 in the small neighborhood of x^* then we have constant K>0 st the term with xi ≤ K

8. Thus |x^*-x_{n+1}| ≤ K|x^*-x_n|^2.

Limitations of Newtons Method

1. Runaway: If we pick an x0 that is too far away from x^* then we might move away from the root instead of converging

2. Flat Spot: if f’(x0)=0 then the tan line at x0 is horizontal and the newton iteration cannot be performed as we would have to divide by 0.

3. Cycle: We might iterate between the same points instead of converging

Strengths and Limitations of Newtons Method

Strengths:

1. Simple formula

2. Quadratic convergence near a suitable root

3. can easily be extended to higher dimensions

Weakness

1. f’ and f’’ must be well behaved to guarantee convergence

2. The initial guess and interval of convergence should be chosen carefully

Secant Method

x_n+1=x_n-f(x_n)((x_n-x_n-1)/(f(x_n)-f(x_n-1))

When there are issues with differentiability we can us ethe secant method instead. The secant method addresses this issue by using a difference quotient instead of the derivative of f.

Def. Fixed Point

A fixed point for a function g is a point x^* st g(x^*)=x^*

We can also think about where g(x) intersects with y=x

Theorem: Equivalence of Root-Finding and Fixed-Point Problems

Root-finding problems and fixed-point problems are equivalent: if f has a root at x^*, then for a suitably chosen function g, x^* is a fixed point of g.

Proof for Theorem: Equivalence of Root-Finding and Fixed-Point Problems

1. we want to solve f(x)=0

2. Define g(x)=x-f(x)

3. Then f(x^*)↔x^*-f(x^*)↔x^*↔g(x^*)=x^*

4. that means x^* is a fixed point of g

How to find fixed points?

set f(x)=x and then solve for x

How do you show a function g has a fixed point at p corresponding to a root of f(x)?

solve g(p)=p

and then get 0 on one side and that should be f(p)=0

Fixed Point Theorem

Consider the following assumptions:

1. g is continuous on [a,b].

2. g maps [a,b] into itself; that is, g(x) ∈ [a,b] for all x ∈ [a,b].

3. g'(x) exists on (a,b), and there exists a constant λ ∈(0,1) such that |g'(x)| ≤ λ

for all x ∈ (a,b).

Then:

1. {Existence: If (a) and (b) hold, then g has a fixed point in [a,b].

2. Uniqueness: If (a)--(c) hold, then there exists exactly one point x^* ∈ [a,b] such that x^*=g(x^*).

Proof of Existence for Fixed Point Thm

1. If g(a)=a and g(b)=b then g has a fixed point and we are done.

2. if that is not the case then because g maps on to itself we can say

3. g(a)>a↔a-g(a)<0 and g(b)<b↔b-g(b)>0

4. Define h(x)=x-g(x)

   1. Then h is continuous on [a,b] because both x and g(x) are continuous

   2. h(a)=a-g(a)<0

   3. h(b)=b-g(b)>0

5. By IVT there exists some x^*∈[a,b] such that h(x^*)=0↔x^*-g(x^*)=0↔x^*=g(x^*)

6. Thus x^* is a fixed point of g on [a,b]

Proof of Uniqueness for Fixed Point Thm

1. Suppose fixed pt is not unique so g(p)=p and g(q)=q st p,q∈[a,b]

2. Since p and q are distinct and g is differentiable by MVY there exists some c between p and q such that g’( c)=(g(p)-g(q))(p-q)

3. multiply both side by p-q and take abs val

4. then remove g’( c) bc p and q are fixed pts so |g(p)-g(q)|=|g’( c)||p-q| to |g(p)-g(q)|=|p-q|

5. then |p-q|=|g’( c)||p-q|

6. Since |g’(c )| ≤ λ we get |p-q|≤ λ|p-q|

7. since λ is btwn 0 and 1 we get λ|p-q|< |p-q|

8. so |p-q|< |p-q| which is a contradiction

9. so fixed pt is unique

Fixed point iteration

Given initial val x0 in domain of g the recursion x_n+1=g(x_n) is called a fixed point iteration

Convergence of Fixed-Point Iteration

Assume that g has the following properties:

1. g ∈ C[a,b];

2. g(x) ∈ [a,b] for all x ∈ [a,b];

3. |g'(x)| ≤ λ <1 on [a,b].

Then, for any initial guess

x_0 ∈ [a,b], the sequence of iterates x_{n+1}=g(x_n) converges to the unique fixed point x^* ∈ [a,b].

Proof Convergence of Fixed-Point Iteration

1. We get existence and uniqueness form Fixed Point Thm

2. WTS lim|xn-x^*|=0

3. Use def of fixed pt iteration |x_{n+1}-x^*|=|g(xn)-g(x^*)|

4. By MVT there exists some c between xn and x^* such that |g’( c)|xn-x^*|=|g(xn)-g(x^*)|

5. TF |x_{n+1}-x^*|≤λ|xn-x^*|

6. Then |x_{n+1}-x^*|≤|xn-x^*|=λ|g(xn)-g(x^*)|≤λ²|x_{n-1}-x^*|

7. |x_{n+1}-x^*|≤λⁿ⁺¹|x₀-x_*|

8. thus lim |xn-x^*|≤limλ^n|xo-x^*|

9. Since 0<λ<1

10. then λ^n to 0 as n to infinty

11. tf lim|xn-x^*|=0

12. hence xn to x^*

Corollary

If g satisfies all of the conditions of the fixed-point theorem,

then, starting with x_0 ∈ [a,b], we have the error bound |x_n-x^*| ≤ λⁿ max\{|x_0-a|,\;|b-x_0|\}.

Also, for every n ≥ 1, |x_n-x^*| ≤ (λ^n)/(1-λ)

|x_1-x_0|.

Lagrange Polynomial Inerpolation

pn(x)= ∑f(xi)L_n,i(x)

Lagrange Interpolation Error

E_n(x) = f(x)-p_n(x) = \frac{f^{(n+1)}(\zeta)}{(n+1)!} \prod_{i=0}^n (x-x_i)

spline

S_i(x)

=

\frac{x-x_{i+1}}{x_i-x_{i+1}}f(x_i)

+

\frac{x-x_i}{x_{i+1}-x_i}f(x_{i+1})

}.

L^\infty$ Norm

For a continuous function $g$ on $[a,b]$, define

\[

\boxed{

\|g\|_\infty

=

\max_{a\leq x\leq b}|g(x)|

}.

\]

Linear Spline Interpolation Error

Let

\[

f\in C^2[a,b],

\]

and let $S_L$ be the linear spline interpolating $f$ at the nodes

\[

a=x_0<x_1<\cdots<x_n=b.

\]

Define

\[

h

=

\max_{0\leq i\leq n-1}(x_{i+1}-x_i).

\]

Then

\[

\boxed{

\|f-S_L\|_\infty

\leq

\frac{h^2}{8}\|f''\|_\infty

}.

\]

Optimality of Natural Cubic Splines

Cubic Splines requirements