We can improve this method by calculating a general formula for the repetition step. This
is given by
With a good ﬁrst guess, this method can converge extremely quickly. If it fails to converge,
use bisection to improve your initial guess.
Fixed Point Iteration
A simpler alternative to Newton’s Method is to rewrite f(x) = 0 as x=g(x). Thus we ﬁnd
an approximate solution via
This converges slower than Newton’s Method, but is simpler to calculate.
Theorem: Convergence of Fixed-Point Iteration. Suppose that f(x) is deﬁned for all
x∈R, difderntiable everywhere, and has a bounded derivative at all points. If f(x) = x
has a solution, and if
<1 for all values of xwithin some interval containing the ﬁxed
point, then the sequence generated by letting xn+1 =f(xn) will converge with any choice of
Suppose we are given n+1 points (x, y) and we want to ﬁnd a polynomial of degree n passing
through them. We could either solve this with matrices, or we can use Newton’s Forward
∆myn= ∆m−1yn+1 −∆m−1yn
we can reduce the system to one of size n−1. A shorthand way to do this is to create a
column of y-values, then create a new n−1 row of the diﬀereneces between each row, etc.
You should end up with a triangular shape.
By iterating through this method until we have an n= 1 system, we can solve for each of
the coeﬃcients by substituting them into the general polynomial. This will give us a general
solution which can then be used for any dataset. This solution is of the form
y=y0+x∆y0+... +x(x−1)...(x−n+ 1)∆ny0
If we have non-unit spacing, this formula becomes