Intereting Posts

prove that a function is an immersion
Reconciling several different definitions of Radon measures
How does Cramer's rule work?
Why is $\tan((1/2)\pi)$ undefined?
Number of ways to get exactly one 3 of a kind from 9 dice
Prove that $\frac{a_1^2}{a_1+a_2}+\frac{a_2^2}{a_2+a_3}+ \cdots \frac{a_n^2}{a_n+a_1} \geq \frac12$
Priority of the content of a note by Lebesgue from 1905
Evaluating the integral $\int_{-\infty}^\infty \frac{\sin^2(x)}{x^2}e^{i t x} dx$
for each $\epsilon >0$ there is a $\delta >0$ such that whenever $m(A)<\delta$, $\int_A f(x)dx <\epsilon$
Integration double angle
Derive $\frac{d}{dx} \left = \frac{1}{\sqrt{1-x^2}}$
Overlapping Probability in Minesweeper
Orthogonal Projection onto the $ {L}_{1} $ Unit Ball
Is $2 + 2 + 2 + 2 + … = -\frac12$ or $-1$?
Must the intersection of connected sets be connected?

Show that Newton’s method can be used to compute the square root function $\sqrt a$ using the formula

$$x_{n+1} = \frac{1}{2}\left(x_{n} + \frac{a}{x_{n}}\right)$$

show that the error is

- Local vs global truncation error
- $\beta_k$ for Conjugate Gradient Method
- Math Analysis Designing Algorithms
- How should a numerical solver treat conserved quantities?
- Variational formulation of Robin boundary value problem for Poisson equation in finite element methods
- Non-linear SDE: how to?

$$\sqrt a – x_{n+1} = -\frac{1}{2x_{n}}\left(\sqrt a – x_{n}\right)^2$$

edit: As pointed out below $x^2-a$ has $\sqrt a$ as a root.

I have done as suggested below and plugged in $\sqrt a + \epsilon$ for $x_n$ giving me

$$x_{n+1} = \frac{2\epsilon\sqrt a + \epsilon^2}{2(\sqrt a + \epsilon)}$$ and once again not sure where to proceed.

- What is a nice way to compute $f(x) = x / (\exp(x) - 1)$?
- Relationship between rate of convergence and order of convergence
- Fermat-quotient of “order” 3: I found $68^{112} \equiv 1 \pmod {113^3}$ - are there bigger examples known?
- fast algorithm for solving system of linear equations
- Matlab numerical integration involving Bessel functions returns NaN
- How to calculate APR using Newton Raphson
- resources to study PDE from
- What's the most efficient way to mow a lawn?
- Name for kind of big O notation with leading coefficient
- Floating point arithmetic: $(x-2)^9$

Hint: start with the fact that $f(x) = x^2-a$ has $\sqrt{a}$ as a root.

Use the Newton’s Method formula:

$$x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}$$

where $f(x_n) = x_n^2-a$ and $f'(x_n) = 2 x_n$.

Plug these into the above equation and the first result is obtained with a little algebra. For the second result, note that

$$\sqrt{a}-x_{n+1} = \sqrt{a}-\frac{1}{2} \left (x_n + \frac{a}{x_n} \right )$$

What you can do here is multiply that last piece out and factor out $-1/(2 x_n)$. What you should get is 3 terms that fit a pattern of a binomial squared. Look at the result you are trying to show to guide you.

We have Newton’s method as

\begin{align}

x_{k+1} = x_k – \frac{f(x_k)}{f'(x_k)}

\end{align}

And Newton’s method is used to solve $f(x)=0$. As rlgordonma pointed out,if you want to calculate $\sqrt{a}$ you need to solve $f(x)=0$ for a function $f$ that fulfills $f(\sqrt{a})=0$. He also told, that such a function is $f(x) = x^2-a$. Now combine the two information.

You can find what it converges to by plugging in $x$ for $x_{n+1}$ and $x_n$. To show that it converges, let $x_n=\sqrt a + \epsilon_n$. Plug this into the equation and compute $x_{n+1}$. You should be able to find that $x_{n+1}-\sqrt a$ is of order $\epsilon^2$, so if $\epsilon \lt 1$ it will converge.

Added: So $x_{n+1}=\frac 12 (x_n+\frac a{x_n})$

Let $x_n=\sqrt a + \epsilon_n$ (and we imagine that $\epsilon_n \ll 1$)

Then $x_{n+1}=\sqrt a + \epsilon_{n+1}=\frac 12(\sqrt a + \epsilon_n+\frac a{\sqrt a – \epsilon_n}) \\ \approx \frac 12(\sqrt a + \epsilon_n+ \sqrt a(1-\frac {\epsilon_n}{\sqrt a}

+\frac {\epsilon_n^2}a))\\ =\sqrt a+\frac {\epsilon_n^2}{\sqrt a}$

So $\epsilon_{n+1}\approx \frac {\epsilon_n^2}{\sqrt a}$ showing the error gets squared each iteration.

- Revisited: Binomial Theorem: An Inductive Proof
- How much set theory and logic should typical algebraists/analysts/geometers know? (soft-question)
- Lucas Theorem but without prime numbers
- I have a problem understanding the proof of Rencontres numbers (Derangements)
- If $X$ has a metric $d$ then the topology induced by $d$ is the smallest topology relative to which $d$ is continuous
- A bounded net with a unique limit point must be convergent
- Measure of Image of Linear Map
- If $a+b+c=3$ show $a^2+b^2+c^2 \leq (27-15\sqrt{3})\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)$
- Can someone show me why mathematicians use $d\mu$ instead of $dx$ for Lebesgue Integral over $u(x)$
- Three finite groups with the same numbers of elements of each order
- Proving that $f(n)=n$ if $f(n+1)>f(f(n))$
- Is there a Definite Integral Representation for $n^n$?
- How are we able to calculate specific numbers in the Fibonacci Sequence?
- Compatibility of topologies and metrics on the Hilbert cube
- Possible distinct positive real $x,y,z \neq 1$ with $x^{(y^z)} = y^{(z^x)} = z^{(x^y)}$ in cyclic permutation?