Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The secant method for solving an equation $F(x)=0$ in one variable is much older than Newton's one. Recall that given two iterates $x_{k-1}$ and $x_k$, it provides an update $x_k$ by taking the intersection of the chord joining the graph points $(x_{k-1},F(x_{k-1}))$ and $(x_k,F(x_k))$, with the horizontal axis $y=0$. The intersection is $(x_k,0)$. Students are taught that this method is convergent in the following sense, that if $F$ is ${\mathcal C}^2$ at $\hat x$, if $F(\hat x)=0$ and $F'(\hat x)\ne0$, and if $x_0,x_1$ are close enough to $\hat x$, then the sequence converges towards $\hat x$. In addition, the error $e_k:=|x_k-\hat x|$ satisfies $e_{k+1}\le{\rm cst}\cdot e_ke_{k-1}$ for some constant. This ensures that $e_k\le\rho^{\omega^k}$ for some $\rho< 1$ and $\omega=\frac{1+\sqrt{5}}{2}$ the golden ratio. This order is optimal, as seen on the example of a quadratic polynomial $F$.

The following is a natural generalization to $n\ge2$ variables. Now, $F:B(\hat x;r) \rightarrow {\mathbb R}^n$ is a vector field. Given $n+1$ iterates $x_{k-n},\ldots,x_{k-1},x_k$, we determine $x_{k+1}$ as the point $x\in{\mathbb R}^n$ such that $(x,0)$ is the intersection of the horizontal space ${\mathbb R}^n\times 0$, with the $n$-dimensional affine space spanned by the graph points $(x_j,F(x_j))$.

Question. Is this method classical ? Does there exist a reference ? Do we know convergence ? Order ?

Remark. Unlike the one-variable case, the algorithm can stop in finite time, when the affine space spanned by graph points does not intersect the horizontal space. Thus we expect convergence only for reasonnable initial data $(x_0,\ldots,x_n)$.

share|improve this question
3  
It seems that the book [J. Ortega and W. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, Philadelphia, PA, 2000] (avaliable at google books) discusses the multivariate method. –  Wadim Zudilin Oct 12 '10 at 11:38
    
I do not have access to this book (actually a reprint of a 1970 edition) here. Google scholar provides some scattered pages, which leave me uncomfortable whether the book really deals with this version of secant method. I'll come back when I know more about this. –  Denis Serre Oct 12 '10 at 12:58
3  
On page 198 of Ortega-Rheinboldt it says "Although the $n+1$-point sequential secant method requires the least amount of computation per step, it will be shown in Chapter 11 that the method is prone to unstable behavior and that no satisfactory convergence results can be given. In contrast, the two-point methods will be shown to retain the essential properties of Newton's method and, in particular, satisfactory local convergence theorems will be obtained for them in section 11.2". Chapters 9-11 are devoted to convergence and local convergence theorems for various iterative processes. –  Gjergji Zaimi Oct 12 '10 at 23:33
    
@Gjergji. This is clear and it answers my question. Thanks to Wadim for having pointed the reference. I have asked our library to purchase the book. –  Denis Serre Oct 13 '10 at 5:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.