Local convergence of general Steffensen type methods

9 years ago

Abstract

We study the local convergence of a generalized Steffensen method. We show that this method substantially improves the convergence order of the classical Steffensen method. The convergence order of our method is greater or equal to the number of the controlled nodes used in the Lagrange-type inverse interpolation, which, in its turn, is substantially higher than the convergence orders of the Lagrange type inverse interpolation with uncontrolled nodes (since their convergence order is at most (2)).

Author

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

Keywords

nonlinear equations in R; Steffensen method.

PDF

PDF file (on the journal website).

Cite this paper as:

I. Păvăloiu, Local convergence of general Steffensen type methods, Rev. Anal. Numér. Théor. Approx., 33 (2004) 1, pp. 79-86. https://doi.org/10.33993/jnaat331-762

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] Balazs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Num ́er. Theor. Approx., 21 , no. 2, pp. 111–117, 1992.

[2] Brent, R., Winograd, S. and Walfe, Ph., Optimal iterative processes for root-finding, Numer. Math., 20 , no. 5, pp. 327–341, 1973.

[3] Coman, C., Some practical approximation methods for nonlinear equations, Mathematica – Rev. Anal. Num ́er. Theor. Approx., 11, nos. 1–2, pp. 41–48, 1982.

[4] Cassulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25–44, 1977.

[5] Iancu, C., Pavaloiu, I. and Serb, I., Methodes iteratives optimales de type Steffensen obtinues par interpolation inverse , Faculty of Mathematics, “Babes-Bolyai” University, Seminar on Functional analysis and Numerical Methods, Preprint no.1, pp. 81–88, 1983.

[6] Kacewicz, B., An integral-interpolation iterative method for the solution of scalar equations, Numer. Math., 26 , no. 4, pp. 355–365, 1976.

[7] Ostrowski, A., Solution of Equations in Euclidian and Banach Spaces, Academic Press, New York and London, 1973.

[8] Pavaloiu, I., La resolution des equations par interpolation, Mathematica, 23(46), no. 1, pp. 61–72, 1981.

