On a Halley-Steffensen method for approximating the solutions of scalar equations

9 years ago

Abstract

We show that the Steffensen method for solving the scalar equation $f(x)=0$, applied to equation $$h(x)=\frac{f(x)}{\sqrt{f'(x)}}=0,$$ leads to bilateral approximations for the solution. Moreover, the convergence order is at least 3, i.e. as in the case of the Halley method.

Author

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

Keywords

nonlinear equations in R; Steffensen method; Halley method; monotone iterations.

PDF

PDF-LaTeX file.

Cite this paper as:

I. Păvăloiu, On a Halley-Steffensen method for approximating the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 30 (2001) no. 1, pp. 69-74, https://ictp.acad.ro/jnaat/journal/article/view/2001-vol30-no1-art9

About this paper

Print ISSN

1222-9024

Online ISSN

2457-8126

References

[1] Adi Ben-Israel, Newton’s method with modi ed functions, Contemp. Math., 204 (1997),pp. 39-50.

[2] G. H. Brown, Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly, 84 (1977), 726{728.

[3] V. Candela and A. Marquina, Recurrence relations for rational cubic methods I: the Halley’s method , Computing 44 (1990), 169{184.

[4] G. Deslauries and S. Dubuc, Le calcul de la racine cubique selon Heron , El. Math., 51 (1996), 28{34.

[5] D. Luca and I. Pavaloiu, On the Heron’s method for the approximation of the cubic root of a real number , Rev. Anal. Numer. Theor. Approx., 28 (1997), 103{108.

[6] A. M. Ostrowski, The Solution of Equations and Systems of Equations , Academic Press, New York-London, 1960.

[7] I. Pavaloiu, On the monotonicity of the sequences of approximations obtained by Steffensen’s method , Mathematica (Cluj) 35 (58) (1993), 71-76.

[8] I. Pavaloiu, Approximation of the roots of equations by Aitken-Ste ensen-type monotonic sequences , Calcolo, 32 (1995), 69{82.

[9] T. Popoviciu, Sur la delimitation de l’erreur dans l’approximation des racines d’une equation par interpolation lineaire ou quadratique , Rev. Roumaine Math. Pures Appl., 13 (1968), 75-78.

Google Scholar Profile

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; } ON A HALLEY-STEFFENSEN METHOD FOR APPROXIMATING THE SOLUTIONS OF SCALAR EQUATIONS

ON A HALLEY-STEFFENSEN METHOD
FOR APPROXIMATING THE SOLUTIONS
OF SCALAR EQUATIONS

ION PĂVĂLOIU^∗ Dedicated to the memory of Acad. Tiberiu Popoviciu

Abstract.

In the present paper we show that the Steffensen method for solving the scalar equation $f (x) = 0$ , applied to equation

h (x) = \frac{f (x)}{\sqrt{f^{'} (x)}} = 0,

leads to bilateral approximations for the solution. Moreover, the convergence order is at least $3,$ i.e. as in the case of the Halley method.

1991 Mathematics Subject Classification:

65H05

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

1. Introduction

Let $a, b \in ℝ,$ $a < b$ , and $f : [a, b] \to ℝ$ be given. Assume that $f \in C^{4} [a, b]$ and $f^{'} (x) > 0, \forall x \in [a, b]$ . Consider the function $h : [a, b] \to ℝ$ given by $h (x) = f (x) / \sqrt{f^{'} (x)} .$ As it is well known (see e.g. [2]), the Halley method for solving

(1)

f (x) = 0

consists in constructing the sequence ${(x_{n})}_{n \geq 0}$ by

(2)

x_{n + 1} = x_{n} - \frac{h (x_{n})}{h^{'} (x_{n})}, n = 0, 1, \dots, x_{0} \in [a, b]

As it can be easily noticed, (2) is the Newton method applied to equation $h (x) = 0 .$ The advantage of using the function $h$ instead of $f$ in (2) consists

in the fact that $h$ obeys $h^{''} (\bar{x}) = 0,$ where $\bar{x}$ is a solution of (1). It is well known that $h^{''} (\bar{x}) = 0$ ensures for (2) the convergence order 3 (see [2]).

Starting from an algorithm proposed by Heron for approximating $\sqrt[3]{100},$ the authors of [4] establish the following relation:

(3)

\sqrt[3]{N} ≃ Φ (N; α, β) = α + \frac{β d_{1}}{β d_{1} + α d_{2}} (β - α)

where $d_{1} = N - α^{3},$ $d_{2} = β^{3} - N$ and $α^{3} \leq N \leq β^{3}$ . The Heron algorithm is obtained from (3) for $α = 4$ and $β = 5 .$

In the paper [5], the authors noticed that the approximation given by (3) for $\sqrt[3]{N}$ is obtained by applying one step of the chord method to equation $φ (x) = 0$ , where $φ (x) = x^{2} - N / x,$ $x > 0$ .

In [5] it is noticed that if one considers equation $f (x) = x^{3} - N$ , then, apart of a constant factor, equation $φ (x) = 0$ is equivalent to

h (x) = \frac{f (x)}{\sqrt{f^{'} (x)}} = 0, x > 0,

i.e., $1 / \sqrt{3} (x^{2} - N / x) = 0 .$ Therefore there exists a connection between the Halley method (2) and the Heron algorithm concerning the function $h .$ In the case of the Halley method there is applied the Newton method to $h (x) = 0$ whereas in the Heron method there is applied the chord method to $h (x) = 0 .$ The both methods benefit from the advantages implied by $h^{''} (\bar{x}) = 0 .$ These remarks have led in [5] to generalizations of the results from [4]. A brief analysis of the convergence order of the chord method applied to $h (x) = 0$ in the general case (quasi-Halley method) is given in [1].

In this note we shall study the convergence of an iterative method obtained by applying the Steffensen algorithm to equation $h (x) = 0,$ where $h (x) = f (x) / \sqrt{f^{'} (x)} .$ As we shall see, this method has some advantages over the Halley and chord methods applied to $h .$ The most important one is the fact that the method we propose allows the control of the absolute error at each iteration step. Its convergence order is the same as for the Halley method, being higher than the order of the chord method.

For solving (1) we shall consider the sequence

(4)

x_{n + 1} = x_{n} - \frac{h (x_{n})}{[x_{n}, φ (x_{n}); h]}, n = 0, 1, \dots, x_{0} \in [a, b]

where $φ$ will be suitably chosen, and $[x, y; f] = (f (y) - f (x)) / (y - x)$ denotes

the first order divided difference of $f$ on $x$ and $y$ . We shall call this method the Halley-Steffensen method.

2. Local convergence and error bounds

Concerning the function $f$ we shall assume the following conditions:

i.

$f \in C^{4} [a, b];$
ii.

$f^{'} (x) > 0$ for all $x \in [a, b];$
iii.

equation (1) has a solution $\bar{x} \in] a, b [;$
iv.

the function $φ$ from (4) is given by

(5) $φ (x) = x - \frac{f (x)}{λ}$

where $0 < λ < f_{d}^{'} (a),$ and $f_{d}^{'} (a)$ is the right derivative of $f$ at $a;$
v.

$f^{'} (x) < 2 λ, \forall x \in [a, b];$
vi.

$f^{''} (x) > 0, \forall x \in [a, b] .$

We notice in the beginning that

x_{n} - \frac{h (x_{n})}{[x_{n}, φ (x_{n}); h]} = φ (x_{n}) - \frac{h (φ (x_{n}))}{[x_{n}, φ (x_{n}); h]}, n = 0, 1, \dots

which shows that the Halley-Steffensen sequence obeys

(6)

x_{n + 1} = φ (x_{n}) - \frac{h (φ (x_{n}))}{[x_{n}, φ (x_{n}); h]}, n = 0, 1, \dots,

while for the first and second order derivatives we obtain

(7)		$h^{'} (x) =$	$\frac{2 {(f^{'} (x))}^{2} - f^{''} (x) f (x)}{2 {(f^{'} (x))}^{3 / 2}};$
(8)		$h^{''} (x) =$	$\frac{3 {(f^{''} (x))}^{2} - 2 f^{'''} (x) f^{'} (x)}{4 {(f^{'} (x))}^{5 / 2}} f (x) .$

Relation (8) implies $h^{''} (\bar{x}) = 0$ , while (7) implies $h^{'} (\bar{x}) = {(f^{'} (\bar{x}))}^{1 / 2} > 0 .$ Since $h^{'}$ is continuous and $h^{'} (\bar{x}) > 0$ it follows the existence of $α, β \in ℝ,$ $a \leq α < \bar{x} < β \leq b,$ such that $h^{'} (x) > 0, \forall x \in [α, β] .$

We obtain the following result:

Theorem 1.

Assume that the function $f$ and the initial approximation $x_{0}$ satisfy:

i₁.

the number $x_{0}$ is sufficiently close to $\bar{x}$ and $φ (x_{0}) \in [α, β]$ , with $α$ and $β$ determined above;
ii $_{2} .$

the function $f$ obeys (i)–(vi);

Then the Halley-Steffensen sequence $(1.4)$ converges to the solution $\bar{x}$ and, moreover,

(9)		$\| x_{n + 1} - \bar{x} \| \leq$	$\max {\| x_{n + 1} - x_{n} \|, \| x_{n + 1} - φ (x_{n}) \|}, n = 0, 1, \dots,$
(10)		$\| x_{n + 1} - \bar{x} \| \leq$	$K {\| x_{n} - \bar{x} \|}^{3}, n = 0, 1, \dots,$

where $K$ is a constant which does not depend on $n .$

Proof.

Since $f^{''} (x) > 0, \forall x \in [a, b],$ it follows that $f^{'}$ is increasing on $[a, b]$ and hence $φ^{'} (x) = 1 - f^{'} (x) / λ$ obeys $φ^{'} (x) < 0, \forall x \in [a, b] .$ The existence of the interval $[α, β] \subseteq [a, b]$ such that $h^{'} (x) > 0,$ $\forall x \in [α, β],$ has been proved above. Assumption iv) implies $\bar{x} = φ (\bar{x})$ and so, if $x_{0} < \bar{x},$ we get $φ (x_{0}) > \bar{x} .$ Analogously, $x_{0} > \bar{x} \Rightarrow φ (x_{0}) < \bar{x},$ i.e., $\bar{x} \in I_{0},$ $I_{0}$ being the interval determined by $x_{0}$ and $φ (x_{0})$ . From $h^{'} (x) > 0,$ $\forall x \in [α, β],$ it follows $h (x_{0}) < 0$ for $x_{0} < \bar{x}$ resp. $h (x_{0}) > 0$ for $x_{0} > \bar{x}$ . Relation (4) implies $x_{1} > x_{0}$ when $x_{0} < \bar{x}$ resp. $x_{1} < x_{0}$ when $x_{0} > \bar{x} .$ By (6) we get $x_{1} < φ (x_{0})$ when $x_{0} < \bar{x}$ resp. $x_{1} > φ (x_{0})$ when $x_{0} > \bar{x}$ , i.e. $x_{1} \in I_{0} .$ We shall show that $φ (x_{1}) \in I_{0} .$ For this we prove that $x_{0} < φ (φ (x_{0}))$ when $x_{0} < \bar{x}$ resp. $x_{0} > φ (φ (x_{0}))$ when $x_{0} > \bar{x} .$ For $φ (φ (x_{0}))$ we easily obtain the following expression:

φ (φ (x_{0})) = x_{0} - \frac{2}{λ} f (x_{0}) + \frac{1}{λ^{2}} f^{'} (ξ_{0}) f (x_{0}), ξ_{0} \in I_{0},

whence, taking into account (v) and $f (x_{0}) < 0$ for $x_{0} < \bar{x},$ we obtain $φ (φ (x_{0}))$ $- x_{0} > 0 .$ Analogously, if $x_{0} > \bar{x}$ then $φ (φ (x_{0})) - x_{0} < 0 .$ So, $φ (φ (x_{0})) \in I_{0} .$ Let $x_{0} < \bar{x}$ , and so $φ (x_{0}) > \bar{x}$ and $x_{0} < x_{1} < φ (x_{0}) .$ Since $φ$ is decreasing we get $φ (x_{1}) > φ (φ (x_{0})) > x_{0},$ and, on the other hand, from $x_{0} < x_{1} \Rightarrow φ (x_{0}) > φ (x_{1}),$ i.e. $φ (x_{1}) \in I_{0}$ . Analogously, if $x_{0} > \bar{x} \Rightarrow φ (x_{1}) \in I_{0} .$ Denoting by $I_{1}$ the closed interval determined by $x_{1}$ and $φ (x_{1})$ then

(11)

\bar{x} \in I_{1} and I_{0} \supset I_{1} .

Let $I_{s}$ denote the closed intervals determined by the points $x_{s}$ and $φ (x_{s})$ , $s = \bar{0, k} .$ Suppose that

(12)

I_{0} \supset I_{1} \supset \dots \supset I_{k - 1} \supset I_{k},

and $\bar{x} \in I_{k} .$ As we have shown for $x_{0},$ we can prove that the interval $I_{k + 1},$ determined by $x_{k + 1}$ and $φ (x_{k + 1}),$ obeys

I_{k} \supset I_{k + 1}

and $\bar{x} \in I_{k + 1} .$ From the above reasons, it follows that relations (9) are true. It remains to show that (10) holds, which implies the convergence of ${(x_{n})}_{n \geq 0}$ generated by (4). For this purpose we shall use the identity

h (\bar{x}) = h (x_{n}) + [x_{n}, φ (x_{n}); h] (\bar{x} - x_{n}) + [\bar{x}, x_{n}, φ (x_{n}); h] (\bar{x} - x_{n}) (\bar{x} - φ (x_{n})),

whence, taking into account (4) and $h (\bar{x}) = 0,$ it follows (see [9])

(13)

\bar{x} - x_{n + 1} = - \frac{[\bar{x}, x_{n}, φ (x_{n}); h]}{[x_{n}, φ (x_{n}); h]} (\bar{x} - x_{n}) (\bar{x} - φ (x_{n})), n = 0, 1, \dots

By (ii) and (v) we get $| φ^{'} (x) | < 1, \forall x \in I_{0},$ and so

(14)

| \bar{x} - φ (x_{n}) | < | \bar{x} - x_{n} |, n = 0, 1, \dots

On the other hand, from the mean value theorems for divided differences one obtains

(15)		$[\bar{x}, x_{n}, φ (x_{n}); h]$	$= \frac{h^{''} (ξ_{n})}{2!}, ξ_{n} \in I_{n}, and$
(16)		$[x_{n}, φ (x_{n}); h]$	$= h^{'} (η_{n}), η_{n} \in I_{n} .$

From (15) and from $h^{''} (\bar{x}) = 0$ we get

(17)

| [\bar{x}, x_{n}, φ (x_{n}); h] | = \frac{1}{2} | h^{''} (ξ_{n}) - h^{''} (\bar{x}) | = \frac{1}{2} h^{'''} (δ_{n}) | ξ_{n} - \bar{x} |,

where $δ_{n} \in I_{n} .$ Further, by $(2.10)$ it follows

(18)

| ξ_{n} - \bar{x} | \leq \max {| \bar{x} - x_{n} |, | \bar{x} - φ (x_{n}) |} \leq | \bar{x} - x_{n} | .

Denote $m_{3} = {sup}_{x \in I_{0}} | h^{'''} (x) |$ and $m_{1} = {inf}_{x \in I_{0}} | h^{'} (x) | .$ Relations (13)–(18) lead to

| x_{n + 1} - \bar{x} | \leq \frac{m_{3}}{2 m_{1}} {| x_{n} - \bar{x} |}^{3}, n = 0, 1, \dots,

i.e., (10) with $K = m_{3} / (2 m_{1}) .$ The proof is complete. ∎

3. Numerical example

Consider the equation

f (x) = x^{3} - 20, x > 0,

and the function $h (x) = \frac{1}{\sqrt{3}} (x^{2} - 20 / x) .$ Obviously, $h^{'} (x) = 2 (x + 10 / x^{2}) > 0, \forall x > 0 .$ It can be easily seen that $2.6 < \sqrt[3]{20} < 2.8 .$ We choose $φ (x) = x - (x^{3} - 20) / 20.28 .$ Then, for $x_{0} = 2.6,$ $φ (x_{0}) < 2.8,$ and hence our theorem may be applied. We obtain the following results:

$n$	$x_{n}$	$φ (x_{n})$	$h (x_{n})$
$0$	2,600 000 000 0 $\cdot$ 10⁺⁰⁰	2,719 526 627 2 $\cdot$ 10⁺⁰⁰	-9,323 076 923 2 $\cdot$ 10^-01
$1$	2,714 420 633 0 $\cdot$ 10⁺⁰⁰	2,714 417 345 3 $\cdot$ 10⁺⁰⁰	2,456 359 652 6 $\cdot$ 10^-05
$2$	2,714 417 616 6 $\cdot$ 10⁺⁰⁰	2,714 417 616 6 $\cdot$ 10⁺⁰⁰	-1,455 191 522 8 $\cdot$ 10^-11

References

[1] Adi Ben-Israel, Newton’s method with modified functions, Contemp. Math., 204 (1997), pp. 39–50.
[2] G. H. Brown, Jr., On Halley’s variation of Newton’s method, Amer. Math. Monthly, 84 (1977), 726–728.
[3] V. Candela and A. Marquina, Recurrence relations for rational cubic methods I: the Halley’s method, Computing 44 (1990), 169–184.
[4] G. Deslauries and S. Dubuc, Le calcul de la racine cubique selon Héron, El. Math., 51 (1996), 28–34.
[5] ^†^†margin: clickable $\to$ D. Luca and I. Păvăloiu, On the Heron’s method for the approximation of the cubic root of a real number, Rev. Anal. Numér. Théor. Approx., 28 (1997), 103–108.
[6] A. M. Ostrowski, The Solution of Equations and Systems of Equations, Academic Press, New York–London, 1960.
[7] ^†^†margin: clickable $\to$ I. Păvăloiu, On the monotonicity of the sequences of approximations obtained by Stef- fensen’s method, Mathematica (Cluj) 35 (58) (1993), 71–76.
[8] ^†^†margin: clickable $\to$ I. Păvăloiu, Approximation of the roots of equations by Aitken-Steffensen-type monoto- nic sequences, Calcolo, 32 (1995), 69–82.
[9] T. Popoviciu, ^†^†margin: available soon,
refresh and click here $\to$ Sur la délimitation de l’erreur dans l’approximation des racines d’une équation par interpolation linéaire ou quadratique, Rev. Roumaine Math. Pures Appl., 13 (1968), 75–78.

Received June 17, 2000.

2001

On some Aitken-Steffensen-Halley-type method for approximating the roots of scalar equations

January 20, 2018

Continuation results for mappings of contractive type

April 8, 2022

Korovkin type error estimates for Meyer-Konig and Zeller operators

February 16, 2023

(9)		$\| x_{n + 1} - \bar{x} \| \leq$	$\max {\| x_{n + 1} - x_{n} \|, \| x_{n + 1} - φ (x_{n}) \|}, n = 0, 1, \dots,$
(10)		$\| x_{n + 1} - \bar{x} \| \leq$	$K {\| x_{n} - \bar{x} \|}^{3}, n = 0, 1, \dots,$

On a Halley-Steffensen method for approximating the solutions of scalar equations

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Article on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

ON A HALLEY-STEFFENSEN METHOD FOR APPROXIMATING THE SOLUTIONS OF SCALAR EQUATIONS

Abstract.

1991 Mathematics Subject Classification:

1. Introduction

2. Local convergence and error bounds

Theorem 1.

Proof.

3. Numerical example

References

Related Posts

ON A HALLEY-STEFFENSEN METHOD
FOR APPROXIMATING THE SOLUTIONS
OF SCALAR EQUATIONS