#bisection method

[dailyvahine]

Hey does anyone have exercises with their solution about numerical methods (bisection method, fixed point method, newton raphson method)

[habituallearner]

An application of the intermediate value theorem is the bisection method.

[lawsofemotion]

Tangent-line Approximations

The line tangent to the graph of y = f(x) at x = a describes the behavior of that graph near the point P = (a,f(a)) better than any other straight line through P.

Approximating Values of x Near a To approximate values of x near a, consider the equation of the tangent line to y = f(x) at x = a:

y = f(a) + f'(a)(x - a)

Therefore, the approximation is the following:

f(x) ≈ f(a) + f'(a)(x - a)

The Error Estimate If the tangent line at x = a is used to approximate f(x) near a with the following equation:

f(x) ≈ f(a) + f'(a)(x - a)

Then the error E(x) in this approximation is the following:

E(x) = true value - approximate value E(x) = f(x) - f(a) + f'(a)(x - a)

If f is twice differentiable on an interval containing a and x, then there is some point X between a and x that is the following:

In particular, if |f''(t)| ≤ K on an interval containing a and x, then the following is true:

Error in Tangent-line Approximation in Terms of Differentials The error in tangent-line approximation can be interpreted in terms of differentials.

If x - a = Δx = dx, then the change in height to the graph of y = f(x) from x = a to x = a + Δx is the following:

f(a + Δx) - f(a) = Δy

The corresponding change in height to the tangent line is the following:

f'(a)(x - a) = f'(a)dx

It is just the value at x = a of the differential dy = f'(x)dx.

Therefore:

E(x) = Δy - dy

The fact that the approximating line is tangent to the graph of f at x = a implies that the error is small compared with Δx as Δx approaches 0.

If |f''(t)| ≤ K near t = a, then the following is true:

Therefore:

Errors in Measurement Suppose that a quantity x is obtained by measurement, and that a second quantity y is determined as a function of x, y = f(x). Any error involved in the measurement of x will result in an error in the calculated value of y as well.

It is convenient to use the differential dx = Δx to denote the error involved in the measurement of x. The corresponding error in y is Δy = f(x + dx) - f(x).

The tangent-line approximation gives the following first-order approximation of Δy:

Δy ≈ dy = f'(x)dx

The errors dx = Δx and dy ≈ Δy are absolute errors. Errors are frequently represented in relative terms, where they are represented as a fraction or percentage of the size of the quantity being expressed. The relative error in a measurement of x with absolute error dx is dx/x.

Bisection Method Suppose a root, or zero, needs to be found of the function f(x), which is a solution x = r of the equation f(x) = 0. Unless f is a particularly simple function, such as a linear or quadratic polynomial function, there does not seem to be a general procedure for finding its roots exactly.

Suppose that f is continuous on [a,b], and that f has opposite signs at the opposite ends of the interval, such as f(a) < 0 and f(b) > 0. The intermediate-value theorem assures that at least one root r must exist in [a,b].

To try and approximate this existing root, bisect [a,b] at c and choose the interval, [a,c] or [c,b], that f has opposite signs at opposite ends to use as the new search interval. If f( c) = 0, then the root is found.

This bisection process is repeated, where at each stage yielding an interval containing the root that is half as long as the interval at the previous stage.

The process is finished when the interval is short enough that its midpoint has the desired degree of closeness to the root.

The bisection method always works for continuous functions, but it is a slow method, because many values of f(x) must be computed before achieving an accuracy in locating the root.

Newton's Method If f is differentiable near the root r, then tangent lines can be used to produce a sequence of approximations to the root that approaches the root quite quickly.

To begin, make an initial guess of the root, such as x = x₀. Let x₁ be the x-intercept of the tangent line to y = f(x) at x = x₀. It can be expected that x₁ is closer to the root than x₀.

The process is repeated to get closer to r, where xᵥ₊₁ is the x-intercept of the tangent line at x = xᵥ. The tangent line at x = x₀ has the following equation:

y = f(x₀) + f'(x₀)(x - x₀)

Since the point (x₁,0) lies on this line:

Generally:

A calculator is generally used to calculate the successive approximations x₁, x₂, x₃, ..., observing whether they appear to converge into a limit.

