A note on the efficiency index of a class of two step Hermite iterative methods

3 years ago

(proceedings), html, inverse interpolation, nonlinear equations in R, Numerical Analysis, paper, PDF, solving F(x)=0 iteratively, works

Abstract

One considers Hermite interpolatory methods, based on two interpolatory nodes which have the same multiplicity order. Duing the efficiency index, defined by A. M. Ostrowski, one determines the method of optimal efficiency index.

Authors

Ion Păvăloiu
”Tiberiu Popoviciu! Institute of Numerical Analysis Romanian Academy, Cluj-Napoca, Romania

Keywords

Paper coordinates

I. Păvăloiu, A note on the efficiency index of a class of two step Hermite iterative methods, Conferences in Analysis, Functional Equations Approximation and Convexity, in honor of prof. Elena Popoviciu, Cluj-Napoca, pp. 228-233 (1999).

PDF

scanned paper.

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

google scholar link

[1] R. Breent, S. Winograd, F. Wolfe, Optimal Iterative Processes for Root-Finding, Numer. Math. 20 (1973), pp. 327-341.
[2] Gh. Coman, Some Practical Approximation Methods for Nonlinear Equations, Matematica-Revue d’Analyse Numerique et de Theorie de l’Approximation, T.11, no.1-2 (1982), pp. 41-48.
[3] H.T. Kung, J.F. Traub, Optimal Order and Efficiency for Iterations with Two Evaluations, SIAM J. Numer. Anal., vol. 13, no.1, (1976), pp.84-99.
[4] A. M. Ostrowski, Solution of Equation and Systems of Equations, Academic Press, New York and London (1966).
[5[ I. Păvăloiu, Bilateral Approximations for the Solutions of Scalar Equations, Revue D’Analyse Numerique et de Theorie de l’Approximation, 23 1, (1994), pp. 95=100.
[6] I. Păvăloiu, Optimal Concerning Interpolation Methods of Solutions of Equaitons, Publ. Inst. Math., 52(66) (1992), pp. 113-126.
[7] I. Păvăloiu, Optimal Efficiency Index for Iterat ive Methods of Intyerpolatory Type, Computer Science Journal of Moldova, vol. 5, no.1 (13), (1997), pp. 20-43.
[8] Traub J.F., Iterative methods for solution of equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[9] Turowicz, B.A., Sur les derives d’ordre superieur d’une fonction inverse, Ann. Polon. Math., 8 (1960), pp. 265-269.

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; } A note on the efficiency index of a class of two step Hermite iterative methods

A note on the efficiency index of a class of two step Hermite iterative methods

Ion Păvăloiu

1 Introduction

As we have shown in [7], the problem of determining the Hermite interpolatory iterative methods having the optimal efficiency index cannot be solved in the general case. We have determined however in [7] some upper and lower bounds for the efficiency indexes; these bounds depend on the coefficients of the characteristical equation whose positive root provide the convergence order of the considered equation.

In this note we shall consider a subclass of Hermite interpolatory methods, based on two interpolatory nodes which have the same multiplicity order $q \in ℕ .$ We shall use the efficiency index defined in [4] for determining the method with the optimal efficiency index.

Let $I = [a, b],$ $a, b \in ℝ,$ $a < b,$ $f : I \to ℝ$ and consider the equation

(1)

f (x) = 0 .

We assume that this equation has a unique solution $\bar{x} \in] a, b [.$ For solving the above equation we consider a function $g : I \to I$ and we also assume that $\bar{x}$ is the unique fixed point of $g$ in $I .$

For approximating $\bar{x}$ there is usually taken an element from the sequence ${(x_{s})}_{s \geq 0}$ generated by the iterative method:

(2)

x_{s + 1} = g (x_{s}), s = 0, 1, \dots, x_{0} \in I .

More generally, if $h : I^{k} \to I$ is a function of $k$ variables whose restriction to the diagonal of the set $I^{k}$ coincides with $g,$ then the following sequence may be considered for approximating $\bar{x} :$

(3)

x_{s + k} = h (x_{s}, x_{s + 1}, \dots, x_{s + k - 1}), s = 0, 1, \dots, x_{0}, x_{1}, \dots, x_{k - 1} \in I .

The convergence of the sequence ${(x_{s})}_{s \geq 0}$ generated by (2) or (3) depends on certain properties of the functions $f, g$ and resp. $h$ . The time needed by a computer to obtain a convenient approximation of $\bar{x}$ depends on the convergence order of the sequence ${(x_{s})}_{s \geq 0}$ and also on the number of elementary operations performed at each iteration step.

While the convergence order may be determined exactly in most of the situations, the number of elementary operations may be hard to evaluate.

For this reason Ostrowski has proposed in [4] a simplification of this problem, by considering the number of function evaluations needed at each iteration step. This leads to the definition of the efficiency index, which may be naturally applied to the comparison of different methods.

Consider a sequence ${(x_{s})}_{s \geq 0},$ which together with $f$ and $g$ satisfies:

a) $x_{s} \in I;$ for all $s = 0, 1, \dots$

