On optimal iterative methods

9 years ago

Abstract

Let $\left( X,\rho \right)$ be a complete matrix space, the nonlinear mapping $\varphi:I\subset X\rightarrow X$ and the equation $x=\varphi \left(x\right) $ with solution $x^{\ast}$. We consider another application, $F:X^{k}\rightarrow X$ for which we assume the diagonal coincides with $\varphi$: $F(x,…,x)=\varphi(x)$. In order to solve the mentioned equation we consider the iterative method \[x_{n+1}=F\left(x_{n},x_{n-1},\cdots,x_{n-k+1}\right),\] $n=k-1,k,…$ Let $i_{0},i_{1},….,i_{k-1}$ be a permutation of the numbers $0,1,…,k-1$ and therefore $i_{0}-n-k-1,~i_{1}+n-k+1,…,i_{k-1}+n-k+1$ a permutation of the numbers $n-k+1,\ n-k+2,…,n$. Among the class of methods given by \[x_{n+1}=F\left( x_{i_{0}+n-k+1},x_{i_{1}+n-k+1},…,x_{i_{k-1}+n-k+1}\right) \] we determine the method for which the difference $\mathcal{\rho}\left( x^{\ast},x_{n+1}\right)$ is the smallest.

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 des méthodes itératives optimales

English translation of the title

On optimal iterative methods

Keywords

multistep successive approximations; optimal iterative methods

PDF

Scanned paper.

PDF-Latex version of the paper.

Cite this paper as:

I. Păvăloiu, I. Şerb, Sur des méthodes itératives optimales, Seminar on functional analysis and numerical methods, Preprint no. 1 (1983), pp. 175-182 (in French).

About this paper

Journal

Seminar on Functional Analysis and Numerical Methods
Preprint

Publisher Name

“Babes-Bolyai” University
Faculty of Mathematics and Physics
Research Seminars

DOI

Not available yet.

References

[1] I. Pavaloiu, Introducere in teoria aproximarii solutiilor ecuatiilor, Ed. Dacia, Cluj-Napoca, 1976.

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

[3] Weinischke, J. H., Uber eine Klasse von Iterationsverfahren, Num. Math., 6 (1964), 395–404.

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

"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

Preprint Nr.1, 1983, pp. 175-182

On Optimal Iterative Methods

by
Ion Pavaloiu and Ioan Serb

In this work we study iterative methods for solving the equation:

(1)

x = f (x),

Or $f : I \to X$ is a given application and $(X, r)$ is a complete metric space.

A l’application $f$ we will attach an application $F : X^{k} \to X$ , which has the following property:

(2)

F (x, x, \dots, x) = f (x), x \in X .

To solve equation ( 1 ) we consider the multi-step iterative method, of the form:

(3)

x_{n + 1} = F (x_{n}, x_{n - 1}, \dots, x_{n - k + 1}), n = k - 1, k, k + 1, \dots

And $i_{0}, i_{1}, \dots, i_{k - 1}$ is a permutation of numbers $0, 1, \dots, k - 1$ , SO $i_{0} + n - k + 1, i_{1} + n - k + 1, \dots, i_{k - 1} + n - k + 1$ will be a permutation that matches the numbers $n - k + 1, n - k + 2, \dots, n$ .

For such a permutation we obtain a new multi-step iterative method:

(4)

x_{n + 1} = F (x_{i_{0} + n - k + 1}, x_{i_{1} + n - k + 1}, \dots, x_{i_{k - 1} + n - k + 1}),

Or $n = k - 1, k, \dots$

In this way, from the given application $F$ , we obtain $k!$ iterative methods, which are generally distinct.

If under certain conditions imposed on the application $F$ , all these $k!$ iterative methods converge to a solution of equation ( 1 ), the problem arises of choosing the method for which the best error bound is obtained.

In the following we will assume that $F$ verifies the following relationship:

(5)

r (F ({in}_{1}, {in}_{2}, \dots, {in}_{k}), F ({in}_{1}, {in}_{2}, \dots, {in}_{k})) \leq {(\sum_{i = 1}^{k} a_{i} r {({in}_{i}, {in}_{i})}^{b})}^{\frac{1}{b}},

