On approximating the eigenvalues and eigenvectors of linear continuous operators

9 years ago

(original), eigenvalue/eigenvector problems, html, Numerical Analysis, paper, PDF, Schulz type iterations, semilocal convergence, solving F(x)=0 iteratively, works

Abstract

We consider the computing of an eigenpair (an eigenvector $v=(v^{(i)})_{i=1,n}$ and an eigenvalue $\lambda$) of a matrix $A\in\mathbb{R}^{n\times n}$, by considering a supplementary condition (we call it norming function for the eigenvector), represented by a polynomial of degree 2. A usual choice is
\begin{equation}
G(v):={\textstyle\frac12} \sum_{i=1}^n( v^{(i)})^2-1=0.
\end{equation}
We propose here a new choice:
\begin{equation}
G(v):={\textstyle\frac1{2n}} \sum_{i=1}^n( v^{(i)})^2-1=0,
\end{equation}
which has the advantage that leads to a smaller nonlinearity.

Indeed, for the $n+1$-dimensional nonlinear system (a polynomial equation of degree 2) we obtain:
\[
F\left( x\right) :={{Av-\lambda v} \choose {G(v)-1}}
=0,
\]
and our proposed choice leads to a second derivative of $F$ that has norm 2 (compared to $n$, for the usual choice).

We consider this problem in a general setting, of a linear continuous operator $A:V\rightarrow V$, $V$ Banach space, which leads to a polynomial equation of degree two.

We study the semilocal convergence of an iterative method of Schultz type for this problem; this method has the advantage that does not require the solving of a linear system at each iteration step:
\begin{align*}
x_{k+1} =&x_k-\Gamma_kF\left( x_k\right) \\
\Gamma_{k+1} =&\Gamma_k\left( 2I-F^{\prime }\left( x_{k+1}\right) \Gamma_k\right) , \qquad k=0,1,\ldots,
\end{align*}
where $x_0\in X$, $\Gamma_0\in \mathcal{L}\left( X\right)$, and $I$ is the identity operator of $\mathcal{L}\left( X\right)$.

We obtain semilocal convergence conditions which show that the method has r-convergence order 2.

Authors

Emil Cătinaş

Emil Cătinaş

Ion Păvăloiu

Ion Păvăloiu

Keywords

linear continuous operator; Banach space; Newton type method; eigenvector; eigenvalue; eigenpair; Schultz method; r-convergence order.

Cite this paper as:

E. Cătinaş, I. Păvăloiu, On approximating the eigenvalues and eigenvectors of linear continuous operators, Rev. Anal. Numér. Théor. Approx., 26 (1997) nos. 1-2, pp. 19-27.

PDF

Scanned paper: on the journal website.

Latex-pdf version of the paper. (soon)

About this paper

Print ISSN

1222-9024

Online ISSN

MR

ZBL

2457-8126

Google Scholar citations

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

[2] E. Catinas, I. Pavaloiu, On the Chebyshev method for approximating the eigenvalues of linear operators, Rev. Anal. Numer. Theor. Approx. 25 (1996) nos. 1–2, pp. 43–56.
article post, article on the journal website

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

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

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

[6] A. Diaconu, On the convergence of an iterative proceeding of Chebyshev type, Rev. Anal. Numer. Theor. Approx. 24 (1995) nos. 1–2, pp. 91–102.
article on the journal website

[7] A. Diaconu, I. Pavaloiu, Sur quelque methodes iteratives pour la resolution des equations operationelles, Rev. Anal. Numer. Theor. Approx. 1 (1972) no. 1, pp. 45–61.
article on the journal website

[8] 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.

[9] I. Lazar, On a Newton type method, Rev. Anal. Numer. Theor. Approx. 23 (1994) no. 2, pp. 167–174.
article on journal website

[10] I. Pavaloiu, Observations concerning some approximation methods for the solutions of operator equations, Rev. Anal. Numer. Theor. Approx. 23 (1994) no. 2, pp. 185–196.
article on the journal website

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

