On computational complexity in solving equations by interpolation methods

9 years ago

Ion Păvăloiu

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

Abstract

Authors

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

Keywords

PDF

Scanned paper: on the journal website.

Latex version of the paper.

Cite this paper as:

I. Păvăloiu, On computational complexity in solving equations by interpolation methods, Rev. Anal. Numér. Théor. Approx., 24 (1995) no. 1, pp. 201-214.

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] Brent, R., Winograd, S. and Wolfe, Ph., Optimal Iterative Processes for Root-Finding. Numer. Math. 20(5) (1973), pp. 327-341.

[2] Casulli, V. and Trigiante, D., Sui procedimenti Iterativi Compositi. Calcolo, XIII. IV (1976), pp. 403-420.

[3] Coman, Gh., Some practical Approximation Methods for Nonlinear

Equations. Mathematica Revue d’Analyse Num'{e}rique et de Th'{e}orie de l’Approximation, 11, 1-2 (1982), pp. 41-48.

[4] Kacewitcz, B., An Integral-Interpolation Iterative Method for the Soltuion of Scalar Equations, Numer. Math. 26 (4), (1976), pp. 355-365.

[5] Kung, H.T. and Traub, J.F., Optimal Order and Efficiency for Iterations With Two Evaluations. SIAM, Numer Anal. 13, 1, (1976), pp. 84-99.

[6] Ostrowski, M.A., Soltuion of Equations and Systems of Equations. Academic Press. New York and London (1960).

[7] Păvăloiu I., The Soltuion of the Equations by Interpolation (Romanian) Ed. Dacia Cluj-Napoca (1981).

[8] Păvăloiu I., Optimal Problems Concerning Interpolation Methods of Solution of Equations. Publications de L’Institut Mathematique Beograd. 52, (66), (1992), pp. 113-126.

[9] Traub, J.F., Iterative Methods for the Solution of Equations. Prentice-Hall, New York (1964).

[10] Traub, J.F., Theory of Optimal algorithms, Preprint. Department of Computer Science Carnegie-Mellon University (1973), pp. 1-22.

[11] Traub, J.F. and Wozniakowski, H., Optimal Radius of Convergence of Interpolatory Iterations for Operator Equations, Aequationes Mathematicae, 21 (1980), pp. 159-172.

[12] Turowicz, A.B., Sur les derivees d’ordre suprieur 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; } On computational complexity in Solving Equations by Interpolation Methods

On computational complexity in Solving Equations
by Interpolation Methods

Ion Păvăloiu
(Cluj-Napoca)

1. Introduction

Let $I \subseteq ℝ$ be an interval of the real axis and $f : I \to ℝ$ a function. Consider the equation:

(1)

f (x) = 0,

supposed to have a solution $\bar{x} \in I$ . Also get $g : I \to I$ be a function whose fixed points from $I$ coincide with the root of (1).

For solving (1) one can usually use an iterative method of the form:

(2)

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

More generally, if $G : I^{k} \to I$ is a function depending on $k$ variables, whose restriction to the diagonal of the set $I^{k}$ coincides with $g$ , i.e.

(3)

g (x) = G (x, x, \dots, x), for all x \in I

then one can consider the following iterative method for solving equation (1):

(4)

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

The convergence of the sequences ${(x_{n})}_{n \geq 0}$ generated by (2) or (4) to a solution of equation (1) depends obviously on the properties of the functions $f, g$ respectively $G,$ and the amount of time necessary to obtain a suitable approximation for the solution $\bar{x}$ is influenced both by the convergence order of the methods (2), resp. (4) and by the amount of elementary operations that must be performed at each iteration step. This last aspect belongs to a chapter of the calculus theory and practice, chapter concerning the computational complexity.

Many authors ([1], [2], [3], [5], [6], [9], [10], [11]), who studied the computational complexity of the iteration processes, have defined different notions, as: the efficiency of a method, the efficiency index of a method or the cost of a method, which they have quantitatively expressed by different scalar magnitudes.

Throughout this paper we shall adopt the following definition for the convergence order of an iteration method:

Definition 1.1.

The real number $p \geq 1$ is called the convergence order of the sequence ${(x_{n})}_{n \geq 0}$ generated by an iterative method if the following limit exists and is not zero:

(5)

lim_{n \to \infty} \frac{| x_{n + 1} - \bar{x} |}{{| x_{n} - \bar{x} |}^{p}} = a \neq 0 .

