Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences

9 years ago

(original), Convergence order, html, JCR/ISI, Numerical Analysis, paper, PDF, solving F(x)=0 iteratively, works

Abstract

We study the conditions under which the well-known Aitken-Steffensen method for solving equations leads to monotonic sequences whose terms approximate (from the left and from the right) the root of an equation. The convergence order and efficiency index of this method are also studied in the general case and then in various particular cases.

Authors

Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)

Keywords

nonlinear equations in R; Aitken-Steffensen method; monotone sequences; iterative methods; convergence order.

PDF

https://ictp.acad.ro/wp-content/uploads/2026/09/1995-Pavaloiu-Calcolo32-nos1-2-Approximation-of-the-roots-of-equations-by-Aitken-Steffensen-type-monotonic-sequences-pp.-69-82.pdf

Cite this paper as:

I. Păvăloiu, Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32 (1995) nos. 1-2, pp. 69-82.

About this paper

Journal

Calcolo

Publisher Name

Springer

DOI

https://doi.org/10.1007/BF02576543

Print ISSN

0008-0624

Online ISSN

1126-5434

References

[1] M. Balázs,A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théorie Approximation, (21),2 (1992), 111–117.

[2] V. Casulli, D. Trigiante,The convergence order for iterative multipoint procedures, Calcolo, (13),1 (1977), 25–44.

[3] A. M. Ostrowski,Solution of equations and systems of equations, (1960), Academic Press, New York and London.

[4] I. Păvăloiu,On the monotonicity of the sequences of approximations obtained by Steffensen’s method, Mathematica (Cluj), (35), (58),1 (1993), 71–76.

[5] I. Păvăloiu,Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théorie Approximation, (23),1 (1994), 95–100.

[6] F. J. Traub,Iterative methods for the solution of equations, (1964), Prentice-Hall, Inc. Englewood Cliffs, N.J.

Paper (preprint) in HTML form

