Aitken-Steffensen-type methods for nondifferentiable functions (I)

9 years ago

Abstract

We study the convergence of the Aitken-Steffensen method for solving a scalar equation $f(x)=0$. Under reasonable conditions (without assuming the differentiability of $f$) we construct some auxilliary functions used in these iterations, which generate bilateral sequences approximating the solution of the considered equation.

Author

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

Keywords

nonlinear equations in R; Aitken-Steffensen method.

PDF

PDF-LaTeX file on the journal website.

Cite this paper as:

I. Păvăloiu, Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal. Numér. Théor. Approx., 31 (2002) no. 1, pp. 109-114. https://doi.org/10.33993/jnaat311-713

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

Balázs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., 21, no. 2, pp. 111-117, 1992, https://ictp.acad.ro/jnaat/journal/article/view/1992-vol21-no2-art3

Casulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25-44, 1977, https://doi.org/10.1007/BF02576646

Cobzaş, S., Mathematical Analysis, Presa Universitară Clujeană, Cluj-Napoca, 1997 (in Romanian).

Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.

Păvăloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens’s method, Mathematica (Cluj), 35 (58), no. 1, pp. 71-76, 1993.

Păvăloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 23, no. 1, pp. 95-100, 1994, https://ictp.acad.ro/jnaat/journal/article/view/1994-vol23-no1-art10

Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, no. 1-2, pp. 69-82, 1995, https://doi.org/10.1007/BF02576543

Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.

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; } AITKEN-STEFFENSEN TYPE METHODS FOR NONDIFFERENTIABLE FUNCTIONS (I)∗

AITKEN-STEFFENSEN TYPE METHODS FOR NONDIFFERENTIABLE FUNCTIONS (I)^∗

Ion Pǎvǎloiu^†

(Date: November 15, 2001.)

Abstract.

We study the convergence of the Aitken-Steffensen method for solving a scalar equation $f (x) = 0$ . Under reasonable conditions (without assuming the differentiability of $f$ ) we construct some auxilliary functions used in these iterations, which generate bilateral sequences approximating the solution of the considered equation.

^∗This work was supported by the Romanian Academy under Grant GAR 45/2002.

^†“T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68-1, 3400 Cluj-Napoca, Romania, e-mail: pavaloiu@ictp.acad.ro.

{amssubject}

65H05.

{keyword}

Aitken-Steffensen method, bilateral approximations.

1. INTRODUCTION

In this note we shall deal with the construction of the auxiliary functions appearing in the Aitken-Steffensen-type methods for solving the equation:

(1)

f (x) = 0,

where $f : [a, b] \to ℝ, a, b \in ℝ, a < b$ . Since we shall not assume differentiability conditions on $f$ , we shall consider instead the first and second order divided differences of $f$ , denoted by $[u, v; f]$ , resp. $[u, v, w; f]$ , $u, v, w \in [a, b]$ .

Let $g, g_{i} : [a, b] \to ℝ$ , $i = 1, 2$ , be three functions such that the equations

(2)		$x - g (x)$	$=$	$0 and$
(3)		$x - g_{i} (x)$	$=$	$0, i = 1, 2$

are equivalent to (1).

The following three Aitken-Steffensen methods are well known:

1. The Steffensen method, which generates two sequences, ${(x_{n})}_{n \geq 1}$ and ${(g (x_{n}))}_{n \geq 1}$ , by

(4)

x_{n + 1} = x_{n} - \frac{f (x_{n})}{[x_{n}, g (x_{n}); f]}, n = 1, 2, \dots, x_{1} \in [a, b],

where $g$ is given by (2).

2. The Aitken method, which generates the sequences ${(x_{n})}_{n \geq 1}$ , ${(g_{i} (x_{n}))}_{n \geq 1}$ $i = 1, 2,$ by

(5)

