*In this section, we will only consider single variable functions. The proof
for multivariable functions is similar except one would have to use inverse
matrices of the Jacobian instead of division by f ' making proof much
more difficult to read.*

Let `r` be a root of `f(x) = 0` so that `f(r) = 0`.

Assume that`f`, `f'` and `f"` are continuous
and differentiable near `r` and
`f'(r) ≠ 0`.

Lets use Newton's method so that

`x`_{k+1} = x_{k} - f(x_{k}) / f'(x_{k})

Define errors`e`_{k} = r - x_{k}
and `e`_{k+1} = r - x_{k+1}

We will now expand e_{k} in a way that will eventually prove
to be very useful. First, the iteration formula

`x`_{k+1} = x_{k} - f(x_{k}) / f'(x_{k})

Thus

`x`_{k} = x_{k+1}
+ f(x_{k}) / f'(x_{k})

Returning to`e`_{k}, we obtain

`e`_{k} = r - x_{k}

= r - x_{k+1} - f(x_{k}) / f'(x_{k})

= e_{k+1} - f(x_{k}) / f'(x_{k})

Let's expand`f(r)` in the Lagrange form of the Taylor series
`ξ`_{k} is between `x`_{k} and `r`. But
`f(r) = 0` so` f'(x`_{k}) to obtain`e`_{k} by its value obtained earlier.`-f"(ξ`_{k}) / [2 f'(x_{k}) in an
appropriate interval near r and apply absolute values, we see that the
convergence is quadratic if `x`_{0} is close enough to
`r`.

Assume that

Lets use Newton's method so that

Define errors

We will now expand e

Thus

Returning to

= r - x

= e

Let's expand

f(r) = f(xwhere_{k}+ e_{k}) = f(x_{k}) + f'(x_{k})e_{k}+ f"(ξ_{k})e_{k}^{2}/ 2

0 = f(xDivide by_{k}) + f'(x_{k})e_{k}+ f"(ξ_{k})e_{k}^{2}/ 2

0 = f(xNow replace_{k}) / f'(x_{k}) + e_{k}+ f"(ξ_{k})e_{k}^{2}/ [2 f'(x_{k})]

0 = f(xIf we maximize_{k}) / f'(x_{k}) + e_{k+1}- f(x_{k}) / f'(x_{k}) + f"(ξ_{k})e_{k}^{2}/ [2 f'(x_{k})] 0 = e_{k+1}+ f"(ξ_{k})e_{k}^{2}/ [2 f'(x_{k})] e_{k+1}= {-f"(ξ_{k}) / [2 f'(x_{k})]} e_{k}^{2}

