The inverse interpolatory polynomials of Hermite type with 2 nodes, allhaving the same order of multiplicity \(q\in N\), provide a class of iterative methods for solvingscala-r’ equations. In this note we determine the iterative method with the highest efficiencyindex: the optimal method is obtained for \(q=2\).
(soon)
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)
[1] BRENT, R., WINOGRAD, S., WOLFE, F., Optimal Iterative Processes for Root-Finding, Numer. Math., 20, pp.327-341, 1973.
[2] COMAN, GH., Some Practical Approximation Methods for nonlinear Equations, Matematica-Revue d’Analyse Numerique et de Theorie de l’Approximation, 11, no.1-2, pp.11-48, 1982.
[3] KUNG, H.T., TRAUB, J.F., Optimal Order and Efficiency for Iterations with Two Evaluations, SIAM J. Numer. Anal., 13, no.1, pp. 84-99, 1976.
[4] OSTROWSKI, A.M., Solution of Equation and Systems of Equations, Academic Press, New York and London, 1966.
[5] Păvăloiu, I., Bilateral Approximation for the Soltuions of Scalar Equations, Revue D’Analyse Numerique et de Theorie del’Approximation, 23, 1, pp.95-100, 1994.
[6] Păvăloiu, I., Optimal Problems Concerning Interpolation Methods of Solutions of Equations, Publ. Inst. Math. 52 (66), pp.113-126, 1992.
[7] Păvăloiu,I., Optimal Efficiency Index for Iterative Methods of Interpolatory Type, Computer Science Journal of Moldova, 5, nr.1 (13), pp.20-43, 1997.
[8] TRAUB, J.F., Iterative methods for slution of equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[9] TUROWICZ, B.A., Sur les derivees d’ordre superieur d’une fonction inverse, Ann.Polon. Math., 8, pp.265-269, 1960.
/*======================================================================
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; }
The Optimal Efficiency Index of a Class of Hermite Iterative Methods with Two Steps
The Optimal Efficiency Index of a Class of Hermite Iterative Methods with Two
Steps
ION PĂVĂLOIU
Abstract.
The inverse iterpolatory polynomials of Hermite type with two nodes, all having the same
order of multiplicity , provide a class of iterative methods for
solving scalar equations. In this note we determine the iterative method with
the highest efficiency index: the optimal method is obtained for .
2000 AMS Subject Classification: 65H05, 65Y20.
1. Introduction
As we have shown in [8], the problem of determining the Hermite
interpolatory iterative methods having the optimal efficiency index cannot be
solved in the general case. We have determined however in [8] some
upper and lower bounds for the efficiency indexes; these bounds depend on the
coefficients of the characteristical equation whose positive root provide the
convergence order of the considered equation.
In this note we shall consider a subclass of Hermite interpolatory methods,
based on two interpolatory nodes which have the same multiplicity order
We shall use the efficiency index defined in [5]
for determining the method with the optimal efficiency index.
Let and consider the equation
We assume that this equation has a unique solution For solving the above equation we consider a function
and we also assume that is the unique fixed
point of in
For approximating there is usually taken an element from the
sequence generated by the iterative method:
| (2) |
|
|
|
More generally, if is a function of variables whose
restriction to the diagonal of the set coincides with then the
following sequence may be considered for approximating
| (3) |
|
|
|
The convergence of the sequence generated by
(2) or (3) depends on certain properties of the functions
and resp. . The time needed by a computer to obtain a convenient
approximation of depends on the convergence order of the
sequence and also on the number of
elementary operations performed at each iteration step.
While the convergence order may be determined exactly in most of the
situations, the number of elementary operations may be hard to evaluate.
For this reason Ostrowski has proposed in [5] a simplification of
this problem, by considering the number of function evaluations needed at each
iteration step. This leads to the definition of the efficiency index, which
may be naturally applied to the comparison of different methods.
Consider a sequence which together with
and satisfies:
-
a)
-
b)
-
c)
the sequence converges
also to
-
d)
-
e)
-
f)
for all there exists such that where denotes the divided
differences of at the nodes and
Concerning the convergence order of we
shall consider the following definition:
Definition 1.
[5]
The sequence has the convergence order
with respect to the function if
there exists the limit
|
|
|
and
Lemma 2.
[8]
If the sequence and the functions
and satisfy conditions a)–f), then the necessary and
sufficient condition for the sequence to
have the convergence order with respect
to is that there exists the limit
|
|
|
and
Lemma 3.
[8]
If is a sequence of real positive
numbers satisfying
-
i)
the sequence converges to ;
-
ii)
There exist the nonnegative real numbers and a bounded sequence of real positive numbers
and the following equalities hold:
|
|
|
-
iii)
The sequence is
convergent and
then is the positive root of the equation
|
|
|
We shall denote in the following by the number of function evaluations
that must be performed at the step for the iteration (2) or
(3).
Taking into account Lemmas 2 and 3, the following definition
becomes natural:
Definition 4.
[5]
The real number is called the efficiency index of the method
(2) (resp.(3)) if there exists
|
|
|
and
2. Two step Hermite interpolatory iterative methods
Let be a natural number and consider the Hermite
inverse interpolatory polynomial on two nodes with the same multiplicity order
We shall make the following assumptions concerning the function
-
)
is derivable on up to and including the
-th order;
-
)
for all ;
-
)
equation (1) has a solution
Under these assumptions, it is clear that admits an inverse where and also that
is given by relation
Moreover, is derivable up to the order at all points from
and the -th derivative, for is given
by [10]
| (5) |
|
|
|
where we have denoted and the above sum extends on
the nonnegative whole solutions of the system
|
|
|
|
|
|
|
|
Denote by the Hermite inverse
interpolatory polynomial satisfying
| (6) |
|
|
|
where and
Consider also the polynomial
The residual in the interpolation formula becomes then
|
|
|
|
|
|
|
|
where belongs to the smallest open interval determined by the
points and
Let be two approximations of the solution Then the next approximation may be determined by
| (7) |
|
|
|
We shall assume that all the elements of the sequence generated by (7) belong to the interval
Taking into account the above assumptions we easily get for that
|
|
|
where belongs to the open interval determined by the points
and and is contained in the open
interval determined by
Assuming that for all denoting
|
|
|
and applying Lemma 3, we obtain the following equation for determining
the convergence order of method (7):
It follows that the convergence order is
3. The Optimal efficiency index
We remark that in order to generate the elements of the sequence given by (7), at each iteration step
the following function evaluations are needed:
all at since their values at are known from the previous
step. Hence there are needed function evaluations.
We have proved the following theorem:
Theorem 5.
Among all the iterative methods (7), the method with the highest
efficiency index is the one corresponding to being given by
| (11) |
|
|
|
Finally we give for an expression based on the divided differences on
double nodes (see [7])
| (12) |
|
|
|
|
|
|
|
|
where
For computing the divided differences from (12) one can use the
recurrence formula for divided differences with the aid of the following table:
where
|
|
|
and
|
|
|
References
-
[1]
-
[2]
R. Brent, S. Winograd, F. Wolfe, Optimal iterative
processes for root-finding, Numer.Math. 20 (1973), pp. 327–341.
-
[3]
Gh. Coman,
††margin:
available soon,
refresh and click here
Some practical approximation methods for
nonlinear equations, Anal. Numér. Théor. Approx., vol. 11,
nos.1–2, (1982), pp. 41–48.
-
[4]
H.T. Kung, J.F. Traub, Optimal order and efficiency
for iterations with two evaluations, SIAM J. Numer. Anal., 13, no.
1, (1976), pp.84–99.
-
[5]
A.M. Ostrowski, Solution of Equation and Systems of
Equations, Academic Press, New York and London, (1966).
-
[6]
††margin:
clickable
I. Păvăloiu,
Bilateral approximations for the
solutions of scalar equations, Rev. Anal. Numér. Théor. Approx.,
23, 1, (1994), pp. 95–100.
-
[7]
††margin:
clickable
I. Păvăloiu,
Optimal problems concerning
interpolation methods of solutions of equations, Publ. Inst. Math.,
52(66) (1992), pp. 113–126.
-
[8]
††margin:
clickable
I. Păvăloiu,
Optimal efficiency index for
iterative methods of interpolatory type, Computer Science J. Moldova,
5, no.1 (13), (1997), pp. 20–43.
-
[9]
Traub J.F., Iterative Methods for Solution of
Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
-
[10]
Turowicz B.A., Sur les derivées d’ordre superieur
d’une fonction inverse, Ann. Polon. Math. 8 (1960), pp. 265–269.
Received September 10, 1999.
”Tiberiu Popoviciu” Institute of
Numerical Analysis
str. Republicii 37
P.O.Box 68-1