x_{n + 1} = g_{1} (x_{n}) - \frac{f (g_{1} (x_{n}))}{[g_{1} (x_{n}), g_{2} (x_{n}); f]}, n = 1, 2, \dots, x_{n} \in [a, b],

with $g_{1}, g_{2}$ given by (3).

3. The Aitken-Steffensen method, which generates the sequences ${(x_{n})}_{n \geq 1}$ , ${(g_{1} (x_{n}))}_{n \geq 1}$ , and ${(g_{2} (g_{1} (x_{n})))}_{n \geq 1}$ , by

(6)

x_{n + 1} = g_{1} (x_{n}) - \frac{f (g_{1} (x_{n}))}{[g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f]}, n = 1, 2, \dots, x_{1} \in [a, b] .

A certain method presents an important advantage particularly when it yields sequences approximating the solution both from the left and from the right. In such a case we obtain a rigorous control if the error at each iteration step.

We shall study the choice of the functions $g, g_{1}, g_{2}$ such that the above methods to yield bilateral approximations for the solution of (1).

Regarding the monotonicity and the convexity of the function $f$ we shall use the following definitions. The function $f$ is nondecreasing (increasing) on $[a, b]$ if $[u, v; f] \geq 0$ $(> 0)$ for all $u, v \in [a, b]$ . The function $f$ is nonconcave (convex) on $[a, b]$ if $[u, v, w; f] \geq 0$ $(> 0)$ for all $u, v, w \in [a, b]$ .

Let $x_{0} \in [a, b]$ and $p_{x_{0}} : [a, b] \ {x_{0}} \to ℝ$ , given by

(7)

p_{x_{0}} (x) = [x_{0}, x; f] .

The following result was proved in [3, p. 290].

Theorem 1.

a)

If the function $f$ is nonconcave on $[a, b]$ , the $p_{x_{0}}$ is a nondecreasing function on $[a, b] \ {x_{0}} .$
b)

If $f$ is a convex function on $[a, b]$ , then $p_{x_{0}}$ is an increasing function on $[a, b] \ {x_{0}} .$

In other words, if $f$ is nonconcave (convex) on $[a, b]$ , then for all $x^{'}, x^{''} \in [a, b] \ {x_{0}}, x^{'} < x^{''}$ one obtains

(8)

[x_{0}, x^{'}; f] \leq (<) [x_{0}, x^{''}; f] .

Consider now $u, v, w, t \in [a, b]$ such that $u = \min {u, v, w, t}$ and $t = \max {u, v, w, t} .$ The following lemma holds.

Lemma 2.

If $f$ is nonconcave (convex) on $[a, b]$ , then for all $v, w \in (u, t)$ , $v \neq w,$ one has

(9)

[u, v; f] \leq (<) [w, t; f] .

Proof..

We shall consider only the case $” \leq ”$ , since the other one is similarly obtained. There an two alternatives:

Case I. $u < v < w < t$ . Taking into account the symmetry of the divided differences with respect to the nodes and Theorem 1 we get $[u, v; f] \leq [u, w; f] = [w, u; f] \leq [w, t; f] .$

Case II. $u < w < v < t$ . As above, we obtain: $[u, v; f] \leq [u, t; f] = [t, u; f] \leq [t, w; f] = [w, t; f] .$ ∎

2. THE CONVERGENCE OF THE AITKEN-STEFFENSEN-LIKE METHOD

We shall make the following assumptions on $f :$

i.

$f (a) \cdot f (b) < 0;$
ii.

$f$ is increasing on $[a, b];$
iii.

$f$ is convex on $[a, b]$ and continuous in $a$ and $b$ ;
iv.

$f$ is differentiable at $\bar{x} \in (a, b)$ , where $\bar{x}$ is the solution of (1).

Remark 1.

Hypothesis iii. ensures the continuity of $f$ on $[a, b]$ (see [3, p. 295]). ∎

Remark 2.

Hypothesis i.–iii. ensure the existences and the uniqueness of the solution $\bar{x} \in (a, b)$ of the equation (1). ∎

Let $α$ and $β$ be two numbers such that $a < α < β < b, f (α) < 0$ and $f (β) > 0$ . Consider the functions $g_{1},$ $g_{2}$ given by

(10)		$g_{1} (x) = x - \frac{f (x)}{[β, b; f]}, x \in [α, β] and$
(11)		$g_{2} (x) = x - \frac{f (x)}{[a, α; f]}, x \in [α, β] .$

From hypotheses ii. iii. and applying Lemma 2 it follows that for all $u, v \in (α, β)$

(12)

[u, v; g_{1}] > 0 and [u, v; g_{2}] < 0 .

Consider now an initial approximation $x_{1} \in (α, β)$ satisfying

a)

$f (x_{1}) < 0$ ;
b)