[12] R.A. Tapia, L.D. Whitley, The projected Newton method has order 1+√2 for the symmetric eigenvalue problem, SIAM J. Numer. Anal. 25 (1988) no. 6, pp. 1376–1382.
CrossRef

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

[14] S. Ul’m, On the iterative method with simultaneous approximation of the inverse of the operator, Izv. Acad. Nauk. Estonskoi S.S.R. 16 (1967) no. 4, pp. 403–411.

[15] T. Yamamoto, Error bounds for computed eigenvalues and eigenvectors, Numer. Math. 34 (1980), pp. 189–199.
CrossRef

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 approximating the eigenvalues and eigenvectors of linear continuous operators

On approximating the eigenvalues and eigenvectors of linear continuous operators

Emil Cătinaş and Ion Păvăloiu

1991 AMS Subject Classification: 65J20, 65H17.

1. Introduction

One of the difficulties that appear when solving numerically the operatorial equations by iterative methods having high convergence orders is that at each iteration step there must be solved a linear operatorial equation, or, in some cases, even more than one [3].

In a series of papers ([7], [8], [10], [15]) there has been proposed the elimination of this inconvenience by the simultaneous generation of two sequences: a sequence approximating the solution, and a sequence of linear operators approximating the inverse of the linear operator appearing at each step in the linear equation.

In the present paper we shall study this approach when the solutions of the equation yield eigenvalues and eigenvectors of a linear operator. It is well known that all the derivatives of order higher than three of the attached operator are the null multilinear operators. The convergence results may also be applied to polynomial operator equations of degree two.

The r convergence order of the sequence approximating the solution is proved to be 2.

The operatorial equation which lead us to the approximation of the eigenvalues and eigenvectors of a linear operator can be constructed in the following way (see [6]):

Let $V$ be a Banach space over the field $𝕂$ (where $𝕂 = ℂ$ or $𝕂 = ℝ$ ); denote by $ℒ (V)$ the set of linear continuous operators acting from $V$ into $V$ and let $A \in ℒ (V)$ . The scalar $λ \in 𝕂$ is an eigenvalue of $A$ if the equation

(1)

A v - λ v = θ

has at least a solution $v \neq θ$ , called an eigenvector of $A$ corresponding to $λ$ , where $θ$ is the null element of $V$ .

For the determination of an eigenpair $(v, λ)$ we also consider another equation

(2)

G (v) - 1 = 0,

where $G : V \to 𝕂$ is a polynomial functional of degree at most two (a norming function) for which $G (0) \neq 1$ .

Remark.

The functional $G$ may also be taken as a linear continuous functional, but in this case, if $\dim V = n$ , then $\dim \ker G = n - 1$ , so there exist eigenvectors which do not fulfill equation (2). ∎

Denote the Banach space $X = V \times 𝕂$ and for $x = (\binom{v}{λ})$ , $v \in V$ , $λ \in 𝕂$ define

‖ x ‖ = \max {‖ v ‖, | λ |} .

Considering the operator $F : X \to X$ given by

F (x) = (\binom{A v - λ v}{G (v) - 1}) = (\binom{(A - λ I) v}{G (v) - 1}),

and denoting by $\bar{θ} = (\binom{θ}{0})$ the null element of $X$ , then the operatorial equation for which a solution yields an eigenpair of $A$ is

(3)

F (x) = \bar{θ} .

It is known that the Fréchet derivatives of $F$ are (see [6]):