where $\bar{x}$ is the solution of equation (1).

Concerning the calculus complexity, using the convergence order we can define now the following notion:

Definition 1.2.

[6]. The number $I$ is called the efficiency index of the method (2) or (4), if the following limit exists and is finite:

(6)

lim_{n \to \infty} {(\frac{\ln | x_{n + 1} - \bar{x} |}{\ln {| x_{n} - \bar{x} |}^{p}})}^{1 / m_{n}} = I,

where $m_{n}$ represents the number of function evaluations that must be performed when passing from the step $n$ to the step $n + 1$ .

If we suppose that $m_{n}$ is the same for all $n$ , and take into account that (6) has an asymptotical character, then there results for $I$ the following expression:

(7)

I = I (p, m) = p^{\frac{1}{m}} .

In the following we shall study certain classes of iteration methods,namely the methods obtained by interpolation, among which we shall select those for which the efficiency index given by (7) is optimal, i.e. the greatest. For this purpose in the next section we shall briefly recall the classes of methods that we want to study.

2. Interpolation Iterative Methods

2.1. Lagrange’s inverse interpolation polynomial

Let $I \subseteq ℝ$ be an interval and $f : I \to ℝ$ a function. Denote by $F = f (I)$ the set of all values of $f$ for $x \in I$ . Suppose that $f$ is one-to-one, i.e. there exists the inverse function $f^{- 1}; F \to I$ . Consider in $I, n + 1$ interpolation nodes:

(8)

x_{1}, x_{2}, \dots, x_{n + 1}, with x_{i} \neq x_{j}; for i \neq j; i, j = \bar{1, n + 1 .}

Suppose that equation (1) has the unique solution $\bar{x} \in I$ .

Obviously,

(9)

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

and so the problem of approximation the solution $\bar{x}$ reduces to the approximation of $f^{- 1} (0)$ .

A simple and efficient approximation method for the functions is given by the interpolating approximation.

Denote by:

(10)

y_{1}, y_{2}, \dots, y_{n + 1}, y_{i} = f (x_{i}), i = \bar{1, n + 1,}

the values of the $f$ on the nodes $x_{i}$ from (8).

The Lagrange interpolation polynomial corresponding to the function $f^{- 1}$ on the nodes from (10) (taking into account that $y_{i} \neq y_{j}, i \neq j; i, j = \bar{1, n + 1}$ ) has the form:

(11)

L (y_{1}, y_{2}, \dots, y_{n + 1}; f^{- 1} | y) = \sum_{i = 1}^{n + 1} \frac{x_{i} ω_{1} (y)}{(y - y_{i}) ω_{1} (y_{i})},

where $ω_{1} (y) = \prod_{i = 1}^{n + 1} (y - y_{i})$ .

