On approximating the solutions of equations in metric spaces

Ion Păvăloiu
(original), html, paper, PDF, works

Abstract

Let \(\left( X,\rho \right)\) be a complete metric space, \(f:X\rightarrow X\) a nonlinear mapping. In order to solve the equation \(x=f\left( x\right) \) we consider a multistep method \[x_{n+k+1}=G(x_{n},x_{n+1},…,x_{n+k}), \quad n=1,2,… \] generated by a mapping \(G:X^{k+1}\rightarrow X\), whose diagonal restriction coincides with \(f\): \(G(x,…,x)=f(x)\). Under Lipschitz assumption on \(G\) we determine the algebraic equation whose unique positive solution leads to the convergence order of the iterations. We also study the case when the operator \(G\) replaced by an approximation of it.

Authors

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

Title

Original title (in French)

Sur l’approximation des racines des equations dans une espace métrique

English translation of the title

On approximating the solutions of equations in metric spaces

Keywords

multistep iterative methods; convergence; successive approximations

PDF

Scanned paper.

PDF-Latex version of the paper.

Cite this paper as:

I. Păvăloiu, Sur l’approximation des racines des equations dans une espace métrique, Seminar on functional analysis and numerical methods, Preprint no. 1 (1989), pp. 95-104 (in French).

About this paper

Journal

Seminar on functional analysis and numerical methods,
Preprint

Publisher Name

“Babes-Bolyai” University,
Faculty of Mathematics,
Research Seminars

DOI

Not available yet.

References

[1] I. Pavaloiu, I., Serb, Sur des methodes iteratives optimales, Research Seminars, Seminar on Functional Analysis and Numerical Methods, Preprint Nr.1 (1983), 175–182.

[2] I.A. Rus, An iterative method for the solution of the equation x = f (x, x, . . . , x), Anal. Num´er. Theor. Approx., 10 (1981), 95–100.

[3] Weinischke, J.H., Uber eine klasse von Iterationverfahren, Numerische Mathematik 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, 1989, pp.95-104

On approximating the solutions of equations in metric spaces

Ion Pavaloiu

In this note we study the evaluation of errors that arise during the numerical resolution of equations in metric spaces using certain multi-step iteration methods.

Consider a metric space(X,r)complete and the following equation:

(1) x=f⁢(x),

Orf:X→Xis any operator.

Let us designate byXk+1=X×X×…×X,that is to say the Cartesian product of the setXwith himselfk+1times.

For the resolution of equation ( 1 ) we consider the applicationG:Xk+1→Xwhich we assume is restricted to the diagonal of spaceXk+1coincides with the operatorf, that's to say:

(2) G⁢(x,x,…,x)=f⁢(x),

for eachx∈X.

Consider the following(xn)n=0∞provided by the following iteration process:

(3) xn+k+1=G⁢(xn,xn+1,…,xn+k),n=0,1,2,…

Orx0,x1,…,xk∈Xare given elements.

Let us designate byD⊂Xa bounded set in this space. We assume that on the setDk+1the operatorGverifies the Lipschitz condition, that is:

(4) r⁢(G⁢(in1,in2,…,ink+1),G⁢(in1,in2,…,ink+1))≤∑i=1k+1ai⁢r⁢(ini,ini),

Orai∈ℝ,ai≥0,i=1,2,…,k+1,for each (in1,in2,…,ink+1), (in1,in2,…,ink+1)∈Dk+1.

Consider the equation:

(5) a1+a2⁢t+…+ak+1⁢tk=tk+1.

We know that in the case whereai≥0  for eachi=1,2,…,k+1 and where there exists at least one numberi1,1≤i1≤k+1for which ai1>0, this equation has only one roott1real and positive.

If in addition:

(6) b=∑i=1k+1ai<1

then this root verifies the inequality

(7) 0<t1<1.

Regarding the convergence of the sequence(xn)n=0∞provided by method ( 3 ) we have the following theorem:

Theorem 1 .

