1
Q
What is the bisection method
A
- Let f : R → R be a continuous function on an interval [a,b] with a < b
- If f(a)f(b) < 0 then there must exist a root in the interval
- Start with an initial interval [a,b] where f(a)f(b) < 0
- Compute p = (a + b) /2
- If f(a)f(p) < 0 update the half-interval to be [a,p] and [b,p] otherwise
- Repeat the process until the length of the interval is less than a predetermined tolerance ϵ
- Return the midpoint of the final interval as the root.
2
Q
What is the bound on the error of the midpoint sequence generated by the bisection method
A
3
Q
Describe the proof of the error bound on the bisection method
A
4
Q
What is Linear Convergence
A
5
Q
What is Newton’s Method
A
6
Q
What are two problems with Newton’s Method
A
- When f ′(x0) ≈ 0, the tangent line at (x0, f (x0)) is almost horizontal and takes us far away from the solution
- The iteration can get stuck oscillating between two values forever
7
Q
Describe the convergence properties of the bisection method and the newton’s method
A
- Bisection method - Converges linearly
- Newton-Raphson method - Converges quadratically
8
Q
What is a fixed point of a function
A
A fixed point of a function g : R → R is a number x such that g (x) = x
9
Q
What is a fixed point iteration
A
10
Q
What is the fixed point theorem
A
11
Q
What does it mean to converge quadratically
A
12
Q
Under what conditions does the sequence {xn} generated by Newton’s method converge quadratically to x
A