F^{'} (x_{0}) h = (\begin{matrix} A - λ_{0} I & - v_{0} \\ G^{'} (v_{0}) & 0 \end{matrix}) (\begin{matrix} u \\ α \end{matrix}) = (\begin{matrix} A u - λ_{0} u - α v_{0} \\ G^{'} (v_{0}) u \end{matrix}),

and

F^{''} (x_{0}) h k = (\begin{matrix} - α w - β u \\ G^{''} u w \end{matrix}),

where $x_{0} = (\binom{v_{0}}{λ_{0}}),$ $h = (\binom{u}{α})$ , $k = (\binom{w}{β}) \in X .$

It is obvious that $F^{(i)} (x_{0}) h_{1} \dots h_{i} = \bar{θ},$ for all $i \geq 3$ and $x_{0}, h_{1}, \dots, h_{i} \in X$ , and also that $‖ F^{''} ‖ = \max {2, ‖ G^{''} ‖} .$

For such an operator the following identity holds:

(4)

F (y) = F (x) + F^{'} (x) (y - x) + F^{''} (x) {(y - x)}^{2}, \forall x, y \in X,

where the bilinear operator $F^{''}$ does not depend on $x$ .

We shall consider two sequences ${(x_{k})}_{k \geq 0},$ ${(Γ_{k})}_{k \geq 0}$ having elements from $X,$ resp. $ℒ (X),$ using the following iterative method:

(5)		$x_{k + 1}$	$=$	$x_{k} - Γ_{k} F (x_{k})$
	$Γ_{k + 1}$	$=$	$Γ_{k} (2 I - F^{'} (x_{k + 1}) Γ_{k}), k = 0, 1, \dots,$

where $x_{0} \in X,$ $Γ_{0} \in ℒ (X)$ , and $I$ is the identity operator of $ℒ (X)$ .

We call (5) the combined Newton method. In the following sections we shall study its convergence when $F$ is a polynomial operator of degree 2 and we shall apply it for the approximation of the eigenvalues and eigenvectors of matrices.

2. The convergence of the combined Newton method

For the study of the convergence of the method (5) we shall use the following lemma:

Lemma 1.

If the sequences ${(δ_{k})}_{k \geq 0}$ and ${(ρ_{k})}_{k \geq 0}$ of real positive numbers satisfy the following conditions

	$δ_{k + 1}$	$\leq {(δ_{k} + 2 ρ_{k})}^{2}$
	$ρ_{k + 1}$	$\leq ρ_{k} δ_{k} + ρ_{k}^{2}, k = 0, 1, \dots$

where $\max {δ_{0}, ρ_{0}} \leq \frac{1}{9} d,$ for some $d < 1,$ then the following relations hold:

	$δ_{k}$	$\leq \frac{1}{9} d^{2^{k}},$
	$ρ_{k}$	$\leq \frac{1}{9} d^{2^{k}}, k = 0, 1, \dots$

The proof of this lemma is immediately obtained by induction.

Let $x_{0} \in X$ , $Γ_{0} \in ℒ (X)$ and $S = {x \in X | ‖ x - x_{0} ‖ \leq r},$ $r > 0 .$ Suppose that the following estimation holds:

‖ F^{''} (x) ‖ \leq K, \forall x \in S .

The following theorem holds.

Theorem 2.

If $x_{0} \in S,$ $Γ_{0} \in ℒ (X),$ $r$ and $F$ satisfy the following conditions

a)

there exists $F^{'} {(x_{0})}^{- 1}$ and $b_{0} = ‖ F^{'} {(x_{0})}^{- 1} ‖;$
b)

$q = K b_{0} r < 1;$
c)

$\max {δ_{0}, ρ_{0}} \leq \frac{1}{9} d,$ for some $d < 1,$ where

$δ_{0}$ $= ‖ I - F^{'} (x_{0}) Γ_{0} ‖,$

$ρ_{0}$ $= \frac{50}{81} b^{2} K ‖ F (x_{0}) ‖, a n d$

$b$ $= \frac{b_{0}}{1 - q};$
d)

$\frac{d}{5 K (1 - q)} \leq r,$

then the following properties hold:

1)

the sequences ${(x_{k})}_{k \geq 0},$ ${(Γ_{k})}_{k \geq 0}$ generated by (5) converge, and $x_{k} \in S$ for all $k \geq 0;$
2)

