Skip to main content
37 votes
Accepted

Why is it not possible to generate an explicit formula for Newton's method?

First, note that such a formula would violate the "too good to be true" test: it would let you find the minima of any (sufficiently smooth, strictly) convex function in a single step, no matter how ...
user7530's user avatar
  • 49.5k
18 votes

Why is it not possible to generate an explicit formula for Newton's method?

You wouldn't really gain much with a formula for the $n$th iteration. The appeal of the Newton-Raphson method is that a single step: is conceptually easy to understand, is fast to compute, and can ...
John's user avatar
  • 26.4k
12 votes
Accepted

Convergence of Newton Method for monotonic polynomials

No, not necessarily. In particular, consider the polynomial, $$p(x) = \frac{7}{2}x - \frac{5}{2}x^3 + x^5.$$ Note that $$p'(x) = \frac{7}{2} - \frac{15}{2}x^2 + 5x^4,$$ a positive quadratic in $x^2$ ...
Theo Bendit's user avatar
  • 51.5k
11 votes

When does the Newton Raphson method fail?

To visualize geometrically what's going on, I will code an interactive diagram with GNU Dr. Geo (free software of mine) from where I can drag the initial value (the red dot) and see how the method ...
Hilaire Fernandes's user avatar
10 votes
Accepted

Examples of when Newton's Method will fail?

Example for Case (A): $$f(x) = \frac{1}{1+x^2} - \frac{1}{2},$$ which has roots at $x \in \{-1,1\}$. The initial choice $x_0 = 2$ converges to the negative root. Example for Case (B): $$f(x) = \...
heropup's user avatar
  • 139k
9 votes
Accepted

Using Newton-Raphson method to approximate the minimum value of the function

