China
Africa
Explore chapters and articles related to this topic
Nonlinear Algebra
Published in Brian Vick, Applied Engineering Mathematics, 2020
The bisection method is one type of incremental search methods where the interval containing the root is refined by dividing into halves and retaining the subinterval containing the root. This process is repeated until some desired accuracy criterion is met. In order to start the search, an interval that brackets or surrounds the root must be located. In general, if f(x) is real and continuous in the interval from xl to xu, and f(xl) and f(xu) have opposite signs (i.e., f(xl)f(xu)<0), then there exists at least one real root between xl and xu. The method is depicted graphically in Figure 6.5.
Roots of Equations
Published in Bilal M. Ayyub, Richard H. Mccuen, Numerical Analysis for Engineers, 2015
Bilal M. Ayyub, Richard H. Mccuen
The bisection method is an extension of the direct-search method for cases when it is known that only one root occurs within a given interval of x. For the same level of precision, the bisection method will, in general, require fewer calculations than the direct-search method. Using Figure 4.6 as a reference, the steps in the bisection method can be outlined as follows: For the interval of x from the starting point xs to the end point xe, locate the midpoint xm at the center of the interval. These points correspond to the starting and ending points of the half-intervals.At the starting point xs, midpoint xm, and the ending point xe of the interval, evaluate the function resulting into f(xs), f(xm), and f(xe), respectively.Compute the products of the functions evaluated at the ends of the two half-intervals, that is, f(xs) f(xm) and f(xm) f(xe). The root lies in the interval for which the product is negative, and the midpoint xm is used as the estimate of the root for this iteration.Check for convergence as follows: If the convergence criterion (that is, tolerance) is satisfied, then use xm as the final estimate of the root.If the tolerance has not been met, specify the ends of the half-interval in which the root is located as the starting and ending points for a new interval and return to step 1.
Electromagnetic Fields in One Dimension
Published in Stanley Humphries, Field Solutions on Computers, 2020
For most applications we want to determine the resonant frequency to high accuracy. Each point in a search involves a solution of finite-element equations. Solutions can be time-consuming in two- and three-dimensional problems. The implication is that we should seek methods to find the zero-crossing that minimize the number of steps. Figure 13.15a illustrates the bisection method. Initially, the frequency values fd and fu define a search range. Bisection of the range gives f1=(fu+fd)/2. If the probe response at f1 is less than 0, we use f1–fu as the new interval; otherwise, the interval is fd–f1. The bisection continues either for a maximum number of steps or until the frequency width of the bisection region drops below a target frequency width. If Δf is the target width and Δfo is the initial range, the maximum number of steps is n=log2(Δfo/Δf). The advantage of the bisection method is that it never fails to converge — the decreasing intervals always bracket the root. For well-behaved functions, alternative methods can achieve a target accuracy in fewer steps. Figure 13.15b shows the false position method for root finding. Starting again from points fu and fd that bracket the root, we interpolate the frequency as shown and calculate the corresponding value of Ex to find f1. We choose the range fd–f1 or f1–fu that encloses the root and repeat the interpolation. The bisection method was used for the baseline calculation of Figure 13.14 with an initially broad range of 120 to 180 MHz. The search converged in 16 steps to the value 149.89496 MHz. The accuracy of 1 part in 1.2 × 105 was limited by the mesh size. Table 13.1 shows predicted resonant frequencies and numerical results for the first five modes of the one-dimensional resonator. The error is approximately proportional to the ratio Δz/λn where Δz is the element size and λn is the mode wavelength.
An improved optimality criterion combined with density filtering method for structural topology optimization
Published in Engineering Optimization, 2023
Mingtao Cui, Pengjie Li, Jie Wang, Tongtong Gao, Min Pan
When the conventional OC method is used for solving the SIMP model of structural topology optimization, the bisection method is usually used to update the Lagrange multiplier in the inner loop of the OC method. The bisection method is a simple one-dimensional search algorithm, but its computational efficiency is relatively low. In particular, the search range of the Lagrange multiplier is usually huge (from the lower bound 0 to the upper bound ) in the calculation by the bisection method. In reality, however, the value of the Lagrange multiplier is far less than the upper bound at the end of each density update when the OC method is used for solving the SIMP model of structural topology optimization. This implies that a great deal of redundant calculation may be caused when solving the density by the bisection method. For this reason, a new one-dimensional search algorithm, the advance and retreat golden searching scheme, is proposed to update the Lagrange multiplier with higher convergence speed in the inner loop of the OC method.
Price discounts and personalized product assortments under multinomial logit choice model: A robust approach
Published in IISE Transactions, 2021
Qingwei Jin, Jen-Yen Lin, Sean X. Zhou
To find the optimal discounts we divide the original optimization problem into two subproblems: (i) find with and (ii) find the optimal discount and so the optimal revenue zp. By Theorem 3, the first subproblem can be solved by finding the smallest such that The second subproblem, i.e., finding and zp, is equivalent to solving z such that This can be done by the line search method using the bisection method as proposed in Algorithm 1. The bisection method is known to have a linear convergence rate and the total number of iterations to find z such that with any given is Note that based on Theorem 3, dividing Problem (4) into two subproblems is not essential for Algorithm 1, and one may derive a similar bisection method which does not require solving the first subproblem. However, it is crucial in the analysis of linear/superlinear convergence for Algorithm 2 in Theorem 4
Online profile monitoring for surgical outcomes using a weighted score test
Published in Journal of Quality Technology, 2018
Liu Liu, Xin Lai, Jian Zhang, Fugee Tsung
On theL: Control limit L is determined by the IC ARL. The simulation method based on bisection can be used to find the control limit. The bisection method in mathematics is a root-finding method that repeatedly bisects an interval, then selects a subinterval in which a root must lie for further processing. Specifically, we can apply it to numerically solve the equation f(L) = ARL(L) − ARL0 = 0 for the real variable L, where ARL(L) is the ARL when the control limit is L and ARL0 is the IC ARL we desired. f(L) is a continuous function defined on an interval [a, b] where f(a) and f(b) have opposite signs. In this case a and b are said to bracket a root since, by the intermediate value theorem, the continuous function f must have at least one root (control limit) in the interval (a, b).