On the Chebyshev method for approximating the eigenvalues of linear operators

9 years ago

(original), Chebyshev method, eigenvalue/eigenvector problems, html, Newton method, Numerical Analysis, paper, PDF, semilocal convergence, solving F(x)=0 iteratively, works

Abstract

We study the approximation of an eigenpair (an eigenvalue and a corresponding eigenvector) of a a linear operator T from X to X, X be a Banach space.

The eigenpair is regarded as a solution of a nonlinear system obtained by considering the usual definition plus a norming function and then applying the Chebyshev or the Newton method.

We take into account that the augmented mapping has the third Frechet derivative the null operator, and we give a semilocal convergence result, which ensures the r-order three (cubic r-order) of the iterates.

We consider next the finite dimensional case, and analyse the computation of an eigenpair of a matrix. We also compare in this case the efficiency of the Newton and Chebyshev method, and find out that the later is more efficient.

Authors

Emil Cătinaş

Emil Cătinaş

Ion Păvăloiu

Ion Păvăloiu

Keywords

linear operator; eigenvalue; eigenvector; eigenpair; Newton method; Chebyshev method; semilocal convergence; r-convergence order.

Cite this paper as:

E. Cătinaş, I. Păvăloiu, On the Chebyshev method for approximating the eigenvalues of linear operators, Rev. Anal. Numér. Théor. Approx., 25 (1996) nos. 1-2, pp. 43-56.

PDF

Scanned paper: on the journal website.

Latex-pdf version of the paper. (soon)

About this paper

Print ISSN

2457-6794

Online ISSN

2501-059X

Google Scholar citations

[1] M.P. Anselone, L.B. Rall, The solution of characteristic value-vector problems by Newton method, Numer. Math. 11 (1968), pp. 38–45.
CrossRef

[2] P.G. Ciarlet, Introduction a l’analyse numerique matricielle et a l’optimisation, Mason, Paris, 1990.

[3] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.

[4] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.

[5] V.S. Kartısov, F.L. Iuhno, O nekotorıh Modifikatiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vıcisl. matem. i matem. fiz. (33) (1973) 9, pp. 1403–1409.

[6] I. Pavaloiu, Sur les procedes iteratifs a un ordre eleve de convergence, Mathematica (Cluj) 12 (35) (1970) 2, pp. 309–324.
paper

[7] J.F. Traub, 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; } On the Chebyshev method for approximating the eigenvalues of linear operators

On the Chebyshev method for approximating
the eigenvalues of linear operators

Emil Cătinaş and Ion Păvăloiu
(Cluj-Napoca)

1. Introduction

Approaches to the problem of approximating the eigenvalues of linear operators by the Newton method have been done in a series of papers ([1], [3], [4], [5]). There is a special interest in using the Newton method because the operatorial equation to be solved has a special form, as we shall see. We shall study in the following the convergence of the Chebyshev method attached to this problem and we shall apply the results obtained for the approximation of an eigenvalue and of a corresponding eigenvector for a matrix of real or complex numbers. It is known that the convergence order of Newton method is usually 2 and the convergence order of Chebyshev method is usually 3. Taking into account as well the number of operations made at each step, we obtain that the Chebyshev method is more efficient than the Newton method.

Let $E$ be a Banach space over $K$ , where $K = ℝ$ or $K = ℂ$ , and $T : E \to E$ a linear operator. It is well known that the scalar $λ$ is an eigenvalue of $T$ if the equation

(1)

T x - λ x = θ

has at least one solution $\bar{x} \neq θ$ , where $θ$ is the null element of the space $E$ . The elements $x \neq θ$ that satisfy equation (1) are called eigenvectors of the operator $T$ , corresponding to the eigenvalue $λ$ .

For the simultaneously determination of the eigenvalues and eigenvectors of $T$ we can proceed in the following way.

We attach to the equation (1) an equation of the form

(2)

G x = 1

where $G$ is a linear functional $G : E \to K .$

Consider the real Banach space $F = E \times K$ , with the norm given by

(3)

‖ u ‖ = \max {‖ x ‖, | λ |}, u \in F, u = (\binom{x}{λ}), with x \in E and λ \in K .

In this space we consider the operator $f : F \to F$ given by

(4)

f (\binom{x}{λ}) = (\begin{matrix} T x - λ x \\ G x - 1 \end{matrix}) .

If we denote by $θ_{1} = (\binom{θ}{0})$ the null element of the space $F$ , then the eigenvalues and the corresponding eigenvectors of the operator $T$ are solutions of the equation

(5)

f (u) = θ_{1} .

Obviously, $f$ is not a linear operator.

It can be easily seen that the first order Fréchet derivative of $f$ has the following form [4]:

(6)

f^{'} (u_{0}) h = (\begin{matrix} T h_{1} - λ_{0} h_{1} - λ_{1} x_{0} \\ G h_{1} \end{matrix}),

where $u_{0} = (\binom{x_{0}}{λ_{0}})$ and $h = (\binom{h_{1}}{λ_{1}}) .$ For the second order derivative of $f$ we obtain the expression

(7)

f^{''} (u_{0}) h k = (\begin{matrix} - λ_{2} h_{1} - λ_{1} h_{2} \\ 0 \end{matrix}),

where $k = (\binom{h_{2}}{λ_{2}}) .$

The Fréchet derivatives of order higher than $2$ of $f$ are null.

Considering the above forms of the Fréchet derivatives of $f$ , in the following we shall study the convergence of the Chebyshev method for the operators having the third order Fréchet derivative the null operator.

2. The convergence of Chebyshev method

The iterative Chebyshev method for solving equation (5) consists in the successive construction of the elements of the sequence ${(u_{n})}_{n \geq 0}$ given by

(8)

u_{n + 1} = u_{n} - Γ_{n} f (u_{n}) - \frac{1}{2} Γ_{n} f^{''} (u_{n}) {(Γ_{n} f (u_{n}))}^{2}, n = 0, 1, \dots, u_{0} \in F,

where $Γ_{n} = {[f^{'} (u_{n})]}^{- 1} .$

Let $u_{0} \in F$ and $δ > 0, b > 0$ be two real numbers. Denote $S = {u \in F :$ $∥ u - u_{0} ∥ \leq δ} .$ If

m_{2} = sup_{u \in S} ‖ f^{''} (u) ‖,

then

	$sup_{u \in S} ‖ f^{'} (u) ‖$	$\leq ‖ f^{'} (u_{0}) ‖ + m_{2} δ,$
	$sup_{u \in S} ‖ f (u) ‖$	$\leq ∥ f (u_{0}) ∥ + δ ∥ f^{'} (u_{0}) ∥ + m_{2} δ^{2} = : m_{0} .$

Consider the numbers

(9)

\begin{matrix} μ = \frac{1}{2} m_{2}^{2} b^{4} (1 + \frac{1}{4} m_{2} m_{0} b^{2}) \\ ν = b (1 + \frac{1}{2} m_{2} m_{0} b^{2}) \end{matrix}

With the above notations, the following theorem holds:

Theorem 1.

If the operator $f$ is three times differentiable with $f^{'''} (u) \equiv θ_{3}$ for all $u \in S$ ( $θ_{3}$ being the $3$ -linear null operator) and if, moreover, there exist $u_{0} \in F$ , $δ > 0, b > 0$ such that the following relations hold

i. the operator $f^{'} (u)$ has a bounded inverse for all $u \in S$ , and

‖ f^{'} {(u)}^{- 1} ‖ \leq b;

ii. the numbers $μ$ and $ν$ given by $(9)$ satisfy the relations

ρ_{0} = \sqrt{μ} ‖ f (u_{0}) ‖ < 1

and

\frac{ν ρ_{0}}{\sqrt{μ} (1 - ρ_{0})} \leq δ,

then the following properties hold:

j. ${(u_{n})}_{n \geq 0}$ given by $(8)$ is convergent;

jj. if $\bar{u} = lim_{u \to \infty} u_{n},$ then $\bar{u} \in S$ and $f (\bar{u}) = θ_{1};$

jjj. $‖ u_{n + 1} - u_{n} ‖ \leq \frac{ν ρ_{0}^{3^{n}}}{\sqrt{μ}}, n = 0, 1, \dots;$

jv. $‖ \bar{u} - u_{n} ‖$ $\leq \frac{ν ρ_{0}^{3^{n}}}{\sqrt{μ} (1 - ρ_{0}^{3^{n}})}, n = 0, 1, \dots$

Proof.

Denote by $g : S \to F$ the following mapping:

(10)

g (u) = - Γ (u) f (u) - \frac{1}{2} Γ (u) f^{''} (u) {(Γ (u) f (u))}^{2},

where $Γ (u) = f^{'} {(u)}^{- 1} .$

It can be easily seen that for all $u \in S$ the following identity holds

	$f (u) + f^{'} (u) g (u) + \frac{1}{2} f^{''} (u) g^{2} (u) =$
	$= \frac{1}{2} f^{''} (u) [f^{'} {(u)}^{- 1} f (u), f^{'} {(u)}^{- 1} f^{''} (u) {(f^{'} {(u)}^{- 1} f (u))}^{2}] +$
	$+ \frac{1}{8} f^{''} (u) {[f^{'} {(u)}^{- 1} f^{''} (u) {(f^{'} {(u)}^{- 1} f (u))}^{2}]}^{2}$

whence we obtain

(11)

‖ f (u) + f^{'} (u) g (u) + \frac{1}{2} f^{''} (u) g^{2} (u) ‖ \leq \frac{1}{2} m_{2}^{2} b^{4} (1 + \frac{1}{4} m_{0} m_{2} b^{2}) {‖ f (u) ‖}^{3},

(12)

‖ f (u) + f^{'} (u) g (u) + \frac{1}{2} f^{''} (u) g^{2} (u) ‖ \leq μ {‖ f (u) ‖}^{3}, for all u \in S .

Similarly, by (10) and taking into account the notations we made, we get

(13)

‖ g (u) ‖ \leq ν ‖ f (u) ‖, for all u \in S .

Using the hypotheses of the theorem, the inequality (12) and the fact that $f^{'''} (u) = θ_{3}$ , we obtain the following inequality:

	$‖ f (u_{1}) ‖ \leq$	$‖ f (u_{1}) - f (u_{0}) - f^{'} (u_{0}) g (u_{0}) - \frac{1}{2} f^{''} (u_{0}) g^{2} (u_{0}) ‖$
		$+ ‖ f (u_{0}) + f^{'} (u_{0}) g (u_{0}) + \frac{1}{2} f^{''} (u_{0}) g^{2} (u_{0}) ‖$
	$\leq$	$μ {‖ f (u_{0}) ‖}^{3} .$

Since $u_{1} - u_{0} = g (u_{0})$ , by (12) we have

‖ u_{1} - u_{0} ‖ \leq ν ‖ f (u_{0}) ‖ = \frac{ν \sqrt{μ} ‖ f (u_{0}) ‖}{\sqrt{μ}} < \frac{ν ρ_{0}}{\sqrt{μ} (1 - ρ_{0})} \leq δ,

whence it follows that $u_{1} \in S$ .

Suppose now that the following properties hold:

a)

$u_{i} \in S$ , $i = \bar{0, k};$
b)

$‖ f (u_{i}) ‖ \leq μ {‖ f (u_{i - 1}) ‖}^{3}, i = \bar{1, k} .$

By the fact that $u_{k} \in S$ , using (12) it follows

(14)

‖ f (u_{k + 1}) ‖ \leq μ {‖ f (u_{k}) ‖}^{3},

and from relation $u_{k + 1} - u_{k} = g (u_{k})$

(15)

‖ u_{k + 1} - u_{k} ‖ < ν ‖ f (u_{k}) ‖ .

The inequalities b) and (14) lead us to

(16)

‖ f (u_{i}) ‖ \leq \frac{1}{\sqrt{μ}} {(\sqrt{μ} ‖ f (u_{0}) ‖)}^{3^{i}}, i = \bar{1, k + 1} .

We have that $u_{k + 1} \in S :$

(17)

‖ u_{k + 1} - u_{0} ‖ \leq \sum_{i = 1}^{k + 1} ‖ u_{i} - u_{i - 1} ‖ \leq \sum_{i = 1}^{k + 1} ν ‖ f (u_{i - 1}) ‖ \leq \frac{ν}{\sqrt{μ}} \sum_{i = 1}^{k + 1} ρ_{0}^{3^{i - 1}} \leq \frac{ν ρ_{0}}{(1 - ρ_{0}) \sqrt{μ}} .

Now we shall prove that the sequence ${(u_{n})}_{n \geq 0}$ is Cauchy. Indeed, for all $m, n \in ℕ$ we have

(18)		$‖ u_{n + m} - u_{n} ‖ \leq$	$\sum_{i = 0}^{m - 1} ‖ u_{n + i + 1} - u_{n + i} ‖$
	$\leq$	$ν \sum_{i = 0}^{m - 1} ‖ f (u_{n + i}) ‖$
	$\leq$	$\frac{ν}{\sqrt{μ}} \sum_{i = 0}^{m - 1} ρ_{0}^{3^{n + i}}$
	$=$	$\frac{ν}{\sqrt{μ}} ρ_{0}^{3^{n}} \sum_{i = 0}^{m - 1} ρ_{0}^{3^{n + i} - 3^{n}}$
	$\leq$	$\frac{ν ρ_{0}^{3^{n}}}{\sqrt{μ} (1 - ρ_{0}^{3^{n}})},$

whence, taking into account that $ρ_{0} < 1$ , it follows that ${(u_{n})}_{n \geq 0}$ converges. Let $\bar{u} = {lim}_{n \to \infty} u_{n} .$ Then, for $m \to \infty$ in (17) it follows jv. The consequence jjj. follows from (15) and (16). ∎

3. The approximation of the eigenvalues and eigenvectors of matrices

In the following we shall apply the previously studied method to the approximation of eigenvalues and eigenvectors of matrices with elements real or complex numbers.

Let $p \in ℕ$ and the matrix $A = {(a_{i j})}_{i, j = \bar{1, p}}$ , where $a_{i j} \in K$ , $i, j = \bar{1, p}$ .

Using the above notations, we shall consider $E = K^{p}$ and $F = K^{p} \times K$ . Any solution of equation

(19)

f (\binom{x}{λ}) := (\binom{A x - λ x}{x_{i_{0}} - 1}) = (\binom{θ}{0}),

$i_{0} \in {1, \dots, p}$ being fixed, where $x = (x_{1}, \dots, x_{p}) \in K^{p}$ and $θ = (0, \dots, 0) \in K^{p},$ will lead us to an eigenvalue of $A$ and to a corresponding eigenvector. For the sake of simplicity denote $λ = x_{p + 1}$ , so that equation 19 is represented by the system

(20)

f_{i} (x_{1}, \dots, x_{p}, x_{p + 1}) = 0, i = \bar{1, p + 1}

where

(21)

f_{i} (x_{1}, \dots, x_{p + 1}) = a_{i 1} x_{1} + \dots + (a_{i i} - x_{p + 1}) x_{i} + \dots + a_{i p} x_{p}, i = \bar{1, p}

and

(22)

f_{p + 1} (x) = x_{i_{0}} - 1 .

Denote by $P$ the mapping $P : K^{p + 1} \to K^{p + 1}$ defined by relations (21) and (22).

Let ${\bar{x}}_{n} = (x_{1}^{n}, \dots, x_{p + 1}^{n}) \in K^{p + 1}$ . Then the first order Fréchet derivative of the operator $P$ at ${\bar{x}}_{n}$ has the following form

(23)

P^{'} ({\bar{x}}_{n}) h = (\begin{matrix} a_{11} - x_{p + 1}^{n} & a_{12} & \dots & a_{1 i_{0}} & \dots & a_{1 p} & - x_{1}^{n} \\ a_{21} & a_{22} - x_{p + 1}^{n} & \dots & a_{2 i_{0}} & \dots & a_{2 p} & - x_{2}^{n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{p 1} & a_{p 2} & \dots & a_{p i_{0}} & \dots & a_{p p} - x_{p + 1}^{n} & - x_{p}^{n} \\ 0 & 0 & \dots & 1 & \dots & 0 & 0 \end{matrix}) (\begin{matrix} h_{1} \\ h_{2} \\ ⋮ \\ h_{p} \\ h_{p + 1} \end{matrix}),

where $\bar{h} = (h_{1}, \dots, h_{p + 1}) \in K^{p + 1} .$ If we write $\bar{k} = (k_{1}, \dots, k_{p + 1}) \in K^{p + 1}$ then for the second order Fréchet derivative we get

(24)

P^{''} ({\bar{x}}_{n}) \bar{k} \bar{h} = (\begin{matrix} - k_{p + 1} & 0 & \dots & 0 & - k_{1} \\ 0 & - k_{p + 1} & \dots & 0 & - k_{2} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & - k_{p + 1} & - k_{p} \\ 0 & 0 & \dots & 0 & 0 \end{matrix}) (\begin{matrix} h_{1} \\ h_{2} \\ ⋮ \\ h_{p} \\ h_{p + 1} \end{matrix}) .

Denote by $Γ ({\bar{x}}_{n})$ the inverse of the matrix attached to the operator $P^{'} (x_{n})$ and ${\bar{u}}_{n} =$ $Γ ({\bar{x}}_{n}) P ({\bar{x}}_{n}) = (u_{1}^{n}, u_{2}^{n}, \dots, u_{p + 1}^{n}) .$ Let ${\bar{v}}_{n} = P^{''} ({\bar{x}}_{n}) {(Γ ({\bar{x}}_{n}) P ({\bar{x}}_{n}))}^{2} = P^{''} ({\bar{x}}_{n})$ ${\bar{u}}_{n}^{2} .$ We obtain the following representation

(25)

{\bar{v}}_{n} = P^{''} ({\bar{x}}_{n}) {\bar{u}}_{n}^{2} = (\begin{matrix} - u_{p + 1}^{n} & 0 & \dots & 0 & - u_{1}^{n} \\ 0 & - u_{p + 1}^{n} & \dots & 0 & - u_{2}^{n} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & - u_{p + 1}^{n} & - u_{p}^{n} \\ 0 & 0 & \dots & 0 & 0 \end{matrix}) (\begin{matrix} u_{1}^{n} \\ u_{2}^{n} \\ ⋮ \\ u_{p}^{n} \\ u_{p + 1}^{n} \end{matrix}) .

From this relation we can easily deduce the equalities

(26)

\begin{matrix} v_{i}^{n} = - 2 u_{p + 1}^{n} u_{i}^{n}, i = \bar{1, p}; \\ v_{p + 1}^{n} = 0 . \end{matrix}

Denoting ${\bar{w}}_{n} = (w_{1}^{n}, w_{2}^{n}, \dots, w_{p + 1}^{n}) = Γ (x_{n}) {\bar{v}}_{n}$ and supposing that ${\bar{x}}_{n}$ is an approximation of the solution of system (20), then the next approximation ${\bar{x}}_{n + 1}$ given by method (8) is obtained by

(27)

{\bar{x}}_{n + 1} = {\bar{x}}_{n} - {\bar{u}}_{n} - \frac{1}{2} {\bar{w}}_{n}, i = 0, 1, \dots

Consider $K^{p}$ with the norm of an element $x = (x_{1}, \dots, x_{p})$ given by the equality

(28)

‖ x ‖ = \max_{1 \leq i \leq p} {| x_{i} |},

and consequently

(29)

‖ A ‖ = \max_{1 \leq i \leq p} \sum_{j = 1}^{p} | a_{i j} | .

It can be easily seen that $‖ P^{''} ({\bar{x}}_{n}) ‖ = 2,$ for all ${\bar{x}}_{n} \in K^{p + 1} .$ Let ${\bar{x}}_{0} \in K^{p + 1}$ be an initial approximation of the solution of system (20). Consider a real number $r > 0$ and the set $\bar{S} = {x \in K^{p + 1} ∣ ‖ x - x_{0} ‖ \leq r}$ . Denote by

	${\bar{m}}_{0} =$	$‖ P ({\bar{x}}_{0}) ‖ + r ‖ P^{'} ({\bar{x}}_{0}) ‖ + 2 r^{2},$
	$\bar{μ} =$	$2 {\bar{b}}^{4} (1 + \frac{1}{2} {\bar{m}}_{0} {\bar{b}}^{2}),$
	$\bar{ν} =$	$\bar{b} (1 + {\bar{m}}_{0} {\bar{b}}^{2}),$

where $\bar{b} = {sup}_{x \in \bar{S}} ‖ Γ (x) ‖, Γ (x)$ being the inverse of the matrix attached to the operator $P^{'} (x)$ .

Taking into account the results obtained in Section 2, the following consequence holds:

Corollary 2.

If ${\bar{x}}_{0} \in K^{p + 1}$ and $r \in ℝ, r > 0,$ are chosen such that the matrix attached to the operator $P^{'} (x)$ is nonsingular for all $x \in \bar{S}$ , and the following inequalities hold:

ρ_{0} < \sqrt{\bar{μ}} ‖ P ({\bar{x}}_{0}) ‖ < 1

\frac{\bar{ν} {\bar{ρ}}_{0}}{\sqrt{\bar{μ}} (1 - {\bar{ρ}}_{0})} \leq r

then the following properties are true

j $_{1}$ .

the sequence ${({\bar{x}}_{n})}_{n \geq 0}$ generated by $(27)$ is convergent;
jj $_{1}$ .

if $\bar{x} = lim_{n \to \infty} {\bar{x}}_{n}$ , then $P (\bar{x}) = θ_{1} = (0, \dots, 0) \in K^{p + 1};$
jjj $_{1}$ .

$‖ {\bar{x}}_{n + 1} - {\bar{x}}_{n} ‖ \leq \frac{\bar{ν} {\bar{ρ}}_{0}^{3^{n}}}{\sqrt{\bar{μ}}}, n = 0, 1, \dots;$
jv $_{1}$ .

$‖ \bar{x} - {\bar{x}}_{n} ‖ \leq \frac{\bar{ν} {\bar{ρ}}_{0}^{3^{n}}}{\sqrt{\bar{μ}} (1 - {\bar{ρ}}_{0}^{3^{n}})}, n = 0, 1, \dots$

Remark.

If the radius $r$ of the ball $\bar{S}$ is given and there exists $P^{'} {(x_{0})}^{- 1}$ and $2 r ‖ P^{'} {(x_{0})}^{- 1} ‖$ $< 1$ , then

‖ P^{'} {(x)}^{- 1} ‖ \leq \frac{‖ P^{'} {(x_{0})}^{- 1} ‖}{1 - 2 r ‖ P^{'} {(x_{0})}^{- 1} ‖},

for all $x \in \bar{S}$ and in the above Corollary, taking into account the proof of Theorem 1, we can take

\bar{b} = \frac{‖ P^{'} {(x_{0})}^{- 1} ‖}{1 - 2 r ‖ P^{'} {(x_{0})}^{- 1} ‖} .

4. A comparison to the Newton method

Note that if in (27) we neglect the term $- \frac{1}{2} {\bar{w}}_{n}$ , then we get the Newton method:

{\bar{x}}_{n + 1} = {\bar{x}}_{n} - {\bar{u}}_{n} = {\bar{x}}_{n} - Γ ({\bar{x}}_{n}) F ({\bar{x}}_{n}), n = 0, 1, \dots .

In order to compare the Newton method and the Chebyshev method, we shall consider that the linear systems which appear in both methods are solved by the Gauss method.

While the Newton method require at each step the solving of a system $A x = b$ , the Chebyshev method require the solving of two linear systems $A x = b, A y = c$ with the same matrix $A$ and the vector $c$ depending on the solution $x$ of the first system. So, we shall adapt the Gauss method in order to perform as few as possible multiplications and divisions. When comparing the two methods we shall neglect the number of addition and subtraction operations.

The solving of a given linear system $A x = b, A \in M_{m} (K), b, x \in K^{m}$ , (where we have denoted $m = p + 1$ ) using the Gauss method consists in two stages. In the first stage, the given system is transformed into an equivalent one but with the matrix of the coefficients being upper triangular. In the second stage the unknowns ${(x_{i})}_{i = 1, m}$ are determined by backward substitution.

The first stage. There are performed $m - 1$ steps, at each one vanishing the elements on the same column below the main diagonal.

We write the initial system in the form

(\begin{matrix} a_{11}^{1} & \dots & a_{1 m}^{1} \\ ⋮ & ⋮ \\ a_{m 1}^{1} & \dots & a_{m m}^{1} \end{matrix}) (\begin{matrix} x_{1} \\ ⋮ \\ x_{m} \end{matrix}) = (\begin{matrix} b_{1}^{1} \\ ⋮ \\ b_{m}^{1} \end{matrix}) .

Suppose that $a_{11}^{1} \neq 0, a_{11}^{1}$ being called the first pivote. The first line in the system is multiplied by $α = - \frac{a_{21}^{1}}{a_{11}^{1}}$ and is added to the second one, which becomes $0, a_{22}^{2}, a_{23}^{2}, \dots, a_{2 m}^{2}, b_{2}^{2},$ after performing $m + 1$ multiplication or division $(M / D)$ operations. After $m - 1$ such transformations the system becomes

(\begin{matrix} a_{11}^{1} & a_{12}^{1} & \dots & a_{1 m}^{1} \\ 0 & a_{22}^{2} & \dots & a_{2 m}^{2} \\ ⋮ & ⋮ & ⋮ \\ 0 & a_{m 2}^{2} & \dots & a_{m m}^{2} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{m} \end{matrix}) = (\begin{matrix} b_{1}^{1} \\ b_{2}^{2} \\ ⋮ \\ b_{m}^{2} \end{matrix}) .

Hence at the first step there were performed $(m - 1) (m + 1)$ $M / D$ operations.

In the same manner, at the $k$ -th step we have the system

(\begin{matrix} a_{11}^{1} & a_{12}^{1} & \dots & a_{1 k}^{1} & a_{1, k + 1}^{1} & \dots & a_{1 m}^{1} \\ 0 & a_{22}^{2} & \dots & a_{2 k}^{2} & a_{2, k + 1}^{2} & \dots & a_{2 m}^{2} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & a_{k k}^{k} & a_{k, k + 1}^{k} & \dots & a_{k m}^{k} \\ 0 & 0 & \dots & a_{k + 1, k}^{k} & a_{k + 1, k + 1}^{k} & \dots & a_{k + 1, m}^{k} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & a_{m k}^{k} & a_{m, k + 1}^{k} & \dots & a_{m m}^{k} \end{matrix}) (\begin{matrix} x_{1}^{} \\ x_{2}^{} \\ ⋮ \\ x_{k}^{} \\ x_{k + 1}^{} \\ ⋮ \\ x_{m}^{} \end{matrix}) = (\begin{matrix} b_{1}^{1} \\ b_{2}^{2} \\ ⋮ \\ b_{k}^{k} \\ b_{k + 1}^{k} \\ ⋮ \\ b_{m}^{k} \end{matrix}) .

Supposing the $k$ -th pivote $a_{k k}^{k} \neq 0$ and performing $(m - k) (m - k + 2)$ $M / D$ operations we get

(\begin{matrix} a_{11}^{1} & a_{12}^{1} & \dots & a_{1 k}^{1} & a_{1, k + 1}^{1} & \dots & a_{1 m}^{1} \\ 0 & a_{22}^{2} & \dots & a_{2 k}^{2} & a_{2, k + 1}^{2} & \dots & a_{2 m}^{2} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & a_{k k}^{k} & a_{k, k + 1}^{k} & \dots & a_{k, m}^{k} \\ 0 & 0 & \dots & 0 & a_{k + 1, k + 1}^{k + 1} & \dots & a_{k + 1, m}^{k + 1} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & 0 & a_{m, k + 1}^{k + 1} & \dots & a_{m m}^{k + 1} \end{matrix}) (\begin{matrix} x_{1}^{} \\ x_{2}^{} \\ ⋮ \\ x_{k}^{} \\ x_{k + 1}^{} \\ ⋮ \\ x_{m}^{} \end{matrix}) = (\begin{matrix} b_{1}^{1} \\ b_{2}^{2} \\ ⋮ \\ b_{k}^{k} \\ b_{k + 1}^{k + 1} \\ ⋮ \\ b_{m}^{k + 1} \end{matrix}) .

At each step $k$ , the elements below the $k$ -th pivote vanish, so they are not needed any more in the solving of the system.

The corresponding memory in the computer is used keeping in it the coefficients

- \frac{a_{k + 1, k}^{k}}{a_{k k}^{k}}, \dots, - \frac{a_{m k}^{k}}{a_{k k}^{k}},

which, of course, will be needed only for solving another system $A y = c$ , with $c$ depending on $x$ , the solution of $A x = b$ .

At the first stage there are performed

(m - 1) (m + 1) + \dots + 1 \cdot 3 = \frac{2 m^{3} + 3 m^{2} - 5 m}{6} M / D operations.

The second stage. Given the system

(\begin{matrix} a_{11}^{1} & a_{12}^{1} & \dots & a_{1 m}^{1} \\ 0 & a_{22}^{2} & \dots & a_{2 m}^{2} \\ ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & a_{m m}^{m} \end{matrix}) (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{m} \end{matrix}) = (\begin{matrix} b_{1}^{1} \\ b_{2}^{2} \\ ⋮ \\ b_{m}^{m} \end{matrix})

the solution $x$ is computed in the following way:

\begin{matrix} x_{m} = b_{m}^{m} / a_{m m}^{m}, \\ ⋮ \\ x_{k} = (b_{k}^{k} - (a_{k, k + 1}^{k} x_{k + 1} + \dots + a_{k m}^{k} x_{m})) / a_{k k}^{k}, \\ ⋮ \\ x_{1} = (b_{1}^{1} - (a_{12}^{1} x_{2} + \dots + a_{1 m}^{1} x_{m})) / a_{11}^{1} . \end{matrix}

At this stage there are performed $1 + 2 + \dots + m = \frac{m (m + 1)}{2} M / D$ operations. In the both stages, there are totally performed

\frac{m^{3}}{3} + m^{2} - \frac{m}{3} M / D operations.

In the case when we solve the systems $A x = b, A y = c$ , where the vector $c$ depends on the solution $x$ , we first apply the Gauss method for the system $A x = b$ and at the first stage we keep below the main diagonal the coefficients by which the pivotes were multiplied.

Then we apply to the vector $c$ the transformations performed to the vector $b$ when solving $A x = b$ .

Denote $c = {(c_{i}^{1})}_{i = 1, m} .$

At the first step

\begin{matrix} c_{2}^{2} := a_{21} c_{1}^{1} + c_{2}^{1} \\ ⋮ \\ c_{m}^{2} := a_{m 1} c_{1}^{1} + c_{m}^{1} . \end{matrix}

At the $k$ -th step

\begin{matrix} c_{k + 1}^{k + 1} := a_{k + 1, k} c_{k}^{k} + c_{k + 1}^{k} \\ ⋮ \\ c_{m}^{k + 1} := a_{m k} c_{k}^{k} + c_{m}^{k} . \end{matrix}

At the $m$ -th step

c_{m}^{m} := a_{m, m - 1} c_{m - 1}^{m - 1} + c_{m}^{m - 1} .

There were performed $m - 1 + m - 2 + \dots + 1 = \frac{m (m - 1)}{2} M / D$ operations.

Now the second stage of the Gauss method is applied to

(\begin{matrix} a_{11}^{1} & \dots & a_{1 m}^{1} \\ ⋮ & ⋮ \\ 0 & \dots & a_{m m}^{m} \end{matrix}) (\begin{matrix} y_{1} \\ ⋮ \\ y_{m} \end{matrix}) = (\begin{matrix} c_{1}^{1} \\ ⋮ \\ c_{m}^{m} \end{matrix}) .

In addition to the case of a single linear system, in this case were performed $\frac{m (m - 1)}{2} M / D$ operations, getting

\frac{m^{3}}{3} + \frac{3}{2} m^{2} - \frac{5}{6} m M / D operations,

and taking into account $(3.8)$ we add $(m - 1)$ more $M / D$ operations, obtaining

\frac{m^{3}}{3} + \frac{3}{2} m^{2} + \frac{m}{6} - 1 M / D operations.

Remark. At the first stage, if for some $k$ we have $a_{k k}^{k} \approx 0$ , then an element $a_{i_{0}, k}^{k} \neq 0, i_{0} \in {k + 1, \dots, m}$ must be find, and the lines $i_{0}$ and $k$ in $A$ and $b$ be swapped.

In order to avoid the error accumulations, a partial or total pivote strategy is recommended even if $a_{k k}^{k} \neq 0$ for $k = \bar{1, m - 1}$ .

For partial pivoting, the pivote is chosen such that $a_{i_{0}, k}^{k} = \max_{i = \bar{k, m}} | a_{i k}^{k} | .$

The interchange of lines can be avoided by using a permutation vector $p = {(p_{i})}_{i = 1, m}$ , which is first initialized so that $p_{i} = i$ . The elements in $A$ and $b$ are then referred to as $a_{i j} := a_{p (i), j}$ and $b_{i} := b_{p (i)}$ , and swapping the lines $k$ and $i_{0}$ is done by swapping the $k$ -th and $i_{0}$ -th elements in $p$ .

For the Chebyshev method, the use of the vector $p$ cannot be avoided by the very interchanging of the lines, because we must keep track for the permutations made, in order to apply them in the same order to the vector $c$ .

Moreover, we need two extra vectors $t$ and $q$ . In $t$ we store the transpositions applied to the lines in $A x = b,$ which are then successively applied to $q$ . At the first stage of the Gauss method, when the $k$ -th pivote is $a_{i_{0}, k}^{k}$ and $i_{0} \neq k$ , the $k$ -th and $i_{0}$ -th elements in $p$ are swapped, and we assign $t_{k} := i_{0}$ to indicate that at the $k$ -th step we applied to $p$ the transposition $(k, i_{0})$ .

After computing the solution of $A x = b$ , we initialize the vector $c$ by (25), the permutation vector $q$ by $q_{i} := i, i := \bar{1, m}$ , and then we successively apply the transforms operated to $b$ , taking into account the eventual transpositions.

The algorithm for solving the second linear system in the Chebyshev method is as follows.

for $k := 1$ to $m - 1$ do

begin

if $t [k] < > k$

then {at the $k$ -th step the transposition}

begin { $(k, t [k])$ has been applied to $p$ }

$a u x i := q [k];$

$q [k] := q [t [k]];$

$q [t [k]] := a u x i;$

end,

for $i := k + 1$ to $m$ do $c [q [i]] := c [q [i]] + A [q [i], k] * c [q [k]]$

end;

for $i := m$ downto $1$ do {the solution $y$ is now computed}

begin

$s u m := 0;$

for $j := i + 1$ to $m$ do $s u m := s u m + A [p [i], j] * y [j];$ {now $p = q$ }

$y [i] := (c [p [i]] - s u m) / A [p [i], i];$

end.

We adopt as the efficiency measure of an iterative method $M$ the number

E (M) = \frac{\ln q}{s},

where $q$ is the convergence order and $s$ is the number of $M / D$ operations needed at each step.

We obtain

E (N) = \frac{3 \ln 2}{m^{3} + 3 m^{2} - m}

for the Newton method and

E (C) = \frac{6 \ln 3}{2 m^{3} + 9 m^{2} + m - 6}

for the Chebyshev method.

It can be easily seen that we have $E (C) > E (N)$ for $n \geq 2$ , i.e. the Chebyshev method is more efficient than the Newton method.

5. Numerical example

Consider the real matrix

A = (\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & 1 & - 1 & - 1 \\ 1 & - 1 & 1 & - 1 \\ 1 & - 1 & - 1 & 1 \end{matrix})

which has the following eigenvalues and eigenvectors

\begin{matrix} λ_{1, 2, 3} = 2, x_{1} = (1, 1, 0, 0), x_{2} = (1, 0, 1, 0), x_{3} = (1, 0, 0, 1) and \\ λ_{4} = - 2, x_{4} = (1, - 1, - 1, - 1) . \end{matrix}

Taking the initial value $x_{0} = (1, - 1.5, - 2, - 1.5, - 1)$ , and applying the two methods we obtain the following results:

Newton method

$n$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5} = λ$
0	1.0	-1.500 000 000 0	-2.000 000 000 0	-1.500 000 000 0	-1.000 000 000 0
1	1.0	-0.900 000 000 0	-0.800 000 000 00	-0.900 000 000 00	-1.600 000 000 0
2	1.0	-1.012 500 000 0	-1.025 000 000 0	-1.012 500 000 0	-2.050 000 000 0
3	1.0	-1.000 152 439 0	-1.000 304 878 0	-1.000 152 439 0	-2.000 609 756 1
4	1.0	-1.000 000 023 2	-1.000 000 046 5	-1.000 000 023 2	-2.000 000 092 9
5	1.0	-1.000 000 000 0	-1.000 000 000 0	-1.000 000 000 0	-2.000 000 000 0

Chebyshev method

$n$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5} = λ$
0	1.0	-1.500 000 000 0	-2.000 000 000 0	-1.500 000 000 0	-1.000 000 000 0
1	1.0	-0.972 000 000 00	-0.944 000 000 00	-0.972 000 000 00	-1.888 000 000 0
2	1.0	-0.999 950 001 89	-0.999 900 003 77	-0.999 950 001 89	-1.999 800 007 5
3	1.0	-1.000 000 000 0	-1.000 000 000 0	-1.000 000 000 0	-2.000 000 000 0

References

[1] M.P. Anselone, L.B. Rall, The solution of characteristic value-vector problems by Newton method, Numer. Math. 11 (1968), pp. 38–45.
[2] P.G. Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Mason, Paris, 1990.
[3] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.
[4] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.
[5] V.S. Kartîşov, F.L. Iuhno, O nekotorîh Modifikaţiah Metoda Niutona dlea Resenia Nelineinoi Spektralnoi Zadaci, J. Vîcisl. matem. i matem. fiz. (33) (1973) 9, pp. 1403–1409.
[6] I. Păvăloiu, Sur les procédés itératifs à un ordre élevé de convergence, Mathematica (Cluj) 12 (35) (1970) 2, pp. 309–324.
[7] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall Inc., Englewood Cliffs, N. J., 1964.

Received March 7, 1996.

$\begin{matrix} Tiberiu Popoviciu Institute of Numerical
Analysis \\ Romanian Academy \\ P.O. Box 68 Cluj-Napoca 1 \\ RO-3400 \\ Romania \end{matrix}$

1996

On the monotonicity of a sequence of Stancu-Bernstein type operators

March 1, 2023

The application of Kantorovich-Ritz method to the flow of an incompressible potential fluid between two solid walls

October 24, 2024

A note on inexact secant methods

December 25, 2017

On the Chebyshev method for approximating the eigenvalues of linear operators

Abstract

Authors

Keywords

Cite this paper as:

PDF

About this paper

Journal

Publisher Name

Paper on journal website

Print ISSN

Online ISSN

Google Scholar citations

Paper (preprint) in HTML form

On the Chebyshev method for approximating the eigenvalues of linear operators

1. Introduction

2. The convergence of Chebyshev method

Theorem 1.

Proof.

3. The approximation of the eigenvalues and eigenvectors of matrices

Corollary 2.

Remark.

4. A comparison to the Newton method

5. Numerical example

References

Related Posts

On the Chebyshev method for approximating
the eigenvalues of linear operators