Solving Equations by Steepest Descent

4 Pages · 2008 · 62 KB ·

At the minimum, which we call y0, the gradient has to vanish which means that Ay0 = b and hence y0 is the solution. Example. Lets take A be the 2 × 2

Pro ject : Steepest Descent for solving linear equations This pro ject is devoted to an idea for iteratively solving linear systems, ie, solving equations of the form Ax=b (1) where Ais an n nmatrix and bis a vector in Rn Henceforth we shall assume that Ais a positive de nite matrix Recall that this means that for all nonzero vectors x2 Rn x Ax > 0: This means, in particular, that the kernel of the matrix Aconsists of the zero vector only and hence the matrix is invertible The equation (1) has always a unique solution A rst thought is to formulate the problem as a minimization problem To this end we consider the function F(x ) = 1 2 x Ax bx : At the minimum, which we call y 0, the gradient has to vanish which means that Ay 0= b and hence y 0 is the solution Example Lets take Abe the 2 2 diagonal matrix 1 0 0 2  and b=  3 4  : In this case the function Fis a function of two variables and is given by F (u; v ) = 1 2 ( u 2 + 2 v2 ) 3u 4v which, by completing the squares, can be brought into the form F(x; y ) = 1 2 ( u 3)2 + ( v 2)2 17 2 : We see right away that the level curves of Fare ellipses The gradient of Fis given by r F(u; v ) = ( u 3;2 v 4) and it vanishes precisely at the point (3 ;2) which is the solution of the system Ax=b The completion of the square can be carried out quite generally Expanding the expression 1 2 ( x A 1 b) A (x A 1 b) = 1 2 x Ax bx + 1 2 b A 1 b 1 yields F(x ) = 1 2 ( x A 1 b) A (x A 1 b) 1 2 b A 1 b : From this we see right away that the minimal value of Fis attained at the unique solution y 0 and the the value of the function Fat this point is 1 2 b A 1 b We also see that the level surfaces of the function Fare ellipsoids who have y 0 as the common center So far so good, but the real question we want to address is how to nd y 0 eciently and we would like to acquaint you with an idea on how this can be achieved Note that the issue at hand is not to work this out for 2 2 or 3 3 matrices, but with large matrices, where computers are needed The method, which is in a way the simplest one, is the steepest descent method Start at a point x 0 and think of skiing as fast as possible towards the lowest point Let us assume that we are not good skiers and cannot turn in a continuous fashion, ie, we ski rst in a straight line, then stop and turn and then again ski in a straight line You would start in the direction of steepest descent which is opposite to the gradient direction, ie, you would ski rst in the direction of rF(x 0) How far would you ski? First you will go down and at some point you will go up again Clearly you want to stop once you have reached the lowest point in the valley along that direction Call this point x 1 Then turn and ski in the direction rF(x 1) until you hit the bottom of you straight tra jectory in this new direction and then stop Repeating this gets you obviously closer and closer to absolute bottom of the valley Now we formalize this picture You starting tra jectory is x0 + td 0 where d 0 = r F(x 0) Now, by a calculation using general properties of the dot product, F (x 0 + td 0) = F(x 0) + td 0 (Ax 0 b) + t 2 2 d 0  Ad 0: Note that d 0 = (Ax 0 b) and hence F (x 0 + td 0) = F(x 0) tjd 0j2 + t 2 2 d 0  Ad 0: According to our plan, we have to nd the minimum

Interpreting sloppy stick figures by graph rectification and

14 Pages · 2001 · 822 KB · English

1 Interpreting sloppy stick figures by graph rectification and constraint-based matching. James V. Mahoney and Markus P. J. Fromherz Xerox Palo Alto Research Center

Date Park R Address Phone Movie Rating CC Underwritten by

3 Pages · 2012 · 34 KB · English

Produced by: Chicago Park District Presented by: Charter One Date Park R Address Phone Movie Rating CC Underwritten by Monday, June 11, 2012 Belmont Harbor N SE

OSMO TOP OIL Product Quick Sheet Revised: 3/10/10 By: SCR

2 Pages · 2010 · 39 KB · English

Product Quick Sheet – OSMO Top Oil Page 1 of 2 OSMO TOP OIL Product Quick Sheet . Revised: 3/10/10 By: SCR . GENERAL PRODUCT INFO . Product Description

A Method for Thermal Performance Characterization of Ultra-Thin Vapor Chambers Cooled by ...

8 Pages · 2016 · 1.41 MB · English

Mark A. MacDonald. Intel Corporation,. 5200 Elam Young Pkwy,. Hillsboro, OR 97124 e-mail: [email protected] A Method for Thermal The evaporator- side and ambient temperatures are measured directly; the condenser-side surface temper- ature distribution, which has critical ergonomics

Introduction to MPI by examples

169 Pages · 2015 · 2.77 MB · English

5 Basic parallel techniques . #include . #include using namespace std; int main(int argc, char **argv){ int id, nproc;. MPI_Status status; double x,y, Pi, error; long long allsum; . The second programming excercise will be the implementation of a parallel matrix-matrix multiplication.

DVD Authoring Tools - Manifest Technology Site by Douglas Dixon

11 Pages · 2005 · 782 KB · English

14 Pages · 2010 · 1.7 MB · English