Browse Prior Art Database

Optimal Secant Method for Solving Systems of Nonlinear Equations

IP.com Disclosure Number: IPCOM000077052D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 1 page(s) / 12K

IBM

Related People

Brent, RP: AUTHOR

Abstract

An efficient algorithm for finding an approximate solution of a system of nonlinear equations is set forth herein. The algorithm uses function, but not derivative, evaluations. The present algorithm permits a faster solution of this class of problems than has been hitherto available.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 84% of the total text.

Page 1 of 1

Optimal Secant Method for Solving Systems of Nonlinear Equations

An efficient algorithm for finding an approximate solution of a system of nonlinear equations is set forth herein. The algorithm uses function, but not derivative, evaluations. The present algorithm permits a faster solution of this class of problems than has been hitherto available.

Suppose that x(0), x'(0) are distinct approximations to a zero x* of the system f(x) = 0 of n nonlinear equations in n unknowns.

Let k be a positive integer chosen as described below. The algorithm S(k) generates sequences (x(i)) and (x'(i)) with limit x*, provided the Jacobian of f is nonsingular at x*, satisfies a Lipschitz condition, and the approximations x(0) and x'(0) are sufficiently close to x*. If x(i) and x'(i) have been generated, then x(i+1) and x'(i+1) are found in the following way: if f(x(i)) = 0, then x(i+1) = x'(i+1) = x(i), otherwise
A) The unique orthogonal matrix Q(i) = +/-(I - 2u(i)u(i)/T/)

such that

x'(i) = x(i) + h(i)Q(i)e(1) is found. Here h(i)

the absolute value of x(i) - x'(i) (2), u(i) is a unit

vector, and e(j)j = 1,..., n) is the jth coordinate vector.
B) The matrix A(i) whose j/th/ column is A(i)e(j) =

[f(x(i)+j(i)Q(i)e(j)) - f(x(i))]/h(i) for j = 1,..., n)

is found. A function evaluation

may be saved by making use of the previously computed value

of f(x'(i)).
C) Let y(i,0) = x(i), J(i) = A(i)Q(i)/T/, and compute

y(i,j) = y(i,j-1) - J(i)/-1/f(y(i,j-1)

for j = 1,..., k.
D) Let x(i+1) = y(i,k...