On a Steffensen-Hermite type method for approximating the solutions of nonlinear equations

9 years ago

Abstract

It is well known that the Steffensen and Aitken-Steffensen type methods are obtained from the chord method, using controlled nodes. The chord method is an interpolatory method, with two distinct nodes. Using this remark, the Steffensen and Aitken-Steffensen methods have been generalized using interpolatory methods obtained from the inverse interpolation polynomial of Lagrange or Hermite type. In this paper we study the convergence and efficiency of some Steffensen type methods which are obtained from the inverse interpolatory polynomial of Hermite type with two controlled nodes.

Author

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

Keywords

nonlinear equations in R; Steffensen and Aitken-Steffensen methods; inverse interpolatory polynomial of Hermite type

PDF

PDF-LaTeX file (on the journal website).

Cite this paper as:

I. Păvăloiu, On a Steffensen-Hermite type method for approximating the solutions of nonlinear equations, Rev. Anal. Numér. Théor. Approx. 35 (2006) no. 1, pp. 87-94. https://doi.org/10.33993/jnaat351-1015

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] Costabile, F., Gualtieri, I.M. and Luceri, R., A new iterative method for the computation of the solution of nonlinear equations, Numer. Algorithms, 28, pp. 87-100, 2001.

[2] Frontini, M., Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo, 40, pp. 109-119, 2003.

[3] Grau, M. An improvement to the computing of nonlinear equation solutions, Numer. Algorithms, 34, pp. 1-12, 2003.

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

[5] Păvăloiu I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 1, 5, pp. 20-43, 1997.

[6] Păvăloiu I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic wequences, Calcolo, 32, 1-2, pp. 69-82, 1995.

[7] Păvăloiu I., Optimal problems concerning interpolation methods of solution of equations, Publications de L’Institut Mathematique, 52 (66), pp. 113-126, 1992.

[8] Păvăloiu I., Optimal effiency index of a class of Hermite iterative methods, with two steps, Rev. Anal. Numer. Theor. Approx., 29, 1, pp. 83-89, 2000.

[9] Păvăloiu I., Local convergence of general Steffensen type methods, Rev. Anal. Numer. Theor. Approx., 33, 1, pp. 79-86, 2004.

[10] Traub, J.F., Iterative Methods for Solutions of Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.

[11] Turowicz, B.A., Sur les derivees d’ordre superieur d’une function 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; } ON A STEFFENSEN-HERMITE TYPE METHOD FOR APPROXIMATING THE SOLUTIONS OF nonlinear EQUATIONS∗

ON A STEFFENSEN-HERMITE TYPE METHOD
FOR APPROXIMATING THE SOLUTIONS OF nonlinear EQUATIONS^∗

Ion Păvăloiu^†

(Date: March 11, 2006.)

Abstract.

Key words and phrases:

Nonlinear equations in

ℝ

, Steffensen and Aitken-Steffensen methods, inverse interpolatory polynomial of Hermite type.

1991 Mathematics Subject Classification:

65H05

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

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

1. Introduction

The most well-known methods for approximating the solutions of nonlinear equations are of interpolatory type.

The Newton type methods and, more generally, the Chebyshev type methods are obtained from the inverse interpolatory polynomial of Taylor type, with one node. The chord method and its generalizations are obtained from the inverse interpolation polynomial of Lagrange, or more generally, from the inverse interpolation polynomial of Hermite [5], [8], [11]. The Steffensen and Aitken-Steffensen methods are also of interpolatory type, but their nodes are controlled at each step [7]–[10]. For the methods of interpolatory type it is necessary to compute the values of the derivative of the inverse function at different points in $ℝ .$

Let $f : [c, d] ⟶ ℝ$ be a given function, where $c, d \in ℝ,$ $c < d,$ and denote by $F = f ([c, d])$ the set of the values of $f$ on $[c, d] .$ Assume that $f$ is one-to-one and therefore there exists $f^{- 1} : F ⟶ [c, d] .$

Consider the equation

(1)

f (x) = 0 .

If equation (1) has a solution $\bar{x} \in [c, d]$ then obviously

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

It is therefore natural to seek methods of approximation of the values of $f^{- 1}$ at $y = 0,$ in order to determine different approximations to $\bar{x} .$

Several methods of approximation for $f^{- 1} (0)$ have been studied in papers such as [3]–[6], [8], [9], [11].

In the following we shall consider a method of Hermite type with two interpolation nodes. Such a method has been studied in [3], [4], [9], etc.

