From Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, 2nd edition Apply Algorithm 1.4.1 on P.38(picture attached) with f(x)=x^3+2^x, T = 100, A = 5, B = 4, δ = 0.1. Draw the corresponding walkthrough as shown in P.39(picture attached)
From Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, 2nd edition Apply Algorithm 1.4.1 on P.38(picture attached) with f(x)=x^3+2^x, T = 100, A = 5, B = 4, δ = 0.1. Draw the corresponding walkthrough as shown in P.39(picture attached)
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
From Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, 2nd edition
Apply
![// When the condition between the "If" and "Then" is true, the steps between
// This pseudo-code contains 2 conditional statements with no Else part:
it can be madé as
Algorithm 1.4.1: The Bisection Algorithm for Solving f(x) = T
Begin
z - (A + B) / 2;
While (z - A >= d) Do
If (f(z)<= T) Then
A - z;
%3D
End;
If (f(z)>= T) Then
BE Z;
End;
z - (A + B) / 2;
End;
Return(z);
End.
// “Then" and “End" are done. but when it is false nothing at all is o
// What would happen if at some point, (z) = T?
%3D](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F341d06cc-fc5c-4ccd-b5b0-8d9552e9adb4%2F987b8a74-f88a-4ad6-a4bd-85fbaabf2b8f%2F6iugdc_processed.jpeg&w=3840&q=75)
Transcribed Image Text:// When the condition between the "If" and "Then" is true, the steps between
// This pseudo-code contains 2 conditional statements with no Else part:
it can be madé as
Algorithm 1.4.1: The Bisection Algorithm for Solving f(x) = T
Begin
z - (A + B) / 2;
While (z - A >= d) Do
If (f(z)<= T) Then
A - z;
%3D
End;
If (f(z)>= T) Then
BE Z;
End;
z - (A + B) / 2;
End;
Return(z);
End.
// “Then" and “End" are done. but when it is false nothing at all is o
// What would happen if at some point, (z) = T?
%3D
![1.4 Numerical Solutions
39
Walkthrough with input f(x) = x' + 2*, T = 200, A = 5, B = 10, and ô = 0.005:
/ Each line in the table corresponds to fixed values of A and B (and z between them).
%3D
|z - A|
A
B
f (z)
5
7.5
10
2.5
602.894 ...
6.25
7.5
1.25
320.249 ...
5.625
6.25
%3D
.625
227.329 ...
5.3125
5.625
.3125
189.672 ...
5.3125
5.46875
.15625
207.840 ..
...
5.390625
5.46875
.078125
198.596 ...
5.390625
5.4296875
.0390625
203.177 ...
5.41015625
5.4296875
.01953125
200.876 ...
5.400390625
5.41015625
.009765625
199.733 ...
5.400390625 5.4052734375
.0048828125 (200.304...)
The algorithm returns z =
f the equation, x*, and this number has an absolute error that is < 8
5.405 273 437 5 as an approximation of the solution
0.005.
If we continue, we find 5.402 668 655 < x* < 5.402 668 656,
but no one can ever know the exact (numerical) value of x*.
Before this algorithm can be executed, certain “preconditions" must be met:
f(x) must be a continuous and computable function.
A target value T for the function f(x) must be specified
. An x-value A where (A) < T must be specified.
. An x-value B where f(B) > T must be specified.
A bound ô on the absolute error in the approximation must be given.
// "guessed" somehow
// “guessed" too
Continuity is a concept from calculus; it ensures f has no sudden "jumps" in
value so that the Intermediate Value Theorem applies.
And f must be in a form that can be evaluated fairly accurately despite roundoff
errors. In practical applications, this precondition is almost always met.
Very often the target value T for the function is taken to be zero.
Preconditions 3 and 4 imply that A # B and (at least one) exact solution x* is
between A and B.
Therefore, either A < x* < B or B < x* < A.
ô provides "quality control"; it specifies how "good" an approximation we will
get and gives a termination criterion for the algorithm.
But how many iterations will be done?
A
Zi
В
X**](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F341d06cc-fc5c-4ccd-b5b0-8d9552e9adb4%2F987b8a74-f88a-4ad6-a4bd-85fbaabf2b8f%2F1mxt1y7_processed.jpeg&w=3840&q=75)
Transcribed Image Text:1.4 Numerical Solutions
39
Walkthrough with input f(x) = x' + 2*, T = 200, A = 5, B = 10, and ô = 0.005:
/ Each line in the table corresponds to fixed values of A and B (and z between them).
%3D
|z - A|
A
B
f (z)
5
7.5
10
2.5
602.894 ...
6.25
7.5
1.25
320.249 ...
5.625
6.25
%3D
.625
227.329 ...
5.3125
5.625
.3125
189.672 ...
5.3125
5.46875
.15625
207.840 ..
...
5.390625
5.46875
.078125
198.596 ...
5.390625
5.4296875
.0390625
203.177 ...
5.41015625
5.4296875
.01953125
200.876 ...
5.400390625
5.41015625
.009765625
199.733 ...
5.400390625 5.4052734375
.0048828125 (200.304...)
The algorithm returns z =
f the equation, x*, and this number has an absolute error that is < 8
5.405 273 437 5 as an approximation of the solution
0.005.
If we continue, we find 5.402 668 655 < x* < 5.402 668 656,
but no one can ever know the exact (numerical) value of x*.
Before this algorithm can be executed, certain “preconditions" must be met:
f(x) must be a continuous and computable function.
A target value T for the function f(x) must be specified
. An x-value A where (A) < T must be specified.
. An x-value B where f(B) > T must be specified.
A bound ô on the absolute error in the approximation must be given.
// "guessed" somehow
// “guessed" too
Continuity is a concept from calculus; it ensures f has no sudden "jumps" in
value so that the Intermediate Value Theorem applies.
And f must be in a form that can be evaluated fairly accurately despite roundoff
errors. In practical applications, this precondition is almost always met.
Very often the target value T for the function is taken to be zero.
Preconditions 3 and 4 imply that A # B and (at least one) exact solution x* is
between A and B.
Therefore, either A < x* < B or B < x* < A.
ô provides "quality control"; it specifies how "good" an approximation we will
get and gives a termination criterion for the algorithm.
But how many iterations will be done?
A
Zi
В
X**
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 3 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education