If we suppose that the function $f$ has derivatives up to the order $k, k \in ℕ$ and $f^{'} (x) \neq 0$ for all $x \in I,$ then we have the following formula for the computation of the $k$ -th derivative of $f^{- 1}$ at the point $y = f (x), x \in I$ ([7], [12]):

(12)

{[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}} \dots {(\frac{f {(x)}^{(k)}}{k!})}^{i_{k}},

where the above sum extends to all nonnegative integer numbers, solutions of the system:

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

If we suppose that $f$ admits derivatives up to the order $n + 1$ on the interval $I$ and the $n + 1$ -th derivative is bounded on $I$ , then by (12) we obtain,

(14)

\bar{x} = f^{- 1} (0) = L (y_{1}, y_{2}, \dots, y_{n + 1}; f^{- 1} | 0) + \frac{{[f^{- 1} (c)]}^{(n + 1)}}{(n + 1)!} ω_{1} (0),

where $c$ is a point belonging to the smallest interval containing $0, y_{1}, y_{2}, \dots, y_{n + 1}$ and $ω_{1} (0) = {(- 1)}^{n + 1} f (x_{1}) f (x_{2}) \dots f (x_{n + 1}) .$

Denote by $x_{n + 2}$ the number:

(15)

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

and by (14) we get:

(16)

| \bar{x} - x_{n + 2} | \leq \frac{M_{n + 1}}{(n + 1)!} | f (x_{1}) | | f (x_{2}) | \dots | f (x_{n + 1}) |,

from which we see that if $x_{1}, x_{2}, \dots, x_{n + 1}$ are chosen in a neighbourhood of $\bar{x}$ such that $| f (x_{i}) | < 1, i = \bar{1, n + 1},$ then $x_{n + 1}$ can be considered as a new approximation for $\bar{x}$ . We have denoted in inequality (16), $M_{n + 1} = sup_{y \in F} | {[f^{- 1} (y)]}^{(n + 1)} |$ .

Let now $x_{k}, x_{k + 1}, \dots, x_{k + n} \in I$ be $n + 1$ approximations for $\bar{x}$ . Then the Lagrange polynomial corresponding to the function $f^{- 1}$ on the nodes $y_{i} = f (x_{i}), i = \bar{k, n + k}$ has the form:

(17)

L (y_{k}, y_{k + 1}, \dots, y_{k + n}; f^{- 1} | y) = \sum_{i = k}^{k + n} \frac{x_{i} ω_{k} (y)}{(y - y_{i}) ω_{k} (y_{i})}

where $ω_{k} (y) = \prod_{i = k}^{n + k} (y - y_{i})$ . From this relation, for $y = 0$ , we obtain a new approximation for $\bar{x}$ , namely

(18)

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

which satisfies the delimitation

(19)

| \bar{x} - x_{n + k + 1} | \leq \frac{M_{n + 1}}{(n + 1)!} | f (x_{k}) | | f (x_{k + 1}) | \dots | f (x_{k + n}) | .

It is well known that the iterative method given by (18) has the convergence order $θ_{n + 1}$ , which is the unique positive root of the equation, [6]:

(20)

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

It is also known (see [6]) that $θ_{n + 1}$ verifies:

(21)

\frac{2 (n + 1)}{n + 2} < θ_{n + 1} < 2

and

(22)

θ_{n} < θ_{n + 1}; lim_{n \to \infty} θ_{n} = 2, for all n \geq 1 .

Remark 2.1.

In the successive computation of the elements of the sequence ${(x_{n})}_{n \geq 0}$ generated by (18) it is necessary to compute at each step $k$ the values $ω_{k} (0)$ and $ω_{k}^{'} (y_{i}), i = k, k + 1, \dots, k + n$ .

We observe that practically there exists a connection both between $ω_{k} (0)$ and $ω_{k + 1} (0)$ and between $ω_{k}^{'} (y_{i})$ and $ω_{k + 1}^{'} (y_{i})$ .

Indeed:

ω_{k} (y) = \prod_{i = k}^{n + k} (y - y_{i})

and

ω_{k + 1} (y) = \prod_{i = k + 1}^{n + k + 1} (y - y_{i})

hence we get

(23)

ω_{k + 1} (y) = \frac{ω_{k} (y) (y - y_{n + k + 1})}{y - y_{k}},

which for $y = 0$ yields

(24)

ω_{k + 1} (0) = \frac{ω_{k} (0) y_{n + k + 1}}{y_{k}}

From (23) we obtain:

(25)

ω_{k + 1}^{'} (y) = \frac{[ω_{k}^{'} (y) (y - y_{n + k + 1}) + ω_{k} (y)] (y - y_{k}) - ω_{k} (y) (y - y_{n + k + 1})}{{(y - y_{k})}^{2}},

which gives us the following recurrence formula:

(26)

ω_{k + 1}^{'} (y_{i}) = {\begin{matrix} \frac{ω_{k}^{'} (y_{i}) (y_{i} - y_{n + k + 1})}{y_{i} - y_{k}}, & i = k + 1, k + 2, \dots, k + n \\ \frac{ω_{k} (y_{i})}{y_{i} - y_{k}}, & i = k + n + 1 \end{matrix}

Recurrence formulae (24) and (26) hold for all $k = 1, 2, \dots,$ ∎

2.2. Hermite Inverse Interpolating Polynomial

We consider, besides the interpolatory nodes (8), the natural numbers $a_{1}, a_{2}, \dots, a_{n + 1}$ with $a_{i} \geq 1 i = \bar{1, n + 1}$ and

(27)

a_{1} + a_{2} + \dots + a_{n + 1} = m + 1, m \in ℕ .

Suppose that $f$ admits derivatives up to the order $m + 1$ on the interval $I$ and $f^{'} \neq 0$ . Then, by (12) it follows that the function $f^{- 1}$ also admits derivatives up to the order $m + 1$ . The Hermite polynomial of degree $m$ associated to the function $f^{- 1}$ on the nodes $y_{i} = f (x_{i}), i = \bar{1, n + 1}$ , assuming that $f^{'} (x) \neq 0$ for all $x \in I$ , is:

