Solving Equations by Steepest Descent

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 

Solving Equations by Steepest Descent free download


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 bx : 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 bx + 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 eciently 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

------------- Read More -------------

Download solving-equations-by-steepest-descent.pdf

Solving Equations by Steepest Descent related documents

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

– DVD-ROM, Web DVD Page 12 DVD Authoring Tools 5/2005 Copyright 2001-2005 Douglas Dixon, All Rights Reserved - www.manifest-tech.com

Proudly prepared by Equine Canada, Canada’s comprehensive

14 Pages · 2010 · 1.7 MB · English

1 Proudly prepared by Equine Canada, Canada’s comprehensive national governing body for equestrianism. www.equinecanada.ca For more information please contact Julie

A Film By: DB Rich Productions LLC

12 Pages · 2013 · 720 KB · English

Ed Asner Wolfgang Bodison Robert Loggia Randolf Mantooth Terry Moore Doris Roberts Alan Thicke Dee Wallace Interviewed with the following Casting Directors:

Words & Music by Bud Green, Les Brown & Ben Homer, 1944 Recorded

1 Pages · 2012 · 11 KB · English

Sentimental Journey Words & Music by Bud Green, Les Brown & Ben Homer, 1944 Recorded by Les Brown Orchestra, 1944 Theme song for the Les Brown Orchestra