denoting $x^{*} = {lim}_{k \to \infty} x_{k}$ and $Γ^{*} = {lim}_{k \to \infty} Γ_{k}$ , then $F (x^{*}) = \bar{θ}$ and $Γ^{*} = F^{'} {(x^{*})}^{- 1};$
3)

the following relations are true:

$‖ x^{*} - x_{k} ‖$ $\leq \frac{d^{2^{k}}}{5 b K (1 - d^{2^{k}})}, k = 0, 1, \dots;$

$‖ Γ^{*} - Γ_{k} ‖$ $\leq \frac{d^{2^{k}}}{3 (1 - d^{2^{k}})}, k = 0, 1, \dots$

Proof.

At first we shall show that for any $x \in S$ there exists $F^{'} {(x)}^{- 1}$ and $‖ F^{'} {(x)}^{- 1} ‖ \leq b .$

Indeed, under the above assumptions, it easily follows that

‖ I - Γ_{0} F^{'} (x) ‖ \leq K b_{0} r = q < 1 .

Applying the Banach lemma we get

‖ F^{'} {(x)}^{- 1} ‖ \leq \frac{b_{0}}{1 - q} = b .

Taking into account a) and b) it follows that

(6)

‖ Γ_{0} ‖ \leq ‖ F^{'} {(x_{0})}^{- 1} ‖ (‖ F^{'} (x_{0}) Γ_{0} - I ‖ + 1) \leq b_{0} (1 + δ_{0}) \leq \frac{10}{9} b_{0} \leq \frac{10}{9} b,

which, together with the first relation from (5), for $k = 0,$ imply

‖ x_{1} - x_{0} ‖ \leq ‖ Γ_{0} ‖ ‖ F (x_{0}) ‖ \leq \frac{10 \cdot 81 b d}{9 \cdot 9 \cdot 50 b^{2} K} < \frac{d}{5 b K (1 - d)} \leq r,

i.e. $x_{1} \in S .$

Denote $ρ_{1} = \frac{50}{81} b^{2} K ‖ F (x_{1}) ‖$ and $δ_{1} = ‖ I - F^{'} (x_{1}) Γ_{1} ‖ .$ An elementary reasoning shows that

	$ρ_{1}$	$\leq ρ_{0}^{2} + δ_{0} ρ_{0}$
	$δ_{1}$	$\leq {(δ_{0} + 2 ρ_{0})}^{2},$

whence, by the above Lemma and by relation c) we infer that

	$ρ_{1}$	$\leq \frac{1}{9} d^{2}$
	$δ_{1}$	$\leq \frac{1}{9} d^{2} .$

Suppose now that the following relations hold:

$α)$ $x_{1}, \dots, x_{k} \in S;$

$β)$ $δ_{i} = ‖ I - F^{'} (x_{i}) Γ_{i} ‖ \leq \frac{1}{9} d^{2^{i}}$ , $ρ_{i} = \frac{50}{81} b^{2} K ‖ F (x_{i}) ‖ \leq \frac{1}{9} d^{2^{i}}$ , $i = \bar{0, k};$

$γ)$ $‖ x_{i} - x_{i - 1} ‖ \leq \frac{d^{2^{i}}}{5 b K},$ $i = \bar{1, k} .$

We shall show that they also hold for $k + 1$ .

The inequality

‖ Γ_{k} ‖ \leq \frac{10}{9} b

is proved similarly to (2.2). Using also the second relation from (5) we get

‖ x_{k + 1} - x_{k} ‖ \leq ‖ Γ_{k} ‖ ‖ F (x_{k}) ‖ \leq \frac{d^{2^{k}}}{5 b K},

i.e. the relation $γ)$ for $i = k + 1 .$

Further,

‖ x_{k + 1} - x_{0} ‖ \leq \sum_{i = 0}^{k} ‖ x_{i + 1} - x_{i} ‖ \leq \frac{1}{56 K} \sum_{i = 0}^{k} d^{2^{k}} < \frac{d}{5 K b (1 - d)} \leq r,