b) ${(x_{s})}_{s \geq 0}$ converges to $\bar{x};$

c) the sequence ${(g (x_{s}))}_{s \geq 0}$ converges also to $\bar{x};$

d) $f (\bar{x}) = 0;$

e) $f$ is derivable at $\bar{x};$

f) for all $x, y \in I$ there exists $m \in ℝ_{+}$ such that $0 < [x, y; f] < m,$ where $[x, y; f]$ denotes the divided differences of $f$ on the nodes $x$ and $y .$

Concerning the convergence order of ${(x_{s})}_{s \geq 0},$ we shall consider the following definition:

Definition 1

The sequence ${(x_{s})}_{s \geq 0}$ has the convergence order $ω \in ℝ,$ $ω \geq 1,$ with respect to the function $g$ if there exists the limit

α = lim_{s \to \infty} \frac{\ln | g (x_{s}) - \bar{x} |}{\ln | x_{s} - \bar{x} |}

and $α = ω .$

Lemma 1

If the sequence ${(x_{s})}_{s \geq 0}$ and the functions $f$ and $g$ satisfy conditions a) - f), then the necessary and sufficient condition for the sequence ${(x_{s})}_{s \geq 0}$ to have the convergence order $ω \in ℝ,$ $ω \geq 1$ with respect to $g$ is that there exists the limit

β = lim_{s \to \infty} \frac{\ln | f (g (x_{s})) |}{\ln | f (x_{s}) |}

and $β = ω .$

Lemma 2

If ${(u_{s})}_{s \geq 0}$ is a sequence of real positive numbers satisfying

i) The sequence ${(u_{s})}_{s \geq 0}$ converges to $0$ .

ii) There exist the nonnegative real numbers $α_{1}, α_{2}, \dots, α_{n + 1}$ and a bounded sequence of real positive numbers ${(c_{s})}_{s \geq 0},$ $0 < inf_{s} {c_{s}} .$

iii) The following equalities hold:

u_{s + n + 1} = c_{s} u_{s}^{α_{1}} u_{s + 1}^{α_{2}} \dots u_{s + 1}^{α_{n + 1}}, s = 0, 1, \dots

iv) The sequence ${(\frac{\ln u_{s} + 1}{\ln u_{s}})}_{s \geq 0}$ is convergent and $lim \frac{\ln u_{s + 1}}{\ln u_{s}} = ω > 0,$

then $ω$ is the positive root of the equation

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

We shall denote in the following by $m_{s}$ the number of function evaluations that must be performed at the step $s$ for the iteration (2) or (3).

Taking into account Lemmas 1 and 2, the following definition becomes natural:

Definition 2

The real number $E$ is called the efficiency index of the method (2) (resp.(3)) if there exists

l = lim {(\frac{\ln | f (x_{s + 1}) |}{\ln | f (x_{s}) |})}^{\frac{1}{m_{s}}}

and $l = E .$

Remark. If there exist $s_{0} \in ℕ$ such that for $s > s_{0}$ the values $m_{s}$ are constant, $m_{s} = r,$ then the efficiency index is given by relation