whatever the elements ${in}_{1}, {in}_{2}, \dots, {in}_{k}, {in}_{1}, {in}_{2}, \dots, {in}_{k} \in X$ , Or $a_{i} \geq 0$ And $b > 0$ are given and $0 < \sum_{i = 1}^{k} a_{i} < 1 .$

We note that if $F$ verifies conditions ( 2 ) and ( 5 ) then $f$ checks the condition:

	$r (f (x), f (and))$	$= r (F (x, x, \dots, x), F (and, and, \dots, and))$
		$\leq {(\sum_{i = 1}^{k} a_{i} r {(x, and)}^{b})}^{\frac{1}{b}} = {(\sum_{i = 1}^{k} a_{i})}^{\frac{1}{b}} r (x, and),$

and the fact that $0 < \sum_{i = 1}^{k} a_{i} < 1$ , it follows that $f$ is a contraction, that is, equation ( 1 ) has only one solution.

On the other hand, if we designate by $ℱ_{b} (a_{1}, a_{2}, \dots, a_{k})$ all functions $F$ verifying conditions ( 2 ) and ( 5 ), then if $b < b^{'}$ it results $ℱ_{b} (a_{1}, a_{2}, \dots, a_{k}) \subset ℱ_{b^{'}} (a_{1}, a_{2}, \dots a_{k})$ .

