On the convergence order of the multistep methods

9 years ago

Abstract

We analyze in a unitary way the iterative methods for solving scalar equations, which are of inverse interpolation form. We determine their convergence orders.

Authors

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

Keywords

nonlinear equations in R; inverse interpolation iterative methods; convergence orders.

PDF

Scanned paper.

Scanned paper also freely available on the journal website.

Latex version of the paper (soon).

Cite this paper as:

I. Păvăloiu, On the convergence order of the multistep methods, Bul. Ştiinţ. Univ. Baia Mare, Ser. Mat.-Inf. 13 (1997), pp. 59-64.

About this paper

Journal

Buletin Științific

Publisher Name

Universitatea Baia Mare

JSTOR permalink

http://www.jstor.org/stable/44001540

Print ISSN

Not available yet.

Online ISSN

Not available yet.

References

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 THE CONVERGENCE ORDER OF THE MULTISTEP METHODS

Buletinul Ştiinţific al Universităţii din Baia Mare

Seria B, Matematică-Informatică, vol. XIII (1997), 107–116

ON THE CONVERGENCE ORDER
OF THE MULTISTEP METHODS

Ion Pǎvǎloiu

1. Introduction

In this paper we analyse some aspects concerning the convergence order of the iterative methods of interpolatory type for solving scalar equations. A unitary approach to these methods will enable us to analyse them and then to select among them those with the optimal convergence order.

2. Convergence order

Denote $I = [a, b], a, b \in ℝ, a < b$ and consider the equation

(1)

f (x) = 0

where $f : I \to ℝ$ . For the sake of the simplicity we shall suppose in the following that equation (1) has a unique solution $\bar{x} \in I$ . Let $g : I \to I$ be a function for which $\bar{x}$ is the unique fixed point on $I$ .

For the approximation of the solution of (1) there is generally considered, under certain conditions, a sequence ${(x_{p})}_{p \geq 0}$ generated by:

(2)

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

More generally, if $G : I^{k} \to I$ is a function of $k$ variables for which the restriction to the diagonal of the set $I^{k}$ coincides with $g,$ namely

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

then there is considered the following iterative method:

(3)

x_{s + k} = G (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_{p})}_{p \geq 0}$ generated by (2) or (3) depends on certain properties of the functions $f$ and $g$ , respectively $G$ . The amount of time needed to obtain a convenient approximation $x_{p}$ of $\bar{x}$ depends both on the convergence order of the sequence ${(x_{p})}_{p \geq 0}$ and on the amount of elementary operations that must be performed by the computer at each iteration step. In this paper we shall study only the first aspect of this problem, i.e. we shall deal with the convergence order.

We shall adopt as the convergence order a definition a little more generally then the one given by Ostrowski [3].

Consider an arbitrary sequence ${(x_{p})}_{p \geq 0}$ satisfying, together with $f$ and $g$ , the following conditions:

a)

$x_{s} \in I$ and $g (x_{s}) \in I$ for $s = 0, 1, \dots;$
b)

the sequences ${(x_{p})}_{p \geq 0}$ and ${(g (x_{p}))}_{p \geq 0}$ converge to $\bar{x},$ the solution of equation (1);
c)

there exists $m \in ℝ, m > 0$ such that $0 < | [x, y; f] | \leq m$ , for all $x, y \in I$ , where we have denoted by $[x, y; f]$ the first order divided difference of $f$ at the points $x$ and $y$ ;
d)

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

Definition 2.1.

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

(4)

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

and $α = ω$ .

Remark 2.1.

If the elements of ${(x_{p})}_{p \geq 0}$ are generated by the iterative method (2), then the convergence order defined above coincides with the one defined in [3]. ∎

For the determination of the convergence order of some classes of iterative methods we shall need in the following two lemmas:

Lemma 2.1.