/*====================================================================== Core CSS for LaTeXML documents converted to (X)HTML */ /* Generic Page layout */ .ltx_page_header, .ltx_page_footer { font-size:0.8em; } .ltx_page_header *[rel~="prev"], .ltx_page_footer *[rel~="prev"] { float:left; } .ltx_page_header *[rel~="up"], .ltx_page_footer *[rel~="up"] { display:block; text-align:center; } .ltx_page_header *[rel~="next"], .ltx_page_footer *[rel~="next"] { float:right; } /* What was I trying for here; need more selective rule! .ltx_page_header .ltx_ref, .ltx_page_footer .ltx_ref { margin:0 1em; } */ .ltx_page_header li { padding:0.1em 0.2em 0.1em 1em;} /* Main content */ .ltx_page_content { clear:both; } .ltx_page_header { border-bottom:1px solid; margin-bottom:5px; } .ltx_page_footer { clear:both; border-top:1px solid; margin-top:5px; } .ltx_page_header:after, .ltx_page_footer:after, .ltx_page_content:after { content:"."; display:block; height:0; clear:both; visibility:hidden; } .ltx_page_footer:before { content:"."; display:block; height:0; clear:both; visibility:hidden; } .ltx_page_logo { font-size:80%; margin-top: 5px; clear:both; float:right; } .ltx_page_logo a { font-variant: small-caps; } .ltx_page_logo img { vertical-align:-3px; } /* if shown */ .ltx_page_navbar li { white-space:nowrap; display:block; overflow:hidden; } /* If ref got turned into span, it's "this section"*/ .ltx_page_navbar li span.ltx_ref { white-space:normal; overflow:visible; } /* Ought to be easily removable/overridable? */ .ltx_pagination.ltx_role_newpage { height:2em; } /*====================================================================== Document Structure; Titles & Frontmatter */ /* undo bold here to remove the browser's native h# styling, at let all other styles override it (with more specific rules)*/ .ltx_title { font-size:100%; font-weight:normal; } /* Hack to simulate run-in! put class="ltx_runin" on a title or tag for it to run-into the following text. */ .ltx_runin { display:inline; } .ltx_runin:after { content:" "; } .ltx_runin + .ltx_para, .ltx_runin + .ltx_para p, .ltx_runin + p { display:inline; } .ltx_outdent { margin-left: -2em; } /* .ltx_chapter_title, etc should be in ltx-article.css etc. */ .ltx_page_main { margin:0px; padding:1em 3em 1em 2em; } .ltx_tocentry { list-style-type:none; } /* support for common author block layouts.*/ /* add class ltx_authors_1line to get authors in single line with pop-up affiliation, etc. */ .ltx_authors_1line .ltx_creator, .ltx_authors_1line .ltx_author_before, .ltx_authors_1line .ltx_author_after { display:inline;} .ltx_authors_1line .ltx_author_notes { display:inline-block; } .ltx_authors_1line .ltx_author_notes:before { content:"*"; color:blue;} .ltx_authors_1line .ltx_author_notes span { display:none; } .ltx_authors_1line .ltx_author_notes:hover span { display:block; position:absolute; z-index:10; background:white; text-align:left; border: 1px solid black; border-radius: 0 5px 5px 5px; box-shadow: 5px 5px 10px gray; } /* add class=ltx_authors_multiline to get authors & affliations on separate lines*/ .ltx_authors_multiline .ltx_creator, .ltx_authors_multiline .ltx_author_before, .ltx_authors_multiline .ltx_author_after, .ltx_authors_multiline .ltx_author_notes, .ltx_authors_multiline .ltx_author_notes .ltx_contact { display:block; } /*====================================================================== Para level */ .ltx_float { margin: 1ex 3em 1ex 3em; } td.ltx_subfigure, td.ltx_subtable, td.ltx_subfloat { width:50%; } /* theorems, figure, tables, floats captions.. */ /*====================================================================== Blocks, Lists, Floats */ .ltx_p, .ltx_quote, .ltx_block, .ltx_para { display: block; } /* alignment within blocks */ .ltx_align_left { text-align:left; } .ltx_align_right { text-align:right; } .ltx_align_center { text-align:center; } .ltx_align_justify { text-align:justify; } .ltx_align_top { vertical-align:top; } .ltx_align_bottom { vertical-align:bottom; } .ltx_align_middle { vertical-align:middle; } .ltx_align_baseline { vertical-align:baseline; } .ltx_align_floatleft { float:left; } .ltx_align_floatright { float:right; } .ltx_td.ltx_align_left, .ltx_th.ltx_align_left, .ltx_td.ltx_align_right, .ltx_th.ltx_align_right, .ltx_td.ltx_align_center, .ltx_th.ltx_align_center { white-space:nowrap; } .ltx_td.ltx_align_left.ltx_wrap, .ltx_th.ltx_align_left.ltx_wrap, .ltx_td.ltx_align_right.ltx_wrap, .ltx_th.ltx_align_right.ltx_wrap, .ltx_td.ltx_align_center.ltx_wrap, .ltx_th.ltx_align_center.ltx_wrap, .ltx_td.ltx_align_justify, .ltx_th.ltx_align_justify { white-space:normal; } .ltx_tabular .ltx_tabular { width:100%; } .ltx_inline-block { display:inline-block; } /* equations in non-aligned mode (not normally used) */ .ltx_eqn_div { display:block; width:95%; text-align:center; } /* equations in aligned mode (aligning tags, etc as well as equations) */ .ltx_eqn_table { display:table; width:100%; border-collapse:collapse; } .ltx_eqn_row { display:table-row; } .ltx_eqn_cell { display:table-cell; width:auto; } /* Padding between column pairs in ams align */ table.ltx_eqn_align tr.ltx_equation td.ltx_align_left + td.ltx_align_right, table.ltx_eqn_align tr.ltx_equation td.ltx_align_left + td.ltx_align_center, table.ltx_eqn_align tr.ltx_equation td.ltx_align_center + td.ltx_align_right, table.ltx_eqn_align tr.ltx_equation td.ltx_align_center + td.ltx_align_center { padding-left:3em; } table.ltx_eqn_eqnarray tr.ltx_eqn_lefteqn + tr td.ltx_align_right { min-width:2em; } .ltx_eqn_eqno { max-width:0em; overflow:visible; white-space: nowrap; } .ltx_eqn_eqno.ltx_align_right .ltx_tag { float:right; } .ltx_eqn_center_padleft, .ltx_eqn_center_padright { width:50%; min-width:2em;} .ltx_eqn_left_padleft, .ltx_eqn_right_padright { min-width:2em; } .ltx_eqn_left_padright, .ltx_eqn_right_padleft { width:100%; } /* Various lists */ .ltx_itemize, .ltx_enumerate, .ltx_description { display:block; } .ltx_itemize .ltx_item, .ltx_enumerate .ltx_item { display: list-item; } /* Position the tag to look like a normal item bullet. */ li.ltx_item > .ltx_tag { display:inline-block; margin-left:-1.5em; min-width:1.5em; text-align:right; } .ltx_item .ltx_tag + .ltx_para, .ltx_item .ltx_tag + .ltx_para .ltx_p { display:inline; } /* NOTE: Need to try harder to get runin appearance? */ dl.ltx_description dt { margin-right:0.5em; float:left; font-weight:bold; font-size:95%; } dl.ltx_description dd { margin-left:5em; } dl.ltx_description dl.ltx_description dd { margin-left:3em; } /* Theorems */ .ltx_theorem {margin:1em 0em 1em 0em; } .ltx_title_theorem { font-size:100%; } /* Bibliographies */ .ltx_bibliography dt { margin-right:0.5em; float:left; } .ltx_bibliography dd { margin-left:3em; } /*.ltx_biblist { list-style-type:none; }*/ .ltx_bibitem { list-style-type:none; } .ltx_bibitem .ltx_tag { font-weight:bold; margin-left:-2em; width:3em; } /*.bibitem-tag + div { display:inline; }*/ .ltx_bib_title { font-style:italic; } .ltx_bib_article .bib-title { font-style:normal !important; } .ltx_bib_journal { font-style:italic; } .ltx_bib_volume { font-weight:bold; } /* Indices */ .ltx_indexlist li { list-style-type:none; } .ltx_indexlist { margin-left:1em; padding-left:1em;} /* Listings */ .ltx_listing { display:block; margin: 1ex 3em 1ex 0em; overflow-x:auto; text-align: left; } .ltx_float .ltx_listing { margin: 0; } .ltx_listingline { white-space:nowrap; min-height:1em; } .ltx_lst_numbers_left .ltx_listingline .ltx_tag { background-color:transparent; margin-left:-3em; width:2.5em; position:absolute; text-align:right; } .ltx_lst_numbers_right .ltx_listingline .ltx_tag { background-color:transparent; width:2.5em; position:absolute; right:3em; text-align:right; } /* position:absolute; left:0em; max-width:0em; text-align:right; } */ .ltx_parbox {text-indent:0em; } /* NOTE that it is CRITICAL to put position:relative outside & absolute inside!! I wish I understood why! Outer box establishes resulting size, neutralizes any outer positioning, etc; inner establishes position of stuff to be rotated */ .ltx_transformed_outer { position:relative; bottom:0pt;left:0pt; overflow:visible; } .ltx_transformed_inner { display:block; position:absolute;bottom:0pt;left:0pt; } .ltx_transformed_inner > .ltx_p {text-indent:0em; margin:0; padding:0; } /* If simulating a table (html5), try to get rowspan to work...sorta? */ span.ltx_rowspan { position:absolute; top:0; bottom:0; } /* by default, p doesn't indent */ .ltx_p { text-indent:0em; white-space:normal; } /* explicit control of indentation (on ltx_para) */ .ltx_indent > .ltx_p:first-child { text-indent:2em!important; } .ltx_noindent > .ltx_p:first-child { text-indent:0em!important; } /*====================================================================== Columns */ .ltx_page_column1 { width:44%; float:left; } /* IE uses % of wrong container*/ .ltx_page_column2 { width:44%; float:right; } .ltx_page_columns > .ltx_page_column1 { width:48%; float:left; } .ltx_page_columns > .ltx_page_column2 { width:48%; float:right; } .ltx_page_columns:after { content:"."; display:block; height:0; clear:both; visibility:hidden; } /*====================================================================== Borders and such */ .ltx_tabular { display:inline-table; border-collapse:collapse; } .ltx_tabular.ltx_centering { display:table; } .ltx_thead, .ltx_tfoot, .ltx_tbody { display:table-row-group; } .ltx_tr { display:table-row; } .ltx_td, .ltx_th { display:table-cell; } .ltx_framed { border:1px solid black;} .ltx_tabular .ltx_td, .ltx_tabular .ltx_th { padding:0.1em 0.5em; } /* regular lines */ .ltx_border_t { border-top:1px solid black; } .ltx_border_r { border-right:1px solid black; } .ltx_border_b { border-bottom:1px solid black; } .ltx_border_l { border-left:1px solid black; } /* double lines */ .ltx_border_tt { border-top:3px double black; } .ltx_border_rr { border-right:3px double black; } .ltx_border_bb { border-bottom:3px double black; } .ltx_border_ll { border-left:3px double black; } /* Light lines */ .ltx_border_T { border-top:1px solid gray; } .ltx_border_R { border-right:1px solid gray; } .ltx_border_B { border-bottom:1px solid gray; } .ltx_border_L { border-left:1px solid gray; } /* Framing */ .ltx_framed_rectangle { border-style:solid; border-width:1px; } .ltx_framed_top { border-top-style:solid; border-top-width:1px; } .ltx_framed_left { border-left-style:solid; border-left-width:1px; } .ltx_framed_right { border-right-style:solid; border-right-width:1px; } .ltx_framed_bottom, .ltx_framed_underline { border-bottom-style:solid; border-bottom-width:1px; } .ltx_framed_topbottom { border-top-style:solid; border-top-width:1px; border-bottom-style:solid; border-bottom-width:1px; } .ltx_framed_leftright { border-left-style:solid; border-left-width:1px; border-right-style:solid; border-right-width:1px; } /*====================================================================== Misc */ /* .ltx_verbatim*/ .ltx_verbatim { text-align:left; } /*====================================================================== Meta stuff, footnotes */ .ltx_note_content { display:none; } /*right:5%; */ .ltx_note_content { max-width: 70%; font-size:90%; left:15%; text-align:left; background-color: white; padding: 0.5em 1em 0.5em 1.5em; border: 1px solid black; border-radius: 0 5px 5px 5px; box-shadow: 5px 5px 10px gray; } .ltx_note_mark { color:blue; } .ltx_note_type { font-weight: bold; } .ltx_note { display:inline-block; text-indent:0; } /* So we establish containing block */ .ltx_note_content .ltx_note_mark { position:absolute; left:0.2em; top:-0.1em; } .ltx_note:hover .ltx_note_content, .ltx_note .ltx_note_content:hover { display:block; position:absolute; z-index:10; } .ltx_ERROR { color:red; } .ltx_rdf { display:none; } .ltx_missing { color:red;} .ltx_nounicode { color:red; } /*====================================================================== SVG (pgf/tikz ?) basics */ /* Stuff appearing in svg:foreignObject */ .ltx_svg_fog foreignObject { margin:0; padding:0; overflow:visible; } .ltx_svg_fog foreignObject > p { margin:0; padding:0; display:block; } /*.ltx_svg_fog foreignObject > p { margin:0; padding:0; display:block; white-space:nowrap; }*/ /*====================================================================== Low-level Basics */ /* Note that LaTeX(ML)'s font model doesn't map quite exactly to CSS's */ /* Font Families => font-family */ .ltx_font_serif { font-family: serif; } .ltx_font_sansserif { font-family: sans-serif; } .ltx_font_typewriter { font-family: monospace; } /* dingbats should be converted to unicode? */ /* Math font families handled within math: script, symbol, fraktur, blackboard ? */ /* Font Series => font-weight */ .ltx_font_bold { font-weight: bold; } .ltx_font_medium { font-weight: normal; } /* Font Shapes => font-style or font-variant */ .ltx_font_italic { font-style: italic; font-variant:normal; } .ltx_font_upright { font-style: normal; font-variant:normal; } .ltx_font_slanted { font-style: oblique; font-variant:normal; } .ltx_font_smallcaps { font-variant: small-caps; font-style:normal; } .ltx_font_oldstyle { font-variant: oldstyle-nums; /* experimental css3 ? Doesn't seem to work!*/ font-style:normal; -moz-font-feature-settings: "onum"; -ms-font-feature-settings: "onum"; -webkit-font-feature-settings: "onum"; font-variant-numeric: oldstyle-nums; } .ltx_font_mathcaligraphic { font-family: "Lucida Calligraphy", "Zapf Chancery","URW Chancery L"; } /* .ltx_font_mathscript { ? } */ cite { font-style: normal; } .ltx_red { color:red; } /*.ltx_centering { text-align:center; margin:auto; }*/ /*.ltx_inline-block.ltx_centering,*/ /* Hmm.... is this right in general? */ .ltx_centering { display:block; margin:auto; text-align:center; } /* Dubious stuff */ .ltx_hflipped { display:inline-block; -moz-transform: scaleX(-1); -o-transform: scaleX(-1); -webkit-transform: scaleX(-1); transform: scaleX(-1); filter: FlipH; -ms-fliter: "FlipH"; } .ltx_vflipped { display:inline-block; -moz-transform: scaleY(-1); -o-transform: scaleY(-1); -webkit-transform: scaleY(-1); transform: scaleY(-1); filter: FlipV; -ms-fliter: "FlipV"; } /* .ltx_phantom handled in xslt */ /* A somewhat amsart-like style */ .ltx_title_document { text-transform:uppercase; font-size: 150%; text-align:center; } .ltx_title_section { font-family:serif; font-weight:normal; font-variant:small-caps; font-size: 120%; text-align:center; } .ltx_authors { text-align:center; } .ltx_author_before,.ltx_author_after, .ltx_role_author .ltx_personname { text-transform:uppercase; } .ltx_abstract { margin-bottom:1em; } .ltx_title_abstract { font-family:serif; font-weight:normal; font-variant:small-caps;} .ltx_title_keywords, .ltx_title_classification { display:inline; font-size:100%; font-weight:normal; font-style:italic; } .ltx_role_dedicatory { font-size:100%; font-style:italic; text-align:center; margin:1em;} .ltx_figure .ltx_tag, .ltx_table .ltx_tag { font-family:serif; font-variant:small-caps;} .ltx_title_subsection, .ltx_title_subsubsection { font-family:serif; font-weight:bold;} .ltx_title_subsection:after, .ltx_title_subsubsection:after, .ltx_title_paragraph:after { content:"."; } /* abstract, subsection, subsubsection and paragraph titles are runin */ .ltx_abstract .ltx_title, .ltx_abstract .ltx_title + .ltx_p { display:inline; } .ltx_subsection .ltx_title, .ltx_subsection .ltx_title + .ltx_para, .ltx_subsection .ltx_title + .ltx_para > .ltx_p { display:inline; } .ltx_subsubsection .ltx_title, .ltx_subsubsection .ltx_title + .ltx_para, .ltx_subsubsection .ltx_title + .ltx_para > .ltx_p { display:inline; } .ltx_paragraph .ltx_title, .ltx_paragraph .ltx_title + .ltx_para, .ltx_paragraph .ltx_title + .ltx_para > .ltx_p { display:inline; } .ltx_title +.ltx_para > .ltx_p {text-indent:2em; } .ltx_itemize, .ltx_enumerate, .ltx_description { margin-left: clamp(1em, 3%, 2em); } .ltx_title_document { font-size:170%; text-align:center; margin:0.5em 0 0.5em 0; } .ltx_authors, .ltx_role_author { text-align:center; margin:0.5em 0 0.5em 0; } .ltx_role_author .ltx_personname { font-size: 120%; } .ltx_date { text-align:center; font-size: 120%; margin:0.5em 0 0.5em 0; } .ltx_subtitle { text-align:center; font-size: 120%; padding-left:0.2em; margin-left:-0.5em; } .ltx_title_abstract { text-align:center; font-size: 100%; font-weight:bold; } .ltx_abstract { margin-left:4em; margin-right:4em; } .ltx_title_acknowledgements, .ltx_title_keywords, .ltx_title_classification { text-align:left; font-size: 100%; font-weight:bold; margin:0.5 0 0 0; } .ltx_appendix, .ltx_section, .ltx_subsection, .ltx_subsubsection { margin-top:1.5em; } .ltx_paragraph, .ltx_subparagraph { margin-top:1.0em; } .ltx_title_appendix, .ltx_title_section, .ltx_title_bibliography { font-size:140%; font-weight:bold; margin-bottom:1em; } .ltx_title_subsection { font-size:120%; font-weight:bold; margin-bottom:1em; } .ltx_title_subsubsection { font-size:100%; font-weight:bold; margin-bottom:1em; } /* Paragraph & Subparagraph titles should be runin! */ .ltx_title_paragraph { font-size:100%; font-weight:bold; display:inline; margin-right:1em; } .ltx_paragraph .ltx_title, .ltx_paragraph .ltx_title + .ltx_para, .ltx_paragraph .ltx_title + .ltx_para > .ltx_p { display:inline; } .ltx_title_subparagraph { font-size:100%; font-weight:bold; display:inline; margin-left:2em; margin-right:1em; } .ltx_subparagraph .ltx_title, .ltx_subparagraph .ltx_title + .ltx_para, .ltx_subparagraph .ltx_title + .ltx_para > .ltx_p { display:inline; } .ltx_figure { text-align:center; margin:auto; margin:0.5em; } .ltx_table { text-align:center; margin:auto; margin:0.5em; } /* experimental: flex model, to center short captions, justify long ones */ .ltx_table, .ltx_figure { display:flex; flex-direction:column; align-items:center; } .ltx_table .ltx_caption, .ltx_figure .ltx_caption { text-align:justify; } /* first p in para gets indented */ .ltx_para > .ltx_p:first-child { text-indent:2em; } /* except the initial in a section */ section > .ltx_title +.ltx_para > .ltx_p, section > .ltx_title +.ltx_date +.ltx_para > .ltx_p {text-indent:0em; } .ltx_title_abstract + .ltx_p {text-indent:2em; } .ltx_itemize, .ltx_enumerate { margin-left:1em; } .ltx_theorem { margin-top:0.5em; margin-bottom:0.5em; } .ltx_theorem .ltx_title { margin-bottom:0.1em; } .ltx_theorem .ltx_title + .ltx_para, .ltx_theorem .ltx_title + .ltx_para .ltx_p, .ltx_theorem .ltx_title + .ltx_p { margin-top:0em; } Approximation of the Roots of Equations by Aitken-Steffensen-Type Monotonic Sequences(¹)