(28)		$H (y_{1}; a_{1}, y_{2}; a_{2}, \dots, y_{n + 1}; a_{n + 1}; f^{- 1} \| y) =$
	$= \sum_{i = 1}^{n + 1} \sum_{j = 0}^{a_{i} - 1} \sum_{k = 0}^{a_{i} - j - 1} {[f^{- 1} (y_{i})]}^{(j)} \frac{1}{k! j!} {[\frac{{(y - y_{i})}^{a_{i}}}{ω_{1} (y)}]}_{y = y_{i}}^{(k)} \frac{ω_{1} (y)}{{(y - y_{i})}^{a_{i} - j - k}} .$

where

(29)

ω_{1} (y) = \prod_{i = 1}^{n + 1} {(y - y_{i})}^{a_{i}}

This polynomial satisfies:

(30)

H^{(j)} (y_{1}; a_{1}, y_{2}; a_{2}, \dots, y_{n + 1}; a_{n + 1}; f^{- 1} | y_{i}) = {[f^{- 1} (y_{i})]}^{(j)}

for all $j = 0, 1, \dots, a_{i} - 1; i = 1, 2, \dots, n + 1$ .

As in 2.1 we obtain from (28) the following iterative method for solving equation (8):

(31)

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

where in the polynomial $H, ω_{k} = \prod_{i = k}^{n + k} {(y - y_{i})}^{a_{i}}$ .

Using the differentiability assumptions for $f$ , we obtain:

(32)

| x_{n + k + n} - \bar{x} | \leq \frac{M_{m + 1}}{(m + 1)!} {| f (y_{k}) |}^{a_{1}} {| f (y_{k + 1}) |}^{a_{2}} \dots {| f (y_{k + n}) |}^{a_{n + 1}}

where $M_{m + 1} = sup_{y \in F} | {[f^{- 1} (y)]}^{(m + 1)} |$ .

It is well known that the convergence order of (31) is given by the positive root $ω_{n + 1}$ of the equation:

(33)

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

In the particular cases when $a_{1} = a_{2} = \dots = a_{n + 1}$ we have iterative method:

(34)

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

and when $n = 0$ we get the Chebyshev iterative method of order $m + 1$ :

(35)

x_{k + 1} = x_{k} - \frac{{[f^{- 1} (y)]}^{'}}{1!} f (x_{k}) + \dots + {(- 1)}^{m} {\frac{[f^{- 1} (y_{k})]}{m!}}^{(m)} f^{m} (x_{k}), k = 1, 2, \dots

which has the convergence order $p = m + 1$ .

For the method (34), by (33) it follows that the convergence order is given by the positive root $ω_{n + 1}$ of the equation:

(36)

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

which satisfies:

(37)

ω_{n} < ω_{n + 1}, n = 1, 2, \dots,

(38)

\max {q, \frac{n + 1}{n + 2} (q + 1)} < ω_{n + 1} < q + 1; n = 1, 2, \dots,

(39)

lim_{n \to \infty} ω_{n + 1} = q + 1 .

3. The Efficiency Index of the Chebyshev Method of Order $m + 1$

In the following we shall make the assumptions:

a)

Consider as a function evaluation, the evaluation of the derivatives ${[f^{- 1} (y)]}^{(k)},$ assuming $f^{(k)} (x), k = \bar{1, m}$ as having been computed.
b)

Consider as a function evaluation, the evaluation of the right hand side of expression (35) assuming $f (x)$ and ${[f^{(- 1)} (y)]}^{(k)}, k = \bar{1, m}$ as having been computed.
c)

Consider as a function evaluation the evaluation of the function $f$ or of any of its derivatives.