If the applicationGand the initial elements x0,x1,…,xkmeet the following conditions:

  • i)

    L’application Gfulfills condition ( 4 ) where ai,i=1,2,…,k+1, satisfy the relation ( 6 );

  • ii)

    The wholeS={x∈X:r⁢(x,x0)≤a1−t1}⊆D,Ort1is the positive root of equation ( 5 ) and

    a≥max⁡{r⁢(x0,x1),1t1⁢r⁢(x1,x2),…,1t1k−1⁢r⁢(xk−1,xk)};

then we have the following properties:

  • j)

    xn∈Sfor eachn=0,1,…;

  • jj)

    the sequel(xn)n=0∞is convergent and if we denote byx∗the limit of the sequence(xn)n=0∞, SOx∗∈SAndx∗is the unique solution of equation ( 1 ) of the sphereS;

  • jjj)

    we have the following inequalities:

    r⁢(x∗,xn)≤a⁢t1n1−t1,for each ⁢n=0,1,…
Demonstration.

From conclusion ii) it follows thatr⁢(xi,xi+1)≤a⁢t1ifor eachi=0,1,…,k−1. Fori=1,2,…,kwe have the following inequalities:

(8) r⁢(xi,x0) ≤r⁢(x0,x1)+r⁢(x1,x2)+…+r⁢(xi−1,xi)
≤a+a⁢t1+…+a⁢t1i−1
<a1−t1

from which we deduce thatxi∈S,Fori=1,2,…,k.

Subsequently we assume thatxi∈SAndr⁢(xi−1,xi)≤a⁢ti−1,for eachi=1,2,…,n+k+1. From this inequality we deduce that:

r⁢(xn+k+2,xn+k+1)≤r⁢(G⁢(xn,xn+1,…,xn+k),G⁢(xn+1,…,xn+k+1))
∑i=1−k+1ai⁢r⁢(xn+i−1,xn+i)≤a⁢(a1⁢t1n+…+ak+1⁢t1k+n)=a⁢t1n+k+1,

where we used the fact thatt1verifies equation ( 5 ).

From the above inequalities, and in a manner similar to that used in the demonstration of relation ( 8 ), we deduce thatxn+k+2∈S. From the principle of mathematical induction it therefore follows that all the elements of the sequence(xn)n=0∞ belong to the sphereS.

On the completeness of spaceXand inequalities

(9) r⁢(xn+s,xn) ≤r⁢(xn,xn+1)+…+r⁢(xn+s−1,xn+s)
≤a⁢(t1n+t1n+1+…+t1n+s−1)≤a⁢t1n1−t1

for eachs=1,2,…,it follows that the following(xn)n=0∞is convergent.

Let us designate byx∗=limn→∞xn. So by passing to limit in the inequalities ( 9 ) with s→∞, on a:

(10) r⁢(xn,x∗)≤a⁢t1n1−t1,n=0,1,…

Let us now demonstrate thatG⁢(x∗,x∗,…,x∗)=x∗.

In fact we have:

r⁢(x∗,G⁢(x∗,x∗,…,x∗))≤
≤r⁢(xn+k+1,x∗)+r⁢(xn+k+1,G⁢(x∗,x∗,…,x∗))
≤r⁢(xn+k+1,x∗)+r⁢(G⁢(xn,xn+1,…,xn+k),G⁢(x∗,x∗,…,x∗))
≤r⁢(xn+k+1,x∗)+∑i=1k+1ai⁢r⁢(xn+i−1,x∗)
≤a⁢t1n+k+11−t1+∑i=1k+1ai⁢a⁢t1n+i−11−t1
=a1−t1⁢[t1n+k+1+t1n⁢∑i=1k+1ai⁢t1i−1]
=2⁢a⁢t1n+k+11−t1.

This inequality is verified for each n∈ℕ, from which it follows that we have the equalityx∗=G⁢(x∗,x∗,…,x∗), but this relation and relation ( 2 ) imply that the elementx∗⊂Sis the solution to equation ( 1 ). ∎