Approximation of the Roots of Equations by Aitken-Steffensen-Type Monotonic Sequences

I. Păvăloiu

Abstract.

The aim of this paper is to study the conditions under which the well-known Aitken-Steffensen method for solving equations leads to monotonic sequences whose terms approximate (from the left and from the right) the root of an equation. The convergence order and efficiency index of this method are also studied in the general case and then in various particular cases.

- Received: 27 March 1995.

This work has been supported by the Romanian Academy of Sciences.

Romanian Academy of Sciences, ”T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68, 3400 Cluj-Napoca 1, Romania.

1. Introduction

From a practical standpoint, in order to approximate the roots of equations it is advantageous to use methods which lead to monotonic sequences. In this paper we shall use a single iterative process to determine an increasing sequence ${(x_{n})}_{n \geq 0}$ and a decreasing one ${(y_{n})}_{n \geq 0}$ , both converging to a root $\bar{x}$ of the equation $f (x) = 0 .$ Such a procedure has the advantage of allowing, at each iteration step, an approximation error checking, i.e.

\max {\bar{x} - x_{n}, y_{n} - \bar{x}} \leq y_{n} - x_{n} .

As it is well known, such sequences can be generated by applying simultaneously two methods, e.g. Newton’s method and the chord method. In the sequel we shall show that, in conditions similar to those imposed to the above mentioned methods, the Aitken-Steffensen method generates two sequences which fulfil the above inequality.