If the sequence ${(x_{p})}_{p \geq 0}$ and the functions $f$ and $g$ satisfy the properties a)–d) then the necessary and sufficient condition for the sequence ${(x_{p})}_{p \geq 0}$ to have the convergence order $ω \in ℝ, ω \geq 1$ with respect to the function $g$ is that the following limit to exist:

(5)

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

and $β = ω .$

Proof.

Supposing that one of the relations (4) or (5) holds and, taking into account the properties a)–d), we obtain:

	$α$	$=$	$lim \frac{\ln \| g (x_{p}) - \bar{x} \|}{\ln \| x_{p} - \bar{x} \|} = lim \frac{\ln \| f (g (x_{p})) \| - \ln \| [g (x_{p}), \bar{x}; f] \|}{\ln \| f (x_{p}) \| - \ln \| [x_{p}, \bar{x}; f] \|}$
		$=$	$lim \frac{\ln \| f (g (x_{p})) \|}{\ln \| f (x_{p}) \|} \cdot \frac{1 - \frac{\ln \| [g (x_{p}), \bar{x}; f] \|}{\ln \| f (g (x_{p})) \|}}{1 - \frac{\ln \| [x_{p}, \bar{x}; f] \|}{\ln \| f (x_{p}) \|}} = lim \frac{\ln \| f (g (x_{p})) \|}{\ln \| f (x_{p}) \|} = β .$

∎

Lemma 2.2.

If ${(u_{p})}_{p \geq 0}$ is a sequence of real numbers that satisfies:

i.

the sequence ${(u_{p})}_{p \geq 0}$ is convergent and $lim u_{p} = 0;$
ii.

there exist the nonnegative numbers $α_{1}, α_{2}, \dots, α_{n + 1}$ and a bounded sequence ${(c_{p})}_{p \geq 0}, c_{p} > 0, p = 0, 1, \dots$ for which $inf {c_{p}} > 0$ such that

(6) $u_{s + n + 1} = c_{s} u_{s}^{α_{1}} u_{s + 1}^{α_{2}} \dots u_{s + n}^{α_{n + 1}}, s = 0, 1, \dots;$
iii.

the sequence ${(\frac{\ln u_{p + 1}}{\ln u_{p}})}_{p \geq 0}$ is convergent and $lim \frac{\ln u_{p + 1}}{\ln u_{p}} = ω .$

Then $ω$ is the positive root of the equation:

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

Proof.

From (6) we obtain

lim_{s \to \infty} \frac{\ln u_{n + s + 1}}{\ln u_{n + s}} = lim_{s \to \infty} \frac{\ln c_{s}}{\ln u_{n + s}} + \sum_{i = 0}^{n} α_{i + 1} lim_{s \to \infty} \frac{\ln u_{s + i}}{\ln u_{s + n}} .

Taking into account the equalities

lim_{s \to \infty} \frac{\ln c_{s}}{\ln u_{n + s}} = 0 and lim_{s \to \infty} \frac{\ln u_{i + s}}{\ln u_{n + s}} = \frac{1}{ω^{n - i}}, i = \bar{0, n}

we obviously have

ω = \sum_{i = 0}^{n} α_{i + 1} \frac{1}{ω^{n - i}},

i.e.,

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

∎

In the following we shall consider the equations:

(7)

P (t) = t^{n + 1} - α_{n + 1} t^{n} - α_{n} t^{n - 1} - \dots - α_{2} t - α_{1} = 0;

(8)

Q (t) = t^{n + 1} - α_{1} t^{n} - α_{2} t^{n - 1} - \dots - α_{n} t - α_{n + 1} = 0;

(9)

R (t) = t^{n + 1} - α_{i_{1}} t^{n} - α_{i_{2}} t^{n - 1} - \dots - α_{i_{n}} t - α_{i_{n + 1}} = 0,

where we shall suppose that $α_{1}, α_{2}, \dots, α_{n + 1}$ satisfy

(10)

α_{i} \geq 0 i = \bar{1, n + 1}, \sum_{i = 1}^{n + 1} α_{i} > 1