Let us now show thatx∗is the unique solution of equation ( 1 ) which belongs to the sphereS. Suppose instead that equation ( 1 ) has at least two solutionsx∗Andand∗ inS. So fromx∗=f⁢(x∗)Andand∗=f⁢(and∗), and from ( 2 ) it follows that:

r⁢(x∗,and∗) =r⁢(G⁢(x∗,x∗,…,x∗),G⁢(and∗,and∗,…,and∗))
≤∑i=1k+1ai⋅r⁢(x∗,and∗)

from which, if we take into account ( 6 ) we obtain

0<r⁢(x∗,and∗)<r⁢(x∗,and∗).

This last inequality being impossible, it follows that the assumption is false, therefore that equation ( 1 ) has a unique solution.

Let us then consider the applicationG∗:Xk+1→Xwhich fills with the applicationGthe following condition:

(11) r⁢(G⁢(in1,in2,…,ink+1),G∗⁢(in1,in2,…,ink+1))≤e,e>0

for each(in1,in2,…,ink+1)∈Dk+1.

To solve equation ( 1 ) we will replace the sequence(xn)n=0∞provided by the relation ( 3 ), subsequently(xn∗)n=0∞ provided by the following iterative process:

(12) xn+k+1∗=G∗⁢(xn∗,xn+1∗,…,xn+k∗),n=0,1,…,

where we assume that the initial elements have been chosenx0∗,x1∗,…,xk∗such that the following conditions are met:

(13) r⁢(x0∗,x1∗) ≤a+2⁢e1−b
r⁢(x1∗,x2∗) ≤a⁢t1+2⁢e1−b
…⁢…⁢…⁢…⁢…⁢…..
r⁢(xk−1∗,xk∗) ≤a⁢t1k−1+2⁢e1−b.

Regarding the relationshipxk+1∗=G∗⁢(x0∗,x1∗,…,xk∗)we assume that we have the following condition

r⁢(xk∗,xk+1∗)≤a⁢t1k+2⁢e1−b.

Let us also assume that the set:

(14) S∗={x∈X:r⁢(x,x0)≤a⁢(2−t1)1−t1+e1−b}

is contained inD.

Furthermore we assume that the initial elementsx0∗,x1∗,…,xk∗of method ( 12 ) fill with the elementsx0,x1,…,xkof ( 3 ) the following conditions:

(15) r⁢(x0,x0∗) ≤a+e1−b
r⁢(x1,x1∗) ≤a⁢t1+e1−b
…⁢…⁢…⁢…⁢…⁢…⁢…
r⁢(xk,xk∗) ≤a⁢t1k+e1−b

Using these assumptions and further using the fact thatG verifies the hypotheses of Theorem 1 , we will demonstrate that for eachn∈ℕwe have the following inequalities:

(16) r⁢(xn+k+1,xn+k+1∗)≤a⁢t1n+k+1+e1−b
(17) r⁢(xn+k+1∗,xn+k+2∗)≤a⁢t1n+k+1+2⁢e1−b

And

(18) r⁢(x∗,xn+k+1∗)≤a⁢(2−t1)1−t1⁢t1n+k+1+e1−b.

Indeed, by using relations ( 15 ) we obtain the following relations:

(19) r⁢(xk+1,xk+1∗)=
=r⁢(G⁢(x0,x1,…,xk),G∗⁢(x0∗,x1∗,…,xk∗))
≤r⁢(G⁢(x0,x1,…,xk),G⁢(x0∗,x1∗,…,xk∗))+
+r⁢(G⁢(x0∗,x1∗,…,xk∗),G∗⁢(x0∗,…,xk∗))
≤e+a1⁢r⁢(x0,x0∗)+a2⁢r⁢(x1,x1∗)+…⁢ak+1⁢r⁢(xk,xk∗)
≤e+e1−b⁢(a1+…+ak+1)+a⁢(a1+a2⁢t1+…+ak+1⁢t1k)
=e1−b+a⁢t1k+1

that is to say that inequality ( 16 ) is verified, forn=0.Let us now show thatxk+1∗∈S∗. Using inequalities ( 19 ) and ( 8 ) we obtain:

(20) r⁢(xk+1∗,x0) ≤r⁢(xk+1∗,xk+1)+r⁢(xk+1,x0)
≤a1−t1+e1−b+a⁢t1k+1≤a+a1−t1+e1−b
=a⁢(2−t1)1−t1+e1−b.

Generally, if we assume that

xn∗,xn+1∗,…,xn+k∗∈S∗

and that we have the following inequalities:

r⁢(xn+i,xn+1∗)≤a⁢t1n+1+e1−b

for eachi=1,2,…,k,then in a manner similar to that used to demonstrate inequality ( 19 ) we obtain:

(21) r⁢(xn+k+1,xn+k+1∗) ≤e+a1⁢r⁢(xn,xn∗)+…+ak+1⁢r⁢(xn+k,xn+k∗)
≤e+a⁢t1n⁢(a1+a2⁢t1+…+ak+1⁢t1k)+e⁢b1−b
e+a⁢t1n+k+1+e⁢b1−b=a⁢t1n+k+1+e1−b

from which it follows that we have the inequalities ( 16 ) for eachn∈ℕ. From relations ( 21 ) and ( 8 ), in a manner similar to that used in the deduction of relation ( 20 ), it follows thatxn+k+1∗∈S∗.

Let us now demonstrate that the inequalities ( 17 ) are verified. If we consider the relations ( 13 ) we have the following inequalities:

(22) r⁢(xk+1∗,xk+2∗) ≤r⁢(G∗⁢(x0∗,x1∗,…,xk∗),G∗⁢(x1∗,…,xk+1∗))
≤r⁢(G∗⁢(x0∗,x1∗,…,xk∗),G⁢(x0∗,x1∗,…⁢xk∗))
+r⁢(G⁢(x0∗,x1∗,…,xk∗),G⁢(x1∗,x2∗,…,xk+1∗))
+r⁢(G∗⁢(x1∗,x2∗,…,xk+1∗),G⁢(x1∗,x2∗,…,xk+1∗))
≤2⁢e+2⁢e⁢b1−b+a⁢(a1+a2⁢t1+…+ak+1⁢t1k)
=2⁢e1−b+a⁢t1k+1,

so we obtained the inequality ( 17 ) forn=0.

Now assuming that we have the following inequalities:

r⁢(xn+i∗,xn+i+1∗)≤2⁢e1−b+a⁢t1n+i,

Fori=0,1,…,k,in a manner similar to that employed in the deduction of inequality ( 22 ) we obtain inequalities ( 17 ).

For inequalities ( 18 ) we have

r⁢(x∗,xn+k+1∗) ≤r⁢(x∗,xn+k+1)+r⁢(xn+k+1,xn+k+1∗)
≤a⁢t1n+k+11−t1+a⁢t1n+k+1+e1−b
=a⁢(1−t1)1−t1⁢t1n+k+1+e1−b

that is, inequalities ( 18 ).

Inequalities ( 18 ) provide an assessment of the distance between the exact solution of equation ( 1 ) and its approximation, obtained using the iteration method ( 12 ).

Noticed .

If we notice that the wholeD⊂X,on which condition ( 4 ) is fulfilled, is itself a metric space, it follows that we can consider theorem 1 as a special case of the main result contained in the work [ 3 ] . From our point of view the importance of this theorem consists in the fact that the setDbeing limited it allows easy choice of applicationG∗, application that fills with the applicationGthe condition ( 11 ). Let us imagine for example the trivial case of the equation x=a⁢x+b=G⁢(x),x∈ℝand the approximate equation x∗=a∗⁢x∗+b∗=G∗⁢(x∗).

Because|G⁢(x)−G∗⁢(x)|=|a−a∗|⋅|x|, it follows that the difference|G⁢(x)−G∗⁢(x)|is not bounded, so even in the case0<a<1condition ( 11 ) cannot be fulfilled in the whole spaceℝ.

Bibliography


Institute of Computing

Post Office 1

C.P. 68

3400 Cluj-Napoca

Romania



This paper is in final form and no version of it is or will be submitted for publication elsewhere.

1989

Related Posts