(Again in this section, we will only consider single variable functions. The proof for multivariable functions is similar except one would have to use inverse matrices of the Jacobian instead of division by f ' making proof much more difficult to read.)

Let `r` be a root of `f(x) = 0` so that `f(r) = 0`.

Assume that`f`, `f'` and `f"` are continuous near `r` and
`f'(r) ≠ 0`.

Lets use*an alternative to* Newton's method * by replacing
f '(x*_{k}) by the approximation

` x`_{k+1} = x_{k} - f(x_{k})/*d(x*_{k}, Δ)

Define errors`e`_{k} = r - x_{k}
and `e`_{k+1} = r - x_{k+1}.

We will now expand e_{k} in a way that will eventually prove
to be very useful. First, the iteration formula

`x`_{k+1} = x_{k} - f(x_{k}) / *d(x*_{k}, Δ)

Thus

`x`_{k} = x_{k+1}
+ f(x_{k}) / *d(x*_{k}, Δ)

Returning to`e`_{k}, we obtain

`e`_{k} = r - x_{k}

= r - x_{k+1} - f(x_{k}) / *d(x*_{k}, Δ)

= e_{k+1} - f(x_{k}) / *d(x*_{k}, Δ)

Let's expand`f(r)` in the Lagrange form of the Taylor series
`ξ`_{k} is between `x`_{k} and `r`. But
`f(r) = 0` so` f'(x`_{k}) to obtain`e`_{k} by its value obtained earlier.*where*`Q(x`_{k}, Δ).
If `Q(x`_{k}, Δ) is zero, then the method would
converge quadratically. But in general, it will not be. Lets examine
`[1 / f'(x`_{k}) - 1 / d(x_{k}, Δ)]
more closely. Because
Thus we can make `Q(x`_{k}) as close to 0 as desired by making Δ small
enough. Unfortunately, in practice, we will lose numerical accuracy if
it is too small. This would be a significant problem if we were using
single precision arithmetic. But in modern computers and many languages
(including Javascript), double precision is used without much inefficiency.
(This technique would not be recommended if calculations are carried out
in single precision.)
Experimentally it has been found that using Δ from 10^{-4}
to 10^{-6} often approximates
the derivative very well and the resulting convergence appears to be
quadratic. (Sometimes, negative values of Δ can cause faster
convergence.) Even smaller values have been used successfully.
## Newton's Method with multiple variables

Consider Newton's method for systems with multiple variables. For example,
if f is a vector function with 2 functions of 2 variables, then we could
write`J(x`_{k}, y_{k})^{-1}.
Instead one can solve

`J(x`_{k},y_{k})Y = F(x_{k}, y_{k})

for Y and iterate with` X`_{k+1} = X_{k} - Y.

The proof that the sequence converges quadratically is much the same as for the single variable proof with`f'` replaced with `J`. Division by `f'`
is replaced by a left multiplication of `J`^{-1}. f " is
replaced by Hessian matrix, H, the matrix of second partials, and
`f"e`_{k}^{2}
is replaced by
`E`_{k}^{T}HE_{k}.
A norm such as max norm is used in place
of absolute values.

If there are more than 2 variables, the vectors and matrices are expanded in the obvious way.## Approximating Newton's method with multiple variables

For 2 dimensional systems, the partials in the Jacobian are replaced by_{1} when approximating Newton's method. The same
concept is used for systems with more variables. Experience has shown that
`Δ = 0.0001` often produces quadratic like
convergence.

Assume that

Lets use

d(xand using the iteration_{k}, Δ) =f'(xΔ_{k}+ Δ) - f'(x_{k})

Define errors

We will now expand e

Thus

Returning to

= r - x

= e

Let's expand

f(r) = f(xwhere_{k}- e_{k}) = f(x_{k}) - f'(x_{k})e_{k}+ f"(ξ_{k})e_{k}^{2}/2

0 = f(xDivide by_{k}) - f'(x_{k})e_{k}+ f"(ξ_{k})e_{k}^{2}/2

0 = f(xNow replace_{k}) / f'(x_{k}) + e_{k}+ f"(ξ_{k})e_{k}^{2}/ [2 f'(x_{k})]

0 = f(x_{k}) / f'(x_{k}) + e_{k+1}- f(x_{k}) /d(x+ f"(ξ_{k}, Δ)_{k})e_{k}^{2}/ [2 f'(x_{k})] 0 = e_{k+1}+ f(x_{k}) / f'(x_{k}) - f(x_{k}) /d(x+ f"(ξ_{k}, Δ)_{k})e_{k}^{2}/ [2 f'(x_{k})]e_{k+1}= -f(x_{k}) / f'(x_{k}) + f(x_{k}) / d(x_{k}, Δ) + {-f"(ξ_{k}) / [2 f'(x_{k})]} e_{k}^{2}= -f(x_{k}) * [1 / f'(x_{k}) - 1 / d(x_{k}, Δ)] + {-f"(ξ_{k}) / [2 f'(x_{k})]} e_{k}^{2}= Q(x_{k}, δ_{k}) + C_{k}e_{k}^{2}

Q(xand_{k}, Δ) = -f(x_{k}) * [1 / f'(x_{k}) - 1 / d(x_{k}, Δ)]

CConsider_{k}= -f"(ξ_{k}) 2f'(x_{k})

lim Q(xWe see_{k}, Δ) Δ → 0 = limf(x+Δ) - f(x)= f'(x) Δ → 0 Δ

lim [1 / f'(x_{k}) - 1 / d(x_{k}, Δ)] = 0 Δ → 0

The expression for Q(x_{k}, Δ) also shows that
there can be serious problems with convergence if f '(r) = 0 because
both f '(x_{k}) and d(x_{k}, Δ) approach 0 as
x_{k} approaches the solution. While
iteration patterns when f '(r) ≠ 0 normally closely resemble
those of regular Newton's method, they often differ when f '(r) = 0
as the iterations start getting closer r.

X = ⌈x⌉ F(x, y) = ⌈fThen Newton's method can be carried out with_{0}(x, y)⌉ E = ⌈x - r_{0}⌉ ⌊y⌋ ⌊f_{1}(x, y)⌋ ⌊y - r_{1}⌋ J(x, y) = ⌈δf_{0}(x, y)/δx δf_{0}(x, y)/δy⌉ ⌊δf_{1}(x, y)/δx δf_{1}(x, y)/δy⌋

XActually it is not necessary to calculate_{k+1}= X_{k}- J(x_{k}, y_{k})^{-1}F(x_{k}, y_{k})

for Y and iterate with

The proof that the sequence converges quadratically is much the same as for the single variable proof with

If there are more than 2 variables, the vectors and matrices are expanded in the obvious way.

δfLikewise for f_{0}(x_{k}, y_{k})/δx = f_{0}(x_{k}+ Δ, y_{k}) - f_{0}(x_{k}, y_{k}) Δ δf_{0}(x_{k}, y_{k})/δy = f_{0}(x_{k}, y_{k}+ Δ) - f_{0}(x_{k}, y_{k}) Δ

©James Brink, 11/12/2021