# Introduction

Returning to my old field (see the references below), I am investigating a new broad family of algorithms for optimization and solution of equations.

To demonstrate one of these algorithms we solve the linear system of equations *A x = b* where *A* is a
square tri-diagonal matrix of size *n* with "2" on its diagonal and "-1" above and below. The right hand side
is chosen so that the solution *x ^{*}* is (1, 2, 3, ...,

*n*) and the starting point is (1, 1, 1, ..., 1). The input is the problem size

*n*and the output is a table of error values and the solution

*x*. The algorithm stops when the norm of the error is smaller than 10

^{*}^{-8}.

The algorithms in this family are monotone (in the case of solving linear systems or quadratic minimization) and this one outperforms the 2-point gradient algorithm [2] by an order of magnitude.

Jonathan Barzilai

# References

Jonathan Barzilai and Michael A.H. Dempster, "Measuring Rates of Convergence of Numerical Algorithms," *Journal of Optimization Theory and Applications*, Vol. 78, No. 1, pp.109—125, 1993.

Jonathan Barzilai and Jonathan M. Borwein, "Two-Point Step Size Gradient Methods," *IMA Journal of Numerical Analysis*, Vol. 8, pp. 141—148, 1988.

Jonathan Barzilai and Aharon Ben-Tal, "Nonpolynomial and Inverse Interpolation for Line Search: Synthesis and Convergence Rates," *SIAM J. Numer. Anal.*, Vol. 19, pp. 1263—1277, 1982.

Jonathan Barzilai and Aharon Ben-Tal, "A Non-Orthogonal Fourier Expansion for Conic Decomposition," *Mathematics of Operations Research*, Vol. 6, pp. 363—373, 1981.

Jonathan Barzilai, "On Differentiating Hyperosculatory Error Terms," Report No. 408, Center for Cybernetic Studies, The University of Texas at Austin, 1981.

# Demonstration

Enter problem size n between 2 and 100: |
||