From Fundamentals of Discrete Math for Computer Science: A Problem-Solving Primer, 2nd editionApply 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) // 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é asAlgorithm 1.4.1: The Bisection Algorithm for Solving f(x) = TBeginz - (A + B) / 2;While (z - A >= d) DoIf (f(z)<= T) ThenA - z;%3DEnd;If (f(z)>= T) ThenBE 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 Solutions39Walkthrough 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|ABf (z)57.5102.5602.894 ...6.257.51.25320.249 ...5.6256.25%3D.625227.329 ...5.31255.625.3125189.672 ...5.31255.46875.15625207.840 .....5.3906255.46875.078125198.596 ...5.3906255.4296875.0390625203.177 ...5.410156255.4296875.01953125200.876 ...5.4003906255.41015625.009765625199.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 < 85.405 273 437 5 as an approximation of the solution0.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" tooContinuity is a concept from calculus; it ensures f has no sudden "jumps" invalue so that the Intermediate Value Theorem applies.And f must be in a form that can be evaluated fairly accurately despite roundofferrors. 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* isbetween A and B.Therefore, either A < x* < B or B < x* < A.ô provides "quality control"; it specifies how "good" an approximation we willget and gives a termination criterion for the algorithm.But how many iterations will be done?AZiВX**

Answered: From Fundamentals of Discrete Math for…

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

See similar textbooks

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)

// 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**

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

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.

Similar questions