In Section 2 we give sufficient conditions for the general method of Aitken-Steffensen ((3) below) to generate two monotonic sequences, both converging to the solution $\bar{x}$ of equation (1) below. In this way some similar results obtained in [4] are completed, and the proofs given in [5] are made simpler to a certain extent.

In Section 3 we study some particular cases of the method (3), namely the methods (7) and (9) below. In Section 4 there is indicated a way to construct the auxiliary functions $g_{1}, g_{2,}$ or $g,$ required by (3) or (7), in relatively simple conditions as the monotonicity and convexity of the function $f .$ In Section 5 the convergence orders and the efficiency indices of the methods (3) and (7) are studied, concluding that the method (7) has a higher efficiency index. This one is the same as that of Newton’s method, but is given conditions, the method (7) as well as (3) and (9), provide in addition bilateral approximations for the root of the equation (1).

So, let $I = [a, b], a < b,$ be an interval of the real axis, and consider the equation

(1)

f (x) = 0

where $f : I \to ℝ$ . Besides (1), consider two more equations

(2)		$x - g_{1} (x)$	$= 0,$
	$x - g_{2} (x)$	$= 0,$

where $g_{1}, g_{2} : I \to ℝ$ .

The Aitken-Steffensen method consists in constructing the sequences ${(g_{2} (g_{1} (x_{n})))}_{n \geq 0}$ and ${(g_{1} (x_{n}))}_{n \geq 0}$ by means of the following iterative process

(3)

x_{n + 1} = g_{1} (x_{n}) - \frac{f (g_{1} (x_{n}))}{[g_{1} (x_{n}); g_{2} (g_{1} (x_{n})); f]}, n = 0, 1, \dots, x_{0} \in I,

where $[u, v; f]$ stands for the first order divided difference of $f$ on the points $u, v \in I .$ We shall denote by $[u, v, w; f]$ the second order divided difference of $f$ on $u, v, w \in I .$

As it is well known [6, pp. 268–269], and will also be shown in Section 5, the convergence order of the sequence ${(x_{n})}_{n \geq 0}$ generated by (3) is at least 2, but it generally depends on the convergence orders of the sequences ${(y_{n})}_{n \geq 0}$ and ${(z_{n})}_{n \geq 0}$ generated by $y_{n + 1} = g_{1} (y_{n}), y_{0} \in I; z_{n + 1} = g_{2} (z_{n}),$ $z_{0} \in I; n = 0, 1, \dots,;$ [2], [5].

Another advantage of the iteration method (3) is the following: if equation (1) is given, then (as we shall see in Section 4) we have at our disposal many possibilities to construct the functions $g_{1}$ and $g_{2}$ from equations (2). On the other hand, hypotheses concerning the differentiability of $f$ on the whole interval $I$ are not needed.

If $g : I \to ℝ$ is a function, we shall adopt the following definitions concerning the monotonicity and convexity of $g$ :

Definition 1.1.

The function $g : I \to ℝ$ is said to be increasing (nondecreasing; decreasing; nonincreasing) on $I$ if for every $x, y \in I$ the relations $[x, y; f] > 0 (\geq 0; < 0; \leq 0)$ hold respectively.

Definition 1.2.

The function $g : I \to ℝ$ is convex (nonconcave; concave; nonconvex) on $I$ if for every $x, y, z \in I$ the relations $[x, y, z; f] > 0 (\geq 0; < 0; \leq 0)$ hold respectively.

2. Convergence of the Aitken-Steffensen method

We shall adopt the following hypotheses concerning the functions $f, g_{1}$ and $g_{2};$

(a)

$f, g_{1}, g_{2}$ are continuous on $I;$
(b)

$g_{1}$ is increasing on $I;$
(c)

$g_{2}$ is decreasing on $I;$
(d)

