Solving equations by Hermite type inverse interpolation

9 years ago

Abstract

We study the convergence of an iterative method for solving the equation (fleft( xright) =0, f:Isubseteq mathbb{Rrightarrow R}). The iterative method is obtained by the Hermite inverse interpolation polynomial. We show that the convergence order of this method is given by the unique positive solution of a polynomial equation with coefficients given by the multiplicity orders. We consider the particular instance of two interpolation nodes and we determine the resulted methods.

Authors

Crăciun Iancu
(Tiberiu Popoviciu Institute of Numerical Analysis)

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

Title

Original title (in French)

La resolution des équations par interpolation inverse de type Hermite

English translation of the title

Solving equations by Hermite inverse interpolation

Keywords

Hermite interpolation; inverse interpolation; nonlinear equations in R; iterative methods; multistep method; convergence order

PDF

Scanned paper.

PDF-Latex version of the paper.

Cite this paper as:

C. Iancu, I. Păvăloiu, La resolution des équations par interpolation inverse de type Hermite, Mathematica (Cluj), 26(49) (1984) no. 2, pp. 115-123 (in French).

About this paper

Journal

Mathematica

Publisher Name

DOI

Not available yet.

Print ISSN

Not available yet.

Online ISSN

Not available yet.

References

[1] I.G. Berezin, P.N. Zidkov, Metody vycislenii, I. Moskow, 1962.

[2] Gh. Coman, Some practical approximation methods for nonlinear equations, Anal. Numer. Theor. Approx., 11, 1-2, (1982), 41–48.

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

[4] I. Pavaloiu, Rezolvarea ecua¸iilor prin interpolare, Ed. Dacia, 1981.

[5] I. Pavaloiu, Introducere in aproximarea solutiilor ecuatiilor, Ed. Dacia, 1976.

[6] D.D. Stancu, Asupra formulei de interpolare a lui Hermite si a unor aplicatii ale acesteia, Studii ¸si Cercet. Mat. (Cluj), 3-4 VIII, (1957), 339-355.

[7] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice Hall Series in Automatic Computation 1964.

[8] B.A. Turowicz, Sur les derivees d’ordre superiour d’une fonction inverse, Colloq. Math., (1959), 83–87.

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; }

Solving equations by Hermite type inverse interpolation

by
C. Iancu and I. Păvăloiu

1.

In this work we study some numerical 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.

We designate by $AND$ a set of $n + 1$ distinct real numbers of the set $I,$ that's to say, $AND = {x_{1}, x_{2}, \dots, x_{n + 1}}$ Or $x_{i} \neq x_{j}$ For $i \neq j, i, j = 1, 2, \dots, n + 1 .$

Let us designate by

(2)

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

$n + 1$ natural numbers that satisfy the condition:

(3)

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

Or $m \in ℕ$ , and by

(4)

{and}_{i}^{j}; j = 0, 1, \dots, a_{i} - 1; i = 1, 2, \dots, n + 1,

$m + 1$ given real numbers.

The following theorem is well known.

Theorem 1 .

The $and$ has a single polynomial $P$ of at least degree $m,$ which verifies the following conditions:

(5)

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

The polynomial $P$ has the following form:

(6)

P (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)} \cdot \frac{oh (x)}{{(x - x_{i})}^{a_{i} - j - k}},

(7)

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

If we assume that the function $f$ admits derivatives up to order $m + 1$ inclusive in 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,$ then the remainder of the Hermite interpolation formula satisfies the following equality:

(8)

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

Or $x \in I .$

Let's suppose that $f^{'} (x) \neq 0,$ for each $x \in I$ and designate by $F = f (I),$ the image of the interval $I$ by function $f .$ From the above hypothesis it follows that the function $f : I \to F$ is bijective, that the function $f^{- 1} : F \to I$ admits derivatives up to order $m + 1$ inclusive in the interval $F .$ The order derivative $k$ $(k \in ℕ, k \leq m + 1)$ at one point ${and}_{0} = f (x_{0}), {and}_{0} \in F$ has the following form [ 4 ] , [ 8 ] :