$g_{2} (g_{1} (x_{1})) < β .$

The following result holds regarding the convergence of the sequence (6).

Theorem 3.

If the function $f$ obeys i.–iv., the functions $g_{1}$ and $g_{2}$ are given by (10) resp. (11) and $x_{1}$ satisfies the assumptions a) and b), then the sequences ${(x_{n})}_{n \geq 1}$ , ${(g_{1} (x_{n}))}_{n \geq 1}$ and ${(g_{2} (g_{1} (x_{n})))}_{n \geq 1}$ generated by (6) satisfy:

j.

${(x_{n})}_{n \geq 1}$ is increasing;
jj.

${(g_{1} (x_{n}))}_{n \geq 1}$ is increasing;
jjj.

${(g_{2} (g_{1} (x_{n})))}_{n \geq 1}$ is decreasing;
jv.

for all $n \in ℕ,$ $n \geq 1$ , the following relations hold:

(13) $x_{n} < g_{1} (x_{n}) < x_{n + 1} < \bar{x} < g_{2} (g_{1} (x_{n})) .$

Proof..

By ii. and a) it follows that $x_{1} < \bar{x}$ , and from $f (x_{1}) < 0$ and $[β, b; f] > 0$ we get $g_{1} (x_{1}) > x_{1}$ . Since $x_{1} < \bar{x}$ and $g_{1}$ is increasing, one obtains $g_{1} (x) < g_{1} (\bar{x}) = \bar{x},$ i.e., $x_{1} < g_{1} (x_{1}) < \bar{x}$ . On the other hand, by b) and (6) it follows

(14)

x_{2} = g_{1} (x_{1}) - \frac{f (g_{1} (x_{1}))}{[g_{1} (x_{1}), g_{2} (g_{1} (x_{1})); f]} .

Since $g_{1} (x_{1}) < \bar{x}$ we get $f (g_{1} (x_{1})) < 0$ and hence $x_{2} > g (x_{1}) .$ The fact that $g_{2}$ is decreasing and $g_{1} (x_{1}) < \bar{x}$ imply that $g_{2} (g_{1} (x_{1})) > g_{2} (\bar{x}) = \bar{x} .$ It follows that $f (g_{2} (g_{1} (x_{1}))) > 0$ , and taking into account the equality

g_{1} (x_{1}) - \frac{f (g_{1} (x_{1}))}{[g_{1} (x_{1}), g_{2} (g_{1} (x_{1})); f]} = g_{2} (g_{1} (x_{1})) - \frac{f (g_{2} (g_{1} (x_{1})))}{[g_{1} (x_{1}), g_{2} (g_{1} (x_{1})); f]} = x_{2}

it follows that $x_{2} < g_{2} (g_{1} (x_{1}))$ and hence the following identity is true

	$f (x_{2}) =$	$f (g_{1} (x_{1})) + [g_{1} (x_{1}), g_{2} (g_{1} (x_{1})); f] (x_{2} - g_{1} (x_{1}))$
		$+ [x_{2}, g_{1} (x_{1}), g_{2} (g_{1} (x_{1})); f] (x_{2} - g_{1} (x_{1})) (x_{2} - g_{2} (g_{1} (x_{1}))),$

