Solution methods Iterative Techniques Lecture 6
✂✁☎✄✝✆✟✞✡✠☛✁☎☞✍✌✏✎✑✞✡✒✓✁✕✔✗✖✙✘ ✚ ✞✛✎✢✜✛✣✙✞✡✠✥✤✦✎★✧✩✎✫✪✛✒✓☞✗✠✭✬✦✆✮✎✫✖ ✯✎✫✪✑✞✡✆✮✜✰✎★✱
1 Motivation SLIDE 1 Consider a standard second order finite difference discretization of V-u= on a regular g 1.2. and 3 dimensions 1.1 1D Finite differences △m=h bandwidth b= 1 n points Cost of Gaussian elimination O(bin)=O(n) 1.2 2D Finite differences slide 3 i-1,},i+1,j 1 7× points bandwidth b= n Cost of Gaussian elimination 0(b2n2)=0(n")
✲ ✳✴☎✵✷✶✝✸☎✹✺✵✻✶✭✴✽✼ ✾❀✿❂❁❄❃❆❅❈❇ ❉✫❊●❋■❍❑❏▼▲❖◆✭P❘◗✕❍❑❙✥◗●❋❚▲❯◗❱P❲▲✟❍❳◆❩❨✭❊●❋❚▲✗❊●P❲▲❖◆❩P✫❬■❋❯❏❭❙✥◆❪▲❖❏❴❫❀◆❩P❳◆❩❋❚❨☛◆☎▲❖❏▼❍✥❨☛P✥◆☛❙❳❏❛❵❩◗❱❙❳❏❛❊●❋✓❊❱❜ ❝❡❞✦❢☛❣✮❤❥✐✛❦ ❊●❋✮◗✦P❳◆❩❧●♠❯♥▼◗❱P♦❧♣P❳❏▼▲ ❦ ❏❛❋rq ❦❚s❖❦ ◗●❋❚▲✮t✦▲❯❏❴✉✈◆✭❋■❍❑❏❛❊●❋❚❍❩✇ ① ②④③ ❤⑥⑤ ⑦✷⑧❑⑦ ⑦✰⑨✍⑩✕❶❑❷❸❶❺❹❖❻❼⑨❥❶❾❽❿❻✰➀❯❻❆❷❸➁➂❻❆➃ ✾❀✿❂❁❄❃❆❅r➄ ➅➇➆ ❊●❏❛❋♣❙❲❍ ➈ 0 1 2 3 4 5 6 0 1 2 3 4 5 6 nz = 13 ➅➊➉✗➅ ✉✈◗❱❙❳P✥❏❭➋ ➌◗❱❋■▲❖➍❘❏❛▲❖❙❳➎④➏ ❤ q ❉✫❊♣❍❑❙❘❊❱❜✑➐➑◗❱♠❚❍✥❍❑❏▼◗❱❋✗◆✭♥❛❏❴✉✈❏❛❋❚◗➒❙✥❏❴❊♣❋➔➓✈→➣➏❢ ➅❆↔ ❤⑥↕➇➙❾➛✙➜ ⑦✷⑧➞➝ ➝✷⑨✍⑩✕❶❑❷❸❶❺❹❖❻❼⑨❥❶❾❽❿❻✰➀❯❻❆❷❸➁➂❻❆➃ ✾❀✿❂❁❄❃❆❅r➟ ➅➊➉✗➅➠➆❊♣❏❴❋❂❙❲❍ ➈ 0 5 10 15 20 25 0 5 10 15 20 25 nz = 105 ➅❢ ➉✓➅❢ ✉✕◗➒❙❳P✥❏❴➋ ➌◗❱❋❚▲❯➍❘❏❛▲➡❙✥➎④➏ ❤ ➅ ❉✫❊♣❍❑❙✙❊❱❜✷➐➑◗❱♠❚❍✥❍❑❏▼◗❱❋✓◆✭♥❛❏❛✉✦❏❛❋❚◗❱❙❳❏❛❊●❋★➓✈→➣➏❢ ➅❢ ↔ ❤⑥↕➠➙❺➛♦➢➡➜ q
1.3 3D Finite differences +1,k 7×n× n points bandwidth b=n This means that we we halve the grid spacing, we will have 8 times(23)more unknowns and the cost of soluing the problem will increase by a factor of 128 (2). It is apparent that, at least for practical three dimensional problems, faster methods are needed 2 Basic iterative methods 2.1J aconI 2.1.1 Intuiti d of sol at starting from an arbitrary u(a, 0) That is, we ecpect the solution af the time dependent problem to converge to the lution of Solution by relaxation By adding the time dependent term at, we have now a parabolic equation. If kept fixed, we expect the solution to"ce to the steady state solution (i.e 0). Recall that the time dependent heat transfer problem is modeled by this equation. In this case, we expect the temperature to settle to a steady state distribution provided that the heat source,f, and the boundary conditions, do not depend on t
➤✷➥➞➦ ➦✷➧✍➨✕➩❑➫❸➩❺➭❖➯❼➧❥➩❾➲❿➯✰➳❯➯❆➫❸➵➂➯❆➸ ➺❀➻❂➼❄➽❆➾➇➚ ➪r➶✗➪r➶✗➪r➹❀➘●➴❛➷♣➬❲➮ ➱ 0 20 40 60 80 100 120 0 20 40 60 80 100 120 nz = 725 ➪✰✃☎➶✓➪✰✃➑❐✕❒➒➬❳❮✥➴❴❰ Ï ❒❱➷■Ð❖Ñ❘➴❛Ð❖➬❳Ò④Ó❘ÔÕ➪✰Ö ×➘❂➮❾➬❘➘●Ø✷Ù➑❒●Ú❚➮❳➮❳➴▼❒❱➷✟Û❩Ü❴➴❛❐✈➴❴➷■❒➒➬❳➴❛➘●➷ÞÝ✈ß➞ÓÖ ➪✰✃❩àáÔ⑥â➇ã❾ä❘å➡æáç è➂é➡ê▼ë✦ì✈í❲î➒ï❚ë✽ðñé❯î❱ð❘òáí✈òáí❪é❯î❱óõô➒í✕ðñé❯í❿ö●÷✝êùø✗ë➣ú❯î♣û☛ê❄ï➡ö➒ü✙òáí✈ò✷ê❄ó❄ó❆é❚î➒ô➒í✂ý✮ð➣ê❄ì✈í☛ë✗þñÿ ✃✁ ì✄✂➒÷❳í ☎ï✝✆❱ï✞✂❱ò✷ï❯ë✂î➒ï➂ø ðñé❯í✓û✟✂➒ë✝ð✠✂☛✡✕ë☞✂❱óõôê❄ï❂ö➇ð❄é❚í➑ú➂÷✌✂✎✍✭ó❴í✭ì➔ò✷ê❄ó❄ó✫ê❄ï❀û✭÷❳í❲îë✭í✏✍☞✑➇î✒✡☛î●û✭ð✓✂❱÷✔✂☛✡✖✕✘✗♣ý þñÿ✘✙ ✎✚✜✛ð✛ê▼ë✙î❲ú●ú❚î➒÷❳í✭ï❚ð✻ðñé❯î❱ðùü✷î➒ð✛ó❴í❲îë✝ð✢✡☞✂❱÷✻ú❀÷✥î●û✭ð➞êùû❲î➒ó■ð❄é❖÷❳í❲í❸ø❱ê❄ì✈í✭ï❯ë✝ê✣✂❱ï❀î➒ó●ú❀÷✟✂✎✍✭ó❴í☛ì✽ë❲ü✢✡☛î➒ë❲ð❺í✭÷ ì✕í☛ðñé✤✂øë❪î➒÷✥í❿ï➂í✥í❲ø♣í✥ø✚ ✥ ✦★✧✪✩✬✫☞✭✯✮✞✰✬✱✳✲✴✧✠✰✬✫☞✵✶✱✸✷✱✹✰✬✺✼✻✾✽✿✩ ❀♦➥❑➤ ❁❃❂✻➵❅❄❇❆❸➩ ❈❊❉✣❋✞❉✣❋ ●☞❍❅■❑❏▼▲✣■◆▲✣❖◗P❘●❙❍❅■◆P✢❚❱❯▼❚❲P✢■◆❳❨■❑▲✣❩✞❍ ➺❀➻❂➼❄➽❆➾❭❬ ❪➷❚➮❑➬❳Û❒●Ð✗➘❱Ø✷➮❑➘♣Ü❴❫➡➴❛➷✤❵ ❛❝❜❅❞◆❞ Ô❢❡❤❣ Ñ✢Û➑➮❳➘●Ü✐❫●Û ❥ ❥✞❦❜ Ô ❜❞❑❞✳❧ ❡❤❣ ♠✒♥ ➮❑➬✥❒❱❮❳➬❳➴❛➷✤❵✽Øñ❮❳➘♣❐ ❒●➷✓❒●❮Ï ➴❴➬❳❮❲❒❱❮✟♦ ❜ ßq♣sr✟t♣à☞✉ ✈Û☎Û✭❰➡➹❀Û◆✇☛➬ ❜ ß✣♣sr ❦ ➱②①à ➱ ❜ ßq♣➂à✁✉ è➂é❯î❱ð✑ê▼ë❲ü✛òáí☎í✟③☛ú❯í❲û✭ð✷ð❄é❚í❸ë☞✂❱ó☎ð➣ê✣✂➒ï④✂☛✡❸ð❄é❚í✺ð➞ê❄ì✕í☎ø●í❺ú❚í☛ï➂ø●í✭ï❚ð❀ú❀÷✟✂✎✍✭ó❴í☛ì ð✓✂✈û⑤✂➒ï■ô í✭÷➞ö❂í➑ð✓✂✽ðñé❯í ë❙✂➒ó☎ð➣ê✣✂➒ï⑥✂☛✡➑ðñé❯í❿ë✝ðí❲î●ø✘✑✕ë✝ðî❱ðí♦ú❀÷✌✂⑦✍☛ó❛í☛ì✚ ⑧❭⑨❶⑩✁❷❘❸ ❹✬⑨❨❺✌❻▼⑩❽❼☛⑨✝❾➀❿⑦➁➃➂⑦❷✘❺➅➄❨➆s➄❶⑩❽❼☛⑨✝❾ ➇♦✓❒♣Ð❯Ð❖➴❛➷✤❵✂➬✥Ò❯Û❿➬✥➴❴❐✈Û✈Ð❖Û✭➹❀Û✭➷■Ð❖Û✭➷❂➬❡➬✥Û✭❮✥❐➉➈◆➊ ➈◆➋ ❣❀Ñ✢Û❪Ò❚❒❱❫♣Û❿➷❯➘➒Ñ ❒✂➹❚❒●❮✥❒Ï ➘♣Ü❴➴➌✇➑Û◆➍❂Ú❚❒❱➬❳➴❛➘●➷❊✉ ❪Ø ➬❳Ò❚Û Ï ➘♣Ú❯➷❚Ð❯❒●❮✌♦➎✇☛➘●➷■Ð❖➴❭➬✥➴❴➘♣➷❚➮❿❒●❮❳Û➐➏●Û❩➹❖➬➒➑❯❰❖ÛÐ❶❣✡Ñ✢Û✕Û☛❰❖➹❀Û◆✇☛➬☎➬❳Ò❯Û✟➮❳➘●Ü❛Ú❖➬✥➴❴➘♣➷➠➬✥➘➃➓✌✇✭➘●➷✝❫●Û❩❮✌❵♣Û◆➔ ➬❳➘➊➬✥Ò❯Û④➮❑➬❳Û❩❒♣Ð❨♦❈➮❑➬✥❒❱➬❳Û④➮❳➘●Ü❛Ú❖➬❳➴❛➘●➷ ßñ➴→✉ Û✎✉✐❣ ➈❑➊ ➈◆➋ Ô➣t❂à✁✉↕↔❘Û❑✇✭❒●Ü❴Ü❘➬✥Ò❚❒➒➬✕➬✥Ò❯Û ➬✥➴❴❐✈Û④Ð❖Û❩➹■Û❩➷❚Ð❖Û✭➷❂➬ Ò❯Û❒➒➬✂➬✥❮✥❒●➷❚➮❾ØñÛ❩❮✂➹❯❮✥➘Ï Ü❛Û✭❐ ➴▼➮✂❐✈➘❖Ð❖Û✭Ü❛Û❩Ð Ï ♦❈➬❳Ò❯➴▼➮✟Û❑➍❂Ú❚❒➒➬✥➴❴➘♣➷❊✉ ❪➷Õ➬❳Ò❯➴▼➮✔✇❩❒●➮❳Û✎❣♦Ñ✢Û④Û☛❰❖➹❀Û◆✇✝➬ ➬❳Ò❚Û☎➬❳Û❩❐✦➹❀Û✭❮❲❒➒➬✥Ú❯❮✥Û☎➬❳➘✂➮❳Û☛➬❳➬❳Ü❛Û☎➬❳➘✟❒✟➮❾➬✥Û❩❒●Ð✤♦✗➮❑➬✥❒➒➬✥Û❪Ð❖➴▼➮❾➬✥❮❳➴ÏÚ❖➬✥➴❴➘♣➷ ➹❯❮✥➘❲❫❂➴▼Ð❖ÛÐ✟➬✥Ò❚❒➒➬❡➬❳Ò❯Û❿Ò❚Û❩❒➒➬ ➮❳➘●Ú❯❮⑤✇☛Û⑦❣❨❡❤❣❯❒●➷❚Ð✗➬❳Ò❯Û Ï ➘●Ú❚➷❚Ð❯❒❱❮✟♦✖✇✭➘●➷❚Ð❖➴❴➬❳➴❛➘●➷■➮❙❣❯Ð❖➘✈➷❯➘●➬❡Ð❖Û✭➹❀Û✭➷■Ð✗➘♣➷ ❦ ✉ ÿ
we use an inexpensive(explicit)method. Thus avoiding the need to solve ystem o equ For instance 20+ }2=1,f={f} Here, we use the super indec r to denote iteration(or time level). u will denote the solution vector. An appro imation to u at iteration r will be denoted by l' SLIDE 7 2 possible, i.e.(At=h2/2) h2 1+12f) 2.1.2 Matrix form SLIDE 8 A=D-L-U L: Lower triangl triangular (D-L-Uu=f Iterative method (L+Uu+ D-(L +U)u+D- f D-(D-A)ur+ (I-D-1A)
➙✞➛✢➜➞➝s➟❭➠ ➡▼➢➐➤✌➢✎➥✐➦✎➧ ➨✞➩➨◗➫✿➭ ➩ ➯◆➯➳➲➸➵ ➺➧✏➻◗➤❽➧④➼✎➽➸➾✐➽✤➧☞➚❨➪✞➧❙➽➶➤✌➾✐➦✎➧➘➹q➧❙➚✝➪➶➥❴➾➌➴☞➾❴➷⑤➬➐➮➐➧❙➷✌➱✤➢❨✃❶❐❮❒❅❰❨Ï✝Ð✿Ñ✘Ò❱Ó✘Ô✣Õ❲Ô➞Ö✢×➸Øq❰✤Ù❘Ö✞Ù⑤Ù⑤Õ⑥ØÚÓ❭Ð❙Ó❲ÛÜÒ❲Ù➎Ñ ÛÜÔ➞Ö❅Ù✟Ñ✘ÝÞÐ✁ß❱Ð⑤ØÚÙ❙àáÓ❽â➒Ù✟ã❙Ï➶Ñ❲Ø→Ô✣Ó❲Ö➶Ð❙ä å✤➢⑦æ❝➾❴➽◗➤☛➷⑤➼✘➽➶➴❙➧✎çéè➩✞ê✟ë▼ì í î è➩ê í ï ➫ ➭ è➩ê íë▼ì î➘ð è➩ê í ➲ è➩ê íqñ ì ò➶ó ➲ ➵è í ô ➭öõ è➩ í✓÷❱øí❴ù ì❱úüû❭➭ýõ ➵èíÚ÷❑øí✐ù ì þ✒Ù❙Ý✌Ù☞ÿ✁❇ÙÞÏ✝Ð❙Ù Øq❰✤Ù Ð✁Ï✄✂✤Ù❙Ý➳Ô➞Ö❅Õ✎Ù✆☎✞✝✾ØÚÓ➐Õ✎Ù❙Ö✞Ó❲ØÚÙ✠Ô➞ØÚÙ☞Ý✌Ñ✘Ø➅Ô✣Ó✘Ö✠✟ÚÓ✘Ý Ø→Ô➞à✄Ù✠Û❴Ù☞Ò❲Ù❙Û✡✎ä ô ✴Ô➞Û➞Û❊Õ✎Ù❙Ö✞Ó❲ØÚÙ Øq❰✤Ù Ð❙Ó❲ÛÜÏ❨Ø→Ô✣Ó❲Ö✿Ò❲Ù☞☛☞ØÚÓ❲Ý❙ä✍✌ Ö④Ñ✆✂✎✂✞Ý✌Ó✏☎✎Ô➞à✄Ñ❲Ø→Ô✣Ó❲Ö➎Ø✓Ó ô Ñ❲Ø✴Ô➞ØÚÙ❙Ý✌Ñ❲Ø→Ô✣Ó❲Ö✑✝✒✴Ô➞Û➞Û✔✓⑤Ù✪Õ✎Ù❙Ö✞Ó❲ØÚÙ⑤Õ✕✓☞ß ô ê ä ô ê✌ë▼ì ➭ ô ê ➲ ï ➫ ➹ û î✠✖ô ê ➬ ➭ ➹✘✗ î ï ➫✖➬ ô ê ➲ ï ➫û✚✙ ➙✞➛✢➜➞➝s➟✜✛ ✢➷⑤➼✤✣✤➾✐➥❴➾❴➷✦✥✖✃❨➾➌➴✁➷⑤➼❲➷✟➧◆➤✹➷✟➱➶➼❲➷ ï ➫★✧ òó ð ➡✹➱✝➻➶➤◆ç ➺➧✠➷✟➼✪✩✎➧ ï ➫ ➼⑦➤✹➥✐➼✎æ✬✫⑦➧✠➼⑦➤✹➪◗➢✢➤✌➤✌➾✭✣✤➥❴➧⑦ç❨➾➅❐ ➧✎❐✳➹ï ➫ ➭ òó✄✮ ð ➬✁❐ ô ê✌ë❤ì ➭✰✯✗ î òó ð ✖✲✱✴✳ô ê ➲ òó ð û ✵ è➩ê✌ë▼ì í ➭✷✶ ð ➹ è➩ê íë❤ì ➲ è➩ê íqñ ì ➲ òó ➵è í ➬✹✸q➢✎æ✻✺ ➭ ✶ ú✏✙✼✙✼✙✾✽ ❐ ✿❁❀❃❂❄❀❅✿ ❆❈❇❊❉✼❋❍●❏■▲❑✔▼◆❋❍❖ ➙✞➛✢➜➞➝s➟◗P ✢➪✤➥✐➾❴➷ ✖ ✖ ➭❙❘ î✠❚⑥î✜❯ ❱❲❳ ❘❩❨❭❬➾✐➼✪✫✎➢✎➽◗➼✘➥ ❚ ❨❭❪➢➺➧❙æ❃➷✟æ✌➾➌➼✘➽❊✫⑦➻✤➥➌➼✘æ ❯ ❨❭❫➪➶➪◗➧◆æ❝➷✌æ✟➾✐➼✎➽❊✫✎➻➶➥✐➼✎æ ✖ ô ➭➀û ✣✞➧◆➴❙➢✎➮➐➧◆➤ ➹❘ î✠❚⑥î✜❯➬ ô ➭❢û ❴✓➷✌➧◆æ✟➼✘➷✌➾✐➦✎➧✠➮➐➧☞➷✌➱➶➢✝✃ ❘ ô ê✌ë▼ì ➭ ➹❚ ➲ ❯➬ ô ê ➲ û ➙✞➛✢➜➞➝s➟◗❵ ô ê✟ë▼ì ➭ ❘ ñ ì ➹❚ ➲ ❯➬ ô ê ➲ ❘ ñ ì û ➭ ❘ ñ ì ➹❘ î◗✖➬ ô ê ➲ ❘ ñ ì û ➭ ➹✘✗ î ❘ ñ ì ✖➬ ô ê ➲ ❘ ñ ì û ❛
RJ R=(-D-1 acobi iteration matrix D"=n2 Note that, in order to implement this method t for matrices, but update the unknowns, one component at a time, according to +hifi)for 2.1.3 Implementation Jacobi iterat 2.2 Gauss-Seidel SLIDE 11 Assuming we are updating the unknowns according to their index i, at the time u r +I needs to be calculated, we already know ur+i. The idea of Gauss-Seidel iteration is to always use the most recently computed value nknown values ost recent +1 12f)
❜❞❝✆❡✁❢❤❣❙✐❦❥❧❜★❝❧♠♦♥❩♣q❢sr ✐t❥✉❣✇✈✘①③②✠♥④♣q❢⑥⑤❦⑦⑨⑧❶⑩❁❷❊❸✪❹◆❺❶❻❤❼❾❽✏❿➁➀❍❷➂❽✏❻✘❹◆➃❙➄✴❷➂❽✼➀❍❻❏➅ ♥ ♣q❢ ➆➇➆ ❣➉➈◆➊✄➋✤➌ ➍➏➎✤➐➒➑➓➐❏➔❊→✤➐❃➣✍↔➙↕➛➎❍➜✆➝✪➑✼➜➞➐➟➎✒↔➙➠✲➡➤➢➇➑⑥➠✕➑✼↕➥➐✲➐❏➔➦↔❅➧➓➠➨➑✼➐➙➔➥➎✏➝➫➩❧➑✕➩❧➎❍➭➂➢➇➝➫➐➲➯✆➡❄↔❃➳☞→❍➢➙➢➵➯➫↕➤➎❍➐❁➸⑥➎✤➜❾➠➺→❍↕◆➯ ➠✕→❍➐➲➜❾↔❃➳✆➑⑥➧☞➣❞➻⑥➭➂➐❞➭✄➡❊➝✎→❍➐➟➑③➐❏➔❊➑➏➭➂↕➦➼✤↕❄➎✤➩s↕❊➧☞➣❞➎❍↕➤➑➞➳☞➎✤➠✲➡➥➎❍↕➤➑⑥↕◆➐✍→✤➐★→✕➐➲↔➙➠✕➑❾➣★→✎➳☞➳✆➎✤➜✬➝❍↔➙↕➦➽✒➐➒➎ ➾ ➪➚ ❝✬❡➶❢ ➆ ❣➘➹ ➌ ✈➪➚ ❝ ➆❡✁❢ ♠ ➪➚ ❝ ➆ ♣q❢ ♠➴➈➊ ➷➚ ➆ ⑦➮➬❏➱✎✃➉❐❶❣ ➹✎❒✼❮✼❮✏❮✦❰ Ï❁Ð❃Ñ❄Ð✭Ò ❼⑥Ó♦Ô➶Õ✘❿➁Ó➛❿➁➃➤❽✄❷➂❽✏❻✘❹◆➃ Ö❄×➁Ø➙Ù✔Ú➴Û✤Ü known values unknown values Ý➁Þ✪ß➱✎à❊á➤á➵â✆ã✼✃Þâ✆á➇➱✎ä ➪❝✬❡➶❢ ➆ ❣ ❢ ➊ ✈➪❝ ➆❡✁❢ ♠ ➪❝ ➆ ♣❁❢ ♠➛➈◆➊ ➷ ➆ ⑦ å✍æ✘å ç❙è❶é❦ê➦ê✤ë✎ì★í✔î✬ï✲í✔ð Ö❄×➁Ø➙Ù✔Ú➴Û❊Û ñ ➧☞➧❾➭➂➠➓↔➙↕➁➽➨➩❧➑➓→❍➜✬➑➏➭✄➡➥➝✪→❍➐➲↔➙↕➁➽ò➐❏➔❊➑✉➭➂↕➂➼❍↕➤➎❍➩s↕➥➧✉→✎➳✆➳☞➎✤➜✬➝❍↔➙↕➦➽ò➐➟➎➨➐❏➔❊➑✼↔➙➜✉↔➙↕❄➝✎➑✬ó ❐ ➣❧→❍➐❧➐❏➔❊➑➏➐➲↔➙➠➨➑ ➪❝✬❡✁❢ ➆ ↕❄➑☞➑☞➝ô➧✑➐➟➎õ➻☞➑④➳☞→❍➢➇➳✼➭➂➢➇→✤➐➒➑☞➝ô➣✉➩❧➑④→❍➢➵➜✬➑☞→✪➝❍➯❩➼❍↕➤➎❍➩ ➪❝✆❡✁❢ ➆ ♣q❢➤ö✻÷➔➥➑➫↔❃➝✪➑☞→✠➎✦➸ùø❤→✤➭➦➧☞➧☞ú➒ûq➑⑥↔❃➝✎➑⑥➢ ↔➙➐➟➑⑥➜✬→✤➐✘↔❃➎✤↕ù↔❅➧✉➐➟➎ò→❍➢➵➩❧→❍➯ô➧③➭➦➧✼➑✉➐❏➔❊➑➏➠➨➎❍➧❾➐❞➜✬➑☞➳☞➑✼↕➥➐➲➢ü➯✑➳✆➎✤➠✲➡➤➭➂➐➒➑☞➝✑ýô→✤➢ü➭➥➑ ö known values unknown values þ❷❊ÿ✁✂☎✄✝✆✔❿➦❻✟✞➶❿➦Õ❧❻❏❽✄❿➁➀ô❷❊❽✏❻❃❹❄➃❙✈ ß➱✪ä✡✠✬á☞☛➂ã✼✃✍✌➨➱✎✠✾â❤✃✬ã ßã✏ä✎â❤á➇â✬ã✏✃Þâ✬ã✄⑦ ➪❝✬❡✁❢ ➆ ❣ ❢ ➊ ✈➪❝ ➆❡✁❢ ♠ ➪✑✏✓✒ Ñ ➆ ♣q❢ ♠➴➈➥➊ ➷ ➆ ⑦ ✔
2 Matrix Form SLIDE 12 Split a L-U L: Lower triangular Au=f becomes (D-L-t)u=f Iterative (D-L)ur+l=Uur+f The above matri form assumes that we are updating through our unknowns in ascending order. If we were to update in reverse order, i.e., the last unknown firs Note 2 Updating order We see that, unlike in the jacobi method. the order in which the unkowns are updated in Gauss-Seidel changes the result of the iterative procedure. One could sweep through the unknowns in ascending, descending, or alternate orders. The dure is called symmetric Gauss-Seidel Another effective strategy, known as red-black Gauss-Seidel iteration, is to up date the even unknowns first(red) (n2+1+u2-1+h2f2) and then the odd components(black) The red-black Gauss-Seidel iteration is popular for parallel computation since he red (black) points only require the black (red) points and these can be updated in any order. The method readily extends to multiple dimensions. In r instance, the red and black points are shown below 排
✕✗✖☞✕✗✖✟✘ ✙✛✚✢✜☎✣✥✤✧✦✩★✫✪✑✣✥✬ ✭✯✮✱✰✳✲✫✴✶✵✸✷ ✹✻✺✢✼✾✽❀✿❂❁ ❁❄❃❆❅❈❇❊❉❊❇●❋ ❍■❏ ❅▲❑◆▼❖✽✾P✸◗✸❘✸❙✑P❚✼ ❉❂❑◆❯✗❘✥❱❳❲☎❨❳✿❩❨❬✽☞P❚❙✢◗✎❭✢✼☞P❚❨ ❋❪❑◆❫❴✺✡✺✑❲✂❨✍✿❬❨❩✽✾P✸❙✢◗✸❭✡✼✾P✸❨ ❁❊❵✶❃❜❛❞❝✯❲✂❡☎❘✸❢❣❲✂❤❥✐✟❅❈❇❊❉❊❇●❋❧❦✯❵✶❃❄❛ ♠✿❬❲✂❨❩P❚✿❬✽✾♥✸❲♦❢❣❲♣✿❬q✡❘✻r ✐s❅❈❇t❉❳❦✻❵✈✉❩✇②①✍❃❄❋③❵❳✉✈④✶❛ ⑤⑦⑥✢⑧❣⑨✸⑩❷❶❚❸❹⑧❻❺✓⑨✥❼❾❽✝❿➁➀❖➂♣❶❚❽✝❺➃⑨✥➄❷➄❷➅➆❺✓⑧♣➄➇❼✧⑥✢⑨❚❼➉➈✈⑧❣⑨❚❽❬⑧❧➅➋➊✡➌✸⑨❚❼s❿✳➍✻➎➏❼✧⑥✻❽❩❶✥➅✸➎❹⑥➐❶❚➅➆❽➑➅➆➍✻➒❚➍✯❶✥➈➓➍✡➄♦❿✳➍ ⑨❹➄☎➔❷⑧☎➍✯➌✥❿✳➍✻➎➐❶❚❽❬➌✸⑧☎❽☎→➏➣✧➂❪➈✈⑧➏➈✈⑧♣❽❬⑧✓❼↔❶↕➅➋➊✡➌✸⑨❚❼↔⑧➏❿✳➍●❽❬⑧☎❸❹⑧☎❽❷➄☎⑧➙❶✥❽❩➌✸⑧☎❽❷➛❂❿✟→✳⑧✂→❀➛❖❼✳⑥✡⑧✓➜❀⑨✥➄❷❼❖➅➆➍✻➒❚➍✯❶❚➈➓➍ ➝❽❷➄✝❼s➛➓❼✳⑥✡⑧❧❿✳❼➞⑧♣❽❩⑨✥❼❾❿✟❶✥➍➐❺✓⑨✥❼❾❽✝❿➁➀➟➈✈❶✥➅➆➜❀➌➟⑩❷⑧❩➔❷❶❚❺❣⑧❖➠❖➡✫➢ ❃➤✐✟❅❈❇➥❋➑❦✝➦ ① ❉ → ➧t➨➫➩✝➭➲➯ ➳❂➵❂➸➫➺✗➩➼➻✟➽②➾✩➨➆➚✸➸✁➭❚➚ ➪❲❻❤❬❲☎❲➑✿❩q✡P✥✿➋➶✑❭✢❙✡✼❀✽✾➹✸❲❧✽✾❙▲✿❩q✢❲❻➘✱P✸❡☎❘✸❝✢✽✗❢❣❲☎✿❬q✢❘➆r➫➶✯✿❬q✡❲➴❘✸❨❷r➆❲✂❨❴✽❀❙▲❱✍q✡✽✾❡❷q▲✿❩q✢❲➴❭✡❙✢➹✸❘✥❱✍❙✡❤❂P❚❨❩❲ ❭✢✺⑦r✢P✥✿❩❲✂r➑✽✾❙❪➷➇P✸❭✡❤❩❤➮➬➮✹✻❲☎✽☞r➆❲✂✼✎❡❷q✡P✸❙✢◗✸❲➋❤➫✿❬q✡❲✈❨❩❲✂❤❬❭✢✼➁✿✁❘❚➱➆✿❩q✢❲➉✽❀✿❬❲✂❨❩P❚✿❬✽✾♥✸❲✃✺✡❨❬❘➆❡♣❲➋r➆❭✢❨❩❲✸❐✁❒❖❙✡❲➉❡♣❘✎❭✢✼☞r ❤❬❱➉❲✂❲☎✺❻✿❬q✢❨❩❘✸❭✢◗✎q❪✿❬q✢❲❴❭✡❙✢➹✻❙✢❘✥❱✍❙✡❤❮✽✾❙➏P✸❤❩❡♣❲☎❙✑r➆✽❀❙✡◗✡➶✸r➆❲➋❤❬❡☎❲☎❙✡r✢✽❀❙✢◗✑➶✸❘✎❨✈P❚✼❀✿❬❲✂❨❬❙✡P❚✿❬❲❰❘✸❨❷r➆❲✂❨❩❤✂❐②Ï❰q✢❲ ✼☞P✥✿➼✿❩❲☎❨✍✺✢❨❩❘➆❡♣❲➋r➆❭✢❨❩❲♦✽☞❤✍❡☎P✸✼❀✼✾❲✂r➲❤❬Ð✱❢❣❢❣❲♣✿❩❨❬✽☞❡❧➷➇P❚❭✑❤❬❤➼➬➞✹➆❲☎✽☞r➆❲☎✼❾❐ Ñ❙✡❘❚✿❬q✡❲☎❨❴❲☎Ò✯❲➋❡✝✿❬✽✾♥✸❲❧❤➼✿❬❨❷P✥✿❩❲☎◗✎Ð✸➶➆➹✻❙✢❘✥❱✍❙↕P✸❤✍❨❩❲✂r✻➬↔❝✢✼☞P✸❡❷➹➙➷➇P✸❭✡❤❬❤➼➬➮✹✻❲☎✽☞r➆❲☎✼➫✽❀✿❬❲✂❨❩P❚✿❬✽✾❘✸❙✗➶✡✽✾❤❰✿❩❘✓❭✢✺➆➬ r✢P❚✿❬❲♦✿❬q✢❲➑❲✂♥✸❲✂❙➟❭✢❙✡➹✱❙✡❘✥❱✍❙✡❤❳Ó✡❨❷❤➮✿➴✐✟❨❬❲➋r✡❦ Ô✉❩✇②① Õ❩Ö ❃➃×Ø❥ÙÔ✉ Õ❩Ö✇②① ④ Ô✉ Õ❩Ö ➦ ① ④✶ÚÕ✃ÛÕ❩Ö↔Ü③Ý P❚❙✑r➏✿❩q✢❲☎❙➲✿❬q✡❲➑❘✻r✡r➲❡☎❘✸❢❣✺✯❘✸❙✢❲✂❙✎✿❷❤➑✐✧❝✢✼☞P✸❡❷➹✢❦ Ô✉❩✇②① Õ❩Ö✇②① ❃ × Ø ÙÔ✉❩✇②① Õ❩Ö✇②① ④ Ô✉❬✇②① Õ❬Ö ④✶ÚÕ✈ÛÕ❩Ö✇②① ÜßÞ Ï❰q✢❲❣❨❩❲✂r✻➬↔❝✢✼☞P✸❡❷➹à➷➇P❚❭✡❤❩❤➼➬➞✹✻❲✂✽✾r✢❲☎✼❮✽➁✿❩❲☎❨❷P✥✿❩✽❀❘✎❙➐✽☞❤➇✺✑❘✎✺✢❭✢✼☞P❚❨♦➱✧❘✸❨➇✺✡P✸❨❩P✸✼❀✼✾❲☎✼➓❡♣❘✎❢❣✺✢❭➆✿❩P❚✿❬✽✾❘✸❙t❤➼✽✾❙✡❡♣❲ ✿❬q✡❲➐❨❩❲✂r➤✐✧❝✡✼✾P✎❡❷➹➆❦✓✺✑❘✎✽❀❙✱✿❩❤➟❘✸❙✡✼❀Ðß❨❬❲➋á✱❭✢✽❀❨❩❲▲✿❩q✢❲➐❝✢✼☞P✸❡❷➹â✐✧❨❩❲✂r✑❦✓✺✯❘✸✽✾❙✎✿❷❤➙P✸❙✡r✩✿❬q✡❲✂❤❬❲➐❡☎P✸❙ã❝✑❲ ❭✢✺⑦r✢P✥✿❩❲✂r▲✽✾❙àP❚❙✻Ð➲❘✸❨❷r➆❲☎❨➋❐❰Ï❰q✢❲➴❢❣❲♣✿❩q✢❘➆r▲❨❩❲✂P✸r✢✽❀✼✾Ð➙❲☎ä✱✿❩❲☎❙✡r✡❤✍✿❬❘➙❢➴❭✢✼❀✿❬✽✾✺✢✼✾❲❻r➆✽✾❢❣❲☎❙✡❤❬✽❀❘✎❙✡❤✂❐ ♠❙ Ø▼❻➶✻➱✧❘✸❨✍✽✾❙✡❤➼✿❩P✸❙✡❡♣❲✎➶➆✿❬q✢❲➑❨❩❲✂r➲P❚❙✑r➙❝✢✼☞P✸❡❷➹➙✺✑❘✎✽❀❙✱✿❩❤❂P❚❨❩❲♦❤❬q✢❘✥❱✍❙➲❝✑❲✂✼❀❘✥❱➑❐ Red Black ✭✯✮✱✰✳✲✫✴✶✵✸å æ
u+I =(D-L)-Uu+(D-l)-if =R RGs=(D-L)-U: Gauss-Seidel Iteration Matix 2.3 Error Equation SLIDE 1 For an approximate solution u, we define Iteration Error Residual: rr=f sabt from both sides of Au=f, ERROR EQUATION→Aer=y We note that, whereas the iteration error is not an acessible quantity, since it requires u, the residual is easiy computable and only requires Note 3 Relationship betwe d residual We have seen that the residual is easily computable and i e sense it sures the amount by which our approximate solution u' Iin some to satisfy the iginal problem It is clear that if r=0, we have e=0. However, it is not always the case that all in We have that A u=f and A-r=e. Taking norms, We have f|l2≤‖4242 el2 rl2 Combining these two expressions, we have lell ond (a) From here we see that if our matrix is not well conditioned, i.e., cond(A)is large, then small residuals can correspond to significant errors
ç➉è❩é②êìë ísî❈ïtð❳ñ❷ò➫ê✂ó③ç➉è✈ôõí✟î❈ï❊ð➉ñ❷ò✗ê➓ö çè❬é②ê ëõ÷❖ø✫ù❰çè ôõí✟î❥ïtð❳ñ ò✗ê ö ÷ø✗ù ë✛ísîúï❊ð➉ñ✝ò➫ê✂óüû➉ý➲þ✡ÿ✁✂☎✄☎✆✞✝✠✟☛✡✁✝✠☞✍✌☎✎✏✝✒✑✥þ✓✎✏✟☛✔✖✕✘✗✛þ✙✎✏✟✛✚ ✜✣✢☛✤ ✥✧✦✙✦✙★✩✦✪✥✬✫✮✭✰✯✲✱✓✳✴★✍✵ ✶ ✷✒✸✺✹✼✻✪✽✿✾ ❀✞❁❃❂ ç✘❄❁❅❂❇❆✙❁❉❈✴❊●❋✓❂■❍❏❊▲❑▼❊❖◆◗P ç✶ëõö❙❘ ❚✙❊●❯❲❱❖❑✧❱❖❳✙❳❨❯■❊❬❩✓❍❏❭❪❱❖❂■❁❅❈✴❊●❫❴❋✙❂■❍❏❊▲❑ ç➉è✿❵✙❛❁❝❜✓❁☎❞✖❑✙❁ ❡❣❢✐❤☎❥❇❦✿❢♠❧♦♥✿♣✧q✣❥❣❥■♥✿❥ û r✢è❂ëãç●ï ç✈è st❤❣✉❣❧♦✈❖✇❨❦✿① û ②✑è❂ë❄ö ï P ç➉è ③✇❨④❃❢♠❥■❦▲⑤❃❢☛❧✺♣✠⑥❉P çè❲⑦❥■♥✿⑧⑨④⑩♥✿❢✛❶▼✉❣❧♦✈●❤❣✉❷♥⑦ P ç③ë❄ö❹❸ P ç ïP ç✍❺➴ë❜ö ï P ç✍❺ ❻✍❼❲❼❲❽❾❼❿❻✮➀❾➁t➂➄➃✣➅■❽❾➆➈➇ P r✢è❂ë➉②✡è ➆t➊ ➋✬❤❪♣➌♥❖❢➍❤❪❢✛❶✙❦❖❢❸❙➎❶❨❤☎❥■❤⑩❦✿✉➏❢✛❶✙❤❪❧✺❢✐❤❃❥■❦✿❢♠❧♦♥✿♣➐❤❃❥❣❥■♥✿❥➏❧➑✉❪♣➌♥✿❢✰❦❖♣➐❦▲⑤⑩❤☎✉❇✉❣❧♦④❃①❴❤▼➒☎✇❨❦❖♣❨❢♠❧✺❢☛➓❸ ✉❣❧✺♣➌⑤⑩❤❪❧✺❢ ❥■❤⑩➒❃✇✓❧✺❥■❤❣✉ ç❲❸ ❢✛❶✙❤❷❥■❤☎✉❣❧♦✈✿✇❨❦✿①✁❧➑✉❷❤❇❦✿✉❣❧✺①➔➓→⑤⑩♥✿⑧✰➣➌✇✓❢✐❦▲④❃①❴❤➏❦✿♣➌✈▼♥✿♣✖①➔➓↔❥■❤⑩➒❃✇✓❧✺❥■❤❣✉ ç➉è✒↕ ➙➜➛➞➝❣➟✬➠ ➡✬➟❖➢☛➤➞➝■➥✐➛✓➦✁➧✂➨✲➥➑➩➭➫◗➟✙➝❇➯❝➟✒➟❖➦❿➟❖➲❬➲●➛✠➲➳➤✙➦✩➵➐➲●➟❖➧✏➥➸➵➄➺➌➤✓➢■➻ ➼➜❁❉❆❨❱❬➽▲❁❉❈■❁❃❁✏❑✧❂■❆❨❱❖❂❲❂■❆❨❁❉❯■❁✂❈✴❍➑❜✓❋❨❱▲❫✞❍➑❈❲❁✏❱●❈✴❍❏❫❏➾▼➚❃❊▲❭❪❳✙❋✓❂⑩❱❄❫❏❁❉❱❖❑❨❜✧❍❏❑➪❈■❊▲❭❪❁❷❈■❁❃❑❨❈■❁❝❍➶❂❾❭❪❁✏❱✿➹ ❈■❋✙❯■❁✂❈↔❂❇❆✙❁➘❱▲❭➏❊●❋✙❑✒❂ ❄➾ ❛❆❨❍❏➚⑩❆➉❊●❋✙❯→❱▲❳✙❳✙❯❇❊❬❩✓❍❴❭↔❱✿❂❇❁➪❈✴❊●❫❴❋✙❂■❍❏❊▲❑ ç➉è ◆♦❱❖❍❏❫❏❈➳❂■❊➐❈❇❱✿❂❇❍❏❈✴◆✛➾➴❂■❆✙❁ ❊▲❯❇❍❏➷▲❍❏❑❨❱❖❫➬❳✙❯❇❊❄❫❏❁❃❭❘ ➅➍❂❙❍❏❈❙➚❃❫❴❁✂❱❖❯✣❂❇❆❨❱✿❂❙❍❴◆ ②➙ë➱➮✞❵✓❛❁❅❆❨❱❬➽▲❁ r➏ë✃➮✞❘✩❐❊❛❁❃➽▲❁✏❯ ❵ ❍❴❂❙❍❏❈✣❑✙❊▲❂✰❱❖❫❛❱❬➾✓❈✍❂■❆✙❁❝➚✏❱▲❈■❁t❂❇❆❨❱✿❂ ❛❆✙❁✏❑ ② ❍➑❈❙❈✴❭↔❱▲❫❴❫➞❍❏❑✧❑✙❊▲❯❇❭❵✙r ❍➑❈❲❱▲❫❏❈■❊➏❈■❭↔❱❖❫❏❫➞❍❴❑✧❑✙❊●❯■❭❘ ➼➜❁❝❆❨❱❬➽▲❁t❂■❆❨❱❖❂✰P ç③ë❄ö ❱▲❑❨❜→Pò➫ê☎②➙ë➉r➞❘ ➃✲❱❖❒✠❍❏❑✙➷❪❑✙❊▲❯❇❭↔❈ ❵✓❛❁❅❆❨❱❬➽▲❁ ❮❃❰➄❮❃Ï❾ÐÑ❮ P ❮☎Ï❲❮☎Ò◗❮❃Ï✿Ó ❮☎Ô✓❮☎Ï❾Ð❿❮ Pò✗ê ❮☎Ï❲❮☎Õ✙❮☎Ï❪Ö ×❊▲❭❄❍❏❑✙❍❴❑❨➷Ø❂❇❆✙❁✏❈■❁❾❂❛❊❪❁❃❩✠❳❨❯■❁✂❈■❈■❍❴❊●❑❨❈ ❵✒❛❁❅❆❨❱❬➽▲❁ ❮☎Ô✓❮☎Ï ❮❣Ò➄❮☎Ï ÐÑ❮ P ❮ Ï ❮ Pò➫ê ❮ Ï Ù Ú☎Û Ü Ý✐Þ■ß✏à➄á❴â➞ã ❮❣Õ✙❮☎Ï ❮❃❰➄❮☎Ï Ö ❚✙❯❇❊▲❭ä❆✙❁✏❯■❁ ❛❁→❈■❁❃❁å❂■❆❨❱❖❂Ø❍❴◆✰❊▲❋✙❯Ø❭↔❱✿❂■❯❇❍❴❩➜❍➑❈❷❑❨❊❖❂ ❛❁❃❫❏❫❹➚❃❊▲❑❨❜✙❍➶❂❇❍❴❊●❑✙❁✏❜ ❵ ❍ ❘ ❁ ❘❏❵ ➚☎❊▲❑✖❜ íPñ ❍❏❈ ❫➑❱❖❯❇➷▲❁ ❵ ❂❇❆✙❁❃❑✬❈■❭❪❱▲❫❴❫➞❯❇❁✏❈■❍➑❜✓❋❨❱❖❫➑❈❙➚❃❱▲❑▼➚❃❊▲❯❇❯■❁✂❈✴❳➌❊▲❑✖❜↔❂■❊↔❈■❍❴➷●❑✙❍❴❞✖➚❃❱▲❑●❂❙❁✏❯■❯❇❊▲❯⑩❈ ❘ æ
2.3.1 Jacobi D-(L+U)u+D-f D-(L +U)u+D-f subtracting I(L+u)er 2.3 Gauss-Seidel er+I=(d-dUe=reser It is clear that the above equations satisfied by the error are not useful for prac- tical purposes since eo =u-u, will not be known before the problem is solved We will see however, that by studying the equation satisfied by the error we can determine useful properties regarding the convergence of our schemes candLes 2.4.1 Jacobi SLIDE 1 (0)=(1)=0; u0=0 2.4.2 Gauss-Seidel LIDE 18 0
ç✞è❏é✼è♦ê ë✞ì✙í●î❨ï◗ð ñ➌ò✒ó✺ô✼õ✪ö▲÷ ø✮ù■ú✲ûýü þ✧ÿ✞û✁✄✂✆☎✞✝✠✟➌ø✮ù✡☎ þ✬ÿ➞û☞☛ ø ü þ✧ÿ✞û✁✄✂✆☎✞✝✠✟➌ø✌☎➐þ✧ÿ✞û☞☛ ✍✏✎✒✑✔✓✏✕✗✖✙✘☞✓✏✚✜✛✒✢ ✣✙ù❇ú✁û❙ü✘þ ÿ➞û ✄✂✤☎✥✝✠✟ ✦ ✧✩★ ✪ ✫✭✬ ✣✙ù✰ü✯✮✱✰✡✣✙ù ç✞è❏é✼è➑ç ✲▼ì✒✳✵✴✶✴☞✷☞✸✺✹✠ð✄✻✵✹✽✼ ñ➌ò✒ó✺ô✼õ✪ö✙✾ ✿ ✚✜❀❁✚❃❂❄✖❅✕❆❂❃❇❉❈ ✣✙ù❇ú✁û✣ü❊☛þ●❋✆✂❍✟ ÿ➞û ✝ ✦ ✧☞★ ✪ ✫✺■❑❏ ✣✙ù✰ü▲✮✱▼❖◆❍✣❨ù P✩◗❙❘❄❚❱❯❳❲❃❨✗❩✁❬❭◗❫❪❴❩✁◗❵◗❛❪✒❨❱❩❉❜✗❝✁❞✁❨❡❨✗❢☞❣❴❩❅◗❤❘✄❝❅✐✒❚❭❚❳❩✁◗❥❘❄❚❫❦❍❨✗❧♠❜☞♥♦◗❫❪❴❨❡❨❳❬✩❬✏❝✁❬✠❩✁❬❆❨♣✐q❝❅◗❵❣✽❚❳❨✄r✗❣✔❲✁r☞❝✁❬✡sq❬❆❩✙❯❳t ◗❥❘✄❯❆❩❅❲❉sq❣✔❬❥s❴❝✉❚❳❨✩❚✈❚✗❘❫✐✇❯✗❨ ✣✔①tü➉ø②❋▼ø❵①✙③✵④❘❫❲❫❲✭✐✇❝✁◗✡❜✗❨⑥⑤✁✐✇❝④✐⑦❜✗❨✄r☞❝❅❬✏❨♣◗❛❪✒❨⑧s✇❬✏❝✙❜❳❲❃❨❳⑨⑩❘❄❚⑥❚❳❝✁❲❶❞✉❨✗❧✙❷ ❸❹❨ ④❘❫❲❫❲✭❚❳❨✗❨✈❪✒❝④❨☞❞✁❨☞❬③ ◗❫❪❴❩✁◗⑧❜❳♥♦❚✗◗❥❣❴❧✁♥✁❘❫✐✽❺❁◗❛❪✒❨❡❨✗❢❳❣❴❩✁◗❥❘✄❝✁✐❹❚❳❩❅◗❤❘❄❚❛❦⑧❨✗❧♠❜❳♥❁◗❫❪❴❨❡❨❳❬✩❬✏❝✁❬ ④❨❡❯✗❩✁✐ ❧✙❨❳◗❻❨☞❬✩⑨♦❘❫✐q❨❡❣✽❚❳❨✄r✗❣✔❲✽s✇❬✏❝❆s❴❨❳❬✩◗❤❘✄❨☞❚❱❬✏❨❼❺❉❩❅❬✏❧✁❘❫✐✽❺❽◗❛❪✒❨♦❯✗❝✁✐❾❞✉❨❳❬❤❺❑❨☞✐✇❯❆❨♦❝❿r➀❝✁❣✔❬❭❚❳❯❆❪❴❨☞⑨♠❨✩❚❳❷ ➁➃➂❛➄ ➅②➆➈➇➊➉➌➋❭➍❿➎❖➏ ç✞è❃➐✁è♦ê ë✞ì✙í●î❨ï◗ð ñ➌ò✒ó✺ô✼õ✪ö❑➑ ❋➈➒✇➓➔➓❝ü➣→ ➒➊✄↔❑✟✩ü↕➒➊❿→✉✟➄ü✯↔❴➙ ø① ü✯➛ 0.3 0.2 0.1 0 # Iterations log(||e|| L2 ) n=10 n=20 n=40 0 20 40 60 80 100 120 140 160 180 ç✞è❃➐✁è➑ç ✲▼ì✒✳✵✴✶✴☞✷☞✸✺✹✠ð✄✻✵✹✽✼ ñ➌ò✒ó✺ô✼õ✪ö✙➜ ❋➈➒✇➓➔➓❝ü➣→ ➒➊✄↔❑✟✩ü↕➒➊❿→✉✟➄ü✯↔❴➙ ø① ü✯➛ ➝
2. 4.3 Observations The number of iterations required to obtain a cer tain level of convergence O(72) Gauss-Seidel is about twice as fast as jacobi Whu? 3 Convergence Analysis e= re=rrer The iterative method will converge if mF=0→p(R)=max|(r)<1 T→0 P(R)is the spectral radius The spectral radius is the radius of the smallest circle centered at the origin that contains all the eigenvalues. The above condition indi cates that the nec conditions, is that the largest eienvalue, in modulus, lies within the unit circle p() The condition that if and only if P(r)<1
0.3 0.2 0.1 0 # Iterations log(||e|| L2 ) n=10 n=20 n=40 0 10 20 30 40 50 60 70 80 90 ➞✺➟❃➠➡➟✜➢ ➤♠➥✵➦✶➧❑➨✶➩✒➫✒➭➔➯✄➲q➳✵➦ ➵q➸❑➺❫➻❖➼✞➽✙➾ ➚↕➪➃➶❴➹✈➘✽➴✒➷❡➬q➹❳➮❍➱❅✃✺❐❃❒✏➹➔➮❆❮❅❒✏❐✜➱✙➘❴❰⑧➮❆➹➔Ï❑➴✒❐✜➮✏➹✶Ð♦❒✏➱❡➱❉➬✔❒❆❮✙❐❃➘Ñ❮❱Ò☞➹➔➮Ó❒✗❮❅❐✜➘❽Ô❃➹➔Õ✙➹➔Ô❴➱❅✃✵Ò☞➱✙➘✽Õ❉➹❳➮❆Ö✙➹❳➘❾Ò☞➹ ❐❄❰✈×❁Ø✄Ù✺Ú✶Û☞Ü ➚✯Ý♣❮✙➴❴❰❆❰❿Þ❿ß✽➹❳❐❄Ð✔➹➔Ô✭❐✜❰⑥❮✙➬❾➱❉➴✔❒➃❒❿à➈❐✜Ò❳➹❱❮✙❰❍✃✄❮❉❰❿❒⑥❮✙❰➈á❑❮✙Ò❳➱✙➬✒❐❥Ü â❽ã✽ä✔å æ ç●è➀é❁ê♦ë⑥ì❙í❡ë✈éïî➈ëñðòéïó❱ô☞õ÷ö➊ø☞ö ➵q➸❑➺❫➻❖➼✆ù✔ú û✒ü✈ý✯þ✞û✒ü❳ÿ✁➈ý↕þ✞þ✞û❴ü☞ÿ Ú ý✄✂☎✂✆✂❑ý▲þ❭ü➊û✞✝✠✟ ➪➃➶✒➹♣❐❃❒✏➹❳➮✗❮✁❒❆❐❃Õ❉➹♣➷♦➹❳❒✏➶✒➱✔Ð②à➈❐✜Ô❃Ô❖Ò❳➱✙➘✽Õ✙➹➔➮✏Ö❉➹✈❐❃✃ Ô✜❐❃➷ ü☛✡✌☞ þ♣ü✈ý✎✍✑✏✓✒✕✔ ØþÛ ý ➷❁❮✗✖✙✘ ✚❖ØþÛ☎✘✞✛✢✜ ✟ ✣✥✤ ✔ ØþÛ⑧❐✜❰➃❒❆➶✒➹❱❰✧✦❾➹✶Ò✩❒✏➮✗❮❅Ô✭➮✗❮✙Ð✒❐❃➴❴❰➔Ü ★✇ã✪✩✬✫✮✭✪✩☛✯☎✰✲✱✧✳✗✴✵✱✧✳✷✶✗✸✺✹✻✫✼✸✽✫✾✰❛ã✪✩✬✱✧✳✷✶✗✸✺✹✻✫❀✿❂❁✾✰❛ã✪✩✾✫❄❃✠✳❅✴✺✴❆✩❇✫❄✰✓✯☎✸✺✱✧✯☎✴❆✩❈✯❉✩☎❊❋✰●✩☎✱✧✩☛✶❍✳❅✰■✰❫ã❋✩❏✿✗✱❄✸▲❑✗✸✺❊ ✰❛ã✪✳❅✰✌✯☛✿❅❊▼✰◆✳✗✸✺❊✪✫❖✳✗✴✺✴P✰❛ã✪✩✾✩☎✸▲❑◗✩☎❊❋❘❅✳❅✴❙✹❋✩❇✫☎❚✢★✇ã❋✩✼✳✷❯☛✿❅❘❅✩✼✯☛✿❅❊❱✶✗✸✺✰✲✸❲✿✗❊❳✸✺❊❱✶❅✸❲✯☛✳✗✰◆✩❇✫❨✰❛ã✪✳❅✰✙✰❛ã✪✩❖❊❱✩☛✯☎❩ ✩❇✫❉✫☎✳✗✱✩ä✼✳✗❊❱✶❬✫❄✹❇❭❳✯❇✸❲✩☎❊❋✰❪✯❉✿✗❊❱✶✗✸✺✰✲✸❲✿✗❊❨❁❇✿❅✱✓✰❛ã✪✩✓✫☎✯✗ã✪✩☎❃✓✩❫✰◆✿✼✯☛✿✗❊❋❘❅✩❇✱✲❑❴✩❇❵❛❁❇✿❅✱❫✳❅✱☎❯☎✸✺✰✮✱✧✳❅✱✩ä✾✸✺❊❋✰✮✸❲✳❅✴ ✯☛✿❅❊❜✶❅✸✺✰✮✸❲✿❅❊✪✫☛❵❝✸✽✫❞✰❛ã✪✳✗✰P✰❛ã✪✩❡✴❆✳❅✱✮❑◗✩❇✫❄✰❢✩☎✸❲✩❇❊▼❘❣✳✗✴❙✹❋✩❇❵❝✸✺❊❀❃✠✿✆✶✗✹✞✴❙✹✻✫☛❵❤✴❙✸❲✩❇✫✙✐❥✸✺✰❛ã✻✸✺❊❈✰❛ã✪✩❡✹✞❊❋✸✺✰❦✯☎✸✺✱✧✯☎✴❆✩❧❚ ♠❈♥✁♦❄♣❬q r❡♥✻s❝t✁✉✈♦✈✉❂♥✻s✇♥✞s ✔ ØþÛ ➪➃➶✒➹✠Ò☞➱❉➘❴Ð✔❐❃❒✏❐✜➱✙➘②❒✏➶❾❮✁❒ Ô❃❐✜➷ ü❉✡❡☞ þü ý✇✍ ❐❃✃➊❮✙➘❴Ð÷➱❉➘✒Ô②①÷❐❃✃ ✔ ØþÛ❦✛✢✜ ③
can be easily shown for the case where R is diagonalizable. In this case R XAX, where A is the diagonal matrix of eigenvectors. We have that R X-A X and hence we require that which is equivalent to p(r)∑ laiil for all i If the matrix A is symmetric positive definite then Gauss-Seidel iteration converges for any initial solution Note 5 Convergence of Jacobi iteration for diagonally dominant matrices For the Jacobi iteration, RJ=D(L+U), it can be easily seen that R has zero diagonal entries. It can be shown(Gershgorin Theorem-see G Vl that a matrix with zeros in the main diagonal, p(Rj)<Rjlloo. Hence B)=≤B==41 the last inequality follows form the diagonal dominance of A Convergence of Gauss-Seidel for SPD matrices (See Theorem 10.1.2 of GVL
④☎⑤✷⑥❏⑦❱⑧✠⑧✆⑤◗⑨✈⑩②❶②❷❏⑨✧❸✪❹❅❺✵⑥❀❻❼❹◗❽✙❾✧❸✪⑧❫④✆⑤✷⑨✧⑧✓❺✵❸✪⑧☎❽❉⑧❫❿➀⑩✽⑨✌➁✞⑩✽⑤✗➂✷❹◗⑥❋⑤✗❶②⑩②➃✆⑤✗⑦❋❶❆⑧◗➄➆➅●⑥❈❾❉❸✪⑩②⑨❡④☎⑤✷⑨✧⑧✠❿➈➇ ➉➋➊➍➌➏➎✬➉❍➐ ❺✵❸✪⑧✆❽✧⑧ ➎ ⑩②⑨➑❾✧❸✪⑧➆➁✞⑩✽⑤✗➂✷❹◗⑥❋⑤✗❶➓➒✓⑤✗❾✧❽❉⑩▲➔✾❹✗❻❥⑧✆⑩❆➂◗⑧☎⑥✻→✷⑧❧④❄❾✧❹◗❽❉⑨✆➄❦➣❏⑧■❸❋⑤❣→✷⑧✙❾❉❸❋⑤❅❾✙❿❪↔✙➇ ➉➋➊➍➌↕➎↔ ➉ ⑤✗⑥❋➁❬❸✪⑧✆⑥❋④❇⑧❞❺❦⑧✙❽✧⑧❧➙◗➛❋⑩❆❽❉⑧✥❾❉❸❋⑤❅❾ ❶②⑩❆➒ ↔☛➜✌➝ ➎↔ ➇➟➞ ❺✵❸✪⑩✽④☛❸❖⑩✽⑨✵⑧❧➙◗➛❋⑩❆→❅⑤✗❶②⑧☎⑥❴❾❢❾✧❹✠➠❜➡❲❿❞➢❦➤➦➥✷➄ ➧❢➨✈➩ ➫❈➭➑➯➍➲❤➳❋➯➓➵✑➸ ➺❱➻❴➼✺➽➓➾❈➚✁➪ ➶ ➅◆❻➹❾✧❸✪⑧✾➒✠⑤❅❾❉❽✧⑩❆➔❍➘➴⑩②⑨❖➷❄➬✲➮❄➱❲✃☎➬✮❐❙❒❨❮❅➱❲❰✆Ï◗Ð✗Ñ❱❰❅❐✺❐▲❒✾❮◗Ð❅Ò➆➱✺Ñ❱❰❅Ñ▼➬❡❾❉❸✪⑧☎⑥❳Ó❴⑤✷④❇❹◗⑦✪⑩❢⑤✗⑥❋➁ÕÔ✙⑤✗➛❋⑨❉⑨❂Ö × ⑧☎⑩✽➁✞⑧☎❶✻⑩❆❾✧⑧☎❽☛⑤❅❾❉⑩❆❹◗⑥❋⑨➓④☎❹✷⑥✻→✷⑧✆❽✧➂◗⑧❥⑨❂❾☛⑤✗❽✧❾✧⑩②⑥✪➂✵❻❼❽❉❹✷➒Ø⑤✗⑥❡⑤✷❽✧⑦❋⑩▲❾❉❽❉⑤✷❽✧❷➑⑩②⑥✪⑩❆❾✧⑩✽⑤✗❶✞④❇❹◗⑥❋➁✞⑩❆❾✧⑩②❹✷⑥➍➄ Ù❪Ú ➘➦➇✢Û❣Ü❴Ý❇Þ✗ß❞⑩②⑨✥⑨❂❾❉❽✧⑩✽④❄❾❉❶❆❷❨➁✪⑩②⑤✷➂✷❹✷⑥▼⑤✗❶②❶❆❷❫➁✞❹◗➒✓⑩❆⑥❋⑤✷⑥❴❾➑⑩▲❻ à ÜÝ☎Þ à✻áãâä Þ✧å ➌ à ÜÝ❇Þ à ❻❼❹✷❽➑⑤✷❶❆❶✁æ☛ç ➶ ➅◆❻↕❾✧❸❋⑧❞➒✓⑤✗❾✧❽❉⑩▲➔❨➘è⑩✽⑨✵⑨✧❷❴➒✓➒✓⑧❇❾❉❽✧⑩✽④❪é▼❹❴⑨✈⑩❆❾✧⑩②→✷⑧❞➁✞⑧☎ê❋⑥✪⑩❆❾✧⑧✙❾❉❸✪⑧☎⑥✼Ô✙⑤✗➛❋⑨❉⑨✈Ö × ⑧✆⑩②➁✪⑧☎❶✁⑩❆❾✧⑧☎❽☛⑤❅❾❉⑩❆❹◗⑥ ④☎❹✷⑥✻→✷⑧✆❽✧➂◗⑧✆⑨❝❻❼❹✷❽➑⑤✷⑥❴❷❨⑩❆⑥✪⑩❆❾✧⑩✽⑤✗❶❛⑨✈❹◗❶❆➛✞❾❉⑩❆❹◗⑥➍➄ Ù➹ë ì❈í✁î❄ï✬ð ñ❡í✻ò❥ó✪ï✗ô✆õ❛ï✗ò❤ö◗ï✬í✪÷❢ø➍ù❱ö✷í✁ú▼û✵û✧î❄ï✗ô❅ù✁î✈û❂í✻ò➟÷✈í✞ô✾ü❜û✮ù✻õ❛í✻ò➏ù✞ý❲ý✺þ✇ü↕í✻ÿ❍û✲ò↕ù✪ò❥î ÿù✁î✧ô❣û●ö✷ï✁ ✂❹◗❽✙❾✧❸✪⑧❖Ó◗⑤◗④❇❹✷⑦❋⑩↕⑩❆❾✧⑧✆❽❉⑤✗❾✧⑩②❹✷⑥ ➐ ❿☎✄❖➇✝✆ ➊✁➌ ➡✟✞✡✠☞☛✌➢ ➐ ⑩❆❾■④✆⑤✗⑥❈⑦▼⑧❫⑧❧⑤✷⑨✧⑩❆❶②❷❀⑨✧⑧☎⑧✆⑥❏❾❉❸❋⑤❅❾❡❿➈❸❋⑤✷⑨ ➃☎⑧✆❽✧❹✓➁✞⑩✽⑤✗➂◗❹✷⑥❋⑤✷❶▼⑧✆⑥◗❾❉❽✧⑩②⑧✆⑨✆➄➏➅◆❾➑④☎⑤✗⑥❬⑦❱⑧✙⑨✧❸✪❹❅❺✵⑥ ➡✲Ô❪⑧✆❽❉⑨✧❸✪➂✷❹◗❽✧⑩②⑥✍✌❢❸✪⑧✆❹✷❽❉⑧☎➒✑Ö❝⑨✧⑧☎⑧✌Ô✏✎✒✑↕➢❝❾✧❸❋⑤✗❾✵⑤ ➒✠⑤❅❾❉❽✧⑩❆➔❨❺✵⑩❆❾✧❸✾➃☎⑧✆❽✧❹❴⑨P⑩②⑥❬❾✧❸✪⑧❞➒✠⑤✷⑩❆⑥✼➁✞⑩✽⑤✗➂◗❹✷⑥❋⑤✷❶ ➐ ➠❜➡❲❿✄ ➢✔✓✖✕❇❿✄ ✕ ➝ ➄✘✗➑⑧☎⑥▼④❇⑧ ➠❱➡✲❿✄ ➢❝➇✙✕❇❿✄ ✕✛✚✜✓✢✕❇❿✄ ✕ ➝ ➇ ➒✓⑤✗➔ ➌✤✣ Þ ✣ â ✥✦ â ✧✩★ ✦✫✪✧✩★ ✬ ✬ ✬ ✬ Ü✻Ý❇Þ Ü✻Ý❧Ý ✬ ✬ ✬ ✬ ➤✇➥✮✭ ❾✧❸❋⑧❞❶②⑤◗⑨❂❾✵⑩②⑥✪⑧✆➙❴➛❋⑤✷❶❆⑩❆❾❂❷✠❻❼❹✷❶②❶②❹❅❺➑⑨❦❻❼❹✷❽❉➒➀❾✧❸✪⑧✌➁✪⑩②⑤✷➂✷❹✷⑥▼⑤✗❶✁➁✞❹✷➒✓⑩②⑥❋⑤✗⑥▼④❇⑧✙❹✗❻❥➘✌➄ ì❈í✁î❄ï✰✯ ñ❡í✞ò❥ó✞ï✗ô❧õ➓ï✗ò❝ö✷ï❏í✞÷✲✱✠ù✴✳✁✵✁✵✶✸✷ï✗û●ü↕ï✗ý❦÷✈í✞ô ✷✺✹✲✻ ÿù✁î✈ô❣û❂ö✷ï✁ ➡ × ⑧☎⑧✼✌❢❸✪⑧✆❹✷❽❉⑧☎➒ ➥✆➞❋➄❆➥◗➄ ✽❡❹✗❻❤Ô✏✎✒✑↕➢ ✾