(11)

α_{n + 1} \geq α_{n} \geq \dots \geq α_{2} \geq α_{1},

$i_{2},$ $i_{2}, \dots, i_{n + 1}$ being an arbitrary permutation of the numbers $1, 2, \dots, n + 1$ .

Lemma 2.3.

If $α_{1}, α_{2}, \dots, α_{n + 1}$ satisfy conditions (10) then any of the equations (9) has a unique solution $ω > 1$ . Moreover, if (11) holds and we denote by $a, b, c$ the positive solutions of (7), (8) and (9) then

(12)

1 < b \leq c \leq a,

i.e. equation (7) has the greatest positive solution.

Proof.

Consider one of the $(n + 1)!$ equations of the form (9), denote by $s$ the greatest natural number for which $α_{i_{s}} \neq 0,$ i.e. $α_{i_{s + 1}} = α_{i_{s + 2}} = \dots = α_{i_{n + 1}} = 0$ and consider the function

φ (t) = \frac{R (t)}{t^{n - s + 1}} .

We have $φ (1) = 1 - α_{i_{1}} - α_{i_{2}} - \dots - α_{i_{s}} < 0$ and $lim_{t \to \infty} φ (t) = + \infty,$ whence it follows that the equation $R (t) = 0$ has a solution greater than $1$ . Since the function $ψ (t) = \frac{R (t)}{t^{n + 1}}$ is increasing in the variable $τ = \frac{1}{t}$ , $τ > 0$ it follows that this solution is unique.

In order to prove (12) it will suffice to show that $R (b) \leq 0$ and $R (a) \geq 0$ . Indeed, since $Q (b) = 0$ , we have:

	$R (b) =$	$R (b) - Q (b)$
	$=$	$(a_{1} - a_{i_{1}}) b^{n} + (a_{2} - a_{i_{2}}) b^{n - 1} + \dots + (a_{n} - a_{i_{n}}) b + a_{n + 1} - a_{i_{n + 1}}$
	$=$	$(b - 1) [(a_{1} - a_{i_{1}}) b^{n - 1} + (a_{1} + a_{2} - a_{i_{1}} - a_{i_{2}}) b^{n - 2} + \dots +$
		$+ (a_{1} + a_{2} + \dots + a_{n - 1} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{n - 1}}) b +$
		$+ (a_{1} + a_{2} + \dots + a_{n} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{n}})],$

whence it follows that $R (b) < 0,$ since $b > 1$ and the inequalities

a_{1} + a_{2} + \dots + a_{s} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{s}} \leq 0, s = \bar{1, n}

hold.

The inequality $R (a) \geq 0$ is proved in a similar manner. ∎

3. Iterative methods of interpolatory type

It is known that most of the iterative methods are obtained by inverse interpolation of Lagrange, Taylor or Hermite type.

