### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 297 Class Note for MATH M0050 at Purdue

### View Full Document

## 16

## 0

## Popular in Course

## Popular in Department

This 74 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 16 views.

## Similar to Course at Purdue

## Reviews for 297 Class Note for MATH M0050 at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

Numerical Methods in Financial Engineering Finite Difference Methods Jos FigueroaL pez Purdue University Math 516 Stat 541 Fall 2008 Overview of the method w mdua m fIIK Fil iile illyiyi ii yr introduaion Overview of the method 0 Objective Find numerical approximations TI for a function u which is the solution of a wellposed PDE with suitable boundary Fil iile illyiyi ii yr lntroduaion Overview of the method 0 Objective Find numerical approximations TI for a function u which is the solution of a wellposed PDE with suitable boundary 0 Basic steps lnlrodudion Overview of the method 0 Objective Find numerical approximations TI for a function u which is the solution of a wellposed PDE with suitable boundary 0 Basic steps 0 Discretize time and space on a region of interest leading to a lattice determined by mesh parameters At and AX XnxgnAx tmtgmAt n0N m0M lnlrodudion Overview of the method 0 Objective Find numerical approximations TI for a function u which is the solution of a wellposed PDE with suitable boundary 0 Basic steps 0 Discretize time and space on a region of interest leading to a lattice determined by mesh parameters At and AX XnxgnAx tmtgmAt n0N m0M 9 Approximate the derivatives Btu and axu of the PDE at each point of the lattice by some type finite differencequot Backward difference Afy W Forward difference Afy W I Forward difference All2 y fyhhtyih lnlrodudion Overview of the method 0 Objective Find numerical approximations TIC for a function u which is the solution of a wellposed PDE with suitable boundary 0 Basic steps 0 Discretize time and space on a region of interest leading to a lattice determined by mesh parameters At and AX XnxgnAx tmtgmAt n0N m0M 9 Approximate the derivatives Btu and axu of the PDE at each point of the lattice by some type finite differencequot Backward difference Afy W Forward difference Afy W I Forward difference All2 y fyhhtyih 9 Impose boundary conditions Dirichlet Conditions for uTXM utxM utx0 Neuman Conditions for uTxM 3XutxM 3Xutx0 lnlrodudion Overview of the method 0 Objective Find numerical approximations TIC for a function u which is the solution of a wellposed PDE with suitable boundary 0 Basic steps 0 Discretize time and space on a region of interest leading to a lattice determined by mesh parameters At and AX XnxgnAx tmtgmAt n0N m0M 9 Approximate the derivatives Btu and axu of the PDE at each point of the lattice by some type finite differencequot Backward difference Afy W Forward difference Afy W I Forward difference All2 y fyhhtyih 9 Impose boundary conditions Dirichlet Conditions for uTXM utxM utx0 Neuman Conditions for uTxM 3XutxM 3Xutx0 o The above discretization process transform the PDE into a system of finitedifference equations which solution Earn Xn must be determined Fir ii39yVE iNyryi39ii y iiiyti39iud The eXpiioit method The simplest variation The explicit method Fit ii39yVE iNyryt39ii y Myihud The eXpiioii method The simplest variation The explicit method 0 Consider the PDE Btutx MAX 8Xutx atX BXXutX 7 r utX 0t 1 Finiwtunyryrwt we TheeXpiiciimeihod The simplest variation The explicit method 0 Considerthe PDE Btufx MAX 8Xufx afX BXXufX 7 r ufX 0t 1 o Discretization Using Backward difference in time and centered differences in space leads to the system of finitedifference equations met m m m m m it i n m n1 n71 m n1 2un n71 6f 6X a 6x2 fru 0 where W 2 Wan 85quot r aUman and LIEquot r 3fm7Xn tmzxn39 Finiwtunyryrwt we TheeXpiiciimeihod The simplest variation The explicit method 0 Considerthe PDE Btufx MAX 8Xufx afX BXXufX 7 r ufX 0t 1 o Discretization Using Backward difference in time and centered differences in space leads to the system of finitedifference equations quotH um 711 711 2urT 111 m n i n m n1 m 7 m if M 6X 8 602 run 0 where ofquot MUMX a5quot afmXn and u quot 3fmxn m ufmXn 0 Boundary conditions uX T gX gt u gXN Finiwtunyrw i The eXpiicii method The simplest variation The explicit method 0 Considerthe PDE Btufx MAX 8Xufx afX BXXufX 7 r ufX 0 1 o Discretization Using Backward difference in time and centered differences in space leads to the system of finitedifference equations mil m m m m m it i n m n1 n71 m n1 2un n71 7 m if M 6X 8 602 run 0 where ofquot MUMX a5quot afmXn and u quot 3fmxn m ufmXn 0 Boundary conditions uX T gX gt u gXN 0 Solving the system The special structure of the system allow us to solve it explicitly using Backward induction in time met mm m mm m mm m n Pu 39Un1Ps 39un pd 39unitv 2 withpupdiandpstf6fr7pdipu memww y Mum The eXpllell melhod Technical problems of practical relevance Fli il39wE lllyly i e Manual The eXpli oil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Fli ll39y The eXpli oil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Efficiency How fast is the algorithmquot The eXplioil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Efficiency Howtast is the algorithmquot Stability Are there any error propagation whether the error is in the input data or rounding errorquot The eXplioil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Efficiency Howtast is the algorithmquot Stability Are there any error propagation whether the error is in the input data or rounding errorquot Consistency Does the solution converge to what it should approximate as the disoretization meshes shrink quot The eXplioil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Efficiency Howtast is the algorithmquot Stability Are there any error propagation whether the error is in the input data or rounding errorquot Consistency Does the solution converge to what it should approximate as the disoretization meshes shrink 7quot 9 Tools to analyze and guarantee the above conditions The eXplioil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Efficiency How fast is the algorithmquot Stability Are there any error propagation whether the error is in the input data or rounding errorquot Consistency Does the solution converge to what it should approximate as the disoretization meshes shrink 7quot 9 Tools to analyze and guarantee the above conditions Transform the PDE into a simpler form say a LINEAR PDE The eXplicil method Technical problems of practical relevance 0 Desirable properties of the numerical solution Efficiency How fast is the algorithmquot Stability Are there any error propagation whether the error is in the input data or rounding errorquot Consistency Does the solution converge to what it should approximate as the discretization meshes shrink 7quot 9 Tools to analyze and guarantee the above conditions Transform the PDE into a simpler form say a LINEAR PDE Employ other finite difference approximations this will lead to the so called implicit methodsquot Hmwtuww y Mum The eXpnizn melhod Transforming the BlackScholes equation The eXpli oit method Transforming the BIackScholes equation 0 For numerical reason and stability analysis it is convenient to transform the BS PDE in a simpler form Fil iile illyryi iiyl i we TheeXplicitmethod Transforming the BIackScholes equation 0 For numerical reason and stability analysis it is convenient to transform the BS PDE in a simpler form 9 Working with log return X log 5 and discounted option prices e vt X If vt s is the option price at time twhen the spot asset price is s 2 6vt s rsasvt s szassvt s 7 r vt s 0 VT7 5 57 Fif file illyfyi fiyl i we TheeXplicitmethod Transforming the BIackScholes equation 0 For numerical reason and stability analysis it is convenient to transform the BS PDE in a simpler form 9 Working with log return X log 5 and discounted option prices e vt X wtX vt 9quot satisfies 6wtx r 7 g 6Xwtx a BXXwU X 7 r wtX 0 wTX dgteXt Fif file illyfyi fiyl i we TheeXplicitmethod Transforming the BIackScholes equation 0 For numerical reason and stability analysis it is convenient to transform the BS PDE in a simpler form 9 Working with log return X log 5 and discounted option prices e vt X utX e wt X e vt 9quot satisfies 0392 0392 Btutx r7 6Xutx Jr BXXutX O uTX e TdgteXt Fif iile illyiyi iwl i we TheeXplicitmethod Transforming the BIackScholes equation 0 For numerical reason and stability analysis it is convenient to transform the BS PDE in a simpler form 9 Working with log return X log 5 and discounted option prices e vt X utX e wt X e vt 9quot satisfies 0392 0392 Btutx r7 6Xutx Jr BXXutX O uTX e TdgteXt 9 Explicit Method Solution u e MdgteXquot u quot puu 1psu pdu w m M71 m0 3 05 6t 02m 6t W39th Pu m f 275x Pd W 275x and PS 1 Pd Pu metunyrw y Mm u Important Remarks fhenexpvizft melaod DJ fIIK The eXpiicit method Important Remarks 0 Notice that the solution at each point tmxn is a weighted average of the three closest points at tm Hence we can think of this method as an Additive trinomial tree methodquot Fit ii39wE iiiyry iyi i we TheeXpiicitmethod Important Remarks 0 Notice that the solution at each point tmxn is a weighted average of the three closest points at tm Hence we can think of this method as an Additive trinomial tree methodquot 9 Indeed the piecewise process 7 defined by m6t 6X with prob pu Xm16t m6t with prob p5 m6t 7 6X with prob pd converges to log S 0W r 7022t as if a 0 and 6X a 0 Fli illyVE lllylyl39iiyl i we TheeXplicilmelhod Important Remarks 0 Notice that the solution at each point tmxn is a weighted average of the three closest points at tm Hence we can think of this method as an Additive trinomial tree methodquot 9 Indeed the piecewise process 7 defined by m6t 6X with prob pu Xm16t m6t with prob p5 m6t 7 6X with prob pd converges to log S aW r 7022t as if a 0 and 6X a 0 9 The explicit method is essentially Backward induction on a discrete approximation of the BlackScholes model given by Soex Fli illyVE lllylyl39iiyl i we TheeXplicilmelhod Important Remarks 0 Notice that the solution at each point tmxn is a weighted average of the three closest points at tm Hence we can think of this method as an Additive trinomial tree methodquot 9 Indeed the piecewise process 7 defined by m6t 6X with prob pu Xm16t m6t with prob p5 m6t 7 6X with prob pd converges to log S aW r 7 022t as if a 0 and 6X a 0 9 The explicit method is essentially Backward induction on a discrete approximation of the BlackScholes model given by Soex 9 For positive weights pupdps it suffices that 0261 602 and that if and 6X are small enough lt1 Stability Hemp fim zw The eXpiioit method Stability 0 Question Under what conditions the explicit method is stable Fli illyf lllyryl iiyl i we TheeXplicilmelhod Stability 0 Question Under what conditions the explicit method is stable 9 To analyze the problem we first notice that vt s is the solution of 2 atvt s rsasvt s aiszassv s 7 r vt s 0 VT s dgts if and only if vt s s 2quot e 2 2T uazT 7 i log 5 with n 2ra2 and u7 X being the solution of the diffusion equation 87u7X 7 BXXu7 X 0 u0X e 2quot Xdgtext 4 Fli il39wE lllyryl ii i The eXpiicii method Stability 0 Question Under what conditions the explicit method is stable 9 To analyze the problem we first notice that vt s is the solution of 2 atvt s rsasvt s aiszassv s 7 r vt s 0 VT s dgts if and only if vt s s 2quot e 2 2T uazT 7 i log 5 with n 2ra2 and u7 X being the solution of the diffusion equation 87u7X 7 BXXu7x 0 u0x e 2quot Xdgtext 4 9 Next apply the explicit method with the initial cond u0X 9 Does the numerical solution uT remain bounded when 67 H 0 and 6X a 0 Fli il39wE lllyryl ii i The eXpiicii method Stability 0 Question Under what conditions the explicit method is stable 9 To analyze the problem we first notice that vt s is the solution of 2 atvt s rsasvt s aiszassv s 7 r vt s 0 VT s dgts if and only if vt s s 2quot e 2 2T uazT 7 i log 5 with n 2ra2 and u7 X being the solution of the diffusion equation 67u7X 7 BXXu7x 0 u0x e 2quot Xdgtext 4 9 Next apply the explicit method with the initial cond u0X 9 Does the numerical solution uT remain bounded when 67 H 0 and 6X a 0 9 It turn out that the solution uT takes the general form m 6t 76 k6 39an un 16X2e Xe X 2 e Fli il39wE lllyryl ii i The eXpiicii method Stability 0 Question Under what conditions the explicit method is stable 9 To analyze the problem we first notice that vt s is the solution of 2 6vt s rsasvt s szavi s 7 r vt s 0 vT s dgts if and only if vt s s z1 e 12 72T uazT 7 f log 5 with n 2ra2 and u7X being the solution of the diffusion equation 87u7X 7 BXXu7 X 0 u0x e zquot x equott 4 9 Next apply the explicit method with the initial cond u0X 9 Does the numerical solution u quot remain bounded when 67 H 0 and 6X a 0 9 It turn out that the solution u quot takes the general form quot7 IT 1 6t eik6x eeikax 72 eikxn 9 Thus the condition a 82 g g is necessary for stability Fli il39wE lllyryl ii i The eXpiicii method Stability 0 Question Under what conditions the explicit method is stable 9 To analyze the problem we first notice that vt s is the solution of 2 atvt s rsasvt s aiszassv s 7 r vt s 0 VT s dgts if and only if vt s s 2quot e 2 2T uazT 7 i log 5 with n 2ra2 and u7 X being the solution of the diffusion equation 67u7X 7 BXXu7x 0 u0x e 2quot Xdgtext 4 9 Next apply the explicit method with the initial cond u0X 9 Does the numerical solution uT remain bounded when 67 H 0 and 6X a 0 9 It turn out that the solution uT takes the general form m 6t 76 k6 39an un 16X2e Xe X 2 e 9 Since almost any function gx can be expressed as series expansions Ekez e ank the conditions is both necessary and sufficient Hmwtuww y Mum The eXpnizn melhod Stability General case Fli il39wE lllyly i yl The eXpiioil method Stability General case 0 Consider the method 2 It follows that if pmpmpS 2 0 and atX Max and gX are bounded then sup lam g G lt 00 mm Fli ll39lellylyl liyl i we TheeXplicilmelhod Stability General case 0 Consider the method 2 It follows that if pmpmpS 2 0 and afX Max and gX are bounded then supla l g G lt 00 mm 9 Inspection of the coefficients of 2 makes evident that if lafXl lt A and 6t 39W lt then pmpmpS 2 0 for small enough if and 6X 17 Fli ll39yVE lllylyl39liyl i we TheeXplicilmelhod Stability General case 0 Consider the method 2 It follows that if pmpmpS 2 0 and afX Max and gX are bounded then sup lam g G lt 00 mm 9 Inspection of the coefficients of 2 makes evident that if lafXl lt A and 6t 39W lt then pmpmpS 2 0 for small enough if and 6X 9 How bad can the instability be W H amp D apply the explicit method to 4 and then approximate the value of a put option Strike10 Mat12 year in the BS model a 20 r 5 17 Fli ll39yVE lllylyl39liyl i we TheeXplicilmelhod Stability General case 0 Consider the method 2 It follows that if pmpmpS 2 0 and afX Max and gX are bounded then sup lam g G lt 00 mm 9 Inspection of the coefficients of 2 makes evident that if lafXl lt A and 6t 39W lt then pmpmpS 2 0 for small enough if and 6X 9 How bad can the instability be W H amp D apply the explicit method to 4 and then approximate the value of a put option Strike10 Mat12 year in the BS model a 20 r 5 So a 25 a 5 a 52 Exact 7 275 275 1741 275 10 44 44 625 44 14 0028 0027 1521 0028 17 meuyrw y Mum The eXprizn melhod What is the discretization error memuyrw yr The eXprrott method What is the discretization error 0 Will the solution of the finitedifference system converge to the solution of the PDE as the mesh parameters shrink memuyrw yr The eXprrott method What is the discretization error 0 Will the solution of the finitedifference system converge to the solution of the PDE as the mesh parameters shrink 9 At what rate does the discretization error maxmm tutmxn 7 um converge to 0 memuyrw yr The eXprrott method What is the discretization error 0 Will the solution of the finitedifference system converge to the solution of the PDE as the mesh parameters shrink 9 At what rate does the discretization error maxmm tutmxn 7 um converge to 0 Fil iilyVE illyiyl39iiyl i we TheeXplioilmelhod What is the discretization error 0 Will the solution of the finitedifference system converge to the solution of the PDE as the mesh parameters shrink 9 At what rate does the discretization error maxmm lutmxn 7 u 7quotl converge to 0 9 Example Consider the explicit method 2 applied to the heat equation 4 It turns out that manxlu mxn 7 um 0a 0mm This follows from plugging utmXn into the finitedifference operatorand use Taylor s expansions of u Fil iilyVE illyiyl39iiyl i we TheeXplioilmelhod What is the discretization error 0 Will the solution of the finitedifference system converge to the solution of the PDE as the mesh parameters shrink 9 At what rate does the discretization error maxmm lufmxn 7 u 7quotl converge to 0 9 Example Consider the explicit method 2 applied to the heat equation 4 It turns out that manxlu mxn 7 um 0a 0mm This follows from plugging ufmXn into the finitedifference operatorand use Taylor s expansions of u o The above rate of convergence holds for the general system 1 under boundedness conditions on the coefficients a and u FW39yrE Myrm y MAW u General description JMTER meibodrz39 fIIK my mpn n me hods39 General description 0 Motivation implicit methods General description 0 Motivation The stability condition 616X2 lt 1 of the explicit methods implies that if we one wishes to improve accuracy by doubling the number of Xpoints one must quarter the time mesh taking about 8 times longer implicit methods General description 0 Motivation The stability condition 616X2 lt 1 of the explicit methods implies that if we one wishes to improve accuracy by doubling the number of Xpoints one must quarter the time mesh taking about 8 times longer Implicit methodsquot will allow us to increase the number of X points without having to take very small time mesh implicit methods General description 0 Motivation The stability condition 616X2 lt 1 of the explicit methods implies that if we one wishes to improve accuracy by doubling the number of Xpoints one must quarter the time mesh taking about 8 times longer Implicit methodsquot will allow us to increase the number of X points without having to take very small time mesh 9 Basic idea Approximate by a linear combination of fonNard and backward difference approximations 6utx N ut 61 7X7 utX utX 7 ut7 6tX TNOerU awf 5 implicit methods General description 0 Motivation The stability condition 616X2 lt 1 of the explicit methods implies that if we one wishes to improve accuracy by doubling the number of Xpoints one must quarter the time mesh taking about 8 times longer Implicit methodsquot will allow us to increase the number of X points without having to take very small time mesh 9 Basic idea Approximate by a linear combination of fonNard and backward difference approximations 6utx N ut 61 7X7 utX utX 7 ut7 6tX TNOerU awf 5 9 Known methods 9 O Explicit method 9 1 Fully implicit method 9 O gt CrankNicolson method Hmwtmm y WM mpn h me hods39 Fully Implicit Method Hmwtmm y WM mpn n mamas Fully Implicit Method 0 Consider the PDE Btutx MAX 8Xutx atX BXXutX 7 r utX 0 6 Hmwtmyw c mpnc39n me hods Fully Implicit Method 0 Considerthe PDE Btutx MAX 8Xutx atX BXXutX 7 r utX 0 6 o Discretization Using Forward diff in time and centered diff in space 1 m m m m m 571 771 Mm n1 n71 am n1 2un n71 6t 5x 602 erusquoto 7 where W 2 Wan 85quot 1 80mm and ULquot 1 WM tTMXN rmnyrmim i implicit methods Fully Implicit Method 0 Considerthe PDE Btutx MAX 8Xutx atX BXXutX 7 r utX 0t 6 o Discretization Using Forward diff in time and centered diff in space 1 m m m m m 571 771 Mm n1 n71 am n1 2un n71 6t 5x 602 eruiquoto 7 where ofquot MUmXN a5quot atmxn and u 1quot Etmxn m utmXn 0 Solving the system Notice that u quot can not be solved explicitly and rather u quot um i u q is implicitly defined in terms of u quot1 via a linear system of equations IdedtAgumu quot mltM 8 with final cond u gXn and Dirichlet cond ug g 0 mltM Hmwtmm mm mpn hmemodsr Fully Implicit Method Cont Finuyrmnm yi impiic ii meihods Fully Implicit Method Cont o The matrix A22 is given by 751m w o o o o 0 a2 32 72m 0 0 A27 I I I I I I I I 0 a 71 where m 7 arT MIT m 7 8r 7 MIT m 7 8 a 6x2 axy 7 6x2 60 5quot 26X2 r39 9 rmnymm yr implicit methods Fully Implicit Method Cont o The matrix A2 is given by 751m 71m 0 o o t 0 Am 0 a quot 73 7gquot 0 t 0 6X 0 am1 where m arT MIT In 89 MIT m 8 7 2 9 aquot W W lquot W 60 5quot W l l o The implicit method resulting from the approximation 5 with general 6 will take a form Idi dtAgu quot1d1766tAju quot mltM 10 with final cond u gXn and Dirichlet cond L16quot y 0 mgM iJmz ITliill39 T1719 LU m ihod I m mil lowr iiimm m i un 3930 Hu39n JJUSiillJiiLi H54 in n 1il39lmJ LOI39JGiI39m i 3 QEQLJEJI39IJE n M 1 Nil 35 iliv The EI39I implicit methods Overview 0 The tridiagonal matrix Idi t A22 is not necessarily invertible However it is known that a diagonally dominant matrix is invertible Under what conditions the matrix is diagonaly dominant lmplic it methods Overview 0 The tridiagonal matrix Idi t A22 is not necessarily invertible However it is known that a diagonally dominant matrix is invertible Under what conditions the matrix is diagonaly dominant 0 There are two popular methods to find u quot in 810 LU decomposition and iterative methods implicit methods Overview 0 The tridiagonal matrix Idi t A22 is not necessarily invertible However it is known that a diagonally dominant matrix is invertible Under what conditions the matrix is diagonaly dominant 0 There are two popular methods to find u quot in 810 LU decomposition and iterative methods 0 The LU method is an exact method It consists of bringing the matrix Id 7 6t All into a lower triangular matrix using elementary operations and then solve using substitution implicit methods Overview 0 The tridiagonal matrix Idi t A22 is not necessarily invertible However it is known that a diagonally dominant matrix is invertible Under what conditions the matrix is diagonaly dominant 0 There are two popular methods to find u quot in 810 LU decomposition and iterative methods 0 The LU method is an exact method It consists of bringing the matrix Id 7 6t All into a lower triangular matrix using elementary operations and then solve using substitution 0 Iterative methods construct a sequence umquot k 0 such that Iim uTgtkuT mltM n1N71 kaoo implicit methods Overview 0 The tridiagonal matrix Idi t A22 is not necessarily invertible However it is known that a diagonally dominant matrix is invertible Under what conditions the matrix is diagonaly dominant 0 There are two popular methods to find u quot in 810 LU decomposition and iterative methods 0 The LU method is an exact method It consists of bringing the matrix Id 7 6t All into a lower triangular matrix using elementary operations and then solve using substitution 0 Iterative methods construct a sequence umquot k 0 such that Iim u quotgtk u 7quot mlt M n 1N71 kaoo All these method exploits heavily the tridiagonal structure of the matrix Id 7 6t A22 motilier oi implicit methods Iterative solution methods 0 The key idea comes from the following manipulation of 7 where 047quot 67quot and 7quot are as in 9 1 u quot u397quot1 a397quot6tu397quot1 7 7quot6tu quot1 n 1ttN71t The above can be seen as an equation of the form u quot Hu quot motivating the use of a fixed point type method umquot1 Hu quotgtk momer oi lmplic it methods Iterative solution methods 0 The key idea comes from the following manipulation of 7 where 047quot 67quot and 7quot are as in 9 1 1 505quot The above can be seen as an equation of the form u quot Hu quot motivating the use of a fixed point type method umquot1 Hu quotgtk u n uff aT6tuT17T6tu 11 n1mN71t o Jacobi Starting with uT u t compute iteratively 1 k 1 7 1 k k unm t 7 W u anm6tu1 mam1 momer oi implicit methods Iterative solution methods 0 The key idea comes from the following manipulation of 7 where 047quot 67quot and 7quot are as in 9 1 u quot u397quot1 a397quot6tu397quot1 7397quot6tu quot1 n 1ttN71t The above can be seen as an equation of the form u quot Hu quot motivating the use of a fixed point type method umquot1 Hu quotgtk o GaussSeidel Starting with uTgt u t compute iteratively mk1 7 1 uquot 1 6f quot forn1tN71 in thatorder u amou t woou mormm 1 implicit methods Iterative solution methods 0 The key idea comes from the following manipulation of 7 where 047quot 67quot and 73quot are as in 9 u quot 7 1 T 1 HMWquot The above can be seen as an equation of the form u quot Hu quot motivating the use of a fixed point type method umquot1 Hu quotgtk W1 anm6tuquot1 v quot6fu quot17 n 1vN1 o SOR Successive OverRelaxation Starting with uTgt u t compute iteratively for n 1 t t N 7 1 in that order 1 k 1 f k 1 k yr 7 1 6W W a9quotltgttu j manual mk1 m k mkt mk un un WltYn un 7 where 1 lt w lt 2 the overrelaxation parameter There is an optimal of 6 12 that make the method to converge the fastest Fir ii39wE iiiyryi ii yr impiic it methods Convergence of implicit methods Theorem See Lamberton and Lapeyre for references and details Let ut X be the solution of 6 and letu quot Mquot t t t u qy be the solution of the system 10 Define DtX E5 gt5Xtx as follows EI7Xu 7quot ifxniltxgxn m716tltt m6t 0 otwt 6X30 X 617 Etx6X2 7 31 7X7 6X2 Then 0 Whent2g6g1 Iim Et ut Iim BEt But mm 7x x mm X x X x 0 When 0 g 6 lt 12 the limit above holds provided thata 6f6X2 a 0 as 6t 6X A 0

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.