In this hypothesis, it is necessary for an iteration step with method (35) to compute firstly the values of the functions: $f, f^{'}, \dots, f^{(m)}$ at the point $x_{k}$ , altogether $m + 1$ function for the calculus of the values of the successive derivatives of $f^{- 1}$ , by (12). If we take into account that for evaluating the right hand side expression from relation (35) is computed another function value, we have altogether $2 (m + 1)$ function evaluations at each iteration step.

Using definition (7) for the efficiency index, method (35) has the following index:

(40)

I (m + 1, 2 (m + 1)) = {(m + 1)}^{\frac{1}{2 (m + 1)}}

(We have taken into account that the convergence order is $m + 1$ ).

We are searching for the maximum value of the index $I$ from (40), for $m \in ℕ$ .

For this purpose we consider the auxiliary function $φ : (0, \infty) \to ℝ_{+} φ (t) = t^{\frac{1}{2 t}}$ and we note that: $lim_{t \to 0} φ (t) = 0$ , $lim_{t \to \infty} φ (t) = 1$ , $φ$ is increasing for $t \in (0, e)$ and decreasing for $t \in (e, \infty); t = e$ is a maximum point for the function $φ$ .

For $t \in ℕ$ , the function $φ$ attains its maximum for $t = 3,$ so $I (m + 1, 2 (m + 1))$ attains its maximum form $m = 2$ .

So, the following holds:

Theorem 3.1.

In the above assumptions a)–c) among all the Chebyshev iterative methods of the form (35) the method with the greatest efficiency index is the one of $3^{r d}$ order, namely

(41)

x_{k + 1} = x_{k} - \frac{f (x_{k})}{f^{'} (x_{k})} - \frac{1}{2} \frac{f^{''} (x_{k}) f^{2} (x_{k})}{{[f^{'} (x_{k})]}^{3}}, k = 0, 1, \dots, x_{0} \in I .

In the following table are shown the approximations of the efficiency index of Chebyshev methods for some values of $m$ .

$m$	$2$	$3$	$4$	$5$	$6$
$I (m + 1, 2 (m + 1))$	$1.1892$	$1.2009$	$1.1892$	$1.1746$	$1.1610$

We see that $I (3, 6) ≅ 1.2009 .$

4. The Efficiency Index for the Lagrange-Hermite Methods

In the following we shall study the case when $n \geq 1$ , i.e. when number of nodes is greater than one. In the beginning we shall take the method given by (18) for which, if we take into account the assumptions a) - c) and neglect the first step, we get that at each iteration step we have first one function evaluation, namely the value of the function $f$ at $x_{n + k}$ , and then we have another function evaluation, for the right hand side of relation (18), hence altogether two function evaluations. Recalling that the convergence order for (18) is $θ_{n + 1}$ , which satisfies (21) and (22) we get for the efficiency index the relation

(42)

I (θ_{n + 1}, 2) = \sqrt{θ_{n + 1}} .

By (22) we have that $I (θ_{n}, 2) < I (θ_{n + 1}, 2)$ for all $n \geq 1$ .

So we conclude:

Theorem 4.1.

If the assumptions a)–c) hold, for the Lagrange methods given by (17) the efficiency index is increasing with respect to the number of interpolation nodes and

lim_{n \to \infty} I (θ_{n}, 2) = \sqrt{2} .

Now we study the efficiency index for the methods given by (34), for which the convergence order $ω_{n + 1}$ verifies (36)–(39). Obviously, we suppose that $q > 1, q = 1$ in (34) giving (18).

There are two aspects that must be considered: the efficiency with respect to the number of interpolation nodes, when their multiplicity order $q$ is kept fixed and, on the second hand, the efficiency with respect to the multiplicity order $q$ for fixed $n, n \geq 1$ .

We again suppose that assumptions a)–c) hold. So from the right hand side of (34), at each iteration step, excepting the first one, we have the following function evaluations: we compute $f (x_{n + k}), f^{'} (x_{n + k}), \dots, f^{(q - 1)} (x_{n + k}),$ i.e. $q$ function evaluations, and then by (12) we compute ${[f^{- 1} (y_{n + k})]}^{'},$ ${[f^{- 1} (y_{n + k})]}^{''}, \dots, {[f^{- 1} (y_{n + k})]}^{(q - 1)}$ i.e., $q - 1$ function evaluations, and finally we compute the right hand side of (34). so altogether, $2 q$ function evaluations.

Using (37)–(39) we get:

(43)

I (ω_{n + 1}, 2 q) > I (ω_{n}, 2 q), for
all n \geq 1, q > 1,

and

(44)

{(\max {q, \frac{n + 1}{n + 2} (q + 1)})}^{\frac{1}{2 q}} < I (ω_{n + 1}, 2 q) < {(q + 1)}^{\frac{1}{2 q}} .

for all $n \geq 1, q > 1$ .

For a fixed $q$ by (43) we get that the efficiency index is increasing as a function of $n$ , and by (44)