whence it follows that $x_{k + 1} \in S .$

Denoting $ρ_{k + 1} = \frac{50}{81} b^{2} K ‖ F (x_{k + 1}) ‖$ and $δ_{k + 1} = ‖ I - F^{'} (x_{k + 1}) Γ_{k + 1} ‖,$ then

	$ρ_{k + 1}$	$\leq ρ_{k}^{2} + ρ_{k} δ_{k}$
	$δ_{k + 1}$	$\leq {(δ_{k} + ρ_{k})}^{2},$

whence, by our Lemma we get

	$ρ_{k + 1}$	$\leq \frac{1}{9} d^{2^{k + 1}}$
	$δ_{k + 1}$	$\leq \frac{1}{9} d^{2^{k + 1}},$

i.e. the relation $β)$ for $i = k + 1 .$

It is obvious that $x_{i} \in S$ for all $i = 1, 2, \dots$ and the relations $β)$ and $γ)$ hold for all $k \in ℕ .$

From the inequalities

‖ x_{k + m} - x_{k} ‖ \leq \sum_{i = k}^{k + m - 1} ‖ x_{i + 1} - x_{i} ‖ \leq \frac{d^{2^{k}}}{5 K b (1 - d^{2^{k}})}, m = 1, 2, \dots

it follows that the sequence ${(x_{k})}_{k \geq 0}$ converges. Denoting $x^{*} = {lim}_{k \to \infty} x_{k}$ then from the last relation for $m \to \infty$ we get

‖ x^{*} - x_{k} ‖ \leq \frac{d^{2^{k}}}{5 K b (1 - d^{2^{k}})}, k = 0, 1, \dots

From the second relation of (5) it follows that

	$‖ Γ_{k + 1} - Γ_{k} ‖$	$= ‖ I - F^{'} (x_{k + 1}) Γ_{k} ‖$
		$\leq ‖ I - F^{'} (x_{k}) Γ_{k} ‖ + ‖ F^{'} (x_{k}) - F^{'} (x_{k + 1}) ‖ ‖ Γ_{k} ‖$
		$\leq δ_{k} + {‖ Γ_{k} ‖}^{2} K ‖ F (x_{k}) ‖$
		$\leq δ_{k} + 2 ρ_{k} \leq \frac{1}{3} d^{2^{k}} .$

The previous inequality implies that the sequence ${(Γ_{k})}_{k \geq 0}$ converges and the relations $2)$ and the second inequality in $3)$ hold. ∎

3. The approximation of eigenvalues and eigenvectors of matrices

In the following we shall apply the studied method for the approximation of the eigenvalues and eigenvectors of complex matrices.

Let $A = {(a_{i j})}_{i, j = 1, n} \in ℳ_{n} (𝕂)$ be a square matrix with the elements $a_{i, j} \in 𝕂 .$ Consider $V = 𝕂^{n}$ and $X = 𝕂^{n + 1} .$ In this case the equation (3) is written

F_{i} (x) = F_{i} (x^{(1)}, \dots, x^{(n + 1)}) = 0, i = \bar{1, n + 1},

where

F_{i} (x) = a_{i 1} x^{(1)} + \dots + a_{i, i - 1} x^{(i - 1)} + (a_{i i} - x^{(n + 1)}) x^{(i)} + a_{i, i + 1} x^{(i + 1)} + \dots + a_{i n} x^{(n)},

$i = \bar{1, n} .$

For the norming function we can take $G = F_{n + 1}$ , where

(7)

F_{n + 1} (x) = \frac{1}{2} \sum_{i = 1}^{n} {(x^{(i)})}^{2} - 1 .

The first and second order derivatives of $F$ are given by

