1489:
645:
36:
3162:
2106:
In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. Convergent fixed-point iterations are
2060:, this one in particular is very useful because not all fixed-points are attractive. When constructing a fixed-point iteration, it is very important to make sure it converges to the fixed point. We can usually use the Banach fixed-point theorem to show that the fixed point is attractive.
2539:
1324:
1447:
1102:
769:
2258:
2613:
1691:
2875:
2792:
1738:, not degrees or other units) has exactly one fixed point, and that fixed point is attracting. In this case, "close enough" is not a stringent criterion at allâto demonstrate this, start with
608:
458:
306:
2334:
2051:
1212:
368:
3238:
is a member of the given IFS randomly selected for each iteration. Hence the chaos game is a randomized fixed-point iteration. The chaos game allows plotting the general shape of a
906:
2656:
2428:
2944:
3053:
2683:
2419:
536:
489:
3405:
Brkic, Dejan (2017) Solution of the
Implicit Colebrook Equation for Flow Friction Using Excel, Spreadsheets in Education (eJSiE): Vol. 10: Iss. 2, Article 2. Available at:
2389:
1360:
948:
813:
2996:
2916:
846:
1829:
1161:
1979:
1128:
978:
1929:
1351:
1188:
196:
2153:
1774:
1477:
3073:
3016:
2707:
1949:
1898:
630:
556:
509:
220:
165:
1854:
3086:
to a special sequence of functions which forms a fixed-point iteration, constructing the solution to the equation. Solving an ODE in this way is called
3406:
3662:
3586:
3246:
by repeating the iterative process a large number of times. More mathematically, the iterations converge to the fixed point of the IFS. Whenever
1589:
3320:
One may also consider certain iterations A-stable if the iterates stay bounded for a long time, which is beyond the scope of this article.
3295:
987:
2950:, the less stable it is, and the more computationally expensive it gets. For these reasons, higher order methods are typically not used.
561:
225:
706:
100:
72:
53:
3763:
2160:
3655:
3449:
3347:
79:
17:
3590:
2807:
3860:
2544:
1904:
has precisely one fixed point, and the fixed-point iteration is attracted towards that fixed point for any initial guess
3786:
3555:
377:
86:
2724:
3576:
3531:
3505:
3482:
3394:
3146:
119:
3679:
3407:
https://sie.scholasticahq.com/article/4663-solution-of-the-implicit-colebrook-equation-for-flow-friction-using-excel
3881:
3648:
68:
3850:
1793:, but iteration of this function for any value other than zero rapidly diverges. We say that the fixed point of
1750:(about 0.739085133), which is a fixed point. That is where the graph of the cosine function intersects the line
2957:
1999:
57:
3079:
2264:
1746:
key on a calculator (checking first that the calculator is in "radians" mode). It eventually converges to the
314:
3891:
2534:{\textstyle x_{\text{fix}}=g(x_{\text{fix}})=x_{\text{fix}}-{\frac {f(x_{\text{fix}})}{f'(x_{\text{fix}})}}}
3127:
corresponds to the fixed-point iteration of the composition of the supply function and the demand function.
858:
3814:
3442:
Nonlinearity, Bounded
Rationality, and Heterogeneity: Some Aspects of Market Economies as Complex Systems
2619:
1559:
3153:, and it can be shown that Steffensen's method yields a rate of convergence that is at least quadratic.
3082:, which shows that ordinary differential equations have solutions, is essentially an application of the
3886:
3819:
3083:
2921:
2710:
1873:
981:
680:
3025:
3635:
3595:
3180:
2960:
solvers in general can be viewed as fixed-point iterations. Indeed, the core idea when analyzing the
1541:
1319:{\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}
1200:. The Banach fixed-point theorem allows one to obtain fixed-point iterations with linear convergence.
141:
2661:
2397:
1384:
1240:
514:
467:
3804:
3748:
3184:
3138:
911:
788:
93:
2339:
3829:
3707:
3671:
46:
2884:
980:
This example does satisfy (at the latest after the first iteration step) the assumptions of the
818:
3753:
3280:
3150:
2953:
2121:
3519:
3493:
3337:
3142:
2718:
1901:
1796:
1493:
1133:
2080:
studies dynamical systems and classifies various behaviors such as attracting fixed points,
1958:
1107:
953:
3824:
3799:
2967:
2057:
1952:
1907:
1329:
1166:
199:
174:
2129:
8:
3809:
3738:
3730:
3427:
3300:
3243:
3109:
1877:
1753:
1700:
1456:
461:
3855:
3776:
3720:
3715:
3612:
3102:
3058:
3001:
2801:
2797:
2714:
2692:
2117:
2077:
1934:
1883:
1197:
849:
615:
541:
494:
205:
150:
133:
3389:
M A Kumar (2010), Solve
Implicit Equations (Colebrook) Within Worksheet, Createspace,
1442:{\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}
3771:
3616:
3572:
3551:
3527:
3501:
3478:
3445:
3390:
3343:
2878:
2085:
1779:
Not all fixed points are attracting. For example, 0 is a fixed point of the function
689:
371:
3471:
3687:
3604:
3541:
3113:
2101:
2073:
3566:
3545:
3364:
2081:
1850:
1839:
3630:
3137:
The speed of convergence of the iteration sequence can be increased by using a
3019:
3440:
Onozaki, Tamotsu (2018). "Chapter 2. One-Dimensional
Nonlinear Cobweb Model".
3165:
Sierpinski triangle created using IFS, selecting all members at each iteration
2068:
Attracting fixed points are a special case of a wider mathematical concept of
3875:
3794:
3743:
1876:
gives a sufficient condition for the existence of attracting fixed points. A
1747:
3692:
3608:
3515:
3290:
3124:
3120:
2089:
633:
3640:
3149:. The application of Aitken's method to fixed-point iteration is known as
1209:
is continuous is important, as the following example shows. The iteration
3285:
2961:
2881:). In general, it is possible to design methods that converge with speed
1987:
is continuously differentiable in an open neighbourhood of a fixed point
693:
168:
3469:
Burden, Richard L.; Faires, J. Douglas (1985). "Fixed-Point
Iteration".
3426:
Sniedovich, M. (2010). Dynamic
Programming: Foundations and Principles,
3116:
are based on fixed-point iterations in the space of the return function.
3697:
3636:
Fixed-point iteration online calculator (Mathematical
Assistant on Web)
3170:
3101:
The iteration capability in Excel can be used to find solutions to the
2713:, the Newton iteration, framed as the fixed-point method, demonstrates
3267:
2069:
1857:
of the second order is an example of a neutrally stable fixed point.
1488:
679:
converges to 0. This example does not satisfy the assumptions of the
3417:
Bellman, R. (1957). Dynamic programming, Princeton
University Press.
35:
3161:
3022:, and to check whether the ODE solver converges to the fixed point
2336:, we may rewrite the Newton iteration as the fixed-point iteration
1097:{\displaystyle |x_{n}-x|\leq {q^{n} \over 1-q}|x_{1}-x_{0}|=Cq^{n}}
644:
309:
3336:
Rassias, Themistocles M.; Pardalos, Panos M. (17 September 2014).
3239:
1931:
in the domain of the function. Common special cases are that (1)
764:{\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}
1735:
1731:
2107:
mathematically rigorous formalizations of iterative methods.
3339:
Mathematics
Without Boundaries: Surveys in Pure Mathematics
1435:
1312:
3500:(Second ed.). New York: CRC Press. pp. 141â145.
3266:
stay inside the attractor and, with probability 1, form a
3591:"An episodic history of the staircased iteration diagram"
2253:{\textstyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.}
3108:
Some of the "successive approximation" schemes used in
2727:
2547:
2431:
2342:
2267:
2163:
1686:{\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }
3565:
Shashkin, Yuri A. (1991). "9. The
Iteration Method".
3061:
3028:
3004:
2970:
2924:
2887:
2810:
2695:
2664:
2622:
2400:
2132:
2124:
for finding roots of a given differentiable function
2002:
1961:
1937:
1910:
1886:
1799:
1756:
1592:
1459:
1363:
1332:
1215:
1169:
1136:
1110:
990:
956:
914:
861:
821:
791:
709:
618:
564:
544:
517:
497:
470:
380:
317:
228:
208:
177:
153:
3255:
belongs to the attractor of the IFS, all iterations
2870:{\displaystyle |x_{n}-x_{\text{fix}}|<Cq^{3^{n}}}
2608:{\textstyle f(x_{\text{fix}})/f'(x_{\text{fix}})=0,}
1951:
is defined on the real line with real values and is
908:
converges to the unique fixed point of the function
511:
is continuous, then one can prove that the obtained
60:. Unsourced material may be challenged and removed.
3470:
3067:
3047:
3010:
2990:
2938:
2910:
2869:
2786:
2701:
2677:
2650:
2607:
2533:
2413:
2383:
2328:
2252:
2147:
2045:
1973:
1943:
1923:
1892:
1860:Multiple attracting points can be collected in an
1823:
1768:
1685:
1471:
1441:
1345:
1318:
1182:
1155:
1122:
1096:
972:
942:
900:
840:
807:
763:
624:
602:
550:
530:
503:
483:
452:
362:
300:
214:
190:
159:
3571:(First ed.). American Mathematical Society.
2964:of ODE solvers is to start with the special case
2787:{\textstyle |x_{n}-x_{\text{fix}}|<Cq^{2^{n}}}
603:{\displaystyle f(x_{\text{fix}})=x_{\text{fix}}.}
453:{\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }
301:{\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }
3873:
3335:
3498:Numerical Methods for Engineers and Scientists
3491:
3656:
2394:If this iteration converges to a fixed point
1867:
1163:.) When the error is less than a multiple of
683:and so its speed of convergence is very slow.
3468:
2110:
3670:
3296:Infinite compositions of analytic functions
3132:
984:. Hence, the error after n steps satisfies
3663:
3649:
3526:. Cambridge: MIT Press. pp. 165â167.
2804:when it works correctly, but its error is
2717:. However, a more detailed analysis shows
1834:An attracting fixed point is said to be a
1483:
3540:
3492:Hoffman, Joe D.; Frankel, Steven (2001).
3105:to an accuracy of 15 significant figures.
2932:
2329:{\textstyle g(x)=x-{\frac {f(x)}{f'(x)}}}
2046:{\displaystyle |f'(x_{\text{fix}})|<1}
939:
897:
688:A first simple and useful example is the
270:
120:Learn how and when to remove this message
3564:
3160:
2072:. Fixed-point iterations are a discrete
1855:linear homogeneous differential equation
1487:
643:
363:{\displaystyle x_{0},x_{1},x_{2},\dots }
3439:
14:
3874:
3550:(First ed.). Dover Publications.
3544:(2010). "Iteration and fixed points".
3356:
3196:, successive iterations are formed as
3644:
3362:
3179:refers to a method of generating the
1742:real number and repeatedly press the
1586:, the fixed-point iteration sequence
3585:
3514:
2946:. As a general rule, the higher the
2095:
1853:but not attracting. The center of a
901:{\displaystyle x_{n+1}=\cos x_{n}\,}
147:More specifically, given a function
58:adding citations to reliable sources
29:
2651:{\displaystyle f(x_{\text{fix}})=0}
171:with real values and given a point
24:
3477:(Third ed.). PWS Publishers.
3462:
1479:, and in fact has no fixed points.
25:
3903:
3624:
2939:{\displaystyle k\in \mathbb {N} }
1721:is the largest such neighborhood
1326:converges to 0 for all values of
3861:Sidi's generalized secant method
3048:{\displaystyle y_{\text{fix}}=0}
1567:of "close enough" points around
636:with values in that same space.
34:
3851:Inverse quadratic interpolation
3187:(IFS). Starting with any point
2709:. Under the assumptions of the
222:, the fixed-point iteration is
45:needs additional citations for
3524:Numerical Methods in Economics
3433:
3420:
3411:
3399:
3383:
3329:
3314:
3147:Aitken's delta-squared process
2958:ordinary differential equation
2840:
2812:
2794:, under certain circumstances.
2757:
2729:
2678:{\displaystyle x_{\text{fix}}}
2639:
2626:
2593:
2580:
2564:
2551:
2525:
2512:
2499:
2486:
2461:
2448:
2414:{\displaystyle x_{\text{fix}}}
2378:
2365:
2320:
2314:
2301:
2295:
2277:
2271:
2241:
2228:
2215:
2202:
2142:
2136:
2033:
2029:
2016:
2004:
1845:A fixed point is said to be a
1809:
1803:
1674:
1671:
1668:
1662:
1656:
1650:
1638:
1635:
1629:
1623:
1611:
1605:
1373:
1367:
1357:a fixed point of the function
1074:
1046:
1013:
992:
924:
918:
815:(from whatever starting point
719:
713:
581:
568:
531:{\displaystyle x_{\text{fix}}}
484:{\displaystyle x_{\text{fix}}}
441:
438:
425:
419:
410:
397:
264:
251:
13:
1:
3631:Fixed-point algorithms online
3307:
3156:
3114:Bellman's functional equation
2384:{\textstyle x_{n+1}=g(x_{n})}
2063:
1734:function ("natural" means in
1712:. The basin of attraction of
943:{\displaystyle f(x)=\cos x\,}
848:). This is a special case of
808:{\displaystyle x={\sqrt {a}}}
612:More generally, the function
1847:neutrally stable fixed point
7:
3273:
2088:. An example system is the
1576:such that for any value of
703:, which consists in taking
639:
10:
3908:
3680:Bracketing (no derivative)
3168:
3084:Banach fixed-point theorem
3055:whenever the real part of
2911:{\displaystyle Cq^{k^{n}}}
2711:Banach fixed-point theorem
2099:
1874:Banach fixed-point theorem
1868:Banach fixed-point theorem
982:Banach fixed-point theorem
855:The fixed-point iteration
841:{\displaystyle x_{0}\gg 0}
681:Banach fixed-point theorem
648:The fixed-point iteration
3838:
3785:
3762:
3729:
3706:
3678:
3596:Antiquitates Mathematicae
2111:Iterative method examples
2056:Although there are other
771:, i.e. the mean value of
140:is a method of computing
3185:iterated function system
3139:convergence acceleration
3133:Convergence acceleration
3096:Picard iterative process
1955:with Lipschitz constant
785:, to approach the limit
308:which gives rise to the
3882:Root-finding algorithms
3830:Splitting circle method
3815:JenkinsâTraub algorithm
3672:Root-finding algorithms
3520:"Fixed-Point Iteration"
3494:"Fixed-Point Iteration"
3371:. Wolfram Research, Inc
3080:PicardâLindelöf theorem
1981:, and (2) the function
1824:{\displaystyle f(x)=2x}
1484:Attracting fixed points
1156:{\displaystyle x_{0}=1}
950:for any starting point
69:"Fixed-point iteration"
3820:LehmerâSchur algorithm
3609:10.14708/am.v15i1.7056
3281:Fixed-point combinator
3166:
3069:
3049:
3012:
2992:
2940:
2912:
2871:
2788:
2703:
2679:
2652:
2609:
2535:
2415:
2385:
2330:
2254:
2149:
2122:root-finding algorithm
2047:
1975:
1974:{\displaystyle L<1}
1945:
1925:
1894:
1825:
1770:
1687:
1532:attracting fixed point
1527:
1473:
1443:
1347:
1320:
1196:, we say that we have
1184:
1157:
1124:
1123:{\displaystyle q=0.85}
1098:
974:
973:{\displaystyle x_{0}.}
944:
902:
842:
809:
765:
684:
632:can be defined on any
626:
604:
552:
532:
505:
485:
454:
364:
302:
216:
192:
161:
27:Root-finding algorithm
3846:Fixed-point iteration
3164:
3143:Anderson acceleration
3070:
3050:
3013:
2993:
2991:{\displaystyle y'=ay}
2941:
2913:
2872:
2789:
2719:quadratic convergence
2704:
2680:
2653:
2610:
2536:
2416:
2386:
2331:
2255:
2150:
2048:
1976:
1946:
1926:
1924:{\displaystyle x_{0}}
1902:complete metric space
1895:
1826:
1771:
1688:
1494:fixed point iteration
1491:
1474:
1444:
1348:
1346:{\displaystyle x_{0}}
1321:
1203:The requirement that
1185:
1183:{\displaystyle q^{n}}
1158:
1125:
1099:
975:
945:
903:
843:
810:
766:
647:
627:
605:
553:
533:
506:
486:
455:
365:
303:
217:
193:
191:{\displaystyle x_{0}}
162:
138:fixed-point iteration
18:Fixed point iteration
3892:Fixed-point theorems
3805:DurandâKerner method
3749:NewtonâKrylov method
3428:Taylor & Francis
3059:
3026:
3002:
2968:
2922:
2885:
2808:
2725:
2693:
2662:
2620:
2545:
2429:
2398:
2340:
2265:
2161:
2148:{\displaystyle f(x)}
2130:
2058:fixed-point theorems
2000:
1959:
1953:Lipschitz continuous
1935:
1908:
1884:
1862:attracting fixed set
1797:
1754:
1590:
1457:
1449:as this function is
1361:
1330:
1213:
1167:
1134:
1108:
988:
954:
912:
859:
819:
789:
707:
616:
562:
542:
538:is a fixed point of
515:
495:
468:
378:
315:
226:
206:
175:
151:
54:improve this article
3754:Steffensen's method
3363:Weisstein, Eric W.
3301:Rate of convergence
3244:Sierpinski triangle
3151:Steffensen's method
3110:dynamic programming
2954:RungeâKutta methods
2157:. The iteration is
1878:contraction mapping
1769:{\displaystyle y=x}
1516:with initial value
1472:{\displaystyle x=0}
1130:, if we start from
1104:(where we can take
669:with initial value
3787:Polynomial methods
3473:Numerical Analysis
3167:
3103:Colebrook equation
3065:
3045:
3008:
2988:
2936:
2908:
2867:
2784:
2715:linear convergence
2699:
2675:
2648:
2605:
2531:
2411:
2381:
2326:
2250:
2145:
2086:strange attractors
2078:Bifurcation theory
2043:
1971:
1941:
1921:
1890:
1836:stable fixed point
1821:
1766:
1683:
1528:
1469:
1439:
1434:
1343:
1316:
1311:
1198:linear convergence
1190:for some constant
1180:
1153:
1120:
1094:
970:
940:
898:
838:
805:
761:
692:for computing the
685:
622:
600:
548:
528:
501:
481:
460:which is hoped to
450:
360:
298:
212:
188:
157:
134:numerical analysis
3887:Iterative methods
3869:
3868:
3825:Laguerre's method
3800:Bairstow's method
3547:Dynamical Systems
3542:Sternberg, Shlomo
3451:978-4-431-54971-0
3369:Wolfram MathWorld
3349:978-1-4939-1106-6
3068:{\displaystyle a}
3036:
3011:{\displaystyle a}
2879:cubic convergence
2836:
2753:
2702:{\displaystyle f}
2672:
2636:
2590:
2561:
2529:
2522:
2496:
2474:
2458:
2439:
2408:
2324:
2245:
2096:Iterative methods
2076:on one variable.
2026:
1944:{\displaystyle f}
1893:{\displaystyle f}
1646:
1619:
1601:
1395:
1258:
1043:
803:
748:
733:
690:Babylonian method
625:{\displaystyle f}
594:
578:
551:{\displaystyle f}
525:
504:{\displaystyle f}
478:
372:iterated function
215:{\displaystyle f}
160:{\displaystyle f}
130:
129:
122:
104:
16:(Redirected from
3899:
3810:Graeffe's method
3739:Broyden's method
3688:Bisection method
3665:
3658:
3651:
3642:
3641:
3620:
3587:Rosa, Alessandro
3582:
3561:
3537:
3516:Judd, Kenneth L.
3511:
3488:
3476:
3456:
3455:
3437:
3431:
3424:
3418:
3415:
3409:
3403:
3397:
3387:
3381:
3380:
3378:
3376:
3360:
3354:
3353:
3333:
3321:
3318:
3265:
3254:
3237:
3226:
3195:
3088:Picard iteration
3074:
3072:
3071:
3066:
3054:
3052:
3051:
3046:
3038:
3037:
3034:
3017:
3015:
3014:
3009:
2997:
2995:
2994:
2989:
2978:
2949:
2945:
2943:
2942:
2937:
2935:
2917:
2915:
2914:
2909:
2907:
2906:
2905:
2904:
2876:
2874:
2873:
2868:
2866:
2865:
2864:
2863:
2843:
2838:
2837:
2834:
2825:
2824:
2815:
2793:
2791:
2790:
2785:
2783:
2782:
2781:
2780:
2760:
2755:
2754:
2751:
2742:
2741:
2732:
2708:
2706:
2705:
2700:
2684:
2682:
2681:
2676:
2674:
2673:
2670:
2657:
2655:
2654:
2649:
2638:
2637:
2634:
2614:
2612:
2611:
2606:
2592:
2591:
2588:
2579:
2571:
2563:
2562:
2559:
2540:
2538:
2537:
2532:
2530:
2528:
2524:
2523:
2520:
2511:
2502:
2498:
2497:
2494:
2481:
2476:
2475:
2472:
2460:
2459:
2456:
2441:
2440:
2437:
2424:
2420:
2418:
2417:
2412:
2410:
2409:
2406:
2390:
2388:
2387:
2382:
2377:
2376:
2358:
2357:
2335:
2333:
2332:
2327:
2325:
2323:
2313:
2304:
2290:
2259:
2257:
2256:
2251:
2246:
2244:
2240:
2239:
2227:
2218:
2214:
2213:
2197:
2192:
2191:
2179:
2178:
2156:
2154:
2152:
2151:
2146:
2102:Iterative method
2074:dynamical system
2052:
2050:
2049:
2044:
2036:
2028:
2027:
2024:
2015:
2007:
1995:
1986:
1980:
1978:
1977:
1972:
1950:
1948:
1947:
1942:
1930:
1928:
1927:
1922:
1920:
1919:
1899:
1897:
1896:
1891:
1830:
1828:
1827:
1822:
1792:
1775:
1773:
1772:
1767:
1726:
1720:
1711:
1698:
1693:is contained in
1692:
1690:
1689:
1684:
1644:
1617:
1599:
1585:
1579:
1575:
1566:
1557:
1551:
1539:
1525:
1515:
1478:
1476:
1475:
1470:
1448:
1446:
1445:
1440:
1438:
1437:
1396:
1388:
1353:. However, 0 is
1352:
1350:
1349:
1344:
1342:
1341:
1325:
1323:
1322:
1317:
1315:
1314:
1302:
1301:
1274:
1273:
1259:
1254:
1253:
1244:
1231:
1230:
1208:
1195:
1189:
1187:
1186:
1181:
1179:
1178:
1162:
1160:
1159:
1154:
1146:
1145:
1129:
1127:
1126:
1121:
1103:
1101:
1100:
1095:
1093:
1092:
1077:
1072:
1071:
1059:
1058:
1049:
1044:
1042:
1031:
1030:
1021:
1016:
1005:
1004:
995:
979:
977:
976:
971:
966:
965:
949:
947:
946:
941:
907:
905:
904:
899:
896:
895:
877:
876:
847:
845:
844:
839:
831:
830:
814:
812:
811:
806:
804:
799:
784:
774:
770:
768:
767:
762:
760:
756:
749:
741:
734:
726:
702:
678:
668:
631:
629:
628:
623:
609:
607:
606:
601:
596:
595:
592:
580:
579:
576:
557:
555:
554:
549:
537:
535:
534:
529:
527:
526:
523:
510:
508:
507:
502:
490:
488:
487:
482:
480:
479:
476:
459:
457:
456:
451:
437:
436:
409:
408:
390:
389:
369:
367:
366:
361:
353:
352:
340:
339:
327:
326:
307:
305:
304:
299:
263:
262:
244:
243:
221:
219:
218:
213:
197:
195:
194:
189:
187:
186:
166:
164:
163:
158:
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
3907:
3906:
3902:
3901:
3900:
3898:
3897:
3896:
3872:
3871:
3870:
3865:
3856:Muller's method
3834:
3781:
3777:Ridders' method
3758:
3725:
3721:Halley's method
3716:Newton's method
3702:
3674:
3669:
3627:
3579:
3558:
3534:
3508:
3485:
3465:
3463:Further reading
3460:
3459:
3452:
3438:
3434:
3425:
3421:
3416:
3412:
3404:
3400:
3388:
3384:
3374:
3372:
3365:"Dottie Number"
3361:
3357:
3350:
3334:
3330:
3325:
3324:
3319:
3315:
3310:
3305:
3276:
3270:in the latter.
3264:
3256:
3253:
3247:
3236:
3228:
3224:
3215:
3206:
3197:
3194:
3188:
3173:
3159:
3141:method such as
3135:
3130:
3092:Picard's method
3060:
3057:
3056:
3033:
3029:
3027:
3024:
3023:
3003:
3000:
2999:
2971:
2969:
2966:
2965:
2947:
2931:
2923:
2920:
2919:
2900:
2896:
2895:
2891:
2886:
2883:
2882:
2859:
2855:
2854:
2850:
2839:
2833:
2829:
2820:
2816:
2811:
2809:
2806:
2805:
2802:Newton's method
2798:Halley's method
2776:
2772:
2771:
2767:
2756:
2750:
2746:
2737:
2733:
2728:
2726:
2723:
2722:
2694:
2691:
2690:
2669:
2665:
2663:
2660:
2659:
2633:
2629:
2621:
2618:
2617:
2587:
2583:
2572:
2567:
2558:
2554:
2546:
2543:
2542:
2519:
2515:
2504:
2503:
2493:
2489:
2482:
2480:
2471:
2467:
2455:
2451:
2436:
2432:
2430:
2427:
2426:
2422:
2405:
2401:
2399:
2396:
2395:
2372:
2368:
2347:
2343:
2341:
2338:
2337:
2306:
2305:
2291:
2289:
2266:
2263:
2262:
2235:
2231:
2220:
2219:
2209:
2205:
2198:
2196:
2187:
2183:
2168:
2164:
2162:
2159:
2158:
2131:
2128:
2127:
2125:
2118:Newton's method
2113:
2104:
2098:
2082:periodic orbits
2066:
2032:
2023:
2019:
2008:
2003:
2001:
1998:
1997:
1994:
1988:
1982:
1960:
1957:
1956:
1936:
1933:
1932:
1915:
1911:
1909:
1906:
1905:
1885:
1882:
1881:
1870:
1851:Lyapunov stable
1840:Lyapunov stable
1831:is repelling.
1798:
1795:
1794:
1780:
1755:
1752:
1751:
1722:
1719:
1713:
1710:
1704:
1694:
1591:
1588:
1587:
1581:
1577:
1574:
1568:
1562:
1553:
1550:
1544:
1535:
1523:
1517:
1514:
1505:
1496:
1486:
1458:
1455:
1454:
1433:
1432:
1421:
1412:
1411:
1400:
1387:
1380:
1379:
1362:
1359:
1358:
1337:
1333:
1331:
1328:
1327:
1310:
1309:
1297:
1293:
1291:
1282:
1281:
1269:
1265:
1263:
1249:
1245:
1243:
1236:
1235:
1220:
1216:
1214:
1211:
1210:
1204:
1191:
1174:
1170:
1168:
1165:
1164:
1141:
1137:
1135:
1132:
1131:
1109:
1106:
1105:
1088:
1084:
1073:
1067:
1063:
1054:
1050:
1045:
1032:
1026:
1022:
1020:
1012:
1000:
996:
991:
989:
986:
985:
961:
957:
955:
952:
951:
913:
910:
909:
891:
887:
866:
862:
860:
857:
856:
850:Newton's method
826:
822:
820:
817:
816:
798:
790:
787:
786:
776:
772:
740:
739:
735:
725:
708:
705:
704:
697:
676:
670:
667:
658:
649:
642:
617:
614:
613:
591:
587:
575:
571:
563:
560:
559:
543:
540:
539:
522:
518:
516:
513:
512:
496:
493:
492:
475:
471:
469:
466:
465:
432:
428:
404:
400:
385:
381:
379:
376:
375:
348:
344:
335:
331:
322:
318:
316:
313:
312:
258:
254:
233:
229:
227:
224:
223:
207:
204:
203:
182:
178:
176:
173:
172:
167:defined on the
152:
149:
148:
144:of a function.
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
3905:
3895:
3894:
3889:
3884:
3867:
3866:
3864:
3863:
3858:
3853:
3848:
3842:
3840:
3836:
3835:
3833:
3832:
3827:
3822:
3817:
3812:
3807:
3802:
3797:
3791:
3789:
3783:
3782:
3780:
3779:
3774:
3772:Brent's method
3768:
3766:
3764:Hybrid methods
3760:
3759:
3757:
3756:
3751:
3746:
3741:
3735:
3733:
3727:
3726:
3724:
3723:
3718:
3712:
3710:
3704:
3703:
3701:
3700:
3695:
3690:
3684:
3682:
3676:
3675:
3668:
3667:
3660:
3653:
3645:
3639:
3638:
3633:
3626:
3625:External links
3623:
3622:
3621:
3583:
3577:
3562:
3557:978-0486477053
3556:
3538:
3532:
3512:
3506:
3489:
3483:
3464:
3461:
3458:
3457:
3450:
3432:
3419:
3410:
3398:
3382:
3355:
3348:
3327:
3326:
3323:
3322:
3312:
3311:
3309:
3306:
3304:
3303:
3298:
3293:
3288:
3283:
3277:
3275:
3272:
3260:
3251:
3232:
3220:
3211:
3201:
3192:
3169:Main article:
3158:
3155:
3134:
3131:
3129:
3128:
3117:
3106:
3099:
3076:
3064:
3044:
3041:
3032:
3020:complex number
3007:
2987:
2984:
2981:
2977:
2974:
2956:and numerical
2951:
2934:
2930:
2927:
2903:
2899:
2894:
2890:
2862:
2858:
2853:
2849:
2846:
2842:
2832:
2828:
2823:
2819:
2814:
2800:is similar to
2795:
2779:
2775:
2770:
2766:
2763:
2759:
2749:
2745:
2740:
2736:
2731:
2698:
2668:
2647:
2644:
2641:
2632:
2628:
2625:
2604:
2601:
2598:
2595:
2586:
2582:
2578:
2575:
2570:
2566:
2557:
2553:
2550:
2527:
2518:
2514:
2510:
2507:
2501:
2492:
2488:
2485:
2479:
2470:
2466:
2463:
2454:
2450:
2447:
2444:
2435:
2404:
2380:
2375:
2371:
2367:
2364:
2361:
2356:
2353:
2350:
2346:
2322:
2319:
2316:
2312:
2309:
2303:
2300:
2297:
2294:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2249:
2243:
2238:
2234:
2230:
2226:
2223:
2217:
2212:
2208:
2204:
2201:
2195:
2190:
2186:
2182:
2177:
2174:
2171:
2167:
2144:
2141:
2138:
2135:
2114:
2112:
2109:
2100:Main article:
2097:
2094:
2065:
2062:
2042:
2039:
2035:
2031:
2022:
2018:
2014:
2011:
2006:
1992:
1970:
1967:
1964:
1940:
1918:
1914:
1889:
1869:
1866:
1838:if it is also
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1765:
1762:
1759:
1717:
1708:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1616:
1613:
1610:
1607:
1604:
1598:
1595:
1572:
1548:
1534:of a function
1521:
1510:
1500:
1485:
1482:
1481:
1480:
1468:
1465:
1462:
1453:continuous at
1436:
1431:
1428:
1425:
1422:
1420:
1417:
1414:
1413:
1410:
1407:
1404:
1401:
1399:
1394:
1391:
1386:
1385:
1383:
1378:
1375:
1372:
1369:
1366:
1340:
1336:
1313:
1308:
1305:
1300:
1296:
1292:
1290:
1287:
1284:
1283:
1280:
1277:
1272:
1268:
1264:
1262:
1257:
1252:
1248:
1242:
1241:
1239:
1234:
1229:
1226:
1223:
1219:
1201:
1177:
1173:
1152:
1149:
1144:
1140:
1119:
1116:
1113:
1091:
1087:
1083:
1080:
1076:
1070:
1066:
1062:
1057:
1053:
1048:
1041:
1038:
1035:
1029:
1025:
1019:
1015:
1011:
1008:
1003:
999:
994:
969:
964:
960:
938:
935:
932:
929:
926:
923:
920:
917:
894:
890:
886:
883:
880:
875:
872:
869:
865:
853:
837:
834:
829:
825:
802:
797:
794:
759:
755:
752:
747:
744:
738:
732:
729:
724:
721:
718:
715:
712:
674:
663:
653:
641:
638:
621:
599:
590:
586:
583:
574:
570:
567:
547:
521:
500:
474:
449:
446:
443:
440:
435:
431:
427:
424:
421:
418:
415:
412:
407:
403:
399:
396:
393:
388:
384:
359:
356:
351:
347:
343:
338:
334:
330:
325:
321:
297:
294:
291:
288:
285:
282:
279:
276:
273:
269:
266:
261:
257:
253:
250:
247:
242:
239:
236:
232:
211:
185:
181:
156:
128:
127:
42:
40:
33:
26:
9:
6:
4:
3:
2:
3904:
3893:
3890:
3888:
3885:
3883:
3880:
3879:
3877:
3862:
3859:
3857:
3854:
3852:
3849:
3847:
3844:
3843:
3841:
3839:Other methods
3837:
3831:
3828:
3826:
3823:
3821:
3818:
3816:
3813:
3811:
3808:
3806:
3803:
3801:
3798:
3796:
3795:Aberth method
3793:
3792:
3790:
3788:
3784:
3778:
3775:
3773:
3770:
3769:
3767:
3765:
3761:
3755:
3752:
3750:
3747:
3745:
3744:Secant method
3742:
3740:
3737:
3736:
3734:
3732:
3728:
3722:
3719:
3717:
3714:
3713:
3711:
3709:
3705:
3699:
3696:
3694:
3691:
3689:
3686:
3685:
3683:
3681:
3677:
3673:
3666:
3661:
3659:
3654:
3652:
3647:
3646:
3643:
3637:
3634:
3632:
3629:
3628:
3618:
3614:
3610:
3606:
3602:
3598:
3597:
3592:
3588:
3584:
3580:
3578:0-8218-9000-X
3574:
3570:
3569:
3563:
3559:
3553:
3549:
3548:
3543:
3539:
3535:
3533:0-262-10071-1
3529:
3525:
3521:
3517:
3513:
3509:
3507:0-8247-0443-6
3503:
3499:
3495:
3490:
3486:
3484:0-87150-857-5
3480:
3475:
3474:
3467:
3466:
3453:
3447:
3443:
3436:
3429:
3423:
3414:
3408:
3402:
3396:
3395:1-4528-1619-0
3392:
3386:
3370:
3366:
3359:
3351:
3345:
3341:
3340:
3332:
3328:
3317:
3313:
3302:
3299:
3297:
3294:
3292:
3289:
3287:
3284:
3282:
3279:
3278:
3271:
3269:
3263:
3259:
3250:
3245:
3241:
3235:
3231:
3223:
3219:
3214:
3210:
3204:
3200:
3191:
3186:
3182:
3178:
3172:
3163:
3154:
3152:
3148:
3144:
3140:
3126:
3122:
3118:
3115:
3111:
3107:
3104:
3100:
3097:
3093:
3089:
3085:
3081:
3077:
3062:
3042:
3039:
3030:
3021:
3005:
2985:
2982:
2979:
2975:
2972:
2963:
2959:
2955:
2952:
2928:
2925:
2901:
2897:
2892:
2888:
2880:
2860:
2856:
2851:
2847:
2844:
2830:
2826:
2821:
2817:
2803:
2799:
2796:
2777:
2773:
2768:
2764:
2761:
2747:
2743:
2738:
2734:
2720:
2716:
2712:
2696:
2688:
2666:
2645:
2642:
2630:
2623:
2615:
2602:
2599:
2596:
2584:
2576:
2573:
2568:
2555:
2548:
2516:
2508:
2505:
2490:
2483:
2477:
2468:
2464:
2452:
2445:
2442:
2433:
2402:
2392:
2373:
2369:
2362:
2359:
2354:
2351:
2348:
2344:
2317:
2310:
2307:
2298:
2292:
2286:
2283:
2280:
2274:
2268:
2247:
2236:
2232:
2224:
2221:
2210:
2206:
2199:
2193:
2188:
2184:
2180:
2175:
2172:
2169:
2165:
2139:
2133:
2123:
2119:
2116:
2115:
2108:
2103:
2093:
2091:
2087:
2083:
2079:
2075:
2071:
2061:
2059:
2054:
2040:
2037:
2020:
2012:
2009:
1991:
1985:
1968:
1965:
1962:
1954:
1938:
1916:
1912:
1903:
1900:defined on a
1887:
1879:
1875:
1865:
1863:
1858:
1856:
1852:
1848:
1843:
1841:
1837:
1832:
1818:
1815:
1812:
1806:
1800:
1791:
1787:
1783:
1777:
1763:
1760:
1757:
1749:
1748:Dottie number
1745:
1741:
1737:
1733:
1728:
1725:
1716:
1707:
1702:
1697:
1680:
1677:
1665:
1659:
1653:
1647:
1641:
1632:
1626:
1620:
1614:
1608:
1602:
1596:
1593:
1584:
1571:
1565:
1561:
1556:
1547:
1543:
1538:
1533:
1520:
1513:
1509:
1503:
1499:
1495:
1490:
1466:
1463:
1460:
1452:
1429:
1426:
1423:
1418:
1415:
1408:
1405:
1402:
1397:
1392:
1389:
1381:
1376:
1370:
1364:
1356:
1338:
1334:
1306:
1303:
1298:
1294:
1288:
1285:
1278:
1275:
1270:
1266:
1260:
1255:
1250:
1246:
1237:
1232:
1227:
1224:
1221:
1217:
1207:
1202:
1199:
1194:
1175:
1171:
1150:
1147:
1142:
1138:
1117:
1114:
1111:
1089:
1085:
1081:
1078:
1068:
1064:
1060:
1055:
1051:
1039:
1036:
1033:
1027:
1023:
1017:
1009:
1006:
1001:
997:
983:
967:
962:
958:
936:
933:
930:
927:
921:
915:
892:
888:
884:
881:
878:
873:
870:
867:
863:
854:
852:quoted below.
851:
835:
832:
827:
823:
800:
795:
792:
783:
779:
757:
753:
750:
745:
742:
736:
730:
727:
722:
716:
710:
700:
695:
691:
687:
686:
682:
673:
666:
662:
656:
652:
646:
637:
635:
619:
610:
597:
588:
584:
572:
565:
545:
519:
498:
472:
463:
447:
444:
433:
429:
422:
416:
413:
405:
401:
394:
391:
386:
382:
374:applications
373:
357:
354:
349:
345:
341:
336:
332:
328:
323:
319:
311:
295:
292:
289:
286:
283:
280:
277:
274:
271:
267:
259:
255:
248:
245:
240:
237:
234:
230:
209:
201:
183:
179:
170:
154:
145:
143:
139:
135:
124:
121:
113:
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: â
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
3845:
3731:Quasi-Newton
3693:Regula falsi
3600:
3594:
3568:Fixed Points
3567:
3546:
3523:
3497:
3472:
3444:. Springer.
3441:
3435:
3422:
3413:
3401:
3385:
3373:. Retrieved
3368:
3358:
3342:. Springer.
3338:
3331:
3316:
3291:Markov chain
3261:
3257:
3248:
3242:such as the
3233:
3229:
3221:
3217:
3212:
3208:
3202:
3198:
3189:
3176:
3174:
3136:
3125:price theory
3121:cobweb model
3095:
3091:
3087:
3075:is negative.
2686:
2393:
2261:If we write
2260:
2105:
2090:logistic map
2067:
2055:
1989:
1983:
1871:
1861:
1859:
1846:
1844:
1835:
1833:
1789:
1785:
1781:
1778:
1743:
1739:
1730:The natural
1729:
1723:
1714:
1705:
1695:
1582:
1569:
1563:
1560:neighborhood
1554:
1545:
1536:
1531:
1529:
1518:
1511:
1507:
1501:
1497:
1450:
1354:
1205:
1192:
781:
777:
698:
671:
664:
660:
654:
650:
634:metric space
611:
169:real numbers
146:
142:fixed points
137:
131:
116:
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
3708:Householder
3286:Cobweb plot
3181:fixed point
2962:A-stability
2658:, that is,
1542:fixed point
694:square root
464:to a point
3876:Categories
3698:ITP method
3308:References
3177:chaos game
3171:Chaos game
3157:Chaos game
2616:therefore
2070:attractors
2064:Attractors
80:newspapers
3617:247259939
3268:dense set
3175:The term
3112:to solve
3094:, or the
2929:∈
2827:−
2744:−
2478:−
2287:−
2194:−
1880:function
1849:if it is
1701:converges
1681:…
1406:≠
1276:≠
1061:−
1037:−
1018:≤
1007:−
934:
885:
833:≫
448:…
358:…
296:…
3603:: 3â90.
3589:(2021).
3518:(1998).
3274:See also
3227:, where
2998:, where
2976:′
2918:for any
2721:, i.e.,
2577:′
2509:′
2311:′
2225:′
2013:′
640:Examples
558:, i.e.,
462:converge
310:sequence
110:May 2010
3375:23 July
3240:fractal
3183:of any
2425:, then
2155:
2126:
1736:radians
1558:with a
198:in the
94:scholar
3615:
3575:
3554:
3530:
3504:
3481:
3448:
3393:
3346:
1996:, and
1732:cosine
1645:
1618:
1600:
1506:= cos
701:> 0
659:= sin
200:domain
96:
89:
82:
75:
67:
3613:S2CID
3018:is a
2685:is a
2541:, so
2120:is a
2084:, or
1788:) = 2
1540:is a
491:. If
101:JSTOR
87:books
3573:ISBN
3552:ISBN
3528:ISBN
3502:ISBN
3479:ISBN
3446:ISBN
3391:ISBN
3377:2016
3344:ISBN
3145:and
3119:The
3078:The
2845:<
2762:<
2687:root
2038:<
1966:<
1872:The
1699:and
1524:= â1
1492:The
1118:0.85
775:and
73:news
3605:doi
3123:of
3035:fix
2835:fix
2752:fix
2689:of
2671:fix
2635:fix
2589:fix
2560:fix
2521:fix
2495:fix
2473:fix
2457:fix
2438:fix
2421:of
2407:fix
2025:fix
1993:fix
1744:cos
1740:any
1718:fix
1709:fix
1703:to
1580:in
1573:fix
1552:of
1549:fix
1530:An
1451:not
1355:not
931:cos
882:cos
696:of
677:= 2
593:fix
577:fix
524:fix
477:fix
370:of
202:of
132:In
56:by
3878::
3611:.
3601:15
3599:.
3593:.
3522:.
3496:.
3367:.
3207:=
3205:+1
3090:,
2391:.
2092:.
2053:.
1864:.
1842:.
1776:.
1727:.
1504:+1
657:+1
136:,
3664:e
3657:t
3650:v
3619:.
3607::
3581:.
3560:.
3536:.
3510:.
3487:.
3454:.
3430:.
3379:.
3352:.
3262:k
3258:x
3252:0
3249:x
3234:r
3230:f
3225:)
3222:k
3218:x
3216:(
3213:r
3209:f
3203:k
3199:x
3193:0
3190:x
3098:.
3063:a
3043:0
3040:=
3031:y
3006:a
2986:y
2983:a
2980:=
2973:y
2948:k
2933:N
2926:k
2902:n
2898:k
2893:q
2889:C
2877:(
2861:n
2857:3
2852:q
2848:C
2841:|
2831:x
2822:n
2818:x
2813:|
2778:n
2774:2
2769:q
2765:C
2758:|
2748:x
2739:n
2735:x
2730:|
2697:f
2667:x
2646:0
2643:=
2640:)
2631:x
2627:(
2624:f
2603:,
2600:0
2597:=
2594:)
2585:x
2581:(
2574:f
2569:/
2565:)
2556:x
2552:(
2549:f
2526:)
2517:x
2513:(
2506:f
2500:)
2491:x
2487:(
2484:f
2469:x
2465:=
2462:)
2453:x
2449:(
2446:g
2443:=
2434:x
2423:g
2403:x
2379:)
2374:n
2370:x
2366:(
2363:g
2360:=
2355:1
2352:+
2349:n
2345:x
2321:)
2318:x
2315:(
2308:f
2302:)
2299:x
2296:(
2293:f
2284:x
2281:=
2278:)
2275:x
2272:(
2269:g
2248:.
2242:)
2237:n
2233:x
2229:(
2222:f
2216:)
2211:n
2207:x
2203:(
2200:f
2189:n
2185:x
2181:=
2176:1
2173:+
2170:n
2166:x
2143:)
2140:x
2137:(
2134:f
2041:1
2034:|
2030:)
2021:x
2017:(
2010:f
2005:|
1990:x
1984:f
1969:1
1963:L
1939:f
1917:0
1913:x
1888:f
1819:x
1816:2
1813:=
1810:)
1807:x
1804:(
1801:f
1790:x
1786:x
1784:(
1782:f
1764:x
1761:=
1758:y
1724:U
1715:x
1706:x
1696:U
1678:,
1675:)
1672:)
1669:)
1666:x
1663:(
1660:f
1657:(
1654:f
1651:(
1648:f
1642:,
1639:)
1636:)
1633:x
1630:(
1627:f
1624:(
1621:f
1615:,
1612:)
1609:x
1606:(
1603:f
1597:,
1594:x
1583:U
1578:x
1570:x
1564:U
1555:f
1546:x
1537:f
1526:.
1522:1
1519:x
1512:n
1508:x
1502:n
1498:x
1467:0
1464:=
1461:x
1430:0
1427:=
1424:x
1419:,
1416:1
1409:0
1403:x
1398:,
1393:2
1390:x
1382:{
1377:=
1374:)
1371:x
1368:(
1365:f
1339:0
1335:x
1307:0
1304:=
1299:n
1295:x
1289:,
1286:1
1279:0
1271:n
1267:x
1261:,
1256:2
1251:n
1247:x
1238:{
1233:=
1228:1
1225:+
1222:n
1218:x
1206:f
1193:q
1176:n
1172:q
1151:1
1148:=
1143:0
1139:x
1115:=
1112:q
1090:n
1086:q
1082:C
1079:=
1075:|
1069:0
1065:x
1056:1
1052:x
1047:|
1040:q
1034:1
1028:n
1024:q
1014:|
1010:x
1002:n
998:x
993:|
968:.
963:0
959:x
937:x
928:=
925:)
922:x
919:(
916:f
893:n
889:x
879:=
874:1
871:+
868:n
864:x
836:0
828:0
824:x
801:a
796:=
793:x
782:x
780:/
778:a
773:x
758:)
754:x
751:+
746:x
743:a
737:(
731:2
728:1
723:=
720:)
717:x
714:(
711:f
699:a
675:0
672:x
665:n
661:x
655:n
651:x
620:f
598:.
589:x
585:=
582:)
573:x
569:(
566:f
546:f
520:x
499:f
473:x
445:,
442:)
439:)
434:0
430:x
426:(
423:f
420:(
417:f
414:,
411:)
406:0
402:x
398:(
395:f
392:,
387:0
383:x
355:,
350:2
346:x
342:,
337:1
333:x
329:,
324:0
320:x
293:,
290:2
287:,
284:1
281:,
278:0
275:=
272:n
268:,
265:)
260:n
256:x
252:(
249:f
246:=
241:1
238:+
235:n
231:x
210:f
184:0
180:x
155:f
123:)
117:(
112:)
108:(
98:·
91:·
84:·
77:·
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
