Mixing
Approximation to $sqrt{5}$ correct to an exactitude of $10^{-10}$ [duplicate]
$begingroup$
This question already has an answer here:
Is there any simple method to calculate $sqrt x$ without using logarithm
13 answers
I am attempting to resolve the following problem:
Find an approximation to $sqrt{5}$ correct to an exactitude of $10^{-10}$ using the bisection algorithm.
From what I understand, $sqrt{5}$ has to be placed in function of $x$ but I am not sure where to go from there.
Also, a function in Mathematica are given to do the calculations in which the function $f(x)$, $a$ and $b$ (from the interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs), the tolerance and the number of iterations.
numerical-methods algorithms bisection
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
$endgroup$
marked as duplicate by Simply Beautiful Art, Jack D'Aurizio, Xander Henderson, mrtaurho, user91500 Jan 15 at 6:40
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
$begingroup$
This question already has an answer here:
Is there any simple method to calculate $sqrt x$ without using logarithm
13 answers
I am attempting to resolve the following problem:
Find an approximation to $sqrt{5}$ correct to an exactitude of $10^{-10}$ using the bisection algorithm.
From what I understand, $sqrt{5}$ has to be placed in function of $x$ but I am not sure where to go from there.
Also, a function in Mathematica are given to do the calculations in which the function $f(x)$, $a$ and $b$ (from the interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs), the tolerance and the number of iterations.
numerical-methods algorithms bisection
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
$endgroup$
marked as duplicate by Simply Beautiful Art, Jack D'Aurizio, Xander Henderson, mrtaurho, user91500 Jan 15 at 6:40
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
3
$begingroup$
Are you supposed to do this by hand? Because an accuracy of $10^{-10}$ requires over $30$ bisections. That's just tedious and boring, and has very little educational value over, say, $10^{-2}$.
$endgroup$
– Arthur
Jan 14 at 16:33
$begingroup$
Note that $sqrt{5}$ is the solution to $x^2-5 = 0$.
$endgroup$
– D.B.
Jan 14 at 16:35
$begingroup$
@Arthur Algorithms in Mathematica are given to solve the problem.
$endgroup$
– Omari Celestine
Jan 14 at 17:23
$begingroup$
Bisection is definetely not an efficient way for approximating $sqrt{5}$. If you exploit the convergents of $frac{1+sqrt{5}}{2}$, which are ratios of consecutive Fibonacci numbers, you have that $2frac{F_{27}}{F_{26}}-1$ meets the wanted constraints. This can be through $leq 15$ integer multiplications/ratios, see math.stackexchange.com/a/2081266/44121
$endgroup$
– Jack D'Aurizio
Jan 14 at 18:04
$begingroup$
@SimplyBeautifulArt It is not the same problem.
$endgroup$
– Omari Celestine
Jan 14 at 20:41
add a comment |
$begingroup$
This question already has an answer here:
Is there any simple method to calculate $sqrt x$ without using logarithm
13 answers
I am attempting to resolve the following problem:
Find an approximation to $sqrt{5}$ correct to an exactitude of $10^{-10}$ using the bisection algorithm.
From what I understand, $sqrt{5}$ has to be placed in function of $x$ but I am not sure where to go from there.
Also, a function in Mathematica are given to do the calculations in which the function $f(x)$, $a$ and $b$ (from the interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs), the tolerance and the number of iterations.
numerical-methods algorithms bisection
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
$endgroup$
This question already has an answer here:
Is there any simple method to calculate $sqrt x$ without using logarithm
13 answers
I am attempting to resolve the following problem:
Find an approximation to $sqrt{5}$ correct to an exactitude of $10^{-10}$ using the bisection algorithm.
From what I understand, $sqrt{5}$ has to be placed in function of $x$ but I am not sure where to go from there.
Also, a function in Mathematica are given to do the calculations in which the function $f(x)$, $a$ and $b$ (from the interval $[a, b]$ where $f(a)$ and $f(b)$ have opposite signs), the tolerance and the number of iterations.
This question already has an answer here:
Is there any simple method to calculate $sqrt x$ without using logarithm
13 answers
numerical-methods algorithms bisection
numerical-methods algorithms bisection
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
edited Jan 14 at 20:35
Omari Celestine
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
asked Jan 14 at 16:21
Omari CelestineOmari Celestine
608111
608111
marked as duplicate by Simply Beautiful Art, Jack D'Aurizio, Xander Henderson, mrtaurho, user91500 Jan 15 at 6:40
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Simply Beautiful Art, Jack D'Aurizio, Xander Henderson, mrtaurho, user91500 Jan 15 at 6:40
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
3
$begingroup$
Are you supposed to do this by hand? Because an accuracy of $10^{-10}$ requires over $30$ bisections. That's just tedious and boring, and has very little educational value over, say, $10^{-2}$.
$endgroup$
– Arthur
Jan 14 at 16:33
$begingroup$
Note that $sqrt{5}$ is the solution to $x^2-5 = 0$.
$endgroup$
– D.B.
Jan 14 at 16:35
$begingroup$
@Arthur Algorithms in Mathematica are given to solve the problem.
$endgroup$
– Omari Celestine
Jan 14 at 17:23
$begingroup$
Bisection is definetely not an efficient way for approximating $sqrt{5}$. If you exploit the convergents of $frac{1+sqrt{5}}{2}$, which are ratios of consecutive Fibonacci numbers, you have that $2frac{F_{27}}{F_{26}}-1$ meets the wanted constraints. This can be through $leq 15$ integer multiplications/ratios, see math.stackexchange.com/a/2081266/44121
$endgroup$
– Jack D'Aurizio
Jan 14 at 18:04
$begingroup$
@SimplyBeautifulArt It is not the same problem.
$endgroup$
– Omari Celestine
Jan 14 at 20:41
add a comment |
3
$begingroup$
Are you supposed to do this by hand? Because an accuracy of $10^{-10}$ requires over $30$ bisections. That's just tedious and boring, and has very little educational value over, say, $10^{-2}$.
$endgroup$
– Arthur
Jan 14 at 16:33
$begingroup$
Note that $sqrt{5}$ is the solution to $x^2-5 = 0$.
$endgroup$
– D.B.
Jan 14 at 16:35
$begingroup$
@Arthur Algorithms in Mathematica are given to solve the problem.
$endgroup$
– Omari Celestine
Jan 14 at 17:23
$begingroup$
Bisection is definetely not an efficient way for approximating $sqrt{5}$. If you exploit the convergents of $frac{1+sqrt{5}}{2}$, which are ratios of consecutive Fibonacci numbers, you have that $2frac{F_{27}}{F_{26}}-1$ meets the wanted constraints. This can be through $leq 15$ integer multiplications/ratios, see math.stackexchange.com/a/2081266/44121
$endgroup$
– Jack D'Aurizio
Jan 14 at 18:04
$begingroup$
@SimplyBeautifulArt It is not the same problem.
$endgroup$
– Omari Celestine
Jan 14 at 20:41
3
3
$begingroup$
Are you supposed to do this by hand? Because an accuracy of $10^{-10}$ requires over $30$ bisections. That's just tedious and boring, and has very little educational value over, say, $10^{-2}$.
$endgroup$
– Arthur
Jan 14 at 16:33
$begingroup$
Are you supposed to do this by hand? Because an accuracy of $10^{-10}$ requires over $30$ bisections. That's just tedious and boring, and has very little educational value over, say, $10^{-2}$.
$endgroup$
– Arthur
Jan 14 at 16:33
$begingroup$
Note that $sqrt{5}$ is the solution to $x^2-5 = 0$.
$endgroup$
– D.B.
Jan 14 at 16:35
$begingroup$
Note that $sqrt{5}$ is the solution to $x^2-5 = 0$.
$endgroup$
– D.B.
Jan 14 at 16:35
$begingroup$
@Arthur Algorithms in Mathematica are given to solve the problem.
$endgroup$
– Omari Celestine
Jan 14 at 17:23
$begingroup$
@Arthur Algorithms in Mathematica are given to solve the problem.
$endgroup$
– Omari Celestine
Jan 14 at 17:23
$begingroup$
Bisection is definetely not an efficient way for approximating $sqrt{5}$. If you exploit the convergents of $frac{1+sqrt{5}}{2}$, which are ratios of consecutive Fibonacci numbers, you have that $2frac{F_{27}}{F_{26}}-1$ meets the wanted constraints. This can be through $leq 15$ integer multiplications/ratios, see math.stackexchange.com/a/2081266/44121
$endgroup$
– Jack D'Aurizio
Jan 14 at 18:04
$begingroup$
Bisection is definetely not an efficient way for approximating $sqrt{5}$. If you exploit the convergents of $frac{1+sqrt{5}}{2}$, which are ratios of consecutive Fibonacci numbers, you have that $2frac{F_{27}}{F_{26}}-1$ meets the wanted constraints. This can be through $leq 15$ integer multiplications/ratios, see math.stackexchange.com/a/2081266/44121
$endgroup$
– Jack D'Aurizio
Jan 14 at 18:04
$begingroup$
@SimplyBeautifulArt It is not the same problem.
$endgroup$
– Omari Celestine
Jan 14 at 20:41
$begingroup$
@SimplyBeautifulArt It is not the same problem.
$endgroup$
– Omari Celestine
Jan 14 at 20:41
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The bisection method is a method for finding the roots of a continuous function ie finding $ x $ such that $ f(x) $ equals zero. Thus, you need a function which has a zero equal to $ sqrt{5} $. The function $x^2 - 5 = f(x)$ will do.
Then, select an initial interval $[a, b]$ which contains the root. and for which $f(a)$ and $f(b)$ have different signs. The interval $[2, 3]$ will do.
The bisection method converges by repeatedly cutting the length of this interval in half.
Here is pseudocode from wikipedia:
N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
c ← (a + b)/2 # new midpoint
If f(c) = 0 or (b – a)/2 < TOL then # solution found
Output(c)
Stop
EndIf
N ← N + 1 # increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded
The difference between the midpoint of the $n-th$ interval and the root $c$ is given by
$$|c_n - c| leq frac{|b-a|}{2^n}$$
which follows directly from the fact that the interval is halved each iteration. You can figure out the number of iterations necessary for the desired $epsilon$ using this formula.
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
$endgroup$
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The bisection method is a method for finding the roots of a continuous function ie finding $ x $ such that $ f(x) $ equals zero. Thus, you need a function which has a zero equal to $ sqrt{5} $. The function $x^2 - 5 = f(x)$ will do.
Then, select an initial interval $[a, b]$ which contains the root. and for which $f(a)$ and $f(b)$ have different signs. The interval $[2, 3]$ will do.
The bisection method converges by repeatedly cutting the length of this interval in half.
Here is pseudocode from wikipedia:
N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
c ← (a + b)/2 # new midpoint
If f(c) = 0 or (b – a)/2 < TOL then # solution found
Output(c)
Stop
EndIf
N ← N + 1 # increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded
The difference between the midpoint of the $n-th$ interval and the root $c$ is given by
$$|c_n - c| leq frac{|b-a|}{2^n}$$
which follows directly from the fact that the interval is halved each iteration. You can figure out the number of iterations necessary for the desired $epsilon$ using this formula.
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
$endgroup$
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
add a comment |
$begingroup$
The bisection method is a method for finding the roots of a continuous function ie finding $ x $ such that $ f(x) $ equals zero. Thus, you need a function which has a zero equal to $ sqrt{5} $. The function $x^2 - 5 = f(x)$ will do.
Then, select an initial interval $[a, b]$ which contains the root. and for which $f(a)$ and $f(b)$ have different signs. The interval $[2, 3]$ will do.
The bisection method converges by repeatedly cutting the length of this interval in half.
Here is pseudocode from wikipedia:
N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
c ← (a + b)/2 # new midpoint
If f(c) = 0 or (b – a)/2 < TOL then # solution found
Output(c)
Stop
EndIf
N ← N + 1 # increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded
The difference between the midpoint of the $n-th$ interval and the root $c$ is given by
$$|c_n - c| leq frac{|b-a|}{2^n}$$
which follows directly from the fact that the interval is halved each iteration. You can figure out the number of iterations necessary for the desired $epsilon$ using this formula.
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
$endgroup$
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
add a comment |
$begingroup$
The bisection method is a method for finding the roots of a continuous function ie finding $ x $ such that $ f(x) $ equals zero. Thus, you need a function which has a zero equal to $ sqrt{5} $. The function $x^2 - 5 = f(x)$ will do.
Then, select an initial interval $[a, b]$ which contains the root. and for which $f(a)$ and $f(b)$ have different signs. The interval $[2, 3]$ will do.
The bisection method converges by repeatedly cutting the length of this interval in half.
Here is pseudocode from wikipedia:
N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
c ← (a + b)/2 # new midpoint
If f(c) = 0 or (b – a)/2 < TOL then # solution found
Output(c)
Stop
EndIf
N ← N + 1 # increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded
The difference between the midpoint of the $n-th$ interval and the root $c$ is given by
$$|c_n - c| leq frac{|b-a|}{2^n}$$
which follows directly from the fact that the interval is halved each iteration. You can figure out the number of iterations necessary for the desired $epsilon$ using this formula.
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
$endgroup$
The bisection method is a method for finding the roots of a continuous function ie finding $ x $ such that $ f(x) $ equals zero. Thus, you need a function which has a zero equal to $ sqrt{5} $. The function $x^2 - 5 = f(x)$ will do.
Then, select an initial interval $[a, b]$ which contains the root. and for which $f(a)$ and $f(b)$ have different signs. The interval $[2, 3]$ will do.
The bisection method converges by repeatedly cutting the length of this interval in half.
Here is pseudocode from wikipedia:
N ← 1
While N ≤ NMAX # limit iterations to prevent infinite loop
c ← (a + b)/2 # new midpoint
If f(c) = 0 or (b – a)/2 < TOL then # solution found
Output(c)
Stop
EndIf
N ← N + 1 # increment step counter
If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval
EndWhile
Output("Method failed.") # max number of steps exceeded
The difference between the midpoint of the $n-th$ interval and the root $c$ is given by
$$|c_n - c| leq frac{|b-a|}{2^n}$$
which follows directly from the fact that the interval is halved each iteration. You can figure out the number of iterations necessary for the desired $epsilon$ using this formula.
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
answered Jan 14 at 16:36
Klint QinamiKlint Qinami
1,137410
1,137410
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
add a comment |
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
How do I find the intervals?
$endgroup$
– Omari Celestine
Jan 14 at 17:24
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
$begingroup$
It is given in the algorithm description "If sign(f(c)) = sign(f(a)) then a ← c else b ← c # new interval"
$endgroup$
– Klint Qinami
Jan 14 at 21:02
add a comment |
3
$begingroup$
Are you supposed to do this by hand? Because an accuracy of $10^{-10}$ requires over $30$ bisections. That's just tedious and boring, and has very little educational value over, say, $10^{-2}$.
$endgroup$
– Arthur
Jan 14 at 16:33
$begingroup$
Note that $sqrt{5}$ is the solution to $x^2-5 = 0$.
$endgroup$
– D.B.
Jan 14 at 16:35
$begingroup$
@Arthur Algorithms in Mathematica are given to solve the problem.
$endgroup$
– Omari Celestine
Jan 14 at 17:23
$begingroup$
Bisection is definetely not an efficient way for approximating $sqrt{5}$. If you exploit the convergents of $frac{1+sqrt{5}}{2}$, which are ratios of consecutive Fibonacci numbers, you have that $2frac{F_{27}}{F_{26}}-1$ meets the wanted constraints. This can be through $leq 15$ integer multiplications/ratios, see math.stackexchange.com/a/2081266/44121
$endgroup$
– Jack D'Aurizio
Jan 14 at 18:04
$begingroup$
@SimplyBeautifulArt It is not the same problem.
$endgroup$
– Omari Celestine
Jan 14 at 20:41