Let $F = f (I)$ be the image of $I$ by $f$ . We shall suppose that $f$ is derivable on $I$ up to the order $n + 1$ , and $f^{'} (x) \neq 0$ for all $x \in I$ . It then follows that $f : I \to F$ is invertible, so there exists $f^{- 1} : F \to I$ . It is obvious that if $\bar{x}$ is the solution of (1) then

(13)

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

In order to determine an approximation $\tilde{x}$ of $\bar{x}$ it is sufficient to determine a function $h$ which approximates $f^{- 1}$ on a neighborhood $V_{0}$ of $y = 0 .$

(14)

f^{- 1} (y) = h (y) + R (f^{- 1}, y), \forall y \in V_{0},

then we can consider that $\tilde{x} \approx \bar{x}$ with the error

(15)

| \bar{x} - \tilde{x} | = | R (f^{- 1}, 0) |, where \tilde{x} = h (0) .

A simple and efficient method for constructing functions that approximate $f^{- 1}$ on $V_{0}$ is the inverse interpolation. The most general method of this type is the method that lead us to the Hermite inverse interpolatory polynomial.

In order to construct the Hermite inverse interpolatory polynomial in its most general form we must know both the values of $f^{- 1}$ and the values of the derivatives of $f^{- 1}$ at some precized points from $V_{0}$ .

Concerning the successive derivatives of $f^{- 1}$ we shall rely on the following lemma:

Lemma 3.1.

[6]. If $f : I \to F$ is derivable up to the order $n + 1$ and $f^{'} (x) \neq 0$ for all $x \in I$ , then there exists $f^{- 1} : F \to I$ and the following equality holds:

(16)

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

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

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

Let $x_{i} \in I,$ $i = \bar{1, n + 1}$ be $n + 1$ interpolation nodes and $a_{1}, a_{2}, \dots, a_{n + 1} \geq 1$ , $n + 1$ natural numbers. Denote by $m + 1$ their sum:

(17)

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

We also denote $y_{i} = f (x_{i}), i = \bar{1, n + 1}$ and so $f^{- 1} (y_{i}) = x_{i}$ .

For the construction of the Hermite inverse interpolatory polynomial we consider as interpolation nodes the numbers $y_{i} \in F$ , $i = \bar{1, n + 1}$ , and we need a polynomial

H (y_{1}, a_{1}; y_{2}, a_{2}; \dots; y_{n + 1}, a_{n + 1}; f^{- 1} ∣ y) = H (y)

which satisfies

(18)

H^{(j)} (y_{i}) = {(f^{- 1})}^{(j)} (y_{i}), j = \bar{0, a_{i} - 1}, i = \bar{1, n + 1} .

It is well known that such a polynomial has the following form

			$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})}^{(j)} (y_{i}) \frac{1}{k! j!} {[\frac{{(y - y_{i})}^{a_{i}}}{ω (y)}]}_{y = y_{i}}^{(k)} \cdot \frac{ω (y)}{{(y - y_{i})}^{a_{i} - j - k}},$

where

(20)

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

The following equality holds:

(21)

f^{- 1} (y) = H (y_{1}, a_{1}; y_{2}, a_{2}; \dots; y_{n + 1}, a_{n + 1}; f^{- 1} ∣ y) + R (f^{- 1}, y)

where

(22)

R (f^{- 1}, y) = \frac{{(f^{- 1})}^{(m + 1)} (θ)}{(m + 1)!} ω (y),

$θ$ being a point belonging to the smallest interval determined by the points $y, y_{1},$ $y_{2}, \dots, y_{n + 1}$ .

From (3), for $a_{1} = a_{2} = \dots = a_{n + 1} = 1$ , there is obtained the Lagrange inverse interpolatory polynomial, i.e.

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

and for $n = 0$ , again (3) gives the Taylor inverse interpolatory polynomial:

T (y_{1}, f^{- 1} y) = \sum_{j = 0}^{m} \frac{1}{j!} {(f^{- 1})}^{(j)} (y_{1}) {(y - y_{1})}^{j} .

Let $x_{s}, x_{s + 1}, \dots, x_{s + n} \in I$ be $n + 1$ approximations for the solution $\bar{x}$ of equation (1). Then another approximation $x_{s + n + 1}$ can be obtained by

(23)

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

where the function $H$ is given by (3) and the polynomial $ω_{s}$ is given by

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

It can be easily seen that, taking into account (21),

(24)