F^{'} (x) h = (\begin{matrix} a_{11} - x^{(n + 1)} & a_{12} & \dots & a_{1 n} & - x^{(1)} \\ a_{21} & a_{22} - x^{(n + 1)} & \dots & a_{2 n} & - x^{(2)} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} - x^{(n + 1)} & - x^{(n)} \\ x^{(1)} & x^{(2)} & \dots & x^{(n)} & 0 \end{matrix}) (\begin{matrix} h^{(1)} \\ h^{(2)} \\ ⋮ \\ h^{(n)} \\ h^{(n + 1)} \end{matrix}),

and

F^{''} (x) h k = (\begin{matrix} - k^{(n + 1)} & 0 & \dots & 0 & - k^{(1)} \\ 0 & - k^{(n + 1)} & \dots & 0 & - k^{(2)} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & \dots & - k^{(n + 1)} & - k^{(n)} \\ k^{(1)} & k^{(2)} & \dots & k^{(n)} & 0 \end{matrix}) (\begin{matrix} h^{(1)} \\ h^{(2)} \\ ⋮ \\ h^{(n)} \\ h^{(n + 1)} \end{matrix}) .

where $x = (x^{(1)}, \dots, x^{(n + 1)}), h = (h^{(1)}, \dots, h^{(n + 1)}), k = (k^{(1)}, \dots, k^{(n + 1)}) \in 𝕂^{n + 1} .$

Suppose that $𝕂^{n + 1}$ is equipped with the max-norm. Then, from the above formula it follows that $‖ F^{''} (x) ‖ = n$ , for all $x \in 𝕂^{n + 1} .$

Another possible choice for the norming function $G$ is

(8)

F_{n + 1} (x) = \frac{1}{2 n} \sum_{i = 1}^{n} {(x^{(i)})}^{2} - 1 .

in which case we get $‖ F^{''} (x) ‖ = 2$ , for all $x \in 𝕂^{n + 1} .$

The Theorem stated in the previous section can be reformulated according to this setting.

Remark.

In [16] it is proved that for a given eigenpair $(v, λ)$ the operator $F^{'} (v, λ)$ is nonsingular iff $λ$ is simple. Hence our result applies only for such eigenvalues.

4. Numerical example

Consider the real matrix

A = (\begin{matrix} 1 & 1 & 0.5 \\ 1 & 1 & 0.25 \\ 0.5 & 0.25 & 2 \end{matrix})

which has the following eigenvalues and eigenvectors

\begin{matrix} λ_{1} = - 0.01664728361 & v_{1} = (- 0.7212071298, 0.6863492877, 0.09372796349) \\ λ_{2} = 1.480121423 & v_{2} = (- 0.4442810581, - 0.5621094204, 0.6976011330) \\ λ_{3} = 2.536525860 & v_{3} = (0.5314834119, 0.4614733520, 0.7103293096) . \end{matrix}

Taking the initial values $x_{0} = (- 0.7, 0.6, 0.09, - 0.01)$ , and applying the studied method for $G$ given by (7), we obtain the following results:

$k$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4} = λ$
$0$	$- 0.7$	$0.6$	$0.09$	$- 0.01$
$1$	$- 0.724 175 907 5$	$0.689 434 334 6$	$0.094 069 599 84$	$- 0.016 114 176 48$
$2$	$- 0.721 237 913 5$	$0.686 375 347 9$	$0.093 732 538 57$	$- 0.016 634 900 68$
$3$	$- 0.721 207 134 0$	$0.686 349 290 8$	$0.093 727 964 20$	$- 0.016 647 279 74$
$4$	$- 0.721 207 129 8$	$0.686 349 287 7$	$0.093 727 963 50$	$- 0.016 647 283 61$

For the initial values $x_{0} = (- 1.7, 1.6, 0.2, - 0.01)$ , and taking $G$ given by (8) we obtain:

$k$	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4} = λ$
$0$	$- 1.7$	$1.6$	$0.2$	$- 0.01$
$1$	$- 1.768 398 012$	$1.682 966 665$	$0.229 883 578 0$	$- 0.016 956 741 74$
$2$	$- 1.766 594 350$	$1.681 210 330$	$0.229 586 553 3$	$- 0.016 649 009 83$
$3$	$- 1.766 589 467$	$1.681 205 540$	$0.229 585 685 2$	$- 0.016 647 283 65$