whence, taking into account the following facts: $f$ is convex, $x_{2} > g_{1} (x_{1}),$ $x_{2} < g_{2} (g_{1} (x_{1}))$ and (14), it follows that $f (x_{2}) < 0$ , i.e., $x_{2} < \bar{x} .$

The inequality $x_{1} < x_{2}$ and the fact that $g_{1}$ is increasing imply that $g_{1} (x_{1}) < g_{1} (x_{2})$ . Since $g_{2}$ is decreasing we get $g_{2} (g_{1} (x_{1})) > g_{2} (g_{1} (x_{2}))$ . From $x_{2} < \bar{x}$ it follows that $g_{1} (x_{2}) < \bar{x}$ and $g_{2} (g_{1} (x_{2})) > g_{2} (\bar{x}) = \bar{x} .$

Obviously, the above reason may be applied for any $x_{n}$ , $n \geq 2$ , so that the induction principle completes the proof.∎

The sequences ${(x_{n})}_{n \geq 1}, {(g_{1} (x_{n}))}_{n \geq 1}$ and ${(g_{2} (g_{1} (x_{n})))}_{n \geq 1}$ are monotone and bounded, and therefore they converge.

Let $x^{*} = lim x_{n}$ , hence $x^{*} = {sup}_{n \in ℕ} {x_{n}}$ , and let $b = {sup}_{n \in ℕ} {g_{1} (x_{n})} .$ We shall prove that $x^{*} = b .$ The relations $x^{*} < b$ and $x^{*} > b$ cannot hold, since, as implied by (13), we get

x_{n} < g_{1} (x_{n}) < x_{n + 1} < g_{1} (x_{n + 1}), n = 1, 2, \dots

which lead to conclusions contradicting the definition of the exact upper bound. Therefore, the following relations are true: $x^{*} = lim g_{1} (x_{n}) = g_{1} (x^{*}),$ whence, taking into account the equivalence of (1) and (3), it follows that $x^{*} = \bar{x}$ . The equality $\bar{x} = g_{2} (\bar{x})$ implies $lim g_{2} (g_{1} (x_{n})) = g_{2} (g_{1} (\bar{x})) = g_{2} (\bar{x}) = \bar{x} .$

The three sequences have the same limit $\bar{x},$ which is the solution of (1).

By (13) we obtain

\bar{x} - x_{n + 1} \leq g_{2} (g_{1} (x_{n})) - x_{n + 1},

and

\bar{x} - x_{n + 1} \leq g_{2} (g_{1} (x_{n})) - g_{1} (x_{n}), n \in ℕ^{*},

which provide a control of the error at each iteration step.

In a forthcoming work we shall present some results regarding the convergence of the Steffensen and Aitken methods.

We end with some remarks.

Remark 3.

Since $f$ is convex, then in (10), resp. (11) we may replace the divided differences $[a, α; f]$ and $[β, b; f]$ by $f_{r}^{'} (a)$ , resp. $f_{l}^{'} (b) .$ ∎

Remark 4.

The following relations hold:

| \bar{x} - x_{n + 1} | \leq \frac{l^{3} m [β, b; f]}{{[a, α; f]}^{2}} {| \bar{x} - x_{n} |}^{2}, n = 1, 2, \dots,

where $l = 1 - \frac{[a, α; f]}{[β, b; f]}$ and $m = sup {[u, v, w; f] : u, v, w \in [α, β]} .$

{proof*}

Consider the following identities:

	$f (\bar{x}) =$	$f (g_{1} (x_{n})) + [g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f] (\bar{x} - g_{1} (x_{n}))$
		$+ [\bar{x}, g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f] (\bar{x} - g_{1} (x_{n})) (\bar{x} - g_{2} (g_{1} (x_{n}))),$

whence, by (6) and $f (\bar{x}) = 0$ , we get