(4)

E = ω^{\frac{1}{r}}

2 Two step Hermite interpolatory iterative methods

Let $q \in ℕ,$ $q \geq 1$ be a natural number and consider the Hermite inverse interpolatory polynomial on two nodes with the same multiplicity order $q .$

We shall make the following assumptions concerning the function $f :$

$α$ ) $f$ is derivable on $] a, b [$ up to and including the $2 q$ - th order;

$β$ ) $f^{'} (x) \neq 0$ for all $x \in] a, b [$ ;

$γ$ ) equation (1) has a solution $\bar{x} \in] a, b [.$

Under this assumptions, it is clear that $f$ admits an inverse $f^{- 1} : D \to I,$ where $D = f (I),$ and also that $\bar{x}$ is given by relation

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

Moreover, $f^{- 1}$ is derivable up to the order $2 q$ at all points from $D$ and the $k$ - th derivative, for $k \in ℕ,$ $1 \leq k \leq 2 q$ is given by [9].

(5)

{[f^{- 1} (y)]}^{(k)} = \sum \frac{(2 k - i_{1} - 2)! {(- 1)}^{k + i_{1} - 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 we have denoted $y = f (x),$ and the above sum extends on the nonnegative whole solutions of the system

	$i_{2} + 2 i_{3} + \dots + (k - 1) i_{k}$	$=$	$k - 1$
	$i_{1} + i_{2} + \dots + i_{k}$	$=$	$k - 1 .$

Denote by $H (y_{1}, q; y_{2}, q; f^{- 1} | y)$ the Hermite inverse interpolatory polynomial satisfying

(6)

H^{(k)} (y_{1}, q; y_{2}, q; f^{- 1} | y_{i}) = {[f^{- 1} (y_{i})]}^{(k)}, i = 1, 2; k = 0, 1, \dots, q - 1

where ${[f^{- 1} (y_{i})]}^{(0)} = f^{- 1} (y_{i}),$ $i = 1, 2$ and $y_{1}, y_{2} \in D .$

Consider also the polynomial

ω_{1} (y) = {(y - y_{1})}^{q} {(y - y_{2})}^{q} .

The residual in the interpolation formula becomes then

	$R (f^{- 1}; y)$	$=$	$f^{- 1} (y) - H (y_{1}, q; y_{2}, q; f^{- 1} \| y) =$
		$=$	$\frac{1}{(2 q)!} {[f^{- 1} (θ_{1})]}^{(2 q)} ω_{1} (y),$

where $θ_{1}$ belongs to the smallest open interval determined by the points $y, y_{1}$ and $y_{2} .$

Let $x_{s}, x_{s + 1} \in I$ be two approximations of the solution $\bar{x} .$ Then the next approximation may be determined by

(7)

x_{s + 2} = H (y_{s}, q; y_{s + 1}, q; f^{- 1} | 0), s = 0, 1 \dots, .

We shall assume that all the elements of the sequence ${(x_{s})}_{s \geq 0}$ generated by (7) belong to the interval $I .$

Taking into account the above assumptions we easily get for $s = 0, 1, \dots$ that

| f (x_{s + 2}) | = | f^{'} (α_{s}) | \frac{| {[f^{- 1} (θ_{s})]}^{(2 q)} |}{(2 q)!} {| f (x_{s + 1}) |}^{q} {| f (x_{s}) |}^{q}, s = 0, 1, \dots,

where $α_{s}$ belongs to the open interval determined by the points $\bar{x}$ and $x_{s + 2},$ and $θ_{s}$ is contained in the open interval determined by $0, y_{s}, y_{s + 1} .$

Assuming that ${[f^{- 1} (y)]}^{(2 q)} \neq 0$ for all $y \in i n t D,$ denoting

c_{s} = | f^{'} (α_{s}) | \frac{| {[f^{- 1} (θ_{s})]}^{(2 q)} |}{(2 q)!}, s = 0, 1, \dots

and applying Lemma 2, we obtain the following equation for determining the convergence order of method (7):

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

It follows that the convergence order is

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

3 The Optimal efficiency index

We remark that in order to generate the elements of the sequence ${(x_{s})}_{s \geq 0}$ given by (7), at each iteration step $s, s \geq 2,$ the following function evaluations are needed:

f, f^{'}, \dots, f^{(q - 1)},

all at $x_{s},$ since their values at $x_{s - 1}$ are know from the previous step. Hence there are needed $q$ function evaluations.

Remark. Taking into account that the Hermite inverse interpolatory polynomial is computed with the aid of the succession derivatives of $f^{- 1},$ which, by (5) have a rather complicated form, then it becomes necessary to take into account $q - 1$ more function evaluations. On the other hand, the evaluation of the Hermite polynomial determined by (6) may lead us to the consideration of a one more function evaluation. We can therefore conclude that at each iteration step there is necessary an amount of $2 q$ function evaluations. These considerations may affect the value of the efficiency index, but we shall see in the following that the optimal efficiency index is not affected by considering a number of function evaluations proportional with $q .$

Indeed, considering the number of function evaluations as being equal to $δ q,$ $δ$ being a positive constant, then by (4), the efficiency index of method (7) is

(8)

E = φ (q) = {[\frac{q + \sqrt{q^{2} + 4 q}}{2}]}^{\frac{1}{δ q}} .

The value of $q$ for which $E$ attains the upper bound is given by the solution of $φ^{'} (q) = 0,$ and we see bellow that this solution does not depend on $δ .$

By (8) we get

φ^{'} (q) = \frac{1}{δ} φ (q) {[\frac{1}{q} \ln \frac{q + \sqrt{q^{2} + 4 q}}{2}]}^{'} .

Since $φ (q) > 0,$ it follows that equation $φ^{'} (q) = 0$ is equivalent with the following one

{(\frac{1}{q} \ln \frac{q + \sqrt{q^{2} + 4 q}}{2})}^{'} = 0,

whence we get

(9)

Ψ (q) = \frac{\sqrt{q^{2} + 4 q} + q + 2}{\sqrt{q^{2} + 4 q} + q + 4} - \ln \frac{q + \sqrt{q^{2} + 4 q}}{2} = 0 .

For solving this equation denote $t = q + \sqrt{q^{2} + 4 q}$ and we notice that $\frac{d t}{d q} > 0$ for $q > 0 .$ By this substitution, equation (9) becomes

η (t) = \frac{t + 2}{t + 4} - \ln \frac{t}{2} = 0,

and since $η^{'} (t) < 0$ for $t > 0,$ it follows that equation $η (u) = 0$ has a unique positive solution $\bar{t} .$ We also notice that $η (2) = \frac{2}{3} > 0$ and $η (2 e) = \frac{e + 1}{e + 2} - 1 < 0,$ i.e. $2 < E < 2 e,$ which lead us to the conclusion that the positive root $\bar{q}$ of equation $φ^{'} (q) = 0$ satisfies

2 < \bar{q} + \sqrt{{\bar{q}}^{2} + 4 \bar{q}} < 2 e,

and whence

(10)

\frac{1}{2} < \bar{q} < \frac{e^{2}}{e + 1} .

We also remark that $η (t) > 0$ for $1 \leq t \leq \bar{t}$ and $η (t) < 0$ for $\bar{t} < t,$ so it follows that $φ^{'} (q) > 0$ for $\frac{1}{2} < q < \bar{q}$ and $φ^{'} (q) < 0$ for $q > \bar{q} .$ The function $E = φ (q)$ has at $q = \bar{q}$ a maximum value. It remains to compute the maximum value of $E$ in the set of natural numbers from the neighborhood of the real number $\bar{q} .$ By (10), the value of $q$ for which $E$ attains the maximum belong to the set ${1, 2, 3} .$ One can easily check that $φ (1) < φ (2)$ and $φ (2) > φ (3),$ which imply that $E$ attains the maximum value for $q = 2 .$

We have proved the following theorem:

Theorem 3

Among all the iterative methods (7), the method with the highest efficiency index is the one corresponding to $q = 2,$ being given by

(11)

x_{s + 2} = H (y_{s}, 2; y_{s + 1}, 2; f^{- 1} | 0), x_{0}, x_{1} \in I, s = 0, 1, \dots, .

Finally we give for $H$ an expression based on the divided differences on double nodes (see [6]).

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

where $y_{s} = f (x_{s}),$ $y_{s + 1} = f (x_{s + 1}) .$

For computing the divided differences from (3) one can use the recurrence formula for divided differences with the aid of the following table:

$y_{s}$	$f^{- 1} (y_{s})$
$y_{s}$	$f^{- 1} (y_{s})$	$[y_{s}, y_{s}; f^{- 1}]$
$y_{s + 1}$	$f^{- 1} (y_{s + 1})$	$[y_{s}, y_{s + 1}; f^{- 1}]$	$[y_{s}, y_{s}; y_{s + 1}; f^{- 1}]$
$y_{s + 1}$	$f^{- 1} (y_{s + 1})$	$[y_{s + 1}, y_{s + 1}; f^{- 1}]$	$[y_{s}, y_{s + 1}; y_{s + 1}; f^{- 1}]$	$[y_{s}, y_{s}, y_{s + 1}; y_{s + 1}; f^{- 1}]$

where $y_{s} = f (x_{s}), y_{s + 1} = f (x_{s + 1}),$ $[y_{s}, y_{s}; f^{- 1}] = \frac{1}{f^{'} (x_{s})}, [y_{s}, y_{s + 1}; f^{- 1}] = \frac{1}{[x_{s}, x_{s + 1}; f]}$
and $[y_{s + 1}, y_{s + 1}; f^{- 1}] = \frac{1}{f^{'} (x_{s + 1})} .$

References

[1] R. Breent, S. Winograd, F. Wolfe, Optimal Iterative Processes for Root-Finding, Numer.Math.20 (1973), pp.327-341.
[2] Gh. Coman, Some Practical Approximation Methods for Nonlinear Equations, Matematica-Revue d’Analyse Numérique et de Théorie de l’Approximation, T.11, No.1-2, (1982), pp.41-48.
[3] H.T. Kung, J.F. Traub, Optimal Order and Efficiency for Iterations with Two Evaluations, SIAM J. Numer.Anal., Vol.13, No.1, (1976), pp.84-99.
[4] A.M. Ostrowski, Solution of Equation and Systems of Equations, Academic Press, New York and London, (1966).
[5] I. Păvăloiu, Bilateral Approximations for the Solutions of Scalar Equations, Revue D’Analyse Numérique et de Théorie de l’Approximation, 23, 1, (1994), pp.95-100.
[6] I. Păvăloiu, Optimal Problems Concerning Interpolation Methods of Solutions of Equations, Publ.Inst.Math., 52(66) (1992), pp.113-126.
[7] I. Păvăloiu, Optimal Efficiency Index for Iterative Methods of Interpolatory Type, Computer Science Journal of Moldova, Vol. 5, No.1 (13); (1997), pp.20-43.
[8] Traub J.F., Iterative methods for solution of equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[9] Turowicz B.A., Sur les derivées d’ordre superieur d’une fonction inverse, Ann. Polon. Math. 8 (1960), pp.265-269.

”Tiberiu Popoviciu” Institute of Numerical Analysis

str. Republicii 37 P.O.Box 68-1

3400 Cluj-Napoca

1999

The influence of the alloy flow during the cast filling on the solidification process

November 27, 2018

A Characterization of the Efficient Solutions of Multiobjective Optimization Problems by Means of a Scalar Problem

July 15, 2025

A Stability For Multivalued Optimization,

July 1, 2025

A note on the efficiency index of a class of two step Hermite iterative methods

Abstract

Authors

Keywords

Paper coordinates

PDF

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

Paper (preprint) in HTML form

A note on the efficiency index of a class of two step Hermite iterative methods

1 Introduction

Definition 1

Lemma 1

Lemma 2

Definition 2

2 Two step Hermite interpolatory iterative methods

3 The Optimal efficiency index

Theorem 3

References

Related Posts