[9] Pavaloiu, I. and Serb, I., Sur des methodes de type interpolatoire `a vitesse de convergence optimale, Rev. Anal. Numer. Theor. Approx., 12 , no. 1, pp. 83–88, 1983.

[10] Pavaloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 5 , no. 1 (13), pp. 20–43, 1997.

[11] Traub, J. F., Iterative Methods for the Solution of Equations, Pretince-Hall, Inc. Englewood Clifs, N.J., 1964.

[12] Turowicz, A. B., Sur les deriv ́ees d’ordre superieur d’une fonction inverse, Ann. Polon. Math., 8, pp. 265–269, 1960

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; } Local convergence of general Steffensen type methods∗

Local convergence
of general Steffensen type methods^∗

Ion Păvăloiu^†

(Date: January 21, 2004)

Abstract.

We study the local convergence of a generalized Steffensen method. We show that this method substantially improves the convergence order of the classical Steffensen method. The convergence order of our method is greater or equal to the number of the controlled nodes used in the Lagrange-type inverse interpolation, which, in its turn, is substantial higher than the convergence orders of the Lagrange type inverse interpolation with uncontrolled nodes (since their convergence order is at most $2$ ).

^∗This work has been supported by the Romanian Academy under grant GAR 16/2004.

^†“T. Popoviciu” Institute of Numerical Analysis, O.P. 1, C.P. 68, Cluj-Napoca, Romania, e-mail: pavaloiu@ictp.acad.ro.

{amssubject}

65H05.

{keyword}

Nonlinear scalar equations, Steffensen type method.

1. Introduction

In this paper we study the local convergence of some general methods of Aitken-Steffensen type, which are based on inverse interpolation of Lagrange type.

Let $f : [a, b] \to ℝ$ , $a, b \in ℝ$ , $a < b$ be a function and $x_{i}$ , $i = \bar{0, n}$ , $n + 1$ distinct points in $[a, b]$ , which we call interpolation nodes. Denote $y_{i} = f (x_{i})$ , $i = \bar{0, n}$ , and suppose that $y_{i} \neq y_{j}$ for $i \neq j$ . Assume in the beginning that $f : I \to f (I)$ , $I = [a, b]$ is one-to-one, i.e., there exists $f^{- 1} : f (I) \to I$ . Consider the Lagrange polynomial with the interpolation nodes $y_{i}$ , $i = \bar{0, n}$ and the values of $f^{- 1}$ on these nodes $x_{i} = f^{- 1} (y_{i})$ , $i = \bar{0, n}$ . This is the inverse interpolation polynomial, which we denote by $L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} | y)$ , and it can be represented in the Lagrange form

(1)

L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} | y) = \sum_{i = 0}^{n} \frac{x_{i} ω (y)}{(y - y_{i}) ω^{'} (y_{i})}, ω (y) = \prod_{i = 0}^{n} (y - y_{i})

and in the Newton form:

(2)	$L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} \| y) =$	$x_{0} + [y_{0}, y_{1}; f^{- 1}] (y - y_{0})$
	$+ [y_{0}, y_{1}, y_{2}; f^{- 1}] (y - y_{0}) (y - y_{1}) + \dots$
	$+ [y_{0}, y_{1}, \dots, y_{n}; f^{- 1}] (y - y_{0}) (y - y_{1}) \dots (y - y_{n - 1}),$

where $[y_{0}, \dots, y_{i}; f^{- 1}], i = \bar{1, n}$ denotes the $i$ -th order divided difference of the function $f^{- 1}$ on the nodes $y_{0}, \dots, y_{i}$ .

Assuming that $f$ admits derivatives up to the order $n + 1$ on the interval $[a, b]$ , then

(3)

f^{- 1} (y) = L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} | y) + \frac{{[f^{- 1} (ξ)]}^{(n + 1)}}{(n + 1)!} ω (y)

where $ξ$ is a point belonging to the smallest interval containing $y, y_{0}, \dots, y_{n}$ . Denote

R_{n} [f^{- 1}; y] = \frac{{[f^{- 1} (ξ)]}^{(n + 1)}}{(n + 1)!} ω (y) .

Consider now the equation

(4)

f (x) = 0 .

If it has a solution $\bar{x} \in [a, b]$ , then obviously

(5)

\bar{x} = f^{- 1} (0) .

An approximation of the solution $\bar{x}$ can be obtained from (3) for $y = 0$ , i.e.,

(6)

\bar{x} = L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} | 0) + R_{n} [f^{- 1}; 0],

whence, by neglecting the remainder $R_{n} [f^{- 1}, 0]$ we get

(7)

x_{n + 1} = L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} | 0),

and the error

(8)

\bar{x} - x_{n + 1} = R_{n} [f^{- 1}; 0] .

Denoting $M = sup_{y \in f (I)} | {[f^{- 1} (y)]}^{(n + 1)} |$ , then

(9)

| \bar{x} - x_{n + 1} | \leq \frac{M}{(n + 1)!} | y_{0} | | y_{1} | \dots | y_{n} | .

Assuming that $x_{n + 1} \in [a, b]$ and denoting $y_{n + 1} = f (x_{n + 1})$ , then we can obtain a new approximation $x_{n + 2}$ given by relation

(10)

x_{n + 2} = L (y_{1}, y_{2}, \dots, y_{n}, y_{n + 1}; f^{- 1} | 0),

where, as it can be seen, the node $x_{0}$ has been neglected and instead we consider $y_{n + 1}$ . The above procedure may continue indefinitely: assuming that we have obtained the approximations $x_{k}, x_{k + 1}, \dots, x_{k + n} \in [a, b]$ then the next approximation is given by

(11)

x_{n + k + 1} = L (y_{k}, y_{k + 1}, \dots, y_{n + k}; f^{- 1} | 0), k = 0, 1, \dots,

where $y_{k + i} = f (x_{k + i})$ , $i = \bar{0, n}$ . If all the iterates are contained in $[a, b]$ , then the procedure may continue indefinitely.

In the same way as for (9), we get the following error bound:

(12)

| \bar{x} - x_{n + k + 1} | \leq \frac{M}{(n + 1)!} | y_{k} | | y_{k + 1} | \dots | y_{k + n} |, k = 0, 1, \dots,

Assume that $f^{'} (x) \neq 0, \forall x \in [a, b]$ , and denote

m = sup_{x \in I} | f^{'} (x) | .

Obviously

(13)

| \bar{x} - x | \geq \frac{| f (x) |}{m} .

By (12) and (13)

(14)

| f (x_{n + k + 1}) | \leq \frac{m M}{(n + 1)!} | f (x_{k}) | | f (x_{k + 1}) | \dots | f (x_{k + n}) |, k = 0, 1, \dots .

Multiplying relations (14) by ${(\frac{m M}{(n + 1)!})}^{\frac{1}{n}}$ and denoting

ρ_{i} = {(\frac{m M}{(n + 1)!})}^{\frac{1}{n}} | f (x_{i}) |, i = 0, 1, \dots

leads to

(15)

ρ_{n + k + 1} \leq ρ_{k} ρ_{k + 1} \dots ρ_{k + n}, k = 0, 1, \dots .

Suppose now that $ρ_{i} \leq d^{α_{i}}$ , with $0 < d < 1$ and $α_{i} \in ℝ$ , $α_{i} > 0,$ $i = \bar{0, n}$ . Then

(16)

ρ_{n + 1} \leq d^{α_{0} + α_{1} + \dots + α_{n}} = d^{α_{n + 1}},

where

(17)

α_{n + 1} = α_{n} + α_{n - 1} + \dots + α_{1} + α_{0} .

In general, from (15) it follows

(18)

ρ_{n + k + 1} \leq d^{α_{n + k + 1}},

where

(19)

α_{n + k + 1} = α_{n + k} + α_{n + k - 1} + \dots + α_{k + 1} + α_{k}, n = 0, 1, \dots .

Let now $t_{0} > 0$ be the unique positive solution of equation

(20)

t^{n + 1} - t^{n} - t^{n - 1} - \dots - t - 1 = 0 .

Assume that the values of $f$ obey

(21)

ρ_{i} \leq d^{α t_{0}^{i}}, i = \bar{0, n},

for a certain constant $α > 0$ , i.e., $α_{i} = α t_{0}^{i}$ . Then one can show by induction using (19) that

(22)

ρ_{n + k + 1} \leq d^{α t_{0}^{n + k + 1}}, k = 0, 1, \dots .

In [8] it is shown that $t_{0}$ verifies $\frac{2 (n + 1)}{n + 2} < t_{0} < 2$ . It is clear that the convergence order of the sequence given in (11) is less than 2.

In order to increase the convergence order of the sequence we proceed as follows. Consider the following equation, equivalent to (4):

(23)

x - g (x) = 0 .

We shall choose the interpolation nodes in (11) using $g$ , generalizing in this way the Steffensen method.

2. General methods of Steffensen type

Assume in the beginning that for all $x \in [a, b]$ , it follows that $g (x) \in [a, b]$ .

Let $u_{0} \in [a, b]$ be an initial approximation of the solution $\bar{x}$ of equation (14). We shall use the following notations:

(24)

x_{0} = u_{0}, x_{1} = g (x_{0}), x_{2} = g (x_{1}), \dots, x_{n} = g (x_{n - 1}),

which, by (7) lead to a new approximation for $\bar{x}$

(25)

u_{1} = L (y_{0}, y_{1}, \dots, y_{n}; f^{- 1} | 0),

where $y_{i} = f (x_{i}), i = \bar{0, n}$ , $x_{i}$ being given by (24).

From (9) we get:

(26)

| \bar{x} - u_{1} | \leq \frac{M}{(n + 1)!} | f (x_{0}) | | f (x_{1}) | \dots | f (x_{n}) |,

whence, by (13) we get

(27)

| \bar{x} - u_{1} | \leq \frac{M m^{n + 1}}{(n + 1)!} | \bar{x} - x_{0} | | \bar{x} - x_{1} | \dots | \bar{x} - x_{n} | .

Assume that $g$ obeys the Lipschitz condition on $[a, b]$ , i.e. there exists $l > 0$ such that

| g (x) - g (y) | \leq l | x - y |, \forall x, y \in [a, b] .

Under this hypothesis, taking into account (24), we are lead to

(28)

| \bar{x} - u_{1} | \leq \frac{M \cdot m^{n + 1} \cdot l^{\frac{n (n + 1)}{2}}}{(n + 1)!} {| \bar{x} - u_{0} |}^{n + 1} .

Let now $u_{1}$ be the next approximation for $\bar{x}$ ; then, analogously to (24), we consider in (7) the following values to $f^{- 1}$ at the interpolation nodes:

(29)

x_{0} = u_{1}, x_{1} = g (x_{0}) \dots, x_{n} = g (x_{n - 1}) .

In the same way as above, we obtain the next approximation $u_{2}$ for $\bar{x}$ , which satisfies

| \bar{x} - u_{2} | \leq \frac{M \cdot m^{n + 1} \cdot l^{\frac{n (n + 1)}{2}}}{(n + 1)!} {| \bar{x} - u_{1} |}^{n + 1} .

In general, if $u_{k}$ is an approximation of $\bar{x}$ and we set

x_{0} = u_{k}, x_{1} = g (x_{0}), \dots, x_{n} = g (x_{n - 1}),

then by (7) we obtain the next approximation $u_{k + 1}$ , which satisfies

(30)

| \bar{x} - u_{k + 1} | \leq \frac{M \cdot m^{n + 1} \cdot l^{\frac{n (n + 1)}{2}}}{(n + 1)!} {| \bar{x} - u_{k} |}^{n + 1}, k = 0, 1, \dots .

Denoting $δ_{k} = m l^{\frac{n + 1}{2}} {(\frac{M m}{(n + 1)!})}^{\frac{1}{n}} | \bar{x} - u_{k} |$ , then from the above relation we deduce

δ_{k + 1} \leq δ_{k}^{n + 1}, k = 0, 1, \dots,

which leads to the conclusion that for $n \geq 1$ , method (11) converges superlinearly. Moreover, if $x_{0}$ is chosen such that $δ_{0} < 1$ then ${lim}_{k \to \infty} δ_{k} = 0$ and therefore ${lim}_{k \to \infty} u_{k} = \bar{x} .$

The error at each step is bounded by:

(31)

| \bar{x} - u_{k} | \leq m^{- 1} l^{- \frac{n + 1}{2}} {(\frac{M m}{(n + 1)!})}^{- \frac{1}{n}} δ_{0}^{{(n + 1)}^{k}}, k = 1, 2, \dots .

In the following we analyze two particular cases.

(1)

Case $n = 1$ . In this case (11) leads to the well known Steffensen method.

Indeed, by (2) we get

(32) $L [y_{0}, y_{1} f^{- 1} | y] = x_{0} + [y_{0}, y_{1}; f^{- 1}] (y - y_{0}),$

hence, taking into account the equality

$[y_{0}, y_{1}; f^{- 1}] = \frac{1}{[x_{0}, x_{1}; f]},$

for $y = 0$ we obtain the approximation

(33) $x_{2} = x_{0} - \frac{f (x_{0})}{[x_{0}, x_{1}; f]},$

i.e., the first step in the chord method.

Obviously, (9) may continue by

(34) $x_{k} = x_{k - 2} - \frac{f (x_{k - 2})}{[x_{k - 2}, x_{k - 1}; f]}, k = 2, 3, \dots .$

Denoting in (33) $x_{0} = u_{0}$ and $x_{1} = g (u_{0})$ , we get

$u_{1} = u_{0} - \frac{f (u_{0})}{[u_{0}, g (u_{0}); f]}$

and in general

(35) $u_{k} = u_{k - 1} - \frac{f (u_{k - 1})}{[u_{k - 1}, g (u_{k - 1}); f]},$

which is precisely the Steffensen method.

In this case, the elements of the sequence ${(δ_{k})}_{k \geq 0}$ have the form

$δ_{k} = \frac{l m^{2} M}{2} | \bar{x} - u_{k} |, k = 0, 1, \dots, M = sup_{y \in f (I)} | {(f^{- 1} (y))}^{''} |$

and obey

$δ_{k + 1} \leq δ_{k}^{2}, k = 0, 1, \dots .$

If $δ_{0} < 1$ , then obviously

$lim_{k \to \infty} δ_{k} = 0$

and hence $lim x_{k} = \bar{x}$ , with the error

$| x_{k} - \bar{x} | \leq \frac{2}{l m^{2} M} δ_{0}^{2^{k}}, k = 1, 2, \dots,$

whence (35) converges quadratically.
2.

Case $n = 2$

It can be easily seen that the second order divided difference
$[y_{0}, y_{1}, y_{2}; f^{- 1}]$ can be expressed as

(36) $[y_{0}, y_{1}, y_{2}; f^{- 1}] = \frac{- [x_{0}, x_{1}, x_{2}; f]}{[x_{0}, x_{1}; f] [x_{0}, x; f] [x_{1}, x_{2}; f]} .$

By (2) we get

$L [y_{0}, y_{1}, y_{2}; f^{- 1} | y] =$ $x_{0} + [y_{0}, y_{1}; f^{- 1}] (y - y_{0})$

$+ [y_{0}, y_{1}, y_{2}; f^{- 1}] (y - y_{0}) (y - y_{1}) .$

Setting $y = 0$ and taking into account (36) and the corresponding formula for the first order divided difference, we are lead to

(37) $x_{3} = x_{0} - \frac{f (x_{0})}{[x_{0}, x_{1}; f]} - \frac{[x_{0}, x_{1}, x_{2}; f] f (x_{0}) f (x_{1})}{[x_{0}, x_{1}; f] [x_{1}, x_{2}; f] [x_{1}, x_{2}; f]},$

i.e., to a method correcting the chord method.

In general, a method of type (37) has the form

(38) $x_{n + 3}$ $= x_{n} - \frac{f (x_{n})}{[x_{n}, x_{n + 1}; f]} - \frac{[x_{n}, x_{n + 1}, x_{n + 2}; f]}{[x_{n}, x_{n + 1}; f] [x_{n + 1}, x_{n + 2}; f] [x_{n}, x_{n + 2} f]},$

$n = 0, 1, \dots$ . If in (37) we control the interpolation nodes as

$x_{0} = u_{0}, x_{1} = g (x_{0}), x_{2} = g (x_{1}) = g (g (x_{0}))$

we obtain

$u_{1} =$ $u_{0} - \frac{f (u_{0})}{[u_{0}, g (u_{0}); f]} - \frac{[u_{0}, g (u_{0}); g (g (u_{0})); f] f (u_{0}) f (g (u_{0}))}{[u_{0}, g (u_{0}); f] [u_{0}, g (g (u_{0})); f] [g (u_{0}), g (g (u_{0})); f]} .$

In general, if $u_{k}$ is an approximation to $\bar{x}$ , then $u_{k + 1}$ is given by

(39) $u_{k + 1}$ $= u_{k} - \frac{f (u_{k})}{[u_{k}, g (u_{k}); f]} - \frac{[u_{k}, g (u_{k}), g (g (u_{k})); f] f (u_{k}) f (g (u_{k}))}{[u_{k}, g (u_{k}); f] [u_{k}, g (g (u_{k})); f] [g (u_{k}), g (g (u_{k})); f]} .$

Denoting $M = {sup}_{y \in f (I)} | {[f^{- 1} (y)]}^{'''} |,$ then the error satisfies at each iteration step:

(40) $| u_{k} - \bar{x} | \leq \frac{\sqrt{6}}{m l^{3 / 2} \sqrt{m M}} δ_{0}^{3^{k}},$

where

$δ_{0} = \frac{m l^{3 / 2} \sqrt{M m}}{\sqrt{6}} | \bar{x} - u_{0} | .$

Assuming $δ_{0} < 1$ , then ${lim}_{k \to \infty} u_{k} = \bar{x}$ , with the convergence order at least $3$ .

Suppose in the following that the function $g$ given by (23) has derivatives up to the $p$ -th order, $p \in ℕ,$ $p \geq 2$ , on $[a, b]$ and its derivatives satisfy

(41) $g^{(i)} (\bar{x}) = 0, i = \bar{1, p - 1}, g^{(p)} (\bar{x}) \neq 0 .$

In this case, if the derivative of $p$ -th order in continuous on $[a, b]$ and

$L = sup_{x \in [a, b]} | g^{(p)} (x) |,$

then for all $x \in [a, b]$ one has

(42) $| g (\bar{x}) - g (x) | \leq \frac{L}{p!} {| \bar{x} - x |}^{p} .$

Using the above relation (27) we get

(43) $| \bar{x} - u_{1} | \leq \frac{M m^{n + 1}}{(n + 1)!} {(\frac{p!}{L})}^{\frac{n + 1}{p - 1}} θ_{0}^{\frac{p^{n + 1} - 1}{p - 1}},$

where $θ_{0} = {(\frac{L}{p!})}^{\frac{1}{p - 1}} | \bar{x} - u_{0} | .$

We make the following notations:

$q$ $= \frac{p^{n + 1} - 1}{p - 1};$

$K$ $= \frac{M m^{n + 1}}{(n + 1)!} {(\frac{p!}{L})}^{\frac{n + 1}{p - 1}};$

$ε_{0}$ $= K^{\frac{1}{q - 1}} θ_{0};$

$ε_{1}$ $= K^{\frac{1}{q - 1}} | \bar{x} - u_{1} | .$

By (43), we are lead to

$ε_{1} \leq ε_{0}^{q} .$

We obtain the sequence of approximation ${(u_{s})}_{s \geq 0}$ for which, if denoting

(44) $ε_{s} = K^{\frac{1}{q - 1}} | \bar{x} - u_{s} |, s = 1, 2, \dots,$

we get

(45) $ε_{s} \leq ε_{0}^{q^{s}}, s = 1, 2, \dots .$

Obviously, in this case too, if $ε_{0} < 1$ , then by (44) and (45) it follows $lim_{s \to \infty} u_{s} = \bar{x}$ and the convergence order is $q$ .

References

[1]
[2] Balázs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., 21, no. 2, pp. 111–117, 1992.
[3] Brent, R., Winograd, S. and Walfe, Ph., Optimal iterative processes for root-finding, Numer. Math., 20, no. 5, pp. 327–341, 1973.
[4] Coman, C., Some practical approximation methods for nonlinear equations, Mathematica – Rev. Anal. Numér. Théor. Approx., 11, nos. 1–2, pp. 41–48, 1982.
[5] Cassulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25–44, 1977.
[6] Iancu, C., Păvăloiu, I. and Şerb, I., Méthodes iteratives optimales de type Steffensen obtinues par interpolation inverse, Faculty of Mathematics, “Babeş-Bolyai” University, Seminar on Functional analysis and Numerical Methods, Preprint no. 1, pp. 81–88, 1983.
[7] Kacewicz, B., An integral-interpolation iterative method for the solution of scalar equations, Numer. Math., 26, no. 4, pp. 355–365, 1976.
[8] Ostrowski, A., Solution of Equations in Euclidian and Banach Spaces, Academic Press, New York and London, 1973.
[9] Păvăloiu, I., La résolution des equations par interpolation, Mathematica, 23(46), no. 1, pp. 61–72, 1981.
[10] Păvăloiu, I. and Şerb, I., Sur des méthodes de type intérpolatoire à vitesse de convergence optimale, Rev. Anal. Numér. Théor. Approx., 12, no. 1, pp. 83–88, 1983.
[11] Păvăloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 5, no. 1 (13), pp. 20–43, 1997.
[12] Traub, J. F., Iterative Methods for the Solution of Equations, Pretince-Hall, Inc. Englewood Clifs, N.J., 1964.
[13] Turowicz, A. B., Sur les derivées d’ordre superieur d’une fonction inverse, Ann. Polon. Math., 8, pp. 265–269, 1960.
[14]

2004

Properties of the complexity function for finite words

October 7, 2024

Symmetric periodic orbits in proto-stellar system

October 1, 2024

An alternative point of view on the equations of the inverese problem of dynamics

July 29, 2020

	$L [y_{0}, y_{1}, y_{2}; f^{- 1} \| y] =$	$x_{0} + [y_{0}, y_{1}; f^{- 1}] (y - y_{0})$
		$+ [y_{0}, y_{1}, y_{2}; f^{- 1}] (y - y_{0}) (y - y_{1}) .$

	$q$	$= \frac{p^{n + 1} - 1}{p - 1};$
	$K$	$= \frac{M m^{n + 1}}{(n + 1)!} {(\frac{p!}{L})}^{\frac{n + 1}{p - 1}};$
	$ε_{0}$	$= K^{\frac{1}{q - 1}} θ_{0};$
	$ε_{1}$	$= K^{\frac{1}{q - 1}} \| \bar{x} - u_{1} \| .$

Local convergence of general Steffensen type methods

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Local convergence of general Steffensen type methods∗

Abstract.

1. Introduction

2. General methods of Steffensen type

References

Related Posts

Local convergence
of general Steffensen type methods^∗