A comparison between some iterative methods to solve linear equation systems. We’ll compare 3 different methods: Jacobi, Gauss-Seidel and the Conjugate Gradient method.
First the Jacobi and Gauss-Seidel methods are compared using an example from some lecture notes originating from the University of Oxford (linAlg34.pdf). Among other things it describes the Jacobi and Gauss-Seidel methods, and contain a detailed comparison of the two. That comparison is in part reproduced here using ojAlgo implementations.
Further the Gauss-Seidel solver is compared to the Conjugate Gradient solver using a small example from Hestenes and Steifel’s original paper from 1952.
Example Code
Console Output
class IterativeSolverComparison
ojAlgo
2022-05-21
Simple 3x3 example from linAlg34.pdf
Jacobi
1: 1.0 – { 2.0, 2.8, 3.375 }
2: 0.6587653717103008 – { -1.9312500000000004, 5.35, 2.825 }
3: 0.6507279468265461 – { -2.79375, 2.771249999999999, 0.8859374999999998 }
4: 0.4478723986426338 – { -0.05007812499999931, 1.4781249999999997, 1.6373437500000003 }
5: 0.42967887797702453 – { 0.032929687499999805, 3.4248906250000006, 2.8081835937500004 }
6: 0.307898711170057 – { -1.8185830078125007, 3.94303125, 2.0988984374999995 }
7: 0.2798535778539219 – { -1.5456894531249998, 2.5484095703125, 1.441717529296875 }
8: 0.2139720018620591 – { -0.355492932128906, 2.44927333984375, 2.0329240478515627 }
9: 0.1805602289202561 – { -0.7493297058105468, 3.3998738598632814, 2.367649264526367 }
10: 0.14897424162803904 – { -1.475673878326416, 3.297461882324219, 1.9127148760986326 }
11: 0.11603973088223084 – { -1.083267098236084, 2.6796816234436034, 1.769533324546814 }
12: 0.10316556905352284 – { -0.6669908051319122, 2.8578530708770753, 2.0993026166496276 }
13: 0.07485387969214365 – { -1.0034034979257587, 3.239526563580703, 2.1365573971381187 }
14: 0.0707042489447668 – { -1.2221813296439403, 3.0525808600997926, 1.9093266641757967 }
15: 0.04888359824752583 – { -0.9582854281817437, 2.830421867883955, 1.924736845051593 }
16: 0.047816541976573264 – { -0.8587635677306722, 2.994923481111591, 2.0740204424980813 }
17: 0.03253336266057797 – { -1.0529770724293563, 3.1143500363608294, 2.0372128026504854 }
18: 0.03187337243077582 – { -1.085084620168279, 2.9830988776025804, 1.9438744682573499 }
19: 0.022099352786836786 – { -0.9494552899943025, 2.9264990152019728, 1.985066765856963 }
20: 0.020948869490930108 – { -0.9520495819937087, 3.024353532346204, 2.0401990468006845 }
21: 0.01525492142763488 – { -1.0423260512736154, 3.0448498695240485, 2.0028550298717462 }
22: 0.013603262007164111 – { -1.024566207165834, 2.9757463811845293, 1.9725997861100781 }
23: 0.01061540513180879 – { -0.9673230301748232, 2.9743001901445307, 2.0029535552643427 }
24: 0.008761536602685693 – { -0.9893652615205222, 3.0207876040008435, 2.017806671152095 }
25: 0.007384533622206288 – { -1.023748805364493, 3.0135035115485245, 1.9948633331195533 }
26: 0.005631808593098403 – { -1.0028992556139271, 2.9836960500291254, 1.9889989818281801 }
27: 0.0051012580240613024 – { -0.9835972613856978, 2.993860039362916, 2.005389167335596 }
28: 0.0036422231814439896 – { -1.0009718951831552, 3.0119973101028195, 2.006403169892482 }
29: 0.003484051198687024 – { -1.010801032470771, 3.001978130847099, 1.9952580349156541 }
30: 0.0023898412370680867 – { -0.9974325916102902, 2.9916225944837986, 1.9965579428146452 }
31: 0.0023469520388630623 – { -0.9932297543528832, 3.0001636221596844, 2.003783379166003 }
32: 0.0015996903945511211 – { -1.0029193454543441, 3.005575499054671, 2.0016312031018977 }
33: 0.0015581914595031179 – { -1.0040111518537587, 2.998900873968152, 1.9971793514909124 }
34: 0.001092187810937367 – { -0.9973349506022604, 2.99646504948411, 1.9994093842985032 }
35: 0.0010204343731007885 – { -0.9977895629659326, 3.001362783358045, 2.001991868792894 }
36: 7.562602877678871E-4 – { -1.0021752932736927, 3.0021230097375975, 2.00004156549925 }
37: 6.608135347784931E-4 – { -1.0010926789932362, 2.9987114502354846, 1.9986600480299779 }
38: 5.266243590574894E-4 – { -0.9983507611402258, 2.998808411816049, 2.0002100364133844 }
39: 4.250761676878849E-4 – { -0.9995617332180631, 3.0010735578812184, 2.0008591552839254 }
40: 3.658456888411364E-4 – { -1.001181145403553, 3.0006066221827323, 1.9997069824900273 }
41: 2.734574586396396E-4 – { -1.0000835479588868, 2.9991741057538785, 1.9994772303305872 }
42: 2.5202159495167143E-4 – { -0.9991949756248797, 2.999740763356903, 2.000288823352574 }
43: 1.7742097335805815E-4 – { -1.0000869991928818, 3.000598543966101, 2.0002984698349415 }
44: 1.7149962814795694E-4 – { -1.0005231243592565, 3.0000671884182473, 1.9997537962144918 }
45: 1.1701743569052388E-4 – { -0.9998489413699925, 2.999587643870243, 1.9998440232533432 }
46: 1.1506579144408666E-4 – { -0.9996768393751287, 3.0000282444793425, 2.0001923982061607 }
47: 7.877945484696116E-5 – { -1.000158420894292, 3.000270855657387, 2.0000701984764646 }
48: 7.609496204970834E-5 – { -1.0001880766860423, 2.9999330268540105, 1.9998588239049067 }
49: 5.4036561274823896E-5 – { -0.9998606313556853, 2.999830683550337, 1.9999780957582356 }
50: 4.966303948804589E-5 – { -0.9998989135938452, 3.000074859489883, 2.000098335829702 }
Gauss-Seidel
1: 0.9133323246705825 – { 2.0, 4.0, 2.375 }
2: 0.5370482587999713 – { -1.78125, 2.68125, 1.92421875 }
3: 0.14515644379647788 – { -0.7837890625000001, 3.0994140624999997, 2.0167724609374997 }
4: 0.04135938688754728 – { -1.0622863769531248, 2.969337158203125, 1.9959269714355465 }
5: 0.01214810282195747 – { -0.9816138076782226, 3.009402503967285, 2.0010706090927126 }
6: 0.0036283234663432072 – { -1.005504208803177, 2.9971257183551785, 1.9997018034160137 }
7: 0.0010935481959787462 – { -0.9983392117395995, 3.000877194322646, 2.0000862491941076 }
8: 3.3120074564415804E-4 – { -1.0005032840569037, 2.999732529243501, 1.9999744805194615 }
9: 1.0057440093472309E-4 – { -0.9998471250113465, 3.000081517200977, 2.000007649796797 }
10: 3.058434376918975E-5 – { -1.000046495948086, 2.9999751623498674, 1.9999976901317784 }
11: 9.307702714157708E-6 – { -0.9999858487737676, 3.000007566788451, 2.000000700260889 }
Gauss-Seidel (relaxed x 0.9)
1: 0.9245201395167622 – { 1.8, 3.492, 2.2639500000000004 }
2: 0.4270042780813745 – { -1.1195662500000003, 3.079656225, 1.9726086178125002 }
3: 0.022467687720140392 – { -1.0293127432734377, 2.9822758435448433, 1.996647397348342 }
4: 0.006260060648957713 – { -0.9926923971326541, 3.0009667529482544, 2.0009826712599517 }
5: 0.0011317911254494172 – { -1.0003675816404476, 3.0002519428625662, 1.999930530540778 }
6: 6.793977432935313E-5 – { -1.0001032405672245, 2.999944435374636, 1.9999885769875128 }
7: 2.0903776715188832E-5 – { -0.9999776094418797, 3.0000024221543526, 2.0000030780972344 }
8: 3.4336820312065015E-6 – { -1.00000092862928, 3.0000008488706285, 1.9999998123742984 }
4x4 example from Hestenes and Steifel's original paper from 1952
Methods of Conjugate Gradients for Solving Linear Systems
Conjugate Gradient
1: 0.3338370114665697 – { 1.4709600948241803, 0.8825760568945081, 0.4086000263400501, 0.9806400632161202 }
2: 0.011499448965563692 – { 1.0194610191440532, 0.9496580786326301, 1.0000478393811107, 1.0639090141692322 }
3: 7.706869683635796E-5 – { 1.0500178202676569, 0.9816297762195523, 1.0084050025447466, 0.9955359134386417 }
4: 6.036925315434956E-14 – { 0.99999999999985, 0.9999999999999687, 1.0000000000000204, 0.9999999999999588 }
Gauss-Seidel (relaxed x 1.75)
1: 0.8897968366970219 – { 5.25, -0.525, 2.9895833333333335, 1.0499999999999998 }
2: 0.5987936517176109 – { 6.544270833333334, -1.7722395833333335, 1.1248914930555558, 0.9626215277777778 }
3: 0.4754962719591021 – { 6.828607855902778, -0.9746808810763886, 2.6063420048466432, -0.06819303385416708 }
4: 0.3158206122818307 – { 8.220363509566694, -1.8255086721914768, 1.90118285332197, 0.8856928457001104 }
5: 0.21336103314881016 – { 7.251115233833403, -1.1766341515298517, 2.147354803209932, -0.02134701055974042 }
6: 0.09952228323445433 – { 7.725111279076356, -1.3601593743142422, 2.100974687323155, 0.5965479484918804 }
7: 0.1138215969323771 – { 6.849471143747312, -1.0420938338317531, 1.8803647347672665, 0.27284034424886977 }
8: 0.056772958278284456 – { 6.5733927440078475, -0.8607927864058869, 1.9652993325935058, 0.46514889194897147 }
9: 0.08261621763501432 – { 5.957993465542653, -0.7006050604397224, 1.7221069280048111, 0.4930147133180666 }
10: 0.06659498809717708 – { 5.384533988083842, -0.43883029565154386, 1.737242217187512, 0.5012294835560102 }
11: 0.05842554071569647 – { 4.9105278275726505, -0.3091073960514043, 1.5876389534847224, 0.6202286166422512 }
12: 0.058999109971238514 – { 4.341948104974751, -0.09169315809334852, 1.5340056488374272, 0.6090008273919469 }
13: 0.04411074248401666 – { 3.9332234121252463, 0.039212900907975995, 1.4550192585751263, 0.7031206713236741 }
14: 0.046412324896277446 – { 3.4786598154181902, 0.19334398359971294, 1.3816780022322939, 0.7178732899803022 }
15: 0.035975377250024046 – { 3.125959442278347, 0.3143090997191606, 1.3338130023236305, 0.7714247415133832 }
16: 0.03443726856777071 – { 2.7896280256921098, 0.42153123816678434, 1.2716150890841424, 0.8023619843499834 }
17: 0.028624641184294645 – { 2.50361258043195, 0.5196693760275586, 1.2348423524795453, 0.8315069011200562 }
18: 0.024836246321795773 – { 2.2592847884586886, 0.5966937852742098, 1.1911596322741254, 0.8623109480724779 }
19: 0.021531881715072042 – { 2.0425933575491326, 0.6690466471092149, 1.1607200050795696, 0.8811995754145634 }
20: 0.017751976633711752 – { 1.8655524688696596, 0.7254885836691328, 1.1319127996106402, 0.9044580306511211 }
21: 0.015455945698648627 – { 1.7096714511849482, 0.775992924962902, 1.1080529068876297, 0.9190230513637206 }
22: 0.012595534630848258 – { 1.5825734214079734, 0.8168877753376375, 1.0888775677449367, 0.9345291444286481 }
23: 0.010737936150941828 – { 1.4740724610657931, 0.851313044650663, 1.0716129586688203, 0.9460289872976945 }
24: 0.008796227532473331 – { 1.3846219478228052, 0.8800595619276526, 1.0584716824467029, 0.9560459677144983 }
25: 0.007298814055260071 – { 1.3105700731674697, 0.9033240999368831, 1.0467291761721513, 0.9645881982734051 }
26: 0.0060070299633630765 – { 1.2491848066681124, 0.9228658215882755, 1.0376320198157527, 0.9711909222188926 }
27: 0.004882894441995376 – { 1.1993529402344576, 0.9384699300914481, 1.029920592706569, 0.9771026747590404 }
28: 0.004005720463457803 – { 1.158271895912264, 0.9513853529615008, 1.0237221917778168, 0.9815648095268148 }
29: 0.0032182795690980106 – { 1.1252227616398025, 0.9617096854622419, 1.0187316616449134, 0.9854518155257223 }
30: 0.00261178680467967 – { 1.0983387603608858, 0.9700643327826931, 1.014633392204907, 0.9884718065653831 }
31: 0.002084956721552222 – { 1.0768035398590765, 0.9767590079158585, 1.011425988305217, 0.9909585709229993 }
32: 0.001667653805063536 – { 1.0595587978190686, 0.9820685859436585, 1.008801824801649, 0.9929584228123591 }
33: 0.0013233013953684643 – { 1.0458168043141518, 0.9863059015536983, 1.006761865990391, 0.9945311618948273 }
34: 0.0010429136194241634 – { 1.0349704734936782, 0.9896194290627721, 1.005128321942863, 0.995812851801 }
35: 8.201665026195576E-4 – { 1.0264062159082994, 0.9922320808064112, 1.0038555715161068, 0.9967993075952624 }
36: 6.37460458328739E-4 – { 1.0197315171078147, 0.9942543621030374, 1.0028633471860326, 0.997593711870451 }
37: 4.946579746863298E-4 – { 1.014532956610776, 0.9958205604858629, 1.0020912686219516, 0.9982031708407022 }
38: 3.790313978365103E-4 – { 1.0105324919585836, 0.9970196156761028, 1.0015035253547897, 0.9986807832715127 }
39: 2.888478402078443E-4 – { 1.0074717748104365, 0.9979284975855589, 1.0010516236369518, 0.9990476300571256 }
40: 2.1751426800742458E-4 – { 1.0051534161074123, 0.9986128944956543, 1.0007143619702814, 0.9993264078162355 }
41: 1.6187494672247947E-4 – { 1.0034187269542323, 0.9991187347889317, 1.0004613572172734, 0.9995390794941011 }
42: 1.1891426844145024E-4 – { 1.0021343690386169, 0.9994895349353989, 1.0002765063899746, 0.9996961843489321 }
43: 8.563226430824647E-5 – { 1.0012014145189654, 0.9997545295909225, 1.0001430327755507, 0.9998134187461618 }
44: 6.046311058470503E-5 – { 1.000534910093978, 0.99994027261871, 1.000048740862414, 0.9998975869970633 }
45: 4.1303425737587166E-5 – { 1.0000723825283953, 1.0000658168681467, 0.9999845559239713, 0.9999578002644673 }
46: 2.7099696079605434E-5 – { 0.9997621764693225, 1.000146653635237, 0.9999422178605739, 0.9999992842867683 }
47: 1.6603690389345797E-5 – { 0.9995652136788389, 1.0001948611976472, 0.9999165239275641, 1.0000268240750128 }
48: 9.043206091294053E-6 – { 0.9994510502910703, 1.0002193420455068, 0.9999024967225558, 1.0000442035541917 }