On some interpolation iterative methods with optimal convergence speed

9 years ago

Abstract

We consider nonlinear equations in $\mathbb{R}$, and a class of iterative methods obtained by inverse interpolation of Hermite type. We determine the methods with the highest convergence order among the methods in the considered class.

Authors

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

Ioan Şerb
(Tiberiu Popoviciu Institute of Numerical Analysis)

Title

Original title (in French)

Sur quelques méthodes itératives de type intérpolatoire à vitèsse de convergence optimale

English translation of the title

On some inverse interpolation iterative methods with optimal convergence speed

Keywords

Keywords: inverse interpolation; Hermite polynomial; inverse Hermite interpolation; iterative method; convergence order

PDF

Scanned paper (on the journal website).

PDF-Latex version of the paper.

Cite this paper as:

I. Păvăloiu, I. Şerb, Sur quelques méthodes itératives de type intérpolatoire à vitèsse de convergence optimale, Anal. Numér. Théor. Approx., 12 (1983) no. 1, pp. 83-88 (in French).

About this paper

Journal

Mathematica – Revue d’Analyse Numérique et de Théorie de l’Approximation
L’Analyse Numérique et la Théorie de l’Approximation

Publisher Name

Academia R.S. Romania

Paper on the journal website

Paper on the journal website.

Print ISSN

1010-3376

Online ISSN

2457-8118

References

[1] Ostrowski, M. A., Solution of Equations and Systems of Equations, Academic Press, New-York and London, 1960.

[2] Pavaloiu, I., Rezolvarea ecuatiilor prin interpolare, Ed. Dacia, 1981.

[3] Pavaloiu, I., Iancu, C., La resolution des equations par interpolation inverse de type Hermite, Seminar of functional analysis and Numerical methods, ”Babes-Bolyai” University, Research Seminaries, Preprint Nr. 4, (1981), 72–84. republished in: Mathematica (Cluj), 26(49) (1984), no. 2, pp. 115–123.

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 some interpolation iterative methods with optimal convergence speed

by
I. Păvăloiu and Ioan Şerb
(Cluj-Napoca)

In this paper we study a class of iterative methods for solving equations of the form:

(1)

f (x) = 0,

Or $f : I \to ℝ$ is a real function of a real variable and $I$ is an interval of the real axis.

Let us designate by $x_{1}, x_{2}, \dots, x_{n + 1}, n + 1$ distinct points of the interval $I$ and by $a_{1}, a_{2}, \dots, a_{n + 1}, n + 1$ natural numbers such as:

(2)

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

Or $m \in ℕ$ .

It is well known that whatever the numbers ${and}_{i}^{j}, j = 0, 1, \dots, a_{i} - 1,$ $i = 1, 2, \dots, n + 1,$ there is only one polynomial $H_{1}$ of degree at most $m$ which verifies the conditions:

(3)

H_{1}^{(j)} (x_{i}) = {and}_{i}^{j}, j = 0, 1, \dots, a_{i} - 1, i = 1, 2, \dots, n + 1 .

The polynomial $H_{1}$ determined by conditions ( 3 ) has the form:

(4)

H_{1} (x) = \sum_{i = 1}^{n + 1} \sum_{j = 0}^{a_{i} - 1} \sum_{k = 0}^{a_{i} - j - 1} {and}_{i}^{j} \frac{1}{k! j!} {[\frac{{(x - x_{i})}^{a_{i}}}{oh (x)}]}_{x = x_{i}}^{(k)} \frac{oh (x)}{{(x - x_{i})}^{a_{i} - j - k}},

(5)

oh (x) = \prod_{i = 1}^{n + 1} {(x - x_{i})}^{a_{i}} .

If we assume that the function $f$ admits a derivative of order $m + 1$ on the interval $I$ and if ${and}_{i}^{j} = f^{(j)} (x_{i}), j = 0, 1, \dots, a_{i} - 1, i = 1, 2, \dots, n + 1,$ SO $H_{1}$ , the Hermite polynomial of the function $f$ , relative to the nodes $x_{i},$ to the orders of multiplicity $a_{i}$ , checks the equality:

(6)