If the following exists:

And, if the following is continuous near r:

Then r must be a root of f, because:

Which follows that f( r) = 0, so r = r.

Newton's method does not always work well. If the first derivative f' is very small near the root, or if the second derivative f'' is very large near the root, a single iteration of the formula can make the value very close to the root or very far away from the root.

Conditions for Newton's Method The following gives sufficient conditions for the Newton approximations to converge to a root r of f, if the initial guess x₀ is sufficiently close to that root.

Suppose that f, f', and f'' are continuous on an interval I containing xᵥ, xᵥ₊₁, and a root r of f(x) = 0. Suppose that there exist constants K and L > 0, such that for all x in I, the following is true:

|f''(x)| ≤ K |f'(x)| ≥ L

Then:

If K/2L is not large, such as K/2L < 1, then the above states that xᵥ converges quickly to r once v becomes large enough that |xᵥ - r| < 1.

The conditions for Newton's method have theoretical significance but little practical significance. In practice, successive approximations are computed using Newton's formula and observed whether they seem to converge to a limit. If they do, and if the values of f at these approximations approach 0, there is confidence that the root is located.

Find an appropriate value for the following using a suitable tangent line:

Let f(x) = √x

Then:

Let a = 25, the closest perfect square to 26. Then:

Then for all x near 25:

Since f''(x) < 0 for all x > 0, the graph of f(x) is concave down, where the graph lies below the tangent lines, making the tangent line height greater than the function's value at that point. Since the equation of the tangent line was used to conclude f(x) ≈ 5.1, then it implies the real value of f(x) < 5.1.

Therefore:

Obtain an estimate for the error in this approximation.

If 25 ≤ t ≤ 26, then:

Then the estimate of the size of the error is the following:

Therefore, the estimate for the error is 0.001. Since concavity implies f(x) < 5.1, then the following can be asserted:

Find an approximate value for cos62°.

Let f(x) = cosx

Then:

f'(x) = -sinx f''(x) = -cosx

Let a = 60° = π/3, the closest measure that corresponds to a rational number on the unit circle. Then:

f(a) = cos(π/3) = 1/2 f'(a) = -sin(π/3) = -√3/2

Then for all x near π/3:

Since f''(x) < 0 for all x near π/3, the graph of f(x) is concave down, where the graph lies below the tangent lines, making the tangent line height greater than the function's value at that point. Since the equation of the tangent line was used to conclude f(x) ≈ 0.469770, then it implies the real value of f(x) < 0.469770.

Therefore:

cos62° < 0.469770

Obtain an estimate for the error in this approximation.

If 60 ≤ t ≤ 62, or π/3 ≤ t ≤ 62π/180, then:

Then the estimate of the size of the error is the following:

Therefore, the estimate for the error is 0.00031. Since concavity implies f(x) < 0.469770, then the following can be asserted:

Use a suitable tangent-line approximation to estimate the following, use concavity to determine the sign of error, and obtain an estimate of the size of error:

Let f(x) = √x

Then:

Let a = 49, the closest perfect square to 50. Then:

Then for all x near 49:

Since f''(x) < 0 for all x > 0, the graph of f(x) is concave down, where the graph lies below the tangent lines, making the tangent line height greater than the function's value at that point. Since the equation of the tangent line was used to conclude f(x) ≈ 7.07142, then it implies the real value of f(x) < 7.07142, and that E < 0 (sign of error).

If 49 ≤ t ≤ 50, then:

Then the estimate of the size of the error is the following:

Use a suitable tangent-line approximation to estimate the following, use concavity to determine the sign of error, and obtain an estimate of the size of error:

Let:

Then:

Let a = 81, the closest perfect fourth root to 85. Then:

Then for all x near 81:

Since f''(x) < 0 for all x, the graph of f(x) is concave down, where the graph lies below the tangent lines, making the tangent line height greater than the function's value at that point. Since the equation of the tangent line was used to conclude f(x) ≈ 3.03703, then it implies the real value of f(x) < 3.03703, and that E < 0 (sign of error).

If 81 ≤ t ≤ 85, then:

Then the estimate of the size of the error is the following:

Use a suitable tangent-line approximation to estimate the following, use concavity to determine the sign of error, and obtain an estimate of the size of error:

Let f(x) = e⁻˟

Then:

f'(x) = -e⁻˟ f''(x) = e⁻˟

Let a = 0, the closest value to -0.1 that returns a whole number.

Then:

f(a) = e⁻⁰ = 1 f'(a) = -e⁻⁰ = -1

Then for all x near 0:

Since f''(x) > 0 for all x, the graph of f(x) is concave up, where the graph lies above the tangent lines, making the tangent line height lesser than the function's value at that point. Since the equation of the tangent line was used to conclude f(x) ≈ 0.9, then it implies the real value of f(x) > 0.9, and that E > 0 (sign of error).

If -0.1 ≤ t ≤ 0, then:

Then the estimate of the size of the error is the following:

Use a suitable tangent-line approximation to estimate the following, use concavity to determine the sign of error, and obtain an estimate of the size of error:

Arctan1.05

Let f(x) = Arctanx

Then:

Let a = 1, the closest value to 1.05 that returns a rational number. Then:

Then for all x near 1:

Since f''(x) < 0 for all x > 0, the graph of f(x) is concave down, where the graph lies below the tangent lines, making the tangent line height greater than the function's value at that point. Since the equation of the tangent line was used to conclude f(x) ≈ 0.810398, then it implies the real value of f(x) < 0.810398, and that E < 0 (sign of error).

If 1 ≤ t ≤ 1.05, then:

Then the estimate of the size of the error is the following:

The length of x of the side of a square is measured with a 1 percent error. By approximately what percentage will the calculated area A = x² of the square be in error?

Let f(x) = x²

Then:

Δy ≈ dy = f'(x)dx ΔA ≈ dA = 2xdx

Dividing each term by A:

The relative error in a measurement of x with absolute error dx is 1% or 0.01 = dx/x. Then:

Therefore, the area of the square is in error by approximately 2%.

Approximately what percentage error can result in the calculation of the volume of a cube if the edge is measured to within 2 percent tolerance?

Let f(x) = x³

Then:

Δy ≈ dy = f'(x)dx ΔV ≈ dV = 3x²dx

Dividing each term by V:

The relative error in a measurement of x with absolute error dx is 2% or 0.02 = dx/x. Then:

Therefore, the volume of the cube is in error by approximately 6%.

Use Newton's method to find the real root(s) of the equation x³ + x - 1 = 0.

Let f(x) = x³ + x - 1 Then f'(x) = 3x² + 1

Since f'(x) > 0 for all x, the function is increasing and implies only to have one root r.

Since f(0) = -1, find another point that makes f(x) > 0. f(1) = 1 > 0

Therefore, the interval that will be used is (0,1).

Initial guess = x₀ = 0.5.

Since it converges into a limit, the one root to f(x) is r = 0.682327.

Use Newton's method to find the real root(s) of the equation x³ - 2 = 0.

Let f(x) = x³ - 2 Then f'(x) = 3x²

Since f'(x) > 0 for all x, the function is increasing and implies only to have one root r.

Since f(0) = -2, find another point that makes f(x) > 0. f(1) = -1 f(2) = 5

Therefore, the interval that will be used is (0,2).

Initial guess = x₀ = 0.5.

Since it converges into a limit, the one root to f(x) is r = 1.259921.

Use Newton's method to find the real root(s) of the equation x³ + 3x² - 2 = 0.

Let f(x) = x³ + 3x² - 2 Then f'(x) = 3x² + 6x

Using the first derivative test to determine the amount of roots f(x) has: f'(x) = 3x² + 6x 0 = 3x² + 6x 0 = 3x(x + 2)

The critical points are x = -2, 0.

Placing them in a number line, choosing test points:

f'(-3) = positive, f(x) increasing f'(-1) = negative, f(x) decreasing f'(1) = positive, f(x) increasing

Intervals of f(x) increasing: (-∞,-2)U(0,∞) Interval of f(x) decreasing: (-2,0)

Labeling these intervals: P₁ = (-∞,-2) P₂ = (0,∞) P₃ = (-2,0)

Determining the y-coordinates for each x-coordinate in P₁:

For -∞:

Therefore, f(-∞) = -∞, or (-∞,-∞) is in f(x).

For -2:

f(-2) = (-2)³ + 3(-2)² - 2 = 2

Therefore, f(-2) = 2, or (-2,2) is in f(x).

Since the y-coordinate -∞ becomes 2 at x = -2, f(x) crosses the x-axis, implying f(x) has one root between P₁ = (-∞,-2).

Determining the y-coordinates for each x-coordinate in P₂:

For 0:

f(0) = -2

Therefore, f(0) = -2, or (0,-2) is in f(x).

For ∞:

Therefore, f(∞) = ∞, or (∞,∞) is in f(x).

Since the y-coordinate -2 becomes ∞ as x approaches ∞, f(x) crosses the x-axis, implying f(x) has one root between P₂ = (0,∞).

Determining the y-coordinates for each x-coordinate in P₃:

For -2:

f(-2) = (-2)³ + 3(-2)² - 2 = 2

Therefore, f(-2) = 2, or (-2,2) is in f(x).

For 0:

f(0) = -2

Therefore, f(0) = -2, or (0,-2) is in f(x).

Since the y-coordinate 2 becomes -2 at x = 0, f(x) crosses the x-axis, implying f(x) has one root between P₃ = (-2,0).

Labeling these roots: r₁ in (-∞,-2) r₂ in (0,∞) r₃ in (-2,0)

Determining the root r₁ in (-∞,-2):

Initial guess (should be closer to the real number) = x₀ = -3.

Since it converges into a limit, the first root to f(x) is r₁ = -2.732050.

Determining the root r₂ in (0,∞):

Initial guess (should be closer to the real number) = x₀ = 1.

Since it converges into a limit, the second root to f(x) is r₂ = 0.732050.

Determining the root r₃ in (-2,0):

Initial guess = x₀ = -1.

Since it converges into a limit, the third root to f(x) is r₃ = -1.

Therefore, the three roots to f(x) are -2.732050, -1, and 0.732050.

Find the positive solution of the equation e˟ = 2cosx.

Let f(x) = e˟ - 2cosx Then f'(x) = e˟ + 2sinx

The domain of e˟ is ℝ with an intercept at (0,1), which is beneath 2cosx, because 2cosx's maximum height is at y = 2. Additionally, by the time x = 1, e˟ > 2 = 2cosx's maximum height, so the interval that can be used to search for the solution is small: (0,π/3 ≈ 1.047).

Initial guess = x₀ = 0.7.

Note that calculations will be in radian mode.

Since it converges into a limit, the solution is x = 0.539785.

Find the solution of the equation sinx = 1 - x² between 0 and π/2.

Let f(x) = 1 - x² - sinx Then f'(x) = -2x - cosx

Initial guess = x₀ = 0.5.

Note that calculations will be in radian mode.

Since it converges into a limit, the solution is x = 0.636732.

[monthadar-blog]

Bisection Method vs Fixed-Point Iteration

How much faster is FPI compared to the Bisection Method? For that we need to think about accuracy. Or the error compared to the true solution. Now I know we don't know the true solution otherwise we would not be needing these numeric methods! But we can enclose the true solution inside an interval where we know that it lies in it (well for a continuous functions in the interval of interest).

Starting from The Bisection Method we know for each step the interval [a,b] is cut in half! After n steps our new interval [an, bn] have the length (b-a)/2^n. But choosing the solution to be the midpoint of the n-interval we know the true solution (if it is not the midpoint) is within an interval of length (b-a)/2^(n+1).

A solution is correct within p decimal places if the error |xc-r|<0.5*10^ - p.

How many times do we need to cut the interval [0,1] in half to get an approximation with 6 correct digits for the problem f(x)=x^3+x-1 using the Bisection Method?

Solving (b-a)/2^(n+1) < 0.5*10^(-6) => n = 19.9. Which means The Bisection method will need 20 steps for 6 correct digits. The approximated solution with 6 correct digits is xc=0.682327.

Using FPI with g(x)=(1+2x^3)/(1+3x^2) and an initial guess x0=1. After 4 steps we get the same solution. A major improvement of number of steps by using FPI with a "nice" g(x)!