Your code is for finding the root of $f(x)$, which is not what you want. In fact you should find the root of $$f'(x)=4x^3-9x^2$$ So the correct iteration formula should be $$x_{n+1}=x_n-\frac{f'(x_n)}{...
velut luna's user avatar
7 votes
Accepted

In practice, what does it mean for the Newton's method to converge quadratically (when it converges)?

A great example is to do what your calculator does when it computes $\sqrt{x}$ for some number. This way, you can see quadratic convergence in practice. Say you want to figure out $\sqrt{17}$, this ...
operatorerror's user avatar
7 votes

Convergence of the quadratic map $\left(x-\left(x-\left(x- \dots \right)^2 \right)^2 \right)^2$?

It looks closely related to Newton's way to compute the square-root. If you want the square root of $1+x$, you generate the sequence $$a_{n+1}= \frac12\left(a_n + \frac{1+x}{a_n}\right)$$ with $a_0$ ...
Fabian's user avatar
  • 23.5k
7 votes
Accepted

Faster convergence methods for Lambert W approximation

If you look for higher order formulae, you could consider Householder method which is or order $4$. If you want to go further, have a look at this paper; using it, you can easily build an iteration ...
Claude Leibovici's user avatar
7 votes

Can we find the complex roots by using Newton's method?

Newton's method works for complex differentiable functions too. In fact, we do exactly the same thing as in the real case, namely repeat the following operation: $$ z_n = z_{n+1} - \frac{f(z_n)}{f'(...
Arthur's user avatar
  • 201k
7 votes

Can we find the complex roots by using Newton's method?

You can but, as usual, you typically need to be close to one root for that to work well. Understanding how Newton's method converges and where it converges to depending on the initial value is very ...
lhf's user avatar
  • 217k
6 votes
Accepted

Speed of the binomial series for calculating $\sqrt{3}$

The binomial series, or more general, Taylor's formula in general converges at an exponential rate, here like $(1/4)^n$ (related to singulaties in the complex plane). Newton's method is in general ...
H. H. Rugh's user avatar
  • 35.3k
6 votes

How can a two term Taylor Series be used to derive Newton-Raphson root finding formula?

We have that the 2 term Taylor polynomial is given by $$f(x)\approx f(x_0)+f'(x_0)(x-x_0)$$ Setting $f(x)=0$, we end up with $$ \begin{align} 0&=f(x_0)+f'(x_0)(x-x_0)\\ f'(x_0)(x-x_0)&=-f(x_0)\...
Simply Beautiful Art's user avatar
6 votes
Accepted

Is modified Newton's Raphson method redundant?

The convergence for multiplicity $m$ is geometric with factor $1-\frac1m$. This means that you need more than 3 iterations for each digit of the result. Thus you can both detect the slow convergence ...
Lutz Lehmann's user avatar
6 votes

Pattern of Newton-Raphson iteration $x\mapsto\frac{1}{2}(x+\frac{q}{x})$ over finite fields

Whenever $q_1, q_2$ are both quadratic residues modulo $p$, or both quadratic nonresidues modulo $p$, we can find a constant $c \ne 0$ such that $q_2 \equiv c^2 \cdot q_1 \pmod p$. Then multiplication ...
Misha Lavrov's user avatar
6 votes
Accepted

Pattern of Newton-Raphson iteration $x\mapsto\frac{1}{2}(x+\frac{q}{x})$ over finite fields

Assume first that $q$ is a quadratic residue modulo $p$. By Misha Lavrov's answer we can then assume that $q=1$. We are interested in the behavior of the iterates of $$ f(x):=\frac12\left(x+\frac1x\...
Jyrki Lahtonen's user avatar
6 votes

Why does the sign in Newton's method matter?

The derivation doesn't assume $x_1$ lies on the right of $x_0$. The approximation $x_{k + 1}$ generated from Newton's method is the root of the tangent line at the previous approximation $x_k$: $$ 0 - ...
Chee Han's user avatar
  • 4,655
5 votes

When to use Newtons's, bisection, fixed-point iteration and the secant methods?

You should never seriously use bisection. If you think that derivatives are hard, use the secant method. If you want to force convergence and can find intervals with opposite signs of the function, ...
Lutz Lehmann's user avatar
5 votes

Intuitive Understanding Newton-Raphson method with second derivatives

Read again your new text. With almost certainty you will find that you want to find extremal points of that $f$. Since in general they can be found were $f'(x)=0$, Newton's method for $g(x)=f'(x)$ ...
Lutz Lehmann's user avatar
5 votes
Accepted

Can there be a metric space where no contraction has a fixed point?

If $X$ is non-empty then we can choose some $x_0\in X$ and define $f(x)=x_0$ for all $x\in X$. This is a contraction with a fixed point.
carmichael561's user avatar
5 votes
Accepted

Use Newton's method on a constant?

find the root(s) of $$x^2-7=0$$ and choose $\color{red} {x_0>0}$; $$f(x)=x^2-7\to f'(x)=2x\\x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\\x_{n+1}=x_n-\frac{x_n^2-7}{2x_n}$$ $$x_{n+1}=\frac12(2x_n-\frac{x_n^...
Khosrotash's user avatar
  • 25.1k
5 votes
Accepted

Why does the sign in Newton's method matter?

The fault is that, mathematically, there is no reason to suppose changing the sign will still work. There are three ways (that I am aware of) to think about Newton-Raphson; the first is that it is a ...
FShrike's user avatar
  • 41.8k
5 votes

Why does the sign in Newton's method matter?

I appreciate your question, because you are considering/retrieving things the way Newton himself was doing. That is to say with a geometric intuition, considering (as here) different cases before ...
Jean Marie's user avatar
  • 83.6k
5 votes
Accepted

Newton method with high multiplicity: rigorous proof

Let $f\in \mathcal{C}^{m}([a,b])$ with $m\ge 2$, and let $\alpha \in (a,b)$ such that $$ 0 = f(\alpha) = f'(\alpha) = f''(\alpha) = \dots = f^{(m-1)}(\alpha), \quad f^{(m)}(\alpha) \neq 0. $$ Repeated ...
Martin R's user avatar
  • 116k
5 votes
Accepted

Problem with Newton's method (numerical analysis)

Take the example $f(x) = x^{2/5}$. If you choose some $x_0 \ne 0$, then $x_1$ is given by $$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} = -\frac 32 x_0. $$ So, you can see that the magnitude of the sequence ...
PierreCarre's user avatar
  • 21.3k
4 votes
Accepted

Why does newton's method of successive approximation to compute square roots work?

Newton's method approximates a zero of the function $f$ by iterating $$ x \mapsto x - \frac{f(x)}{f'(x)} $$ which has the geometric interpretation of finding the intersection between the $x$-axis and ...
hmakholm left over Monica's user avatar
4 votes

How to show Newton's method has quadratic convergence rate with an example?

In this case you don't know the value of a root $x^*$, so you can't compute the errors $|x_k - x^*|$. The trick is to use the values $f(x_k)$. Because by definition, $f(x^*) = 0$, a first-order Taylor ...
Dominique's user avatar
  • 3,174
4 votes

Newton's Method and One definition?

If $x_0$ is sufficiently near $\alpha$, but $\ne\alpha$, then there is a $b$ between $\alpha$ and $x_0$ such that $$f'(x_0)=f'(x_0)-f'(\alpha)=(x_0-\alpha )f''(b)\ne0\ .\tag{1}$$ Computing $f(\alpha)=...
Christian Blatter's user avatar
4 votes
Accepted

Derivation of Newton-Raphson method in higher dimensions

You are given a function $f$ of type ${\mathbb R}^n\to{\mathbb R}^n$, defined on some open set $\Omega$, and you want to solve the equation $f(x)=0$. You suspect that the point $p\in\Omega$ is already ...
Christian Blatter's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible