1636:. At each iteration, the domain is partitioned into two parts, and the algorithm decides - based on a small number of function evaluations - which of these two parts must contain a root. In one dimension, the criterion for decision is that the function has opposite signs. The main challenge in extending the method to multiple dimensions is to find a criterion that can be computed easily, and guarantees the existence of a root.
535:, except that, instead of retaining the last two points, it makes sure to keep one point on either side of the root. The false position method can be faster than the bisection method and will never diverge like the secant method; however, it may fail to converge in some naive implementations due to roundoff errors that may lead to a wrong sign for
578:) and then projection onto the minmax interval. The combination of these steps produces a simultaneously minmax optimal method with guarantees similar to interpolation based methods for smooth functions, and, in practice will outperform both the bisection method and interpolation based methods under both smooth and non-smooth functions.
664:. Newton's method may not converge if started too far away from a root. However, when it does converge, it is faster than the bisection method, and is usually quadratic. Newton's method is also important because it readily generalizes to higher-dimensional problems. Newton-like methods with higher orders of convergence are the
571:). It does so by keeping track of both the bracketing interval as well as the minmax interval in which any point therein converges as fast as the bisection method. The construction of the queried point c follows three steps: interpolation (similar to the regula falsi), truncation (adjusting the regula falsi similar to
223:, which asserts that if a continuous function has values of opposite signs at the end points of an interval, then the function has at least one root in the interval. Therefore, they require to start with an interval such that the function takes opposite signs at the end points of the interval. However, in the case of
566:
is the only known method to bracket the root with the same worst case guarantees of the bisection method while guaranteeing a superlinear convergence to the root of smooth functions as the secant method. It is also the only known method guaranteed to outperform the bisection method on the average for
175:
of the root as starting values, then each iteration of the algorithm produces a successively more accurate approximation to the root. Since the iteration must be stopped at some point, these methods produce an approximation to the root, not an exact solution. Many methods compute subsequent values by
1590:
is a hybrid method that uses the value of function at the midpoint of the interval to perform an exponential interpolation to the root. This gives a fast convergence with a guaranteed convergence of at most twice the number of iterations as the bisection method.
1579:. At every iteration, Brent's method decides which method out of these three is likely to do best, and proceeds by doing a step according to that method. This gives a robust and fast method, which therefore enjoys considerable popularity.
636:
root-finding method generally uses a specific type of iteration, consisting of defining an auxiliary function, which is applied to the last computed approximations of a root for getting a new approximation. The iteration stops when a
191:, since algebraic properties of polynomials are fundamental for the most efficient algorithms. The efficiency of an algorithm may depend dramatically on the characteristics of the given functions. For example, many algorithms use the
1665:. This criterion is used by a method called Characteristic Bisection. It does not require to compute the topological degree - it only requires to compute the signs of function values. The number of required evaluations is at least
155:
defined by continuous functions. However, most root-finding algorithms do not guarantee that they will find all the roots; in particular, if such an algorithm does not find any root, that does not mean that no root exists.
594:
of low degree, which takes the same values at these approximate roots. Then the root of the polynomial is computed and used as a new approximate value of the root of the function, and the process is iterated.
400:
526:
1536:
2420:
1475:
1747:
1710:
1077:
1559:
method. Again, convergence is asymptotically faster than the secant method, but inverse quadratic interpolation often behaves poorly when the iterates are not close to the root.
1400:
1341:
1273:
219:
Bracketing methods determine successively smaller intervals (brackets) that contain a root. When the interval is small enough, then a root has been found. They generally use the
991:
620:
is also an interpolation method, which differs from the secant method by using, for interpolating by a line, two points that are not necessarily the last two computed points.
1204:
1643:
gives a criterion for the existence of a root in a rectangle, but it is hard to verify, since it requires to evaluate the function on the entire boundary of the rectangle.
2189:
1020:
and perform the iteration until it converges towards a root of the function. If the iteration converges, it will converge to a root. The iteration will only converge if
199:. In general, numerical algorithms are not guaranteed to find all the roots of a function, so failing to find a root does not prove that there is no root. However, for
1150:
1115:
936:
872:
837:
782:
704:
If we use a polynomial fit to remove the quadratic part of the finite difference used in the Secant method, so that it better approximates the derivative, we obtain
1018:
1658:. This criterion is the basis for several root-finding methods, such as by Stenger and Kearfott. However, computing the topological degree can be time-consuming.
901:
747:
802:
598:
Two values allow interpolating a function by a polynomial of degree one (that is approximating the graph of the function by a line). This is the basis of the
2413:
180:
of the auxiliary function, which is chosen for having the roots of the original equation as fixed points, and for converging rapidly to these fixed points.
1716:
is the length of the longest edge of the characteristic polyhedron. Note that prove a lower bound on the number of evaluations, and not an upper bound.
688:. This method does not require the computation (nor the existence) of a derivative, but the price is slower convergence (the order is approximately 1.6 (
708:, which has quadratic convergence, and whose behavior (both good and bad) is essentially the same as Newton's method but does not require a derivative.
203:, there are specific algorithms that use algebraic properties for certifying that no root is missed, and locating the roots in separate intervals (or
2406:
1611:
is a long-standing problem that has been the object of much research throughout history. A testament to this is that up until the 19th century,
645:
the desired precision) of the auxiliary function is reached, that is when the new computed value is sufficiently close to the preceding ones.
2182:
1914:
1833:
346:
have opposite signs, and one has divided by two the size of the interval. Although the bisection method is robust, it gains one and only one
2387:
2313:
1601:
2667:
2175:
1640:
2377:
1729:
1576:
1556:
1792:
1647:
1719:
A fourth method uses an intermediate-value theorem on simplices. Again, no upper bound on the number of queries is given.
357:
437:
2598:
2568:
2553:
2341:
422:
method, is similar to the bisection method, but instead of using bisection search's middle of the interval it uses the
100:
for complex roots (an interval or disk output being equivalent to an approximate output together with an error bound).
2346:
228:
1895:"Generalizations of the Intermediate Value Theorem for Approximating Fixed Points and Zeros of Continuous Functions"
2623:
2497:
2487:
2467:
1776:
1482:
220:
2502:
1901:. Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp. 223–238.
177:
89:
2331:
2275:
1407:
590:. This consists in using the last computed approximate values of the root for approximating the function by a
2641:
2603:
2356:
2290:
2234:
2206:
2198:
1734:
1668:
665:
2447:
2280:
1753:
705:
152:
93:
85:
1348:
1280:
1212:
2507:
2477:
2372:
717:
638:
415:
350:
of accuracy with each iteration. Therefore, the number of function evaluations required for finding an
239:) for getting information on the number of roots in an interval. They lead to efficient algorithms for
2107:
941:
2618:
2593:
2538:
2351:
2326:
2161:
J.M. McNamee and Victor Pan: "Numerical
Methods for Roots of Polynomials - Part II", Elsevier (2013).
1023:
1155:
2628:
2613:
2558:
2336:
2265:
2257:
1798:
1758:
1740:
1616:
693:
262:
240:
207:
for complex roots) that are small enough to ensure the convergence of numerical methods (typically
196:
168:
47:
2646:
2548:
2543:
2457:
2137:
2108:"Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros"
2088:
2038:
1991:
1920:
1894:
1782:
603:
431:
of the line that connects the plotted function values at the endpoints of the interval, that is
302:
be the middle of the interval (the midpoint or the point that bisects the interval). Then either
204:
184:
97:
51:
43:
31:
2382:
2303:
2247:
2242:
1587:
669:
653:
611:
236:
232:
208:
1854:"On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree"
2608:
2452:
2298:
2129:
2080:
2030:
1983:
1910:
1875:
1829:
1572:
1547:
The appearance of complex values in interpolation methods can be avoided by interpolating the
681:
547:
2588:
2573:
2214:
2119:
2072:
2022:
1975:
1902:
1865:
1773: – Software for approximating the roots of a polynomial with arbitrarily high precision
1764:
1629:
1548:
1120:
1085:
906:
842:
807:
752:
633:
252:
188:
103:
996:
17:
2563:
1608:
877:
723:
2429:
787:
64:
2661:
2578:
2533:
2321:
2270:
2158:
J.M. McNamee: "Numerical
Methods for Roots of Polynomials - Part I", Elsevier (2007).
2141:
2092:
2061:"A rapid Generalized Method of Bisection for solving Systems of Non-linear Equations"
2042:
1995:
1924:
685:
599:
587:
532:
84:. As, generally, the zeros of a function cannot be computed exactly nor expressed in
2528:
2492:
2462:
2219:
1821:
1779: – Number of times an object must be counted for making true a general formula
689:
572:
1750: – Type of functions designed for being unsolvable by root-finding algorithms
2398:
1906:
1654:
on a rectangle is non-zero, then the rectangle must contain at least one root of
2482:
2124:
423:
243:
of polynomials, which ensure finding all real roots with a guaranteed accuracy.
60:
88:, root-finding algorithms provide approximations to zeros, expressed either as
2472:
2224:
2011:"An efficient degree-computation method for a generalized method of bisection"
661:
591:
568:
563:
224:
200:
192:
176:
evaluating an auxiliary function on the preceding values. The limit is thus a
2133:
2084:
2034:
1987:
1879:
2433:
1938:
629:
160:
39:
1870:
1853:
1820:
Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007).
1646:
Another criterion is given by a theorem of
Kronecker. It says that, if the
2167:
607:
402:. Other methods, under appropriate conditions, can gain accuracy faster.
164:
2583:
2076:
2026:
1979:
1770:
1612:
2060:
2010:
1963:
1743: – Quasi-Newton root-finding method for the multivariable case
1632:
has been generalized to higher dimensions; these methods are called
187:. However, for polynomials, root-finding study belongs generally to
692:)). A generalization of the secant method in higher dimensions is
642:
2512:
1939:"Iterative solution of nonlinear equations in several variables"
1575:
is a combination of the bisection method, the secant method and
993:
so that we can perform the iteration. Next, we pick a value for
2402:
2171:
1852:
Mourrain, B.; Vrahatis, M. N.; Yakoubsohn, J. C. (2002-06-01).
567:
any continuous distribution on the location of the root (see
347:
183:
The behavior of general root-finding algorithms is studied in
648:
167:
of numbers that hopefully converges towards the root as its
1767: – Graphical method for the real roots of a polynomial
1822:"Chapter 9. Root Finding and Nonlinear Sets of Equations"
938:
function). Next, we relabel each side of the equation as
1206:, we will rewrite it as one of the following equations.
1897:. In Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.).
1828:(3rd ed.). New York: Cambridge University Press.
1748:
Cryptographically secure pseudorandom number generator
649:
Newton's method (and similar derivative-based methods)
1671:
1485:
1410:
1351:
1283:
1215:
1158:
1123:
1088:
1026:
999:
944:
909:
880:
845:
810:
790:
755:
726:
440:
360:
1964:"Computing the topological degree of a mapping inRn"
606:, which approximates the graph of the function by a
395:{\displaystyle \log _{2}{\frac {b-a}{\varepsilon }}}
2521:
2440:
2365:
2312:
2289:
2256:
2233:
2205:
680:Replacing the derivative in Newton's method with a
521:{\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.}
1826:Numerical Recipes: The Art of Scientific Computing
1795: – Roots of multiple multivariate polynomials
1704:
1530:
1469:
1394:
1335:
1267:
1198:
1144:
1109:
1071:
1012:
985:
930:
895:
866:
831:
796:
776:
741:
520:
394:
195:of the input function, while others work on every
2059:Vrahatis, M. N.; Iordanidis, K. I. (1986-03-01).
720:to find the root of a function. Given a function
151:. Thus root-finding algorithms allow solving any
124:is the same as finding the roots of the function
1801: – About the convergence of Newton's method
628:Although all root-finding algorithms proceed by
1761: – Algorithm for finding polynomial roots
265:, for which one knows an interval such that
2414:
2183:
1899:Numerical Computations: Theory and Algorithms
1531:{\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}
8:
749:which we have set to zero to find the root (
251:The simplest root-finding algorithm is the
2421:
2407:
2399:
2190:
2176:
2168:
1470:{\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}
554:is large in the neighborhood of the root.
2123:
1869:
1691:
1676:
1670:
1520:
1508:
1490:
1484:
1455:
1439:
1434:
1415:
1409:
1386:
1381:
1356:
1350:
1318:
1306:
1288:
1282:
1250:
1241:
1220:
1214:
1178:
1157:
1122:
1087:
1058:
1027:
1025:
1004:
998:
974:
949:
943:
908:
879:
844:
809:
789:
754:
725:
668:. The first one after Newton's method is
447:
439:
374:
365:
359:
159:Most numerical root-finding methods use
1812:
784:), we rewrite the equation in terms of
1705:{\displaystyle \log _{2}(D/\epsilon )}
287:have opposite signs (a bracket). Let
7:
2054:
2052:
1847:
1845:
586:Many root-finding processes work by
67:to the complex numbers, is a number
2106:Vrahatis, Michael N. (2020-04-15).
1395:{\displaystyle x_{n+1}=1-x_{n}^{2}}
1336:{\displaystyle x_{n+1}=1/(x_{n}+1)}
1268:{\displaystyle x_{n+1}=(1/x_{n})-1}
546:; typically, this may occur if the
1624:Finding roots in higher dimensions
1602:Polynomial root-finding algorithms
25:
672:with cubic order of convergence.
531:False position is similar to the
211:) to the unique root so located.
27:Algorithms for zeros of functions
2388:Sidi's generalized secant method
1661:A third criterion is based on a
1600:This section is an excerpt from
986:{\displaystyle x_{n+1}=g(x_{n})}
2378:Inverse quadratic interpolation
1730:List of root finding algorithms
1577:inverse quadratic interpolation
1557:inverse quadratic interpolation
1072:{\displaystyle |g'(root)|<1}
573:Regula falsi § Improvements in
2009:Kearfott, Baker (1979-06-01).
1793:System of polynomial equations
1699:
1685:
1617:theory of polynomial equations
1330:
1311:
1256:
1235:
1199:{\displaystyle f(x)=x^{2}+x-1}
1168:
1162:
1139:
1133:
1098:
1092:
1059:
1055:
1040:
1028:
980:
967:
919:
913:
890:
884:
861:
855:
820:
814:
765:
759:
736:
730:
509:
503:
494:
488:
480:
474:
462:
456:
92:numbers or as small isolating
1:
2112:Topology and Its Applications
1962:Stenger, Frank (1975-03-01).
1893:Vrahatis, Michael N. (2020).
1634:generalized bisection methods
1907:10.1007/978-3-030-40616-5_17
1082:As an example of converting
874:(note, there are often many
712:Fixed point iteration method
63:to real numbers or from the
2125:10.1016/j.topol.2019.107036
171:. They require one or more
18:Root-finding of polynomials
2684:
2207:Bracketing (no derivative)
1777:Multiplicity (mathematics)
1599:
221:intermediate value theorem
46:, also called "roots", of
2637:
1663:characteristic polyhedron
227:there are other methods (
1641:Poincaré–Miranda theorem
1152:, if given the function
602:. Three values define a
229:Descartes' rule of signs
2668:Root-finding algorithms
2642:List of data structures
2357:Splitting circle method
2342:Jenkins–Traub algorithm
2199:Root-finding algorithms
1735:Fixed-point computation
1563:Combinations of methods
2347:Lehmer–Schur algorithm
1871:10.1006/jcom.2001.0636
1754:GNU Scientific Library
1706:
1567:
1532:
1471:
1396:
1337:
1269:
1200:
1146:
1145:{\displaystyle x=g(x)}
1111:
1110:{\displaystyle f(x)=0}
1073:
1014:
987:
932:
931:{\displaystyle f(x)=0}
897:
868:
867:{\displaystyle x=g(x)}
833:
832:{\displaystyle f(x)=0}
798:
778:
777:{\displaystyle f(x)=0}
743:
699:
522:
396:
36:root-finding algorithm
2373:Fixed-point iteration
2065:Numerische Mathematik
2015:Numerische Mathematik
1968:Numerische Mathematik
1858:Journal of Complexity
1707:
1595:Roots of polynomials
1582:
1543:Inverse interpolation
1533:
1472:
1397:
1338:
1270:
1201:
1147:
1112:
1074:
1015:
1013:{\displaystyle x_{1}}
988:
933:
898:
869:
834:
799:
779:
744:
718:fixed-point iteration
666:Householder's methods
660:to have a continuous
656:assumes the function
523:
416:false position method
397:
354:-approximate root is
2539:Breadth-first search
2332:Durand–Kerner method
2276:Newton–Krylov method
1669:
1483:
1408:
1349:
1281:
1213:
1156:
1121:
1086:
1024:
997:
942:
907:
896:{\displaystyle g(x)}
878:
843:
808:
788:
753:
742:{\displaystyle f(x)}
724:
438:
358:
48:continuous functions
2629:Topological sorting
2559:Dynamic programming
2281:Steffensen's method
1799:Kantorovich theorem
1555:, resulting in the
1444:
1391:
903:functions for each
706:Steffensen's method
700:Steffensen's method
569:ITP Method#Analysis
263:continuous function
241:real-root isolation
197:continuous function
104:Solving an equation
2647:List of algorithms
2554:Divide and conquer
2549:Depth-first search
2544:Brute-force search
2458:Binary search tree
2314:Polynomial methods
2077:10.1007/BF01389620
2027:10.1007/BF01404868
1980:10.1007/BF01419526
1702:
1648:topological degree
1615:meant essentially
1528:
1467:
1430:
1392:
1377:
1333:
1265:
1196:
1142:
1107:
1069:
1010:
983:
928:
893:
864:
829:
794:
774:
739:
604:quadratic function
518:
418:, also called the
392:
215:Bracketing methods
185:numerical analysis
52:zero of a function
32:numerical analysis
2655:
2654:
2453:Associative array
2396:
2395:
2352:Laguerre's method
2327:Bairstow's method
1916:978-3-030-40616-5
1835:978-0-521-88068-8
1788:th root algorithm
1526:
797:{\displaystyle x}
682:finite difference
624:Iterative methods
548:rate of variation
513:
390:
16:(Redirected from
2675:
2624:String-searching
2423:
2416:
2409:
2400:
2337:Graeffe's method
2266:Broyden's method
2215:Bisection method
2192:
2185:
2178:
2169:
2146:
2145:
2127:
2103:
2097:
2096:
2056:
2047:
2046:
2006:
2000:
1999:
1959:
1953:
1952:
1950:
1949:
1935:
1929:
1928:
1890:
1884:
1883:
1873:
1849:
1840:
1839:
1817:
1787:
1759:Graeffe's method
1741:Broyden's method
1711:
1709:
1708:
1703:
1695:
1681:
1680:
1630:bisection method
1609:polynomial roots
1537:
1535:
1534:
1529:
1527:
1525:
1524:
1509:
1501:
1500:
1476:
1474:
1473:
1468:
1460:
1459:
1443:
1438:
1426:
1425:
1401:
1399:
1398:
1393:
1390:
1385:
1367:
1366:
1342:
1340:
1339:
1334:
1323:
1322:
1310:
1299:
1298:
1274:
1272:
1271:
1266:
1255:
1254:
1245:
1231:
1230:
1205:
1203:
1202:
1197:
1183:
1182:
1151:
1149:
1148:
1143:
1116:
1114:
1113:
1108:
1078:
1076:
1075:
1070:
1062:
1039:
1031:
1019:
1017:
1016:
1011:
1009:
1008:
992:
990:
989:
984:
979:
978:
960:
959:
937:
935:
934:
929:
902:
900:
899:
894:
873:
871:
870:
865:
838:
836:
835:
830:
803:
801:
800:
795:
783:
781:
780:
775:
748:
746:
745:
740:
694:Broyden's method
553:
545:
527:
525:
524:
519:
514:
512:
483:
448:
428:
406:False position (
401:
399:
398:
393:
391:
386:
375:
370:
369:
345:
334:
323:
312:
301:
286:
275:
260:
253:bisection method
247:Bisection method
189:computer algebra
150:
123:
83:
72:
58:
21:
2683:
2682:
2678:
2677:
2676:
2674:
2673:
2672:
2658:
2657:
2656:
2651:
2633:
2564:Graph traversal
2517:
2441:Data structures
2436:
2430:Data structures
2427:
2397:
2392:
2383:Muller's method
2361:
2308:
2304:Ridders' method
2285:
2252:
2248:Halley's method
2243:Newton's method
2229:
2201:
2196:
2165:
2155:
2153:Further reading
2150:
2149:
2105:
2104:
2100:
2058:
2057:
2050:
2008:
2007:
2003:
1961:
1960:
1956:
1947:
1945:
1937:
1936:
1932:
1917:
1892:
1891:
1887:
1851:
1850:
1843:
1836:
1819:
1818:
1814:
1809:
1804:
1783:
1725:
1672:
1667:
1666:
1626:
1621:
1620:
1605:
1597:
1588:Ridders' method
1585:
1583:Ridders' method
1570:
1565:
1545:
1516:
1486:
1481:
1480:
1451:
1411:
1406:
1405:
1352:
1347:
1346:
1314:
1284:
1279:
1278:
1246:
1216:
1211:
1210:
1174:
1154:
1153:
1119:
1118:
1084:
1083:
1032:
1022:
1021:
1000:
995:
994:
970:
945:
940:
939:
905:
904:
876:
875:
841:
840:
806:
805:
786:
785:
751:
750:
722:
721:
716:We can use the
714:
702:
678:
670:Halley's method
654:Newton's method
651:
626:
612:Muller's method
584:
560:
551:
536:
484:
449:
436:
435:
424:
412:
376:
361:
356:
355:
336:
325:
314:
303:
288:
277:
266:
256:
249:
237:Sturm's theorem
233:Budan's theorem
217:
209:Newton's method
173:initial guesses
125:
106:
74:
68:
65:complex numbers
54:
28:
23:
22:
15:
12:
11:
5:
2681:
2679:
2671:
2670:
2660:
2659:
2653:
2652:
2650:
2649:
2644:
2638:
2635:
2634:
2632:
2631:
2626:
2621:
2616:
2611:
2606:
2601:
2596:
2591:
2586:
2581:
2576:
2571:
2566:
2561:
2556:
2551:
2546:
2541:
2536:
2531:
2525:
2523:
2519:
2518:
2516:
2515:
2510:
2505:
2500:
2495:
2490:
2485:
2480:
2475:
2470:
2465:
2460:
2455:
2450:
2444:
2442:
2438:
2437:
2428:
2426:
2425:
2418:
2411:
2403:
2394:
2393:
2391:
2390:
2385:
2380:
2375:
2369:
2367:
2363:
2362:
2360:
2359:
2354:
2349:
2344:
2339:
2334:
2329:
2324:
2318:
2316:
2310:
2309:
2307:
2306:
2301:
2299:Brent's method
2295:
2293:
2291:Hybrid methods
2287:
2286:
2284:
2283:
2278:
2273:
2268:
2262:
2260:
2254:
2253:
2251:
2250:
2245:
2239:
2237:
2231:
2230:
2228:
2227:
2222:
2217:
2211:
2209:
2203:
2202:
2197:
2195:
2194:
2187:
2180:
2172:
2163:
2162:
2159:
2154:
2151:
2148:
2147:
2098:
2071:(2): 123–138.
2048:
2021:(2): 109–127.
2001:
1954:
1930:
1915:
1885:
1864:(2): 612–640.
1841:
1834:
1811:
1810:
1808:
1805:
1803:
1802:
1796:
1790:
1780:
1774:
1768:
1762:
1756:
1751:
1738:
1737:
1732:
1726:
1724:
1721:
1701:
1698:
1694:
1690:
1687:
1684:
1679:
1675:
1650:of a function
1625:
1622:
1606:
1598:
1596:
1593:
1584:
1581:
1573:Brent's method
1569:
1568:Brent's method
1566:
1564:
1561:
1544:
1541:
1540:
1539:
1523:
1519:
1515:
1512:
1507:
1504:
1499:
1496:
1493:
1489:
1478:
1466:
1463:
1458:
1454:
1450:
1447:
1442:
1437:
1433:
1429:
1424:
1421:
1418:
1414:
1403:
1389:
1384:
1380:
1376:
1373:
1370:
1365:
1362:
1359:
1355:
1344:
1332:
1329:
1326:
1321:
1317:
1313:
1309:
1305:
1302:
1297:
1294:
1291:
1287:
1276:
1264:
1261:
1258:
1253:
1249:
1244:
1240:
1237:
1234:
1229:
1226:
1223:
1219:
1195:
1192:
1189:
1186:
1181:
1177:
1173:
1170:
1167:
1164:
1161:
1141:
1138:
1135:
1132:
1129:
1126:
1106:
1103:
1100:
1097:
1094:
1091:
1068:
1065:
1061:
1057:
1054:
1051:
1048:
1045:
1042:
1038:
1035:
1030:
1007:
1003:
982:
977:
973:
969:
966:
963:
958:
955:
952:
948:
927:
924:
921:
918:
915:
912:
892:
889:
886:
883:
863:
860:
857:
854:
851:
848:
828:
825:
822:
819:
816:
813:
793:
773:
770:
767:
764:
761:
758:
738:
735:
732:
729:
713:
710:
701:
698:
677:
674:
650:
647:
625:
622:
583:
580:
559:
556:
529:
528:
517:
511:
508:
505:
502:
499:
496:
493:
490:
487:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
446:
443:
411:
404:
389:
385:
382:
379:
373:
368:
364:
248:
245:
216:
213:
163:, producing a
90:floating-point
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2680:
2669:
2666:
2665:
2663:
2648:
2645:
2643:
2640:
2639:
2636:
2630:
2627:
2625:
2622:
2620:
2617:
2615:
2612:
2610:
2607:
2605:
2602:
2600:
2597:
2595:
2592:
2590:
2587:
2585:
2582:
2580:
2579:Hash function
2577:
2575:
2572:
2570:
2567:
2565:
2562:
2560:
2557:
2555:
2552:
2550:
2547:
2545:
2542:
2540:
2537:
2535:
2534:Binary search
2532:
2530:
2527:
2526:
2524:
2520:
2514:
2511:
2509:
2506:
2504:
2501:
2499:
2496:
2494:
2491:
2489:
2486:
2484:
2481:
2479:
2476:
2474:
2471:
2469:
2466:
2464:
2461:
2459:
2456:
2454:
2451:
2449:
2446:
2445:
2443:
2439:
2435:
2431:
2424:
2419:
2417:
2412:
2410:
2405:
2404:
2401:
2389:
2386:
2384:
2381:
2379:
2376:
2374:
2371:
2370:
2368:
2366:Other methods
2364:
2358:
2355:
2353:
2350:
2348:
2345:
2343:
2340:
2338:
2335:
2333:
2330:
2328:
2325:
2323:
2322:Aberth method
2320:
2319:
2317:
2315:
2311:
2305:
2302:
2300:
2297:
2296:
2294:
2292:
2288:
2282:
2279:
2277:
2274:
2272:
2271:Secant method
2269:
2267:
2264:
2263:
2261:
2259:
2255:
2249:
2246:
2244:
2241:
2240:
2238:
2236:
2232:
2226:
2223:
2221:
2218:
2216:
2213:
2212:
2210:
2208:
2204:
2200:
2193:
2188:
2186:
2181:
2179:
2174:
2173:
2170:
2166:
2160:
2157:
2156:
2152:
2143:
2139:
2135:
2131:
2126:
2121:
2117:
2113:
2109:
2102:
2099:
2094:
2090:
2086:
2082:
2078:
2074:
2070:
2066:
2062:
2055:
2053:
2049:
2044:
2040:
2036:
2032:
2028:
2024:
2020:
2016:
2012:
2005:
2002:
1997:
1993:
1989:
1985:
1981:
1977:
1973:
1969:
1965:
1958:
1955:
1944:
1940:
1934:
1931:
1926:
1922:
1918:
1912:
1908:
1904:
1900:
1896:
1889:
1886:
1881:
1877:
1872:
1867:
1863:
1859:
1855:
1848:
1846:
1842:
1837:
1831:
1827:
1823:
1816:
1813:
1806:
1800:
1797:
1794:
1791:
1789:
1786:
1781:
1778:
1775:
1772:
1769:
1766:
1765:Lill's method
1763:
1760:
1757:
1755:
1752:
1749:
1746:
1745:
1744:
1742:
1736:
1733:
1731:
1728:
1727:
1722:
1720:
1717:
1715:
1696:
1692:
1688:
1682:
1677:
1673:
1664:
1659:
1657:
1653:
1649:
1644:
1642:
1637:
1635:
1631:
1623:
1618:
1614:
1610:
1603:
1594:
1592:
1589:
1580:
1578:
1574:
1562:
1560:
1558:
1554:
1550:
1542:
1521:
1517:
1513:
1510:
1505:
1502:
1497:
1494:
1491:
1487:
1479:
1464:
1461:
1456:
1452:
1448:
1445:
1440:
1435:
1431:
1427:
1422:
1419:
1416:
1412:
1404:
1387:
1382:
1378:
1374:
1371:
1368:
1363:
1360:
1357:
1353:
1345:
1327:
1324:
1319:
1315:
1307:
1303:
1300:
1295:
1292:
1289:
1285:
1277:
1262:
1259:
1251:
1247:
1242:
1238:
1232:
1227:
1224:
1221:
1217:
1209:
1208:
1207:
1193:
1190:
1187:
1184:
1179:
1175:
1171:
1165:
1159:
1136:
1130:
1127:
1124:
1104:
1101:
1095:
1089:
1080:
1066:
1063:
1052:
1049:
1046:
1043:
1036:
1033:
1005:
1001:
975:
971:
964:
961:
956:
953:
950:
946:
925:
922:
916:
910:
887:
881:
858:
852:
849:
846:
826:
823:
817:
811:
791:
771:
768:
762:
756:
733:
727:
719:
711:
709:
707:
697:
695:
691:
687:
686:secant method
684:, we get the
683:
676:Secant method
675:
673:
671:
667:
663:
659:
655:
646:
644:
640:
635:
631:
623:
621:
619:
615:
613:
609:
605:
601:
600:secant method
596:
593:
589:
588:interpolation
582:Interpolation
581:
579:
577:
576:
570:
565:
557:
555:
549:
543:
539:
534:
533:secant method
515:
506:
500:
497:
491:
485:
477:
471:
468:
465:
459:
453:
450:
444:
441:
434:
433:
432:
430:
427:
421:
417:
409:
405:
403:
387:
383:
380:
377:
371:
366:
362:
353:
349:
343:
339:
332:
328:
321:
317:
310:
306:
299:
295:
291:
284:
280:
273:
269:
264:
259:
254:
246:
244:
242:
238:
234:
230:
226:
222:
214:
212:
210:
206:
202:
198:
194:
190:
186:
181:
179:
174:
170:
166:
162:
157:
154:
148:
144:
140:
136:
132:
128:
121:
117:
113:
109:
105:
101:
99:
95:
91:
87:
81:
77:
71:
66:
62:
57:
53:
49:
45:
41:
37:
33:
19:
2604:Root-finding
2529:Backtracking
2493:Segment tree
2463:Fenwick tree
2258:Quasi-Newton
2220:Regula falsi
2164:
2115:
2111:
2101:
2068:
2064:
2018:
2014:
2004:
1974:(1): 23–38.
1971:
1967:
1957:
1946:. Retrieved
1942:
1933:
1898:
1888:
1861:
1857:
1825:
1815:
1784:
1739:
1718:
1713:
1662:
1660:
1655:
1651:
1645:
1638:
1633:
1627:
1586:
1571:
1552:
1546:
1081:
715:
703:
690:golden ratio
679:
657:
652:
627:
618:Regula falsi
617:
616:
597:
585:
575:regula falsi
574:
561:
541:
537:
530:
425:
420:regula falsi
419:
413:
408:regula falsi
407:
351:
341:
337:
330:
326:
319:
315:
308:
304:
297:
293:
289:
282:
278:
271:
267:
257:
250:
218:
182:
172:
158:
146:
142:
138:
134:
130:
126:
119:
115:
111:
107:
102:
79:
75:
69:
61:real numbers
55:
42:for finding
35:
29:
2483:Linked list
2235:Householder
1943:Guide books
639:fixed point
225:polynomials
201:polynomials
178:fixed point
86:closed form
59:, from the
2619:Sweep line
2594:Randomized
2522:Algorithms
2473:Hash table
2434:algorithms
2225:ITP method
2118:: 107036.
1948:2023-04-16
1807:References
662:derivative
610:. This is
592:polynomial
564:ITP method
558:ITP method
429:-intercept
193:derivative
73:such that
2614:Streaming
2599:Recursion
2142:213249321
2134:0166-8641
2093:121771945
2085:0945-3245
2043:122058552
2035:0029-599X
1996:122196773
1988:0945-3245
1925:211160947
1880:0885-064X
1697:ϵ
1683:
1514:−
1506:±
1462:−
1375:−
1260:−
1191:−
634:iterative
630:iteration
498:−
466:−
388:ε
381:−
372:
161:iteration
94:intervals
40:algorithm
2662:Category
1723:See also
1712:, where
1607:Finding
1037:′
839:becomes
804:so that
608:parabola
165:sequence
153:equation
2609:Sorting
2584:Minimax
1771:MPSolve
1613:algebra
1549:inverse
2589:Online
2574:Greedy
2503:String
2140:
2132:
2091:
2083:
2041:
2033:
1994:
1986:
1923:
1913:
1878:
1832:
255:. Let
96:, or
38:is an
2498:Stack
2488:Queue
2468:Graph
2448:Array
2138:S2CID
2089:S2CID
2039:S2CID
1992:S2CID
1921:S2CID
643:up to
632:, an
324:, or
261:be a
205:disks
169:limit
98:disks
82:) = 0
44:zeros
2569:Fold
2513:Trie
2508:Tree
2478:Heap
2432:and
2130:ISSN
2081:ISSN
2031:ISSN
1984:ISSN
1911:ISBN
1876:ISSN
1830:ISBN
1639:The
1628:The
1477:, or
1064:<
562:The
414:The
335:and
313:and
276:and
235:and
141:) –
133:) =
114:) =
50:. A
34:, a
2120:doi
2116:275
2073:doi
2023:doi
1976:doi
1903:doi
1866:doi
1674:log
1551:of
1117:to
550:of
363:log
348:bit
300:)/2
292:= (
30:In
2664::
2136:.
2128:.
2114:.
2110:.
2087:.
2079:.
2069:49
2067:.
2063:.
2051:^
2037:.
2029:.
2019:32
2017:.
2013:.
1990:.
1982:.
1972:25
1970:.
1966:.
1941:.
1919:.
1909:.
1874:.
1862:18
1860:.
1856:.
1844:^
1824:.
1079:.
696:.
614:.
231:,
2422:e
2415:t
2408:v
2191:e
2184:t
2177:v
2144:.
2122::
2095:.
2075::
2045:.
2025::
1998:.
1978::
1951:.
1927:.
1905::
1882:.
1868::
1838:.
1785:n
1714:D
1700:)
1693:/
1689:D
1686:(
1678:2
1656:f
1652:f
1619:.
1604:.
1553:f
1538:.
1522:n
1518:x
1511:1
1503:=
1498:1
1495:+
1492:n
1488:x
1465:1
1457:n
1453:x
1449:2
1446:+
1441:2
1436:n
1432:x
1428:=
1423:1
1420:+
1417:n
1413:x
1402:,
1388:2
1383:n
1379:x
1372:1
1369:=
1364:1
1361:+
1358:n
1354:x
1343:,
1331:)
1328:1
1325:+
1320:n
1316:x
1312:(
1308:/
1304:1
1301:=
1296:1
1293:+
1290:n
1286:x
1275:,
1263:1
1257:)
1252:n
1248:x
1243:/
1239:1
1236:(
1233:=
1228:1
1225:+
1222:n
1218:x
1194:1
1188:x
1185:+
1180:2
1176:x
1172:=
1169:)
1166:x
1163:(
1160:f
1140:)
1137:x
1134:(
1131:g
1128:=
1125:x
1105:0
1102:=
1099:)
1096:x
1093:(
1090:f
1067:1
1060:|
1056:)
1053:t
1050:o
1047:o
1044:r
1041:(
1034:g
1029:|
1006:1
1002:x
981:)
976:n
972:x
968:(
965:g
962:=
957:1
954:+
951:n
947:x
926:0
923:=
920:)
917:x
914:(
911:f
891:)
888:x
885:(
882:g
862:)
859:x
856:(
853:g
850:=
847:x
827:0
824:=
821:)
818:x
815:(
812:f
792:x
772:0
769:=
766:)
763:x
760:(
757:f
737:)
734:x
731:(
728:f
658:f
641:(
552:f
544:)
542:c
540:(
538:f
516:.
510:)
507:a
504:(
501:f
495:)
492:b
489:(
486:f
481:)
478:a
475:(
472:f
469:b
463:)
460:b
457:(
454:f
451:a
445:=
442:c
426:x
410:)
384:a
378:b
367:2
352:ε
344:)
342:b
340:(
338:f
333:)
331:c
329:(
327:f
322:)
320:c
318:(
316:f
311:)
309:a
307:(
305:f
298:b
296:+
294:a
290:c
285:)
283:b
281:(
279:f
274:)
272:a
270:(
268:f
258:f
149:)
147:x
145:(
143:g
139:x
137:(
135:f
131:x
129:(
127:h
122:)
120:x
118:(
116:g
112:x
110:(
108:f
80:x
78:(
76:f
70:x
56:f
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.