Let $p, q \in ℕ,$ $p, q \geq 1,$ and $x_{1},$ $x_{2} \in$ $[c, d] .$ Denote by

(2)

H (y) = H (y_{1}, p; y_{2}, q; f^{- 1} ∣ y)

the Hermite polynomial associated to the inverse function $f^{- 1}$ with the multiple nodes: $y_{1}$ of order $p,$ and $y_{2}$ of order $q,$ where $y_{i} = f (x_{i}),$ $i = 1, 2 .$ In order that polynomial (2) exists, it suffices that function $f^{- 1}$ to be differentiable up to the order $p + q$ in $F .$

In this sense the following theorem holds [5], [12].

Theorem 1.

If $f$ satisfies the following conditions:

i₁.

$f : [c, d] ⟶ F$ is one-to-one;
ii₁.

$f$ is differentiable up to the order $n \in ℕ$ at each point $x \in [c, d];$
iii₁.

$f^{'} (x) \neq 0$ for all $x \in [c, d],$

then the inverse function $f^{- 1}$ is differentiable up to the order $n$ at each point $y \in F$ , and the following relations hold:

(3)

{[f^{- 1} (y)]}^{(k)} = \sum \frac{(2 k - 2 - i_{1}) {(- 1)}^{k - 1 + i_{1}}}{i_{2}! i_{3}! \dots i_{k}! {[f^{'} (x)]}^{2 k - 1}} {(\frac{f^{'} (x)}{1!})}^{i_{1}} . {(\frac{f^{''} (x)}{2!})}^{i_{2}} \dots {(\frac{f^{(k)} (x)}{k!})}^{i_{k}},

where $y = f (x)$ , and the above sum extends over all integer solutions of the system

(4)

\begin{matrix} i_{2} + 2 i_{3} + \dots + (k - 1) i_{k} = k - 1 \\ i_{1} + i_{2} + i_{3} + \dots + i_{k} = k - 1 . \end{matrix}

Taking into account the above relations, under the hypothesis that $f$ admits derivatives up to the order $p + q$ on $[c, d],$ $f^{'} (x) \neq 0, \forall x \in [c, d],$ and using the remainder of the Hermite interpolation, it follows:

(5)

f^{- 1} (y) = H (y) + \frac{[{(f^{- 1} (η)]}^{(p + q)}}{(p + q)!} {(y - y_{1})}^{p} {(y - y_{2})}^{q}

for some $η \in int (F) .$

Setting $y = 0$ in (5), then we obtain for $\bar{x}$ the following relation:

(6)

\bar{x} = f^{- 1} (0) = H (0) + \frac{{[f^{- 1} (ξ)]}^{(p + q)}}{(p + q)!} {(- 1)}^{p + q} y_{1}^{p} y_{2}^{q} .

Denote by $x_{3}$ the next approximation for $\bar{x},$ obtained from (6)

(7)

x_{3} = H (y_{1}, p; y_{2}, q; f^{- 1} | 0) .

If we assume that the derivative of order $p + q$ of the inverse function is bounded, i.e., there exists $M \in ℝ, M > 0$ , such that

(8)

| {[f^{- 1} (y)]}^{(p + q)} | \leq M, for all y \in F,

then by (2), (6) and (7) we deduce:

| \bar{x} - x_{3} | \leq \frac{M}{(p + q)!} {| f (x_{1}) |}^{p} {| f (x_{2}) |}^{q} .

In general, if $x_{n}, x_{n + 1} \in [c, d]$ are two approximations for $\bar{x},$ then

(9)

x_{n + 2} = H (y_{n}, p; y_{n + 1}, q; f^{- 1} ∣ 0), n = 1, 2, \dots,

where $y_{n} = f (x_{n})$ while $y_{n + 1} = f (x_{n + 1})$ is a new approximation for $\bar{x},$ and obviously

(10)

| \bar{x} - x_{n + 2} | \leq \frac{M}{(p + q)!} | f (x_{n}) |^{p} | f (x_{n + 1} |^{q}, n = 1, 2, \dots .

Taking into account all the above relations one can generate the sequence of approximations ${(x_{n})}_{n \geq 1},$ under the assumption that at each iteration step, the new approximation $x_{n + 2}$ obtained by (9) from $x_{n}$ and $x_{n + 1}$ , lies in $[c, d] .$

It can be easily seen that the convergence order of method (9) is given by the positive root of equation [2]–[5], [9], [11]:

t^{2} - q t - p = 0

i.e.,

(11)

ω = \frac{q + \sqrt{q^{2} + 4 p}}{2} .

If we assume now that the Fréchet derivative $f^{'}$ of $f$ satisfies

(12)

sup_{x \in [c, d]} | f^{'} (x) | \leq a, a \in ℝ, a > 0,

then (10) becomes

(13)

| \bar{x} - x_{n + 2} | \leq \frac{M a^{p + q}}{(p + q)!} {| \bar{x} - x_{n + 1} |}^{q} {| \bar{x} - x_{n} |}^{p}, n = 1, 2, \dots .

In the following we shall denote $ρ_{i},$ $i = 1, 2, \dots$ , the expressions

(14)

ρ_{i} = a {[\frac{M a}{(p + q)!}]}^{\frac{1}{p + q - 1}} | \bar{x} - x_{i} | .

By (13) and (14) we obtain

ρ_{n + 2} \leq ρ_{n + 1}^{q} ρ_{n}^{p}, n = 1, 2, \dots .

If we assume now that $ρ_{1}$ obeys

(15)

ρ_{1} < 1

and, moreover, $ρ_{2} \leq ρ_{1}^{ω},$ with $ω$ given by (11), we easily deduce that for all $n \in ℕ, n \geq 2$ we have

ρ_{n} \leq ρ_{1}^{ω^{n - 1}}, n = 2, 3, \dots

and

lim ρ_{n} = 0

which implies

lim_{n \to \infty} x_{n} = \bar{x} .

Theorem 2.

If the following conditions hold:

i₂.

function $f$ obeys the assumptions of Theorem 1 for $n = p + q;$
ii₂.

equation (1) has a root $\bar{x} \in] c, d [;$
iii₂.

${[f^{- 1} (y)]}^{(p + q)}$ verifies (8);
iv₂.

$f^{'}$ $(x)$ verifies (12);
v₂.

$ρ_{1}$ given by (14) verifies (15) and $ρ_{2 \leq} ρ_{1}^{ω},$ where $ω$ is given by (11);
vi₂.

the sequence ${(x_{n})}_{n \geq}_{1}$ generated by (9) remains in $[c, d],$

then the following relations hold:

j₂.

$| \bar{x} - x_{n} | \leq a^{- 1} {[\frac{M a}{(p + q)!}]}^{- \frac{1}{p + q - 1}} ρ_{1}^{ω^{n - 1}}, n = 1, 2, \dots;$
jj₂.

$lim x_{n} = \bar{x} .$

Remark 1.1.

The uniqueness of the root $\bar{x}$ of equation (1) is ensured by hypothesis iii₁ from Theorem 1.∎

We consider in the following, besides (1), an equivalent equation, of the form

(16)

x - φ (x) = 0

where

φ : [c, d] ⟶ [c, d], φ (\bar{x}) = \bar{x} .

We shall show in the following section that if instead of method (9) we consider the iterative method

(17)

x_{n + 1} = H (f (x_{n}), p; f (φ (x_{n})), q; f^{- 1} ∣ 0), n = 1, 2, \dots, x_{1} \in [c, d],

then the $r$ -convergence order of this resulted method, which we call of Steffensen-Hermite type, is at least $p + q,$ i.e., substantially higher than $ω,$ given by (11).

We shall also determine the values of $p$ and $q$ for which the methods is the class (17) are optimal with respect to the efficiency index [5].

In section $3$ we shall study the convergence of the optimal methods determined in Section $2 .$

2. The convergence and the efficiency of the Steffensen-Hermite type methods

We shall assume that the function $φ$ from (16) is Lipschitz, i.e., there exists $b \in ℝ,$ $b > 0,$ such that

(18)

| φ (x) - φ (y) | \leq b | x - y |, x, y \in [c, d] .

For the approximation of the solution $\bar{x}$ of (1), consider the sequence ${(x_{m})}_{m \geq 1},$ generated by (17).

Concerning the convergence of this method the following result holds.

Theorem 3.

If the functions $f$ and $φ$ obey the following conditions:

i₃.

function $f$ obeys conditions i₂–iv₂ from Theorem 2;
ii₃.

the approximation $x_{1} \in [c, d]$ verifies

(19) $δ_{1} = a {[\frac{M a b^{q}}{(p + q)!}]}^{\frac{1}{p + q - 1}} | \bar{x} - x_{1} | < 1,$

where $b$ is the Lipschitz constant from relation (18) and $0 < b < 1;$
iii₃.

the elements of the sequence ${(x_{n})}_{n \geq 1}$ generated by (17) remain in $[c, d],$

then the following relations hold:

j₃.

$| \bar{x} - x_{n} | \leq a^{- 1} {[\frac{M a b^{q}}{(p + q)!}]}^{- \frac{1}{p + q - 1}} δ_{1}^{{(p + q)}^{(n - 1)}};$
jj₃.

$lim x_{n} = \bar{x} .$

Proof.

The proof can be done along the same lines as in Theorem 2. ∎

From the inequality given in j₃ one can see that the $r$ -convergence order of method (16) is $p + q .$

The following function evaluations are required by method (17) at each iteration step $n$ in order to determine $x_{n + 1},$ under the hypothesis that function $φ$ from (16) is expressed with the aid of function $f$ and its derivatives up to the order $r = \min {p, q}$ :

\begin{matrix} f (x_{n}), f^{'} (x_{n}), \dots, f^{(p - 1)} (x_{n}), \\ f (φ (x_{n}), f^{'} (φ (x_{n)}), \dots, f^{(q - 1)} (φ (x_{n})), \end{matrix}

i.e., $p + q$ function evaluations.

The values of the successive derivatives of $f^{- 1}$ at the points $y_{n} = f (x_{n})$ and ${\bar{y}}_{n} = f (φ (x_{n}))$ respectively, are determined by (3).

We shall admit that the number of function evaluations which must be performed from iteration step $n$ to $n + 1$ is proportional to $p + q$ , with a factor $α \in ℝ,$ $α > 0 .$ In this case, the efficiency index (see, e.g., [5], [11]) of method (17) is given by relation

I (p, q) = {(p + q)}^{\frac{1}{α (p + q)}} .

An elementary study on the function $g : (0, + \infty) ⟶ (0, + \infty)$ given by

g (t) = t^{\frac{1}{α t}},

show that this function attains its maximum at $\bar{t} = e,$ and also that $g$ is increasing on $(0, e)$ and decreasing on $(e, + \infty),$ i.e. $\bar{t}$ is a unique stationary point.

From here it follows that

I_{3} (p, q) = {[\sqrt[3]{3}]}^{^{\frac{1}{α}}}

while for $p + q = 2$

I_{2} (p, q) = {[\sqrt[2]{2}]}^{\frac{1}{α}} .

It is clear that $I_{3} (p, q) > I_{2} (p, q)$ and therefore $I (p, q)$ has the maximum value for $p + q = 3 .$

We shall point out and study the optimal methods in the following section.

3. The convergence of the optimal methods

We shall determine in the beginning the methods which correspond to the two cases which may be considered for $p + q = 3,$ i.e., $p = 1,$ $q = 2$ or $p = 2,$ $q = 1 .$

In the first case $(p = 1,$ $q = 2)$ we want to determine a polynomial $H$ of the form:

H (y) = a_{0} + a_{1} y + a_{2} y^{2}

with the conditions:

(20)		$H (y_{1})$	$= x_{1}, x_{1} \in [c, d],$
	$H (y_{2})$	$= φ (x_{1}),$
	$H^{'} (y_{2})$	$= \frac{1}{f^{'} (φ (x_{1}))} = {[f^{- 1} (y_{2})]}^{'},$

where $y_{1} = f (x_{1})$ and $y_{2} = f (φ (x_{1})) .$

Conditions (20) lead to a system of $3$ equations with the unknowns $a_{0}, a_{1}, a_{2} .$ For our purpose, of approximating the solution of (1), we are interested only in the value $H (0) = a_{0} .$ Denoting by $[φ (x_{1}), φ (x_{1}); f] = f^{'} (φ (x_{1})),$ then for $a_{0}$ we obtain the following two equivalent expressions:

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

The above expressions for $a_{0}$ lead us to the sequences ${(x_{n})}_{n \geq 1}$ and ${(φ (x_{n}))}_{n \geq 1}$ , generated by

(21)

x_{n + 1} = x_{n} - \frac{f (x_{n})}{[x_{n}, φ (x_{n}); f]} - \frac{[x_{n}, φ (x_{n}), φ (x_{n}); f]}{[φ (x_{n}), φ (x_{n}); f] {[x_{n}, φ (x_{n}); f]}^{2}} f (x_{n}) f (φ (x_{n})), n = 1, 2, \dots

or equivalently

(22)

x_{n + 1} = φ (x_{n}) - \frac{f (φ (x_{n}))}{[φ (x_{n}), φ (x_{n}); f]} - \frac{[x_{n}, φ (x_{n}), φ (x_{n}); f]}{[φ (x_{n}), φ (x_{n}); f] {[x_{n}, φ (x_{n}); f]}^{2}} f^{2} (φ (x_{n})), n = 1, 2, \dots .

In the second case, $p = 2,$ $q = 1,$ we obtain in our analogous fashion, the following expressions for ${(x_{n})}_{n \geq 0}$ and ${(φ (x_{n}))}_{n \geq 0}$

(23)

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

$n = 1, 2, \dots,$ or, equivalently,

(24)

x_{n + 1} = φ (x_{n}) - \frac{f (φ (x_{n}))}{[x_{n}, φ (x_{n}); f]} - \frac{[x_{n}, x_{n}, φ (x_{n}); f]}{[x_{n}, x_{n}; f] {[x_{n,} φ (x_{n}); f]}^{2}} f (x_{n}) f (φ (x_{n})), n = 1, 2, \dots .

In order to study the convergence of methods (21) or (23) we need to determine the third order derivative of $f^{- 1}$ .

By (3) for $k = 3,$ we get:

{[f^{- 1} (y)]}^{'''} = \frac{3 {[f^{''} (x)]}^{2} - f^{'''} (x) f^{'} (x)}{{[f^{'} (x)]}^{5}}, y = f (x) .

Regarding methods (21) or (22) the following result holds.

Theorem 4.

If the initial approximation $x_{1}$ and functions $f$ and $φ$ obey

i₄.

equation (1) has a root $\bar{x} \in] c, d [;$
ii₄.

function $f$ is derivable up to the order $3$ on $[c, d];$
iii₄.

$f^{'} (x) \neq 0,$ $\forall x \in [c, d];$
iv₄.

there exists $r > 0$ such that $Δ = [\bar{x} - r, \bar{x} + r] \subseteq [c, d];$
v₄.

$a =$ $\max_{x \in Δ}$ $| f^{'} (x) |;$
vi₄.

function $φ$ verifies (18), where $0 < b < 1;$
vii₄.

$ρ_{1} = a b {[\frac{m a}{6}]}^{1 / 2} ∣ \bar{x} - x_{1} ∣ < 1,$ where

$m = \max_{x \in Δ} | \frac{3 {[f^{''} (x)]}^{2} - f^{'} (x) f^{'''} (x)}{{[f^{'} (x)]}^{5}} |,$

then the elements of the sequence ${(x_{n})}_{n \geq 0}$ generated by (21) remain in $Δ$ and, moreover, the following relations hold:

j₄)

$lim$ $x_{n} = \bar{x};$
jj₄)

$| \bar{x} - x_{n + 1} | \leq \frac{1}{a b} \sqrt{\frac{6}{m a}} ρ_{1}^{3^{n}}, n = 1, 2, \dots,$ i.e., the sequence ${(x_{n})}_{n \geq 1}$ has the $r$ -convergence order $3 .$

Proof.

We assume first that hypothesis iii₄ implies that function $f : [c, d] ⟶ F$ admits an inverse $f^{- 1} :$ $F ⟶ [c, d]$ and also that the root $\bar{x}$ of equation (1) is unique in the interval $[c, d] .$ Conditions ii₄ and iii₄ ensure that function $f^{- 1}$ is derivable up to the order $3$ on $F .$

By (18) and hypothesis vi₄ we have that for any $x_{1} \in Δ,$ $φ (x_{1}) \in Δ .$

The element $x_{2}$ is given by

x_{2} = H (f (x_{1}), 1; f (φ (x_{1})), 2; f^{- 1} ∣ 0)

and by (5) we have:

\bar{x} = x_{2} + {(- 1)}^{3} [0, f (x_{1}), f (φ (x_{1})), f (φ (x_{1})); f^{- 1}] f (x_{1}) f^{2} (φ (x_{1})) .

From this relation, taking into account the mean value formula for divided differences, and also hypotheses v₄–vii₄, we get that

(25)

| \bar{x} - x_{2} | \leq \frac{m a^{3} b^{2}}{6} {| \bar{x} - x_{1} |}^{3} .

Relation $ρ_{1} < 1$ and condition (25) imply that $| \bar{x} - x_{2} | < | \bar{x} - x_{1} |,$ i.e., $x_{2} \in Δ .$

In general, assuming that an element $x_{k}$ of the sequence ${(x_{n})}_{n \geq 1}$ belongs to the interval $Δ,$ obviously $φ (x_{n}) \in Δ,$ and, similarly as above, we can prove that

| x_{n + 1} - \bar{x} | \leq \frac{M a^{3} b^{2}}{6} {| \bar{x} - x_{n} |}^{3}, k = 1, 2, \dots,

The above relations imply jj $_{4} .$ and then obviously j_4. ∎

Regarding the sequence generated by (23), resp. (24), the following result holds:

Theorem 5.

If the initial approximation $x_{1},$ and the function $f, φ$ obey

i₅.

equation (1) has a root $\bar{x} \in] c, d [;$
ii₅

function $f$ admits derivatives of orders up to $3$ on $[c, d];$
iii₅

$f^{'} (x) \neq 0$ for all $x \in [c, d];$
iv₅

there exists $r > 0$ such that $Δ = [\bar{x} - r, \bar{x} + r] \subseteq [c, d];$
v₅.

$a =$ $\max {| f^{'} (x) | : x \in Δ};$
vi₅

function $φ$ verifies (18) with $0 < b < 1;$
vii₅

$ρ_{1} = a \sqrt{\frac{m a b}{6}} | \bar{x} - x_{1} | < 1,$ where

$m = \max_{x \in Δ} | \frac{3 {[f^{''} (x)]}^{2} - f^{'} (x) f^{'''} (x)}{{[f^{'} (x)]}^{5}} |,$

then the sequence ${(x_{n})}_{n \geq 1}$ generated by (23) is convergent, and the following relations hold:

j₅.

$lim x_{n} = \bar{x};$
jj₅.

$| \bar{x} - x_{n + 1} | \leq \frac{1}{a} \sqrt{\frac{6}{m a b}}$ $q_{1}^{3^{n}},$ $n = 1, 2, \dots .$

Proof.

The proof of this theorem can be done in an analogous fashion, as for Theorem 4. ∎

References

[1]
[2] Costabile, F., Gualtieri, I.M. and Luceri, R., A new iterative method for the computation of the solution of nonlinear equations, Numer. Algorithms, 28, pp. 87–100, 2001.
[3] Frontini, M., Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo, 40, pp. 109–119, 2003.
[4] Grau, M. An improvement to the computing of nonlinear equation solutions, Numer. Algorithms, 34, pp. 1–12, 2003.
[5] Ostrowski, A., Solution of Equations in Euclidean and Banach Spaces, Academic Press, New York and London, 1973.
[6] Păvăloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 1, 5, pp. 20–43, 1997.
[7] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic wequences, Calcolo, 32, 1–2, pp. 69–82, 1995.
[8] Păvăloiu, I., Optimal problems concerning interpolation methods of solution of equations, Publications de L’Institut Mathematique, 52 (66), pp. 113–126, 1992.
[9] Păvăloiu, I., Optimal effiency index of a class of Hermite iterative methods, with two steps, Rev. Anal. Numér. Théor. Approx., 29, 1, pp. 83–89, 2000.
[10] Păvăloiu, I., Local convergence of general Steffensen type methods, Rev. Anal. Numér. Théor. Approx., 33, 1, pp. 79–86, 2004.
[11] Traub, J.F., Iterative Methods for Solutions of Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[12] Turowicz, B.A., Sur les derivées d’ordre superieur d’une function inverse, Ann. Polon. Math., 8, pp. 265–269, 1960.
[13]

2006

The convergence of an implicit mean value iteration

June 26, 2025

Iterative functional-differential system with retarded argument

July 9, 2025

The equivalence between the T-stabilities of Mann and Ishikawa iterations

July 19, 2020

On a Steffensen-Hermite type method for approximating the solutions of nonlinear equations

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

ON A STEFFENSEN-HERMITE TYPE METHOD FOR APPROXIMATING THE SOLUTIONS OF nonlinear EQUATIONS∗

Abstract.

Key words and phrases:

1991 Mathematics Subject Classification:

1. Introduction

Theorem 1.

Theorem 2.

Remark 1.1.

2. The convergence and the efficiency of the Steffensen-Hermite type methods

Theorem 3.

Proof.

3. The convergence of the optimal methods

Theorem 4.

Proof.

Theorem 5.

Proof.

References

Related Posts

ON A STEFFENSEN-HERMITE TYPE METHOD
FOR APPROXIMATING THE SOLUTIONS OF nonlinear EQUATIONS^∗