lim_{n \to \infty} I (ω_{n + 1}, 2 q) = {(1 + q)}^{\frac{1}{2 q}} .

From (44) we also obtain:

(45)

q^{\frac{1}{2 q}} < I (ω_{n + 1}, 2 q) < {(q + 1)}^{\frac{1}{2 q}}, for q \geq n + 1

and

(46)

{[\frac{n + 1}{n + 2} (q + 1)]}^{\frac{1}{2 q}} < I (ω_{n + 1}, 2 q) < {(q + 1)}^{\frac{1}{2 q}},,for q < n + 1 .

A. For the first case, when $q \geq n + 1$ we consider the auxiliary functions $φ, ψ; (0, \infty) \to ℝ_{+}$ given by

φ (t) = t^{\frac{1}{2 t}}

and

ψ (t) = {(1 + t)}^{\frac{1}{2 t}} .

As we have seen before, $φ$ satisfies:

lim_{\begin{matrix} t \to 0 \\ t > 0 \end{matrix}} φ (t) = 0, lim_{t \to \infty} φ (t) = 1,

is increasing on $(0, e)$ and decreasing on $(e, + \infty),$ so at $t = e$ attains its maximum.

One can establish the following relations for $ψ$ :

lim_{t \to 0} ψ (t) = \sqrt{e}; lim_{t \to \infty} ψ (t) = 1

and $ψ$ is decreasing on $(0, + \infty)$ .

Recalling that $φ$ attains its maximum value at $t = e,$ let $\bar{t}$ be the solution of the equation

(47)

{(t + 1)}^{\frac{1}{2 t}} - e^{\frac{1}{2 e}} = 0 .

then for $t > \bar{t}$ we have ${(t + 1)}^{\frac{1}{2 t}} < e^{\frac{1}{2 e}},$ hence, by (45), we obtain that the values of $q$ for which $I (ω_{n + 1}, 2 q)$ attains its maximum lie in the set ${q \in ℕ; 1 < q \leq \bar{t}}$ . One can easily prove that $\bar{t} \in (46)$ so we shall study the cases $q = 2, q = 3,$ and $q = 4$ . Since $q \geq n$ we study 1) $q = 2, n = 1;$ 2) $q = 3, n = 1; q = 3, n = 2$ and 3) $q = 4, n = 1; n = 2, n = 3$ .

1) The corresponding equation from (36) for $q = 2, n = 1,$ is $t^{2} - 2 t - 2 = 0$ , with the positive solution $ω_{2} = 1 + \sqrt{3}$ . So $I (ω_{2}, 4) = \sqrt[4]{1 + \sqrt{3}} ≅ 1, 2856 \dots$

2) The convergence orders corresponding for this case are the solutions of the equations $t^{2} - 3 t - 3 = 0$ for $n = 1, q = 3$ respectively $t^{3} - 3 t^{2} - 3 t - 3 = 0$ for $n = 2$ , $q = 3$ .

We obtain $I (ω_{2}, 6) ≅ 1.2487 \dots$ , respectively $I (ω_{3}, 6) ≅ 1.2573 \dots$

3) The corresponding equations give us:

$I (ω_{2,} 8) ≅ 1, 2175 \dots; I (ω_{3}, 8) ≅ 1, 2218 \dots$ and $I (ω_{4}, 8) ≅ 1, 2226 \dots$

So the greatest efficiency index when $q \geq n + 1$ is obtained for $n = 1, q = 2$ i.e $I (ω_{2}, 4) = \sqrt[4]{1 + \sqrt{3}}$ .

B. Let $q < n + 1$ , so (46) holds. We shall again consider two auxiliary functions

	$φ, ψ :$	$(0, + \infty) \to ℝ_{+},$
	$φ (t)$	$= {[\frac{n + 1}{n + 2} (t + 1)]}^{\frac{1}{2 t}}, ψ (t) = {(t + 1)}^{\frac{1}{2 t}}$

which possess the following properties: $lim_{t \to 0} φ (t) = 0; lim_{t \to \infty} φ (t) = 1$ ;