f (x) - H_{1} (x) = \frac{f^{(m + 1)} (x)}{(m + 1)!} oh (x),

Or $x \in I$ .

In the following it is assumed that $f^{'} (x) \neq 0$ regardless of $x \in I$ and we designate by $F = f (I)$ . It follows that $f : I \to F$ is a bijective function and there exists $f^{- 1} : F \to I$ . The inverse function $f^{- 1}$ admits a derivative of order $m + 1,$ for everything $x \in F .$

The order derivative $k, k \leq m + 1$ on one point ${and}_{0} = f (x_{0}), {and}_{0} \in F$ can be calculated by the formula:

(7)

{(f^{- 1})}^{(k)} ({and}_{0}) = \sum \frac{(2 k - i_{1} - 2)! {(1 -)}^{k + i_{1} - 1}}{i_{2}! \dots i_{k}! {(f^{'} (x_{0}))}^{2 k - 1}} {(\frac{f^{'} (x_{0})}{1!})}^{i_{1}} {(\frac{f^{''} (x_{0})}{2!})}^{i_{2}} \dots {(\frac{f^{(k)} (x_{0})}{k!})}^{i_{k}},

where the above sum is extended to all integer and nonnegative solutions of the system:

(8)

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

If we assume that equation ( 1 ) has a root in the interval $I$ , this root is unique because $f^{'} (x) \neq 0$ regardless of $x \in I$ and we will designate it by $\bar{x}$ . So from $f (\bar{x}) = 0$ it follows that $\bar{x} = f^{- 1} (0) .$

In the following, in the expression of the interpolation polynomial given by ( 4 ) we will take as interpolation nodes the values ${and}_{i} = f (x_{i}), i = 1, 2, \dots, n + 1$ and as values ${and}_{i}^{j}$ the values of the derivatives ${(f^{- 1})}^{(j)} ({and}_{i}), i = 1, 2, \dots, n = 1, j = 0, 1, \dots,$ $a_{i} - 1$ . Therefore we obtain the Hermite interpolation polynomial for the inverse function $f^{- 1}$ . This polynomial then has the following form:

(9)

H (and) = \sum_{i = 1}^{n + 1} \sum_{j = 0}^{a_{i} - 1} \sum_{k = 0}^{a_{i} - j - 1} {(f^{- 1})}^{(j)} ({and}_{i}) \frac{1}{k! j!} {[\frac{{(and - {and}_{i})}^{a_{i}}}{oh (and)}]}_{and = {and}_{i}}^{(k)} \frac{oh (and)}{{(and - {and}_{i})}^{a_{i} - j - k}},

(10)

oh (and) = \prod_{i = 1}^{n + 1} {(and - {and}_{i})}^{a_{i}} .

From ( 6 ) the equality results

f^{- 1} (and) - H (and) = \frac{{(f^{- 1})}^{(m + 1)} (or)}{(m + 1)!} oh (and),

Or $or \in F$ .

And $and = 0$ , SO $\bar{x} = f^{- 1} (0)$ And

(11)

\bar{x} - H (0) = \frac{{(f^{- 1})}^{(m + 1)} ({or}_{1})}{(m + 1)!} oh (0),

Or ${or}_{1} and s t$ a point of the smallest interval containing the points:

0, f (x_{1}), \dots, f (x_{n + 1}) .

If we designate by $F_{1}$ this interval and by

M_{m + 1} = sup_{and \in F_{1}} | {(f^{- 1})}^{(m + 1)} (and) |,

| \bar{x} - H (0) | \leq \frac{M_{m + 1}}{(m + 1)!} | oh (0) | .

From ( 10 ) and the fact that ${and}_{i} = f (x_{i}), i = 1, 2, \dots, n + 1$ we deduce

(12)

| \bar{x} - H (0) | \leq \frac{M_{m + 1}}{(m + 1)!} {| f (x_{1}) |}^{a_{1}} \cdot {| f (x_{2}) |}^{a_{2}} \dots {| f (x_{n + 1}) |}^{a_{n + 1}} .

From inequality ( 12 ) it follows that if $x_{1}, x_{2}, \dots, x_{n + 1}$ are in a sufficiently small neighborhood of $\bar{x}$ , SO $\prod_{i = 1}^{n + 1} {| f (x_{i}) |}^{a_{i}}$ will be in a pre-given neighborhood of $0 .$ Therefore, we can assume that $H (0)$ is an approximant of the root $\bar{x}$ of equation ( 1 ).

And $| \bar{x} - H (0) |$ is not small enough, then, by successive iterations we can obtain better approximations. Let us denote by $x_{1}, x_{2}, \dots, x_{n + 1},$ $n + 1$ initial approximations of the root $\bar{x}$ of ( 1 ). Let $x_{n + 2} = H (0) = H ({and}_{1}, a_{1}; \dots; {and}_{n + 1}, a_{n + 1}; 0),$ Or $H ({and}_{1}, a_{1}; {and}_{2}, a_{2}; \dots;$ ${and}_{n + 1}, a_{n + 1}; and)$ is the Hermite interpolation polynomial ( 9 ) of the function $f^{- 1}$ relative to nodes ${and}_{1}, {and}_{2}, \dots, {and}_{n + 1}$ to the respective orders of multiplicity $a_{1}, a_{2}, \dots, a_{n + 1}$ And ${and}_{i} = f (x_{i}), i = 1, 2, \dots, n + 1$ . If we now consider the new node system $x_{2}, x_{3}, \dots, x_{n + 1}, x_{n + 2}$ an obtains a new approximation $x_{n + 3} = H ({and}_{2}, a_{1}; {and}_{3}, a_{2}; \dots; {and}_{n + 2}, a_{n + 1}; 0)$ and so on.

But, if we put the knots away $x_{1}, x_{2}, \dots, x_{n + 1}$ in order $x_{i_{1}}, x_{i_{2}}, \dots,$ $x_{i_{n + 1}}$ we obtain a new sequence of approximations of $\bar{x}$ , given by the formulas

(13)

{\begin{matrix} x_{n + 2} = H ({and}_{i_{1}}, a_{i_{1}}; {and}_{i_{2}}, a_{i_{2}}; \dots; {and}_{i_{n + 1}}; a_{i_{n + 1}}; 0) = H (0) \\ x_{n + s + 2} = H ({and}_{i_{s + 1}}, a_{i_{1}}; \dots; {and}_{i_{n + 1}}, a_{_{n + 1 - s}}; {and}_{n + 2}, a_{i_{n + 2 - s}}; \dots; {and}_{n + s + 1}, a_{i_{n + 1}}; 0), \\ s = 1, 2, \dots, n, \\ x_{n + s + 2} = H ({and}_{s + 1}, a_{i_{1}}; {and}_{s + 2}, a_{i_{2}}; \dots; {and}_{n + s + 1}, a_{i_{n + 1}}; 0), s = n + 1, n + 2, \dots \end{matrix}

Or ${and}_{i} = f (x_{i}), i = 1, 2, \dots$

For each permutation of the numbers $1, 2, \dots, n + 1$ we obtain a sequence of approximations of $\bar{x}$ given by ( 13 ). In all, it $and$ a $(n + 1)!$ sequences of approximations of $\bar{x}$ .

The question is asked to choose among these $(n + 1)!$ suites, the one that ensures the maximum convergence speed.

To solve this problem, we consider the following equations

(14)	$P (t) =$	$t^{n + 1} - a_{n + 1} t^{n} - a_{n} t^{n - 1} - \dots - a_{2} t - a_{1} = 0,$
(15)	$Q (t) =$	$t^{n + 1} - a_{1} t^{n} - a_{2} t^{n - 1} - \dots - a_{n} t - a_{n + 1} = 0,$
(16)	$R (t) =$	$t^{n + 1} - a_{i_{1}} t^{n} - \dots - a_{i_{n}} t - a_{i_{n + 1}} = 0,$

Or $a_{1}, a_{2}, \dots, a_{n + 1} \in R$ check the relationships

(17)		$a_{1} + a_{2} + \dots + a_{n + 1} >$	$1, a_{i} \geq 0, i = 1, 2, \dots, n + 1,$
(18)		$a_{n + 1} \geq$	$a_{n} \geq \dots \geq a_{2} \geq a_{1},$

And $i_{1}, i_{2}, \dots, i_{n + 1}$ is any permutation of $1, 2, \dots, n + 1 .$

Lemme 1.

And $a_{1}, a_{2}, \dots, a_{n + 1}$ verify the relation ( 17 ), then every equation of the form ( 16 ) has a single root greater than unity. If, moreover, $a_{1}, a_{2}, \dots, a_{n + 1}$ verify condition ( 18 ) and if $a, b, c$ are respectively the positive roots of equations ( 14 ), ( 15 ) or ( 16 ), then we have the inequalities

(19)

1 < b \leq c \leq a

Demonstration..

We designate by $s$ the largest number for which $a_{i_{s}} \neq 0$ . SO $a_{i_{s + 1}} = a_{i_{s + 2}} = \dots = a_{i_{n}} = a_{i_{n + 1}} = 0, a_{i_{s}} \neq 0$ . Let us designate by $ψ$ the function defined by $ψ (t) = R (t) / t^{n - s + 1}$ . On a $ψ (1) = 1 - a_{i_{1}} - \dots - a_{i_{s}} < 0$ And $lim_{t \to \infty} ψ (t) = \infty,$ so the equation $ψ (t) = 0$ admits a root greater than unity. Then, the equation $R (t) = 0$ has a root greater than 1. The uniqueness of this root follows immediately by considering the function $f (t) = - t^{n + 1} R (1 \ t)$ which verifies the condition $f^{'} (t) > 0$ For $t > 0$ .

To prove the inequalities ( 19 ) it is enough to show that $R (b) \leq 0$ And $R (a) \geq 0$ . Indeed

	$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} + \dots + a_{n} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{n}}] \leq 0$

because $b > 1$ and from ( 18 ) it results

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

Similarly, we show that $R (a) \geq 0 .$

Be it now $i_{1}, i_{2}, \dots, i_{n + 1}$ a permutation of numbers $1, 2, \dots, n + 1,$ for which the natural numbers $a_{1}, a_{2}, \dots, a_{n + 1}$ which verify the relation ( 2 ) can be arranged in ascending order

(20)

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

The corresponding sequence of nodes is $x_{i_{1}}, x_{i_{2}}, \dots, x_{i_{n + 1}}$ and the corresponding sequence of successive approximations of $\bar{x}$ is given by ( 13 ). If we denote by

(21)

a_{s} = a_{i_{s}}, s = 1, 2, \dots, n + 1

and by

(22)

{in}_{s} = x_{i_{s}}, s = 1, 2, \dots, n + 1,

then the sequence of approximations ( 13 ) becomes ${({in}_{n})}_{n = 1}^{\infty}$ Or

(23)

x_{n + s + 2} = H ({and}_{s + 1}, a_{1}; {and}_{s + 2}, a_{2}; \dots; {and}_{s + n + 1}, a_{n + 1}; 0),

$s = 0, 1, \dots,$ Or ${and}_{i} = f ({in}_{i}), i = 1, 2, \dots .$

Inequality ( 12 ) becomes

(24)

| \bar{x} - H (0) | = | \bar{x} - {in}_{n + 2} | \leq \frac{M}{(m + 1)!} {| f ({in}_{1}) |}^{a_{1}} \dots {| f ({in}_{n + 1}) |}^{a_{n + 1}},

Or $M = sup_{and \in F} | {(f^{- 1})}^{(m + 1)} (and) |$ . If we designate by $b = sup_{x \in I} | f^{'} (x) |$ then from ( 23 ) and ( 24 ) we obtain

(25)

| \bar{x} - {in}_{n + 2} | \leq \frac{M b^{m + 1}}{(m + 1)!} {| \bar{x} - {in}_{1} |}^{a_{1}} \dots {| \bar{x} - {in}_{n + 1} |}^{a_{n + 1}} .

In general, is the elements of the sequence ${({in}_{n})}_{n = 1}^{\infty}$ are in the interval $I$ , SO

(26)

| \bar{x} - {in}_{n + s + 1} | \leq \frac{M b^{m + 1}}{(m + 1)!} {| \bar{x} - {in}_{s} |}^{a_{1}} \dots {| \bar{x} - {in}_{s + n} |}^{a_{n + 1}}

$s = 1, 2, \dots$ . If we write $r_{i} = b \sqrt{\frac{b M}{(m + 1)!}} | \bar{x} - {in}_{i} |, i = 1, 2, \dots,$ then from ( 26 ) we obtain

(27)

r_{n + s + 1} \leq r_{n + s}^{a_{n + 1}} r_{n + s - 1}^{a_{n}} \dots r_{s + 1}^{a_{2}} r_{s}^{a_{1}},

$s = 1, 2, \dots$ .

We now assume that there exists a number $d, 0 < d < 1$ such as

(28)

r_{i} \leq d^{{oh}^{i}}, i = 1, 2, \dots, n + 1,

Or $oh$ is the only positive root of the equation

(29)

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

If we assume that for a $s$ fixed $s \geq 2$ We have

(30)

r_{n + s} \leq d^{x + s},

then from ( 27 ), ( 28 ) and ( 29 ) it immediately follows that

(31)		$r_{n + s + 1}$	$\leq d^{a_{n + 1} {oh}^{n + s}} \cdot d^{a_{n} {oh}^{n + s - 1}} \dots d^{a_{2} {oh}^{s + 1}} \cdot d^{a_{1} {oh}^{s}}$
		$= d^{a_{n + 1} {oh}^{n + s} + a_{n} {oh}^{n + s - 1} + \dots + a_{2} {oh}^{s + 1} + a_{1} {oh}^{s}} = d^{{oh}^{n + s + 1}},$

and by induction it follows that

(32)

r_{n} \leq d^{{oh}^{n}}, n = 1, 2, \dots

The solution $oh$ of equation ( 29 ) is called the order of convergence of the iterative method ( 23 ). We have

(33)

| \bar{x} - {in}_{n} | \leq \frac{1}{b \sqrt[m]{\frac{M b}{(m + 1)!}}} d^{{oh}^{n}}, n = 1, 2, \dots,

from which it follows that $lim_{n \to \infty} {in}_{n} = \bar{x}$ . ∎

We note that the order of convergence of the methods ( 13 ) depends on the positive root $oh$ of equation ( 29 ).

Taking into account the lemma and the above considerations we obtain the following theorem:

Theorem 1 .

Either $i_{1}, i_{2}, \dots, i_{n + 1}$ a permutation of $1, 2, \dots, n + 1$ And $M (i_{1}, i_{2}, \dots, i_{n + 1})$ the corresponding iterative method ( 13 ) . If $a_{i_{1}} \leq a_{i_{2}} \leq \dots \leq a_{i_{n + 1}}$ Or $a_{i_{j}} and s t$ the order of multiplicity of the knot ${and}_{i_{j}} = f (x_{i_{j}}),$ $j = 1, 2, \dots, n + 1,$ then under conditions ( 20 ) method ( 23 ) ensures the order of convergence $oh$ maximum, among the $(n + 1)!$ iterative methods of the form ( 13 ).

Bibliography

[1]
[2] Ostrowski, M. A., Solution of Equations and Systems of Equations, Academic Press, New-York and London, 1960.
[3] ^†^†margin: clickable $\to$ Păvăloiu, I., Solving equations by interpolation , Ed. Dacia, 1981.
[4] ^†^†margin: clickable $\to$ Păvăloiu, I., Iancu, C., The solution of equations by inverse interpolation of Hermite type , Seminar of functional analysis and Numerical methods, ”Babeş-Bolyai” University, Research Seminaries, Preprint Nr. 4, (1981), 72–84.
republished in: Mathematica (Cluj), 26(49) (1984), no. 2, pp. 115–123.

Recu le 5.III.1983

Babeş-Bolyai University Computing Institute

37 Republic Street

3400 Cluj-Napoca

1983

The heat transfer in a viscous unsteady flow through circular ducts

October 31, 2024

Regarding the action of sun and moon on the movement of core of the Earth

November 29, 2018

Iterative methods of interpolation type with optimal speed of convergence

August 6, 2025

On some interpolation iterative methods with optimal convergence speed

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Paper on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On some interpolation iterative methods with optimal convergence speed

Lemme 1.

Demonstration..

Theorem 1 .

Bibliography

Related Posts