For $b < b^{'}$ we deduce from Hölder's inequality:

	${(\sum_{i = 1}^{k} a_{i} r {({in}_{i}, {in}_{i})}^{b})}^{\frac{1}{b}}$	$= {[\sum_{i = 1}^{k} (a_{i}^{\frac{b}{b^{'}}} r {({in}_{i}, {in}_{i})}^{b}) a_{i}^{1 - \frac{b}{b^{'}}}]}^{\frac{1}{b}}$
		$\leq {(\sum_{i = 1}^{k} a_{i} r {({in}_{i}, {in}_{i})}^{b^{'}})}^{\frac{1}{b^{'}}} {[\sum_{i = 1}^{k} {(a_{i}^{1 - \frac{b}{b^{'}}})}^{\frac{b^{'}}{b^{'} - b}}]}^{\frac{b^{'} - b}{b b^{'}}}$
		$= {(\sum_{i = 1}^{k} a_{i} r {({in}_{i}, {in}_{i})}^{b^{'}})}^{\frac{1}{b^{'}}} {(\sum_{i = 1}^{k} a_{i})}^{\frac{b^{'} - b}{b b^{'}}}$
		$< {(\sum_{i = 1}^{k} a_{i} r {({in}_{i}, {in}_{i})}^{b^{'}})}^{\frac{1}{b^{'}}}$

SO $ℱ_{b} (a_{1}, a_{2}, \dots, a_{k}) \subset ℱ_{b^{'}} (a_{1}, a_{2}, \dots, a_{k})$ .

Let's consider the numbers $a_{i} \in ℝ$ , $i = 1, 2, \dots, k$ , which verify the relations:

(6)

a_{1} \geq a_{2} \geq \dots \geq a_{k - 1} \geq a_{k} \geq 0,

And

(6^′)

0 < \sum_{i = 1}^{k} a_{i} < 1 .

We now consider the equations

(7)

P (in) = {in}^{k} - a_{1} {in}^{k - 1} - \dots - a_{k - 1} in - a_{k} = 0,

(8)

Q (in) = {in}^{k} - a_{k} {in}^{k - 1} - \dots - a_{2} in - a_{1} = 0,

And

(9)

R (in) = {in}^{k} - a_{i_{1}} {in}^{k - 1} - \dots - a_{i_{k - 1}} in - a_{i_{k}} = 0,

Or $i_{1}, i_{2}, \dots, i_{k}$ is any permutation of the numbers $1, 2, \dots, k$ .

LEMME.

And $a_{1}, a_{2}, \dots, a_{k}$ verify the conditions ( 6 ) and ( 6 ^′ ) then each equation of the form ( 9 ) has a single positive root. If we denote by a the positive root of equation ( 7 ) and by $b$ the positive root of equation ( 8 ), then the positive root $c$ of equation ( 9 ) verifies the following inequalities:

(10)

0 < a \leq c \leq b < 1 .

Demonstration.

Either $i_{1}, i_{2}, \dots, i_{k}$ a permutation of numbers $1, 2, \dots, k$ and either $s$ the biggest clue for which $a_{i_{s}} \neq 0$ .

We obviously have $a_{i_{s + 1}} = a_{i_{s + 2}} = \dots = a_{i_{k}} = 0$ And $a_{i_{s}} \neq 0$ .

Consider the function $ψ (in) = R (in) / {in}^{k - s}$ . SO $ψ (0) = - a_{i_{s}} < 0$ And $ψ (1) = R (1) = 1 - a_{i_{1}} - \dots - a_{i_{k - 1}} - a_{i_{k}} = 1 - a_{1} - \dots - a_{k} > 0$ .

SO $ψ (in)$ has a positive root in the interval $(0, 1)$ . It follows that $R (in) = {in}^{k - s} ψ (in)$ has a root in the interval $(0, 1)$ .

The uniqueness of this root follows immediately by considering the equation $f (in) = - {in}^{k} R (1 / in) = 0$ , for which $f^{'} (in) > 0$ and $in > 0$ And $f (0) = - 1$ .

To prove inequality ( 10 ) it suffices to show that $R (a) \leq R (c) = 0$ And $R (b) \geq R (c) = 0$ . In fact, we have:

	$R (a) =$	$a^{k} - a_{i_{1}} a^{k - 1} - \dots - a_{i_{k - 1}} a - a_{i_{k}}$
	$=$	$(a_{1} - a_{i_{1}}) a^{k - 1} + (a_{2} - a_{i_{2}}) a^{k - 2} + \dots + a_{k} - a_{i_{k}}$
	$=$	$(a - 1) (a_{1} - a_{i_{1}}) a^{k - 2} + (a_{1} + a_{2} - a_{i_{1}} - a_{i_{2}}) a^{k - 3} + \dots +$
		$+ (a_{1} + a_{2} + \dots + a_{k - 2} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{k - 2}}) a +$
		$+ (a_{1} + a_{2} + \dots + a_{k - 1} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{k - 1}}) \leq 0,$

because $0 < a < 1$ and from ( 6 ) it follows that

a_{1} + a_{2} + \dots + a_{s} - a_{i_{1}} - a_{i_{2}} - \dots - a_{i_{s}} \geq 0;

for each $s = 1, 2, \dots, k - 1$ .

Similarly, we show that $R (b) \geq 0, Q . AND . D .$

Now we sort the coefficients $a_{i}$ from ( 5 ) in descending order, that is:

(11)

a_{i_{1}} \geq a_{i_{2}} \geq \dots \geq a_{i_{k}} \geq 0,

and we write

(11^′)

a_{s} = a_{i_{s}}, s = 1, 2, \dots, k .

We consider the application $G : X^{k} \to X$ , given by the relation

(12)

G ({in}_{1}, {in}_{2}, \dots, {in}_{k}) = F ({in}_{i_{1}}, {in}_{i_{2}}, \dots, {in}_{i_{k}}),

Or $i_{1}, i_{2}, \dots, i_{k}$ is the permutation of numbers $1, 2, \dots, k$ which corresponds to the relation ( 11 ). We then obtain from ( 5 ), for $G$ , the condition

(13)

r (G ({in}_{1}, {in}_{2}, \dots, {in}_{k}), G ({in}_{1}, {in}_{2}, \dots, {in}_{k})) \leq {(\sum_{i = 1}^{k} a_{i} r {({in}_{i}, {in}_{i})}^{b})}^{\frac{1}{b}},

whatever the elements ${in}_{1}, {in}_{2}, \dots, {in}_{k}, {in}_{1}, {in}_{2}, \dots, {in}_{k} \in X,$ Or

a_{1} \geq a_{2} \geq \dots \geq a_{k} \geq 0, b > 0 \dots \dots .0 < \sum_{i = 1}^{k} a_{i} < 1 .

To solve equation ( 1 ) we consider the following iterative method:

(14)

x_{n + 1} = G (x_{n}, x_{n - 1}, \dots, x_{n - k + 1}), n = k - 1, k \dots,

Or $x_{0}, x_{1}, \dots, x_{k - 1} \in X$ .

If we write $q_{i} = r (x_{i}, x_{i + 1}), i = 0, 1, \dots$ , then from ( 13 ) and ( 14 ) we obtain

(15)

q_{i} = {(\sum_{s = 1}^{k} a_{s} q_{i - s}^{b})}^{\frac{1}{b}}, i = k, k + 1, \dots .

If in equation ( 7 ) $a_{1}, a_{2}, \dots, a_{k}$ are given by ( 11 ^′ ) and if $a$ is the positive root of equation ( 7 ), then $a^{\frac{1}{b}} \in (0, 1)$ .

Either $C$ a positive constant such that:

q_{s} \leq C a^{s / b} For s = 0, 1, \dots, k - 1 .

From ( 15 ) we obtain:

	$q_{i}$	$\leq {(\sum_{s = 1}^{k} a_{s} q_{i - s}^{b})}^{\frac{1}{b}} \leq {(C \sum_{s = 1}^{k} a_{s} a^{i - s})}^{\frac{i}{b}}$
		$= C a^{(i - k) / b} {(\sum_{s = 1}^{k} a_{s} a^{k - s})}^{\frac{1}{b}} = C a^{(i - k) / b} a^{k / b} = C a^{i / b},$

$i = k, k + 1, \dots,$ . Since $a^{1 / b} \in (0, 1)$ it follows that the following ${(x_{n})}_{n = 0}^{\infty}$ is fundamental. Let us designate by $\bar{x}$ its limit. It is obvious that $\bar{x}$ is the unique solution of equation ( 1 ) and

(16)

r (\bar{x}, x_{n}) \leq \frac{C a^{n / b}}{1 - a^{1 / b}} .

∎

So, using the lemma we obtain the following theorem:

THEOREM .

Let's suppose that $F \in ℱ_{b} (a_{1}, a_{2}, \dots, a_{k})$ and that we give the $k!$ iterative methods of the form ( 4 ), attached to $F$ .

The iterative method for which the best error bound is obtained is that given by ( 14 ), with $G$ defined by ( 12 ) and which corresponds to the decreasing order of the sequence of coefficients $a_{i}, i = 1, 2, \dots, k,$ from ( 5 ).

Remarks .

1) Because, from the $F \in ℱ_{b} (a_{1}, a_{2}, \dots, a_{k})$ it follows that $f$ is a contraction, with the Lipschitz constant ${(\sum_{i = 1}^{k} a_{i})}^{1 / b}$ , it is clear that the iterative method

(17)

x_{n + 1} = f (x_{n}), x_{0} \in X, n = 0, 1, \dots

converges to the solution $\bar{x}$ from equation ( 1 ). Furthermore, we have

(18)

r (\bar{x}, x_{n}) \leq C_{1} \frac{{(\sum_{i = 1}^{k} a_{i})}^{n / b}}{1 - {(\sum_{i = 1}^{k} a_{i})}^{1 / b}} .

We will demonstrate that $\sum_{i = 1}^{k} a_{i} \leq a$ , where a is the solution to equation ( 7 ), with $a_{s}, s = 1, 2, \dots, k$ given by the formula ( 11 ^′ ).

On a:

		$P (\sum_{i = 1}^{k} a_{i}) =$
		$= {(\sum_{i = 1}^{k} a_{i})}^{k} - a_{1} {(\sum_{i = 1}^{k} a_{i})}^{k - 1} - a_{2} {(\sum_{i = 1}^{k} a_{i})}^{k - 2} - \dots - a_{k - 1} (\sum_{i = 1}^{k} a_{i}) - a_{k}$
		$\leq {(\sum_{i = 1}^{k} a_{i})}^{k} - a_{i} {(\sum_{i = 1}^{k} a_{i})}^{k - 1} - a_{2} {(\sum_{i = 1}^{k} a_{i})}^{k - 1} - \dots - a_{k - 1} {(\sum_{i = 1}^{k} a_{i})}^{k - 1} - a_{k} {(\sum_{i = 1}^{k} a_{i})}^{k - 1}$
		$= {(\sum_{i = 1}^{k} a_{i})}^{k} - {(\sum_{i = 1}^{k} a_{i})}^{k} = 0,$

from which it follows that $\sum_{i = 1}^{k} a_{i} \leq a$ .

Be it now $F \in ℱ_{b} (a_{1}, a_{2}, \dots, a_{k})$ And $f (x) = F (x, x, \dots, x)$ . Formulas ( 16 ) and ( 18 ) valid for any metric and for each pair $(F, f),$ with the above properties, show us that for the iterative method ( 17 ) we obtain a better error delimitation than in the case of other methods of the form ( 4 ). This does not mean that for each choice of the initial points and each application $F,$ method ( 17 ) converges faster than all iterative methods of the form ( 4 ).

For example, $X = ℝ$ , $r = | \cdot |, f (x) = \frac{1}{4} \sin x,$ $F (x, and) = \frac{1}{2} \sin \frac{x}{2} \cos \frac{and}{2}$ . On a

| F (x_{1}, {and}_{1}) - F (x_{2}, {and}_{2}) | \leq \frac{1}{4} | x_{1} - x_{2} | + \frac{1}{4} | {and}_{1} - {and}_{2} |,

for each $x_{1}, x_{2}, {and}_{1}, {and}_{2} \in ℝ$ ; $F \in ℱ_{1} (\frac{1}{4}, \frac{1}{4})$ And $F (x, x) = f (x)$ .

We consider the following iterative methods:

(19)

x_{n + 1} = \frac{1}{4} \sin x_{n}, n = 0, 1, \dots, x_{0} = \frac{p}{2},

(20)

x_{n + 2} = \frac{1}{2} \sin \frac{x_{n + 1}}{2} \cos \frac{x_{n}}{2}, n = 0, 1, \dots, x_{0} = \frac{p}{2}, x_{1} = 0,

(21)

x_{n + 2} = \frac{1}{2} \cos \frac{x_{n + 1}}{2} \sin \frac{x_{n}}{2}, n = 0, 1, \dots, x_{0} = \frac{p}{2}, x_{1} = 0 .

In this case the sequence ( 20 ) converges faster than the sequence ( 19 ) or the sequence ( 21 ).

2) There exist iterative methods of the form ( 4 ) respectively ( 17 ), for which the bounds ( 16 ) respectively ( 18 ) cannot improve, i.e.:

\bar{lim_{n \to \infty}} r {(\bar{x}, x_{n})}^{1 / n} = a^{1 / b},

respectively

\bar{lim_{n \to \infty}} r {(\bar{x}, x_{n})}^{1 / n} = {(\sum_{i = 1}^{k} a_{i})}^{1 / b} .

Example .

Either $X = ℝ, r = | \cdot |, f (x) = \frac{5}{6} x,$

	$F (x, and)$	$= \frac{1}{2} x + \frac{1}{3} and,$
	$F (x, x)$	$= f (x),$
	$\| F (x_{1}, {and}_{1}) - F (x_{2}, {and}_{2}) \|$	$\leq \frac{1}{2} \| x_{1} - x_{2} \| + \frac{1}{3} \| {and}_{1} - {and}_{2} \|, b = 1 .$

Either

(22)

x_{n + 1} = \frac{5}{6} x_{n}, n = 0, 1, \dots, x_{0} = 1 .

(23)

x_{n + 2} = \frac{1}{2} x_{n + 1} + \frac{1}{3} x_{n}, n = 0, 1, \dots, x_{0} = 1, x_{1} = 1 .

(24)

x_{n + 2} = \frac{1}{3} x_{n + 1} + \frac{1}{2} x_{n}, n = 0, 1, \dots < x_{0} = 1, x_{1} = 1 .

In this case we obtain the formulas:

(22^′)

lim_{n \to \infty} {(x_{n})}^{\frac{1}{n}} = \frac{5}{6} = \frac{1}{2} + \frac{1}{3},

(23^′)

lim_{n \to \infty} x_{n}^{1 / n} = a,

where a is the positive root of the equation $x^{2} - \frac{1}{2} x - \frac{1}{3} = 0$ , that's to say $a = \frac{3 + \sqrt{57}}{12}$ . In the same way we obtain

(24^′)

lim_{n \to \infty} x_{n}^{1 / n} = b,

or $b$ is the positive root of the characteristic equation $x^{2} - \frac{1}{3} x - \frac{1}{2} = 0$ that's to say $b = \frac{1 + \sqrt{19}}{6}$ . It is clear that $\frac{5}{6} < \frac{3 + \sqrt{57}}{12} < \frac{1 + \sqrt{19}}{6} .$