| f (x_{n + s + 1}) | = | f^{'} (β_{s}) | \frac{| {(f^{- 1})}^{m + 1} (θ_{s}) |}{(m + 1)!} \prod_{i = 0}^{n} {| f (x_{s + i}) |}^{a_{i + 1}}, s = 1, 2, \dots,

if the sequence ${(x_{p})}_{p \geq 0}$ is generated by (23). For all $s \geq 1$ , the numbers $θ_{s}$ belong to the smallest interval determined by $0, y_{s}, y_{s + 1}, \dots, y_{s + n}$ and $β_{s}$ are numbers belonging to the open intervals determined by $\bar{x}$ and $x_{s + n + 1}$ .

Supposing that

c_{s} = | f^{'} (β_{s}) | \frac{{(f^{- 1})}^{(m + 1)} (θ_{s})}{(m + 1)!}, s = 1, 2, \dots

verify the hypotheses of Lemma 2.2 and, moreover, $lim_{s \to \infty} f (x_{s}) = 0$ , then, taking into account Lemma 2.1, it follows that the convergence order of method (23) is given by the positive solution of equation

(25)

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

If $a_{1} = a_{2} = \dots = a_{n + 1} = q,$ then the corresponding iterative method from (23) has the convergence order $ω_{n + 1} (q)$ given by the positive solution of the equation:

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

In [5] there is shown that the number $ω_{n} (q)$ satisfies

$a^{'}$ )

$ω_{n} (q) < ω_{n + 1} (q), n = 1, 2, \dots;$
$b^{'}$ )

$\max {q, \frac{n + 1}{n + 2} (q + 1)} < ω_{n + 1} (q) < q + 1;$
$c^{'}$ )

$lim ω_{n} (q) = q + 1 .$

For $q = 1,$ the properties $a^{'}$ )– $c^{'}$ ) can be found in [3].

For $n = 0$ , the corresponding iterative method has the form

	$x_{s + 1} =$	$x_{s} - \frac{{(f^{- 1})}^{'} (y_{s})}{1!} f (x_{s}) + \frac{1}{2!} {(f^{- 1})}^{''} (y_{s}) f^{2} (x_{s}) + \dots$
		$+ {(- 1)}^{m} \frac{1}{m!} {(f^{- 1})}^{(m)} (y_{s}) f^{m} (x_{s}), s = 1, 2, \dots,$

i.e., the Chebyshev method. It can be easily seen that the convergence order of this method is $m + 1$ .

We propose ourselves to find bounds for the convergence order $ω$ of (23), i.e for the solutions of (25). First we shall prove the following lemma.

Lemma 3.2.

The positive root $ω$ of equation (23) satisfies

(26)

{(m + 1)}^{α} \leq ω \leq 1 + \max_{1 \leq i \leq n} {a_{i}},

where

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

Proof.

Let $β = {(m + 1)}^{α}$ and $P_{n + 1} (t) = t^{n + 1} - a_{n + 1} t^{n} - \dots - a_{2} t - a_{1} .$ For the first part of inequality (26) it will suffice to show that $P_{n + 1} (β) \leq 0$ . Using the inequality between the geometric and the arithmetic mean, i.e.

\frac{\sum_{i = 1}^{n + 1} p_{i} α_{i}}{\sum_{i = 1}^{n + 1} p_{i}} \geq {(\prod_{i = 1}^{n + 1} α_{i}^{p_{i}})}^{\frac{1}{\sum_{i = 1}^{n + 1} p_{i}}}, α_{i} > 0, p_{i} \geq 0, i = \bar{1, n + 1}, \sum_{i = 1}^{n + 1} p_{i} > 0,

we obtain

	$P_{n + 1} (β)$	$= β^{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}} \cdot \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) {(\prod_{i = 1}^{n + 1} β^{(i - 1) a_{i}})}^{\frac{1}{m + 1}} = 0,$

for $β = {(m + 1)}^{α}$ .

For the second inequality in (26) it easily comes that $P_{n + 1} (a) \geq 0$ for $a = 1 + \max_{1 \leq i \leq n + 1} {a_{i}}$ . ∎

4. Interpolatory methods having optimal convergence order

To each permutation of the set ${1, 2, \dots, n + 1}$ there corresponds an iterative method of the form

(27)		$x_{n + 2} =$	$H (y_{i_{1}}, a_{i_{1}}; y_{i_{2}}, a_{i_{2}}; \dots; y_{i_{n + 1}}, a_{i_{n + 1}}; f^{- 1} 0)$
	$x_{n + s + 2} =$	$H (y_{i_{1} + s}, a_{i_{1}}; y_{i_{2} + s}, a_{i_{2}}; \dots; y_{i_{n + 1} + s}, a_{i_{n + 1}}; f^{- 1} 0), s = 1, 2, \dots$

There are $(n + 1)!$ iterative methods. Lemma 2.3 offers the possibility to establish which method of the form (27) has the optimal convergence order.

Theorem 4.1.

Among the $(n + 1)!$ iterative methods of the form $(27)$ the method with the highest convergence order is the one for which

a_{i_{1}} \leq a_{i_{2}} \leq \dots \leq a_{i_{n + 1}} .

The proof of the above theorem is obtained as a directly consequence of Lemma 2.3.

In the following we shall apply the results of Theorem 4.1 to a particular case. For $n = 1$ , by (23) we obtain two iterative methods:

(28)		$x_{3}$	$= H (y_{1}, a_{1}; y_{2}, a_{2}; f^{- 1} 0), x_{1}, x_{2} \in I, y_{1} = f (x_{1}), y_{2} = f (x_{2})$
	$x_{n + 1}$	$= H (y_{n - 1}, a_{1}; y_{n}, a_{2}; f^{- 1} 0), n = 3, 4, \dots$

and

(29)		$x_{3}$	$= H (y_{1}, a_{2}; y_{2}, a_{1}; f^{- 1} 0), x_{1}, x_{2} \in I, y_{1} = f (x_{1}), y_{2} = f (x_{2}) .$
	$x_{n + 1}$	$= H (y_{n - 1}, a_{2}; y_{n}, a_{1}; f^{- 1} 0), n = 3, 4, \dots$

The convergence order $ω_{1}$ of method (28) is given by the positive solution of

t^{2} - α_{2} t - α_{1} = 0

and for (29) the convergence order is the solution of

t^{2} - α_{1} t - α_{2} = 0 .

It is easily seen that if $α_{2} \geq α_{1}$ then $ω_{2} \leq ω_{1}$ , and so the iterative method (28) has a greater convergence order than the one of (29).

References

[1] R. Brent, S. Winograd, F. Wolfe, Optimal iterative processes for root-finding., Numer. Math. 20 (1973), 327–341.
[2] H.T. Kung, J.F. Traub, Optimal order and efficiency for iterations with two evaluations, Numer. Anal., Vol. 13, 1, (1976), 84–99.
[3] A.M. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York and London, (1966).
[4] I. Pǎvǎloiu, ^†^†margin: available soon,
refresh and click here $\to$ Optimal problems concerning interpolation methods of solution of equations, Publ. Inst. Math., 52 (66) (1992), 113–126.
[5] J.F. Traub , Iterative Methods for Solution of Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, (1964).
[6] B.A. Turowicz, Sur les derivées d’ordre superieur d’une fonction inverse, Ann. Polon. Math. 8 (1960), 265–269.

Romanian Academy

”T. Popoviciu” Institute of Numerical Analysis

P.O. Box 68,

3400, Cluj-Napoca

Romania

1997

A bivariate extension of the Bernstein polynomials

February 10, 2023

Analysis of a nonlinear integral equation modelling infection diseases

May 18, 2022

A method for obtaining iterative formulas of higher order for roots of equations

July 16, 2025

On the convergence order of the multistep methods

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

JSTOR permalink

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

ON THE CONVERGENCE ORDER OF THE MULTISTEP METHODS

1. Introduction

2. Convergence order

Definition 2.1.

Remark 2.1.

Lemma 2.1.

Proof.

Lemma 2.2.

Proof.

Lemma 2.3.

Proof.

3. Iterative methods of interpolatory type

Lemma 3.1.

Lemma 3.2.

Proof.

4. Interpolatory methods having optimal convergence order

Theorem 4.1.

References

Related Posts

ON THE CONVERGENCE ORDER
OF THE MULTISTEP METHODS