Browse Prior Art Database

"Circle Method" - a Procedure for Accelerating Iterative Convergence

IP.com Disclosure Number: IPCOM000037382D
Original Publication Date: 1989-Dec-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 58K

Publishing Venue

IBM

Related People

Henderson, ME: AUTHOR [+2]

Abstract

A technique is described whereby an algorithmic iterative method is accelerated through the use of a "Circle Method", such that between each step of the iterative method, the iterate is rotated by an appropriate angle on an appropriate circle. The intermediate rotation accelerates the iteration process.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 67% of the total text.

Page 1 of 3

"Circle Method" - a Procedure for Accelerating Iterative Convergence

A technique is described whereby an algorithmic iterative method is accelerated through the use of a "Circle Method", such that between each step of the iterative method, the iterate is rotated by an appropriate angle on an appropriate circle. The intermediate rotation accelerates the iteration process.

The "Circle Method" is designed to be used to accelerate any iteration for the iterative method, such as: (1) xk = ( - A)xk-1 + b for solving the linear system Ax = b. To accelerate the convergence of the iteration, plane rotations about center xc are employed: Q(r)(x - xc) = ( +(cosr - 1)(v1v1 + v2v2) + sinr (v1v2 - v2v1)) (x - xc) = (Qo + cosr Qc + sinr Qs)(x - xc) in the plane determined by the orthonormal vectors v1 and v2 .

Ideally, xc should lie halfway between xk-1 and the exact solution, with the plane of rotation containing these two points. (With this ideal choice, there is an angle of rotation which causes the iteration to converge in one step.) This ideal choice is approximately accomplished by the following choice for xc, v1 and v2


.

xc = ( - A)xk-1 + b, (2) v1 = (xc -

xk-1)/ xc - xk-1 ,

* *

v2 = (xc - (v1xc)v1)/ xc - (v1xc)v1 .

is replaced by the compound iteration:

a) x-k-1 = Q(r)(xk-1 - xc) + xc

_

b) xk = ( - A)xk-1 + b.

The angle is specified so that the norm of the residual, II r(xk) II, is minimized. Setting c = cos R and s = sin R , the minimum is specified by

-(b + g)w + te

c =

(a + g)(b + g) - t2' (4)

-(a + g) e + tw

s =

(a + g)(b + g) - t2' where g is chosen so

that c2 + s2 = 1. The parameters here are given by:

* * *

a = (xk-1 - xc) QcB BQc(xk-1 - xc)

* * *

b = (xk-1 - xc) QsB BQs(xk-1 - xc)

* * *

t = (xk-1 - xc) QcB BQs(xk-1 - xc)

* * * _*

w = (xk-1 - xc) QcB BQo(xk-1 - xc) - b

BQc(xk-1...