(9)

{[f^{- 1} ({and}_{0})]}^{(k)}

= \sum \frac{(2 k - 2 - i_{1})! {(- 1)}^{k - 1 + i_{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} \dots {(\frac{f^{(k)} (x_{0})}{k!})}^{i_{k}}

where the above sum extends to all integer, non-negative solutions of the system of equations:

(10)

{\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 $\bar{x} \in I,$ then of $f (\bar{x}) = 0$ it follows that $f^{- 1} (0) = \bar{x},$ and of $f^{'} (x) \neq 0$ for each $x \in I$ it follows that $\bar{x}$ is unique.

If in the expression of the Hermite interpolation polynomial ( 6 ) we choose for the interpolation nodes the values ${and}_{i} = f (x_{i}), i = 1, 2, \dots, n + 1$ and for the values of the function and its derivatives the numbers $f^{- 1} ({and}_{i}) = x_{i}, i = 1, 2, \dots, n + 1,$ respectively ${[f^{- 1} ({and}_{i})]}^{(j)}, j = 1, 2, \dots, a_{i} - 1; i = 1, 2, \dots, n + 1,$ then we obtain the Hermite interpolation polynomial of the function $f^{- 1} .$ This polynomial will have the following form:

(11)

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

(12)

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

The polynomial defined by the relation ( 11 ) is called the inverse Hermite interpolation polynomial.

From equality ( 8 ) it follows:

(13)

f^{- 1} (and) - P (and) = \frac{{[f^{- 1} (or)]}^{(m + 1)}}{(m + 1)!} \cdot oh (and), or \in F .

Taking into account that $f^{- 1} (0) = \bar{x},$ ( 13 ) gives us

(14)

\bar{x} - P (0) = \frac{{[f^{- 1} ({or}_{1})]}^{(m + 1)}}{(m + 1)!} \cdot oh (0)

Or ${or}_{1}$ is contained in the smallest interval that contains the points: $0, f (x_{1}), \dots, f (x_{n + 1}) .$ If we designate by $F_{1}$ the interval above and by $M_{m + 1}$ the number $M_{m + 1} = sup_{and \in F_{1}} | {[f^{- 1} (and)]}^{(m + 1)} |$ then we deduce from ( 14 )

(15)

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

If the points of the set $AND$ are close enough to $\bar{x}$ , then the numbers $f (x_{1}), f (x_{2}), \dots, f (x_{n + 1})$ are close to zero. Even more so the number $\prod_{i = 1}^{n + 1} {| f (x_{i}) |}^{a_{i}}$ is close to zero and the choice of $P (0)$ as an approximation for the root $\bar{x}$ of equation ( 1 ) is justified. Therefore

(16)

\bar{x} ≃ P (0) .

2. Iterative methods obtained using the inverse Hermite interpolation polynomial

Si l’approximation $P (0)$ of $\bar{x}$ given by ( 16 ) is not suitable, then by successive iterations we can obtain in certain cases approximations closer and closer to the root.

Let us designate by

(17)

x_{1}, x_{2}, \dots, x_{n + 1}

$n + 1$ initial approximations of the root $\bar{x}$ of equation ( 1 ). Using these approximations we construct the sequence ${(x_{p})}_{p = 1}^{\infty}$ given by the following iterative process:

(18)

x_{n + s + 1} = P_{n + s} (0),

Or $P_{n + 1} (0) = P (0), P$ has the expression given by ( 11 ) and $P_{n + s}$ has the following expression:

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

(20)

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

In the following we study the convergence of the sequence ${(x_{p})}_{p = 1}^{\infty}$ generated by the iterative process ( 18 ). We denote by

M = sup_{and \in F} | {[(f^{- 1} (and))]}^{(m + 1)} | And b = sup_{x \in I} | f^{'} (x) |,

then from ( 14 ) and ( 18 ) it results:

(21)

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

More generally if the elements of the sequence ${(x_{p})}_{p = 1}^{\infty}$ are contained in the interval $I,$ we have the following inequalities:

(22)		$\| \bar{x} - x_{n + s + 1} \|$	$\leq \frac{M b^{m + 1}}{(m + 1)!} {\| \bar{x} - x_{s} \|}^{a_{1}} \cdot {\| \bar{x} - x_{s + 1} \|}^{a_{2}} \dots {\| x - x_{s + n} \|}^{a_{n + 1}}$
	$s$	$= 1, 2, 3, \dots .$

By multiplying the terms of ( 22 ) by $b \sqrt[m]{\frac{b M}{(m + 1)!}}$ and we designate by $r_{i}$ the number

r_{i} = b \sqrt[m]{\frac{b M}{(m + 1)!}} \cdot | \bar{x} - x_{i} |, i = 1, 2, \dots,

the inequalities ( 22 ) become:

(23)

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 assume in the following:

(24)

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

Or $oh$ is the positive root of the equation

(25)

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

And $0 < d < 1 .$

If we assume

(26)

r_{n + s + 1} \leq d^{{in}_{n + s + 1}}, s = 1, 2, \dots,

then taking into account ( 23 ) and ( 25 ) we have

(27)

{in}_{n + s + 1} = a_{n + 1} {in}_{n + s} + a_{n} {in}_{n + s - 1} + \dots + a_{2} {in}_{s + 1} + a_{1} {in}_{s}

It follows from ( 24 ) that

(28)

{in}_{i} = {oh}^{i}, i = 1, 2, \dots, n + 1 .

It is easy to show that equation ( 25 ) has a single real and positive root $oh > 1 .$ Then from ( 27 ), ( 26 ), ( 28 ) and taking into account that $oh$ is the root of the equation ( 25 ) we deduce the following equalities:

(29)

{in}_{n + s + 1} = {oh}^{n + s + 1}, s = 1, 2, 3, \dots,

that's to say

(30)

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

From equality ( 3 ) it follows that $oh > 1$ And $lim_{s \to \infty} r_{n + s + 1} = 0 .$ Therefore

lim_{s \to \infty} | \bar{x} - x_{n + s + 1} | = 0,

what needed to be demonstrated.

The expression of $r_{n + s + 1}$ provides the following assessment:

(31)

| \bar{x} - x_{n + s + 1} | \leq \frac{1}{b \sqrt[m]{\frac{b M}{(m + 1)!}}} \cdot d^{{oh}^{n + s + 1}}

3. The special case $n = 1 .$

Let us designate by $a_{1}, a_{2}$ two numbers of $N$ such as $a_{1} + a_{2} = m + 1$ , and by $x_{1}, x_{2}$ two points of the interval $I .$ Suppose that in each point $x_{i}, i = 1, 2$ we know the values of the function $f$ and its successive derivatives up to the order $a_{1} - 1, a_{2} - 1$ respectively.

Using formula ( 9 ) we can calculate the values of the function $f^{- 1}$ in the points ${and}_{1} = f (x_{1}), {and}_{2} = f (x_{2})$ and the values of these successive derivatives up to the order $a_{1} - 1, a_{2} - 1$ respectively.

The inverse Hermite interpolation polynomial over knots ${and}_{1}, {and}_{2}$ will have the following form:

(32)

P (and)

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

(33)

oh (and) = {(and - {and}_{1})}^{a_{1}} \cdot {(and - {and}_{2})}^{a_{2}} .

Taking in ( 32 ) $and = 0$ we obtain a first approximation of the root $\bar{x}$ of equation ( 1 ). If we denote by $x_{3}$ this approximation then we have:

(34)		$\bar{x}$	$\approx x_{3} = \sum_{i = 1}^{2} \sum_{j = 0}^{a_{i} - 1} \sum_{k = 0}^{a_{i} - j - 1} {(f^{- 1} ({and}_{i}))}^{(j)} \cdot \frac{1}{k! j!} \cdot {[\frac{{(and - {and}_{i})}^{a_{i}}}{oh (and)}]}_{and - {and}_{i}}^{(k)} \cdot \frac{{(- 1)}^{a_{i} - j - k} \cdot oh (0)}{{and}_{i}^{a_{i} - j - k}}$
		$\cdot$

From ( 34 ) and ( 14 ) we deduce

(35)

| \bar{x} - x_{3} | \leq M {| f (x_{1}) |}^{a_{1}} \cdot {| f (x_{2}) |}^{a_{2}}, M = sup_{or \in f (I)} \frac{| {(f^{- 1} (or))}^{(m + 1)} |}{(m + 1)!}

Using equality

(36)

| \bar{x} - x_{3} | = \frac{| f (x_{3}) |}{| [\bar{x}, x_{3}; f] |},

where by $[\bar{x}, x_{3}; f]$ we denote the divided difference of the function $f$ on the knots $\bar{x}, x_{3};$ we deduce from ( 35 ) the following inequality:

(37)

| f (x_{3}) | \leq K {| f (x_{1}) |}^{a_{1}} \cdot {| f (x_{2}) |}^{a_{2}}

Or $K \geq | M \cdot [x, and; f] |, x, and \in I .$

If we consider the numbers $x_{1}$ And $x_{2}$ as initial approximations for the root $\bar{x}$ from equation ( 1 ), we obtain from ( 19 ) for $and = 0$ a sequel ${(x_{n})}_{n = 1}^{\infty}$ , with

(38)		$x_{s + 1} =$
	$= \sum_{i = 1}^{2} \sum_{j = 0}^{a_{i} - 1} \sum_{k = 0}^{a_{i} - j - 1} {(f^{- 1} ({and}_{s + i - 1}))}^{(j)} \frac{1}{k! j!} {[\frac{{(and - {and}_{s + i - 1})}^{a_{i}}}{{oh}_{s} (and)}]}_{and = {and}_{s + i - 1}}^{(k)} \frac{{(- 1)}^{a_{i} - j - k} {oh}_{s} (0)}{{and}_{s + i - 1}^{a_{i} - j - k}}$

(39)

{oh}_{s} (and) = {(and - {and}_{s - 1})}^{a_{1}} \cdot {(and - {and}_{s})}^{a_{2}}, s = 2, 3, \dots

Assuming that all elements of the sequence ${(x_{n})}_{n = 1}^{\infty}$ are contained in the interval $I,$ we have the following inequalities:

(40)

| f (x_{n + 2}) | \leq K {| f (x_{n}) |}^{a_{1}} \cdot {| f (x_{n + 1}) |}^{a_{2}}, n = 1, 2, \dots

If we multiply the inequalities ( 40 ) by $K^{\frac{1}{m}}$ and if we take into account that $a_{1} + a_{2} = m + 1$ we get:

(41)

K^{\frac{1}{m}} | f (x_{n + 2}) |

\leq {[K^{\frac{1}{m}} | f (x_{n}) |]}^{a_{1}} \cdot {[K^{\frac{1}{m}} | f (x_{n + 1}) |]}^{a_{2}}, n = 1, 2, \dots

In the following we designate by $r_{i}$ the names

(42)

r_{i} = K^{\frac{1}{m}} | f (x_{i}) |, i = 1, 2, \dots

Then the inequalities ( 41 ) become:

(43)

r_{n + 2} \leq r_{n}^{a_{1}} \cdot r_{n + 1}^{a_{2}}, n = 1, 2, \dots

We will assume that

(44)

{\begin{matrix} r_{1} \leq d^{{oh}_{1}} \\ r_{2} \leq d^{{oh}_{2}} \end{matrix}

Or $0 < d < 1$ And ${oh}_{1}$ is the positive root of the equation

(45)

t^{2} - a_{2} t - a_{1} = 0 .

From ( 43 ) we deduce:

(46)

r_{n} \leq d^{{in}_{n}}

where the sequel ${({in}_{n})}_{n = 1}^{\infty}$ checks for equalities

(47)		${in}_{n + 2}$	$= a_{2} {in}_{n + 1} + a_{1} {in}_{n}, n = 1, 2, \dots$
	${in}_{1}$	$= {oh}_{1}, {in}_{2} = {oh}_{1}^{2} .$

From ( 45 ) we deduce:

(48)

{oh}_{1} = \frac{a_{2} + \sqrt{a_{2}^{2} + 4 a_{1}}}{2}

in which case ( 47 ) gives

(49)

{in}_{n} = {oh}_{1}^{n}, n = 1, 2, \dots .

Deduced for $r_{n}$ the following assessments:

(50)

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

The previous inequality and ( 42 ) imply:

(51)

| f (x_{n}) | \leq K^{- \frac{1}{m}} \cdot d^{{oh}_{1}^{n}} .

By designating by $a$ the number

(52)

a = inf_{x, and \in [x_{1}, x_{2}]} | [x, and; f] |

and assuming $a > 0,$ we deduce from ( 51 )

(53)

| \bar{x} - x_{n} | \leq \frac{1}{a} | f (x_{n}) | \leq \frac{1}{a} K^{- \frac{1}{m}} \cdot d^{{oh}_{1}^{n}}, n = 1, 2, \dots

which represents an evaluation of the error after $n - 2$ no iteration.

Passing to limit when $n \to \infty$ we deduce from ( 53 )

(54)

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

and from ( 51 ) it results, from the fact that $f$ is a continuous function, $f (x) = 0 .$

In the following we will present an analysis of the convergence speed of the sequence ${(x_{n})}_{n = 1}^{\infty}$ given by ( 38 ). To do this we note that if we consider in the Hermite interpolation polynomial the knot $x_{1}$ having the order of multiplicity $a_{2},$ and the knot $x_{2}$ having the order of multiplicity $a_{1},$ the equation which gives us the speed of convergence of the sequence ${(x_{n})}_{n = 1}^{\infty}$ ( 45 ) will take the form:

(55)

t^{2} - a_{1} t - a_{2} = 0 .

It can be easily demonstrated that, if $a_{1} \leq a_{2} and t$ and ${oh}_{2}$ is the positive root of equation ( 55 ), then:

(56)

{oh}_{2} \leq {oh}_{1} .

From the above considerations we conclude that the maximum order of convergence is obtained when in the two-node Hermite type inverse interpolation the multiplicity order of $x_{1}$ is at least equal to the order of multiplicity of $x_{2} .$ It goes without saying that in the above conclusion we assumed that the elements of the sequence ${(x_{n})}_{n = 1}^{\infty}$ are obtained using the relation ( 38 ).

In the following we present two special cases of the Hermite inverse interpolation polynomial and the related iterative methods.

1. $a_{1} = a_{2} = 1 .$

In this case the inverse Hermite interpolation polynomial has the following form:

(57)

P_{1} (and) = \frac{1}{{and}_{1} - {and}_{2}} [(and - {and}_{2}) f^{- 1} ({and}_{1}) - (and - {and}_{1}) f^{- 1} ({and}_{2})] .

Taking into account that $f^{- 1} ({and}_{1}) = x_{1}$ And $f^{- 1} ({and}_{2}) = x_{2}$ and doing in ( 57 ) $and = 0$ we obtain the first approximation of $\bar{x}$ given by the relation:

(58)

x_{3} = x_{1} - \frac{x_{2} - x_{1}}{f (x_{2}) - f (x_{1})} \cdot f (x_{1}) .

Proceeding step by step we obtain the following: ${(x_{n})}_{n = 1}^{\infty}$ given by the relation:

(59)

x_{n + 2} = x_{n} - \frac{x_{n + 1} - x_{n}}{f (x_{n + 1}) - f (x_{n})} \cdot f (x_{n}), n = 1, 2, \dots,

which represents the rope method. In this case the following ${(x_{n})}_{n = 1}^{\infty}$ has the order of convergence ${oh}_{1} = (1 + \sqrt{5}) / 2 .$

2. $a_{1} = 1, a_{2} = 2 .$ [2].

The inverse Hermite interpolation polynomial in this case takes the following form:

(60)		$P_{2} (and) =$	${(f^{- 1} ({and}_{2}))}^{'} \cdot \frac{(and - {and}_{1}) (and - {and}_{2})}{{and}_{2} - {and}_{1}} +$
		$+ f^{- 1} ({and}_{2}) \frac{and - {and}_{1}}{{and}_{2} - {and}_{1}} (1 + \frac{and - {and}_{2}}{{and}_{1} - {and}_{2}}) + f^{- 1} ({and}_{1}) \cdot \frac{{(and - {and}_{2})}^{2}}{{({and}_{1} - {and}_{2})}^{2}} .$

Taking into account equalities $f^{- 1} ({and}_{1}) = x_{1}, f^{- 1} ({and}_{2}) = x_{2}$ And ${(f^{- 1} ({and}_{2}))}^{'}$ $= 1 / f^{'} (x_{2}),$ and by doing in ( 60 ) $and = 0,$ we deduce:

(61)

x_{3} = x_{1} - \frac{x_{2} - x_{1}}{f (x_{2}) - f (x_{1})} f (x_{1}) + \frac{f (x_{2}) - f (x_{1}) - (x_{2} - x_{1}) f^{'} (x_{2})}{{(f (x_{2}) - f (x_{1}))}^{2} f^{'} (x_{2})} f (x_{1}) f (x_{2}) .

Proceeding step by step we obtain the following: ${(x_{n})}_{n = 1}^{\infty}$

(62)		$x_{n + 2} =$	$x_{n} - \frac{x_{n + 1} - x_{n}}{f (x_{n + 1}) - f (x_{n})} f (x_{n})$
		$+ \frac{f (x_{n + 1}) - f (x_{n}) - (x_{n + 1} - x_{n}) f^{'} (x_{n + 1})}{{(f (x_{n + 1}) - f (x_{n}))}^{2} \cdot f^{'} (x_{n + 1})} f (x_{n}) f^{'} (x_{n + 1}),$

Or $n = 1, 2, \dots$

The order of convergence of this method is ${oh}_{1} = 1 + \sqrt{2} .$

Bibliography

[1] I.G. Berezin, P.N. Zidkov, Computation Methods , I. Moscow, 1962.
[2] Gh. Coman, ^†^†margin: clickable $\to$ Some practical approximation methods for nonlinear equations, Anal. Numér. Théor. Approx., 11, 1-2, (1982), 41–48.
[3] M.A. Ostrowski, Solution of Equations and Systems of Equations, Academic Press New York - London, 1960.
[4] I. Pavaloiu, ^†^†margin: clickable $\to$
clickable $\to$
clickable $\to$ Solving equations by interpolation , Ed. Dacia, 1981.
[5] I. Păvăloiu, Introduction to the approximation of solutions of equations , Ed. Dacia, 1976.
[6] DD Stancu, On Hermite's interpolation formula and some of its applications , Studii si Cercet. Mat. (Cluj), 3-4 VIII, (1957), 339-355.
[7] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice Hall Series in Automatic Computation 1964.
[8] BA Turowicz, On the higher order derivatives of an inverse function , Colloq. Math., (1959), 83–87.

Received on 06.06.1982

Institute of Computing

3400 Cluj-Napoca, Romania

1984

Strongly proximinal sets in abstract spaces

August 6, 2025

A mean theorem concerning the behaviour of some nonlinear functionals

May 19, 2022

Sequential regularity and the directional differentiability of convex operators are equivalent

August 5, 2025

Solving equations by Hermite type inverse interpolation

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Solving equations by Hermite type inverse interpolation

1.

Theorem 1 .

2. Iterative methods obtained using the inverse Hermite interpolation polynomial

3. The special casen=1.

Bibliography

Related Posts

3. The special case $n = 1 .$