φ^{'} (t) = \frac{1}{2} {[\frac{n + 1}{n + 2} (t + 1)]}^{\frac{1}{2 t}} \cdot \frac{\frac{t}{t + 1} - \ln \frac{n + 1}{n + 2} (t + 1)}{t^{2}},

and one can easily prove that: the equation $φ^{'} (t) = 0$ has a unique positive solution, denoted by $τ_{n}, φ^{'} (t) < 0$ for $t > τ_{n}$ and $φ^{'} (t) > 0$ for $t \in (0, τ_{n}),$ i.e. $φ$ attains its maximum value at $t = τ_{n}$ .

Taking into account the properties of $ψ$ one can see that the equations

(48)

{(t + 1)}^{\frac{1}{2 t}} - e^{\frac{1}{2 (τ_{n} + 1)}} = 0, n = 2, 3, \dots

have a unique positive solution $μ_{n}$ for each $n \geq 2$ .

In the table below we give the approximative values $μ_{n}$ and $τ_{n}$ for $n \in [2, 10]$ .

$n$	$τ_{n}$	$μ_{n}$
$2$	$1.3816 \dots$	$3.6711 \dots$
$3$	$1.1201 \dots$	$2.8679 \dots$
$4$	$0.9566 \dots$	$2.3871 \dots$
$5$	$0.8436 \dots$	$2.0649 \dots$
$6$	$0.7601 \dots$	$1.8327 \dots$
$7$	$0.6955 \dots$	$1.6566 \dots$
$8$	$0.6438 \dots$	$1.5180 \dots$
$9$	$0.6013 \dots$	$1.4056 \dots$
$10$	$0.5656 \dots$	$1.3125 \dots$

An elementary reasoning proves that $τ_{n}$ and $μ_{n}$ are decreasing functions of $n$ , $n \geq 2$ , as we can see in the above table.

If $t > μ_{n}$ then $φ (τ_{n}) > φ (t)$ so the optimal values for $q$ must lie in the set ${q \in ℕ; 2 \leq q < \max {n + 1, μ_{n}}}$ .

It can be shown that for $n \geq 6, μ_{n} < 2$ and for $n \in [2, 5]$ , $2 < μ_{n} < 4$ . It follows that the only suitable value for $q$ is $q = 2$ . In this case we get that $I (ω_{n}, 4) < I (ω_{n + 1}, 4)$ , $n \geq 2,$ i.e. the efficiency index increases with $n$ , but anyway the best results hold for $q = 2$ .

5. Margins for the Efficiency Index in the Case of Lagrange-Hermite Methods

We end this note by indicating, in the above assumptions, left and right margins of the efficiency index of the Lagrange-Hermite methods.

In this respect we shall first establish an inequality that will give left margins for the positive roots of equations (33).

Let

(49)

P (t) = t^{n + 1} - a_{n + 1} t^{n} - a_{n} t^{n - 1} - \dots - a_{1} = 0,

where $a_{1} + a_{2} + \dots + a_{n + 1} = m + 1, a_{i} \geq$ for $i = \bar{1, n + 1}$ .

The following Lemma holds.

Lemma 5.1.

The positive root $ω_{n + 1}$ of (49) satisfies:

(50)

ω_{n + 1} \geq {[m + 1]}^{\frac{m + 1}{(n + 1) (m + 1) - \sum_{i = 1}^{m + 1} (i - 1) a_{i}}}

Proof.

Let

α = {[m + 1]}^{\frac{m + 1}{(n + 1) (m + 1) - \sum_{i = 1}^{m + 1} (i - 1) a_{i}}}

It will suffice to show $P (α) \leq 0$ , using the inequality between the weighted arithmetic and geometric mean, i.e.

(51)

\frac{\sum_{i = 1}^{n + 1} α_{i} p_{i}}{\sum_{i = 1}^{n + 1} p_{i}} \geq {(\prod_{i = 1}^{n + 1} a_{i}^{p_{i}})}^{\frac{1}{\sum_{i = 1}^{n + 1} p_{i}}}

We get

	$P (α)$	$= α^{n + 1} - \sum_{i = 1}^{n + 1} a_{i} α^{i - 1} = α^{n + 1} - \frac{\sum_{i = 1}^{n + 1} a_{i} α^{i - 1}}{\sum_{i = 1}^{n + 1} a_{i}} \sum_{i = 1}^{n + 1} a_{i}$
		$\leq α^{n + 1} - (\sum_{i = 1}^{n + 1} a_{i}) {[\prod_{i = 1}^{n + 1} α^{(i - 1) a_{i}}]}^{\frac{1}{\sum_{i = 1}^{n + 1} a_{i}}} = α^{n + 1} - (m + 1) α^{\frac{\sum_{i = 1}^{n + 1} (i - 1) a_{i}}{m + 1}}$
		$= α^{\frac{\sum_{i = 1}^{n + 1} (i - 1) a_{i}}{m + 1}} [α^{n + 1} - \frac{\sum_{i = 1}^{n + 1} (i - 1) a_{i}}{m + 1} - (m + 1)] = 0,$

i.e. $P (α) \leq 0$ .

We also get $ω_{n + 1} \leq a + 1$ , where $a = \max_{1 \leq i \leq n + 1} {a_{i}}$ .

In the hypotheses of 3., using (31) in generating the sequence ${(x_{n})}_{n \geq 0}$ then the number of function evaluations at each step is $2 (m + 1) - n$ .

The efficiency index (31) then satisfies

α^{\frac{1}{2 (m + 1) - n}} \leq I (ω_{n + 1}, 2 (m + 1) - n) \leq {(a + 1)}^{\frac{1}{2 (m + 1) - n}},

with $α$ and $a$ specified above. ∎

References

[1] Brent, R., Winograd, S. and Wolfe, Ph., Optimal iterative processes for root-finding. Numer Math. 20 (5) (1973), 327–341.
[2] Casulli, V. and Trigiante, D., Sui procedimenti iterativi compositi. Calcolo, XIII, IV (1976), pp. 403–420.
[3] Coman, Gh., ^†^†margin: available soon,
refresh and click here $\to$ Some practical approximation methods for nonlinear equations. Anal. Numér. Théor. Approx., 11, 1–2 (1982), pp. 41–48.
[4] Kacewitcz, B., An integral-interpolation iterative method for the solution of scalar equations, Numer. Math. 26 (4), (1976), pp. 355–365.
[5] Kung, H. T. and Traub, J. F., Optimal order and efficiency for iterations with two evaluations. SIAM. J. Numer Anal. 13, 1, (1976), pp. 84–99.
[6] Ostrowski, M. A., Solution of Equations and Systems of Equations. Academic Press. New York and London (1960).
[7] Păvăloiu, I., ^†^†margin: available soon,
refresh and click here $\to$ The Solution of the Equations by Interpolation (Romanian) Ed. Dacia Cluj-Napoca (1981).
[8] ^†^†margin: clickable $\to$ Păvăloiu, I., Optimal problems concerning interpolation methods of solution of equa- tions, Publications de L’Institut Mathématique Beograd. 52, (66), (1992), pp. 113–126.
[9] Traub, J. F., Iterative Methods for the Solution of Equations. Prentice-Hall, New York (1964).
[10] Traub, J. F., Theory of Optimal Algorithms, Preprint Department of Computer Science Carnegie-Mellon University (1973) pp. 1–22.
[11] Traub, J, F. and Wozniakowski, H., Optimal radius of convergence of interpolatory iterations for operator equations. Aequationes Mathematicae, 21 (1980), pp. 159–172.
[12] Turowicz, A. B., Sur les dérivées d’ordre supérieur d’une fonction inverse, Ann. Polon Math. 8 (1960), pp. 265–269.
[13]

Received 1 X 1994

Academia Română

Institutul de Calcul

”Tiberiu Popoviciu”

P.O. Box 68

3400 Cluj-Napoca 1

România

1995

On the metric projection and the quotient mapping

May 8, 2023

Galerkin Methods for Enginvalue Problems

July 23, 2025

The Ritz variational method for the problem of heat conduction in plates in the plane. Application using test functions in the form of monomials xiyj

October 24, 2024

On computational complexity in solving equations by interpolation methods

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

paper on journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On computational complexity in Solving Equations by Interpolation Methods

1. Introduction

Definition 1.1.

Definition 1.2.

2. Interpolation Iterative Methods

2.1. Lagrange’s inverse interpolation polynomial

Remark 2.1.

2.2. Hermite Inverse Interpolating Polynomial

3. The Efficiency Index of the Chebyshev Method of Order m+1

Theorem 3.1.

4. The Efficiency Index for the Lagrange-Hermite Methods

Theorem 4.1.

5. Margins for the Efficiency Index in the Case of Lagrange-Hermite Methods

Lemma 5.1.

Proof.

References

Related Posts

On computational complexity in Solving Equations
by Interpolation Methods

3. The Efficiency Index of the Chebyshev Method of Order $m + 1$