References

[1]
[2] M.P. Anselone, L.B. Rall, The solution of characteristic value-vector problems by Newton method, Numer. Math. 11 (1968), 38–45.
[3] E. Cătinas, 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.
[4] P.G. Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Mason, Paris, 1990.
[5] F. Chatelin, Valeurs propres de matrices, Mason, Paris, 1988.
[6] L. Collatz, Functionalanalysis und Numerische Mathematik, Springer-Verlag, Berlin, 1964.
[7] A. Diaconu, On the convergence of an iterative proceeding of Chebyshev type, Rev. Anal. Numér. Théor. Approx. 24 (1995) nos. 1–2, pp. 91–102.
[8] A. Diaconu, I. Păvăloiu, Sur quelque méthodes itératives pour la résolution des équations opérationelles, Rev. Anal. Numér. Théor. Approx. 1 (1972) no. 1, pp. 45–61.
[9] 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.
[10] I. Lazăr, On a Newton type method, Rev. Anal. Numér. Théor. Approx. 23 (1994) no. 2, pp. 167–174.
[11] I. Păvăloiu, Observations concerning some approximation methods for the solutions of operator equations, Rev. Anal. Numér. Théor. Approx. 23 (1994) no. 2, pp. 185–196.
[12] I. Păvăloiu, Sur les procédés itératifs à un ordre élevé de convergence, Mathematica (Cluj) 12 (35) (1970) no. 2, pp. 309–324.
[13] R.A. Tapia, L.D. Whitley, The projected Newton method has order 1+ $\sqrt{2}$ for the symmetric eigenvalue problem, SIAM J. Numer. Anal. 25 (1988) no. 6, pp. 1376–1382.
[14] F.J. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall Inc., Englewood Cliffs, N. J., 1964.
[15] S. Ul’m, On the iterative method with simultaneous approximation of the inverse of the operator, Izv. Acad. Nauk. Estonskoi S.S.R. 16 (1967) no. 4, pp. 403–411.
[16] T. Yamamoto, Error bounds for computed eigenvalues and eigenvectors, Numer. Math. 34 (1980), pp. 189–199.

Received August 15, 1996. ”Tiberiu Popoviciu” Institute of Numerical Analysis

$\begin{matrix} Romanian Academy \\ P.O. Box 68 \\ 3400 Cluj-Napoca 1 \\ Romania \end{matrix}$

1997

A bivariate extension of the Bernstein polynomials

February 10, 2023

On an approximating linear positive operator of Cheney-Sharma

September 5, 2022

On the convergence order of the multistep methods

January 21, 2018

	$δ_{0}$	$= ‖ I - F^{'} (x_{0}) Γ_{0} ‖,$
	$ρ_{0}$	$= \frac{50}{81} b^{2} K ‖ F (x_{0}) ‖, a n d$
	$b$	$= \frac{b_{0}}{1 - q};$

	$‖ x^{*} - x_{k} ‖$	$\leq \frac{d^{2^{k}}}{5 b K (1 - d^{2^{k}})}, k = 0, 1, \dots;$
	$‖ Γ^{*} - Γ_{k} ‖$	$\leq \frac{d^{2^{k}}}{3 (1 - d^{2^{k}})}, k = 0, 1, \dots$

On approximating the eigenvalues and eigenvectors of linear continuous operators

Abstract

Authors

Keywords

Cite this paper as:

PDF

About this paper

Journal

Publisher Name

Paper on journal website

Print ISSN

Online ISSN

MR

ZBL

Google Scholar citations

Paper (preprint) in HTML form

On approximating the eigenvalues and eigenvectors of linear continuous operators

1. Introduction

Remark.

2. The convergence of the combined Newton method

Lemma 1.

Theorem 2.

Proof.

3. The approximation of eigenvalues and eigenvectors of matrices

Remark.

4. Numerical example

References

Related Posts