85.7k views
0 votes
Show that newtons method converges when writen as a fixed point iteration​

User Tjuzbumz
by
8.6k points

1 Answer

3 votes

Answer:

Explanation:

Newton's method is an iterative method for finding the roots of a differentiable function. Let's consider finding a root of a function f(x) using Newton's method:

x_{n+1} = x_n - f(x_n)/f'(x_n)

We can write this iteration as a fixed point iteration:

x_{n+1} = g(x_n)

where g(x_n) = x_n - f(x_n)/f'(x_n)

To show that Newton's method converges when written as a fixed point iteration, we need to show that g(x) is a contraction mapping in some neighborhood of the root.

First, let's find the derivative of g(x):

g'(x) = (f(x)f''(x))/(f'(x))^2

Since we are interested in finding the roots of f(x), let's assume that f(x) has a root at r. We can then write:

f(x) = f(r) + f'(r)(x-r) + O((x-r)^2)

Substituting this into the formula for g(x), we get:

g(x) = x - [f(r) + f'(r)(x-r) + O((x-r)^2)]/[f'(r) + f''(r)(x-r) + O((x-r)^2)]

We can simplify this expression by dropping the higher order terms and assuming that x is close to r:

g(x) = x - [f(r) + f'(r)(x-r)]/[f'(r) + f''(r)(x-r)]

= (xf'(r) - f(r))/[f'(r) + f''(r)(x-r)]

Now, let's consider the behavior of g'(x) in a neighborhood of r:

g'(x) = (f(x)f''(x))/(f'(x))^2

= [f(r) + f'(r)(x-r) + O((x-r)^2)][f''(r) + O(x-r)]/([f'(r) + f''(r)(x-r) + O((x-r)^2)])^2

= [f''(r)f(r) + O(x-r)]/[f'(r) + f''(r)(x-r) + O((x-r)^2)]^2

Since f(r) = 0, we can simplify this expression further:

g'(x) = f''(r)/(f'(r))^2 + O(1/(x-r))

As x approaches r, the term O(1/(x-r)) approaches zero, and we are left with:

g'(r) = f''(r)/(f'(r))^2

If g'(r) is less than one in absolute value, then g(x) is a contraction mapping in a neighborhood of r, and Newton's method will converge to r.

Let's consider two cases:

g'(r) = 0

If g'(r) = 0, then g(x) is not a contraction mapping, and Newton's method may not converge to r.

g'(r) ≠ 0

If g'(r) ≠ 0, then we can rewrite g(x) as:

g(x) = r + [g(x) - r]

= r + [(x-r) - f(x)/f'(x)]/[1 + g'(r)(x-r)/f'(r)]

Now, if we choose an initial guess x_0 sufficiently close to r, we can ensure that |g'(r)(x_0-r)/f'(r)| is less than one, and therefore g(x) will be a contraction mapping in a neighborhood of r. Therefore, Newton's method will converge to r in this case.

In summary, we have shown that if g(x) = x - f(x)/f'(x), then Newton's method can be written as a fixed point iteration x_{n+1} = g(x_n), and under certain conditions, g(x) is a contraction mapping in a neighborhood of the root, which implies convergence of the iteration to the root. Specifically, if g'(r) is less than one in absolute value, where r is the root of f(x), then Newton's method will converge to r.

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories