Mixing
show algorithm to compute square root converge. [closed]
$begingroup$
Consider the calculating the square root as follow:
Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=frac{g+frac{x}{g}}{2.0}$. Show that the algorithm eventually stops. Or, $lim_{n to infty} g_n = x$.
recursive-algorithms
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
$endgroup$
closed as off-topic by Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did Jan 11 at 14:13
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Consider the calculating the square root as follow:
Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=frac{g+frac{x}{g}}{2.0}$. Show that the algorithm eventually stops. Or, $lim_{n to infty} g_n = x$.
recursive-algorithms
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
$endgroup$
closed as off-topic by Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did Jan 11 at 14:13
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Why do you say it is slow? It is one of the faster ones, especially if you start close to $sqrt x$. If you prove the error is reduced by more than some constant factor you are there. What have you tried?
$endgroup$
– Ross Millikan
Jan 11 at 3:25
$begingroup$
Here is what I observed: $2gg'=g^2+x$, so if $g^2$ and $x$ are close enough then gg'=x. Please help! I did not say that it is slow. I meant show if that is what you meant.
$endgroup$
– nafhgood
Jan 11 at 3:29
add a comment |
$begingroup$
Consider the calculating the square root as follow:
Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=frac{g+frac{x}{g}}{2.0}$. Show that the algorithm eventually stops. Or, $lim_{n to infty} g_n = x$.
recursive-algorithms
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
$endgroup$
Consider the calculating the square root as follow:
Let's say we want to compute square root of $x>0$, pick a number $g_1>0$, then if $|g_1^2-x| < 0.00001$ then done. Else, let $g_2=frac{g+frac{x}{g}}{2.0}$. Show that the algorithm eventually stops. Or, $lim_{n to infty} g_n = x$.
recursive-algorithms
recursive-algorithms
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
asked Jan 11 at 3:18
nafhgoodnafhgood
1,805422
1,805422
closed as off-topic by Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did Jan 11 at 14:13
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did Jan 11 at 14:13
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Xander Henderson, Lee David Chung Lin, KReiser, Cesareo, Did
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Why do you say it is slow? It is one of the faster ones, especially if you start close to $sqrt x$. If you prove the error is reduced by more than some constant factor you are there. What have you tried?
$endgroup$
– Ross Millikan
Jan 11 at 3:25
$begingroup$
Here is what I observed: $2gg'=g^2+x$, so if $g^2$ and $x$ are close enough then gg'=x. Please help! I did not say that it is slow. I meant show if that is what you meant.
$endgroup$
– nafhgood
Jan 11 at 3:29
add a comment |
$begingroup$
Why do you say it is slow? It is one of the faster ones, especially if you start close to $sqrt x$. If you prove the error is reduced by more than some constant factor you are there. What have you tried?
$endgroup$
– Ross Millikan
Jan 11 at 3:25
$begingroup$
Here is what I observed: $2gg'=g^2+x$, so if $g^2$ and $x$ are close enough then gg'=x. Please help! I did not say that it is slow. I meant show if that is what you meant.
$endgroup$
– nafhgood
Jan 11 at 3:29
$begingroup$
Why do you say it is slow? It is one of the faster ones, especially if you start close to $sqrt x$. If you prove the error is reduced by more than some constant factor you are there. What have you tried?
$endgroup$
– Ross Millikan
Jan 11 at 3:25
$begingroup$
Why do you say it is slow? It is one of the faster ones, especially if you start close to $sqrt x$. If you prove the error is reduced by more than some constant factor you are there. What have you tried?
$endgroup$
– Ross Millikan
Jan 11 at 3:25
$begingroup$
Here is what I observed: $2gg'=g^2+x$, so if $g^2$ and $x$ are close enough then gg'=x. Please help! I did not say that it is slow. I meant show if that is what you meant.
$endgroup$
– nafhgood
Jan 11 at 3:29
$begingroup$
Here is what I observed: $2gg'=g^2+x$, so if $g^2$ and $x$ are close enough then gg'=x. Please help! I did not say that it is slow. I meant show if that is what you meant.
$endgroup$
– nafhgood
Jan 11 at 3:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint: write $g_1=sqrt g+e_1$, so $e_1$ is the error of your first approximation. Let $e_2=g_2-sqrt g$. Show that $e_2$ is smaller than $e_1$ by a factor you can bound away from $1$. Then $e_n$ is smaller than $e_1$ by more than the $n-1$ power of that factor and you are done.
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint: write $g_1=sqrt g+e_1$, so $e_1$ is the error of your first approximation. Let $e_2=g_2-sqrt g$. Show that $e_2$ is smaller than $e_1$ by a factor you can bound away from $1$. Then $e_n$ is smaller than $e_1$ by more than the $n-1$ power of that factor and you are done.
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
$endgroup$
add a comment |
$begingroup$
Hint: write $g_1=sqrt g+e_1$, so $e_1$ is the error of your first approximation. Let $e_2=g_2-sqrt g$. Show that $e_2$ is smaller than $e_1$ by a factor you can bound away from $1$. Then $e_n$ is smaller than $e_1$ by more than the $n-1$ power of that factor and you are done.
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
$endgroup$
add a comment |
$begingroup$
Hint: write $g_1=sqrt g+e_1$, so $e_1$ is the error of your first approximation. Let $e_2=g_2-sqrt g$. Show that $e_2$ is smaller than $e_1$ by a factor you can bound away from $1$. Then $e_n$ is smaller than $e_1$ by more than the $n-1$ power of that factor and you are done.
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
$endgroup$
Hint: write $g_1=sqrt g+e_1$, so $e_1$ is the error of your first approximation. Let $e_2=g_2-sqrt g$. Show that $e_2$ is smaller than $e_1$ by a factor you can bound away from $1$. Then $e_n$ is smaller than $e_1$ by more than the $n-1$ power of that factor and you are done.
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
answered Jan 11 at 3:37
Ross MillikanRoss Millikan
295k23198371
295k23198371
add a comment |
add a comment |
$begingroup$
Why do you say it is slow? It is one of the faster ones, especially if you start close to $sqrt x$. If you prove the error is reduced by more than some constant factor you are there. What have you tried?
$endgroup$
– Ross Millikan
Jan 11 at 3:25
$begingroup$
Here is what I observed: $2gg'=g^2+x$, so if $g^2$ and $x$ are close enough then gg'=x. Please help! I did not say that it is slow. I meant show if that is what you meant.
$endgroup$
– nafhgood
Jan 11 at 3:29