(15)

\bar{x} - x_{n + 1} = - \frac{[\bar{x}, g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f]}{[g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f]} (\bar{x} - g_{1} (x_{n})) (\bar{x} - g_{2} (g_{1} (x_{n}))) .

Next, $g_{1}$ and $g_{2}$ obey the following identities:

(16)		$\bar{x} - g_{1} (x_{n})$	$=$	$g_{1} (\bar{x}) - g_{1} (x_{n}) = [x_{n}, \bar{x}; g_{1}] (\bar{x} - x_{n}),$
(17)		$\bar{x} - g_{2} (g_{1} (x_{n}))$	$=$	$[g_{1} (x_{n}), g_{1} (\bar{x}); g_{2}] [x_{n}, \bar{x}; g_{1}] (\bar{x} - x_{n}) .$

From the definitions of $g_{1}$ and $g_{2}$ we deduce

(18)

0 < [x_{n}, \bar{x}; g_{1}] = 1 - \frac{[x_{n}, \bar{x}; f]}{[β, b; f]} < 1 - \frac{[α, a; f]}{[β, b; f]} = l < 1

and

	$[g_{1} (x_{n}), g_{1} (\bar{x}); g_{2}]$	$= 1 - \frac{[g_{1} (x_{n}), \bar{x}; f]}{[α, a; f]}$
		$> 1 - \frac{[β, b; f]}{[α, a; f]} = \frac{[β, b; f]}{[α, a; f]} (\frac{[α, a; f]}{[β, b; f]} - 1) = - l \frac{[β, b; f]}{[α, a; f]},$

whence $- [g_{1} (x_{n}), g_{1} (\bar{x}); g_{2}] < l \frac{[β, b; f]}{[α, a; f]} .$

Since $g_{2}$ is nondecreasing we get

(19)

| [g_{1} (x_{n}), g_{1} (\bar{x}); g_{2}] | < l \frac{[β, b; f]}{[α, a; f]} .

According to Lemma 2

[g_{1} (x_{n}), g_{2} (g_{1} (x_{n})); f] > [α, a; f], n = 1, 2, \dots

and by (15)–(19) we finally get

| \bar{x} - x_{n + 1} | \leq \frac{m l^{3} [β, b; f]}{{[a, α; f]}^{2}} {| \bar{x} - x_{n} |}^{2}, n = 1, 2, \dots \displayqed

References

[1] Balázs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., 21, no. 2, pp. 111–117, 1992.
[2] Casulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25–44, 1977.
[3] Cobzaş, S., Mathematical Analysis, Presa Universitară Clujeană, Cluj-Napoca, 1997 (in Romanian).
[4] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.
[5] Păvăloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens’s method, Mathematica (Cluj), 35 (58), no. 1, pp. 71–76, 1993.
[6] Păvăloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 23, no. 1, pp. 95–100, 1994.
[7] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, no. 1–2, pp. 69–82, 1995.
[8] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.

2002

Fixed point theorems for acyclic multivalued maps and inclusions of Hammerstein type

April 11, 2022

Quadratic eigenvalue problems in acoustics

July 15, 2025

Extension and approximation of semi-Lipschitz functions on quasi-metric linear spaces

May 4, 2023

Aitken-Steffensen-type methods for nondifferentiable functions (I)

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

AITKEN-STEFFENSEN TYPE METHODS FOR NONDIFFERENTIABLE FUNCTIONS (I)∗

Abstract.

1. INTRODUCTION

Theorem 1.

Lemma 2.

Proof..

2. THE CONVERGENCE OF THE AITKEN-STEFFENSEN-LIKE METHOD

Remark 1.

Remark 2.

Theorem 3.

Proof..

Remark 3.

Remark 4.

References

Related Posts

AITKEN-STEFFENSEN TYPE METHODS FOR NONDIFFERENTIABLE FUNCTIONS (I)^∗