equations (1) and (2) have only one common root $\bar{x} \in] a, b [;$
(e)

for every $x, y \in I,$ the relation $0 < [x, y; g_{1}] \leq 1$ holds.

Concerning the problem stated in Section 1, the following theorem holds:

Theorem 2.1.

Suppose that $f, g_{1}$ and $g_{2}$ fulfil conditions (a)–(e) and, in addition,

(i₁)

$f$ is increasing and convex on $I,$ and there exists $f^{'} (\bar{x});$
(ii₁)

there exists $x_{0} \in I$ such that $f (x_{0}) < 0$ and $g_{2} (g_{1} (x_{0})) \in I .$

Then the sequences ${(x_{n})}_{n \geq 0}$ , ${(g_{1} (x_{n}))}_{n \geq 0},$ ${(g_{2} (g_{1} (x_{n})))}_{n \geq 0}$ generated by (3), where $x_{0}$ fulfils condition (ii₁), have the following properties:

(j₁)

the sequences ${(x_{n})}_{n \geq 0}$ and ${(g_{1} (x_{n}))}_{n \geq 0}$ are increasing and bounded;
(jj₁)

the sequence ${(g_{2} (g_{1} (x_{n})))}_{n \geq 0}$ is decreasing and bounded;
(jjj₁)

$lim x_{n} = lim g_{1} (x_{n}) = lim g_{2} (g_{1} (x_{n})) = \bar{x};$
(jv₁)

$x_{n} \leq g_{1} (x_{n}) \leq x_{n + 1} \leq \bar{x} \leq g_{2} (g_{1} (x_{n})), n = 0, 1, \dots,$

and $\max {\bar{x} - x_{n + 1}, g_{2} (g_{1} (x_{n})) - \bar{x}} \leq g_{2} (g_{1} (x_{n})) - x_{n + 1} .$

Proof.

Since $f$ is increasing on $I$ and $f (x_{0}) < 0,$ it follows that $x_{0} < \bar{x} .$ For $x < y,$ by (e) we get $g_{1} (y) - g_{1} (x) \leq y - x,$ which, for $y = \bar{x},$ leads to $x - g_{1} (x) \leq 0$ if $x < \bar{x}$ and, analogously, $x - g_{1} (x) \geq 0$ if $x > \bar{x} .$ By b) and $x_{0} < \bar{x}$ we obtain $g_{1} (x_{0}) < g_{1} (\bar{x}),$ i.e. $g_{1} (x_{0}) < \bar{x},$ while from the above inequalities it follows $x_{0} \leq g_{1} (x_{0}) .$ By (c) and g ${}_{1}{(x_{0})} < \bar{x}$ we get $g_{2} (g_{1} (x_{0})) > g_{2} (\bar{x}),$ that is, $g_{2} (g_{1} (x_{0})) > \bar{x} .$ By (i₁) and $g_{1} (x_{0}) < \bar{x}$ we obtain $f (g_{1} (x_{0})) < 0$ which, together with $[g_{1} (x_{0}), g_{2} (g_{1} (x_{0})); f] > 0$ and (3), shows that $x_{1} > g_{1} (x_{0}) .$

It is easy to see that the following identities

(4)

g_{1} (x) - \frac{f (g_{1} (x))}{[g_{1} (x), g_{2} (g_{1} (x)); f]} = g_{2} (g_{1} (x)) - \frac{f (g_{2} (g_{1} (x)))}{[g_{1} (x), g_{2} (g_{1} (x)); f]}

(5)

f (z) = f (x) + [x, y; f] (z - x) + [x, y, z; f] (z - x) (z - y,)

hold for every $x, y, z \in I .$

Since $g_{2} (g_{1} (x_{0})) > \bar{x},$ it follows that $f (g_{2} (g_{1} (x_{0}))) > 0$ and, using (4) and (3), we get $x_{1} < g_{2} (g_{1} (x_{0})) .$ If we put in (5) $z = x_{1}, x = g_{1} (x_{0}), y = g_{2} (g_{1} (x_{0})),$ and take into account (3), we get

f (x_{1}) = [g_{1} (x_{0}), g_{2} (g_{1} (x_{0})), x_{1}; f] (x_{1} - g_{1} (x_{0})) (x_{1} - g_{2} (g_{1} (x_{0}))),

from which, considering the convexity of $f$ and the inequalities $x_{1} - g_{1} (x_{0}) > 0$ and $x_{1} - g_{2} (g_{1} (x_{0})) < 0,$ one obtains $f (x_{1}) < 0,$ that is, $x_{1} < \bar{x} .$

In this way we have obtained

(2.2^′)

x_{0} \leq g_{1} (x_{0}) < x_{1} < \bar{x} < g_{2} (g_{1} (x_{0})) .

In order that the above reasoning may be repeated we still have to show that $x_{1}$ verifies the last condition of (ii₁), namely $g_{2} (g_{1} (x_{1})) \in I .$ Indeed, from $x_{0} < x_{1}$ and (b) it follows $g_{1} (x_{0}) < g_{1} (x_{1}),$ which, by (c), leads to $g_{2} (g_{1} (x_{0})) > g_{2} (g_{1} (x_{1})) .$ It remains to show that $g_{2} (g_{1} (x_{0})) > \bar{x} .$ Suppose that $g_{2} (g_{1} (x_{0})) \leq \bar{x},$ that is, $g_{2} (g_{1} (x_{0})) \leq g_{2} (\bar{x}),$ implying $g_{1} (x_{0}) \geq \bar{x},$ which contradicts (2.2^′).

Consider $x_{n} \in I$ for which $f (x_{n}) < 0$ and $g_{2} (g_{1} (x_{n})) \in I, n \in ℕ$ . Repeating the above reasoning, we obtain the inequalities

(6)

x_{n} \leq g_{1} (x_{n}) < x_{n + 1} < \bar{x} < g_{2} (g_{1} (x_{n})), n = 0, 1, \dots,

In this way conclusions (j₁), (jj₁) and (jv₁) of Theorem 2.1 are proved. To prove (jjj₁), denote $l = lim x_{n},$ $l_{1} = lim g_{1} (x_{n}), l_{2} = lim g_{2} (g_{1} (x_{n})) .$ We shall show that $l = l_{1} = l_{2} = \bar{x} .$

By (6) and (a), we deduce:

l \leq g_{1} (l) \leq l \leq \bar{x} \leq g_{2} (g_{1} (l));

but $l_{1} = g_{1} (l),$ therefore $l = l_{1}$ ; i.e. $g_{1} (l) = l .$ From this relation and (3), using the fact that there exists $f^{'} (\bar{x})$ and $f$ is increasing, we get $f (l) = 0,$ that is, $l = \bar{x} .$ Since $l_{2} = g_{2} (l) \geq \bar{x}$ , it follows $f (g_{2} (l)) \geq 0,$ while form (4) it follows that $l \geq g_{2} (l),$ which, together with $l \leq g_{2} (l),$ leads to $l = g_{2} (l) = \bar{x} .$ ∎

In can be shown analogously that the following theorems hold, too:

Theorem 2.2.

Suppose that $f, g_{1}, g_{2}$ fulfil conditions (a)–(e), and in addition

(i₂)

$f$ is increasing and concave on $I,$ and there exists $f^{'} (\bar{x});$
(ii₂)

there exists $x_{0} \in I$ for which $f (x_{0}) > 0$ and $g_{2} (g_{1} (x_{0})) \in I .$

Then the sequences ${(x_{n})}_{n \geq 0}, {(g_{1} (x_{n}))}_{n \geq 0},$ $g_{2} {(g_{1} (x_{n}))}_{n \geq 0}$ generated by (3), have the following properties:

(j₂)

${(x_{n})}_{n \leq 0}, {(g_{1} (x_{n}))}_{n \geq 0}$ are decreasing and bounded;
(jj₂)

${(g_{2} (g_{1} (x_{n})))}_{n \geq 0}$ is increasing and bounded;
(jjj₂)

$lim x_{n} = lim g_{1} (x_{n}) = lim g_{2} (g_{1} (x_{n})) = \bar{x},$ and the following relations hold

$g_{2} (g_{1} (x_{n})) < \bar{x} < x_{n + 1} < g_{1} (x_{n}) \leq x_{n}, n = 0, 1, \dots,$

$\max {\bar{x} - g_{2} (g_{1} (x_{n})), x_{n + 1} - \bar{x}} \leq x_{n + 1} - g_{2} (g_{1} (x_{n})) .$

Theorem 2.3.

Suppose that $f, g_{1}, g_{2}$ fulfil conditions (a)–(e) and in addition

(i₃)

$f$ is decreasing and convex on $I,$ and there exists $f^{'} (\bar{x});$
(ii₃)

there exists $x_{0} \in I$ for which $f (x_{0}) < 0$ and $g_{2} (g_{1} (x_{0})) \in I .$

Then the sequences ${(x_{n})}_{n \geq 0},$ ${(g_{1} (x_{n}))}_{n \geq 0}, {(g_{2} (g_{1} (x_{n})))}_{n \geq 0}$ generated by (3) fulfil the conclusions of Theorem 2.2.

Theorem 2.4.

Suppose that $f, g_{1}, g_{2}$ fulfil conditions (a)–(e) and in addition

(i₄)

$f$ is decreasing and concave on $I,$ and there exists $f^{'} (\bar{x});$
(ii₄)

there exists $x_{0} \in I$ for which $f (x_{0}) > 0$ and $g_{2} (g_{1} (x_{0})) \in I .$

Then the sequences ${(x_{n})}_{n \geq 0}, {(g_{1} (x_{n}))}_{n \geq 0}, {(g_{2} (g_{1} (x_{n})))}_{n \geq 0}$ generated by (3), fulfil the conclusions of Theorem 2.1.

3. Particular cases

An interesting particular case of the procedure (3) is obtained taking

$g_{1} (x) = x$ for every $x \in I .$ In this way one obtains Steffensen’s method, namely

(7)

x_{n + 1} = x_{n} - \frac{f (x_{n})}{[x_{n}, g (x_{n}); f]}, n = 0, 1, \dots, x_{0} \in I,

where $g$ stands for $g_{2} .$

One observes easily that in this case hypotheses (a), (b), (d) and (e) are automatically fulfilled by $g_{1} .$ For the study of the convergence of the sequence ${(x_{n})}_{n \geq 0}$ generated by (7), we have to adopt the following hypotheses:

(a₁)

the functions $f$ and $g$ are continuous on $I;$
(b₁)

the function $g$ is decreasing on $I;$
(c₁)

equations (1) and $x = g (x)$ have only one common root $\bar{x} \in] a, b [.$

With these specifications, the theorems stated in Section 2 yield:

Corollary 3.1.

Suppose that $f$ and $g$ fulfil conditions (a₁)–(c₁) and in addition $f$ is increasing and convex on $I;$ there exists $f^{'} (\bar{x}),$ and the initial point $x_{0}$ in (7) can be chosen such that $f (x_{0}) < 0$ and $g (x_{0}) \in I .$ Then the sequence ${(x_{n})}_{n \geq 0}$ is increasing and bounded, while the sequence ${(g (x_{n}))}_{n \geq 0}$ is decreasing and bounded. Moreover, the relations $\bar{x} = lim x_{n} = lim g (x_{n})$ and

	$x_{n}$	$\leq \bar{x} \leq g (x_{n});$
	$\max {\bar{x} - x_{n}, g (x_{n}) - \bar{x}}$	$\leq g (x_{n}) - x_{n}$

hold.

Corollary 3.2.

Suppose that $f$ and $g$ fulfil conditions (a₁)–(c₁) and in addition $f$ is increasing and concave on $I;$ there exists $f^{'} (\bar{x}),$ and $x_{0}$ from (7) can be chosen such that $f (x_{0}) > 0$ and $g (x_{0}) \in I .$ Then ${(x_{n})}_{n \geq 0}$ is decreasing and bounded, while ${(g (x_{n}))}_{n \geq 0}$ is increasing and bounded. Moreover, the following

relations: $\bar{x} = lim x_{n} = lim g (x_{n})$ and

	$g (x_{n})$	$\leq \bar{x} \leq x_{n};$
	$\max {\bar{x} - g (x_{n}), x_{n} - \bar{x}}$	$\leq x_{n} - g (x_{n})$

hold.

Corollary 3.3.

Suppose that $f$ and $g$ fulfil conditions (a₁)–(c₁) and in addition $f$ is decreasing and convex on $I;$ there exists $f^{'} (\bar{x}),$ and $x_{0}$ from (7) can be chosen such that $f (x_{0}) < 0$ and $g (x_{0}) \in I .$ Then ${(x_{n})}_{n \geq 0}$ and ${(g (x_{n}))}_{n \geq 0}$ verify the conclusions of Corollary 3.2.

Corollary 3.4.

Suppose that $f$ and $g$ fulfil conditions (a₁)–(c₁) and in addition $f$ is decreasing and concave on $I,$ there exists $f^{'} (\bar{x})$ and $x_{0}$ from (7) can be chosen such that $f (x_{0}) > 0$ and $g (x_{0}) \in I .$ Then ${(x_{n})}_{n \geq 0}$ and ${(g (x_{n}))}_{n \geq 0}$ verify the conclusions of Corollary 3.1.

Another interesting particular case is that in which $f$ has the form:

(8)

f (x) = x - g (x) = 0 .

In this case the iterative method (7) will have the form

(9)

x_{n + 1} = x_{n} - \frac{{(x_{n} - g (x_{n}))}^{2}}{g (g (x_{n})) - 2 g (x_{n}) + x_{n}}, n = 0, 1, \dots, x_{0} \in I,

whose convergence follows easily by Corollaries 3.1–3.4. The following results simplify the conditions imposed to $g$ and $x_{0}$ in [1]:

Corollary 3.5.

Suppose that $g$ is continuous, decreasing and convex on $I;$ equation (8) has a root $\bar{x} \in] a, b [,$ there exists $g^{'} (\bar{x}),$ and $x_{0} \in I$ can be chosen such that $x_{0} < g (x_{0})$ and $g (x_{0}) \in I .$ Then the sequences ${(x_{n})}_{n \geq 0}$ and ${(g (x_{n}))}_{n \geq 0}$ verify the conclusions of Corollary 3.1.

Corollary 3.6.

Suppose that $g$ is continuous, decreasing and concave on $I,$ equation (8) has a root $\bar{x} \in] a, b [,$ there exists $g^{'} (\bar{x}),$ and $x_{0} \in I$ can be chosen such

that $x_{0} > g (x_{0})$ and $g (x_{0}) \in I .$ Then the sequences ${(x_{n})}_{n \geq 0}$ and ${(g (x_{n}))}_{n \geq 0}$ verify the conclusions of Corollary 3.2.

The restriction imposed to $f$ in Corollaries 3.3 and 3.4 ( $f$ to be decreasing) can no more be reached in this case, because in those corollaries the condition on $g$ to be decreasing is essential, and is easy to see that if $g$ decreases the $f$ is increasing.

4. Determination of auxiliary functions

In what follows we shall show that, under reasonable hypotheses concerning the monotonicity and convexity of $f,$ we have at our disposal various ways to choose $g_{1}, g_{2}$ and $g$ such that the hypotheses of the theorems and corollaries stated above are verified.

1. Let us admit that $f : [a, b] \to ℝ$ is differentiable on $[a, b],$ and denote by $f^{'} (a)$ the right-hand derivative in a and by $f' (b)$ the left-hand derivative in $b;$ we also admit that $f$ is increasing and convex on $[a, b] .$ Suppose that the equation $f (x) = 0$ has a root $\bar{x} \in] a, b [.$ Then we choose $g_{1} (x) = x - f (x) / f^{'} (b)$ and $g_{2} (x) = x - f (x) / f^{'} (a) .$

Since $f$ is convex, if follows that $f^{'}$ is increasing on $[a, b],$ hence $0 < f^{'} (a) < f^{'} (x) < f^{'} (b)$ for every $x \in] a, b [.$ In this case we have $g_{1}^{'} (x) = 1 - f^{'} (x) / f^{'} (b) > 0$ for every $x \in] a, b [$ and $g_{2}^{'} (x) = 1 - f^{'} (x) / f^{'} (a) < 0$ for every $x \in] a, b [.$ We choose then a subinterval $[α, β] \subset] a, b [$ for which $\bar{x} \in [α, β] .$ If we suppose in addition that there exists $x_{0} \in [α, β]$ for which $f (x_{0}) < 0$ and $g_{2} (g_{1} (x_{0})) \in [α, β]$ then the above constructed functions $f, g_{1}$ and $g_{2}$ verify the hypotheses of Theorem 2.1. It is easy to see that if we choose $g_{1} (x) = x - λ_{1} f (x)$ and $g_{2} (x) = x - λ_{2} f (x),$ with $λ_{1},$ $λ_{2} \in ℝ$ , $λ_{1} > f^{'} (b)$ and $0 < λ_{2} < f^{'} (a),$ then $g_{1}$ and $g_{2}$ also verify the hypotheses of Theorem 2.1.

2. If $f$ is differentiable, decreasing and convex on $[a, b],$ then $g_{1}$ and $g_{2}$ can be chosen as in case $1 .$ If there exists $x_{0} \in [α, β]$ such that $f (x_{0}) < 0$ and $g_{2} (g_{1} (x_{0})) \in [α, β],$ then the hypotheses of Theorem 2.3 are verified.

3. If $f$ is differentiable, decreasing and concave on $[a, b],$ then we may put $g_{1} (x) = x - f (x) / f^{'} (a)$ and $g_{2} (x) = x - f (x) / f^{'} (b) .$ If there exists $x_{0} \in [α, β]$ for which $f (x_{0}) > 0$ and $g_{2} (g_{1} (x_{0})) \in [α, β],$ then $f, g_{1}$ and $g_{2}$ fulfil the conditions of Theorem 2.4.

4. If $f$ is differentiable, increasing and concave on $[a, b],$ then $g_{1}$ and $g_{2}$ can be chosen as in case 3. If there exists $x_{0} \in [α, β]$ such that $f (x_{0}) > 0$ and $g_{2} (g_{1} (x_{0})) \in I,$ then $f, g_{1}$ and $g_{2}$ verify the hypotheses of Theorem 2.2.

5. The function $g$ appearing in Section 3, Procedure (7) can be chosen in the following ways:

a) If $f$ is differentiable, increasing and convex on $[a, b],$ then we can choose $g (x) = x - f (x) / f^{'} (a),$ and if $x_{0}$ verifies $f (x_{0}) < 0$ and $g (x_{0}) \in [α, β],$ then the hypotheses of Corollary 3.1 are verified; while if $f$ is decreasing and convex and there exists $x_{0} \in [α, β]$ for which $f (x_{0}) < 0$ and $g (x_{0}) \in [α, β],$ the hypotheses of Corollary 3.3 are verified.

b) If $f$ is differentiable, decreasing and concave on $[a, b],$ we choose $g (x) = x - f (x) / f^{'} (b) .$ If there exists $x_{0} \in [α, β]$ such that $f (x_{0}) > 0$ and $g (x_{0}) \in [α, β],$ then the hypotheses of Corollary 3.4 are verified; while if $f$ is increasing and concave and there exists $x_{0} \in [a, b]$ such that $f (x_{0}) > 0$ and $g (x_{0}) \in [α, β],$ the hypotheses of Corollary 3.2 are verified.

5. Convergence order and efficiency index

To fix the ideas, we shall consider hereafter, besides (1), another equation, equivalent to (1), of the form

(10)

x - h (x) = 0

where $h : I \to ℝ$ . We shall also consider a sequence ${(x_{n})}_{n \geq 0},$ $x_{n} \in I,$ which, together with $h$ and $f,$ verifies the properties:

(a)

$h (x_{n}) \in I$ for every $n \in ℕ$ ;
(b)

${(x_{n})}_{n \geq 0}$ and ${(h (x_{n}))}_{n \geq 0}$ are convergent and $lim x_{n} = lim h (x_{n}) = \bar{x},$ where $\bar{x}$ is the root of equation (1);
(c)

$[x, y; f] \neq 0$ for every $x, y \in I;$
(d)

$f$ is differentiable at $x = \bar{x} .$

We shall adopt the following definition of the convergence order of the sequence ${(x_{n})}_{n \geq 0} :$

Definition 5.1.

The sequence ${(x_{n})}_{n \geq 0}$ is said to have the convergence order $p \in ℝ$ with respect to $h$ if there exists

(11)

α = lim \frac{\ln | h (x_{n}) - \bar{x} |}{\ln | x_{n} - \bar{x} |}

and $α = p .$

If $x_{n + 1} = h (x_{n}), n = 0, 1, \dots,$ the above definition reduces to the usual one [2], [3].

The following theorem holds:

Theorem 5.1.

If $h$ and $f$ and ${(x_{n})}_{n \geq 0}$ verify the properties (a)–(d), then the necessary and sufficient condition for ${(x_{n})}_{n \geq 0}$ to have the convergence order $p \in ℝ$ , $p > 0,$ with respect to $h$ is to exist

(12)

β = lim \frac{\ln | f (h (x_{n})) |}{\ln | f (x_{0}) |}

and $β = p .$

Proof.

Supposing (11) or (12) to be true and taking into account (a)–(d), it follows

	$lim \frac{\ln \| h (x_{n}) - \bar{x} \|}{\ln \| x_{n} - \bar{x} \|}$	$= lim \frac{\ln \| f (h (x_{n})) \| - \ln \| [h (x_{n}), \bar{x}; f] \|}{\ln \| f (x_{n}) \| - \ln \| x_{n}, \bar{x}; f \|}$
		$= lim \frac{\ln \| f (h (x_{n})) \|}{\ln \| f (x_{n}) \|} \cdot \frac{1 - \frac{\ln \| [h (x_{n}), \bar{x}; f] \|}{\ln \| f (h (x_{n})) \|}}{1 - \frac{\ln \| [x_{n}, \bar{x}; f] \|}{\ln \| f (x_{n}) \|}} = lim \frac{\ln \| f (h (x_{n})) \|}{\ln \| f (x_{n}) \|} .$

The equality of these two limits proves the validity of the theorem. ∎

Consider now the functions $g_{1}, g_{2}$ appearing in equations (2) and let the function $h$ be given by

(13)

h (x) = g_{1} (x) - \frac{f (g_{1} (x))}{[g_{1} (x), g_{2} (g_{1} (x)); f]} .

Concerning the convergence order of the sequence ${(x_{n})}_{n \geq 0}$ generated by (3), the following theorem holds:

Theorem 5.2.

Suppose that the functions $f, g_{1}$ and $g_{2}$ and the initial point $x_{0}$ fulfil the conditions of Theorem 2.1. If there exists $f^{''} (\bar{x})$ and in addition the sequence ${(x_{n})}_{n \geq 0}$ has the convergence order $p_{1}$ with respect to $g_{1},$ while ${(g_{1} (x_{n}))}_{n \geq 0}$ has the convergence order $p_{2}$ with respect to $g_{2},$ then the sequence ${(x_{n})}_{n \geq 0}$ has the convergence order $p_{1} (p_{2} + 1)$ with respect to the function $h$ given by (13).

Proof.

At first observe that, under the stated hypotheses, we may use (12) to determine the convergence order. The same hypotheses also lead to

(14)

lim \frac{\ln | f (g_{1} (x_{n})) |}{\ln | f (x_{n}) |} = p_{1};

(15)

lim \frac{\ln | f (g_{2} (g_{1} (x_{n}))) |}{\ln | f (g_{1} (x_{n})) |} = p_{2} .

Using (4), (5) and the procedure (3), we obtain

f (x_{n + 1}) = [g_{1} (x_{n}), g_{2} (g_{1} (x_{n})), x_{n + 1}; f] \frac{f (g_{1} (x_{n})) \cdot f (g_{2} (g_{1} (x_{n})))}{{[g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f]}^{2}},

from which, by (14) and (15), it follows easily the equality

lim \frac{\ln | f (h (x_{n})) |}{\ln | f (x_{n}) |} = p_{1} (1 + p_{2}) .

∎

Remark 5.1.

Theorem 5.2 remains valid if the hypotheses of Theorem 2.1 are replaced by those of Theorems 2.2, 2.3, or 2.4.

An analogous theorem holds in the case of the procedure (3), too.

Theorem 5.3.

If $f$ and $g$ verify the hypotheses of Corollary 3.1, if there exists $f^{''} (\bar{x}),$ and in addition the sequence ${(x_{n})}_{n \geq 0}$ generated by (7) has the convergence order $p$ with respect to $g,$ then this sequence has the convergence order $p + 1$ with respect to the function $h$ given by

h (x) = x - \frac{f (x)}{[x, g (x); f]} .

Remark 5.2.

Theorem 5.3 remains valid if the hypotheses of Corollary 3.1 are replaced by those of Corollaries 3.2, 3.3, or 3.4.

Remark 5.3.

Returning to the functions $g_{1}$ and $g_{2}$ determined in Section 4, $(g_{1} = x - f (x) / A, g_{2} = x - f (x) / B,$ where $A = f^{'} (b), B = f^{'} (a),$ or $A = f^{'} (a), B = f^{'} (b)$ , according to the case under consideration), it is easy to see

that the convergence order of the sequence generated by (3) is equal to $2$ .

In the case of the procedure (7), for $g (x) = x - f (x) / A$ or $g (x) = x - f (x) / B$ (according to the considered situation), the convergence order is also equal to $2$ .

In the sequel we shall deal with the efficiency index of the iterative procedures studied along the previous sections.

According to A. M. Ostrowski’s [3] definition for the efficiency index of an iterative procedure, and taking into account Theorems 5.1, 5.2 or 5.3 for the iterative procedures (3), (7), or (9), the efficiency index is expressed as

E = p^{1 / m}

Here $p$ is the convergence order of the sequence generated by one of these procedures, while $m$ stands for the number of values of functions to be computed at each iteration step.

Taking into consideration Remark 5.3, it follows that, choosing $g_{1}, g_{2},$ or $g$ as in Section 4, the efficiency index of the procedure (7) is $E = \sqrt[3]{2},$ while that of (9) is $E = \sqrt{2} .$

From this standpoint, the procedure (7) has the efficiency index equal to that of Newton’s method.

In the conditions of Theorem 5.2 for the generalized procedure of Aitken-Steffensen (3), the efficiency index is given by $E = \sqrt[4]{p_{1} (p_{2} + 1)} .$ Analogously, in the conditions of Theorem 5.3, the efficiency index of the method (7) is $E = \sqrt[3]{p + 1} .$

6. Numerical examples

1. Consider the equation

f (x) := x - 2 \arctan x = 0,

for $x \in [\frac{3}{2}, 3] .$ Since $f$ is increasing and convex on $[\frac{3}{2}, 3],$ we can choose $g_{1}$ and $g_{2}$ as in the case 1 (Section 4). We obtain

	$g_{1} (x)$	$= \frac{1}{4} (10 \arctan x - x);$
	$g_{2} (x)$	$= \frac{1}{5} (26 \arctan x - 8 x) .$

Taking $x_{0} = \frac{3}{2},$ the functions $f, g_{1}$ and $g_{2}$ verify the hypotheses of Theorem 2.1 on the interval $[\frac{3}{2}, 3] .$ Applying the procedure (3), we get the following results:

$n$	$x_{n}$	$g_{1} (x_{n})$	$g_{2} (g_{1} (x_{n}))$	$f (x_{n})$
0	1.50000000000000	2.08198430811832	2.50854785469606	-4.6 $\cdot$ 10^-01
1	2.32357265230323	2.33006829103803	2.33195667567199	-5.1 $\cdot$ 10^-03
2	2.33112222668589	2.33112235050042	2.33112238618252	-9.9 $\cdot$ 10^-08
3	2.33112237041442	2.33112237041442	2.33112238041442	-3.5 $\cdot$ 10^-17

2. Consider the equation

f (x) := x - \arcsin \frac{x - 1}{\sqrt{2 (x^{2} + 1)}} = 0,

for $x \in [- 2, - 1] .$ Observe that $f$ is differentiable on $[- 2, - 1],$ and the derivative of $f$ from the left on $x = - 1$ is $\frac{3}{2} .$ The function $f$ is increasing and convex on $[- 2, - 1],$ and we may take $g (x) = \frac{1}{6} (x + 5 \arcsin \frac{x - 1}{\sqrt{2 (x^{2} + 1)}}) .$ An elementary calculation shows that $f (- 2) < 0$ and $g (- 2) \in [- 2, - 1]$ ; and therefore the hypotheses of Corollary 3.1 are verified. The procedure (7) leads to the following results:

$n$	$x_{n}$	$g (x_{n})$	$f (x_{n})$
0	-2.000000000000000	-1.37420481033188	-7.853 981 633 974 48 $\cdot$ 10^-01
1	-1.406051288716128	-1.40401615840899	-7.509 542 276 017 46 $\cdot$ 10^-01
2	-1.404223647476550	-1.40422359726392	-2.442 156 368 565 04 $\cdot$ 10^-03
3	-1.404223602391970	-1.40422360239197	-6.025 515 505 460 58 $\cdot$ 10^-08
4	-1.404223602391970	-1.40422360239197	-3.718 813 451 625 28 $\cdot$ 10^-17

References

[1] M. Balázs, ^†^†margin: available soon,
$\leftarrow$ refresh and click here A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., (21), 2 (1992), 111–117.
[2] V. Casulli, D. Trigiante, The convergence order for iterative multipoint procedures, Calcolo, (13), 1 (1977), 25–44.
[3] A. M. Ostrowski, Solution of Equations and Systems of Equations, (1960), Academic Press, New York and London.
[4] ^†^†margin: $\leftarrow$ clickable I. Păvăloiu, On the monotonicity of the sequences of approximations obtained by Steffensen’s method, Mathematica (Cluj), (35), (58), 1 (1993), 71–76.
[5] ^†^†margin: $\leftarrow$ clickable I. Păvăloiu, Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., (23), 1 (1994), 95–100.
[6] F. J. Traub, Iterative Methods for the Solution of Equations, (1964), Prentice-Hall, Inc. Englewood Cliffs, N.J.

1995

On the Legendre transform and its applications

October 16, 2024

On irreversibility and turbulence

November 26, 2018

Existence results for nonlinear boundary value problems under nonresonance conditions

May 18, 2022

Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Approximation of the Roots of Equations by Aitken-Steffensen-Type Monotonic Sequences

Abstract.

1. Introduction

Definition 1.1.

Definition 1.2.

2. Convergence of the Aitken-Steffensen method

Theorem 2.1.

Proof.

Theorem 2.2.

Theorem 2.3.

Theorem 2.4.

3. Particular cases

Corollary 3.1.

Corollary 3.2.

Corollary 3.3.

Corollary 3.4.

Corollary 3.5.

Corollary 3.6.

4. Determination of auxiliary functions

5. Convergence order and efficiency index

Definition 5.1.

Theorem 5.1.

Proof.

Theorem 5.2.

Proof.

Remark 5.1.

Theorem 5.3.

Remark 5.2.

Remark 5.3.

6. Numerical examples

References

Related Posts